An investigation of algorithmic paradigms: divide and conquer, dynamic programming, greedy algorithms, graph algorithms, randomized algorithms, undecidability; NP-completeness, approximation algorithm, sorting lower bound, selected topics from amortized analysis, network flow, and linear programming. Three lecture hours and one hour of discussion a week for one semester. Only one of the following may be counted: Computer Science 331, 331H, 357, 357H, 378 (Topic: Algorithms and Complexity). Offered on the letter-grade basis only. Prerequisite: The following coursework with a grade of at least C-: Computer Science 311, or 311H, (or 313H or 313K); Computer Science 314, or 314H, (or 307, 315, or 315H); Computer Science 429, or 429H, (or 310 or 310H); Mathematics 362K, or Statistics and Data Sciences 321, (or Statistics and Scientific Computation 321); and credit with a grade of at least C- or registration for Mathematics 340L, or Statistics and Data Sciences 329C, (or Statistics and Scientific Computation 329C); and consent of the honors director.
Core - Theory