Theory of Algorithms

Pattern matching: naive algorithm, the fingerprinting method of Rabin and Karp, solution by finite automata.

Deterministic and non-deterministic finite automata and their equivalence. Regular expressions, regular languages, and their connections to finite automata. Finite automaton as lexical analyser.

Context free grammars. Parse tree, left and right derivation. Ambiguous words, grammars, languages. The importance of unambiguous grammars for algorithms.

Pushdown automaton. Connection between pushdown automata and context free grammars, how to get a PDA from a CF grammar. The main task of a parser.

The general automaton: Turing machine.  Church-Turing thesis. The classes  P, NP, coNP, their relations. Karp reduction and the notion of NP completeness.

Theorem of Cook and Levin. 3SAT, 3COLOR are NP complete languages.

Further NP complete languages: MAXSTABLE, HAM-CYCLE, HAM-PATH, TSP,  3DH, SUBSETSUM, PARTITION, KNAPSACK, SUBGRAPHISO. The problem of GRAPHISO.

 Linear and integer programming. LP is in P (without proof), IP is in NP. LP and IP as algorithmic tools, translation of combinatorial problems to integer programming. Another tool: branch and bound.

Dynamical programming (example: knapsack, longest common substring).

The objective in approximation algorithms. Bin packing has fast and good approximations (FF, FFD, theorem of Ibarra and Kim). Fro the TSP even the approximation s hard in general but there is efficient 2-approximation in the euclidean case.

Comparison based sorting: bubble sort, insertion sort, merge sort, quick sort. Lower bound for the number of comparisons. Other sorting methods: counting sort, bin sort, radix sort.

 Linear and binary search. The binary search is optimal in the number of comparisons. Notion of search tree, their properties and analysis.

Red-black tree as a balanced search tree. The 2-3 tree, and its generalization, the B tree. Comparisons of the different data structures.