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

Lecture 1: Ancient Models of Computation

1. Introduce course
2. The collapsing compass computer
1. Euclid's second proposition through the ages
2. Constructive (direct) proofs

Problem Assignment #1 - Solutions posted September 19

1. Induction proof (triangles in arrangements of lines)
2. Induction proof (sum of squares of numbers)
3. Induction proof (circle map coloring)
4. The collapsing compass computer (translate a segment)

Lecture 2: Induction Proofs

1. Euclid's second proposition cont.
1. Case analysis in proofs
2. Introduction to induction proofs
1. Example 2: 2-coloring the faces of an arrangement of lines in the plane
2. Example 1: 3-coloring the vertices of a triangulated polygon

Reading Assignment

1. Text: Chapter 1 and Sections 2.1, 2.1 and 2.3.
2. Web: 1.2.10.2 - A New Look at Euclid's Second Proposition (Handout)
3. Web: 2.1 - Notes on methods of proof
4. Web: 2.2 - Notes on how to do proofs

Suggested Play

1. Web: 1.1.3 - Pythagoras proof applets
2. Web: 1.2.1 - Straight-edge-and-compass constructions applet of Francois Labelle
3. Web: 1.2.7.1 - Euclid's second proposition applet
4. Web: 1.1.3.1 - Pythagoras' theorem applet
5. Web: 1.2.3 - The straight edge and compass
6. Web: 2.3 - Classical fallatious proofs

Week 2-Sept 12 and 14

Lecture 3: More on Proofs

1. If and only if
2. Proofs by contradiction
1. The infinitude of primes
3. Existence proofs
1. Coloring the points of the plane with two colors
4. Strong induction: triangulating polygons via diagonal insertion
5. Graph theory terminology
6. Double induction
1. Proof of Euler's formula for connected planr graphs

Lecture 4: Proximity Graphs

1. Abstract graphs and geometric graphs
2. Proximity graphs
1. Trees
2. Minimal spanning trees
3. Relative neighborhood graphs
3. Applications of MST to text-line orientation estimation

Reading Assignment

1. Text: 2.4-2.7, 2.11, 2.13-2.14
2. Web: 4.1 - Interactive introduction to graph theory
3. Web: 4.2 - Introduction to graph theory (Luc Devroye's notes)
4. Web: 4.4 - Web Tutorials: Introduction to Graph Theory

Suggested Play

1. Web: 20.3 - Minimal spanning tree applet
2. Web: 4.12 - Euler's theorem
3. Web: 20.2 - Art Gallery Theorem (applet)

Week 3-Sept 19 and 21

Lecture 5: Turing Machines and Random Access Machines

1. Digital models of computation
1. Turing machines
2. Random access machines
3. Ceiling and floor functions
2. Big "Oh" notation
1. Comparing functions
2. L'Hospital's rule
3. Little "oh" notation
3. Running time of an algorithm
1. Worst case
2. Average case
3. Best case

Problem Assignment #2 ("due" September 28)

1. Turing Machines
2. Growth of functions
3. Big "Oh" notation
4. Minimal spanning trees of points

Lecture 6: Complexity Classes and Examples

1. Running time: constant, logarithmic, linear, n log n, quadratic, cubic, polynomial, exponential, factorial
2. 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
4. Polygon triangulation in cubic time

Reading Assignment

1. Web: 1.3.1, 1.3.2, 1.4.1, 1.4.1.1- Turing Machines, RAM's, Complexity and Recursion
2. Text: 3.1, 3.2 - Big "Oh" notation
3. Web: 20.1.2.3 - Two-ears theorem, diagonals and polygon triangulation

Suggested Play

1. Web: 1.3.1.1 - Turing machine applet
2. Web: 4.17.3 - Elastic band approach to TSP applet
3. Web: 4.17.4 - Simple polygon counter applet

Week 4-Sept 26 and 28

Lecture 7: Recurrence Relations

1. Recurrence Relations and Fibonacci sequences
2. Algorithms for computing the Fibonacci function
1. Exponential - O(2^n)
2. Linear - O(n)
3. Logarithmic - O(log n)
3. Polygon triangulation in quadratic time
1. Geoff's algorithm

1. Solving the Fibonacci recurrence relation by induction
1. Approximately
2. Exactly (Binet's formula)
2. Divide & conquer recurrence relations
1. Merge sort
2. The master theorem

Reading Assignment

1. Text: Chapter 3
2. Text: 6.4.3 - Merge sort
3. Web: 1.4.1 - Recursion (Luc Devroye's class notes)
4. Web: 1.4.1.1 - Fibonacci algorithms
5. Web: 1.4.1.9 - Proofs of Binet's formula

Suggested Play

1. Web: 1.4.1.2 - Fibonacci math
2. Web: 1.4.1.3 - Fibonacci and nature
3. Web: 1.4.1.4 - Fibonacci home page

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

Lecture 11:

1. Probabilistic analysis of bucket-sort:
1. Proof that bucket-sort takes O(n) expected time
2. Tree traversals:
1. The Euler-Tour traversal of a tree
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
3. Binary search trees:
1. Inserting and deleting items from BST's

Lecture 12:

1. Complexity of updating binary search trees
2. Balanced multi-way search trees:
1. 2-4 trees
2. Inserting items in 2-4 trees
3. Deleting items from 2-4 trees
3. Searching data bases:
1. Two-dimensional range search via the locus method

Reading Assignment

1. Text: 4.1, 4.2, 4.3.1, 4.3.3
2. Web: 5.1.1 - Introduction to trees (Luc Devroye's class notes)
3. Web: 5.1.2 - Tree traversals (preorder, inorder and postorder)
4. Web: 5.3.3 - Binary search trees (Luc Devroye's class notes)
5. Web: 5.5.1 - (2,3,4)-tree tutorial with applet

Suggested Play

1. Web: 5.3.3 - Binary search tree applet (Luc Devroye's class notes)
2. Web: 5.1 - Tree traversal applet (Luc Devroye's class notes)

Week 7- Oct 17 and 19

Lecture 13

1. Priority queues via the heap data structure
1. Insertion and deletion in heaps in O(log n) time
2. Building a heap in O(n) time
3. Application to sorting (heapsort)

Lecture 14

1. Non-crossing Hamiltonians of point sets
1. Convex hull algorithm of Rosenberg & Landgridge - O(n^3)
2. Monotone simple Hamiltonian circuits in O(n log n) time - The double-comb algorithm
3. Star-shaped Hamiltonian circuits in O(n log n) time

Problem Assignment 4 "due" November 2, 2000

1. Balanced search trees
2. Element uniqueness
3. Non-collinearity of points
4. Maximal points of a set

Reading Assignment

1. Text: 4.3.2 - Heaps
2. Web: 5.6.2 - Heaps (Luc Devroye's class notes)
3. Web: 5.6 - Tutorial on heaps
4. Web: 19.2.1.4 - Heapsort tutorial
5. Text: 6.4.5 - Heapsorting

Suggested Play

1. Web: 5.6 - Heap applet

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

Lecture 17

1. Data compression:
1. Prefix codes
2. Minimal prefix codes
3. Shannon-Fano coding
4. Huffman coding
1. Hu-Tucker algorithm with heaps
2. Schwartz-Kallick algorithm
2. Huffman trees:
1. Applications
1. Merging sorted files
2. Random number generation

Lecture 18

1. 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 algorithms
1. O(n log^2 n)
2. O(n log n)

Problem Assignment #5 "due" November 16

1. The closest pair problem
2. Graph embeddability
3. Vertex degrees in planar graphs

Reading Assignment

1. Text: 6.6 - Data compression
2. Web: 5.7.6 - Huffman trees (Luc Devroye's class notes)
3. Web: 7.1.3 - Shannon-Fano coding
4. Web: 7.1.4 - Huffman coding
5. Text: 8.5 - Closest pair searching
6. Web: 6.8.1 - Closest-pair searching tutorial

Suggested Play

1. Web: 5.7.7 and 5.7.8 - Huffman coding applets
2. Web: 6.8.1 - Closest-pair applet

Week 10 - Nov 7 and 9

Lecture 19: 2nd Class test (November 7)

Lecture 20

1. Orthogonal Hamiltonians
1. Reconstructing simple polygons from their vertex set
2. Testing self-intersections in polygons
3. Computing orthogonal-segment intersections via line-sweep technique and balanced search trees
2. Closest-pair searching:
1. Line-sweep algorithm with (2,4) trees in O(n log n) time

Reading Assignment

1. Text: 8.6 - Orthogonal segment intersections
2. Web: 6.7.1 - Projection methods for nearest neighbor search
3. Web: 4.2 - Introduction to graphs (Luc Devroye's class notes)

Suggested Play

1. Web: 6.7.1 - Nearest neighbor search applet

Week 11 - Nov 14 and 16

Lecture 21: Guest lecturer - Tom Fevens

1. Basic definitions of graphs
2. Data structures for graphs
1. Adjacency matrix
2. Adjacency lists
3. Searching mazes and labyrinths
1. Ancient Greek algorithm (Ariadne's thread)
2. Gaston Tarry's algorithm (1895)
4. Depth-first search in a graph
5. Breadth-first search in a graph
6. Complexity analysis of DFS and BFS

Lecture 22: Guest lecturer - Felix Kwok

1. Map and graph coloring:
1. Planarity
1. Proof of non-planarity of K5 using Euler's formula
2. Dual graphs
3. The four-color theorem and its history
4. Induction proof of 5-color theorem
1. Algorithm for coloring a plane graph

Problem Assignment #6 ("due" November 30)

1. Greedy algorithms and least-cost Hamiltonian cycles in graphs
2. Hamiltonian cycles in dense graphs (Ore's theorem)
3. Prim's minimum spanning tree for graphs

Reading Assignment

1. Text: 4.6 - Adjacency matrix
2. Web: 6.3.1 - Depth-first search (Luc Devroye's class notes)
3. Web: 6.4 - Breadth-first search (Luc Devroye's class notes)
4. Text: 7.3 - Depth-first search and breadth-first search
5. Web: 4.16 - Rotating caliper graph
6. Text: 8.6 - Intersections of horizontal and vertical segments
7. Web: 4.13.1 to 4.13.5 - Map coloring

1. Web: 4.2 - Adjacency matrix and list applet
2. Web: 6.1.1 - A Maze Game
3. Web: 6.1.2 - 3D Maze Applet
4. Web: 6.3.1.1 - Depth-first search applet
5. Web: 6.4.1 - Breadth-first search applet

Week 12 - Nov 21 and 23

Lecture 23

1. Two-colorability
1. Closed-Jordan-curve maps
2. The scheduling problem as graph coloring
1. Chromatic number of a graph
3. Graph isomorphism
4. Eulerian tours and the Konigsberg bridge problem
5. The Euler-Hierholzer Theorem

Lecture 24 Course Evaluations

1. Digraphs and tournaments
1. Round robin tournaments
2. Proof that tournaments are path-Hamiltonian
3. Proof that the distance btween the maximum-degree vertex and all others is at most two
2. Dense graphs
1. Proof of Ore's theorem on cycle-Hamiltonicity of dense graphs

Reading Assignment

1. Web: 4.3 - Graph isomorphism
2. Web: 4.4 - Graph planarity
3. Web: 4.14 - The Bridges of Konigsberg Problem
4. Web: 4.7.2 - Euler circuits
5. Text: 7.2 - Eulerian graphs
6. Text: 7.12 - Hamiltonian tours
7. Web: 4.10.1 - Hamiltonian paths in tournaments

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