Asymptotic notations and their significance, introduction to RAM model of computation, complexity analysis of algorithms, worst case and average case. Basic introduction to algorithmic paradigms like divide and conquer, recursion, greedy, etc. Searching: binary search trees, balanced binary search trees, AVL trees and red-black trees, B-trees, skip lists, hashing. Priority queues, heaps, Interval trees, tries. Order statistics. Sorting: comparison based sorting - quick sort, heap sort, merge sort: worst and average case analysis. Decision tree model and (worst case) lower bound on sorting. Sorting in linear time - radix sort, bucket sort, counting sort, etc. String matching Graph Algorithms: BFS, DFS, connected components, topological sort, minimum spanning trees, shortest paths - single source and all pairs.

- Endterm: 30%
- Class test: 40% (2 class tests and 1 mid term; best 2 out of 3)
- Assignment: 10% (4 assignments; best 2 out of 4)
- Attendance and teachers’ evaluation: 10%
- Students' Presentation: 10%
- Submit initial problem statement by January 24 (Monday)
- Finalize problem statement by January 31 (Monday)
- Deadline for uploading presentation: March 31 EOD
- Format of presentation: Motivation, formal problem definition with clear input and output specification, pseudocode of the algorithm, analysis of the algorithm, implementation of the algorithm in C/C++ programming language.
- Group size is 2-3. In the video presentation, every member of the group should speak for an equal duration of time.
- You need to submit 4 things: (i) video of the presentation, (ii) slides of the presentation, (iii) C/C++ code, and (iv) a readme.txt file clearly explaining how to compile and execute your code. Share a folder containing these on Google Drive.
- Duration of presentation: 15-20 minutes

- Link to last year's classes: here
- Class test 1 is scheduled on January 29 at 6 PM.
- Mid-term is scheduled on February 22 at 10 AM.
- Class test 2 is scheduled on March 26 at 6 PM.
**End-term is scheduled on April 12 at 11 AM in MS Teams.**

- Assignment 4 is here. Submit on MS Teams. Deadline is 11:59 PM on April 6, 2022.
- Assignment 3 is here. Submit on MS Teams. Deadline is 11:59 PM on March 22, 2022. Solution sketches of Q2 and Q3 are here.
- Assignment 2 is here. Submit on MS Teams. Deadline is 11:59 PM on February 17, 2022. Solution sketch of Q1 is here.
- Assignment 1 is here. Submit on MS Teams. Deadline is 11:59 PM on January 26, 2022. Solution sketch of Q1, 2, and 3 is here.

Week 1 | Jan 10 | PPC | Recursive Problem Formulation and Efficient Algorithm Design | Slides |

Jan 11 | Slides: this and this | |||

Jan 13 | PD | Analysis of Algorithm | Board work | |

Jan 15 | PD | Solving Recurrence Relations | Board work | |

Week 2 | Jan 17 | PPC | Recursions, Efficient Algorithm Design and Analysis | Slides |

Jan 18 | PPC | Divide and Conquer | Slides | |

Jan 20 | PD+PPC | Tutorial 1 | Tutorial 1 | |

Jan 22 | ||||

Week 3 | Jan 24 | PPC | Divide and Conquer Technique | Slides |

Jan 25 | PPC | Divide and Conquer Technique | Slides: this and this | |

Jan 27 | ||||

Jan 29 | First Class Test |
Questions: Part 1, Part 2 Solution sketches: Part 2 |
||

Week 4 | Jan 31 | PD | Greedy Algorithm: Job Scheduling | Board work |

Feb 1 | PD | Greedy Algorithm: Huffman Coding | Board work | |

Feb 3 | PD | Tutorial 2 | Tutorial 2 | |

Feb 5 | PPC | Tutorial 3 | Tutorial 3 | |

Week 5 | Feb 7 | PPC | Dynamic Programming: Matrix Chain Multiplication | Slides |

Feb 8 | PPC | Dynamic Programming: String Matching, LCS, Edit Distance | Slides | |

Feb 10 | PPC | Tutorial 4 | Tutorial 4 | |

Week 6 | Feb 14 | PD | Tree, Binary Search Tree | Board work |

Feb 15 | PD | Binary Search Tree, AVL Tree | Board work | |

Feb 17 | PD | Tutorial 5 | Tutorial 5 | |

Week 7 | Feb 21 | -- | No Class (Midsemester break) | -- |

Feb 22 | Mid-semester Examination |
Questions: Part 1, Part 2 Solution sketches: Part 2 |
||

Feb 24 | -- | No Class (Midsemester break) | -- | |

Week 8 | Feb 28 | -- | No Class (Kshitij) | -- |

Mar 1 | PPC | Heap, Heap Sort, and Pririty Queue | Slides: this and this | |

Mar 3 | PPC | Tutorial 6 | Tutorial 6 | |

Week 9 | Mar 7 | PD | Lower bounds | Board work, Reference |

Mar 8 | PD | Linear Time Selection | Board work | |

Mar 10 | PD | Tutorial 7 | Tutorial 7 | |

Week 10 | Mar 14 | PD | Hashing | -- |

Mar 15 | PPC | Graph and Graph Traversals | Slides: this and this | |

Mar 17 | PPC | Traversal of Directed Graphs | Slides | |

Mar 19 | PD+PPC | Tutorial 8 | Tutorial 8 | |

Week 11 | Mar 21 | PPC | Minimum Spanning Tree | Slides |

Mar 22 | PPC | Shortest Path | Slides: this and this | |

Mar 26 | PPC | Tutorial 9 | Tutorial 9 | |

Mar 26 | Second Class Test |
Questions: Part 1, Part 2 Solution sketches: Part 1 |
||

Week 12 | Mar 28 | PD | Disjoint Set Union-Find Data Structure | Board work |

Mar 29 | PD | String Matching | Board work | |

Mar 31 | PD | Tutorial 10 | Tutorial 10 | |

April 12 | End Semester Examination |
Questions: Part 1, Part 2 Solution sketches: Part 1 |

- Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms.
- Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
- Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh V. Vazirani, Algorithms, Tata McGraw-Hill, 2008.
- Jeff Erickson, Algorithms, 2019.
- Mark Allen Weiss, Data Structures and Algorithm Analysis in C.