Description
Algorithm design, analysis, and correctness. Design techniques including divide-and-conquer and dynamic programming. Analysis techniques including solutions to recurrence relations and amortization. Correctness techniques including invariants and inductive proofs. Applications including sorting and searching, graph theoretic problems such as shortest path and network flow, and topics selected from arithmetic circuits, parallel algorithms, computational geometry, and others. An introduction to computational complexity, NP-completeness, and approximation algorithms. Proficiency with programming is expected as some assignments require algorithm implementation. Prerequisite: Computer Science 70 and Mathematics 55; Computer Science 81 recommended.
Cross-listed with Mathematics 168. Students taking the course as Mathematics 168 have slightly different prerequisites.