COMP-251A Data Structures and Algorithms - Fall 2008

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 - Sept 2 and 4

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 September 16

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 in general position contain an emty convex quadrilateral)
3. Geometric proof of  S(n) = 1+2+3+...+n = n(n+1)/2
4. Gauss proof of  S(n) = 1+2+3+...+n = n(n+1)/2
5. Introduction to induction proofs
1. Example 1: S(n) = 1+2+3+...+n = n(n+1)/2
2. Example 2: 2-coloring the faces of an arrangement of lines in the plane
3. Example 3: covering a 2^n by 2^n checkerboard with one square missing by L-shaped pieces.

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 - Sept 9 and 11

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. Proximity graphs
1. Minimal spanning trees (MST)
2. Relative neighbourhood graphs (RNG)
3. Proof (by contradiction) that for n points in the plane the MST is a subgraph of the RNG
4. Gabriel graphs
5. Delaunay triangulations and Voronoi diagrams

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 - Sept 16 and 18:

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" September 30)

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 - Sept 23 and 25

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

1. Hamiltonian cycles induced by point sets (polygonizations)
1. Proof that the shortest polygonalization must be simple
2. Star-shaped polygonizations in O(n log n) time
3. Monotone polygonizations  in O(n log n) time
2. The skyline problem (hidden line removal in computer graphics)
1. O(n^2) via sequential insertion
2. O(n log n) via divide & conquer

Lecture 8: 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
2. Merge sort

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

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 - Sept 30 and Oct 2 - Class Test #1 Thursday October 2

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

Problem Assignment 3 "due"  October 16

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 (Thursday October 2) 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 - Oct 7 and 9

Lecture 11:  Tree Traversals, Floor Functions, Maximum Gap, Lower bounds for sorting, and Bucket Sorting

1. Lower bounds on the complexity of problems
2. Decision trees and lower bound for sorting (comparison model)
3. Adversarial arguments (diameter problem)

Lecture 12:

1. Tree traversals:
1. The Euler-Tour traversal of a tree
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
2. Computing the maximum gap in O(n) time with floor functions
3. Probabilistic analysis of bucket-sort:
1. Proof that bucket-sort takes O(n) expected time
4. 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
5. 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- Oct 14 and 16

Lecture 13:

1. Master theorems for solving recurrence equations
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

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
3. Deleting keys from 2-4 trees
3. Searching for the diameter of a set

Problem Assignment 4 "due" October 30
 
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 - Oct 21 and 23

Lecture 15

1. Locus search methods
1. Range searching via domination queries
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. Dynamic programming
2. Divide and conquer with the master-theorem method
1. Merge sort
2. Convex hull and triangulation (merging with 3-coins algorithm or rotating calipers)
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

Suggested Play

Web: 21.1 - Applet for Dynamic programming (edit distance in sequence comparison)

Week 9 - Oct 28 and 30

Lecture 17

1. Point inclusion query searching
2. Nearest neighbor search:
1. Projection methods
3. In-place quicksort
4. Randomized quicksort
1. Expected complexity of quicksort
5. 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

Problem Assignment #5 "due" November 18

1. Algorithms on sequences
2. Edit distance between strings
3. Graph embeddability

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 - Nov 4 and 6

Lecture 19: 2nd In-Class test (November 4)

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 - Nov 11 and 13

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" November 27)

1. Greedy algorithms and least-cost Hamiltonian cycles in graphs
2. Hamiltonian cycles in dense graphs (Ore's theorem)
3. Parallel computation models

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)

1. Web: 4.2 - Adjacency matrix and list applet
2. Web: 6.3.3 - 3D Maze Applet

Week 12 - Nov 18 and 20

Lecture 23:

1. Computational Aspects of Music:
1. Necklaces and Bracelets,
2. Homometric Rhythms,
3. The Hexachordal Theorem,
4. Patterson's Theorems,
5. Flat Rhythms
6. Deep Rhythms and Scales

Lecture 24

1. Graphs:
1. Terminology
2. Isomorphic versus isotopic graphs
2. Eulerian circuits:
1. Eulerian tours and the Konigsberg bridge problem
2. The Euler-Hierholzer Theorem
1. Fleury's algorithm for computing Euler trails
3. Eulerian graphs need not be Hamiltonian
4. Hamiltonian graphs need not be Eulerian
3. 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: 22.1 - Computational Aspects of Musical Rhythm
3. Web: 4.3 - Graph isomorphism
4. Web: 4.4 - Graph planarity
5. Web: 4.14 - The Bridges of Konigsberg Problem
6. Web: 4.7.2 - Euler circuits
7. Web: 4.7.5 - Paths and circuits
8. Web: 4.7.6 - Algorithm for constructing an Eulerian circuit

Suggested Play

1. Web: 4.7.7.1 - Euler traversal applet

Week 13 - Nov 25 and 27

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

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