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

C++ code for creating a Red-Black Tree

Red-black trees

Elementary graph algorithm

Topological order and SCCs

Dynamic programming

Greedy algorithms

Selected Topics

Network flow

String match

BWT: string compression and string matching

Massive Read Matching

Supplementary material

More about bipartite graphs and general matching

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

General matching

Transitive Closure and Query evaluation in XML databases

Bipartite graphs

Set Intersection (complete manuscript)

Assignments

Assignment #1

Assignment #2

Assignment #3

MID-term Exam.

Projects

Projects

Sample Report