Notes: Advanced Algorithm Design

Course Outline

What is an algorithm?

Asymptotic notations for time complexity bounds

Divide-and-Conquer

Recursive Equation

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

String matching with k differences in DNA databases

Massive Read Matching

Supplementary material

Bipartite graphs

Data mining

Find the Most Popular Package

Approximation Computation

Quantum computation

Turing machine

NP completeness theory - Cook theorm

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

Set Intersection (complete manuscript)

Review

Assignments

Assignment #1

Answers to Assignment #1

Assignment #2

Assignment #3

Discussion on mid-term exam.

MID-term Exam.

Projects

Sample Report