AMCS 260 Design and Analysis of Algorithms



Review of algorithm analysis (search in ordered array, binary insertion sort, merge sort, 2-3 trees, asymptotic notation). Divide and conquer algorithms (master theorem, integer multiplication, matrix multiplication, fast Fourier transform). Graphs (breadth-first search, connected components, topological ordering, depth-first search). Dynamic programming (chain matrix multiplication, shortest paths, edit distance, sequence alignment). Greedy algorithms (binary heaps, Dijkstra's algorithm, minimum spanning tree, Huffman codes). Randomized algorithms (selection, quick sort, global minimum cut, hushing). P and NP (Cook's theorem, examples of NP-complete problems). Approximate algorithms for NP-hard problems (set cover, vertex cover, maximum independent set). Partial recursive functions (theorem of Post, Diophantine equations). Computations and undecidable problems (undecidability of halting problem, theorem of Rice, semantic and syntactical properties of programs).
Course period09/1/09 → …
Course level200