MATH 425: Algorithm Design and Analysis
Course Agenda (Spring 2026)
| Class | Date | Topics covered in class |
|---|---|---|
| 1 | Wed 1/21 | Getting started; syllabus, the o-notation, the O-notation, the Ω-notation, the Θ-notation, the asymptotic equivalence, |
| 2 | Fri 1/23 | Basic sums and equivalences, recurrences and the Master Method, applications of the Master Method. |
| 3 | Mon 1/26 | The Matrix Chain Multiplication Problem: a naive approach, a recursive exponential-time algorithm for the Matrix Chain Multiplication Problem, overlapping subproblems. |
| 4 | Tue 1/27 | The bottom-to-top dynamic programming approach, constructing an optimal matrix multiplication scheme, intro to the polygon triangulation problem. |
| 5 | Wed 1/28 | Solution for the convex polygon triangulation problem, dynamic programming approach to the Longest Common Substring problem. |
| 6 | Fri 1/30 | Analyzing the LCS algorithm, intro to the greedy methods, the lectures scheduling problem. |
| 7 | Mon 2/2 | The Fractional Knapsack problem and its solution with greedy, dynamic programming approach to the 0-1 version of Knapsack. |
| 8 | Tue 2/3 | Intro to matroids (definitions, examples). |
| 9 | Wed 2/4 | The matroid maximization problem and its solution with the greedy method, proof of correctness of the matroid algorithm. |
| 10 | Fri 2/6 | Review of some graph terminology, trees and forests and their properties, the cyclic matroids and maximum/minimum weight spanning trees, the algorithm of Kruskal. |
| 11 | Mon 2/9 | The unit-length task scheduling problem: problem statement, early and late tasks, canonic schedule, constructing an optimal schedule. |
| 12 | Tue 2/10 | Representation of graphs by adjacency matrices and adjacency lists, the DFS algorithm, DFS timestamps and forest. |
| 13 | Wed 2/11 | Properties of vertex labels, the White Path Theorem, characterization of DAGs in terms of back edges, DAGs and topological sort. |
| 14 | Fri 2/13 | Correctness of the Top-Sort algorithm, computing strongly connected components in digraphs. |
| 15 | Mon 2/16 | Shortest path single source problems and auxiliary statements, properties of relaxation, the Bellman-Ford algorithm. |
| 16 | Tue 2/17 | Aux statements related to the relaxation procedure. |
| 17 | Wed 2/18 | Proof of correctness of Bellman-Ford, estimating its running time, Algorithm of Dijkstra for shortest paths. |
| 18 | Fri 2/20 | Proof of correctness of Dijkstra's algorithm, estimating the running time, the all pairs shortest paths problem, the Floyd-Warshall algorithm. |
| 19 | Mon 2/23 | Computing shortest paths by the Floyd-Warshall algorithm, intro to graph coloring problems, recognig=zing bipartite graphs. |
| Tue 2/24 | No class (Workshop in Minneapolis) | |
| 20 | Wed 2/25 | Lower and upper bounds for the chromatic number of graphs, general coloring algorithm, coloring of special graph classes. |
| 21 | Fri 2/27 | Coloring planar graphs, the 4-color theorem. |
| 22 | Mon 3/2 | The 4-color theorem, intro to network flows, residual network and augmenting path, flow along an augmenting path. |
| 23 | Tue 3/3 | Improving a network flow by combining it with a one on the residual network, the Ford-Fulkerson method, cuts in networks, flow through and capacity of a cut. |
| 24 | Wed 3/4 | The Minflow-Maxcut theorem and its proof. |
| 25 | Fri 3/6 | The Edmonds-Karp algorithm, running time of the Edmonds-Karp algorithm, applications of flows: connectivity of graphs and matchings in bipartite graphs. |
| Mon 3/9 | Spring break | |
| Tue 3/10 | Spring break | |
| Wed 3/11 | Spring break | |
| Fri 3/13 | Spring break | |
| 26 | Mon 3/16 | Matchings in bipartite graphs, Hall's theorem on systems of distinct representatives and its proof by using the flows approach, applications of this theorem. |
| 27 | Tue 3/17 | Strassen's algorithm for fast matrix multiplication, the polynomial multiplication problem, the coefficient and the point-value representations of polynomials, Horner's scheme, the roots of unity and their properties. |
| 28 | Wed 3/18 | Evaluations of polynomials at complex points, the Discrete Fourier Transform. |
| 29 | Fri 3/20 | Details of the Discrete Fourier Transform. |
| 30 | Mon 3/23 | The interpolation problem, the Inverse Discrete Fourier Transform, some applications of Fourier analysis. |
| 31 | Tue 3/24 | Searching pattern in a text: naive approach, its running time, the Rabin-Karp method and its improvement with modular arithmetic. |
| 32 | Wed 3/25 | String search by using the finite state machines, the suffix function and its properties, constructing the FSM table, running the FSM search algorithm on an example, statements for the proof of correctness. |
| 33 | Fri 3/27 | Proof of correctness of the FSM-based search, intro to Computational Geometry. |
| 34 | Mon 3/30 | Discussion on the variety of special cases on examples of the segment intersection problem and intersection of rectangles. Point in polygon problem and its special cases, computing simple polygons of point sets. |
| 35 | Tue 3/31 | Computing the convex hall of a point set. |
| 36 | Wed 4/1 | Proof of correctness of the Graham Scan algorithm, convex hulls of simple polygons, lower bound for the convex hull time complexity, the alpha-shapes, the closest pair of points problem. |
| Fri 4/3 | No class (Good Friday) |