COMP251A Data Structures and Algorithms 
Fall 2008
Lecture Descriptions, 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
"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 2: Proofs

The knotted string computer

More on case analysis in proofs:

Example from Ramsey Theory (5 points in general position contain an emty
convex quadrilateral)

Geometric proof of S(n) = 1+2+3+...+n = n(n+1)/2

Gauss proof of S(n) = 1+2+3+...+n = n(n+1)/2

Introduction to induction proofs

Example 1: S(n) = 1+2+3+...+n = n(n+1)/2

Example 2: 2coloring the faces of an arrangement of lines in the
plane

Example 3: covering a 2^n by 2^n checkerboard with one square missing by
Lshaped pieces.
Reading Assignment

Text: Chapter 1 and Sections 2.1  2.4.

Web: 1.2.10.2  A New Look at Euclid's Second Proposition

Web: 2.1  Notes on methods of proof
Suggested Play

Web: 1.1.3  Pythagoras proof applets

Web: 1.2.1  Straightedgeandcompass constructions applet of Francois
Labelle

Web: 1.2.7.1  Euclid's second proposition applet

Web: 1.1.3.1  Pythagoras' theorem applet

Web: 1.2.3  The straight edge and compass

Web: 2.4  Classical fallatious proofs
Week 2  Sept 9 and
11
Lecture 3: More on Proofs

Some beautiful induction proofs:

Example 3: 3coloring the vertices of a triangulated polygon

The twoEars Theorem

Proofs by contradiction

The diagonal of the unit square is irrational

There are an infinite number of prime numbers

Existence proofs

Coloring the points of the plane with two colors

Strong induction: triangulating polygons via diagonal insertion
Lecture 4: Proximity Graphs

Proximity graphs

Minimal spanning trees (MST)

Relative neighbourhood graphs (RNG)

Proof (by contradiction) that for n points in the plane the MST
is a subgraph of the RNG

Gabriel graphs

Delaunay triangulations and Voronoi diagrams
Reading Assignment

Text: 2.42.7, 2.11, 2.132.14

Web: 4.1  Interactive introduction to graph theory

Web: 4.2  Introduction to graph theory (Luc Devroye's 251 course notes)

Web: 4.7.1  Web Tutorials: Introduction to Graph Theory

Web: 4.9.2  The relative neighborhood graph
Suggested Play

Web: 20.3  Minimal spanning tree applet

Web: 4.12  17 proofs of Euler's formula

Web: 20.2  Art Gallery Theorem (applet)
Week 3  Sept 16 and
18:
Lecture 5: Polygon Triangulation Algorithms

Double induction

Proof of Euler's formula for connected planar graphs

Area of a triangle (simple polygon)

Point inclusion testing

Polygon triangulation

O(n^3) time via earcutting
Lecture 6: Turing Machines and
Random Access Machines

Digital models of computation

Turing machines

Random access machines

Big "Oh" notation

Comparing functions

L'Hospital's rule

Little "oh" notation

Running time of an algorithm

Worst case

Average case

Best case
Problem Assignment #2 ("due" September 30)

Turing Machines

Growth of functions

Big "Oh" notation

Minimal spanning trees of
points
Reading Assignment

Web: 1.3.1, 1.3.2, 1.4.1, 1.4.1.1 Turing Machines, RAM's, Complexity and
Recursion

Text: 3.1  3.4  Big "Oh" notation

Web: 20.1.2.3  Twoears theorem, diagonals and polygon triangulation
Suggested Play

Web: 1.3.1.1  Turing machine applet

Web: 4.17.3  Elastic band approach to TSP applet

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

Hamiltonian cycles induced by point sets (polygonizations)

Proof that the shortest polygonalization must be simple

Starshaped polygonizations in O(n log n) time

Monotone polygonizations in O(n log n) time

The skyline problem (hidden line removal in computer graphics)

O(n^2) via sequential insertion

O(n log n) via divide & conquer
Lecture 8: Recurrence Relations

Recurrence Relations and Fibonacci sequences

Algorithms for computing the Fibonacci function

Exponential  O(2^n)

Linear  O(n)

Logarithmic  O(log n)

Induction proof of Binet's formula

Solving recurrence relations by induction

Divide & conquer recurrence relations

Merge sort
Reading Assignment

Text: Chapter 3

Text: 6.4.3  Merge sort

Text: 8.1, 8.2  Point inclusion testing

Web: 1.4.1  Recursion (Luc Devroye's class notes)

Web: 1.4.1.1  Fibonacci algorithms

Web: 1.4.1.9  Proofs of Binet's formula

Web: 4.10.7  Polygonization of point sets
Suggested Play

Web: 1.4.1.2  Fibonacci math

Web: 1.4.1.3  Fibonacci and nature

Web: 1.4.1.4  Fibonacci home page

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

Running time: constant, logarithmic, linear, n log n, quadratic, cubic,
polynomial, exponential, factorial

Proof that the exponential function grows faster than the polynomial function

Examples

Binary search

Sorting: insertion sort, selection sort, bubble sort, merge sort

Travelling salesman problem
Problem Assignment 3 "due" October 16

Algorithms
for computing the Fibonacci function

Binary
search

The
skyline problem in computer graphics

Analysis
of heapsorting
Lecture 10:
1st Class Test (Thursday October 2) Example test (2003)
Reading Assignment

Text: 5.1 and 5.2  Polynomial evaluation

Text: 9.2  Exponentiation

Text: 5.6  The skyline problem (divide and conquer)

Text: Chapter 6, section 6.4 up to and including 6.4.3

Web: 20.6  Polygonizing sets of points

Text: 8.3  Starshaped polygonization of point sets
Suggested Play

Web: 1.4.1.6  Fibonacci numbers and domino tilings

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

Lower bounds on the complexity of problems

Decision trees and lower bound for sorting (comparison model)

Adversarial arguments (diameter problem)
Lecture 12:

Tree traversals:

The EulerTour traversal of a tree

Preorder traversal

Inorder traversal

Postorder traversal

Computing the maximum gap in O(n) time with floor functions

Probabilistic analysis of bucketsort:

Proof that bucketsort takes O(n) expected time

Convex hull algorithms for planar point sets:

Rosenberg and Landgridge algorithm in O(n^3) time

Jarvis algorithm in O(n^2) time

Graham's algorithm in O(n log n) time

Lower bounds via reduction:

Example with convex hull problem
Reading Assignment

Text: 8.4  Convex hulls

Web: 20.10.1, 20.10.4, 20.10.8  Convex hull algorithms

Web: 20.10.9  3coins algorithm

Web: 19.2.1.6  Bucket sorting with floor functions

Text: 4.1, 4.2, 4.3.1, 4.3.3, 6.4.1, 6.4.4

Web: 5.1.1  Introduction to trees (Luc Devroye's
class notes)

Web: 5.1.2  Tree traversals (preorder, inorder and
postorder)

Web: 5.3.3  Binary search trees (Luc Devroye's class
notes)
Suggested Play

Web: 20.10  Convex hull applets

Web: 20.6  Polygonization applet (Hamiltonian noncrossing circuits of
points)

Web: 5.3.3  Binary search tree applet (Luc Devroye's
class notes)

Web: 5.1  Tree traversal applet (Luc Devroye's class
notes)
Week 7 Oct 14 and
16
Lecture 13:

Master theorems for solving recurrence equations

Lower bounds via reduction continued:

Example with noncrossing Hamiltonian circuit of a point set

Convex hull algorithms for planar point sets continued:

The 3coins procedure and applications:

Graham's algorithm in O(n log n) time

Proof that the 3coins algorithm computes the convex hull of a starshaped
polygon in O(n) time

Examples of polygons triangulated with 3coins algorithm

Illumination problems in computer graphics

Illuminating the edges of a polygon versus its interior
Lecture 14

Searching:

Fast point location queries in convex polygons

Range searching

Geometric Search with the locus method

Balanced multiway search trees:

(24)trees

Inserting keys in 24 trees

Deleting keys from 24 trees

Searching for the diameter of a set

Web: 1.4.2  MasterMind applet (decision trees)

Web: 5.5.1  (24)tree applet
Week 8  Oct 21 and
23
Lecture 15

Locus search methods

Range searching via domination queries

Stringcomparison algorithms

Hamming distance

Euclidean distance

Swapdistance

Directed swap distance (scaffold assignment problem)

Linear assignment problems
Lecture 16

Dynamic programming

Divide and conquer with the mastertheorem method

Merge sort

Convex hull and triangulation (merging with 3coins
algorithm or rotating calipers)

Quicksort with secondary storage
Reading Assignment

Handout: Integer multiplication in O(n^1.585) worst
case time

Text: 6.8  Dynamic programming (edit distance in
sequence comparison)

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

Text: 6.4.4  Quicksort and randomized quicksort

Web: 19.2.1.7  Quicksort tutorial

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

Point inclusion query searching

Nearest neighbor search:

Projection methods

Inplace quicksort

Randomized quicksort

Expected complexity of quicksort

Editdistance between sequences

Dynamic programming approach
Lecture 18:

Line sweep methods

3coloring the vertices of an arrangement of lines

Range searching with balanced search trees

Orthogonal Hamiltonians:

Reconstructing simple polygons from their vertex
set

Testing selfintersections in polygons

Computing orthogonalsegment intersections via linesweep
technique and balanced search trees
Problem Assignment #5 "due" November 18

Algorithms
on sequences

Edit
distance between strings

Graph
embeddability
Reading Assignment

Text: 8.6  Orthogonal segment intersections

Web: 6.7.1  Projection methods for nearest neighbor
search
Suggested Play

Web: 5.6  Heap applet

Web: 6.8.1  Closestpair applet

Web: 6.7.1  Nearest neighbor search applet
Week 10  Nov 4 and
6
Lecture 19: 2nd
InClass test (November 4)
Lecture 20

Hamiltonian cycles in dense graphs:

Proof of Ore's theorem on cycleHamiltonicity of dense graphs via backwards
induction

Implementing the backwards induction proof into an O(n^2) algorithm

Priority queues via the heap data structure:

Insertion and deletion in heaps in O(log n) time

Building heaps:

In O(n log n) time via topdown insertion

In O(n) time via bottomup divide & conquer

Proof of linearity via geometric series

Updating the pointer to LAST in heaps after insertions
and deletions

Application of heaps to sorting (heapsort) in O(
n log n) time
Reading Assignment

Text: 7.12  Hamiltonian tours

Web: 5.6.2  Heaps (Luc Devroye's class notes)

Web: 5.6  Tutorial on heaps

Text: 4.3.2  Heaps

Web: 19.2.1.4  Heapsort tutorial

Text: 6.4.5  Heapsorting

Web: 4.2  Introduction to graphs (Luc Devroye's
class notes)
Week 11  Nov 11 and
13
Lecture 21:

Parallel models of computation:

Interconnection networks (MIMD machines: MultipleInstruction Multiple
Data)

Sorting with an array of processors

The oddeven transposition sort (parallel version of bubblesort)

SIMD machines (SingleInstruction MultipleData)

McCulloghPitts neurons

Threshold logic units

Solving systems of linear inequalities
Lecture 22:

Parallel models of computation cont.

Perceptrons and Neural networks

SIMD machines (SingleInstruction MultipleData)

Laplacian operators

Latteral inhibition networks

Machine learning algorithms

Nearest neighbor search in O(1) time with neural networks

Searching Graphs:

Depthfirst search in a graph with a stack

Breadthfirst search with a queue

Data structures for graphs

Adjacency matrices

Adjacency lists

Complexity analysis of DFS and BFS
Problem Assignment #6 ("due" November 27)

Greedy
algorithms and leastcost Hamiltonian cycles in graphs

Hamiltonian
cycles in dense graphs (Ore's theorem)

Parallel
computation models
Reading Assignment

Text: 12.4, 12.4.1  Parallel algorithms for interconnection networks:
sorting on an arrray

Web: 18.2  Real and artificial neurons

Web: 18.3  Threshold logic units

Web: 18.5  Perceptrons and neural networks

Web: 18.6  Neural networks for lateral inhibition (computing Laplacians
and image sharpening)
Suggested Play

Web: 4.2  Adjacency matrix and list applet

Web: 6.3.3  3D Maze Applet
Week 12  Nov 18 and
20
Lecture 23:

Computational Aspects of Music:

Necklaces and Bracelets,

Homometric Rhythms,

The Hexachordal Theorem,

Patterson's Theorems,

Flat Rhythms

Deep Rhythms and Scales
Lecture 24

Graphs:

Terminology

Isomorphic versus isotopic graphs

Eulerian circuits:

Eulerian tours and the Konigsberg bridge problem

The EulerHierholzer Theorem

Fleury's algorithm for computing Euler trails

Eulerian graphs need not be Hamiltonian

Hamiltonian graphs need not be Eulerian

Map coloring:

2coloring the faces of an arrangement of lines

2coloring the faces of a selfintersecting closed curve

3coloring the vertices of an arrangement graph

3coloring the vertices of a triangulated polygon

Scheduling problems via graph coloring

The chromatic number of a graph

The fourcolor theorem
Reading Assignment

Text: 7.2  Eulerian graphs

Web: 22.1  Computational Aspects of Musical Rhythm

Web: 4.3  Graph isomorphism

Web: 4.4  Graph planarity

Web: 4.14  The Bridges of Konigsberg Problem

Web: 4.7.2  Euler circuits

Web: 4.7.5  Paths and circuits

Web: 4.7.6  Algorithm for constructing an Eulerian circuit
Suggested Play

Web: 4.7.7.1  Euler traversal applet
Week 13  Nov 25 and
27
Lecture 25

Map coloring:

Euler's formula for planar graphs

Proof that every planar graph has a vertex of degree at most 5

Induction proof of the the 5color theorem for planar graphs

Algorithm for 5coloring planar graphs in O(n^2) time

Digraphs and tournaments:

Round robin tournaments

Proof that the winner in a round robin tournament loses games only to teams
that lose to teams defeated by the winner
Lecture 26

Hommometric sets:

Proofs of the hexachordal theorem
_____________________________________________________
Additional Possible Material

Digraphs and tournaments cont:

Proof by induction that tournaments contain a Hamiltonian path

O(n^2) algorithm for computing a Hamiltonian path in a tournament

Travelling Salesperson Problem (TSP):

Two versions of TSP (triangle inequality graphs)

Reducing the TSP to a Hamiltonian circuit problem

Approximation algorithms for TSP:

The nearestneighbor heuristic

The twicearoundtheMST heuristic

Minimum spanning trees:

Kruskal's algorithm using heaps

Prim's algorithm using adjacency matrices

Baruvka's algorithm using adjacency lists

Closestpair searching:

In 1D via divide and conquer in O(n log n) time

In 2D via divide and conquer algorithm

In O(n log^2 n) time

In O(n log n) time

In 2D via linesweep algorithm with (2,4) trees
in O(n log n) time

Coding theory and data compression:

Block and Prefix codes

ShannonFano codes

Huffman coding

HuTucker algorithm with heaps

SchwartzKallick algorithm

LempelZiv coding for data compression

Other Huffman tree applications:

Merging sorted files with a minimum number of comparisons

Random number generation with a minimum number of comparisons
Reading Assignment

Text: 7.6  Minimumcost spanning trees

Web: 4.11.1  Minimum spanning trees (Luc Devroye's
class notes)

Web: 4.11.2  Minimum spanning trees (David Eppstein's
class notes)

Web:4.11.3  Kruskal's and Prim's algorithms tutorial

Web: 4.10.1  Hamiltonian paths in tournaments

Web: 4.10.3.1  Posa's proof of Dirac's theorem

Handout: Travelling Salesperson Problem
Suggested Play

Web: 4.11.4.2  Kruskal MST algorithm applet

Web: 4.11.3  AnotherKruskal MST algorithm applet

Web: 4.11.6  Prim MST algorithm applet

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

Text: 8.5  Closest pair

Web: 6.8.1  Closestpair searching tutorial

Web: 20.11.1  Voronoi diagrams

Text: 6.6  Data compression

Web: 5.7.1.6  Huffman trees and applications (Luc
Devroye's class notes)

Web: 5.7.1.3  ShannonFano coding

Web: 5.7.1.4  Huffman coding

Web: 5.7.1.5  Optimality of Huffman coding

Web: 5.7.1.10  LempelZiv adaptive codes (Luc
Devroye's class notes)
Suggested Play

Web: 5.7.7 and 5.7.8  Huffman coding applets