CMSC 351 ALGORITHMS

Catalog Description

A systematic study of the complexity of some elementary algorithms related to sorting, graphs and trees, and combinatorics. Algorithms are analyzed using mathematical techniques to solve recurrences and summations.

Prerequisite

CMSC 214, CMSC 250.

Text

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

Topics

  1. Order Notation
  2. Recurrences (of the type they use to analysis algorithms)
  3. Divide-and-Conquer algorithms (integer mult and/or matrix mult)
  4. Graph Algorithms (Dijkstra's algorithm, shortest path)
  5. Combinatorics and Probability
  6. Sorting
  7. Overview of Data Structures (Heaps, Union-Find)
  8. Brief Intro to NP-Completeness
  9. Optional: Libraries of Data Structures like LEDA, etc.

Typical Grading and Workload