-
This is the second, in a two-course sequence about some of the fundamental data structures, algorithms, problems, and paradigms of computing.
-
A major theme of this course is algorithm paradigms. A paradigm transcends any single problem and serves as a more general program model.
-
Another major theme is combinatorial search and optimization. Many of the problems that we'll study are considered to be classics of the genre, often arising from puzzles and games.
-
Here's a superset of the topics covered in this course.
-
At the conclusion of this course, students will be able to recognize, and discover, divide-and-conquer algorithms; greedy programs; dynamic programming algorithms; randomized algorithms and Monte Carlo simulations; backtracking algorithms; several modern heuristic methods, such as genetic programs, simulated annealing, and ant colony optimization; and algorithms for computational geometry (time-permitting).
-
Students will also be familiar with specific algorithms for a wide range of classic and practical problems, such as: arithmetic and number-theoretic algorithms; minimization/maximization of functions; fast (or otherwise interesting) matching, longest common subsequence, edit distance, and compression of strings; self-balancing data structures, and structures for union-find; generating combinatorial objects (e.g., permutations, combinations, integer and set partitions, Ramsey partitions, random graphs); network flows and maximum matchings; algorithms on graphs, e.g., connectivity and traversal, shortest paths, spanning trees; and algorithms for cake-cutting and fair division.
Visit the class Website to learn more.