Subject 
Finite automata, nondeterminism and determinization, minimization, regular languages, regular expressions and their conversion from/to finite automata, Turing machines, Random Access Machines, Loop and WhilePrograms, primitive and murecursive functions, further Turingcomplete computability models, the halting problem, problem reduction, further undecidable problems.
Complexity measures, worsttime complexity and average complexity, asymptotic complexity, complexity classes; relationship between different complexity models, problem complexity, NPcomplete problems; exemplary complexity analysis of iterative and recursive algorithms, solving of sums and recurrences, analysis of randomized programs, amortised analysis.
