Regular Zoom Interaction Sessions: Tuesday & Thursday at 2:00PM to 4:00PM
Discussion Hours with TAs: Friday 7PM to 8PM
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%. 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:
Manaswi Parashaar (manaswi.isi@gmail.com),
Swarnalipa Datta (rimadatta94@gmail.com),
Omkar Bhalerao (obha1729@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: Recap and Durga Puja Holidays
Week 6: Greedy Algorithms - Finding shortest path and Finding MST (4.1, 4.2, 4.3, 4.4, 4.5 from KT)
Week 7: Greedy Algorithms - Clustering and Perceptron Learning algorithm (4.6, 4.7, 4.8 from KT and some other materials)
Week 8: Divide and Conquer Algorithms - Finding Median, Karatsuba, Strassen's Algorithm (5.3, 5.4, 5.5, 5.6 from KT)
Week 9: Dynamic Programming - (6.1, 6.2, 6.3, 6.4 from KT)
Week 10: Dynamic Programming - (6.5, 6.6, 6.7, 6.8, 6.9 from KT)
Week 11: Network Flows - (Chapter 7 from KT)
Week 12: Linear Programming
Week 13: NP-completeness and Complexity - (Chapter 8 from KT)
Week 14: More on Complexity - (Chapter 10 from KT)
Lecture 1 (21/9/21) : Introduction to Algorithms [Youtube video], Binary search [Youtube Video] & Proofs of Algorithms [Youtube Video]
Lecture 2: (23/9/21): Quiz on Discrete Mathematics.
Lecture 3: (28/9/21): Asymptotic Notations. Video Recording of class
Lecture 4: (30/9/21): Search and Sorting algorithms (Selection, Bubble, Insertion, Merge sort) Slides and Notes from the class.
Tutorial 1: (1/10/21): Discussion of Quiz problems.
Lecture 5: (5/10/21): Quick sort and randomised quick sort, and lower bound for sorting. Notes from class. Video Recording of class
Lecture 6: (7/10/21): Heap sort. Notes from class. Video Recording of class
Lecture 7: (8/10/21): Counting Sort. Video Recording of class
Lecture 8: (21/10/21): Introduction to Graph Algorithms. Notes from class. Video Recording of class
Lecture 9: (26/10/21): DFS and applications. Video Recording of class.
Lecture 10: (28/10/21): BFS and applications. Video Recording of class.
Tutorial: DFS and BFS problems. Video Recording of class.
Lecture 11: (02/11/21): Single source shortest path, Dijkstra's Algorithm. Slides, Video Recording of class
Lecture 12: (09/11/21): Bellman Ford. (class taken by Manaswi Paraashar). Slides. Video Recording of class.
Lecture 13: (11/11/21): All pair shortest path, Floyd Warshal. Slides.
Tutorial: (12/11/21): Video Recording of class
Midsem (18/11/21) 2:30PM-5:30PM (midsem paper)
Lecture 14: (23/11/21): MST (Primes) and Median finding. Slides. Video Recording of class
Lecture 15: (25/11/21): Classification of algorithms - Greedy, Divide and Conquer & DP. Video Recording of class
Lecture 16: (26/11/21): Perceptron Learning Algorithm. Nice notes. Slides. Video Recording of class
Lecture 17: (30/11/21): Dynamic Programming (Longest Common Subsequence) (Class Notes, Video Recording of Class)
Lecture 18: (2/12/21): Dynamic Programming (Edit Distance) (Class Notes, Video Recording of Class)
Tutorial: (3/12/21): Video Recording of class
Lecture 19: (7/12/21): Introduction to P and NP (class notes, Video Recording of Class)
Tutorial: (9/12/21): Video Recording of Class
Lecture 21: (10/12/21): Introduction to Complexity classes, Reductions, NP-completeness (Class Notes, Video Recording of Class)
Lecture 22: (14/12/21): Proving NP-completeness of ILP, VC. (Class Notes, Video Recording of Class)
Lecture 23: (16/12/21): Surprise exam. (Class Notes, Video Recording of Class)
Tutorial: (17/12/21): Video Recording of Class
Lecture 24: (21/12/21): Network Flows using LP (Class Notes, Video Recording of Class)
Lecture 25: (23/12/21): Matching using Ford-Fulkerson (Class Notes, Video Recording of Class)
Tutorial: (24/12/21): Video Recording of Class
Lecture 26: (28/12/21): FFT algorithm for multiplication on polynomials (Class Notes, Video Recording of Class)
Tutorial: (31/12/21): Video Recording of Class
Lecture 27: (4/1/22): Introduction to Advanced Algorithms Video Recording of Class
Lecture 28: (6/1/22): Introduction to Optimization techniques Video Recording of Class