Algorithm Design, Analysis & Complexity, Spring 2020
This webpage will be populated with brief descriptions of actual material covered in lectures in reverse chronological order. Slides of the evening class use the outline of lectures given by Dr. Denis Pankratov's CSC373 course given in the winter 2017 term. Slides of the day class are majorly based on slides from Kevin Wayne and in order to respect copyright they are password protected. Password will be announced in class and is allowed to be distributed and used only by students who have taken CSC373 this term. Each week will be roughly equivalent to three lectures. Our plan is to post slides when possible for a given week early or before the week and then update these slides based on the actual lecture (e.g., if some question comes up and we elabortate on the discussion). This webpage will be frequently updated. Please point out any typos to the instructors.
| Date | Description of Lecture | March 30 | Random walk algorithms for 2-SAT and k-SAT. Primality testing. Topics beyond scope of course: fine grained complexity, fixed parameter tractable problems, sublinear time algorithms, the streaming model. See Week 12 evening slides. |
|---|---|
| March 23 | Oblivious and non-oblivious local search algorithms for exact-max-k-sat. Randomized algorithms. See Week 11 Monday and Wednesday day and evening slides. | .
| March 16 | Approximation algorithms. Motivating approximation algorithms. The landscape of approximation algorithms. Strict and asymptotic approximation ratio. Online and greedy approximation algorithms. Bin packing and makespan. Unweighted and weighted vertex cover. IP/LP rounding and the integrality gap. Charging arguments for proportional weight interval scheduling, axis aligned rectangle packing and $k+1$ claw free graphs. FPTAS for the knapsack propblem. See Week 10 evening slides. Slides were updated March 19. | .
| March 9 | Linear programming. Standard matrix form. Represnting some problems as LPs. Complexity of solving an LP. Duality. Using Denis Pankratov's slides for evening slides. | .
| March 2 | Turing machines. The proof that 3SAT is NP complete. Reducing search and opotimization problems to their corresponding decision problems. Additional comments on complexity theory. See Week 8 evening slides. | .
| February 24 | Continue discuss of complexity theory and the P vs NP issue. Polynomial time reductions and transformations. The tree of polynomial transformations establishing NP completeness. See Week 7 day and evening slides. | .
| February 10 | Some concluding comments on max flow and min cut. Start complexity theory. P and NP decision problems. Polynomial time reductions and transformations. NP complete problems. See Week 6 day and evening slides. | .
| February 3 | Flow networks. The Ford Fulkerson template. The min cost-max flow theorem. Applications of max flow and min cost. See Week 5 slides day and evening slides. | .January 27 | Finishing up dynamic programming (DP). The edit distance problem. The traveling salesman (TSP) problem. RNA secondary structure, weighted maximum independent set in a tree. See Week 4 day and evening slides. | . .
| January 20 | Finishing up greedy algorithms. Dijkstra's algorithm. The greedy template revisited. Start dynamic programming. Weighted interval selection, knapsack problem, least cost problems, matric chain problem. See Week 3 day and evening slides. | .
| January 13 | Review of DFT/FFT. See CLRT text (chapter 30) and DPW text (chapter 2). Begin greedy algorithms. The greedy algorithm template. Proving optimality of a greedy algorithm. Examples: Interval scheduling/selection and interval colouring, Kruskal and Prim MST algorithm for MST, Huffman coding. See Week 2 day and evening slides. Note: Slides have been updated since they were first posted at the beginning of the week. See also greedy algorithms part 1 and greedy algorithms part 2 for Kevin Wayne slides on greedy algorithms based on Kleinberg-Tardos Chapter 4. Also see Eric Demaine's lecture notes for FFT/DFT. |
| January 6 | Introduction. Tentative schedule and organization of the course. Some introductory comments about the nature of CSC373. The divide and conquer paradigm. Some divide and conquer examples including counting inversions, closest points in Euclidean 2D, polynomial multiplication and Karatsuba integer multiplcation, Strassen's algorithm, master theorem for recurrences. See Week 1 day (with a few supplimental slides)and evening slides for the introductory comments and some examples of divide and conquer algorithms. See also divide and conquer part 1 and divide and conquer part 2 for Kevin Wayne slides on divide and conquer based on Kleinberg-Tardos Chapter 5. See CLRS, section 30.2 and/or DPV, section 2.6 for a discussion of the FFT. |
| Week no | Dates | Topic | Suggested Readings |
|---|---|---|---|
| 0 | Jan 6 | Intro | Course Contents |
| 1 | Jan 6 | Divide and Conquer | CLRS Ch 4, DPV Ch 2, KT Ch 5 |
| 2 | Jan 13 | Greedy Algorithms | CLRS Ch 16, DPV Ch 5, KT 4 |
| 3 | Jan 20 | Dynamic Programming | CLRS Ch 15, DPV Ch 6, KT Ch 6 |
| 4 | Jan 27 | Dynamic Programming | CLRS Ch 15, DPV Ch 6, KT Ch 6 |
| 5 | Feb 3 | Network Flow | CLRS Ch 26, DPV Ch 7(7.1-7.3), KT Ch 7 |
| 6 | Feb 10 | Complexity | CLRS Ch 34, DPV Ch 8, KT Ch 8 |
| 7 | Feb 17 | No Classes, Reading Week | N/A |
| 8 | Feb 24 | Complexity | CLRS Ch 34, DPV Ch 8, KT Ch 8 |
| 9 | Mar 2 | Linear Programming | CLRS Ch 29, DPV Ch 7 |
| 10 | Mar 9 | Linear Programming | CLRS Ch 29, DPV Ch 7 |
| 11 | Mar 16 | Approximation Algorithms | CLRS Ch 35, DPV Ch 9, KT 11 |
| 12 | Mar 23 | Randomized algorithms | CLRS Ch 5, DPV Ch 1, KT Ch 13 |
| 13 | Mar 30 | lRandom walk algorithms for k-SAT, primality testing, public key cryptography. Additional Topics: Fine grained complexity. Fixed parameter tractable problems. Sublinear time algorithms. The streaming model. | See references below |
| Exam Period | Cancelled due to COVID-19 |