Regular Zoom Interaction Sessions: Monday & Wednesday at 11:35AM to 1:20PM
Discussion Hours with TAs: Tuesday at 4:30pm (for MTech CRS) in room 523. & F riday at 6:30pm (for MTech CS) in room 520. JRFs can attend the tutorials in either of the sessions.
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.
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%. 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.
Link to last year's course is available here.
Instructor: Sourav Chakraborty (sourav@isical.ac.in)
TAs:
Sayantan Sen (sayantan789@gmail.com),
Swarnalipa Datta (rimadatta94@gmail.com),
Soumi Nandi (nandisoumi1@gmail.com )
Sutanoya Chakraborty (sutanoya@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: Logistics for the course. Class Recording.
Lecture 1 (16/2/22) : Introduction to Algorithms [Youtube video], Binary search [Youtube Video] & Proofs of Algorithms [Youtube Video]
Lecture 2 (21/2/22): Introduction to Algorithms. Class Recording.
Tutorial for MTech CRS (22/2/22)
Lecture 3 (23/2/22): Searching and Sorting (Insertion Sort). Class Recording. Selection, Bubble, Insertion and Merge Sort. Slides [Youtube video]
Tutorial for MTech CS (25/2/22)
Lecture 4 (28/2/22): Discussion on Asymptotic notations and recurrences. Class Recording. Class notes.
Tutorial for MTech CRS (1/3/22) Recording of class
Lecture 5 (2/3/22): Recursive algorithms (Merge Sort). Class Recording. Class notes.
Tutorial for MTech CS (4/3/22) Recording of class
Lecture 6 (7/3/22): Randomized Quick Sort and Lower bound for comparison sort. Class Recording. Class notes.
Lecture 7 (9/3/22): Heapsort. Class Recording. Class notes.
Lecture 8 (14/3/22): Counting Sort, Radix Sort. And introduction to graph algorithms. Class Recording. Class notes.
Lecture 9 (16/3/22): DFS and its applications. Class Recording. Class notes. Slides.
Lecture 10 (21/3/22): BFS and its applications. An introduction to MST. Class Recording. Class notes. Slides.
Lecture 11 (23/3/22): Kruskal's Algorithm. Class Recording. Slides.
Lecture 12 (28/3/22): Prim's Algorithm. Class Recording. Slides.
Lecture 13 (30/3/22): Discussion on runtime of Prim's and Kruskal's Algorithm. Class Recording. Class notes. Slides.
Midsem (6/4/22). Model Solution for Midsem.
Lecture 14 (11/4/22): Dynamic Programming. Class Recording. Class notes. Slides.
Lecture 15 (13/4/22): Dynamic Programming (Knapsack). Class Recording. Class Notes.
Lecture 16 (18/4/22): Dynamic Programming (LCS and LIS) Class Recording. Class Notes. Slides.
Lecture 17 (20/4/22): Divide and Conquer algorithm (Media Finding, Strassen's) Class Recording. Class Notes.
Lecture 18 (25/4/22): Single source shortest path (Dijkstra's Algorithm) Class Recording. Slides. Class notes.
Lecture 19 (27/4/22): Bellman Ford and All Pair Shortest path (squaring algorithm) Class Recording. Slides1, Slides2, Class notes.
Lecture 20 (2/5/22): Introduction to LP Class Recording, Slides. Class notes
Lecture 21 (9/5/22): NP-complete problems and reductions Class Recording, Class notes
Lecture 22 (11/5/22): NP-completeness of Vertex Cover Class Recording, Class notes
Lecture 23 (16/5/22): NP-completeness of Set Cover Class Recording Class notes
Lecture 24 (18/5/22): Set cover, Matching and flows Class notes
Lecture 25 (23/5/22): Matching in P Class Recording, Class notes
Quiz (Assignment 1)