CS35E - Theory of Computing II |  |
This course uses the following course codes:
- COMP 3600
- CS35E
Number of credits: 4
This course has the following prerequisites:
This course has no corequisites.
The assessment for the course is as follows:
This course has coursework assessment.
In course assignments weight: 25%
Final exam: 75%
Course syllabus
- Turing machines
Computing with Turing machines Extensions of Turing machines Nondeterministic Turing machines. Grammars
- Undecidability
The Church-Turing Thesis. The halting problem. Unsolvable problems
- Computational complexity
Classes P and NP. NP-completeness.
- Special topics
Methods of tackling NP-hard problems
