CSE221 Lesson Plan, Spring 2025

Mid-term: March 19, 8:00 am Course Outline: [Link]

Final:

Class # Topics Materials

0 Ice breaking [Link]
1. Introduction: Algorithms for accuracy, efficiency (space, time); Algorithms in real world Iterative time complexity: [Link]
1
2. Time Complexity (recap): RAM Model, Loop iterations vs execution time, Growth Functions, best-worst scenario
Searching algorithms Linear: [Link]
1. Binary: Logical explanation on the logarithmic time complexity, fitness/feedback function, finding upper - lower bound Binary: [Link]
2
2. Ternary: Concept, Advantages over binary search Ternary: [Link]
3. Balancing between no. of search steps and cost of each step: why quaternary search is not that popular
Sorting algorithms Animated simulations from: [Link]
3 1. Case analysis on N^2 sorting algorithms: Bubble, Insertion/Selection; # of iterations, # of swaps on best/worst scenario
2. Linear (case specific) time sorting: Count sort, a good example of why nested iterations is not always multiplied for time complexity
Sorting contd. Merge: [Link]
4
1. NlgN sorting: Merge, Quick (fixed and random pivots) Quick: [Link]
5 Quiz + Lagged discussion (if any)
6 Asymptotic Notations: upper, lower, tight bound complexity Iterative time complexity: [Link]
Divide and Conquer (DnC) algorithms Max-sum subarray: [Link]
7 1. Look back to merge, quick sort
2. Max-sum subarray: O(NlgN) [can also be solved in O(N^3), O(N^2), O(N)]
8 DnC contd.: Karatsuba multiplication Karatsuba: [Link]
9 Time complexity of recursive/DnC algorithms: recursion tree, substitution method, master theorem Recursive Time complexity: [Link]
10 Quiz + Review
Mid Semester Examination
Graph Introduction Graph intro: [Link]
1. Types: directed-undirected, weighted-unweighted, sparse-dense
9
2. Degree of vertices, theorems, Eulerian path/circuit
3. Adjacency matrix vs list: Space, and Time complexity
10 DFS: traversal, Edge classification, cycle detection bfs dfs: [Link]
11 BFS: traversal, shortest path on unweighted graph, Bicolorable/Bipartite graph detection, cycle detection (odd or even length) bfs dfs: [Link]
What is DAG, Topological ordering, Strongly Connected Components (SCC, Kosaraju's algo) top sort: [Link]
12
SCC: [Link]
13 Shortest path algo: What is SSSP and APSP, Dijkstra's algo, Negative-weight edges in play MST+Dijkstra: [Link]
14 MST: Kruskal's (+DSU) MST+Dijkstra: [Link]
Greedy: Huffman, Interval scheduling (covered in lab before mid) Greedy Basics, time scheduling: [Link]
15
Huffman: [Link]
DP-1: Fractional vs 0-1 Knapsack fractional knapsack: [Link]
17
DP Basics, 0-1 knapsack: [Link]
DP-2: LCS, Recurrence relation, Properties: overlapping subprob and opt. substructure
18
LCS: [Link]
19 Review
Final Examination

Quiz: 20 (best 3 out of 4, or as instructed by course teacher)

Assignment: 05 (4 assignments)
Marks Distribution Mid Semester Exam: 20
Final Exam: 30
Lab: 25