Regular Classes: Monday 11:10 AM to 12:55 PM & Wednesday at 09:20AM to 11:05AM. Room 705-706
Discussion Hours with TAs: Wednesday at 6:30pm.
Reading material and videos and exercises will be posted/uploaded regularly.
Every 2 weeks a small online assignment will be posted. In some of the assignments you may have to code up a small algorithm in C or C++ or Python. While in the other assignments you will have to write up your solutions in the computer and submit the pdf. In case you don't have access to a computer that can be used for writing the codes or assignments please identify yourself to the instructor by sending an email.
Course material to be uploaded in this webpage, and assignments / quizes to be conducted using the classroom.
In you have any doubts or questions feel free to email the instructor or the TAs or post the question in classroom or ask the question during the class.
Evaluation: The endsem will contribute 50% of the marks to the final grade and the midsem will contribute 30%. The remaining 20% will be from the assignments/projects. There will be a total of 7 assignments/projects each of 10 marks. The best 5 will contribute to the 20% of the final marks. .
Instructor: Sourav Chakraborty (sourav@isical.ac.in) & Sanjukta Roy (sanjukta@isical.ac.in)
TAs:
Debarshi Chanda (debarshi.chanda.1997@gmail.com),
Swarnalipa Datta (rimadatta94@gmail.com),
Aranya Bal (rono220125@gmail.com )
Asymptotic Notations (You may go over Chapter 2 in the Discrete Mathematics Lecture Notes of Laszlo Babai)
Solving of Recurrences (You may go over Chapter 5 in the Discrete Mathematics Lecture Notes of Laszlo Babai)
Basic Graph Theory (You may go over Chapter 6 in the Discrete Mathematics Lecture Notes of Laszlo Babai)
Basic probability (You may go over Chapter 7 in the Discrete Mathematics Lecture Notes of Laszlo Babai)
Week 1: Introduction to Algorithms & Simple algorithms - Finding Maximum, Binary Search, Finding GCD
Week 2: Sorting Algorithms - Bubble sort, insertion sort, Merge Sort, Quick Sort, Randomised Quick Sort
Week 3: Heapsort, Lower bound of Sorting and Counting, Bucket and Radix Sort
Week 4: Introduction to Graph Algorithms, BFS, DFS
Week 5: Greedy Algorithms - Finding shortest path and Finding MST (4.1, 4.2, 4.3, 4.4, 4.5 from KT)
Week 6: Greedy Algorithms - Clustering and Perceptron Learning algorithm (4.6, 4.7, 4.8 from KT and some other materials)
Week 7: Divide and Conquer Algorithms - Finding Median, Karatsuba, Strassen's Algorithm (5.3, 5.4, 5.5, 5.6 from KT)
Week 8: Dynamic Programming - (6.1, 6.2, 6.3, 6.4 from KT)
Week 9: Dynamic Programming - (6.5, 6.6, 6.7, 6.8, 6.9 from KT)
Week 10: Network Flows - (Chapter 7 from KT)
Week 11: Linear Programming
Week 12: NP-completeness and Complexity - (Chapter 8 from KT)
Week 13: More on Complexity - (Chapter 10 from KT)
Lecture 0 (5/1/26) : Introduction to Algorithms [Youtube video], Binary search [Youtube Video] & Proofs of Algorithms [Youtube Video]
Lecture 0 (7/1/26): Evaluatory quiz
Lecture 1 (12/1/26): Introduction to greedy and recursive algorithms (perceptron and Euclid's). Nice notes of perceptron algorithm. My old slides on perceptron algorithm. My old slides on Algorithms in AI. Scribed Notes (not fully verified).
Lecture 2 (14/1/26): Discussion on sorting algorithms. Various complexity measures. Scribed Notes (not fully verified).
Lecture 3 (19/1/26): Time complexity calculation of Merge and Quick sort. Lower bounds. Scribed Notes (not fully verified).
Lecture 4 (21/1/26): Randomized Quick sort. Counting Sort. Scribed Notes (not fully verified).
Lecture 5 (28/1/26): Lower bounds with decision trees. Scribed Notes (not fully verified).
Lecture 6 (2/2/26): Recursive algorithms. Median finding algorithm. Scribed Notes (not fully verified).
Lecture 7 (4/2/26): Dynamic Programming. LCS. Scribed Notes (not fully verified).
Lecture 8 (9/2/26): More Dynamic Programming. Knapsack, Billboard Assignment, Sequence Alignment Scribed Notes (not fully verified)
Lecture 9 (11/2/26): Divide & Conquer: Closest Pair, Karatsuba Algorithm, Tower of Hanoi Scribed Notes (not fully verified)
Lecture 10 (16/2/26): Graph Algorithms: Introduction, Greedy Algorithms: Dijkstra's Algorithm, Prim's Algorithms Scribed Notes (not fully verified)
Lecture 11 (18/2/26): Revision and Shortest Path Algorithms
Lecture 12 (2/3/26): Bellman Ford Algorithm
Lecture 13 (9/3/26): Breadth First Search and Depth First Search Scribed Notes (not fully verified)
Lecture 14 (11/3/26): Application of DFS and BFS Scribed Notes (not fully verified)
Lecture 15 (16/3/26): Single Source Shortest Path, Belman Ford (slides1, slides2) Scribed Notes (not fully verified)
Lecture 16 (18/3/26): All Pairs Shortest Path (slides)
Lecture 17 (23/3/26): Modelling problem using Linear Programming and ILP (slides1, slides2)
Lecture 18 (25/3/26): Introduction to complexity theory
Lecture 19 (1/4/26): NP-completeness and Reductions