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

Announcements + Internal Resources

External Resources

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

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)