CS251A/B Data Structures and Algorithms 
Fall 2008, 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 4 and 9
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 11 and
16
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 18 and
23
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" February 1)

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 25 and
30
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 mark

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
Week 5  Feb 1 and
6  Class Test #1 Tuesday Feb 6
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

Proof that solution must be a simple circuit
Problem Assignment 3 "due" February 15

Algorithms
for computing the Fibonacci function

Binary
search

The
skyline problem in computer graphics

Analysis
of heapsorting
Lecture 10:
1st Class Test (Feb 6) 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  Feb 8 and 13
Lecture 11: Guest
Lecturer  Pedro De Rezende 
Tree Traversals,
Floor
Functions, Maximum Gap, Lower bounds for sorting, and Bucket Sorting

Tree traversals:

The EulerTour traversal of a tree

Preorder traversal

Inorder traversal

Postorder traversal

Master theorems for solving recurrence equations

Lower bounds on the complexity of problems

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

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 Feb 15 and
27 (Feb 20 and 22 no class due to study break)
Lecture 13:

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

Web: 1.4.2  MasterMind applet (decision trees)

Web: 5.5.1  (24)tree applet
Week 8  March 1 and
6
Lecture 15

(24)trees continued:

Deleting keys from 24 trees

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

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

Nearest neighbor search:

Projection methods
Problem Assignment #5 "due" March 15

Algorithms
on sequences

Edit
distance between strings

Graph
embeddability

Quicksort
(for 252 students only)
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  March 15
and 20
Lecture 19: 2nd
InClass test (March 15)
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  March 22
and 27
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" April 5)

Greedy
algorithms and leastcost Hamiltonian cycles in graphs

Hamiltonian
cycles in dense graphs (Ore's theorem)

Sorting
with a parallel array of processors

Prim's
minimum spanning tree for graphs
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)

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 29
and April 3
Lecture 23:

Graphs:

Terminology

Isomorphic versus isotopic graphs

Eulerian circuits:

Eulerian tours and the Konigsberg bridge problem
Lecture 24

Eulerian circuits:

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: 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  April 5
and 10
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 (not
covered in final exam)

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