COMP-251B Data Structures and Algorithms - Winter 2009

Lecture Descriptions, Homework, and Play

Text Book: Introduction to Algorithms by Udi Manber

Week: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13

"An idea is best made the possession of the learner by the method by which it has been found.'' Ernst Mach, 1906

Week 1 - Jan 6 and 8

Week 2 - Jan 13 and 15

Week 3 - Jan 20 and 22
Lecture 5: Polygon Triangulation Algorithms

Week 4 - Jan 27 and 29

Week 5 - Feb 3 and 5

    Lecture 9: Complexity Classes and Examples
    1. Solving recurrence relations by guess and test plus induction
      1. Master theorems
    2. Running time: constant, logarithmic, linear, n log n, quadratic, cubic, polynomial, exponential, factorial
    3. Proof that the exponential function grows faster than the polynomial function
    4. Examples
      1. Binary search
      2. Sorting: insertion sort, selection sort, bubble sort, merge sort
      3. Travelling salesman problem
        1. Proof that solution must be a simple circuit
Problem Assignment 3 "due"  February 10
  1. Algorithms for computing the Fibonacci function
  2. Binary search
  3. The skyline problem in computer graphics
  4. Analysis of heap-sorting
Lecture 10:
Bucket sorting, floor functions, convex hulls, and lower bounds via reduction
  1. Probabilistic analysis of bucket-sort:
    1. Proof that bucket-sort takes O(n) expected time
  2. Convex hull algorithms for planar point sets:
    1. Rosenberg and Landgridge algorithm in O(n^3) time
    2. Jarvis algorithm in O(n^2) time
    3. Graham's algorithm  in O(n log n) time
  3. Lower bounds via reduction:
    1. Example with convex hull problem
    Reading Assignment
    1. Text: 5.1 and 5.2 - Polynomial evaluation
    2. Text: 9.2 - Exponentiation
    3. Text: 5.6 - The skyline problem (divide and conquer)
    4. Text: Chapter 6, section 6.4 up to and including 6.4.3
    Suggested Play
    1. Web: 1.4.1.6 - Fibonacci numbers and domino tilings
    2. Web: - 19.2.1.1 - Sorting animation applets

Week 6 - Feb 10 and 12 - Class Test #1 Tuesday Feb 10

  1. Tree traversals:
    1. The Euler-Tour traversal of a tree
      1. Preorder traversal
      2. Inorder traversal
      3. Postorder traversal
  2. Lower bounds on the complexity of problems
  3. Computing the maximum gap in O(n) time with floor functions

Week 7- Feb 17 and 19

  1. Addition, Multiplication and Fast Fourier Transforms
  2. Lower bounds via reduction continued:
    1. Example with non-crossing Hamiltonian circuit of a point set
  3. Convex hull algorithms for planar point sets continued:
    1. The 3-coins procedure and applications:
      1. Graham's algorithm  in O(n log n) time
      2. Proof that the 3-coins algorithm computes the convex hull of a star-shaped polygon in O(n) time
      3. Examples of polygons triangulated with 3-coins algorithm
  4. Illumination problems in computer graphics
    1. Illuminating the edges of a polygon versus its interior

Week 8 - Feb 24 and 26 (Feb 24 and 26 no class due to study break)

    Lecture 15: String comparison
    1. String-comparison algorithms
      1. Hamming distance
      2. Euclidean distance
      3. Swap-distance
      4. Directed swap distance (scaffold assignment problem)
      5. Linear assignment problems
    Lecture 16
    1. Graph embeddability
    2. Divide and conquer with the master-theorem method
      1. Merge sort
      2. Triangulating planar point sets (merging with 3-coins algorithm)
      3. Integer multiplication in O(n^1.585) worst case time
    3. Quicksort with secondary storage
    Reading Assignment
    1. Handout: Integer multiplication in O(n^1.585) worst case time
    2. Text: 6.8 - Dynamic programming (edit distance in sequence comparison)
    3. Web: 21.1 - Dynamic programming (edit distance in sequence comparison)
    4. Text: 6.4.4 - Quicksort and randomized quicksort
    5. Web: 19.2.1.7 - Quicksort tutorial
    6. Web: 19.2.1.8 - Expected analysis of quicksort
    Reading Assignment for 252 students only
    1. Text: 9.4 - Polynomial multiplication
    2. Text: 9.6 - The Fast Fourier Transform
    Suggested Play
      Web: 21.1 - Applet for Dynamic programming (edit distance in sequence comparison)

Week 9 - March 3 and 5

Week 10 - March 10 and 12

Week 11 - March 17 and 19

    1. Eulerian circuits:
Suggested Play

Week 12 - March 24 and 26

Lecture 23: 2nd In-Class test (Tuesday March 24)
Lecture 24: More Graph Theory and Hamiltonian Circuits

Week 13 - March 31 and April 2

    Lecture 25: Greedy algorithms (diameter)
1. Hill climbing
2. Searching for local maxima
3. Approximate algorithms

    Lecture 26: Greedy algorithms (diameter)

1. Rotating calipers algorithm
Reading Assignment
  1. Web: 8.1 - Greedy algorithms
  2. Web: 8.2 - The rotating calipers
  3. Web: 8.2.1 - The rotating caliper page
  4. Web: 8.2.2 - The Reuleaux triangle (Eric-s Treasure Trove)
  5. Web: 8.2.3 - The Reuleaux triangle (Geometry Junkyard)

Week 14 April  7 and 9
Lecture 27: Nearest neighbors and parallel computation
  1. Sequential nearest neighbor search:
    1. Projection methods
    2. Voronoi diagram methods
  1. Parallel models of computation:
      1. Interconnection networks (MIMD machines: Multiple-Instruction Multiple Data)
        1. Sorting with an array of processors
        2. The odd-even transposition sort (parallel version of bubble-sort)
      2. SIMD machines (Single-Instruction Multiple-Data)
        1. Receptor cell networks and lateral inhibition
        2. McCullogh-Pitts neurons
        3. Threshold logic units
        4. Reinforcement learning algorithms in dual weight-space
        5. Solving systems of linear inequalities
Lecture 28: Map coloring
  1. Map coloring:
    1. 2-coloring the faces of an arrangement of lines
    2. 2-coloring the faces of a self-intersecting closed curve
    3. 3-coloring the vertices of an arrangement graph
    4. 3-coloring the vertices of a triangulated polygon
    5. Scheduling problems via graph coloring
    6. The chromatic number of a graph
    7. The four-color theore
    8. Euler's formula for planar graphs
    9. Proof that every planar graph has a vertex of degree at most 5
    10. Induction proof of the the 5-color theorem for planar graphs
      1. Algorithm for 5-coloring planar graphs in O(n^2) time

  2. Digraphs and tournaments:
    1. Round robin tournaments
    2. Proof that the winner in a round robin tournament loses games only to teams that lose to teams defeated by the winner
Reading Assignment
    1. Web: 6.7.1 - Projection methods for nearest neighbor search
    2. Text: 12.4, 12.4.1 - Parallel algorithms for interconnection networks: sorting on an arrray
    3. Web: 18.5 - Perceptrons and neural networks
    4. Web: 18.6 - Neural networks for lateral inhibition (computing Laplacians and image sharpening)


Additional Possible Material
  1. Digraphs and tournaments cont:
    1. Proof by induction that tournaments contain a Hamiltonian path
    2. O(n^2) algorithm for computing a Hamiltonian path in a tournament
  2. Travelling Salesperson Problem (TSP):
    1. Two versions of TSP (triangle inequality graphs)
    2. Reducing the TSP to a Hamiltonian circuit problem
    3. Approximation algorithms for TSP:
      1. The nearest-neighbor heuristic
      2. The twice-around-the-MST heuristic
  3. Minimum spanning trees:
    1. Kruskal's algorithm using heaps
    2. Prim's algorithm using adjacency matrices
    3. Baruvka's algorithm using adjacency lists
  4. Closest-pair searching:
    1. In 1-D via divide and conquer in O(n log n) time
    2. In 2-D via divide and conquer algorithm
      1. In O(n log^2 n) time
      2. In O(n log n) time
    3. In 2-D via line-sweep algorithm with (2,4) trees in O(n log n) time
  1. Coding theory and data compression:
    1. Block and Prefix codes
    2. Shannon-Fano codes
    3. Huffman coding
      1. Hu-Tucker algorithm with heaps
      2. Schwartz-Kallick algorithm
    4. Lempel-Ziv coding for data compression
  2. Other Huffman tree applications:
    1. Merging sorted files with a minimum number of comparisons
    2. Random number generation with a minimum number of comparisons
    Reading Assignment
    1. Text: 7.6 - Minimum-cost spanning trees
    2. Web: 4.11.1 - Minimum spanning trees (Luc Devroye's class notes)
    3. Web: 4.11.2 - Minimum spanning trees (David Eppstein's class notes)
    4. Web:4.11.3 - Kruskal's and Prim's algorithms tutorial
    5. Web: 4.10.1 - Hamiltonian paths in tournaments
    6. Web: 4.10.3.1 - Posa's proof of Dirac's theorem
    7. Handout: Travelling Salesperson Problem
    Suggested Play
    1. Web: 4.11.4.2 - Kruskal MST algorithm applet
    2. Web: 4.11.3 - AnotherKruskal MST algorithm applet
    3. Web: 4.11.6 - Prim MST algorithm applet
    4. Web: 4.17.3 and 4.17.4 - Great applets for travelling salesman problem

      5. Web: 4.17.6 - Great applet for TSP heuristics
    Reading Assignment
     
    1. Text: 8.5 - Closest pair
    2. Web: 6.8.1 - Closest-pair searching tutorial
    3. Web: 20.11.1 - Voronoi diagrams
    4. Text: 6.6 - Data compression
    5. Web: 5.7.1.6 - Huffman trees and applications (Luc Devroye's class notes)
    6. Web: 5.7.1.3 - Shannon-Fano coding
    7. Web: 5.7.1.4 - Huffman coding
    8. Web: 5.7.1.5 - Optimality of Huffman coding
    9. Web: 5.7.1.10 - Lempel-Ziv adaptive codes  (Luc Devroye's class notes)
    Suggested Play
    1. Web: 5.7.7 and 5.7.8 - Huffman coding applets