COMP 251      Algorithms and Data Structures       Winter 2014

Instructor: Professor Michael Langer
Lectures: Tues, Thurs (TJ)  10:05-11:25 pm       BRONF 151

Instructor Office Hours: (ENGMC 329):
Tues/Thurs: 11:30-12:30pm + 1pm-2pm (or by appointment)

Teaching Assistants:
Bentley Oakes, Syed Ahmed, Mohammed Smaoui, Mingzhou Yang

### Lecture Schedule

1. course introduction, Official Course Outline   (slides)

#### Data Structures

1. balanced search trees (slides)
rotations, AVL trees, 2-3 trees
2. hashing (slides)
hash functions & authentication, closed hash tables: linear vs. quadratic probing
3. heaps (slides)
building a heap in O(n log n) vs. O(n), indexed heaps for changing priorities
4. disjoint-sets and union/find (PDF)
equivalence relations, union by size/height, path compression

#### Graph algorithms

1. directed graphs (PDF)
strongly connected components (SCC), directed acyclic graphs (DAG), topological orderings
2. single source shortest paths (PDF)
3. graphs with positive edge weights, Dijkstra's algorithm
4. minimum spanning trees (PDF)
cut property, Prim and Kruskal's algorithms
5. bipartite graphs (PDF)
matching, stable marriages (Gale-Shapley)
6. network flows 1 (PDF)
flow networks, flows, residual graphs, augmenting paths, Ford-Fulkerson
7. network flows 2 (PDF)
max flow = min cut, finding maximal match in bipartite graphs

#### Dynamic Programming

1. interval scheduling (PDF)
greedy approaches, weighted interval scheduling, DP and memoization
2. segmented least squares (PDF)
3. sum of subsets, knapsack (PDF)
4. shortest paths in a graph with negative weights (PDF)   (B-F code in Python)
Bellman-Ford, Floyd-Warshall
STUDY BREAK

#### Divide and Conquer

1. mergesort (review), closest pair of points in 2D (PDF)
2. Karatsuba multiplication, Master method (PDF)
3. determininistic quicksort and select, median-of-median-of-5's (PDF)

#### Probability and information theory

1. what do we mean by "average case"? (PDF)
amortization, discrete probability: random variables, linearity of expectation
2. randomized quicksort and select (PDF)
expected runtimes
3. lower bounds for comparison sorting, sorting in linear time (PDF)
decision trees, counting sort, bucket sort, more probability: independence
4. data compression (PDF)
optimal prefix codes, Huffman coding, run length coding

### Exercises, Exams, etc.

Exercises: balanced search trees

Exercises: hashing, hashtables

Exercises: heaps and priority queues

Exercises: disjoint sets, union-find

Assignment 1 (PDF)   (code)   (solution)   (test code for grading)

Exercises: SCCs, DAGs

Exercises: Dijkstra's algorithm

Assignment 2   - (PDF) & (code)    (solutions)

Exercises: Minimal spanning trees

Midterm 1 exam   and solutions

Exercises: Bipartite graphs

Exercises: Network flows 1

Exercises: Network flows 2

Exercises: Interval scheduling

Exercises: Segmented least squares

Exercises: Subset sum and knapsack

Exercises: Bellman-Ford, Floyd-Warshall

Midterm 2 exam   and solutions

Exercises: closest pair of points
Exercises: master method
Exercises: selection

Assignment 3   (PDF) & (code)  & (solutions)
Assignment 4   (PDF) & (code) ,   solutions: Q1  & Q2

Exercises: average case

Exercises: randomized select

Exercises: lower bounds and linear sorting

Exercises: data compression

(final exam) & (solutions)