CS313 Theory of Computation
Referencing Curricula Print this page
| Course Code | Course Title | Weekly Hours* | ECTS | Weekly Class Schedule | ||||||
| T | P | |||||||||
| CS313 | Theory of Computation | 3 | 2 | 6 | ||||||
| Prerequisite | CS105, MATH204 | It is a prerequisite to | None |
|||||||
| Lecturer | Khaldoun Al Khalidi | Office Hours / Room / Phone | Monday: 13:00-14:30 Tuesday: 13:00-14:30 Thursday: 9:00-11:00 |
|||||||
| kalkhalidi@ius.edu.ba | ||||||||||
| Assistant | Harun Hadzo | Assistant E-mail | 230302480@student.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 | Automata, Computability and Complexity: Theory and Applications, 1/E., Elaine A. Rich, 2008. | |||||||||
| Additional Literature |
|
|||||||||
| Learning Outcomes | After successful completion of the course, the student will be able to: | |||||||||
|
||||||||||
| Teaching Methods | Class discussions with examples. | |||||||||
| Teaching Method Delivery | Face-to-face | Teaching Method Delivery Notes | ||||||||
| WEEK | TOPIC | REFERENCE | ||||||||
| Week 1 | Course introduction | |||||||||
| Week 2 | Theory of computation: The big picture | Chapters 1-4 | ||||||||
| Week 3 | Finite state machines (DFA) | Chapter 5 | ||||||||
| Week 4 | Non-deterministic finite state machines (NFA) | Chapters 5,6 | ||||||||
| Week 5 | Regular and nonregular languages | Chapter 8 | ||||||||
| Week 6 | Context-free grammars | Chapter 11 | ||||||||
| Week 7 | Pushdown automata/ Context-free and non-context-free languages | Chapter 12, 13 | ||||||||
| Week 8 | Review and Test 1 | |||||||||
| Week 9 | Turing machines, Church-Turing thesis | Chapter 17, 18 | ||||||||
| Week 10 | Halting Problem, Decidability | Chapter 19, 20 | ||||||||
| Week 11 | Analysis of complexity/NP-completeness | Chapter 27 (Also Sipser's book) | ||||||||
| Week 12 | NP-complete Reductions | Chapter 28 (Also Sipser's book) | ||||||||
| Week 13 | NP-complete Reductions | Chapter 28 (Also Sipser's book) | ||||||||
| Week 14 | Review and Test 2 | |||||||||
| Week 15 | Final Review | |||||||||
| Assessment Methods and Criteria | Evaluation Tool | Quantity | Weight | Alignment with LOs |
| Final Exam | 1 | 35 | 1,2,3,4,5 | |
| Semester Evaluation Components | ||||
| In-term Exam | 1 | 25 | 1,2,3,4,5 | |
| Quizzes | 4 | 20 | 1,2,3,4,5 | |
| Homeworks | 2 | 20 | 1,2,3,4,5 | |
| *** ECTS Credit Calculation *** | ||||
| Activity | Hours | Weeks | Student Workload Hours | Activity | Hours | Weeks | Student Workload Hours | |||
| Lecture Hours | 3 | 15 | 45 | In-term Exam study | 10 | 1 | 10 | |||
| Final exam study | 15 | 1 | 15 | Home study | 4 | 14 | 56 | |||
| Homeworks | 6 | 4 | 24 | |||||||
| Total Workload Hours = | 150 | |||||||||
| *T= Teaching, P= Practice | ECTS Credit = | 6 | ||||||||
| Course Academic Quality Assurance: Semester Student Survey | Last Update Date: 09/11/2023 | |||||||||