Advanced Algorithm Design and Optimization

This unit explores intermediate-to-advanced algorithmic techniques and data-structure strategies for solving computational problems at scale, including graph algorithms, hashing, recursion, randomized methods, streaming/sketching, and matrix optimizations. Students will learn to design, implement, and evaluate algorithms with attention to correctness, complexity, and practical performance (including hardware acceleration), building on foundational concepts from earlier units and preparing for a culminating unit focused on applied systems and integration.

Learning Objectives

• Analyze algorithmic paradigms (greedy, divide-and-conquer, recursion, randomization, reduction) and their time/space trade-offs on problems such as 3SUM, SAT, matrix multiplication, and streaming sketches
• Apply appropriate data structures (trees, heaps, hash tables, adjacency lists/matrices) and graph algorithms (MST, PageRank, shortest paths) to design and implement correct solutions for representative problems
• Demonstrate techniques to improve algorithm performance—such as sketching/streaming, heuristics, parallelism, and hardware acceleration (SIMD/GPU)—through implementation and empirical benchmarking
• Evaluate and select algorithmic approaches using formal reductions, complexity analysis, and measured performance to justify choices under given resource constraints