FIT2014 · Monash University
Theory of computation
- Credit points
- 6
- Level
- 2
- Workload
- ≈ 12 h / week
- Faculty
- Information Technology
What it covers
This unit introduces formal languages, models of computation, and computational complexity. It looks at what computers can and cannot compute. Topics include finite state automata, regular expressions, grammars, pushdown automata, computable functions, Turing machines, polynomial-time reductions, complexity classes P and NP, and NP-completeness. Skills at writing formal proofs will be developed.
Assessment
| Task | Type | Weight |
|---|---|---|
| Mid-Semester Test | Quiz / Test | 20% |
| Assignment 1 | Project | 10% |
| In-Class Tests | Quiz / Test | 5% |
| Assignment 2 | Project | 10% |
| Scheduled final assessment (3 hours and 10 minutes) | Examination | 55% |
When and where
| Teaching period | Campus | Mode |
|---|---|---|
| Second semester | Malaysia | On-campus |
| Clayton | Flexible | |
| First semester | Malaysia | On-campus |
| Clayton | Flexible |