Notes: Advanced Algorithm Design

Course Outline

What is an algorithm?

About time complexity

Divide-and-Conquer

Quick Sort: algorithm, correctness, and performance analysis

Heap Sort: algorithm, correctness, and performance analysis

Binary search trees

Red-black trees

Elementary graph algorithm

Topological order and SCCs

Dynamic programming

Greedy algorithms

Selected Topics

Network flow

String match

Supplementary material

More about bipartite graphs and general matching

A proof of Tutte's 1-Factor Theorem (easy to understand)

General matching

Assignment

Assignment #1

Assignment #2

Assignment #3

Discussion on Question 3 of Assignment #2

MID-term Exam.

Projects

Projects

Transitive Closure and Query evaluation in XML databases

Bipartite graphs