# 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 6 and 8

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 20
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 13 and 15

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 20 and 22
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" January 29)
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 27 and 29

##### 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 marks
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. Text: 8.3 - Star-shaped polygonization of point sets
5. Web: 1.4.1 - Recursion (Luc Devroye's class notes)
6. Web: 1.4.1.1 - Fibonacci algorithms
7. Web: 1.4.1.9 - Proofs of Binet's formula
8. Web: 4.10.7 - Polygonization of point sets
9. Web: 20.6 - Polygonizing sets of points
##### 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 3 and 5

Lecture 9: Complexity Classes and Examples
1. Solving recurrence relations by guess and test plus induction
1. Master theorems
2. Running time: constant, logarithmic, linear, n log n, quadratic, cubic, polynomial, exponential, factorial
3. Proof that the exponential function grows faster than the polynomial function
4. 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
##### Bucket sorting, floor functions, convex hulls, and lower bounds via reduction
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: 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
##### 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 10 and 12 - Class Test #1 Tuesday Feb 10

##### Lecture 12: Tree traversals, more floor functions, maximum gap, lower bounds for sorting
1. Tree traversals:
1. The Euler-Tour traversal of a tree
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
2. Lower bounds on the complexity of problems
3. Computing the maximum gap in O(n) time with floor functions
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 17 and 19

##### Lecture 13: Searching and balanced trees
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 in 2-4 trees
##### Lecture 14: Convex hulls and lower bounds continued...
1. Addition, Multiplication and Fast Fourier Transforms
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
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. Web: 21.1 - Addition, Multiplication, and Fast Fourier Transforms
4. Text: 6.4.6 - Lower bound for sorting
5. Text: 10.1, 10.4.1, 10.5 - Lower bound reductions
6. 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 - Feb 24 and 26 (Feb 24 and 26 no class due to study break)

##### Lecture 15: String comparison
1. 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 3 and 5

##### 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: Euler Tours and Searching
1. Euler tours
2. Line sweep methods
1. 3-coloring the vertices of an arrangement of lines
3. Range searching with balanced search trees
4. 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" March 17
1. Text: 8.6 - Orthogonal segment intersections
2. Web: 4.7.7.2 - Ethan's notes on Euler tours
##### 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 10 and 12

##### Lecture 19:
Lecture 20:

1. 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
2. Application of heaps to sorting (heapsort) in O( n log n) time
1. Web: 5.6.2 - Heaps (Luc Devroye's class notes)
2. Web: 5.6 - Tutorial on heaps
3. Text: 4.3.2 - Heaps
4. Web: 19.2.1.4 - Heapsort tutorial
5. Text: 6.4.5 - Heapsorting
6. Web: 4.2 - Introduction to graphs (Luc Devroye's class notes)

### Week 11 - March 17 and 19

##### Lecture 21: Graph Theory
1. 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
##### Lecture 22: Parallel computation
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 7)
1. Text: 4.6 - Adjacency matrix
2. Web: 6.3.1 - Depth-first search (Luc Devroye's class notes)
3. Web: 6.4 - Breadth-first search (Luc Devroye's class notes)
4. 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 24 and 26

##### Lecture 24: More Graph Theory and Hamiltonian Circuits
1. Graphs:
1. Terminology
2. Isomorphic versus isotopic graphs
2. 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
1. Text: 7.12 - Hamiltonian tours
2. Text: 7.2 - Eulerian graphs
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 - 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
1. Web: 8.1 - Greedy algorithms
2. Web: 8.2 - The rotating calipers
3. Web: 8.2.1 - The rotating caliper page
4. Web: 8.2.2 - The Reuleaux triangle (Eric-s Treasure Trove)
5. Web: 8.2.3 - The Reuleaux triangle (Geometry Junkyard)

Week 14 April  7 and 9
##### Lecture 27: Nearest neighbors and parallel computation
1. Sequential nearest neighbor search:
1. Projection methods
2. Voronoi diagram methods
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. Receptor cell networks and lateral inhibition
2. McCullogh-Pitts neurons
3. Threshold logic units
4. Reinforcement learning algorithms in dual weight-space
5. Solving systems of linear inequalities
##### Lecture 28: Map coloring
1. 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 theore
8. Euler's formula for planar graphs
9. Proof that every planar graph has a vertex of degree at most 5
10. 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
1. Web: 6.7.1 - Projection methods for nearest neighbor search
2. Text: 12.4, 12.4.1 - Parallel algorithms for interconnection networks: sorting on an arrray
3. Web: 18.5 - Perceptrons and neural networks
4. Web: 18.6 - Neural networks for lateral inhibition (computing Laplacians and image sharpening)

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