CSE 421
Introduction to Algorithms
Credits
3.0
Lead Instructor
Anup Rao
Textbook
- Algorithm Design, Kleinberg
Course Description
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.
Prerequisites
either CSE 312 or CSE 322; either CSE 326 or CSE 332.
CE Major Status
Selected Elective
Course Objectives
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.
ABET Outcomes
No outcomes registered
Course Topics
- 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,
- completeness
- Example problems:
- SAT
- 3-SAT
- clique
- vertex cover
- 0-1 knapsack
- partition
- coloring