Courses:

Advanced Algorithms >> Content Detail



Calendar / Schedule



Calendar

LEC #TOPICSKEY DATES
1Course Introduction

Fibonacci Heaps
2MST

Persistent Data Structures
3Splay Trees
4Splay Trees (cont.)

Suffix Trees

Tries
Problem set 1 due
5Suffix Trees (cont.)

Tries (cont.)

Dial's Algorithm
6Dijkstra's Algorithm

Van Emde Boas Queues
Problem set 2 due
7Van Emde Boas Queues (cont.)

Hashing
82-Level Hashing

Network Flows
9Network Flows: Augmenting Paths, Maximum Augmenting Paths, ScalingProblem set 3 due
10Reductions between Flow Problems

Bipartite Matching

Shortest Augmenting Path

Blocking Flows
11Blocking Flows (cont.)
Recitation Topics: Dynamic Trees, Push-Relabel Max-Flow Algorithm
12Min-Cost FlowsProblem set 4 due
13Min-Cost Flows (cont.)

Linear Programming
Problem set 5 due
14Linear Programming (cont.)

Structure of Optima

Weak Duality
15Linear Programming (cont.)

Strong Duality
Recitation Topic: SimplexProblem set 6 due
16Linear Programming (cont.)

Complementary Slackness

Algorithms: Simplex, Ellipsoid
17Linear Programming (cont.)

Algorithms: Interior Point

NP-hard problems
Problem set 7 due two days after Lec #17
18Approximation Algorithms
194/3-Approximation for TSP
20Relaxations

Directed TSP
Problem set 8 due
21Randomized Rounding

Chernoff Bound

Fixed Parameter Tractability

Kernelization
22Online Algorithms (Ski Rental, Load Balancing, Paging)Problem set 9 due
23Randomized Online Algorithms (Adversaries, Fiat's Marking Algorithm, Potential Functions, Yao's Minimax Principle)
24K-Server Problem

Double-Coverage Algorithm

Computational Geometry Introduction (Orthogonal Range Search)
Problem set 10 due
25Sweep Algorithms (Convex Hull, Segment Intersection, Voronoi Diagrams)
26Sweep Algorithms (Voronoi Diagrams)

Randomized Incremental Constructions

Backwards Analysis

Linear Programming in Fixed Dimension
Problem set 11 due two days after Lec #26
27(Optional Material) External Memory AlgorithmsProblem set 12, problem 1 due
28(Optional Material) Cache Oblivious Algorithms: Matrix Multiplication, Linked Lists, Median
29(Optional Material) Cache Oblivious Algorithms: Search

Streaming Model
Rest of problem set 12 due three days after Lec #29

 








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