MATH 425: Algorithm Design and Analysis
Course Agenda (Spring 2024)
| Class | Date | Topics covered in class |
|---|---|---|
| 1 | Wed 1/24 | Getting started; syllabus, the o-notation, the O-notation. |
| 2 | Fri 1/26 | The Ω-notation, the Θ-notation, the asymptotic equivalence, basic sums and equivalences, recurrences and the Master Method. |
| 3 | Mon 1/29 | Applications of the Master Method, intro to the Matrix Chain Multiplication problem. |
| 4 | Tue 1/30 | The Matrix Chain Multiplication Problem: a naive approach, a recursive exponential-time algorithm for the Matrix Chain Multiplication Problem, overlapping subproblems. |
| 5 | Wed 1/31 | The bottom-to-top dynamic programming approach, constructing an optimal matrix multiplication scheme, intro to the polygon triangulation problem. |
| 6 | Fri 2/2 | Solution for the convex polygon triangulation problem, dynamic programming approach to the Longest Common Substring problem. |
| 7 | Mon 2/5 | Analyzing the LCS algorithm, intro to the greedy methods, the lectures scheduling problem. |
| 8 | Tue 2/6 | The Fractional Knapsack problem and its solution with greedy, dynamic programming approach to the 0-1 version of Knapsack. |
| 9 | Wed 2/7 | Intro to matroids (definitions, examples). |
| 10 | Fri 2/9 | The matroid maximization problem and its solution with the greedy method, proof of correctness of the matroid algorithm. |
| 11 | Mon 2/12 | Review of some graph terminology, trees adns forests and their properties. |
| 12 | Tue 2/13 | The cyclic matroids and maximum/minimum weight spanning trees, the algorithm of Kruskal. |
| 13 | Wed 2/14 | The unit-length task scheduling problem: problem statement, early and late tasks, canonic schedule, constructing an optimal schedule. |
| 14 | Fri 2/16 | Representation of graphs by adjacency matrices and adjacency lists, the DFS algorithm, DFS timestamps and forest. |
| 15 | Mon 2/19 | Properties of vertex labels, the White Path Theorem, characterization of DAGs in terms of back edges, DAGs and topological sort. |
| 16 | Tue 2/20 | Correctness of the Top-Sort algorithm, computing strongly connected components in digraphs. |
| 17 | Wed 2/21 | Shortest path single source problems and auxiliary statements, properties of relaxation, the Bellman-Ford algorithm. |
| 18 | Fri 2/23 | Proof of correctness of Bellman-Ford, estimating its running time. |
| 19 | Mon 2/26 | Algorithm of Dijkstra for shortest paths, proof of correctness of Dijkstra's algorithm, estimating the running time, the all pairs shortest paths problem. |
| 20 | Tue 2/27 | The Floyd-Warshall algorithm, intro to graph coloring problems, lower and upper bounds for the chromatic number of graphs. |
| 21 | Wed 2/28 | Recognizing bipartite graphs, general coloring algorithm, coloring of special graph classes. |
| 22 | Fri 3/1 | Coloring of planar graphs. |
| 23 | Mon 3/4 | The 4-color theorem, intro to network flows, residual network and augmenting path, flow along an augmenting path. |
| 24 | Tue 3/5 | 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, intro to the Minflow-Maxcut theorem. |
| 25 | Wed 3/6 | Proof of Minflow-Maxcut theorem, the Edmonds-Karp algorithm, running time of the Edmonds-Karp algorithm. |
| 26 | Fri 3/8 | Applications of flows: connectivity of graphs. |
| Mon 3/11 | Spring break | |
| Tue 3/12 | Spring break | |
| Wed 3/13 | Spring break | |
| Fri 3/15 | Spring break | |
| 27 | Mon 3/18 | Matchings in bipartite graphs, Hall's theorem on systems of distinct representatives and its proof by using the flows approach, applications of this theorem. |
| 28 | Tue 3/19 | 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. |
| 29 | Wed 3/20 | Evaluations of polynomials at complex points, the Discrete Fourier Transform. |
| 30 | Fri 3/22 | Details of the Discrete Fourier Transform. |
| 31 | Mon 3/25 | The interpolation problem, the Inverse Discrete Fourier Transform, some applications of Fourier analysis. |
| 32 | Tue 3/26 | Searching pattern in a text: naive approach, its running time, the Rabin-Karp method and its improvement with modular arithmetic. |
| 33 | Wed 3/27 | String search by using the finite state machines, the suffix function and its properties, constructing the FSM table. |
| Fri 3/29 | No class (Good Friday) | |
| 34 | Mon 4/1 | Constructing the FSM table on an example, running the FSM search algorithm on an example, statements for the proof of correctness. |
| 35 | Tue 4/2 | Proof of correctness of the FSM-based search, intro to Computational Geometry. |
| 36 | Wed 4/3 | 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. |
| 37 | Fri 4/5 | Computing the convex hall of a point set. |
| 38 | Mon 4/8 | 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. |
| 39 | Tue 4/9 | Computing the closest pair of points in O(n*log(n)) time. |
| 40 | Wed 4/10 | The diameter of a point set problem, lower bound for its complexity, the rectangles windowing problem and the involved algorithm and data structures. |
| 41 | Fri 4/12 | The point object labeling problem, clipping polygons, NURBs, intro to the complexity, the formal language framework, the class P. |
| 42 | Mon 4/15 | The verification algorithms, the class NP and its relations to class P, polynomial-time reducibility, NP-hard problems, NP-complete problems, properties of the class NPC, two approaches to the class NP (oracle-based and unlimited parallelism), discussion on problem reduction. |
| 43 | Tue 4/16 | General approach to establish the NP-completeness, the SAT problem and Cook's theorem, reduction of SAT to 3-SAT. |
| 44 | Wed 4/17 | Completing reduction of SAT to 3-SAT, reduction of 3-SAT to CLIQUE, the Vertex Cover problem, polynomial reduction of CLIQUE to VertexCover. |
| Fri 4/19 | No class | |
| 45 | Mon 4/22 | The PARTITION problem, reduction of VC to PARTITION. |
| 46 | Tue 4/23 | Reduction of HamiltonianCycle problem to TSP, reduction of 3-SAT to 3-COLORING. |
| 47 | Wed 4/24 | Intro to Max2SAT problem, translation to a graph-theoretic problem. polynomial algorithm for solving the 2-SAT, the MAX-2-SAT problem, reduction of 3-SAT to MAX-2-SAT. |
| 48 | Fri 4/26 | Intro to approximation algorithms, 2-approximation algorithm for the Vertex Cover problem (VC), a 2-approx. algorithm for the Traveling Salesman Problem (TSP). |
| 49 | Mon 4/29 | Non-approximability of TSP with a constant rate, approximation algorithms for the task scheduling, the Graham algorithm. |
| 50 | Tue 4/30 | The LPT rule in scheduling algorithm, a deeper analysis of the LPT rule approximation rate, intro to the Set-Cover problem. |
| 51 | Wed 5/1 | Approximation algorithm for Set-Cover problem, intro to Max_Set_Cover problem. |
| 52 | Fri 5/3 | Maximum Set-Cover Problem and its approximation algorithm, Independent sets in graphs and its relation to the VC problem. |
| 53 | Mon 5/6 | Approximation algorithm for coloring 3-colorable graphs, intro to PTAS. the Subset-Sum problem, an exponential-time algorithm for finding an exact solution, trimming procedure, a PTAS for the Subset-Sum problem, estimation of its approximation rate and running time. |
| 54 | Tue 5/7 | Approximation algorithms for the Weighted Independent Set and Weighted Vertex Cover problems, intro to randomized algorithms: 3-CNF-SAT. |
| 55 | Wed 5/8 | Randomized approximation algorithm for max 3-CNF-SAT, general CNF-SAT problem, formulating CNF-SAT as IP problem, approximating IP with LP. |
| 56 | Fri 5/10 | Intro to Monte-Carlo and Las-Vegas algorithms, course review. |