COMP 4804: Design and Analysis of Algorithms II

Instructor: Anil Maheshwari,

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


Term: Fall 2017 Class Hours: Mondays and Wednesdays  1005-1125 in CBY 3400
            Office Hours:  Tuesday from 10:00 to 11:30 or walk in when door is open, or send an e-mail.
            Office Hours (TA --> Darryl Hill)

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),  and some ideas on how to prove the correctness of an algorithm (induction, contradiction, ..)

Topics that will likely be covered include: Approximation algorithms for vertex cover (including FPTs), set cover, subset sum, TSP, clustering problems. Probabilistic inequalities including Markov, Chebyshev, and Chernoff. Randomized algorithms for linear programming and rounding technique, routing, BSP, min-cut, closest pair, fingerprinting, Max3SAT, load balancing, knapsack, MST. Max Flow and its applications. Data structures with amortized analysis flavor.

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

Some Journal/Conference Articles.

Course evaluation

6 Assignments: 30%

Due Date
Sept 20
Oct 04
Oct 30
Nov 08
Nov 22
Dec 06

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:

Sept 11:
Sept 13: 

Sept 18:
Sept 20: A1 Due

Sept 25:
Sept 27: 

Oct  02:

Oct  04: A2 Due

Oct  09: Thanksgiving

Oct  11: 

Oct  16:
Oct  18:

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

Nov 06:
Nov 08:  A4 Due
Nov 13:
Nov 15:
Nov 20:
Nov 22:  A5 Due
Nov 27: 
Nov 29:

Dec 04:
Dec 06: A6 Due
Dec 08: Review for Final

Contents (From Winter 2015 Term):

Jan 06 + 08:  Background Quiz
             Please have a look at all the questions of this quiz. This is an essential background material. You may review your COMP 3804 Notes. Also you can look at the Introduction Chapter in my course notes for another course
             Introduction to Randomization + Verifying Polynomial Identities + Concept of Replacement and Without Replacement Strategies. Here is a copy of lecture notes covering some of this material.
             You may also refer to - for polynomial identity testing, look at Schwartz-Zippel lemma in wikipedia (also follow the link to Lipton's blog to get a bit more insight).  For introduction to probability you can please check the wikipedia and references therein (e.g. follow the link to Britannica article or to the e-book).  An excellent source is Feller's book. You can also look at the last section of Chapter 1 of my notes for COMP 5703.

Jan 13 & 15: Assignment 1 is posted.
Standard facts from probability theory, Analyzing without replacement scenarios, Verifying Matrix Products, Mincuts.
Verification of AB=C and Confidence Boosting (Notes on this lecture). You can look at the wikipedia entry on Freivalds' algorithm or one of his paper from 1979.  Randomized Min-Cut  (Notes on this lecture). You can also look at the wikipedia entry under Karger's algorithm. or at the original paper of Karger+Stein

Jan 20 &  Jan 22:  Expected Value, Indicator Random Variables and Examples (Notes on this lecture)
             Here is a pointer to a good collection of notes on this topic.

Jan 27 & 29: Random Binary Search Trees and more on occupancy problems. (Notes on Randomized BST + An occupancy problem)
                     Assignment 1 is Due
                     Also you may have a look at qsort analysis using indicator r.v. (qsort part)
                     Some comments on Assignment 1.
                     Answer to Question 10
                     Answer to Q9 is in CLRS Book (Look at Pages 91-92 in the 3rd edition).

Feb 03 & 05: Markov's inequality and Chernoff Bounds with some applications.
                       My notes on Birthday problem and Markov's inequality
                       My notes on Chenoff Bounds and some of its applications.

                       Here is an interesting worksheet on Markov's inequality.
                       You may refer to Wikipedia article on Chernoff Bounds and especially the notes by Allistair Sinclair  referenced therein. It also includes  randomized routing which we will do in the class.
                       If you want an elegant mathematical treatment of these topics, look into the notes of Nick Harvey
                       Another good source is Chapter 19.2-19.4 of the online book of  Lehman, Leighton, Meyer
                       For proof of Chernoff Bounds you can look at my COMP 5703 Notes - Section 1.6.1

Feb 10: Test 1 (Conducted by Amin G.)
Feb 12: Introduction to Approximation Algorithms (Class taken by Ahmad Biniaz)

Feb 17 &19: Study Break

Feb 24: Talk on randomized algorithm for Closest Pair.
             Randomized Routing in Hypercubes (My notes on this part)
            You may also look at some lecture notes on this topic on the web, e.g here
            Most of the material which I took is from Motwani-Raghavan Book on Randomized Algorithms.

Feb 26:  Talk on Approximate String Matching + Routing in Hypercube Continued.

Mar 03 & Mar 05: Talks: KMP String Matching,  Infinite Object Coating, Quantum Computing.
             Routing Continued.
             Introduction to Locality Sensitive Hashing.  (Look at Chapter 7 in my ClassNotes  for another course)

Mar 10 & 12: Ahmad will take this class and continue with Approximation Algorithms.
             Talk on Entropy. Assignment 2 is Due.
             Notes on Approximation Algorithms by Ahmad

Mar 17: Talk on Randomized LP, Talk on FFT. Some more comments on LP-ILP.
Mar 19: Talk on Markov Chains. Talk on Count Min Sketcth. LSH Continued.

Mar 24 & 26: Finishing up LSH. Talks on Random Graphs and Probabilistic Methods.
                       More approximation algorithms: Set Cover
                       See my notes on approximation algorithms - many of these are not covered during the lecture, but you may be interested to see the techniques used.

Mar 31: Talks: Primality testing and  Online Algorithms ; More approximation algorithms
Apr 02: Assignment 3 is due. Solutions of tests and assignments.

Apr 07: Test 2 {Will cover all the material starting from the first day of the class, including the main ideas from the talks.)
              As requested - it will be open book/notes etc. Please do not bring computer/cell phone, but you should have a calculator.
              You can also come bit early, and if the class is unoccupied, then we can start early. We need to finish at 14:25 or sure.


  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.