The course
plans to follow the syllabus outlined below. The number of lectures listed is
an estimate. Changes and adjustments may
be made during the semester.
Introduction:
Mathematical Concepts for Algorithm Analysis (4 lectures)
·
General
introduction to algorithm design (Ch. 2)
o
Review
sorting algorithms and their analysis
o
Review
induction
·
Asymptotic
notation (Ch. 3)
·
Recurrences
(
o
Master
theorem
Algorithm Design
Techniques (10 lectures)
·
Divide
and Conquer (Ch. 9.3, 33.4) – 2 lectures
o
Selection in worst-case linear time
o
Finding the closest pair in a set of points
·
Randomization
(Ch. 5, 7.3, 9.2) - 2 lectures
o
Review
probability (Appendix C.1 – C.3)
o
Quicksort
o
Selection
in expected linear time
o
Birthday
paradox, online hiring problem
·
Dynamic
Programming (
o
Assembly-line
scheduling
o
Matrix
chain multiplication
o
Longest
common subsequence
o
Knapsack
o
Generating
a solution
·
Greedy (Ch. 16) – 3 lectures
o
Activity
selection
o
Fractional
knapsack
o
Huffman
codes
Using Data Structures in
Algorithms (9 lectures)
·
Review
prerequisite data structures (Ch. 10-12)
·
Heaps
as Priority Queues – 2 lectures
o
Binary
heaps (Ch. 6)
o
Application:
Prim’s algorithm (
o
Leftist
heaps
·
Balanced
Binary Search Trees (Ch. 13, 14.1-2) – 3 lectures
o
Overview
of existing balanced tree structures
o
Red-Black
Trees
o
Augmenting
data structures
·
Disjoint
set union-find – 3 lectures
o
Union
by rank and path compression techniques (
o
Introduction
to amortized analysis (
o
Application:
Kruskal’s algorithm (
·
2-dimensional
searching – 1 lecture
o
Using
known data structures for range queries
Lower bounds (2
lectures)
·
What
are lower bounds?
·
Comparison
based sorting lower bound (Ch. 8.1)
·
Radix
sort and bucket sort (Ch. 8.2, 8.3)
·
Introduce
the concept of problem reduction
More Graph Algorithms (8
lectures)
·
Fundamental
graph explorations (
o
Breadth-first
search
o
Depth-first
search
o
Topological
sorting
·
Graph
connectivity (Ch.22)
o
Connected
and bi-connected components
o
Strongly
connected components
·
Shortest
Paths (
o
Bellman-Ford
o
Dijkstra
o
Floyd-Warshall
·
Other
graph algorithms
NP-completeness (5
lectures)
·
Introduction
to P and NP (
·
Reductions
(
Approximation Algorithms
(3 lectures)
·
Vertex
Cover, Set Cover, Traveling Salesman (
·
Fully
polynomial time approximation scheme (Ch. 35.5)
Midterm and reviews (4
lectures)