# 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 - Sept 2 and 4

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 September 16
Lecture 2: Proofs

1. The knotted string computer
2. More on case analysis in proofs:
1. Example from Ramsey Theory (5 points in general position contain an emty convex quadrilateral)
3. Geometric proof of  S(n) = 1+2+3+...+n = n(n+1)/2
4. Gauss proof of  S(n) = 1+2+3+...+n = n(n+1)/2
5. Introduction to induction proofs
1. Example 1: S(n) = 1+2+3+...+n = n(n+1)/2
2. Example 2: 2-coloring the faces of an arrangement of lines in the plane
3. Example 3: covering a 2^n by 2^n checkerboard with one square missing by L-shaped pieces.
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 - Sept 9 and 11

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. Proximity graphs
1. Minimal spanning trees (MST)
2. Relative neighbourhood graphs (RNG)
3. Proof (by contradiction) that for n points in the plane the MST is a subgraph of the RNG
4. Gabriel graphs
5. Delaunay triangulations and Voronoi diagrams
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 - Sept 16 and 18:
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" September 30)
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 - Sept 23 and 25

##### Lecture 7: Hamiltonian cycles of point sets, and rulers with few mark
1. Hamiltonian cycles induced by point sets (polygonizations)
1. Proof that the shortest polygonalization must be simple
2. Star-shaped polygonizations in O(n log n) time
3. Monotone polygonizations  in O(n log n) time
2. The skyline problem (hidden line removal in computer graphics)
1. O(n^2) via sequential insertion
2. O(n log n) via divide & conquer
##### Lecture 8: 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
2. Merge sort
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 - Sept 30 and Oct 2 - Class Test #1 Thursday October 2

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
##### Lecture 10: 1st Class Test (Thursday October 2) 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 - Oct 7 and 9

##### Lecture 11:  Tree Traversals, Floor Functions, Maximum Gap, Lower bounds for sorting, and Bucket Sorting
1. Lower bounds on the complexity of problems
2. Decision trees and lower bound for sorting (comparison model)
##### Lecture 12:
1. Tree traversals:
1. The Euler-Tour traversal of a tree
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
2. Computing the maximum gap in O(n) time with floor functions
3. Probabilistic analysis of bucket-sort:
1. Proof that bucket-sort takes O(n) expected time
4. 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
5. 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- Oct 14 and 16

##### Lecture 13:
1. Master theorems for solving recurrence equations
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
##### 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
3. Deleting keys from 2-4 trees
3. Searching for the diameter of a set
Problem Assignment 4 "due" October 30

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 - Oct 21 and 23

##### Lecture 15
1. Locus search methods
1. Range searching via domination queries
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. Dynamic programming
2. Divide and conquer with the master-theorem method
1. Merge sort
2. Convex hull and triangulation (merging with 3-coins algorithm or rotating calipers)
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
##### Suggested Play
Web: 21.1 - Applet for Dynamic programming (edit distance in sequence comparison)

### Week 9 - Oct 28 and 30

##### Lecture 17
1. Point inclusion query searching
2. Nearest neighbor search:
1. Projection methods
3. In-place quicksort
4. Randomized quicksort
1. Expected complexity of quicksort
5. 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
##### Problem Assignment #5 "due" November 18
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 - Nov 4 and 6

##### Lecture 19: 2nd In-Class test (November 4)
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 - Nov 11 and 13

##### 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" November 27)
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)
Suggested Play
1. Web: 4.2 - Adjacency matrix and list applet
2. Web: 6.3.3 - 3D Maze Applet

### Week 12 - Nov 18 and 20

##### Lecture 23:
1. Computational Aspects of Music:
1. Necklaces and Bracelets,
2. Homometric Rhythms,
3. The Hexachordal Theorem,
4. Patterson's Theorems,
5. Flat Rhythms
6. Deep Rhythms and Scales
##### Lecture 24
1. Graphs:
1. Terminology
2. Isomorphic versus isotopic graphs
2. 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
3. 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: 22.1 - Computational Aspects of Musical Rhythm
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 - Nov 25 and 27

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

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