CS 535: Design and Analysis of Algorithms

Objectives

• The course will advance the study of algorithms.
• The study will include techniques of algorithm design and design of data structures for improved complexity bounds.

Prerequisites

• CS 430.

Syllabus

• Data Structures for Improved Algorithmic Complexity
  • Heapsort and Heaps
  • Binomial Heaps
  • Fibonacci Heaps
  • Application of these structures to Minimum Spanning Trees
  • Balanced Binary Search Trees, such as Splay Trees
  • Union-Find Data Structure
• Algorithmic Techniques
  • Greedy Algorithms and Matroids
  • Shortest Paths and Dynamic Programming
  • Divide and Conquer
    • Typical examples: Sorting and Order Characteristics.
  • Randomized algorithms such as Treaps
  • Graph algorithms -- Biconnectivity, Strong Connectivity
  • Network Flows and Bipartite Matching
  • NP-Complete problems

Revised March 2006