Time: MWF 3-3:50 PM
Location: Online
Instructor: Avah Banerjee
Office Hours (via zoom): MW 4-5 PM (or by appointment)
Email: banerjeeav [at] mst [dot] edu
Course website: https://www.avahbanerjee.com/cs6200.html
Course description:
This course is designed to introduce graduate students to advanced algorithm design techniques and to the current state-of-the-art. The course will balance between breadth and depth with slight emphasis given to the former. We will cover variety of different topics without spending too much time on each.
Course Outcomes:
Exposure to state of the art in algorithm research.
Learn how to select open problems.
Model challenging real world problems and develop algorithmic solutions.
Prerequisites:
Some knowledge about algorithm design techniques and analysis tools are needed (e.g. CS 5200). Some background in probability theory will be useful.
Textbooks:
There are no textbooks required for this course.
However, we will use some of the following books as reference along with lecture notes, papers and other reading materials.
1. (CLRS) T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd edition, (available online through MERLIN)
2. (ME) Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005
3. (V) Vijay Vazirani, Approximation Algorithms, Springer. Reserved.
4. (AR) Allan Borodin and Ran El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 2005
Lecture notes scribed by stundents and may contain errors. However they can be used to get an idea about the course content.
Syllabus
1. Introduction, Probability and Randomized Algorithms (3)
Reading: (CLRS) Chapter 5, (ME) Chapters 1,2,3, Chapter 6 (section 6.2, 6.3)
Lecture Note: [Lectures 1-3]
2. Greedy algorithms and Matroids and Linear Time MST
Reading: (CLRS) Section 16.1,16.2 (review), MST (Baruvka):Stanford link , CLRS Chapter 23, Matroids: CLRS 16-4, Oxley's note MST (Linear): KKT
Lecture Note: [Lecture 4], [Lecture 5],[Lecture 6]
3. Mincut: Stoer-Wagner Algorithm Slides: [PDF]
Lecture Note: [Lectures 7]
4. Maximum flow using Push Relabel (3)
Reading: (CLRS) Chapter 26.1-4
Lecture Note: [Lectures 9] , [Lectures 10]
5. Minimum cost maxflow and Matchings (3)
Reading: Stein's Slides from Columbia, Data Structures and Network Algorithms, RE Tarjan, Chapter 8.4, 9 (I will put it on reserve), Cycle canceling paper (Goldberg & Tarjan)
Lecture Note: [Lectures 11] , [Lectures 12],[Lectures 13], [Lectures 14],[Lectures 15],[Lectures 16]
6. Linear programming , Duality (3)
Reading: (CLRS) Chapter 29 (29.4 may be skipped for now), Simplex Tableau from UTD, Cycling : A pathological example (UBC)
Lecture Note: [Lectures 17],[Lectures 18],[Lectures 20]
7. NP-Completeness
Reading: (CLRS) Chapter 34
Lecture Note: [Lectures 23],[Lectures 24]
8. Approximation algorithms
Reading: (CLRS) Chapter 35, Primal-Dual (V) Chapter 12,13 and 15
Lecture Note: [Lectures 26]
9. Semi-definite programming
Reading: (V) Chapter 26
10. Online algorithms
Reading: (AR) Chapter 1, 2, Stein's Slides from Columbia
11. Local Search
Reading: Algorithm Design by Jon Kleinberg and Éva Tardos, Chpater 12, Slides
12. Polynomial Identity Testing, FFT and Fast Multiplication
Reading: CLRS, Chpater 30, PIT survey (Nitin Saxena)
13. Power of two choices and Randomized load balancing.
Reading: ME, Chpater 17
Homework
HW1 [PDF] (Lecture 1-9), [Solution] , HW2 [PDF] (Lectures 10-16), [Solution], HW3 [PDF] (Lectures 17-25),[Solution] HW4 [PDF] (Lecture 26-37),[Solution]
Grading Policy:
1. (Homework 40%): There will be 4 homework. These must be done individually.
2. Scribing (30%): Each student will scribe 3 lectures.
3. Project (30%): Can be done either individually or in a group of 2. If you can solve an open problem or improve upon an existing solution in some non-trivial way then you will automatically get an A in this course.
[Late submissions are not accepted.]
Academic Integrity
Please review S&T's Honor Code at https://stuco.mst.edu/.
Policy regarding student conduct, plagiarism etc. can be found at https://registrar.mst.edu/academicregs/
COVID-19 Policy/ Contingencies
1. Refer to https://coronavirus.mst.edu/ for up to date information and guidlines regarding COVID-19.
2. Since this is a fully online class, content, delivery of lectures, assignements will not change even if there is a campus closure.
3. If you are not able to attend this class online at any point during the semester due to COVID-19, then you should conatct the instructor immidiatley.
Accessibility and Accommodations
It is the university’s goal that learning experiences be as accessible as possible. If you anticipate or experience physical or academic barriers based on a disability, please contact Student Disability Services at (573) 341-6655, sdsmst@mst.edu, visit http://dss.mst.edu/ for information.