CS313 Theory of Computation
CS313 Theory of Computation
Syllabus | International University of Sarajevo - Last Update on Apr 04, 2026
Syllabus Quick Jump
Search and navigate to any syllabus instantly
Computer Sciences and Engineering
Babatunde Kazeem Oladejo
Course Lecturer
Course Objectives
The aims of this course are to understand basic theory of computation concepts that lies at the backbone of all state-of-the-art applications and program design. Students should understand the capabilities and limits of computation, particular applications and capabilities of deterministic and non-deterministic finite automata, context-free grammars, and finally Turing machines, as well as NP-completeness and complexity classes.
Learning Outcomes
After successful completion of the course, the student will be able to:
Course Materials
Required Textbook
Introduction to Theory of Computation, 3rd edition, Anil Maheshwari and Michiel Smid, Carleton University, 2024
Additional Literature
Introduction to the Theory of Computation, 3rd edition, Michael Sipser, Cengage Learning, 2012. Automata, Computability and Complexity: Theory and Applications, 1/E., Elaine A. Rich, 2008. Harry R. Lewis, and Christos H. Papadimitriou Prentice Hall, 2nd Edition, 1998Teaching Methods
Lectures
Class discussions
Practical examples
Homework exercises
Weekly Topics
| Week | Topic | Readings / References |
|---|---|---|
| 1 | Course introduction / Fundamentals | |
| 2 | Fundamentals / Proof techniques | Chapter 1 (Maheshwari & Smid) |
| 3 | Finite state machines (DFA) | Chapter 2 (Maheshwari & Smid) |
| 4 | Non-deterministic finite state machines (NFA); Quiz 1 | Chapter 2 (Maheshwari & Smid) |
| 5 | Regular Languages | Chapter 2 (Maheshwari & Smid) |
| 6 | Nonregular languages; Quiz 2 | Chapter 3 (Maheshwari & Smid) |
| 7 | Mid-Term Prep | |
| 8 | MID-TERM EXAM (No Tutorial due to Mid-term) | |
| 9 | Context-free grammars | Chapter 3 (Maheshwari & Smid) |
| 10 | Pushdown automata; | Chapter 3 (Maheshwari & Smid) |
| 11 | Non-context-free languages; Quiz 3 | Chapter 4 (Maheshwari & Smid) |
| 12 | Turing machines; | Chapter 4 (Maheshwari & Smid) |
| 13 | Church-Turing thesis; Quiz 4 | Chapter 5 (Maheshwari & Smid) |
| 14 | Decidability / Undecidability; | Chapter 6 (Maheshwari & Smid) |
| 15 | Final Exam Prep |
Course Schedule (All Sections)
| Section | Type | Day 1 | Venue 1 | Day 2 | Venue 2 |
|---|---|---|---|---|---|
| CS313.1 | Course | Thursday 09:00 - 11:50 | A F1.26 | - | - |
| CS313.1 | Tutorial | Friday 10:00 - 11:50 | A F1.18 - Computer Lab | - | - |
Office Hours & Room
| Day | Time | Office | Notes |
|---|---|---|---|
| Wednesday | 12:00 - 14:00 | A F2.32 | |
| Thursday | 14:00 - 16:00 | A F2.32 | |
| Friday | 09:00 - 10:00 | A F2.32 |
Assessment Methods and Criteria
Assessment Components
Final Exam
AI: Not AllowedAlignment with Learning Outcomes : 1 2 3 4 5
Mid-term Exam
AI: Not AllowedAlignment with Learning Outcomes : 1 2 5
Quizzes
AI: Not AllowedAlignment with Learning Outcomes : 1 2 3 4 5
Assignments
AI: Not AllowedAlignment with Learning Outcomes : 1 2 3 4 5
Participation
AI: Not AllowedAlignment with Learning Outcomes : 1 2 3 4 5
IUS Grading System
| Grading Scale | IUS Grading System | IUS Coeff. | Letter (B&H) | Numerical (B&H) |
|---|---|---|---|---|
| 0 - 44 | F | 0 | F | 5 |
| 45 - 54 | E | 1 | ||
| 55 - 64 | C | 2 | E | 6 |
| 65 - 69 | C+ | 2.3 | D | 7 |
| 70 -74 | B- | 2.7 | ||
| 75 - 79 | B | 3 | C | 8 |
| 80 - 84 | B+ | 3.3 | ||
| 85 - 94 | A- | 3.7 | B | 9 |
| 95 - 100 | A | 4 | A | 10 |
Late Work Policy
Information about late submission policies will be shared during class and posted in this section. Please check back for official guidelines.
ECTS Credit Calculation
📚 Student Workload
This 6 ECTS credit course corresponds to 150 hours of total student workload, distributed as follows:
Lecture Hours
45 hours ⏳ (15 week × 3 h)
Mid-term Exam study
20 hours ⏳ (1 week × 20 h)
Final exam study
25 hours ⏳ (1 week × 25 h)
Quizzes
40 hours ⏳ (4 week × 10 h)
Participation
20 hours ⏳ (10 week × 2 h)
150 Total Workload Hours
6 ECTS Credits
Course Policies
Academic Integrity
All work submitted must be your own. Plagiarism, cheating, or any form of academic dishonesty will result in disciplinary action according to university policies. When in doubt about citation practices, consult the instructor.
Attendance Policy
Students are expected to adhere to the attendance requirements as outlined in the International University of Sarajevo Study Rules and Regulations. Excessive absences, whether excused or unexcused, may impact academic performance and eligibility for assessment. Mandatory sessions (e.g., labs, workshops) require attendance unless formally exempted. For detailed policies on absences, documentation, and penalties, please refer to the official university regulations.
Technology & AI Policy
Laptops/tablets may be used for note-taking only during lectures. Phones should be silenced and put away during all class sessions. Audio/video recording requires prior permission from the instructor.
Artificial Intelligence (AI) Usage: The use of AI tools (e.g., ChatGPT, Copilot, Gemini) varies by assessment component. Please refer to the AI usage indicator next to each assessment item in the Assessment Methods and Criteria section above. Submitting AI-generated content as your own work, where AI is not explicitly allowed, constitutes an academic integrity violation.
Communication Policy
All course-related communication should occur through official university channels (institutional email or SIS). Emails should include [CS313] in the subject line.
Academic Quality Assurance Policy
Course Academic Quality Assurance is achieved through Semester Student Survey. At the end of each academic year, the institution of higher education is obliged to evaluate work of the academic staff, or the success of realization of the curricula.
Learning Tips
Be prepared to contribute thoughtfully during class discussions, labs, or collaborative work. Active participation deepens understanding and encourages critical thinking.
Complete assigned readings or prep materials before class. Take notes, highlight key ideas, and jot down questions. Aim to grasp core concepts and their applications—not just facts.
Use course frameworks or methodologies to analyze problems, case studies, or projects. Begin early to allow time for reflection and refinement. Seek feedback to improve your work.
Don’t hesitate to reach out when something is unclear. Use office hours, discussion boards, or peer networks to clarify concepts and stay on track.
Syllabus Last Updated on Apr 04, 2026 | International University of Sarajevo
Print Syllabus
Referencing Curricula Print this page
| Course Code | Course Title | Weekly Hours* | ECTS | Weekly Class Schedule | ||||||
| T | P | |||||||||
| CS313 | Theory of Computation | 3 | 2 | 6 | Thu 9:00-11:50 AM | |||||
| Prerequisite | CS105, MATH204 | It is a prerequisite to | - | |||||||
| Lecturer | Babatunde Kazeem Oladejo | Office Hours / Room / Phone | Wednesday: 12:00-14:00 Thursday: 14:00-16:00 Friday: 9:00-10:00 |
|||||||
| koladejo@ius.edu.ba | ||||||||||
| Assistant | Harun Hadzo | Assistant E-mail | hhadzo@ius.edu.ba | |||||||
| Course Objectives | The aims of this course are to understand basic theory of computation concepts that lies at the backbone of all state-of-the-art applications and program design. Students should understand the capabilities and limits of computation, particular applications and capabilities of deterministic and non-deterministic finite automata, context-free grammars, and finally Turing machines, as well as NP-completeness and complexity classes. | |||||||||
| Textbook | Introduction to Theory of Computation, 3rd edition, Anil Maheshwari and Michiel Smid, Carleton University, 2024 | |||||||||
| Additional Literature |
|
|||||||||
| Learning Outcomes | After successful completion of the course, the student will be able to: | |||||||||
|
||||||||||
| Teaching Methods | Lectures. Class discussions. Practical examples. Homework exercises. | |||||||||
| Teaching Method Delivery | Face-to-face | Teaching Method Delivery Notes | ||||||||
| WEEK | TOPIC | REFERENCE | ||||||||
| Week 1 | Course introduction / Fundamentals | |||||||||
| Week 2 | Fundamentals / Proof techniques | Chapter 1 (Maheshwari & Smid) | ||||||||
| Week 3 | Finite state machines (DFA) | Chapter 2 (Maheshwari & Smid) | ||||||||
| Week 4 | Non-deterministic finite state machines (NFA); Quiz 1 | Chapter 2 (Maheshwari & Smid) | ||||||||
| Week 5 | Regular Languages | Chapter 2 (Maheshwari & Smid) | ||||||||
| Week 6 | Nonregular languages; Quiz 2 | Chapter 3 (Maheshwari & Smid) | ||||||||
| Week 7 | Mid-Term Prep | |||||||||
| Week 8 | MID-TERM EXAM (No Tutorial due to Mid-term) | |||||||||
| Week 9 | Context-free grammars | Chapter 3 (Maheshwari & Smid) | ||||||||
| Week 10 | Pushdown automata; | Chapter 3 (Maheshwari & Smid) | ||||||||
| Week 11 | Non-context-free languages; Quiz 3 | Chapter 4 (Maheshwari & Smid) | ||||||||
| Week 12 | Turing machines; | Chapter 4 (Maheshwari & Smid) | ||||||||
| Week 13 | Church-Turing thesis; Quiz 4 | Chapter 5 (Maheshwari & Smid) | ||||||||
| Week 14 | Decidability / Undecidability; | Chapter 6 (Maheshwari & Smid) | ||||||||
| Week 15 | Final Exam Prep | |||||||||
| Assessment Methods and Criteria | Evaluation Tool | Quantity | Weight | Alignment with LOs | AI Usage |
| Final Exam | 1 | 40 | 1,2,3,4,5 | Not Allowed | |
| Semester Evaluation Components | |||||
| Mid-term Exam | 1 | 25 | 1,2,5 | Not Allowed | |
| Quizzes | 4 | 20 | 1,2,3,4,5 | Not Allowed | |
| Assignments | 2 | 10 | 1,2,3,4,5 | Not Allowed | |
| Participation | 1 | 5 | 1,2,3,4,5 | Not Allowed | |
| *** ECTS Credit Calculation *** | |||||
| Activity | Hours | Weeks | Student Workload Hours | Activity | Hours | Weeks | Student Workload Hours | |||
| Lecture Hours | 3 | 15 | 45 | Mid-term Exam study | 20 | 1 | 20 | |||
| Final exam study | 25 | 1 | 25 | Quizzes | 10 | 4 | 40 | |||
| Participation | 2 | 10 | 20 | |||||||
| Total Workload Hours = | 150 | |||||||||
| *T= Teaching, P= Practice | ECTS Credit = | 6 | ||||||||
| Course Academic Quality Assurance: Semester Student Survey | Last Update Date: 19/04/2026 | |||||||||