Algorithm Design, Analysis & Complexity, Fall 2017

Course Contents

This webpage will be populated with brief descriptions of actual material covered in lectures in reverse chronological order. Initially, I am using the outline of lectures given by Dr. Denis Pankratov's CSC373 course given in the winter 2017 term. Each week will be roughly equivalent to three lectures. This webpage will be frequently updated. Please point out any typos to the instructors.

. . . . . . . . . . .
Date Description of Lecture
December 6 Answering questions about Term Test 2, Assignment 3 and the nature and scope of the Final Exam. The remainder of the lecture considered topics not often or usually considered in an undergraduate course. Random walks and the complexity of k-SAT and SAT. Very brief discussion of Fine-grained Comlexity. Online algorithms and the KVV randomized algorithm for online bipartite matching. A randomized 1-sided error algorithm for primality/compositness testing. Fixed parameter tractable problems. Sublinear time algorithms. Streaming algorithms. See Week 12 slides .
November 29 More on the local search paradigm. Non-oblivious local search approximation for exact max-2-sat and for weighted maximum independent set in a k+1 claw free graph. More on randomized algorithms. 0-sided, 1-sided and 2-sided error randomized algorithms. Polynomial identity testing and the symbolic determinant problem. The naive randomized algorithm for exact max-k-sat. De-randomization by the method of conditional expectations. Johnson's max-say algorithm. The Buchbinder et al and van Zeulen max-sat algorithm. Start of random walks and the complexity of k-SAT. See Week 11 slides .
November 22 The local search paradigm. Local search approximation for exact max-2-sat. Local search heuristic for traveling salesman problem. Dual fitting analysis for set cover greedy algorithm approximation. Begin randomized algorithms. The why of randomized algorithms. Probability theory review. Monte Carlo vs Las Vegas randomized algorithms. Polynomial identity testing. Amplifying probability of success. Schwartz Zipple lemma. See Week 10 slides .
November 15 Discussion of Assignment 2 solutions. The why of approximation algorithms. Online and greedy approximation algorithms for the makespan and vertex cover problems. The IP/LP rounding method. Greedy algorithms for proportional profit interval selection, intersection graph of a fixed rectangle, k+1 claw free graphs, and the JISP problem using the charging method. Local search algorithms for max-cut and max-sat. See Week 9 slides .
November 1 Introduction to Linear Programming (LP). Geometric view of LP. LPs in standard form. Representing max flow and multi-commodity flow as LPs. Single source shortest path as an LP. The dual of an LP; weak and strong duality. LPs in slack form. The simplex method. See Week 8 slides .
October 25 More polynomial time transformations. Transforming Independent Set to Vertex Cover and Vertex Cover to Set Cover. Transforming Subset Sum to the Knapsack decision problem. Transforming 3SAT to 3-Coloring. Defining Turing machines (done on board). Using excoding of a non-deterministic Turing machine computation to prove that SAT is NP-hard. Some concluding remarks on complexity theory. See Week 7 slides .
October 18 Review of introduction to complexity theory. The P vs NP conjecture. Polynomial time reductions and transformations. Transforming 3SAT to Independent Set and 3SAT to Subset Sum. See Week 6 slides .
October 11 Review of some basic graph theory concepgts. Finishing up discussion of max flow-min cut and applications. Begin complexity theory and NP-completeness. See Week 5 slides .
October 4 Dynamic programming for the eidit distance problem, dynamic programming for TSP. Concluding remarks on dynamic programming. Start flow networks and applications. Note: the daytime section is discussing basic graph theory concepts and the evening section has moved directly to flow networks. We will do any necessary graph theory concepts (as needed) either in lectrues or in tutorials. See Week 4 slides .
September 27 Some concluding remarks on greedy algorithms. Dynamic programming and its characteristics. The weighted interval selection problem. The knapsack problem, an NP hard problem with an arbitrarily good approximation. Shortest path problems. The matrix chain problem. See Week 3 slides .
September 20 Finishing up divide and conquer. Randomized median and selection, the FFT. Begin Greedy algorithms. The greedy algiorithm template. The unweighted interval scheduling problem, proving optimality of earliest finishing time algorithm, greedy algorithms for the MST problem, Huffman encoding, interval coloring. See Week 2 slides .
September 13 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 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.

Tentative Course Schedule based on 373 Winter 2017 course; to be modifed as course proceeds

Week no Dates Topic Suggested Readings
0 Sept 13 Intro Course Contents
1 Sept 13 Divide and Conquer CLRS Ch 4, DPV Ch 2, KT Ch 5
2 Sept 20 Greedy Algorithms CLRS Ch 16, DPV Ch 5, KT 4
3 Sept 27 Dynamic Programming CLRS Ch 15, DPV Ch 6, KT Ch 6
4 Oct 4 Dynamic Programming CLRS Ch 15, DPV Ch 6, KT Ch 6
5 Oct 11 Network Flow CLRS Ch 26, DPV Ch 7(7.1-7.3), KT Ch 7
6 Oct 18 Complexity CLRS Ch 34, DPV Ch 8, KT Ch 8
7 Oct 25 Complexity CLRS Ch 34, DPV Ch 8, KT Ch 8
8 Nov 1 Linear Programming CLRS Ch 29, DPV Ch 7
9 Nov 8 No Classes, Reading Week N/A
10 Nov 15 Linear Programming CLRS Ch 29, DPV Ch 7
11 Nov 22 Approximation Algorithms CLRS Ch 35, DPV Ch 9, KT 11
12 Nov 29 Randomized algorithms CLRS Ch 5, DPV Ch 1, KT Ch 13
13 Dec 6 Special Topics, Exam Prep TBA
Exam Period Dec 9 - Dec 20