Regular Zoom Interaction Sessions: Tuesday & Thursday at 11:30AM to 12:30PM
Discussion Hours with TAs: Saturday at 11:30AM to 12: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, 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. The remaining 50% 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 50% of the final marks.
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: Introduction to Graph Algorithms, BFS, DFS
Week 6: Recap and Durga Puja Holidays
Week 7: Greedy Algorithms - Finding shortest path and Finding MST (4.1, 4.2, 4.3, 4.4, 4.5 from KT)
Week 8: Greedy Algorithms - Clustering and Perceptron Learning algorithm (4.6, 4.7, 4.8 from KT and some other materials)
Week 9: Divide and Conquer Algorithms - Finding Median, Karatsuba, Strassen's Algorithm (5.3, 5.4, 5.5, 5.6 from KT)
Week 10: Dynamic Programming - (6.1, 6.2, 6.3, 6.4 from KT)
Week 11: Dynamic Programming - (6.5, 6.6, 6.7, 6.8, 6.9 from KT)
Week 12: Network Flows - (Chapter 7 from KT)
Week 13: Linear Programming
Week 14: NP-completeness and Complexity - (Chapter 8 from KT)
Week 15: More on Complexity - (Chapter 10 from KT)
Lecture 1 (15/9/20) : Introduction to Algorithms [Youtube video]: Video Recording of the class [Youtube video]
Lecture 2 (17/9/20): Binary search [Youtube Video] & Proofs of Algorithms [Youtube Video]: Video Recording of class [Youtube video]
Lecture 3 (22/9/20): Asymptotic Notations: Video Recording of class [Youtube video]
Lecture 4 (24/9/20): Discussion on first assignment: Video Recording of class [Youtube video]
Lecture 5 (29/9/20): Selection, Bubble, Insertion, Merge sort [Youtube video] Video Recording of class [Youtube video, Class notes]]
Lecture 6 (1/10/20): Analysis of Randomized Quicksort [Nice Write-up & Nice Slides] Video Recording of class[Youtube video, Class notes]
Lecture 7 (6/10/20): Heap Datastructure [Youtube video] Video Recording of class [Youtube video]
Lecture 8 (8/10/20): Counting, Bucket and Radix Sort. Video Recording of class [Youtube video]
Tutorial (10/10/20): Modelling of problems using graphs. Video Recording of class [Youtube video]
Lecture 9 (13/10/20): Introduction to Graph Algorithms. Video Recording of class [Youtube video]
Lecture 10 (15/10/20): DFS and BFS. Video Recording of class [Youtube video]
Lecture 11 (20/10/20): Recap of Things done so far. Video Recording of class [Youtube video]
Lecture 12 (22/10/20): DFS and its applications Video Recording of class [Youtube video, Class notes]. Nice write up on DFS [PDF}
No class on 27th October 2020
Lecture 13 (29/10/20): Finding Shortest Path Algorithm [Youtube video, Class notes]
Lecture 14 (3/11/20): Perceptron Learning algorithm (nice notes) [Youtube video, Class notes]
Lecture 15 (7/11/20): Clustering Algorithms [Youtube video, Class notes]
Lecture 16 (10/11/20): Divide and Conquer Algorithms (Karatsuba's Algorithm and Strassen's Algorithm) [Youtube video, Class notes]
Lecture 17(12/11/20): Finding Median Algorithm [Youtube video, Class notes]
Lecture 18(17/11/20): Dynamic Programming (LCS) [Youtube video, Class notes]
Lecture 19(19/11/20): A proof using probabilistic method [Youtube video, Class notes]
Lecture 20(21/11/20): Discussion on DP for the Knapsack Problem [Youtube video, Class notes]
No class on 24th October 2020
Lecture 21(26/11/20): Another look into Probabilistic Method: Crossing Lemma. Nice write up [PDF].
Lecture 22(28/11/20): Bellman-Ford Algorithms. [Youtube video, Class notes]
Lecture 23(01/12/20): Introduction to matching and flows. [Youtube video, Class notes]
Lecture 24(03/12/20): Ford-Fulkerson Algorithm - Max-flow-Min-Cut Thm. [Youtube video, Class notes]
Lecture 25(05/12/20): Hall's-Marriage-Theorem and Introduction to Linear Programming [Youtube video, Class notes]
Lecture 26(08/12/20):Introduction to complexity classes P, NP, NP-complete [Youtube video, Class notes]
Lecture 27(10/12/20):More discussion on P, NP and reductions [Youtube video, Class notes]
Lecture 28(12/12/20): Recap - 1 [Youtube video]
Lecture 29(15/12/20): Recap - 2 [Youtube video] (Sorry only a part of the lecture could be recorded.)
Lecture 30(17/12/20): PRIMES in NP [Youtube video, Classnotes] Nice notes on PRIMES in NP.
Endsem (online)
Assignment 1 Due date: 22/9/2020
Assignment2 Assignment2(Q7) Due date:19/10/2020
Assignment 3 Due date: 2/11/2020
Assignment 4 Due date 23/11/2020
Assignment 5 Due date 14/12/2020
Assignment 6 Due date 21/12/2020