Expressivity, Complexity, and Computability

Content (tentative)

• Regular expressions
• Context-free grammars
• Models of computation: (e.g., Turing machines)
• Automata, decision problems, and relation to temporal logic
• Hard problems, satisfiability problem 3-SAT, P=NP, clique problem, problem reduction, NP-hard and NP-complete problems, algorithmic design patterns for handling NP-hard problems (DPLL, non-chronological backtracking), Mapping of Sudoku to 3-SAT, 2-SAT, constraint satisfaction problems, reduction of backtracking by heuristics (using the example of chromatic number and n-queens problems), constraint propagation, Euler circle, Euler path, Hamilton circle
• Pruning and subgraph isomorphism, Ullmann's algorithm, applications to character recognition, recognition of protein structures, etc.
• Approximation, optimal solution problem and use of approximation methods? Approximation quality of greedy methods, example: load balancing
• Limits of computation: decidability, halting problem