ECE 406: Algorithm Design and Analysis

Sources and References

Equivalent UW courses — CS 341 (Algorithms), CS 466/666 (Algorithm Design and Analysis), CO 351 (Network Flow Theory)

Primary textbook — Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. Introduction to Algorithms, 4th ed., MIT Press, 2022.

Supplementary references — Kleinberg, J. and Tardos, E. Algorithm Design, Pearson, 2005; Sedgewick, R. and Wayne, K. Algorithms, 4th ed., Addison-Wesley, 2011; Dasgupta, S., Papadimitriou, C. H. and Vazirani, U. V. Algorithms, McGraw-Hill, 2006; Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.

Equivalent UW Courses

ECE 406 is the ECE department’s upper-year algorithms course and covers essentially the same syllabus as CS 341, which is the required algorithms course for CS majors. Both cover asymptotic analysis, divide and conquer, greedy algorithms, dynamic programming, graph algorithms, and an introduction to intractability. CS 466/666 is a single cross-listed course that goes a level further, spending more time on randomized, approximation, and online algorithms and on formal proofs of correctness and hardness — ECE 406 samples some of that material but with less formal depth. CO 351 is a dedicated course on network flow theory and polyhedral methods, which ECE 406 touches only through maximum flow as one topic among many.

What This Course Adds Beyond the Equivalents

Compared with CS 341, ECE 406 has a similar core but often spends slightly more time on applications that matter in engineering practice — shortest paths, matchings, and flow networks used for routing and scheduling — and slightly less time on the formal proof style of invariants and loop reasoning that CS 341 emphasizes. Relative to CS 466/666, it offers a broader but shallower view: randomized and approximation algorithms are introduced but not developed as deeply as in the graduate-level split of that course. Unlike CO 351, it does not derive the duality of linear programming or the full polyhedral theory of network flows.

Topic Summary

Asymptotic Analysis and Recurrences

The course opens with big-O, big-Omega, and big-Theta notation and the standard techniques for solving recurrences: substitution, recursion trees, and the master theorem

\[ T(n) = a\, T(n/b) + f(n). \]

Amortized analysis is introduced through aggregate, accounting, and potential methods, with applications to dynamic arrays and union-find.

Divide and Conquer

Merge sort, quicksort with randomized pivoting, Strassen’s matrix multiplication, the Karatsuba integer multiplication, and the linear-time selection algorithm illustrate the paradigm. Lower bounds for comparison-based sorting \( \Omega(n \log n) \) are proved via decision trees.

Greedy Algorithms

Interval scheduling, Huffman coding, minimum spanning trees via Kruskal and Prim, and the matroid view of greedy correctness are covered. The exchange-argument proof technique is emphasized.

Dynamic Programming

Weighted interval scheduling, longest common subsequence, edit distance, matrix-chain multiplication, knapsack, and Bellman-Ford are developed. Students learn to identify optimal substructure, overlapping subproblems, and to reconstruct solutions from DP tables.

Graph Algorithms

Breadth-first and depth-first search, topological sort, strongly connected components (Tarjan and Kosaraju), single-source shortest paths via Dijkstra and Bellman-Ford, and all-pairs shortest paths via Floyd-Warshall and Johnson’s algorithm are covered in standard form.

Network Flow

Maximum flow via Ford-Fulkerson and Edmonds-Karp, the max-flow min-cut theorem, and bipartite matching via flow are treated. Applications include assignment problems and image segmentation. The full LP duality of CO 351 is not developed.

Advanced Data Structures

Balanced binary search trees (red-black or AVL), binary heaps and binomial or Fibonacci heaps, hash tables with universal hashing, and union-find with path compression and union by rank are covered to the level needed to analyze the algorithms above.

NP-Completeness

Decision versus optimization problems, polynomial-time reductions, the classes P and NP, and Cook-Levin are stated. Standard reductions cover SAT, 3-SAT, clique, vertex cover, independent set, Hamiltonian cycle, and subset sum. Students learn to recognize intractable problems and to argue hardness by reduction.

Approximation Algorithms

For NP-hard problems, constant-factor approximations are introduced: 2-approximation for vertex cover via LP rounding or maximal matching, Christofides-style reasoning for metric TSP, and greedy approximations for set cover with an \( O(\log n) \) ratio.

Randomized Algorithms

Randomized quicksort, randomized min-cut (Karger), universal hashing, and the probabilistic method are used to show that randomness can simplify design and analysis. Expected-time bounds and Markov’s inequality are the main tools.

Search, Backtracking, and Branch-and-Bound

Systematic search with pruning is presented for problems where no polynomial algorithm is known, with worked examples on SAT, graph coloring, and the traveling salesman problem. Complexity is measured empirically rather than in worst-case terms.