COL351, Fall Semester 2024
Analysis and Design of Algorithms
Instructor: Rohit Vaish ()
Teaching Assistants:
Lakshay Saggi (),
Pratikkumar Sureshkumar Bulani (),
Gaurav Rajput (),
Adithya R Narayan (),
Shivansh Garg (),
Vaibhav Katendra (),
Ramanuj Goel (),
Geetansh Juneja (),
Samyak Jain (),
Mayank Mangla ()
Course Information
What this course is about
This course will provide an introduction to the fascinating field of algorithms. Participants will learn various techniques for designing algorithms and formally reasoning about their correctness and resource requirements.
The course is designed for third-year undergraduate students. This offering of COL351 is for CS students; non-CS students should sign up for the Spring semester offering.
PrerequisitesThis is a theoretical course that will require familiarity with Data Structures (COL106) and Discrete Mathematical Structures (COL202).
References- [DPV] Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms. First Edition.
- [KT] Jon Kleinberg and Éva Tardos. Algorithm Design. First Edition
- [R] Tim Roughgarden. Algorithms Illuminated, Parts 1-4. [Website]
- A Second Course in Algorithms at Stanford
- Dance your way to sorting with AlgoRhythmics
- Visualizing algorithms with VisuAlgo
- Nice explanations of CS Theory concepts
Admin
Lecture and tutorial timings
Lectures: TWF 10-11 AM. Venue: LH 121.
Tutorials: M/T/Th/F 1-2 PM. Venue: LH 408. (Tutorial Groups).
Sign up on the Microsoft Teams channel of the course for announcements. Evaluation policy
Tutorial quizzes: 24% (best eight x 3%)
In-class quizzes: 36% (best three x 12%)
Minor: 20%
Major: 20%
- For missed minor and/or major exams due to a medical reason, a single exam will be held after the regular major exam (date will be announced later), for which the syllabus will be the entire course. The weightage of this make-up exam will be 20%.
Only those who obtain prior approval from the instructor (before the date of the missed regular minor and/or regular major exam) and have at least 75% attendance will qualify for this exam. In particular, if you miss both the regular minor and the regular major exam, there will still be only one make-up exam (worth 20%). - For students with an E grade, a remajor exam will be held at the start of the next semester. Again, at least 75% attendance will be required.
- Audit policy: No audits allowed.
Date and Lecture | Topic | Tutorials | |
---|---|---|---|
Week 1 | |||
July 22 (Mon) |
|
||
July 23 (Tue) Lecture 1 |
Introduction to Algorithms |
|
|
July 24 (Wed) Lecture 2 |
Divide and Conquer I: Integer Multiplication and Merge Sort |
|
|
July 25 (Thurs) |
|
||
July 26 (Fri) Lecture 3 |
Divide and Conquer II: Merge Sort (Contd.) and Asymptotic Analysis |
|
|
Week 2 | |||
July 29 (Mon) |
|
||
July 30 (Tue) Lecture 4 |
Divide and Conquer III: Asymptotic Analysis (Contd.) and Counting Inversions |
|
|
July 31 (Wed) Lecture 5 |
Divide and Conquer IV: Counting Inversions (Contd.), Matrix Multiplication and Master Theorem |
|
|
Aug 01 (Thurs) |
|
||
Aug 02 (Fri) Lecture 6 |
Divide and Conquer V: Proof and Applications of Master Theorem |
|
|
Week 3 | |||
Aug 05 (Mon) | Last date for course drop |
|
|
Aug 06 (Tue) Lecture 7 |
Quiz 1 |
|
|
Aug 07 (Wed) Lecture 8 |
Graph Algorithms I: Basic Definitions Last date for adding courses in lieu of dropped courses Finalization of roll lists |
|
|
Aug 08 (Thurs) |
|
||
Aug 09 (Fri) Lecture 9 |
Graph Algorithms II: Representation and Search |
|
|
Week 4 | |||
Aug 12 (Mon) |
|
||
Aug 13 (Tue) Thursday timetable |
No lecture |
|
|
Aug 14 (Wed) Lecture 10 |
Graph Algorithms III: BFS, DFS, and Applications |
|
|
Aug 15 (Thurs) Independence Day |
|
||
Aug 16 (Fri) No Class Day |
No lecture |
|
|
Week 5 | |||
Aug 19 (Mon) Rakshabandhan |
|
||
Aug 20 (Tue) Lecture 11 |
Graph Algorithms IV: Topological Ordering and Strongly Connected Components |
|
|
Aug 21 (Wed) Lecture 12 |
Graph Algorithms V: Kosaraju's Algorithm |
|
|
Aug 22 (Thurs) |
|
||
Aug 23 (Fri) Lecture 13 |
Graph Algorithms VI: Dijkstra's Algorithm |
|
|
Week 6 | |||
Aug 26 (Mon) Janmashtami |
|
||
Aug 27 (Tue) Lecture 14 |
Greedy Algorithms I: Job Scheduling |
|
|
Aug 28 (Wed) Lecture 15 |
Greedy Algorithms II: Job Scheduling (Contd.) and Huffman Coding |
|
|
Aug 29 (Thurs) |
|
||
Aug 30 (Fri) Lecture 16 |
Quiz 2 |
|
|
Aug 31 (Sat) Monday timetable |
|
||
Week 7 | |||
Sep 02 (Mon) |
|
||
Sep 03 (Tue) Lecture 17 |
Greedy Algorithms III: Huffman Coding (Contd.) |
|
|
Sep 04 (Wed) Lecture 18 |
Greedy Algorithms IV: Huffman's Algorithm |
|
|
Sep 05 (Thurs) |
|
||
Sep 06 (Fri) Lecture 19 |
Greedy Algorithms V: Minimum Spanning Trees |
|
|
Week 8 | |||
Sep 09 (Mon) |
|
||
Sep 10 (Tue) Lecture 20 |
Greedy Algorithms VI: Minimum Spanning Trees (Contd.) |
|
|
Sep 11 (Wed) Lecture 21 Friday timetable |
Mid-Term Review and Introduction to Dynamic Programming |
|
|
Weeks 8 and 9 (Sept 12-18) | |||
Sep 17 (Tue) | Mid-Semester Examination (8 AM-10 AM) at LH 121 and LH 325 |
|
|
Week 9 | |||
Sept 19 (Thurs) |
|
||
Sept 20 (Fri) Lecture 22 |
Dynamic Programming I: Weighted Independent Set |
|
|
Week 10 | |||
Sep 23 (Mon) |
|
||
Sep 24 (Tue) Lecture 23 |
Dynamic Programming II: Weighted Independent Set (Contd.) and Knapsack |
|
|
Sep 25 (Wed) Lecture 24 |
Dynamic Programming III: Knapsack (Contd.) and Sequence Alignment |
|
|
Sep 26 (Thurs) |
|
||
Sep 27 (Fri) | No lecture Mid-term evaluation of projects |
|
|
Week 11 | |||
Sep 30 (Mon) |
|
||
Oct 01 (Tue) Lecture 25 |
No lecture |
|
|
Oct 02 (Wed) Gandhi Jayanti |
No lecture |
|
|
Oct 03 (Thurs) |
|
||
Oct 04 (Fri) Lecture 26 |
Dynamic Programming IV: Sequence Alignment (Contd.) and Bellman-Ford Algorithm |
|
|
Week 12 (Mid-Semester Break) | |||
Oct 07-11 | No Lectures |
|
|
Week 13 | |||
Oct 14 (Mon) |
|
||
Oct 15 (Tue) Lecture 27 |
Dynamic Programming V: Bellman-Ford Algorithm (Contd.) |
|
|
Oct 16 (Wed) Lecture 28 |
Quiz 3 |
|
|
Oct 17 (Thurs) |
|
||
Oct 18 (Fri) Lecture 29 |
Dynamic Programming VI: All Pairs Shortest Paths Problem |
|
|
Oct 19 (Sat) Lecture 30 Wednesday timetable |
All Pairs Shortest Paths Problem (Contd.) and Introduction to Network Flows |
|
|
Week 14 | |||
Oct 21 (Mon) |
|
||
Oct 22 (Tue) Lecture 31 |
Network Flow II: Ford-Fulkerson Algorithm |
|
|
Oct 23 (Wed) Lecture 32 |
Network Flow III: Maximum Flows and Minimum Cuts |
|
|
Oct 24 (Thurs) |
|
||
Oct 25 (Fri) Lecture 33 |
Network Flow IV: Edmonds-Karp Algorithm |
|
|
Oct 26 (Sat) Lecture 34 Friday timetable |
Network Flow V: Edmonds-Karp Algorithm (Contd.) and Applications |
|
|
Week 15 | |||
Oct 28 (Mon) |
|
||
Oct 29 (Tue) Lecture 35 |
Quiz 4 |
|
|
Oct 30 (Wed) Lecture 36 |
Network Flow VI: Edmonds-Karp Runtime Analysis (Contd.) |
|
|
Oct 31 (Thurs) Diwali |
|
||
Nov 01 (Fri) Lecture 37 |
Maximum Flow Applications (Contd.) |
|
|
Week 16 | |||
Nov 04 (Mon) |
|
||
Nov 05 (Tue) Lecture 38 |
NP-completeness I: Introduction |
|
|
Nov 06 (Wed) Lecture 39 |
NP-completeness II: The Class NP |
|
|
Nov 07 (Thurs) |
|
||
Nov 08 (Fri) Lecture 40 |
NP-completeness III: More Reductions |
|
|
Week 17 | |||
Nov 11 (Mon) |
|
||
Nov 12 (Tue) Lecture 41 |
NP-completeness IV: Even More Reductions |
|
|
Nov 13 (Wed) Lecture 42 |
NP-completeness V: P vs NP, ETH, SETH and Wrap-Up |
|
|
Week 18 | |||
Nov 22 (Fri) | End-Semester Examination |
|
|
TBA | Make-Up Exam |
|