Design and Analysis of Algorithms (DAA), August - December 2023
Day → Branch ↓ |
Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday |
---|---|---|---|---|---|---|---|
CSE-A (C 114) |
09:00 am |
12:00 pm |
11:00 am | 12:00 pm |
The main objective of this course is to discuss the techniques necessary to propose practical algorithmic solution for real world problems, which still permit strong theoretical bounds on time and space utilization. Students will study a wide collection of important and useful algorithms with necessary data structures in different areas of applications, focusing on fundamental concepts.
Upon successful completion of this course, the student should be able to:
You can find the DAA theory and lab syllabus [here].
Sl No # | Date | Time | Duration | Contents Discussed | |
---|---|---|---|---|---|
1 | 22/08/23 | 12:00 | 1 hr | Chapter 1 of T1 [ Lecture Slide ] |
Course overview; Introduction to DAA; Tools for algorithm analysis: RAM model of computation, concepts of worst case, best case and average case time. |
2 | 28/08/20 | 02:00 | 1 hr | Chapter 2 & 3 of T1 [ Lecture Slide ] |
Concept of asymptotic notations; Asymptotic notations: Definitions, interpretations and examples. |
3 | 31/08/23 | 11:00 | 1 hr | Chapter 4 of T1 [ Lecture Slide ] |
Recurrence relations: Definition, Interpretation of the solution of a recurrence relation; Solving recurrence relations using substitution (iterative) method. |
4 | 01/09/23 | 12:00 | 1 hr | Chapter 4 of T1 [ Lecture Slide ] |
Soving recurrence relation by recurrence tree method; Analyzing code fragments. |
5 | 04/09/23 | 9:00 | 1 hr | Exercise 2.1.3 and 2.3.5 of T1 [ Lecture Slide ] |
Genereal Structure of divide and conquer approach; Binary Search (problem statement, algorithm, example and analysing the worst case complexity). |
6 | 07/09/23 | 11:00 | 1 hr | Class notes [ Lecture Slide ] |
Ternary Search (problem statement, algorithm, example and analysis of worst case complexity); Comparision of binary and ternary search algorithms. |
7 | 08/09/23 | 12:00 | 1 hr | Chapter 2.3 of T1 [ Lecture Slide ] |
Merge sort (problem Statement), merge procedure (example), worst case analysis of merge sort. |
8 | 11/09/23 | 09:00 | 1 hr | Chapter 7 of T1 [ Lecture Slide ] |
Divide and Conquer: Quick sort: Idea, Partition procedure, example, Complexity of partition procedure |
9 | 12/09/23 | 12:00 | 1 hr | Chapter 7 of T1 [ Class note ] |
Divide and Conquer: Quick sort: Complexity Analysis (Worst, best and average case) |
10 | 14/09/23 | 11:00 | 1hr | Class Notes | Divide and Conquer: Strassen’s matrix multiplication, Complexity analysis |
11 | 15/09/23 | 12:00 | 1 hr | Chapter 6 of T1 [ Class note ] |
Heap sort: Definition, Properties, Basic building blocks to develop the heap sort algorithm |
12 | 18/09/23 | 09:00 | 1hr | Chapter 6 of T1 [ Class note ] |
Heap sort: Heapify, Build heap, Heap sort, Examples |
13 | 21/09/23 | 11:00 | 1hr | Chapter 6 of T1 [ Class note ] |
Heap sort: Complexity analysis of Heapify, Build heap, Heap sort; Priority queue |
14 | 22/09/23 | 12:00 | 1hr | Chapter 4 of T1 [ Class note ] |
The Master Method: Basic and generalized master method, examples; Basic concept of lower bound for sorting |
15 | 26/09/23 | 12:00 | 1hr | Chapter 8.1 of T1 [ Class Note ] |
Lower bound for Sorting: Detailed analysis and derivation |
16 | 28/09/23 | 11:00 | 1hr | Chapter 15 of T1 [ Class Note ] |
Dynamic Programming: Elements of dynamic programming, Matrix chain multiplication - problem statement explanation using an example |
17 | 10/10/23 | 12:00 | 1hr | Chapter 15 of T1 [ Class Note ] |
Dynamic Programming: Matrix chain multiplication: Developing the recursive solution and idea behind memoization |
18 | 12/10/23 | 11:00 | 1hr | Chapter 15 of T1 [ Class Note ] |
Dynamic Programming: Matrix chain multiplication: Developing Algorithm, Complexity Analysis, Example |
19 | 13/10/23 | 12:00 | 1hr | Chapter 15 of T1 [ Class Note ] |
Dynamic Programming: Longest Common Subsequence: Problem statement, Solution approach, Developing algorithm, Complexity analysis, Example |
20 | 16/10/23 | 09:00 | 1hr | Chapter 16 of T1 [ Proof ] |
Greedy Paradigm: Elements of Greedy paradigm, Fractional Kanpsack: Problem statement formulation, Example, Building solution |
21 | 16/10/23 | 12:00 (Extra) |
1hr | Chapter 16 of T1 [ Class Note ] |
Greedy Paradigm: Fractional Kanpsack: algorithm, Complexity; 0-1 Knapsack failure with greedy, (Optional) Dynamic programming solution of 0-1 knapsack |
22 | 17/10/23 | 12:00 | 1hr | Chapter 16 of T1 [ Class Note ] |
Greedy Paradigm: Huffman Codes: Problem statement, Example, Applications of Huffman code |
23 | 19/10/23 | 09:00 | 1hr | Chapter 16 of T1 [ Class Note ] |
Greedy Paradigm: Building the solution idea of Huffman Code, algorithm, complexity analysis |
24 | 30/10/23 | 12:00 | 1hr | Chapter 16 of T1 [ Proof ] |
Greedy Paradigm: Activity selection (Problem statement, description of the greedy criteria, developing the greedy algorithm, solving an example) |
25 | 31/10/23 | 12:00 | 1hr | Chapter 21 of T1 [ Lecture Slide ] |
Data Structure for Disjoint Sets: Definition, Basic Operations, Linked-list representation of disjoint sets |
26 | 02/11/23 | 11:00 | 1hr | [ Lecture Slide ] | Graphs and their representations |
27 | 06/11/23 | 09:00 | 1hr | Chapter 22 of T1 [ Lecture Slide ] |
Graph Traversal: Breadth First Search (BFS) Problem statement, Algorithm, Complexity, Example |
28 | 07/11/23 | 12:00 | 1hr | Chapter 22 of T1 [ Lecture Slide ] |
Graph Traversal: Depth First Search (DFS) Problem statement, Algorithm, Complexity, Example |
29 | 09/11/23 | 11:00 | 1hr | Chapter 23 of T1 [ Lecture Slide ] |
MST: Kruskal’s algorithm, Example, Complexity |
30 | 10/11/23 | 12:00 | 1hr | Chapter 23 of T1 [ Lecture Slide ] |
MST: Prim’s algorithm, Example, Complexity |
31 | 13/11/23 | 12:00 | 1hr | Chapter 24 of T1 [ Lecture Slide ] [ Class Note ] |
Single Source Shortest Path: Bellman-Ford Algorithm, Example, Complexity |
32 | 14/11/23 | 12:00 | 1hr | Chapter 24 of T1 [ Lecture Slide ] |
Single Source Shortest Path: Dijkstra’s Algorithm, Example, Complexity |
33 | 17/11/23 | 12:00 | 1hr | Chapter 25 of T1 [ Lecture Slide ] |
All pair Shortest Path: Floyd-Warshall’s Algorithm, Example, Complexity |
34 | 17/11/23 | 05:30 | 1hr | Online Mode | ** QUIZ Test ** |
35 | 20/11/23 | 02:00 | 1hr | Chapter 34 of T1 [ Refer class 36 ] |
Complexity Classes: P, NP, NPC basic idea, intractable vs tractable problems, optimization vs decision problems, definition of P class, examples of P class problems |
36 | 21/11/23 | 12:00 | 1hr | Chapter 34 of T1 [ Lecture Slide ] |
Complexity Classes: NP hard, NP complete, co-NP classes, polynomial time reduction and its significance, relationship between P, NP, NPC, NP-hard, co-NP |
37 | 23/11/23 | 11:00 | 1hr | Chapter 35 of T1 [ Lecture Slide ] [ Lecture Slide ] |
Handling NP complete problems: Idea of approximation algorithms, approximation ratio, 2-approximation algorithms for Vertex cover and Euclidean TSP, examples |
38 | 25/11/23 | 10:15 | 1hr | Chapter 32 of T1 [ Lecture Slide ] |
String Matching: Problem statement, Preliminary Idea, Naive algorithm, Example, complexity of naive algorithm; Rabin-Karp Method: Basic idea, Mathematical background, Horner’s rule, Polynomial evalution, Algorithm, Complexity, Example |
39 | 25/11/23 | 11:15 | 1hr | Chapter 30 of T1 [ Refer class 40 ] |
FFT: Polynomial addition, multiplication, evaluation; coefficient vs point-value representaion of polynomials and basic operations, |
40 | 25/11/23 | 12:15 | 1hr | Chapter 30 of T1 [ Lecture Slide ] |
FFT: Fourier transform, DFT and inverse DFT to translate between polynomial representations, quick discussion on complex roots of unity; Divide and conquer algorithm of FFT, complexity analysis |