ALGORITHMS PPT PDF

Course Overview

The need for efficient algorithms arises in nearly every area of computer science. But the type of problem to be solved, the notion of what algorithms are "efficient," and even the model of computation can vary widely from area to area. In this second course in algorithms, we will survey many of the techniques that apply broadly in the design of efficient algorithms, and study their application in a wide range of application domains and computational models. Techniques to be covered include amortization, randomization, fingerprinting, word-level parallelism, bit scaling, dynamic programming, network flow, linear programming, fixed-parameter algorithms, and approximation algorithms. Domains include string algorithms; network optimization; parallel algorithms; computational geometry; online algorithms; external memory, cache, and streaming algorithms; and data structures.

The prerequisites for this class are undergraduate courses in algorithms (e.g., 6.046) and discrete mathematics and probability (e.g., 6.042), in addition to mathematical maturity.

The coursework will involve problem sets and a final project that is research-oriented. For more details, see the handout on course information (HTML).

Lectures

1.	Course introduction. Fibonacci heaps. MST.(scribe notes, latex source) (raw notes on intro, Fibonacci heaps).
2.	Persistent data structures (notes, sources) (raw notes on persistent data structures).
3.	Splay trees (old scribe notes, old latex sources, raw notes ).
4.	Hashing. (old scribe notes, old latex sources) (raw notes on hashing).
5.	Perfect Hashing. Dijkstra's Algorithm. Dial's Algorithm. Tries. (Erik's lecture notes)
6.	van Emde Boas queues. (old scribe notes, old latex sources) (raw notes on multi-level buckets, and vEB queues). Network Flows (scribe notes, latex sources, raw notes on flow). (Erik's lecture notes)
7.	Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling. (see notes from previous lecture)
	Optional Lecture: Link cut trees (raw notes)
	student holiday, no class
8.	Reductions between Flow Problems. Bipartite Matching. Shortest Augmenting Path. Blocking Flows (scribe notes, latex sources) and (scribe notes, latex sources).
9.	Min-Cost Flows. Definitions. Algorithms. feasible prices. complementary slackness. (scribe notes, sources, raw notes on min-cost flow). Min-Cost Flows: shortest augmenting path; pseudopolynomial solution. (scribe notes, sources).
	No class
10.	Linear-programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima. (scribe notes, sources, raw notes on linear programming).
11.	Linear-Programming: Duality. (scribe notes, sources)
	Columbus day, no class
12.	Monday Schedule: Linear-Programming: Complementary slackness. LP algorithms
13.	Linear-Programming algorithms: Simplex, Ellipsoid. (old scribe notes with sources) (scribe notes, latex sources)..
14.	Linear-Programming Algorithms: Interior Point. NP-hard problems. Approximation Algorithms. (scribe notes, latex sources).
15.	Relative Approximations. PAS and FPAS. Scheduling.
16.	Enumeration. Relaxations. 3/2-approximation for TSP. (notes, sources).
	[Optional]: PTAS for Geometric TSP
17.	Fixed Parameter Algorithms. (Erik's notes)
18.	Online Algorithms. (Erik's notes)
19.	ILP relaxations. Randomized Rounding. Fixed-parameter tractability. (scribe notes, sources,scribe notes, sources) Treewidth. (notes, sources)
20.	Online algorithms: paging. ski rental, stock market, load balancing. (notes, sources, notes, sources)
21.	Randomized online algorithms, adversaries. k-server. (notes, sources)
22.	Computational geometry: orthogonal range search, sweep algorithms (segment intersections) (notes, sources)
23.	Computational geometry: convex hull, Computational geometry: Voronoi diagrams (notes, sources, notes)
	No Class - Veteran's day
24.	External memory algorithms. Cache oblivious algorithms (raw notes)