Syllabus

Greedy and dynamic programming algorithms; Kruskals algorithm for minimum spanning trees; the folklore algorithm for the longest common subsequence of two strings; Dijstras algorithm and other algorithms for the shortest path problem; divide-and-conqueror and checkpoint algorithms; the Hirshbergs algorithm for aligning sequences in linear space; quick sorting; the Knuth-Morrison-Pratt algorithm; suffix trees; data structures: chained lists, reference lists, hash- ing; the Chomsky-hierarchy of grammars; parsing algorithms; connections to the automaton theory; Turing-machines; complexity and intractability; complexity of algorithms; the complexity classes P and NP. 3-satisfiability, and NP-complete problems; stochastic Turing machines; the complexity class BPP; counting problems; P, P-complete; FPRAS; discrete time Markov chains; reversible Markov chains; Frobenius theorem; relationship between the second largest eigenvalue modulus and convergence of Markov chains; upper and lower bounds on the second largest eigenvalue; the Sinclair-Jerrum theorem: relationship between approximate counting and sampling.