2022 S6D
CST 306 Algorithm Analysis and Design


Course progress Page


Course So Far
Month
 Date
 Hr.
 Progress
 Class
#
 QA
Range
 Absentees
 No. of
Absentees
 Late
 Remarks
2022
April
 20
 4 Intro, Complexity, Computability,  Modelling, MST -  pipe laying.
 1
 20-38
 23 26 27 30 36 41 50 51 57 64 65 66 6 8 10 11 15 19
 18


22
 2
 MST..., Importance of design, analysis. Re-inventing the wheel. Searching, sorting analysis discussion. Correctness - ax+b=0
 2
 39-16
 41 42 54 56 58 60 67 3 4 5 6 8 9 13 15 19 24 25 26 28 30 32 36 38
 24



6
 Alg for ax+b=0. Concept of complexity.
3
 17-39
 19 20 21 22 24 25 26 27 28 29 30 32 33 36 37 38 41 42 43 44 46 47 49 50 51 54 55 56 58 60 67 2 3 4 5 6 8 9 13 15
 39
6/5: 33 claims present
May
 5
 4
 Best, worst, average case complexities. Analysis - linear search. Analysis - recursive binary search.
 4
 40-42
 55 6 14

55 5 14
 3
9/5: 6 says it is wrongly marked as 6 instead of 5.

6
 4
 Analysis - recursive binary search, recurrence equation. Analysis - non-recursive binary search. 5
5 26 33 34 46 49 55 67
7
9/5: 46 claims present

9
 2
 Asymptotic notations
 6
 43-44
 5 30
 2


10
 1
 Algorithm classification. Recurrence relation - iterative - binary search. QS - worst case.
 7
49 59
 2


11
 1
 QS recursive - worst case -iterative. QS - best case - intuitive logical. QS recursive - best case
 8
 45-56
 63 5 22
 3
 59 4

12
 4
 Recurrence  eqn solution - recursion tree, substitution.
 9
 57-61
 57 58 1 7 9 18 22 23 38 42 44 49 55
 13


17
 4
 Master theorem
 10
 62-5
 4 8 18 28 34 39 40 45 47 49 51 54 57
 13
 22
 Says late due to sports meeting

18
 1
 AVL - LL, RR
 11
 6-12
 9 26 28 54 55 57 63
 7
 62 67

19
 4
 AVL - LR, RL
 12
 13-20
 14 18 22 30 37 45 46 47 57 64 66 1 2 4 7 10
 16
 9

24
 4
 AVL - Deletion
 13
 21-44
 28 42 45 49 55 67 1
 7
 10 15 57 3 54
 First three says - for tech fest meeting

25
 1
 AVL -Deletion. Operation complexities 14 45-60 55 58 63 9 16 26 42 7
 1 45 7 67 54 18 29 31 28 49

26
 4
 Disjoint sets - eg. Kruskal,  Greedy concept also.
 15
9 18 49 55 56
 5


27
 1
 Disjoint sets - representation - LL, Tree - algs  16
 61-4
 9 10 11 28 49 54 55
 7
 5 59 56

31
 6
 Disjoint sets -LL algs. Path compression. Union by rank. 17
 5-13
 10 28 30 47 49 54 55
 7

June
1
 1
 DFS - Stack, recursive; Complexity;  BFS - Q - complexity
 18
5 10 12 28 29 30 37 44 45 47 49 54 55 62
 14
 42 31

8
T1: 9.30 - 11.30
 20
58 62
 2


20
 3
 T1 discussion
 21
16 28 43 54
 4


22
 1
 T1 discussion, SCC
22
9 24 58 60 62
 5
 8 21 59 42 45

23
 6
 T1, AVL, SCC, TopSort
 23
 14-22
 21 42
 2
 15 23
 left early

24
 1
 TopSort 3 algs, complexity
 24
 23-25
 2 9 16 29 46 49 67
 7
 42 31 59 12 57 44 1 7 18 45 4 5 47 13

27
 3
 D&C , Merge sort
 25
 26-27
 57 63
 2


29
 1
 MS - analysis. Strassen
 26
 28-32
 31 10 27 35 50 51
 6
 29
 31 in close to end

30
 6
 Remedial session is scheduled
 No one attended. Happy to know that all are well versed in the subject
July
 1
 1
 Greedy alg. Fractional knapsack
 27
 33-35
 37 46 49
 3
 45

4
 3
 ..., dijkstra's sp
 28
 36-41
 24 26 65
 3


6
 1
 ... complexity, DP - Mat mult order
 29
 42-62
 8 31 63
 3
 3

7
 6
 CA1
30
30 31
 2


8
 1
 Mat mult order - alg, illustration
 31
 63-8
 63 3 26 30
 4
 59 47 45 32 56 38

12
 6
 ... illustration, complexity
 32
39 49
 2
68 joined

13
 1
 DP - optimality pple, control abstraction, Floyd-Warshall APSP, illustration, complexity
 33
 9-10
 11 15 23 24 25 34 39 43 45
 9
 32 49 59

15
T2: 10 - 12
35
39
 1


18
 3
 T2 short discussion.
Back tracking, NQueens problem.
 		36
46 49
 2


21
 6
 Remedial session - Floyd-Warshall APSP




Attended by 26 64 62 65 8 5 59

22
 1
 NQueens
 37
59 68
 1


25
 2-3
 B&B - TSP
Tractable, intractable, P, NP
 39
43 44 68
44 68
 2
1


26
 5-6
 ...., NPC, NPH, examples; Bin packing
 41
32 54 68
32 68
 2
1


27
 1
 CA2
42





29
 1
 ... ffd, P-NP-NOC, reduction
 43
30 32 43 68
 3
 42 37 67 34
August
 1
 3
 Proof - Clique, Vertex cover are in NPC. Vertex colouring.
 44
1 7 12 18 22 27 29 32 33 35 37 40 47 50 57 60 64 65 66
 19
 39

2
scheduled