Advanced Algorithms (CSE 617) 2023-24
Mon: 11AM - 12PM. Thu: 9AM - 10AM. Fri: 10AM - 11AM.
Class overview
This is a depth elective course. Both CSE and ECE students are sitting in the class. We will cover a few advanced topics in polynomial time algorithms and data structures, learn about NP-complete problems and apply approximation algorithms to solve those problems in polynomial time among other topics like randomized algorithms etc.
Students should have an inclination towards Mathematics and problem solving.
Syllabus:
Revisit: Different Complexity analysis and Algorithm’s correctness by Loop-Invariant techniques.
Algorithm Design Techniques: Divide-and Conquer, Greedy Algorithms, Dynamic Programming, Solving Problems by Graph Search, DFS, BFS, Backtracking, Branch-and-Bound.
Data Structures: van Emde Boas Trees, Dynamic graphs, Bloom filters, Hashing, Union-Find Data Structure.
Randomized Algorithm- Las Vegas and Monte Carlo algorithms, Essential mathematical tools for Randomized algorithms: Linearity of expectation, Markov inequality, Chebyshev's inequality, Chernoff bound, and Union bound with examples to Randomized algorithm design. Examples and analysis of: Hiring Assistant Problem, Randomized selection, Min-cut Problem, Primality testing, Skip list.
Network Flow and Matching- Flow networks, Augmenting paths, Ford- Fulkerson Algorithm, Edmonds - Karp algorithm, Max flow min-cut theorem, Push-relabel algorithm, Maximum bipartite matching, Some applications of network flow. Stable Matching
Linear Programming: Introduction, algorithms, and its applications, Linear programming duality.
Parallel Algorithms – Multithreaded Algorithms: Multithreaded matrix multiplication, Multithreaded merge sort. Introduction, PRAM algorithms: Prefix computation, List Ranking, Selection, Merging, Sorting.
Online Algorithms: Overview, Online scheduling and online Steiner tree, Online Bipartite matching, Online learning and multiplicative weights algorithm.
NP- Completeness - Reduction revisited; NP-Completeness proof of different problems: CLIQUE, VERTEX COVER, INDEPENDENT SET, SET COVER.
Approximation Algorithms - Constant factor approximation algorithm: VERTEX COVER and TSP; Christofides algorithm on TSP with 1.5 approximation factor; SET-COVER problem with log n factor approximation algorithm; PTAS and FPTAS, Linear programs and approximation algorithms.
Semidefinite Programming: Introduction with the problem: The Maximum Cut Problem and Semidefinite Programming.
Overview of some Special Topics: Communication complexity, Spectral graph theory, Compressive sensing .
Colored in Green: Not included in syllabus but will be covered.
Colored in Red: Included in syllabus but will not be covered.
Evaluation:
Continuous Assignment - 15 Marks - In-class Assignment x 7 and Homework x 8.
Mid-Semester - 25 Marks. (Syllabus: Chapters 1, 2, 3 and 5).
End-Semester - 60 Marks. (Syllabus: All the topics covered in class).
Text Books:
1. Thomas H. Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 4th Edition..
2. Jeff Ericson. Algorithms.
3. T. Roughgarden. Algorithms Illuminated (Part I-Part IV).
4. Horowitz, Sahni and Rajasekaran. Fundamentals of Computer Algorithms.
5. M.H. Alsuwaiyel. Algorithms - Design Techniques and Analysis.
6. Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, 2nd Edition, Cambridge University press, Cambridge, MA, 1995.
7. Vijay V. Vazirani. Approximation Algorithms.
8. S. G. Akl, The Design and Analysis of Parallel Algorithms, Prentice-Hall, 1989.
9. M. J. Quinn, Designing Efficient Algorithms for Parallel Computers, McGraw Hill Higher Education, 1987, ISBN: 978-0070510715.
10. D. V. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press.
Reference Books and Materials:
1. D.E. Knuth. Art of Computer Programming (Vol. 1-Vol. 4B).
2. Dimitri P. Bertsekas and John N. Tsitsiklis, Introduction to Probability, 2nd Edition, Athena Scientific, July 2008.
3. D.E.Kozen, Design and Analysis of Algorithms.
4. J. Kleinberg and E. Tardos, Algorithm Design, Pearson.
5. N.Alon and J.H.Spencer. The Probabilistic Method.
6. D.S.Hochbaum (Editor). Approximation Algorithms for NP-Hard Problems.
7. M. Mitzenmacher and E. Upfal, Probability and Compuitng: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press.
8. J. Hromkovic. Algorithmics for Hard Problems.
9. J. Hromkovic. Design and Analysis of Randomized Algorithms.
10. T. Roughgarden, Miscellaneous Algorithm Courses.
11. Abhijit Das. Miscellaneous Algorithm Courses.
Others: NMEICT video on:
Design of Algorithms(http://www.nmeict.iitkgp.ac.in/Home/videoLink/10/3gp)
Previous Years' Question Papers:
2022-23 [Midsem |Alternate Midsem|Endsem]
Class News (2023-24):
11/1/24:
There will be an extra class on Monday (15/1/24) from 2PM to 3PM.
The first in-class assignment will be held on Friday (19/1/24).
The first homework will be published on or before Monday (22/1/24).
So far I have used text books 1 and 5 only.
I need a class-photo for this site. Somebody email me a photo ASAP.
16/1/24:
Homework 1 has been uploaded, deadline of submission is 29th January.
Study materials for classes 1-7 will be uploaded soon. have been handed over.
29/1/24:
Submit HW1 to Rimpa (CSE main building, 2nd Floor, L-shaped lab) today by 6PM.
In-class assignment II will be held next Thursday (8/2/24) Monday (5/2/24) 2PM-3PM.
31/1/24:
Homework 2 has been uploaded, deadline of submission is 16th February.
1/2/24:
Study materials on "Algorithm Design Techniques" have been emailed to CR.
For classes 8-12 text books 1,2 and 4 have been used.
There will be an extra class on Monday (5/2/24) 2PM-3PM in LG21, in-class assignment II will be held then.
8/2/24:
There will be an extra class on Monday (12/2/24) from 2PM to 3PM 4PM to 5PM in LG13.
12/2/24:
Today's extra class is postponed to 4PM. So, class will be held from 4PM to 5PM in LG13 today.
I have shared the study materials on "Network Flow and Stable Matching" with the CR.
In-class assignment III will be held this Friday (16/2/24) from 10AM to 11AM.
Homework 3 is now online. Flexible deadline of submission is, 8th March 2024 (Friday).
For classes 13-16 text books 1, 2 and reference materials from 11 have been used.
25/2/24:
Hope you had a good midsem, classes start from Monday (26/2/24) again.
You can submit your homeworks anytime during the semester (last date will be mentioned).
Try to solve the homework-problems yourself before turning to the internet (these are a bit advanced that's why the extra time).
26/2/24:
There will be an extra class today (26/2/24) in LG13 from 2PM to 3PM.
21/3/24:
Online algorithms will not be covered.
I need to take 15 classes in April. So there will be 5 class per week in April.
In-class assignment IV will be held on 1st April (Monday) from 11AM to 12PM on randomized algorithms.
Alternate midsem exam will be held on 27th March, 3PM-4.30PM in L-shaped lab, 2nd floor, CSE main building.
22/3/24:
From April 1st to April 19th (3 Weeks) there will be five classes per week. Mon: 11-12, Mon: 2-3, Thu: 9-10, Fri: 10-11 and Fri: 1-2.
Study materials on "Randomized Algorithms" have been sent to Ritika.
1/4/24:
In-class assignment V will be held on 5th April (Friday) from 1PM to 2PM on parallel algorithms in LG13.
Follow text book 4 for the topic parallel algorithms, study materials will be shared at the end of the topic.
Homeworks 4 and 5 will be uploaded soon.
Positively submit all your homeworks on or before 5th May to Radhika/Rimpa or marks will not be added for the homeworks part.
5/4/24:
In-class assignment V is to be held today from 1PM to 2PM in LG13/LH13.
Midsem/Alternate midsem answer-scripts will be shown only today 12PM-1PM and Monday 12PM-2PM.
Positively submit all your homeworks on or before 5th May to Radhika/Rimpa or marks will not be added for the homeworks part.
7/4/24:
Study materials on parallel algorithms are shared with Ritika.
Next week's classes will NOT be online.
Tomorrow (Monday) I shall take two classes: 11AM-12PM and 2PM-3PM.
Rest of the homeworks will be uploaded soon.
8/4/24:
Due to the suspension of classes and holiday, the two classes of this week will be held on Friday (12/4/24), 10AM-11AM and 1PM-2PM.
Answer-scripts will be shown next Monday (15/4/24) 12PM-2PM only instead of today.
10/4/24:
Homeworks 4 through 8 have been uploaded.
In-class assignment VI will be held on 15th April (Monday) 2PM-3PM in LG13.
Positively submit all your homeworks on or before 5th May 6th May (Monday) to Radhika/Rimpa or marks will not be added for the homeworks part.
15/4/24:
Study materials on P, NP and NP-complete have been shared with Ritika.
Last in-class assignment (in-class assignment VII) on approximation algorithms will be held on 19/4/24 (Friday) 1PM to 2PM in LG13.
19/4/24:
Study materials on approximation algorithms have been sent to Ritika.
In-class assignment VII will be held today 1PM to 2PM.
Positively submit all your homeworks on or before 5th May 6th May (Monday) to Radhika/Rimpa or marks will not be added for the homeworks part.
All the best for the exams!