CS-251A Data Structures and Algorithms - Fall 2000

Lecture Descriptions, Exams, 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-14

Week 1-Sept 5 and 7

Week 2-Sept 12 and 14

Week 3-Sept 19 and 21

Week 4-Sept 26 and 28

Lecture 8: Solving Recurrence Relations

Week 5-Oct 3 and 5

    Lecture 9: 1st Class Test (October 3)
    Problem Assignment 3 "due" October 19
    1. Algorithms for computing the Fibonacci function
    2. Binary search
    3. The skyline problem in computer graphics
    4. Analysis of heap-sorting
    Lecture 10: Floor Functions, Maximum Gap and Bucket Sorting
    1. Computing the maximum gap in O(n) time with floor functions
    2. Bucketsort and radix sort
    3. Bucket sorting real numbers in O(n) expected time
    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 up to and including 6.4.3
    5. Web: 19.2.1.6 - Bucket sorting with floor functions
    Suggested Play
    1. Web: 1.4.1.6 - Fibonacci numbers and domino tilings
    2. Web: - 19.2.1.1 - Sorting animation applets

Week 6 - October 10 and 12

Week 7- Oct 17 and 19

Week 8 - Oct 24 & 26

    Lecture 15
    1. Lower bounds:
      1. Lower bounds on the complexity of problems (comparison model of computation)
      2. Decision trees:
        1. Algebraic decision trees
        2. Linear decision trees
        3. Comparison trees
      3. Optimality of O(n log n) sorting algorithms (heapsort, mergesort)
      4. Lower bounds by reduction
        1. Example with non-crossing Hamiltonian circuit of a point set
        2. Example with convex hull problem
    2. More convex hull algorithms:
      1. Jarvis' adaptive algorithm
      2. Divide and conquer
    Lecture 16
    1. More convex hull algorithms:
      1. 3-coins algorithm for polygons
        1. Star-shaped polygons
        2. Monotone polygons
      2. Grahams's algorithm - O(n log n)
      3. Divide and conquer with presorting - O(n log n)
      4. Beneath-beyond method (sequential insertion method)
    Reading Assignment
    1. Text: 6.4.6 - Lower bound for sorting
    2. Text: 10.1, 10.4.1, 10.5 - Lower bound reductions
    3. Web: 1.4.2 - Lower bounds (Luc Devroye's class notes)
    4. Text: 8.1, 8.2, 8.3, 8.4 - Convex hull algorithms
    5. Web: 20.10 - Convex hull algorithms
    Suggested Play
    1. Web: 20.6 - Polygonization applet
    2. Web: 20.10 - Convex hull applets
    3. Web: 1.4.2 - MasterMind applet (decision trees)

Week 9 - Oct 31 and Nov 2

Week 10 - Nov 7 and 9

Week 11 - Nov 14 and 16

Suggested Play

Week 12 - Nov 21 and 23

Week 13 - Nov 28 and 30

    Lecture 25
    1. Hill climbing algorithms
    2. Greedy algorithms
    3. Minimum spanning trees (MST)
      1. Kruskal's algorithm via heaps
      2. Prim's algorithm
      3. Baruvka's algorithm
    Lecture 26
    1. Travelling salesman problem
      1. Nearest neighbor heuristic yields O(log n) times optimal
      2. Approximation algorithm via MST yields twice optimal
    2. Selection:
      1. Via sorting
      2. Via heaps
      3. Finding the median of a set of numbers in linear time
        1. The median of medians algorithm
    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.17.1 and 4.17.2 - Travelling saleman problem
    6. Web: 4.17.7 - Twice-optimal approximate TSP algorithm
    7. Web: 19.2.2 - Selection and order statistics
    8. Web: 14.3 - Linear time selection (Luc Devroye's course notes)
    9. Web: 14.4 - Linear time selection (David Eppstein's course notes)
    Suggested Play
    1. Web: 4.11.3 - Kruskal algorithm applet
    2. Web: 4.17.3 and 4.17.4 - Great applets for travelling salesman problem
    3. Web: 4.17.6 - Great applet for TSP heuristics
    4. Web: 5.6 - Selection applet

Week 14 - December 5

    Lecture 27: No lecture due to Study Day