# 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

### 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
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
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
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
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. 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

2. O(n log n) via divide & conquer
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
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
##### Lecture 10: 1st Class Test (Feb 6) Example test (2003)
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
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. 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
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. 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
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
2. Complexity analysis of DFS and BFS
##### Problem Assignment #6 ("due" April 5)
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
Suggested Play
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
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
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

5. Web: 4.17.6 - Great applet for TSP heuristics