CS 381: Detailed Syllabus
plans to follow the syllabus outlined below. Changes and adjustments may
be made during the semester.
Mathematical Concepts for Algorithm Analysis
introduction to algorithm design (Ch. 2)
of the analysis of various sorting algorithms
- Review of
induction and other tools
notation (Ch. 3)
and the Master Theorem (Ch.
and Conquer (Ch. 9.3, 33.4)
- Selection in worst-case linear time
- Finding the closest pair in a set of points
- Greedy (Ch. 16)
(Ch. 5, 7.3, 9.2) and Streaming Algorithms
in expected linear time
- Online hiring problem
- Examples of one- and two-pass streaming algorithms
Using Data Structures in
More Graph Algorithms
data structures including heaps as priority queues (Ch. 10-12)
heaps (Ch. 6)
Primís algorithm (Ch.
Binary Search Trees (Ch. 13, 14.1-2)
of balanced tree structures
by rank and path compression techniques (Ch. 21)
to amortized analysis (Ch.
- Kruskalís algorithm (Ch.
searching and range queries
graph explorations (Ch.
search, Depth-first search
- Graph connectivity (Ch.22)
and bi-connected components
- Dijkstra, Floyd-Warshall
are lower bounds?
based sorting lower bound (Ch. 8.1)
sort and bucket sort (Ch. 8.2, 8.3)
- Problem reduction
in lower bounds
- Embarrisingly parallel algorithms
- Parallel design techniques and paradigns
to P and NP (Ch.
Cover, Set Cover, Traveling Salesman (Ch. 35.1-3)
polynomial time approximation scheme (Ch. 35.5)