Embedded Files
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.
Evaluation:
Continuous Assignment - 15 Marks - Homework x 7.
Mid-Semester - 25 Marks.
End-Semester - 60 Marks.
Syllabus:
Syllabus:
- Revisit: Different Complexity analysis and Algorithm’s correctness by Loop-Invariant techniques. (1)
- Greedy Algorithms vs Dynamic Programming. (2)
- Data Structures: van Emde Boas Trees, Dynamic graphs, Bloom filters, Hashing, Union-Find Data Structure. (1+1+1+2+1 = 6)
- 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, Treaps. (1+2+1+1+1+1+1 = 8)
- 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. (1+1+1+1 = 4)
- 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. (1+1+1 = 3)
- Online Algorithms: Overview, Online scheduling and online Steiner tree, Online Bipartite matching, Online learning and multiplicative weights algorithm. (1+1+1 = 3)
- NP- Completeness - Reduction revisited; NP-Completeness proof of different problems: CLIQUE, VERTEX COVER, INDEPENDENT SET, SET COVER. (1+1+1+1 = 4)
- 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. (1+1+1+1 = 4)
- 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 Green: Not included in syllabus but will be covered.
Colored in Red: Included in syllabus but will not be covered.
Colored in Red: Included in syllabus but will not be covered.
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.
Reference Books and Materials:
6. D.E. Knuth. Art of Computer Programming (Vol. 1-Vol. 4B).
7. Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, 2nd Edition, Cambridge University press, Cambridge, MA, 1995.
8. Vijay V. Vazirani. Approximation Algorithms.
9. S. G. Akl, The Design and Analysis of Parallel Algorithms, Prentice-Hall, 1989.
10. M. J. Quinn, Designing Efficient Algorithms for Parallel Computers, McGraw Hill Higher Education, 1987, ISBN: 978-0070510715.
11. D. V. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press.
12. Dimitri P. Bertsekas and John N. Tsitsiklis, Introduction to Probability, 2nd Edition, Athena Scientific, July 2008.
13. D.E.Kozen, Design and Analysis of Algorithms.
14. J. Kleinberg and E. Tardos, Algorithm Design, Pearson.
15. N.Alon and J.H.Spencer. The Probabilistic Method.
16. D.S.Hochbaum (Editor). Approximation Algorithms for NP-Hard Problems.
17. M. Mitzenmacher and E. Upfal, Probability and Compuitng: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press.
18. J. Hromkovic. Algorithmics for Hard Problems.
19. J. Hromkovic. Design and Analysis of Randomized Algorithms.
20. T. Roughgarden, Miscellaneous Algorithm Courses.
21. Abhijit Das. Miscellaneous Algorithm Courses.
Others: NMEICT video on:
Design of Algorithms(http://www.nmeict.iitkgp.ac.in/Home/videoLink/10/3gp)
Homeworks:
Homeworks:
Class News:
17/1/25:
All lecture notes have been shared till today.
Next week first homework goes out.
Advanced Algorithms (Previous Years' Sites)
Page updated
Report abuse