CMSC 451 DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS

Catalog Description

This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their complexity. General topics include sorting, selection, graph algorithms, and basic algorithm design paradigms (such as divide-and-conquer, dynamic programming and greedy algorithms), lower bounds and NP-completeness.

Prerequisites

CMSC 214 and CMSC 251.

Topics

  1. Review of mathematical preliminaries (1 week)

    Order notation, summations, recurrences.

  2. Graph exploration (2.5 weeks)

    Connected components, biconnected components, topological sorting, strongly-connected components.

  3. Greedy Algorithms (2.5 weeks)

    Minimal spanning trees, shortest paths, scheduling.

  4. Divide-and-Conquer (2.5 weeks)

    Merge sort, quicksort, median and selection sorts; lower bounds for finding minimum and sorting; Strassen's matrix multiplication algorithm.

  5. Dynamic Programming (2.5 weeks)

    Shortest paths, Warshall's algorithm, optimal search trees, memory functions.

  6. NP-completeness (3 weeks)

    NP-completeness: introduction to reductions, the classes P and NP, NP-complete problems, approximation algorithms.

Course Text

Thomas Cormen, Charles Leiserson, Ron Rivest, Introduction to Algorithms, McGraw Hill and MIT Press, 1990.

Typical Grading and Workload