# Lecture Descriptions, Exams, 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-14

### Week 1-Sept 5 and 7

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
##### Problem Assignment #1 -Solutions posted September 19

Lecture 2: Induction Proofs

1. Euclid's second proposition cont.
1. Case analysis in proofs
2. Introduction to induction proofs
1. Example 2: 2-coloring the faces of an arrangement of lines in the plane
2. Example 1: 3-coloring the vertices of a triangulated polygon
1. Text: Chapter 1 and Sections 2.1, 2.1 and 2.3.
2. Web: 1.2.10.2 - A New Look at Euclid's Second Proposition (Handout)
3. Web: 2.1 - Notes on methods of proof
4. Web: 2.2 - Notes on how to do proofs
##### 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.3 - Classical fallatious proofs

### Week 2-Sept 12 and 14

##### Lecture 3: More on Proofs
1. If and only if
1. The infinitude of primes
3. Existence proofs
1. Coloring the points of the plane with two colors
4. Strong induction: triangulating polygons via diagonal insertion
5. Graph theory terminology
6. Double induction
1. Proof of Euler's formula for connected planr graphs
##### Lecture 4:Proximity Graphs
1. Abstract graphs and geometric graphs
2. Proximity graphs
1. Trees
2. Minimal spanning trees
3. Relative neighborhood graphs
3. Applications of MST to text-line orientation estimation
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 notes)
4. Web: 4.4 - Web Tutorials: Introduction to Graph Theory
##### Suggested Play
1. Web: 20.3 - Minimal spanning tree applet
2. Web: 4.12 - Euler's theorem
3. Web: 20.2 - Art Gallery Theorem (applet)
##### Lecture 5:Turing Machines and Random Access Machines
1. Digital models of computation
1. Turing machines
2. Random access machines
3. Ceiling and floor functions
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
##### Lecture 6: Complexity Classes and Examples
1. Running time: constant, logarithmic, linear, n log n, quadratic, cubic, polynomial, exponential, factorial
2. 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
4. Polygon triangulation in cubic time
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.2 - 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 26 and 28

##### 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. Polygon triangulation in quadratic time
1. Geoff's algorithm
Lecture 8: Solving Recurrence Relations
1. Solving the Fibonacci recurrence relation by induction
1. Approximately
2. Exactly (Binet's formula)
2. Divide & conquer recurrence relations
1. Merge sort
2. The master theorem
1. Text: Chapter 3
2. Text: 6.4.3 - Merge sort
3. Web: 1.4.1 - Recursion (Luc Devroye's class notes)
4. Web: 1.4.1.1 - Fibonacci algorithms
5. Web: 1.4.1.9 - Proofs of Binet's formula
##### Suggested Play
1. Web: 1.4.1.2 - Fibonacci math
2. Web: 1.4.1.3 - Fibonacci and nature

### Week 5-Oct 3 and 5

##### Lecture 10: Floor Functions, Maximum Gap and Bucket Sorting
1. Computing the maximum gap in O(n) time with floor functions
3. Bucket sorting real numbers in O(n) expected time
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 up to and including 6.4.3
5. Web: 19.2.1.6 - Bucket sorting with floor functions
##### Suggested Play
1. Web: 1.4.1.6 - Fibonacci numbers and domino tilings
2. Web: - 19.2.1.1 - Sorting animation applets

## Week 6 - October 10 and 12

##### Lecture 11:
1. Probabilistic analysis of bucket-sort:
1. Proof that bucket-sort takes O(n) expected time
2. Tree traversals:
1. The Euler-Tour traversal of a tree
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
3. Binary search trees:
1. Inserting and deleting items from BST's
##### Lecture 12:
1. Complexity of updating binary search trees
2. Balanced multi-way search trees:
1. 2-4 trees
2. Inserting items in 2-4 trees
3. Deleting items from 2-4 trees
3. Searching data bases:
1. Two-dimensional range search via the locus method
1. Text: 4.1, 4.2, 4.3.1, 4.3.3
2. Web: 5.1.1 - Introduction to trees (Luc Devroye's class notes)
3. Web: 5.1.2 - Tree traversals (preorder, inorder and postorder)
4. Web: 5.3.3 - Binary search trees (Luc Devroye's class notes)
5. Web: 5.5.1 - (2,3,4)-tree tutorial with applet
##### Suggested Play
1. Web: 5.3.3 - Binary search tree applet (Luc Devroye's class notes)
2. Web: 5.1 - Tree traversal applet (Luc Devroye's class notes)

### Week 7- Oct 17 and 19

##### Lecture 13
1. Priority queues via the heap data structure
1. Insertion and deletion in heaps in O(log n) time
2. Building a heap in O(n) time
3. Application to sorting (heapsort)
##### Lecture 14
1. Non-crossing Hamiltonians of point sets
1. Convex hull algorithm of Rosenberg & Landgridge - O(n^3)
2. Monotone simple Hamiltonian circuits in O(n log n) time - The double-comb algorithm
3. Star-shaped Hamiltonian circuits in O(n log n) time

Problem Assignment 4 "due" November 2, 2000

1. Text: 4.3.2 - Heaps
2. Web: 5.6.2 - Heaps (Luc Devroye's class notes)
3. Web: 5.6 - Tutorial on heaps
4. Web: 19.2.1.4 - Heapsort tutorial
5. Text: 6.4.5 - Heapsorting
##### Suggested Play
1. Web: 5.6 - Heap applet

### Week 8 - Oct 24 & 26

##### Lecture 15
1. Lower bounds:
1. Lower bounds on the complexity of problems (comparison model of computation)
2. Decision trees:
1. Algebraic decision trees
2. Linear decision trees
3. Comparison trees
3. Optimality of O(n log n) sorting algorithms (heapsort, mergesort)
4. Lower bounds by reduction
1. Example with non-crossing Hamiltonian circuit of a point set
2. Example with convex hull problem
2. More convex hull algorithms:
2. Divide and conquer
##### Lecture 16
1. More convex hull algorithms:
1. 3-coins algorithm for polygons
1. Star-shaped polygons
2. Monotone polygons
2. Grahams's algorithm - O(n log n)
3. Divide and conquer with presorting - O(n log n)
4. Beneath-beyond method (sequential insertion method)
1. Text: 6.4.6 - Lower bound for sorting
2. Text: 10.1, 10.4.1, 10.5 - Lower bound reductions
3. Web: 1.4.2 - Lower bounds (Luc Devroye's class notes)
4. Text: 8.1, 8.2, 8.3, 8.4 - Convex hull algorithms
5. Web: 20.10 - Convex hull algorithms
##### Suggested Play
1. Web: 20.6 - Polygonization applet
2. Web: 20.10 - Convex hull applets
3. Web: 1.4.2 - MasterMind applet (decision trees)

### Week 9 - Oct 31 and Nov 2

##### Lecture 17
1. Data compression:
1. Prefix codes
2. Minimal prefix codes
3. Shannon-Fano coding
4. Huffman coding
1. Hu-Tucker algorithm with heaps
2. Schwartz-Kallick algorithm
2. Huffman trees:
1. Applications
1. Merging sorted files
2. Random number generation
##### Lecture 18
1. 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 algorithms
1. O(n log^2 n)
2. O(n log n)
##### Problem Assignment #5 "due" November 16
1. Text: 6.6 - Data compression
2. Web: 5.7.6 - Huffman trees (Luc Devroye's class notes)
3. Web: 7.1.3 - Shannon-Fano coding
4. Web: 7.1.4 - Huffman coding
5. Text: 8.5 - Closest pair searching
6. Web: 6.8.1 - Closest-pair searching tutorial
##### Suggested Play
1. Web: 5.7.7 and 5.7.8 - Huffman coding applets
2. Web: 6.8.1 - Closest-pair applet

### Week 10 - Nov 7 and 9

##### Lecture 20
1. 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
2. Closest-pair searching:
1. Line-sweep algorithm with (2,4) trees in O(n log n) time
1. Text: 8.6 - Orthogonal segment intersections
2. Web: 6.7.1 - Projection methods for nearest neighbor search
3. Web: 4.2 - Introduction to graphs (Luc Devroye's class notes)
##### Suggested Play
1. Web: 6.7.1 - Nearest neighbor search applet

### Week 11 - Nov 14 and 16

##### Lecture 21: Guest lecturer - Tom Fevens
1. Basic definitions of graphs
2. Data structures for graphs
3. Searching mazes and labyrinths
2. Gaston Tarry's algorithm (1895)
4. Depth-first search in a graph
5. Breadth-first search in a graph
6. Complexity analysis of DFS and BFS
##### Lecture 22: Guest lecturer - Felix Kwok
1. Map and graph coloring:
1. Planarity
1. Proof of non-planarity of K5 using Euler's formula
2. Dual graphs
3. The four-color theorem and its history
4. Induction proof of 5-color theorem
1. Algorithm for coloring a plane graph
##### Problem Assignment #6 ("due" November 30)
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.3 - Depth-first search and breadth-first search
5. Web: 4.16 - Rotating caliper graph
6. Text: 8.6 - Intersections of horizontal and vertical segments
7. Web: 4.13.1 to 4.13.5 - Map coloring
Suggested Play
1. Web: 4.2 - Adjacency matrix and list applet
2. Web: 6.1.1 - A Maze Game
3. Web: 6.1.2 - 3D Maze Applet
4. Web: 6.3.1.1 - Depth-first search applet
5. Web: 6.4.1 - Breadth-first search applet

### Week 12 - Nov 21 and 23

##### Lecture 23
1. Two-colorability
1. Closed-Jordan-curve maps
2. The scheduling problem as graph coloring
1. Chromatic number of a graph
3. Graph isomorphism
4. Eulerian tours and the Konigsberg bridge problem
5. The Euler-Hierholzer Theorem
##### Lecture 24 Course Evaluations
1. Digraphs and tournaments
1. Round robin tournaments
2. Proof that tournaments are path-Hamiltonian
3. Proof that the distance btween the maximum-degree vertex and all others is at most two
2. Dense graphs
1. Proof of Ore's theorem on cycle-Hamiltonicity of dense graphs
1. Web: 4.3 - Graph isomorphism
2. Web: 4.4 - Graph planarity
3. Web: 4.14 - The Bridges of Konigsberg Problem
4. Web: 4.7.2 - Euler circuits
5. Text: 7.2 - Eulerian graphs
6. Text: 7.12 - Hamiltonian tours
7. Web: 4.10.1 - Hamiltonian paths in tournaments

### Week 13 - Nov 28 and 30

##### Lecture 25
1. Hill climbing algorithms
2. Greedy algorithms
3. Minimum spanning trees (MST)
1. Kruskal's algorithm via heaps
2. Prim's algorithm
3. Baruvka's algorithm
##### Lecture 26
1. Travelling salesman problem
1. Nearest neighbor heuristic yields O(log n) times optimal
2. Approximation algorithm via MST yields twice optimal
2. Selection:
1. Via sorting
2. Via heaps
3. Finding the median of a set of numbers in linear time
1. The median of medians algorithm
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.17.1 and 4.17.2 - Travelling saleman problem
6. Web: 4.17.7 - Twice-optimal approximate TSP algorithm
7. Web: 19.2.2 - Selection and order statistics
8. Web: 14.3 - Linear time selection (Luc Devroye's course notes)
9. Web: 14.4 - Linear time selection (David Eppstein's course notes)
##### Suggested Play
1. Web: 4.11.3 - Kruskal algorithm applet
2. Web: 4.17.3 and 4.17.4 - Great applets for travelling salesman problem
3. Web: 4.17.6 - Great applet for TSP heuristics
4. Web: 5.6 - Selection applet

### Week 14 - December 5

Lecture 27: No lecture due to Study Day