COMP 4804: Design and Analysis
of Algorithms II
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%
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
2][Q4:
Prove linearity of expectation.]
Oct 30: A3 Due + Review for Mid-Term
Nov 01: Mid-Term
Nov 06:
Nov 08:
Nov 13:
Nov 15: A4 Due
Nov 20:
Nov 22:
Nov 27: A5 Due
Nov 29:
Dec 04:
Dec 06:
Dec 08: A6 Due 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.
Announcements
- 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.
- It will be your responsibility to adhere to all
deadlines. Missing a deadline amounts to receiving a Mark of
`zer0' on that component.
- 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.
- Assignment 1 is posted on Sept 12. Due in Sept 20th
class.
- Assignment 2 is posted. Due in Oct 4th class.
- Assignment 3 is posted.
- Midterm syllabus includes all the material covered in the
classes as well as in the assignments.
- 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.