CS-251A Data Structures and Algorithms

Lecture Descriptions, Homework and Play

Text Book: Data Structures and Algorithms in JAVA by Michael Goodrich and Roberto Tamassia

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

Week 1-Sept 2

Week 2-Sept 7 and 9

Lecture #3: More on Methods of Proof

Week 3-Sept 14 and 16

Week 4-Sept 21 and 23

Week 5-Sept 28 and 30

    Lecture #8:
    1. Algorithms for computing the Fibonacci function
      1. Exponential - O(2^n)
      2. Linear - O(n)
      3. Logarithmic - O(log n)
    2. More induction
      1. Triangulating sets of points
      2. Two-ears theorem
    Lecture #9: QUIZ #2, homework #2 due, homework #3 out (due Oct 14)
    1. Binary search
    2. A master theorem of recursion
    3. Divide and conquer
    4. Sorting
      1. Insertion sort
      2. Selection sort
      3. Bubble sort
      4. Divide and conquer (merge sort)
      5. Bucket sort with floor functions
    Problem Assignment #3
    1. Turing machines
    2. Matrix powering and the Fibonacci function
    3. The skyline problem (Divide and Conquer)
    4. Graphs (properties of vertices of odd degree)
    Reading Assignment
    1. Text: 9.2 - Exponentiation
    2. Text: 5.6 - The skyline problem (divide and conquer)
    3. Text: Chapter 6 up to and including 6.4.3
    4. Web: 1.4.1.1 - Fibonacci algorithms (David Eppstein)
    5. Web: 20.1.2.3 - Two-Ears theorem (Ian Garton)
    6. 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 5 and 7

Week 7 - Oct 12 and 14

Week 8 - Oct 19 and 21

Week 9 - Oct 26 and 28

Week 10 - Nov 2 and 4

Week 11 - Nov 9 and 11

Week 12 - Nov 16 and 18

Week 13 - Nov 23 and 25

    Lecture #24:
      1. Priority queues via the heap data structure
        1. application to sorting (heapsort)
        2. application to minimum spanning trees (Kruskal's algorithm)
      2. More convex hulls
        1. Throw-away principle - O(n) expected time (Quickhull)
    Lecture #24: Course Evaluations
    1. Prune-and-search methods revisited:
      1. Quicksort
      2. Randomized quicksort
      3. Selection
        1. Via sorting
        2. Via heaps
        3. Randomized selection
        4. Finding the median of a set of numbers in linear time
    Reading Assignment
    1. Text: 4.3.2 - Heaps
    2. Web: 5.6 - Tutorial on heaps
    3. Web: 19.2.1.4 - Heapsort tutorial
    4. Web: 19.2.2 - Selection and order statistics
    5. Web: 14.3 - Linear time selection (Luc Devroye's course notes)
    6. Web: 14.4 - Linear time selection (David Eppstein's course notes)
    Suggested Play
    1. Web: 5.6 - Heap applet

Week 14 - Nov 30 and Dec 2