COMP251B Data Structures and Algorithms 
Winter 2009
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  Jan 6 and 8
Lecture 2: Proofs
 The knotted string computer
 More on case analysis in proofs:
 Example from Ramsey Theory (5 points contain a convex
quadrilateral)
 Introduction to induction proofs
 Example 1: n(n+1)/2
 Example 2: 2coloring the faces of an arrangement of
lines in
the
plane
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  Jan 13
and
15
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
 Graph theory terminology
 Abstract graphs and geometric graphs
 Proximity graphs
 Minimal spanning trees (MST)
 Proof (by contradiction) that for n points in the
plane the
closest
pair determines an edge in the MST
 Relative neighbourhood graphs
 Sphereofinfluence graphs
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  Jan 20
and
22
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" January 29)
 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  Jan 27
and
29
Lecture 7: 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
Lecture 8: Hamiltonian
cycles
of point sets, and rulers with few marks
 Straight and circular rulers with few marks
 Hamiltonian cycles induced by point sets (polygonizations)
 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
Reading Assignment
 Text: Chapter 3
 Text: 6.4.3  Merge sort
 Text: 8.1, 8.2  Point inclusion testing
 Text: 8.3  Starshaped polygonization of point sets
 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
 Web: 20.6  Polygonizing sets of points
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  Feb 3
and
5
Lecture 9: Complexity
Classes
and Examples
 Solving recurrence relations by guess and test plus induction
 Master theorems
 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
 Proof that solution must be a simple circuit
Problem Assignment 3 "due" February 10
 Algorithms
for computing the Fibonacci function
 Binary
search
 The
skyline problem in computer graphics
 Analysis
of heapsorting
Lecture 10:
Bucket sorting,
floor functions, convex hulls, and lower bounds via reduction
 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: 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
Suggested Play
 Web: 1.4.1.6  Fibonacci numbers and domino tilings
 Web:  19.2.1.1  Sorting animation applets
Week 6  Feb 10 and 12 
Class
Test #1 Tuesday Feb 10
Lecture 11: 1st Class Test (Feb 6) Example test (2003)
Lecture 12: Tree traversals, more floor functions, maximum gap,
lower bounds for sorting
 Tree traversals:
 The EulerTour traversal of a tree
 Preorder traversal
 Inorder traversal
 Postorder traversal
 Lower bounds on the complexity of problems
 Computing the maximum gap in O(n) time with floor functions
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 Feb 17
and
19
Lecture 13: Searching and
balanced trees
 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 in 24 trees
Lecture 14: Convex
hulls and lower bounds continued...
 Addition, Multiplication and Fast Fourier Transforms
 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
Problem Assignment 4 "due" March 1
 Balanced
search trees
 Element
uniqueness
 Noncollinearity
of points
 Maximal
points of a set
Reading Assignment
 Handout: Geometric Search using the
locus
method
 Web: 5.5.1  (24)tree tutorial with
applet
 Web: 21.1  Addition, Multiplication, and
Fast Fourier Transforms
 Text: 6.4.6  Lower bound for sorting
 Text: 10.1, 10.4.1, 10.5  Lower bound
reductions
 Web: 1.4.2  Lower bounds (Luc
Devroye's
class notes)
 Web: 1.4.2  MasterMind applet (decision trees)
 Web: 5.5.1  (24)tree applet
Week 8  Feb 24
and
26 (Feb 24 and 26 no class due to study
break)
Lecture 15: String
comparison
 Stringcomparison algorithms
 Hamming distance
 Euclidean distance
 Swapdistance
 Directed swap distance (scaffold
assignment problem)
 Linear assignment problems
Lecture 16
 Graph embeddability
 Divide and conquer with the
mastertheorem
method
 Merge sort
 Triangulating planar point sets
(merging
with 3coins
algorithm)
 Integer multiplication in O(n^1.585)
worst case time
 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
Reading Assignment for 252 students only
 Text: 9.4  Polynomial multiplication
 Text: 9.6  The Fast Fourier Transform
Suggested Play
Web: 21.1  Applet for Dynamic programming
(edit
distance in sequence comparison)
Week 9  March 3
and
5
Lecture 17
 Inplace quicksort
 Randomized quicksort
 Expected complexity of quicksort
 Editdistance between sequences
 Dynamic programming approach
Lecture 18: Euler Tours
and Searching
 Euler tours
 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" March 17
 Algorithms
on sequences
 Edit
distance between strings
 Graph
embeddability
Reading Assignment
 Text: 8.6  Orthogonal segment
intersections
 Web: 4.7.7.2  Ethan's notes on Euler
tours
Suggested Play
 Web: 5.6  Heap applet
 Web: 6.8.1  Closestpair applet
 Web: 6.7.1  Nearest neighbor search applet
Week 10  March
10
and 12
Lecture 20:
 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
 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  March
17
and 19
 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
Lecture 22: Parallel
computation
 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" April 7)
 Greedy
algorithms and leastcost Hamiltonian cycles in graphs
 Hamiltonian
cycles in dense graphs (Ore's theorem)
 Sorting
with a parallel array of processors
Reading Assignment
 Text: 4.6  Adjacency matrix
 Web: 6.3.1  Depthfirst search (Luc Devroye's class notes)
 Web: 6.4  Breadthfirst search (Luc Devroye's class notes)
 Text: 7.1  7.3  Depthfirst search
and
breadthfirst
search
Suggested Play
 Web: 4.2  Adjacency matrix and list applet
 Web: 6.3.3  3D Maze Applet
 Web: 6.3.1.1  Depthfirst search applet
 Web: 6.4.1  Breadthfirst search applet
Week 12  March
24
and 26
Lecture
23: 2nd
InClass test (Tuesday March 24)
Lecture 24: More Graph
Theory and Hamiltonian Circuits
 Graphs:
 Terminology
 Isomorphic versus isotopic graphs
 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
Reading Assignment
 Text: 7.12  Hamiltonian tours
 Text: 7.2  Eulerian graphs
 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  March
31
and April 2
Lecture 25: Greedy
algorithms (diameter)
1. Hill climbing
2. Searching for local maxima
3. Approximate algorithms
Lecture 26: Greedy
algorithms (diameter)
1. Rotating calipers algorithm
Reading Assignment
 Web: 8.1  Greedy algorithms
 Web: 8.2  The rotating calipers
 Web: 8.2.1  The rotating caliper page
 Web: 8.2.2  The Reuleaux triangle
(Erics Treasure Trove)
 Web: 8.2.3  The Reuleaux triangle
(Geometry Junkyard)
Week 14
April
7 and 9
Lecture 27: Nearest neighbors and parallel computation
 Sequential nearest neighbor search:
 Projection methods
 Voronoi diagram methods
 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)
 Receptor cell networks and lateral inhibition
 McCulloghPitts neurons
 Threshold logic units
 Reinforcement learning algorithms in dual weightspace
 Solving systems of linear inequalities
Lecture 28: Map coloring
 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 theore
 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
Reading Assignment
 Web: 6.7.1  Projection methods for
nearest
neighbor
search
 Text: 12.4, 12.4.1  Parallel algorithms for interconnection
networks:
sorting on an arrray
 Web: 18.5  Perceptrons and neural networks
 Web: 18.6  Neural networks for lateral inhibition (computing
Laplacians
and image sharpening)
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