Anonymous Feedback form (deactivated on Feb 21)
Declaration and information gathering form (Mandatory to fill in in the first week)
Presentation related sheet
Slides: Group 4, Group 5, Group 3, Group 6, Group 1, Group 2
L1: 14/11/2022 (No lecture since students didn't know the timetable)
L2: 15/11/2022 Day 1 slides (You must go through these)
L3: 16/11/2022 (No lecture since students need time to settle down wrt PG, mess)
L4: 21/11/2022 Functions, growth of functions, Asymptotic notation for upper bound: O(.) defined (CLRS: B3, 3.1)
L5: 22/22/2022 Asymptotic notation for lower bound (Omega) and both bounds (Theta) (CLRS: 3.1), transitivity, relation between O, Omega
L6: 25/11/2022 Recursive algorithms (max, n-th Fibonacci number), recurrence relations (Refer class notes. CLRS: 4.4)
L7: 28/11/2022 Recursion tree method (back substitution), Master Theorem, statement and limitations, examples (CLRS: 4.4, 4.5)
L8: 29/11/2022 Tutorial (ungraded) - 1 solutions
L9: 2/12/2022 Concluded unit 1 with a discussion on master theorem's proof and Akra-Bazzi method), began with unit 2 (problems covered: searching, Fibonacci in linear time and missing integer) (Akra-Bazzi original paper)
L10: 5/12/2022 Warm up: analysis of an algorithm to check if all rows and columns of a matrix are sorted, followed by bubble sort (worst/average case analysis, insertion sort: worst /avg and best case analysis (class notes, CLRS: 2.1)
L11: 6/12/2022 Recursive insertion sort and its analysis, bubble sort best case discussion, discussion on the lower bound on comparison based counting, surprise test 1 (class notes, CLRS: 8.1)
L12: 9/12/2022 Counting sort, ST1 discussion (CLRS: 8.2)
L13: 12/12/2022 Quick sort (deterministic version) and its best, worst and almost best case analysis (CLRS: 7.1,7.2, except partition method)
L14: 13/12/2022 Quick sort (randomized version) and expected running time (CLRS Problem 7-3: refer this pdf).
18/12/2022 Test 1 (solutions)
L15: 19/12/2022 Unit 3 began. Divide and Conquer, binary search and related problems, merge sort idea (CLRS: 2.3.1, Exercise 2.3.5)
L16: 20/12/2022 Completed merge sort algorithm and complexity analysis, discussed related problems in the form of a tutorial (CLRS: 2.3.1, 2.3.2, Exercise 2.3.6,2.3.7)
L17: 26/12/2022 Greedy paradigm, activity selection problem and algorithm, optimal substructure, Knapsack problem and its variants (CLRS: 16.1, Exercise 16.1-3 (partially done), 16.2 (page 425))
L18: 27/12/2022 Greedy paradigm, Algorithm for Fractional Knapsack problem, why does it not work with 0-1 variant, Coin change problem (1,5,10,25 denominations), whether it works for all denominations (CLRS: 16.2, Problem 16-1)
L19: 29/12/2022 Heap Data structure and Heapsort (topic from unit 2)
L20: 30/12/2022 Concluded with unit 3: canonical coin system, interval scheduling: a related problem to activity selection, proof of correctness of activity selection algorithm (partially done) (CLRS: 16.1)
L21: 2/1/2023 Began unit 4: dynamic programming, rod cutting problem, its optimal substructure and overlapping subproblems properties, brute force algorithm, D&C approach, memoized version (CLRS: 15.1)
L22: 3/1/2023 Rod cutting bottom-up/DP algorithm, LCS (Longest Common Subsequence) problem definition and brute force approach, optimal substructure and overlapping subproblems properties (CLRS: 15.1, 15.4)
L23: 6/1/2023 LCS: completed the algorithm with an elaborate example, Tutorial on DP (Longest increasing subsequence problem) (CLRS: related Problem 15.1, Dasgupta)
L24: 9/1/2023 Started with graph theory (notation, definition, types of graphs, representation etc.), DFS algorithm and basic analysis (class notes)
L25: 10/1/2023 Amortized analysis of DFS to show \Theta(m+n) running time using aggregate method and accounting method (class notes), surprise test 2
L26: 13/1/2023 Concluded with amortized analysis of DFS, dynamic stack / table example (class notes, CLRS: 17.1,17.2,17.4), MST problem (min spanning tree)
L27: 16/1/2023 Prim's and Kruskal's basic algorithm, analysis and efficient version using min-heap and union find respectively, MAX independent set (IS) on trees (CLRS: 23.2, Dasgupta: 6.7)
L28: 17/1/2023 MAX-IS on trees concluded, discussed several applications of DFS, BFS, MST, started with backtracking and its relation to brute-force (class notes, Dasgupta: 6.7)
L29: 23/1/2023 N-Queens problem and backtracking algorithm for the same (class notes)
L30: 24/1/2023 Abstracting out "backtracking" method, subset sum problem and backtracking algorithm for the same (class notes)
L31: 27/1/2023 Backtracking template, SAT problem and backtracking algorithm, TSP problem (Dasgupta 9.1.1, 9.1.2)
L32: 30/1/2023 Branch and bound template algorithm, TSP problem : lower bound and branch and bound algorithm (Dasgupta 9.1.2)
L33: 31/1/2023 Executed the B&B algorithm on TSP instance (Dasgupta 9.1.2)
L34: 3/2/2023 Writing verification version of a problem, writing decision version of an optimization problem with examples: MST, SAT (class notes), surprise test 3
L35: 6/2/2023 Verification algorithm for MST (polytime algorithm for MST_veri), TSP, TSP_dec, TSP_veri, TSP_dec_veri and polytime algorithm for TSP_dec_veri), definition of classes: P and NP, relationship between the two, placement of known problems including TSP_dec in the set P or NP (class notes)
L36: 7/2/2023 Discussed the interpretation behind the famous question "whether P = NP"? Poly-time reduction from an NP problem to another NP problem (class notes)
L37: 10/2/2023 Reduction of HC to TSP_decision, background behind defining NP-complete class of problems (class notes)
L38: 13/2/2023 Definition(s) of NP-hard and NP-complete class and their relationships and significance, defined new problem: MAX_IS, MAX_CLIQUE, MIN_VC and their decision versions, started with reduction from dec_IS to dec_CLIQUE (class notes)
L39: 14/2/2023 Completed two reductions: dec_IS --> dec_CLIQUE and dec_IS --> dec_VC (class notes), discussed approaches to deal with NP-completeness (class notes)
L40: 17/2/2023 Approximation algorithms: introduction, definition, examples (class notes)
L41: 20/2/2023 Max Sum Subarray problem : brute force (n^3, n^2), Divide and Conquer (n log n), DP (n) (CLRS 4.1, Exercise 4.1-5)
L42: 21/2/2023 A quick recap and discussion on end semester exam pattern, surprise test 4 (solutions)