COMP 4804: Design and Analysis of Algorithms II

Instructor: Anil Maheshwari,
Office:  Room 5125bHP, Herzberg Building,
              School of Computer Science, Carleton University, Ottawa, Canada K1S 5B6,

E-mail: anil@scs.carleton.ca
www:    http://www.scs.carleton.ca/~anil

Term: Fall 2017 Class Hours: Mondays and Wednesdays  1005-1125 in CBY 3400

Office Hours:  Tuesday from 09:00 to 11:30 or walk in when the door is open, or send an e-mail. (It is likely that some Tuesdays the office hour may be more busy with COMP 3801 students. I have given them slot from 10-11:30. It is advisable to please come early around 9AM on Tuesdays (Thanks)).
                        
Teaching Assistant: Darryl Hill
                                   Office Hours: Mondays and Wednesdays from 13:00-14:00 in HP 4125.
                                  
Course Prerequisite: COMP 3804   (Preferably with high grades)
What is it about (a.k.a. Calender description):
A second course on the design and analysis of algorithms. Topics include: advanced recurrence relations, algebraic complexity, advanced graph algorithms, amortized analysis, algorithms for NP-complete problems, randomized algorithms.

Focus will be on the last three topics, likely in the reverse order. Course will require proofs - most often including probability. You should be familiar with basic graph algorithms (dfs, bfs, MST, SSSP),  basic data structures (dynamic trees, heaps, order statistics), analysis of algorithms (recurrences, substitution),  some ideas on how to prove the correctness of an algorithm (induction, contradiction, ..), basic probability - conditional probability, expected value, birthday problem, indicator r.v., etc. For your reference, final exams for COMP 2804 and COMP 3804 are provided as Assignment 0 for a quick refresher.

Topics that will likely be covered include: Approximation algorithms for:  vertex cover (including FPTs and rounding method for weighted vertex cover), TSP, load balancing in identical machines, set cover, k-center clustering,  subset sum, knapsack. Probabilistic inequalities including Markov, Chebyshev, and Chernoff. Randomized algorithms for:
verifying polynomial identity and matrix multiplication, Minimum Spanning Trees, Minimum Cut, Binary Search Trees, Occupancy Problems (Balls & Bins), Closest Pair, Binary Space Partition, Set Balancing and Routing. Data structures favoring amortized analysis.
Course Text Book:
Main: Kleinberg/Tardos's Algorithm Design (Addison-Wesley 2005),
Secondary: Cormen et al. (CLRS) Algorithms (MIT Press 2009), and  Dasgupta, Papadimitriou, Vazirani's  Algorithms (McGraw 2007).
I have some  ClassNotes  for another course, and may land up touching some material from there.

Likely some Research Papers that will be outlined in the class - most of them should be available from our Library.

Course References:
(Leighton) F.T. Leighton, "Introduction to parallel architectures and algorithms", Morgan Kaufman.
(Knuth) D.E. Knuth, "The art of computer programming", Vol. 1,2,3  Addison-Wesley.
(Kozen) Dexter Kozen, "The design and analysis of Algorithms", Springer 1992
(Tarjan) Robert Tarjan, " Data structures and algorithms", SIAM Press.
(Motwani/Raghavan) R. Motwani and P. Raghavan, "Randomized Algorithms".
(CLRS) Introduction to Algorithms, Cormen Leiserson Rivest and Stein (3rd Edition)
(Dasgupta, Papadimitriou, Vazirani. "Algorithms", McGraw.
(MU) Mitzenmacher and Upfal, "Probability and Computing" Cambridge 2005
(WS) Williamson and Shymos, The design of approximation algorithms, 2010

Some Journal/Conference Articles.

Course evaluation: 

- 6 Assignments: 30%

Assignment

Due Date
Zero
 COMP-2804 Old Final COMP-3804 Old Final
 Never
I
 A1.pdf   A1.tex
 Sept 20
II
 A2.pdf   A2.tex
 Oct 04
III
 A3.pdf A3.tex
 Oct 30
IV
 A4.pdf  A4.tex
 Nov 15
V
 A5.pdf  A5.tex
 Nov 27
VI
 A6.pdf   A6.tex
 Dec 08

Note: All Assignments are due at the start of the class. Solutions will be provided in the class.

- Quizzes: 10%
  During the class - expect about one quiz/week and they will be without any advance notice as they depend on the coverage of the topics.

- Mid-Term: 20%
  In Class on Nov 01.

- Final Exam: 40%
  Date and Location are announced by the Examination Services

(Note: To pass the course you need to obtain at least 50% Marks in the Final Exam AND at least 50% Marks overall.) 

Plan for Fall 2017

Sept 06: Course Logistics. What will we see in this course? Approximation Algorithms for (Weighted) Vertex Cover in a Graph.

Sept 11: Approximation algorithms for Vertex Cover, Weighted Vertex Cover, [Look into Wikipedia page on Vertex Cover and references therein. Chapter 11 of the Textbook.
Sept 13: FPT for Vertex Cover [1], A Load Balancing Problem [See 1 2] + Chapter 11 of the Textbook.

Sept 18:  TSP [See 1] (Q1: 3/2 approximation for greedy load balancing after sorting.)
Sept 20: A1 Due, Short discussion on solutions for questions in the Assignment, 3/2 approximation to TSP, Approximation algorithm for Set Cover (and its connection to the Hospital Optimization problem) 

Sept 25: Approximating Set Cover (1) and Exact Subset Sum.
Sept 27: Approximating Subset Sum (Section 35.5 of CLRS) + Clustering Problem (Q2: Why is the value returned by the exact subset sum is optimal.)

Oct  02: Clustering + Largest independent set of squares
Oct  04: A2 Due, Approximating Knapsack (Section 3.1 of WS book)

Oct  09: Thanksgiving
Oct  11: Finishing the FPTAS for knapsack + Randomized Algorithms - an Intro (Consult Chapter on Probability for CS in ClassNotes)

Oct  16: Randomized algorithms for Verification (Polynomial, Matrix [1] [2], Strings)
Oct  18: Min-Cut (See 1  2 ) and Max-SAT [1 (Skip De-randomization)  2][Q4: Prove linearity of expectation.]

Oct 30: A3 Due + Review for Mid-Term
Nov 01: Mid-Term

Nov 06:  Weighted MAXSAT (Algorithm I: Simple Random Assignment, Algorithm II: ILP->LP relaxation-> Randomized Rounding)
Nov 08:  Weighted MAXSAT (Analysis + New algorithm that combines Algorithm I & II ), Randomized Load Balancing
 
Nov 13: Chernoff Bounds (Consult my notes) with some simple examples. Randomized Routing.
Nov 15: A4 Due. Hypercubes and 2-phase randomized routing algorithm in Hypercubes [1   2]
 
Nov 20: Finishing Routing + Randomized MST (Consult my course notes).
Nov 22:  Randomized MST [KKT Paper]   + Some Applications of Chernoff Bounds

Nov 27:  A5 Due Finishing the proof of Lemma on the expected number of light edges [Timothy Chan Paper]
Nov 29: Closest Pair Problem [1].  Binary Space Partition

Dec 04: BSP Partition [1  2]. Finding Smallest Enclosing Disc for a set of points in plane [1  2].
Dec 06: Smallest Enclosing Discs contd. Applications of Chernoff Bounds.
Dec 08: A6 Due Review for Final. Solutions to some problems from Assignments 6 and 4.

Dec 14: FINAL EXAM TB 206 at 2PM.

Announcements
  1. All the Carleton's standard rules on Equity, Students with special needs, Plagiarism, Academic Integrity etc. hold for this course. All these matters will be handled by appropriate authorities. You should look into the relevant university publications, and if you have questions regarding any of this, you can ask the School of Computer Sciences Administrative Staff. 
  2. It will be your responsibility to adhere to all deadlines. Missing a deadline amounts to receiving a Mark of `zer0' on that component.
  3. All assignments are due at the beginning of the class. The solutions of the assignment will likely be provided (in class on the board) on the due date.
  4. Assignment 1 is posted on Sept 12. Due in Sept 20th class.
  5. Assignment 2 is posted. Due in Oct 4th class.
  6. Assignment 3 is posted.
  7. Midterm syllabus includes all the material covered in the classes as well as in the assignments.
  8. I am away Oct 30- Nov3. Darryl will take Monday Oct 30th class and will go over the solutions of Assignment 3 and possibly a few more problems. He will also conduct the midterm on Nov 1st.
  9. Have a nice break and good luck for 2018.
 
http://www.scs.carleton.ca/~maheshwa