Advanced Algorithms

Course material

Date

Contents

Slides

Addl material

Scribed by

Scribes

3.1

Introduction, Subset sum

 

[Exercises]

 

 

5.1, 7.1

Dynamic Programming:  longest common subsequence, matrix chain multiplication

 

 

 

 

10.1

Divide & conquer: selection, polynomial multiplication

 

 

 

 

17.1, 24.1

Max-flow: introduction, Ford-Fulkerson, max-flow min-cut theorem, FF non-termination example

 [1], [2]

 [1]

Nikhil Sawant, Shamsher Singh/ Mayank Joshi

Slides/Slides

24.1

Distance labels, Augmenting along shortest path

 [1], [2]

 

 

 

28.1

Preflow-Push algorithm

 [1], [2]

 

Aditi Kapoor, Nirupma

Slides

31.1 Excess Scaling     Anjali Aggarwal, Nidhi Arora Slides
7. 2 Randomized Algorithms     Vaibhav Rastogi, Manish Singh Slides
11.2 Randomized Algorithms     Jivitej Chadha, Puneet Ahuja Notes
14. 2 2-SAT and 3-SAT     Sandhya Pillai, Sunita Sharma Slides, Notes
18.2 Primality Testing     Arindam Pal, Nimirita Koul Notes, Slides
25.2 Minor I        
28.2 Solutions for Minor I, Primality Testing (continued)     Pushkar Tripathi, Amandeep Notes
3.3 Primality Testing (finished)     Pushkar Tripathi, Amandeep Notes
6.3 Online Algorithms     Puneet Jain, Yashu Gupta, Bhaskar Chawda Slides
10.3 Online Algorithms        
13.3 Paging Upper bound     Amit Ruhela Notes
24.3 Paging Lower bound     Ankit Aggarwal, Movin Jain Notes
27.3 Learning with expert advice     Kunal Malhan, Gaurav Khurana Notes
31.3 Learning with expert advice     Kunal Malhan, Gaurav Khurana/Saurabh Agrawal, Sandeep Goyal Notes, Notes
3.4 Perceptron Algorithm     Anand Shukla/ Ayush Nayyar, Shailen Agrawal Notes, Notes
7.4 Winnow algorithm     Pratyush Tomar/Neha Dahiya Notes, Slides
10.4 Winnow for majority vote     Jay Shankar Kumar, Siddharth Mitra/Pratyush Tomar Notes, Notes
16.4 Np-hardness and approximation algorithms     Rahul Aggarwal, Tarun Aggarwal Notes
17.4 Maximum Weight matching     (Aditya, Abhishek Arora)/Vishesh Sharma Notes, Notes
21.4 LP Duality     Ankit Kapoor, Chetan Aneja/Niraj Patel, Abhishek Gramin/ Notes, Notes
24.4 Bipartite matching, IP and LP's     Pankaj Sharma, Arun Chaudhary/ Prabhat/ Arpit Nanda, Aman Gupta/Vishal Satya Notes, Notes, Notes, Notes

 

Your marks are here