EECS 4101/5101:
Advanced Data Structures
__
Tentative SYLLABUS
AMORTIZATION, SELF ADJUSTMENT and COMPETITIVENESS (3 hours):
[
Reading: CLRS 17, LN 1
,
11
]
Amortization: aggregate, accounting, and potential function methods
examples: stack with multipop, binary counter with increment
Self Adjusting Data Structures (example: dynamic tables)
Competitive on-line algorithms (examples: ski rental, the cow-path problem, the k-server problem. See LN11)
DICTIONARIES (9 hours):
[
Reading: CLRS 12,13,14,18, LN 2,3, AAW
]
1.5 hours:
Analysis of the Move-to-Front Heuristic on Linear List
[LN 2]
1.5 hours:
BST: binary trees and binary search trees
[CLRS 12]
1.5 hours:
Multi-way Search Trees, B-Trees
[CLRS 18]
1.5 hours:
Red-Black Trees, 2-3-4 Trees
[CLRS 13, AAW]
1.5 hours:
Splay Trees (a self adjusting BST)
[LN 3, AAW]
1.5 hours:
Augmenting Data Structures
[CLRS 14]
Dynamic Order Statistics
Interval Trees
PRIORITY QUEUES (5 hours):
[
Reading: CLRS 19,20*, LN 4,5, AAW
] --------- * = in CLRS 2nd edition
1 hour:
Leftist Heaps
1 hour:
Skew Heaps (a self adjusting version of leftist heap)
1 hour:
Binomial Heaps
2 hours:
Fibonacci Heaps (a quasi self adjusting version of Binomial heap)
DISJOINT SET UNION (2 hours):
[
Reading: CLRS21 and LN 6
]
COMPUTATIONAL GEOMETRY (8 hours):
[
Reading:
CLRS 33, LN 7a,7b,8, AAW
]
Preliminaries
Point-polygon inclusion (simple and convex case)
Intersection reporting among a set of line segments:
horizontal/vertical case, and general case
intersection of two (convex) polygons
intersection of half-planes,
2D Linear Programming
Polygon Triangulation - Guarding an Art Gallery
Convex Hull - diameter (farthest pair)
Closest Pair Problem - All Nearest Neighbors
APPROXIMATION ALGORITHMS
for NP-Hard Optimization Problems
(6 hours):
[
Reading:
CLRS 35, LN 9,10, AAW
]
Weighted Vertex Cover [The Pricing Method: 2-approximation]
Weighted Set Cover
[
The Pricing Method: H(n)-approximation]
The Traveling Salesman Problem (TSP):
General TSP: approximation is also NP-Hard
Metric-TSP:
2-approximation by double-MST.
1.5-approximation by Christofides' method.
Euclidean-TSP: Sanjeev Arora's PTAS [LN10]
K-Clusters [2-approximation, LN9]
0/1 Knapsack (a generalization of Subset Sum) [an FPTAS, LN9]
SELECTED TOPICS (remaining hours if any).
Randomized Algorithms [CLRS 5, LN 11], or
Linear Programming [CLRS 29, LN 11]