ON THIS PAGE:

Course Objectives

Prerequisites

Approach

Typical Text

Course Outline

Course Objectives

• Provide experience in rigorous analysis of algorithm complexity.
• Provide an introduction to algorithms for "hard problems," including optimization and probabilistic algorithms.

Prerequisites
COMP 550 and COMP 455.

Approach
Depth and precision are chosen over breadth of coverage; thus, the algorithms and solution techniques covered will be exemplary rather than exhaustive.

Typical Text
There is no single appropriate text. The following can be used for some topics; it may be necessary to supplement with journal articles.

• Aho, Hopcroft, Ullman: Design and Analysis of Computer Algorithms
• Cormen, Leiserson, Rivest: Algorithms
• Even: Graph Algorithms
• Garey, Johnson: Computers and Intractability
• Kozen: The Design and Analysis of Algorithms
• Tarjan: Data Structures and Network Algorithms

Course Outline
Numbers in parentheses refer to number of 75-minute lectures.

Algorithms that are practical and correct

Lower bound proofs. Sorting. (1)

• Amortization:
  • Union-find (2)
  • Fibonacci heaps (2)
• Planarity testing (or string matching or FFT) (2)

Computability and intractability


• NP-complete and NP-hard problems (1)
• NP-completeness of 3-sat (2)
• Polynomial reduction, with examples (2)
• Other classes: Co-NP, NC, RNC (2)

Algorithms that are usually fast and always correct


• Quicksort (average complexity) (1)
• Random search trees or skip lists (2)

Algorithms that are always fast and usually correct


• Primality testing or integer factorization (3)

Algorithms that are always fast and approximately correct. (Approximation algorithms)


• Traveling salesman problem. (4)

Total number of lectures (24)