CSE421: Introduction to Algorithms

3

Techniques for design of efficient algorithms. Methods for showing lower bounds on computational complexity. Particular algorithms for sorting, searching, set manipulation, arithmetic, graph problems, pattern matching.

CSE 322; CSE 326.

Techniques for design and analysis of efficient algorithms. Particular algorithms for wide variety of problems including graph problems, pattern matching, FFT, scheduling and many others. Theory of NP-completeness.

Kleinberg and Tardos, Algorithm Design. Addison Wesley

Learn basic techniques for design and analysis of algorithms, including correctness proofs. Learn a number of important basic algorithms. Learn how to prove that problems are NP-complete.

Main Techniques: Design: Induction, Graph search, Divide and Conquer, Greedy, Dynamic Programming, Network Flow Analysis: Asymptotic Analysis, Recurrences. Intractablity: Reduction. Typical Algorithm coverage: depth- and breadth-first search, bi- and/or strongly connected components, shortest paths, min spanning trees, transitive closure, flows and matchings, Strassen's method, FFT, knapsack, edit distance/string matching, scheduling. Intractablity: Reduction. P, NP, verification/certificates/witnesses, nondeterminism, reduction, completeness. Example problems: SAT, 3-SAT, clique, vertex cover, 0-1 knapsack, partition, coloring.

3 50 minute lectures per week or 2 80 minute lectures per week.

(a) an ability to apply knowledge of mathematics, science, and engineering

(e) an ability to identify, formulate, and solve computer engineering problems

(m) knowledge of discrete mathematics

karlin