• for

Courses:

Advanced Algorithms >> Content Detail


Table of Contents



Lecture Notes



Lecture Notes

This section contains documents that could not be made accessible to screen reader software. A "#" symbol is used to denote such documents.

Although some of the lecture below were scribed during the 2005 version of this course, many of the scribed notes below are from previous versions of the course. These older notes were made available to the students.

Scribed notes were taken by the students and used with permission.

The instructor notes often span several lectures


LEC #TOPICSSCRIBE NOTESInstructor NOTES
1Course Introduction

Fibonacci Heaps		Fibonacci Heaps (PDF) (Courtesy of David Andersen, Ioana Dumitriu, John Dunagan, and Akshay Patil.)(PDF 1)

(PDF 2)
2MST

Persistent Data Structures		Persistent Data Structures (PDF) (Courtesy of Sommer Gentry and Eddie Kohler.)(PDF)
3Splay TreesSplay Trees (PDF) (Courtesy of Xin Zhang.)(PDF)
4Splay Trees (cont.)

Suffix Trees

Tries		Suffix Trees and Fibonacci Heaps (PDF)(PDF)
5Suffix Trees (cont.)

Tries (cont.)

Dial's Algorithm
6Dijkstra's Algorithm

Van Emde Boas Queues		Van Emde Boas Queues (PDF)# (Courtesy of Abhi Shelat, Andrew Menard, and Akshay Patil.)(PDF)
7Van Emde Boas Queues (cont.)

Hashing		(PDF)
82-Level Hashing

Network Flows		Maximum Flows (PDF) (Courtesy of Alexandr Andoni.)(PDF)
9Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling
10Reductions between Flow Problems

Bipartite Matching

Shortest Augmenting Path

Blocking Flows
11Blocking Flows (cont.)
12Min-Cost FlowsMin-Cost Flow Algorithms (PDF) (Courtesy of Wendy Chang.)(PDF)
13Min-Cost Flows (cont.)

Linear Programming		(PDF)
14Linear Programming (cont.)

Structure of Optima

Weak Duality		Duality (PDF) (Courtesy of Jay-Kumar Sundararajan.)
15Linear Programming (cont.)

Strong Duality		Duality(PDF) (Courtesy of Jay-Kumar Sundararajan.)
16Linear Programming (cont.)

Complementary Slackness

Algorithms: Simplex, Ellipsoid		Duality (PDF) (Courtesy of Jay-Kumar Sundararajan.)
17Linear Programming (cont.)

Algorithms: Interior Point
18Approximation Algorithms

NP-hard problems		(PDF)
194/3-Approximation for TSP
20Relaxations

Directed TSP
21Randomized Rounding

Chernoff Bound

Fixed Parameter Tractability

Kernelization		(PDF)
22Online Algorithms (Ski Rental, Load Balancing, Paging)Lower Bounds for Competitive Ratios of Randomized
Online Algorithms (PDF) (Courtesy of Chun-Chieh Lin.)		(PDF)
23Randomized Online Algorithms (Adversaries, Fiat's Marking Algorithm, Potential Functions, Yao's Minimax Principle)Lower Bounds for Competitive Ratios of Randomized
Online Algorithms (PDF) (Courtesy of Chun-Chieh Lin.)
24K-Server Problem

Double-Coverage Algorithm

Computational Geometry Introduction (Orthogonal Range Search)
25Sweep Algorithms (Convex Hull, Segment Intersection, Voronoi Diagrams)Sweep Line (PDF) (Courtesy of Matt Rasmussen.)(PDF)
26Sweep Algorithms (Voronoi Diagrams)

Randomized Incremental Constructions

Backwards Analysis

Linear Programming in Fixed Dimension
27(Optional Material) External Memory Algorithms(PDF)
28(Optional Material) Cache Oblivious Algorithms: Matrix Multiplication, Linked Lists, Median
29(Optional Material) Cache Oblivious Algorithms: Search

Streaming Model
29(Optional Material) Parallel Algorithms
(PDF)

Lecture notes from the 2004 version of this course.


LEC #TOPICSSCRIBE NOTES
1Course Introduction

Fibonacci Heaps		(PDF)#  Courtesy of David Andersen, Ioana Dumitriu, John Dunagan, and Akshay Patil.) 
2Persistent Data Structures

Suffix Trees		(PDF 1) (Courtesy of Sommer Gentry and Eddie Kohler.)

(PDF 2) (Courtesy of Jiawen Chen.)
3Suffix Trees (cont.)(PDF)#
4Treaps
Splay Trees(PDF) (Courtesy of Naveen Sunkavally.)
5Hashing: 2-Universal, Perfect Hashing

Fingerprinting
6Fingerprinting (cont.)

Max Flows		(PDF 1) (Courtesy of Jiawen Chen.)

(PDF 2) (Courtesy of Alexandr Andoni.)
7Max Flows (cont.)
8Max Flows (cont.)
9Max Flows (Max Flow of Min Cost)
Dynamic Trees

Preflow-push Algorithm
10Min Cost Flow Algorithms

Linear Programming		(PDF 1)# (Courtesy of Brian Dean and John Jannotti.)
11Linear Programming (cont.)

Farkas Lemma

Duality		(PDF)# (Courtesy of Vinod Vaikuntanathan.)
Goldberg-Tarjan Min-cost Flow(PDF)# (Courtesy of Mohammad Hajiaghayi and Vahab Mirrokni.)
12Linear Programming: More Duality (Weak and Strong Duality)

Complementary Slackness Conditions
13Linear Programming: Complementary Slackness Conditions (Same Scribes as Above)
14LP: Interior Points Algorithm

Approximation Algorithms: Constant, Relative Approximation		(PDF)# (Courtesy of Jason Eisenberg.)
15Approximation Algorithm: PAS, FPAS, Rounding, Enumeration
16Approximation Algorithm: Rounding, Relaxation(PDF)# (Courtesy of Sachin Katti.)
17Approximation Algorithm: LP Relaxation, Randomized Rounding(PDF)# (Courtesy of Shannon McDonald.)
18Fixed Parameter Tractability(PDF)# (Courtesy of Shannon McDonald.)
19Fixed Parameter Tractability - Treewidth

Online Algorithms
20Online Algorithms (cont.): Paging, Randomization, Potential Functions
21Randomized Online Algorithms (Adversarial Models, Marking Algorithm)
22Lower Bounds for Randomized Online Algorithms

Geometry: Range Search		(PDF)# (Courtesy of Nick Harvey.)
23Convex Hulls

Voronoi Diagrams
24Voronoi Diagrams (cont.)

Randomized Incremental Construction: Binary Space Partition
25Backwards Analysis for RIC: Convex Hull, Linear Programming
26External Memory Algorithms
27Cache-oblivious Algorithms

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.