Regular Zoom Interaction Sessions: Tuesday at 2:30PM to 4:30PM & Thursday at 4:30PM to 6:30PM
Discussion Hours with TAs:
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, videos will be uploaded in the youtube channel and assignments / quizes to be conducted using the classroom.
Please familiarise yourself with zoom, youtube and classroom. Subscribe to the youtube channel and add yourself to the classroom.
You are expected to read the reading material or watch the video before the zoom interaction sessions. The zoom interaction sessions will be mostly used for clearing doubts and having a discussion on the topic of that week or the next week. The details will be provided in the reading material and/or the videos uploaded.
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 zoom interaction sessions.
Evaluation: The endsem will contribute 50% of the marks to the final grade and the midsem will contribute 30% of the marks. The remaining 20% will be from the assignments/projects. There will be a total of 6-7 assignments/projects each of 10 marks. The best 5 will contribute to the 20% of the final marks.
There will be 2 midsems. Any student will be allowed to sit in only one of them.
1st Midsem Date: The midsem will be conducted on 27th of May 2021 at 2:30PM. The midsem will be conducted online through Google Classroom. The details will be shared later in Google Classroom.
In case you or your family members are suffering from COVID-19 and related issues, and you don't think you will be able to do justice in your midsem exam you need not take the Midsem on 27th. Your health (both physical and mental) is of utmost importance particularly in this pandemic times. Please take care of yourself and your family. Another midsem will be conducted later in the course, which will be scheduled such that people who could not take the first midsem due to COVID-19 related issues will be able to take the second midsem. You can take the second midsem when it is scheduled. You need not force yourself to take the first midsem that will be held on the 27th May.
But if you are doing fine (physically and mentally) I request you to take the first midsem on 27h May. You never know what will be be situation (wrt to COVID) during the second midsem. So if you can, I request you to take the 1st midsem itself.
Instructor: Sourav Chakraborty (sourav@isical.ac.in)
TAs:
Manaswi Parashaar (manaswi.isi@gmail.com),
Sayantan Sen (sayantan789@gmail.com),
Chandrima Kayal (chandrimakayal2012@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: Asymptotic Notations and Problems related to Binary Search
Week 3: Sorting Algorithms - Bubble sort, insertion sort, Merge Sort, Quick Sort, Randomised Quick Sort
Week 4: Heapsort, Lower bound of Sorting and Counting, Bucket and Radix Sort
Week 5 & 6: Introduction to Graph Algorithms, BFS, DFS
Week 7: Greedy Algorithms - Finding shortest path, Dijkstra's Algorithm
Week 8: Shortest Path Algorithms: Bellman Ford and Floyd Warshal (DP)
Week 9: Dynamic Programming: String algorithms
Week 10: Greedy Algorithms: Finding MST and Convex Hull
Week 11: Divide and Conquer Algorithms - Finding Median, Karatsuba, Strassen's Algorithm (5.3, 5.4, 5.5, 5.6 from KT)
Week 12: Network Flows, Linear Programming and SAT
Week 13: NP-completeness and Complexity - (Chapter 8 from KT)
Week 14: More on Complexity - (Chapter 10 from KT)
Lecture 1 (30/3/21) : Introduction to Algorithms [Youtube video]. Class video of Introductory Video [Youtube video]
Lecture 2 (01/4/21): Binary search [Youtube Video] & Proofs of Algorithms [Youtube Video]. Class video [Youtube video]
Lecture 3 (06/4/21): Sorting, Bubble sort, Insertion Sort, Bucket Sort [Youtube Video]. Class video [Youtube video]
Lecture 4(08/4/21): Merge Sort discussion. Class video [Youtube video]
Lecture 5(13/4/21): Discussion on Assignment 1 and lower bound for comparison sort. Class video [Youtube video]
Lecture 6(15/4/21): Stable sorting algorithms. Class video [Youtube video, class notes]
Lecture 7(27/4/21): Lower bound of Sorting. Class video [Youtube video, class notes]
Extra reading: Average time complexity of Quicksort [Nice Write-up & Nice Slides]
Extra reading: Heapsort [Youtube video]
Lecture 8 (29/4/21): Counting Sort [Youtube video, class notes]
Lecture 9 (04/5/21): Introduction to Graph Algorithms [Youtube video, class notes]
Lecture 10 (06/5/21): Depth First Search Algorithms [Youtube video, class notes, slides]
Tutorial (08/5/21): Discussion on Randomised Quick Sort and Bucket Sort [Youtube video]
Tutorial (10/5/21): Discussion of Problem Set on Sorting Algorithms
Lecture 11 (11/5/21): Topological Sort [Youtube video, class notes]
Lecture 12 (13/5/21): Breadth First Search [Youtube video, class notes, slides]
Tutorial (15/5/21) (youtube video). and (17/5/21)
Lecture 13 (18/5/21): Single Source Shortest Path (Dijkstra's Algorithm) [Youtube video, class notes, slides]
Lecture 14 (20/5/21): Dijkstra's Algorithms [Youtube video, class notes, slides]
Tutorial (22/5/21) (youtube video) and (24/5/21)
Lecture 15 (01/6/21): Bellman Ford Algorithm [Youtube video, class notes, slides]
Lecture 16 (03/6/21): All Pair Shortest Path [Youtube video, class notes, slides]
Tutorial (05/6/21) (youtube video) and (07/6/21)
Lecture 17 (08/6/21): Dynamic Programming for LCS [Youtube video, class notes, slides]
Lecture 18 (10/6/21): Dynamic Programming for Edit Distance and Knapsack [Youtube video, class notes, slides]
Tutorial (12/6/21)
Lecture 19 (15/6/21): Minimum Spanning Tree (Kruskal's Algorithm) [Youtube video, slides}
Lecture 20 (17/6/21): Minimum Spanning Tree (Prim's Algorithm) [Youtube video, slides]
Tutorial (19/6/21) and (21/6/21)
Lecture 21 (22/6/21): Introduction to Linear Programming [Youtube video, slides]
Lecture 22 (24/6/21): Reduction to matching and ILP [Youtube video, class notes]
Tutorial (26/6/21) [notes] and (28/6/21)
Lecture 23 (29/6/21): Matching, Network Flows, Ford Fulkerson [Youtube video, class notes]
Lecture 24 (01/7/21): P and NP classes [Youtube video, class notes]
Lecture 25 (06/7/21): SAT problem and polynomial reductions [Youtube video]
Lecture 26 (08/7/21): NP-completeness, reductions [Youtube video, class notes]
Lecture 27 (13/7/21): Fibonacci Heaps [Youtube video]
Assignment 1 : Posted 04/04/21, Due date: 12/04/21
Assignment 2: Posted 30/04/21, Due date: 10/05/21
Assignment 3: Posted 14/05/21. Due date: 24/05/21
Assignment 4: Posted 16/06/21. Due date: 25/06/21
Assignment 5: Posted 24/07/21. Due date: 07/08/21
Heap Datastructure [Youtube video] Video Recording from class from a previous course [Youtube video]
Other data structures like Union-find, Fibonacci Heaps etc. Though they have been mentioned in the class in various contexts.
Perceptron Learning algorithm (nice notes) Video Recording from class from a previous course [Youtube video]
Clustering Algorithms. Video Recording from class from a previous course [Youtube video]
Divide and Conquer Algorithms (Karatsuba's Algorithm and Strassen's Algorithm). Video Recording from class from a previous course [Youtube video]
Finding Median Algorithm. Video Recording from class from a previous course [Youtube video]
Computation of Convex Hull. Link to wikipedia.