CS 260 Design and Analysis of Algorithms

Course

Description

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). The course covers main approaches to design and analysis of algorithms including important algorithms and data structures, and results in complexity and computability. The main contents are: review of algorithm analysis (search in ordered array, binary insertion sort, merge sort, worst-case and average-case time complexity, minimum complexity of sorting n elements for small n, 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, way from planar graphs to Robertson-Seymour theorem);dynamic programming (chain matrix multiplication, shortest paths, edit distance, sequence alignment, extensions of dynamic programming); greedy algorithms (binary heaps, Dijkstra’s algorithm, minimum spanning tree, Huffman codes, matroids); 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 or polynomial algorithms for subproblems of NP-hard problems (set cover, vertex cover, maximum independent set, 2-SAT); partial recursive functions (theorem of Post, Diophantine equations); computations and undecidable problems (existence of complex problems, undecidability of halting problem, theorem of Rice, semantic and syntactical properties of programs).
Course period09/1/09 → …
Course level200