• Course logistics and expectations
• Definition and examples of algorithms
• Rate of growth and efficiency
• Introduction to asymptotic notation

Assessments: None

Reading Materials:

• K&T Ch 1.1, 2.1
• DPV Ch 0.1-0.2

• Big-O notation (formal definition)
• Big-Omega and Big-Theta notations
• Common growth functions and relationships
• Analysis of iterative algorithms (examples)

Assessments:

• Quiz 1 (Syllabus & Intro Lecture) due

Reading Materials:

• K&T Ch 2.2
• DPV Ch 0.3

• Introduction to recursive algorithms
• Base cases and recursive cases
• Mathematical induction principles
• Proving correctness of recursive algorithms

Reading Materials:

• K&T Ch 2.4
• DPV Ch 0.3 + Exercises

• Introduction to divide-and-conquer paradigm
• General problem-solving strategy
• Analyzing divide-and-conquer algorithms
• Setting up and solving recurrence relations

Assessments:

• PS1 (Asymptotic Analysis and Recursion) released

Reading Materials:

• K&T Ch 5.1-5,2
• DPV Ch 2.2

• Brief overview of elementary sorts
• Proof of Ω(n log n) lower bound for comparison sorts
• Merge sort algorithm and implementation
• Analysis of merge sort using recurrence relations

Reading Materials:

• DPV Ch 2.3

• Quicksort algorithm and partitioning strategies
• Average and worst-case analysis of quicksort
• Heapsort algorithm and analysis
• Brief introduction to non-comparison sorts

Assessments:

• Quiz 2 (Recursion/Divide and Conquer) due

Reading Materials:

• K&T Ch 13.5
• DPV Ch 2.3 + Exercises

• Greedy algorithm design principles
• Greedy choice property and optimal substructure
• Minimum spanning tree problem
• Prim’s algorithm (implementation and analysis)
• Kruskal’s algorithm and union-find data structure

Reading Materials:

• K&T Ch 4.1-4.2, 4.5-4.6
• DPV Ch 5.1

• Dijkstra’s shortest path algorithm
• Implementation using priority queues
• Bellman-Ford algorithm for negative edges
• Detecting negative cycles
• Comparison between approaches

Assessments:

• PS1 due (extended to two weeks for first assignment)
• PS2 (Graph Algorithms) released
• Quiz 3 (Greedy) due

Reading Materials:

• K&T Ch 4.4
• DPV Ch 4.5-4.6

• Data compression concepts
• Prefix codes and their properties
• Huffman coding algorithm
• Proof of optimality and analysis
• Applications in compression systems

Reading Materials:

• K&T Ch 4.8
• DPV Ch 5.2

• Kosaraju’s algorithm for SCCs (2-pass DFS)
• Tarjan’s algorithm for SCCs and bridges
• Applications in compiler optimization and network reliability
• Proofs of correctness and complexity analysis

Assessments:

• Quiz 4 (Greedy Algorithms II) due
• Discussion 1 (Greedy vs DP) due
• Peer Review 1 (Code) due

Reading Materials:

• K&T Ch 3.5 (Strong Connectivity)
• DPV Ch 3.3-3.4 (Depth-First Search in Directed Graphs)
• Bonus: Tarjan’s original paper excerpts (provided)

• Dynamic programming principles
• Overlapping subproblems and optimal substructure
• Memoization vs. tabulation approaches
• Rod cutting and making change problems
• 0/1 Knapsack problem and solution

Assessments:

• PS2 due (moved earlier to avoid conflict with midterm)
• PS3 (Dynamic Programming) released

Reading Materials:

• K&T Ch 6.1-6.2, 6.4
• DPV Ch 6.1-6.2, 6.4

• Comprehensive examination of topics covered so far

Assessments:

• Midterm Exam

• Longest common subsequence
• Longest increasing subsequence
• Edit distance problem
• Applications in computational biology and text processing

Reading Materials:

• K&T Ch 6.6
• DPV Ch 6.3

• Decision problems and language recognition
• Complexity classes (P, NP, co-NP)
• NP-completeness and reductions
• Cook’s theorem and SAT problem (overview)

Reading Materials:

• K&T Ch 8.3-8.4
• DPV Ch 8.1-8.2

• Famous NP-complete problems
• Reduction techniques
• Practice with reductions
• Implications of NP-completeness

Assessments:

• Quiz 5 (DP) due
• PS3 due
• PS4 (NP-Completeness) released

Reading Materials:

• K&T Ch 8.3-8.5
• DPV Ch 8.3

• Approximation ratio
• Approximation schemes (PTAS, FPTAS)
• Examples: traveling salesman problem, vertex cover
• Performance guarantees and inapproximability

Reading Materials:

• K&T Ch 11.1-11.3
• DPV Ch 9.2

• Randomization in algorithm design
• Las Vegas vs. Monte Carlo algorithms
• Randomized quicksort
• Randomized selection algorithm
• Analysis of expected running time

Assessments:

• Quiz 6 (NP) due
• Peer Review 2 (Proofs) due

Reading Materials:

• K&T Ch 13.1, 13.3
• DPV Ch 1.5, 2.5

• Naive string matching
• Rabin-Karp algorithm
• Knuth-Morris-Pratt algorithm
• Applications and performance comparison

Reading Materials:

• DPV Ch 9.2

• Convex hull algorithms
• Line intersection problems
• Closest pair of points
• Applications in computer graphics and robotics

Assessments:

• Quiz 7 (Approximation) due
• PS4 due
• PS5 (Advanced Topics) released

Reading Materials:

• K&T Ch 13.7
• DPV Ch 3.4

• Flow networks and terminology (capacity, flow, residual networks)
• Maximum flow problem
• Ford-Fulkerson method
• Analysis and implementation considerations

Reading Materials:

• K&T Ch 7.1-7.2
• DPV Ch 7.2

• Edmonds-Karp algorithm (analysis and implementation)
• Applications: bipartite matching, assignment problems
• Edge-disjoint paths
• Additional flow variants and applications

Assessments:

• Quiz 8 (Strings) due
• Discussion 2 (Flow Apps) due

Reading Materials:

• K&T Ch 7.3
• DPV Ch 7.2-7.3

• Linear programming formulation
• Canonical and standard forms
• Geometric interpretation
• Converting problems to LP formulations

Reading Materials:

• K&T Ch 7.4-7.5
• DPV Ch 7.1

• Simplex algorithm overview
• Duality in linear programming
• Applications of linear programming
• Integer linear programming

Assessments:

• Quiz 9 (Network Flow) due

Reading Materials:

• K&T Ch 7.6
• DPV Ch 7.1

• All-pairs shortest paths problem
• Floyd-Warshall algorithm and implementation
• Dynamic programming approach to matrix path problems
• Introduction to PSPACE-complete and #P-complete problems
• Parameterized complexity

Reading Materials:

• K&T Ch 6.8, 8.4, 8.9, 8.10
• DPV Ch 4.6-4.7, 8.4

• Comprehensive review of all course material
• Practice problems
• Q&A session
• Exam preparation strategies

Assessments:

• Quiz 10 (LP) due
• PS5 due

Reading Materials: Comprehensive review

• Comprehensive assessment of course material

Assessments:

• Final Exam