CS-251A/B Data Structures and Algorithms - Fall 2008, Winter 2009

Lecture Descriptions, Homework, and Play

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 4 and 9

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
3. Case analyses in proofs

Problem Assignment #1 - Solutions posted January 18

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: Proofs
 
1. The knotted string computer
2. More on case analysis in proofs:
1. Example from Ramsey Theory (5 points contain a convex quadrilateral)
3. Introduction to induction proofs
1. Example 1: n(n+1)/2
2. Example 2: 2-coloring the faces of an arrangement of lines in the plane

Reading Assignment

1. Text: Chapter 1 and Sections 2.1 - 2.4.
2. Web: 1.2.10.2 - A New Look at Euclid's Second Proposition
3. Web: 2.1 - Notes on methods of proof

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.4 - Classical fallatious proofs

Week 2 - Jan 11 and 16

Lecture 3: More on Proofs
 
1. Some beautiful induction proofs:
1. Example 3: 3-coloring the vertices of a triangulated polygon
2. The two-Ears Theorem
2. Proofs by contradiction
1. The diagonal of the unit square is irrational
2. There are an infinite number of prime numbers
3. Existence proofs
1. Coloring the points of the plane with two colors
4. Strong induction: triangulating polygons via diagonal insertion

Lecture 4: Proximity Graphs

1. Graph theory terminology
2. Abstract graphs and geometric graphs
3. Proximity graphs
1. Minimal spanning trees (MST)
2. Proof (by contradiction) that for n points in the plane the closest pair determines an edge in the MST
3. Relative neighbourhood graphs
4. Sphere-of-influence graphs

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 251 course notes)
4. Web: 4.7.1 - Web Tutorials: Introduction to Graph Theory
5. Web: 4.9.2 - The relative neighborhood graph

Suggested Play

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

Week 3 - Jan 18 and 23

Lecture 5: Polygon Triangulation Algorithms

1. Double induction
1. Proof of Euler's formula for connected planar graphs
2. Area of a triangle (simple polygon)
3. Point inclusion testing
4. Polygon triangulation
1. O(n^3) time via ear-cutting

Lecture 6: Turing Machines and Random Access Machines
 
1. Digital models of computation
1. Turing machines
2. Random access machines
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" February 1)

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

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.4 - 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 - Jan 25 and 30

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. Induction proof of Binet's formula
4. Solving recurrence relations by induction
1. Divide & conquer recurrence relations
1. Merge sort

Lecture 8: Hamiltonian cycles of point sets, and rulers with few mark

1. Straight and circular rulers with few marks
2. Hamiltonian cycles induced by point sets (polygonizations)
1. Star-shaped polygonizations in O(n log n) time
2. Monotone polygonizations  in O(n log n) time
3. The skyline problem (hidden line removal in computer graphics)
1. O(n^2) via sequential insertion

O(n log n) via divide & conquer

Reading Assignment

1. Text: Chapter 3
2. Text: 6.4.3 - Merge sort
3. Text: 8.1, 8.2 - Point inclusion testing
4. Web: 1.4.1 - Recursion (Luc Devroye's class notes)
5. Web: 1.4.1.1 - Fibonacci algorithms
6. Web: 1.4.1.9 - Proofs of Binet's formula
7. Web: 4.10.7 - Polygonization of point sets


Reading Assignment for 252

1. Rulers with few marks

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
4. Web: 4.10.7 - Applet for polygonization of point sets

Week 5 - Feb 1 and 6 - Class Test #1 Tuesday Feb 6

Lecture 9: Complexity Classes and Examples
1. Running time: constant, logarithmic, linear, n log n, quadratic, cubic, polynomial, exponential, factorial
2. Proof that the exponential function grows faster than the polynomial function
3. 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 15

1. Algorithms for computing the Fibonacci function
2. Binary search
3. The skyline problem in computer graphics
4. Analysis of heap-sorting

Lecture 10: 1st Class Test (Feb 6) Example test (2003)

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
5. Web: 20.6 - Polygonizing sets of points
6. Text: 8.3 - Star-shaped polygonization of point sets

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 8 and 13

Lecture 11:  Guest Lecturer - Pedro De Rezende - Tree Traversals, Floor Functions, Maximum Gap, Lower bounds for sorting, and Bucket Sorting

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

Lecture 12:

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: 8.4 - Convex hulls
2. Web: 20.10.1, 20.10.4, 20.10.8 - Convex hull algorithms
3. Web: 20.10.9 - 3-coins algorithm
4. Web: 19.2.1.6 - Bucket sorting with floor functions
5. Text: 4.1, 4.2, 4.3.1, 4.3.3, 6.4.1, 6.4.4
6. Web: 5.1.1 - Introduction to trees (Luc Devroye's class notes)
7. Web: 5.1.2 - Tree traversals (preorder, inorder and postorder)
8. Web: 5.3.3 - Binary search trees (Luc Devroye's class notes)

Suggested Play

1. Web: 20.10 - Convex hull applets
2. Web: 20.6 - Polygonization applet (Hamiltonian non-crossing circuits of points)
3. Web: 5.3.3 - Binary search tree applet (Luc Devroye's class notes)
4. Web: 5.1 - Tree traversal applet (Luc Devroye's class notes)

Week 7- Feb 15 and 27 (Feb 20 and 22 no class due to study break)

Lecture 13:

1. Lower bounds via reduction continued:
1. Example with non-crossing Hamiltonian circuit of a point set
2. 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
3. Illumination problems in computer graphics
1. Illuminating the edges of a polygon versus its interior

Lecture 14

1. Searching:
1. Fast point location queries in convex polygons
2. Range searching
3. Geometric Search with the locus method
2. Balanced multi-way search trees:
1. (2-4)-trees
2. Inserting keys in 2-4 trees

Problem Assignment 4 "due" March 1
 
1. Balanced search trees
2. Element uniqueness
3. Non-collinearity of points
4. Maximal points of a set

Reading Assignment

1. Handout: Geometric Search using the locus method
2. Web: 5.5.1 - (2-4)-tree tutorial with applet
3. Text: 6.4.6 - Lower bound for sorting
4. Text: 10.1, 10.4.1, 10.5 - Lower bound reductions
5. Web: 1.4.2 - Lower bounds (Luc Devroye's class notes)

Suggested Play

1. Web: 1.4.2 - MasterMind applet (decision trees)
2. Web: 5.5.1 - (2-4)-tree applet

Week 8 - March 1 and 6

Lecture 15

1. (2-4)-trees continued:
1. Deleting keys from 2-4 trees
2. 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 8 and 13

Lecture 17

1. In-place quicksort
2. Randomized quicksort
1. Expected complexity of quicksort
3. Edit-distance between sequences
1. Dynamic programming approach

Lecture 18:

1. Line sweep methods
1. 3-coloring the vertices of an arrangement of lines
2. Range searching with balanced search trees
3. 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
4. Nearest neighbor search:
1. Projection methods

Problem Assignment #5 "due" March 15

1. Algorithms on sequences
2. Edit distance between strings
3. Graph embeddability
4. Quicksort (for 252 students only)

Reading Assignment

1. Text: 8.6 - Orthogonal segment intersections
2. Web: 6.7.1 - Projection methods for nearest neighbor search

Suggested Play

1. Web: 5.6 - Heap applet
2. Web: 6.8.1 - Closest-pair applet
3. Web: 6.7.1 - Nearest neighbor search applet

Week 10 - March 15 and 20

Lecture 19: 2nd In-Class test (March 15)

Lecture 20
 
1. Hamiltonian cycles in dense graphs:
1. Proof of Ore's theorem on cycle-Hamiltonicity of dense graphs via backwards induction
2. Implementing the backwards induction proof  into an O(n^2) algorithm
2. Priority queues via the heap data structure:
1. Insertion and deletion in heaps in O(log n) time
2. Building heaps:
1. In O(n log n) time via top-down insertion
2. In O(n) time via bottom-up divide & conquer
3. Proof of linearity via geometric series
4. Updating the pointer to LAST in heaps after insertions and deletions
3. Application of heaps to sorting (heapsort) in O( n log n) time

Reading Assignment

1. Text: 7.12 - Hamiltonian tours
2. Web: 5.6.2 - Heaps (Luc Devroye's class notes)
3. Web: 5.6 - Tutorial on heaps
4. Text: 4.3.2 - Heaps
5. Web: 19.2.1.4 - Heapsort tutorial
6. Text: 6.4.5 - Heapsorting
7. Web: 4.2 - Introduction to graphs (Luc Devroye's class notes)

Week 11 - March 22 and 27

Lecture 21:

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. McCullogh-Pitts neurons
2. Threshold logic units
3. Solving systems of linear inequalities

Lecture 22:

1. Parallel models of computation cont.
1. Perceptrons and Neural networks
1. SIMD machines (Single-Instruction Multiple-Data)
1. Laplacian operators
2. Latteral inhibition networks
2. Machine learning algorithms
2. Nearest neighbor search in O(1) time with neural networks
2. Searching Graphs:
1. Depth-first search in a graph with a stack
2. Breadth-first search with a queue
1. Data structures for graphs
1. Adjacency matrices
2. Adjacency lists
2. Complexity analysis of DFS and BFS

Problem Assignment #6 ("due" April 5)

1. Greedy algorithms and least-cost Hamiltonian cycles in graphs
2. Hamiltonian cycles in dense graphs (Ore's theorem)
3. Sorting with a parallel array of processors
4. Prim's minimum spanning tree for graphs

Reading Assignment

1. Text: 12.4, 12.4.1 - Parallel algorithms for interconnection networks: sorting on an arrray
2. Web: 18.2 - Real and artificial neurons
3. Web: 18.3 - Threshold logic units
4. Web: 18.5 - Perceptrons and neural networks
5. Web: 18.6 - Neural networks for lateral inhibition (computing Laplacians and image sharpening)
6. Text: 4.6 - Adjacency matrix
7. Web: 6.3.1 - Depth-first search (Luc Devroye's class notes)
8. Web: 6.4 - Breadth-first search (Luc Devroye's class notes)
9. Text: 7.1 - 7.3 - Depth-first search and breadth-first search

1. Web: 4.2 - Adjacency matrix and list applet
2. Web: 6.3.3 - 3D Maze Applet
3. Web: 6.3.1.1 - Depth-first search applet
4. Web: 6.4.1 - Breadth-first search applet

Week 12 - March 29 and April 3

Lecture 23:

1. Graphs:
1. Terminology
2. Isomorphic versus isotopic graphs
2. Eulerian circuits:
1. Eulerian tours and the Konigsberg bridge problem

Lecture 24

1. Eulerian circuits:
1. The Euler-Hierholzer Theorem
1. Fleury's algorithm for computing Euler trails
2. Eulerian graphs need not be Hamiltonian
3. Hamiltonian graphs need not be Eulerian
2. 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 theorem

Reading Assignment

1. Text: 7.2 - Eulerian graphs
2. Web: 4.3 - Graph isomorphism
3. Web: 4.4 - Graph planarity
4. Web: 4.14 - The Bridges of Konigsberg Problem
5. Web: 4.7.2 - Euler circuits
6. Web: 4.7.5 - Paths and circuits
7. Web: 4.7.6 - Algorithm for constructing an Eulerian circuit

Suggested Play

1. Web: 4.7.7.1 - Euler traversal applet

Week 13 - April 5 and 10

Lecture 25

1. Map coloring:
1. Euler's formula for planar graphs
2. Proof that every planar graph has a vertex of degree at most 5
3. 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


Lecture 26 (not covered in final exam)

1. Hommometric sets:
1. Proofs of the hexachordal theorem

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

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