# Lecture Descriptions, Homework and Play

Text Book: Data Structures and Algorithms in JAVA by Michael Goodrich and Roberto Tamassia

Week: 1-2-3-4-5-6-7-8-9-10-11-12-13-14

### Week 1-Sept 2

##### Lecture #1: Induction Proofs
1. Introduce course
2. Introduction to induction proofs
1. Example of 3-coloring triangulated polygons
##### Problem Assignment #1 -due September 16
1. Text: Preface and Chapter 1
2. 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

### Week 2-Sept 7 and 9

##### Lecture #2: Ancient Models of Computation
1. The collapsing compass computer
1. Euclid's second proposition
2. Constructive (direct) proofs
3. Case-analysis in proofs
Lecture #3: More on Methods of Proof
1. The sum of the first n natural numbers
1. Constructive direct proof
2. Induction proof
1. Number of prime numbers
2. Diameter of a convex polygon
3. Constructive case analysis
1. 3-coloring the plane
4. Counting regions in the plane
1. Arrangement of lines
1. Text: 2.1 - 2.6, 2.13, 2.14, 7.1
2. Web: 1.2.10.2 - A New Look at Euclid's Second Proposition (Handout)
3. Web: 2.1 - Notes on methods of proof
##### Suggested Play
1. Web: 1.2.7.1 - Euclid's second proposition applet
2. Web: 1.1.3.1 - Pythagoras' theorem applet
3. Web: 1.2.3 - The straight edge and compass
4. Web: 2.2 - Classical fallatious proofs

### Week 3-Sept 14 and 16

##### Lecture #4: Graphs
1. If and only if
2. Graph theory terminology
3. Properties of trees
4. Inductive proof of Euler's formula
5. Strong induction: triangulating polygons via diagonal insertion
##### Lecture #5: Big "Oh" notation
1. QUIZ #1, homework #1 due, homework #2 out (due Sept. 30)
2. Big "Oh" Notation
3. Minimal spanning trees
##### Problem Assignment #2
1. Text: 2.7 - Euler's formula
2. Web: 4.1 - Interactive introduction to graph theory
3. Web: 4.2 - Introduction to graph theory (Luc Devroye's notes)
4. Text: 2.11 - Arithmetic-Geometric Mean Inequality
5. Web: 4.4 - Web Tutorials: Introduction to Graph Theory
6. Web: 1.3.1, 1.3.2, 1.4.1, 1.4.1.1- Turing Machines, RAM's, Complexity and Recursion
7. Text: 3.1, 3.2 - Big "Oh" notation
##### Suggested Play
1. Web: 20.3 - Minimal spanning tree applet
2. Web: 4.11 - Euler's theorem
3. Web: 20.1.2.1 - Triangulating polygons via ear-cutting (Ian Garton's tutorial with applet)
4. Web: 20.2 - Art Gallery Theorem (applet)

### Week 4-Sept 21 and 23

##### Lecture #6: Turing Machines and Random Access Machines
1. Review quiz #1
2. Little "oh" notation, L'Hospital's rule
3. Digital models of computation
1. Turing machines
2. Random access machines
4. Ceiling and floor functions
1. Computing the maximum gap in O(n) time
##### Lecture #7: Recursion
1. More on maximum gap
2. Recurrence Relations and Fibonacci sequences
1. Web: 1.3.1 - Introduction to Turing machines
2. Web: 1.3.2 - Turing machines and Random Access Machines
3. Text: Chapter 3
4. Web: 1.4.1.1 - Recursion (Luc Devroye's class notes)
##### Suggested Play
1. Web: 1.4.1.1 - Fibonacci math
2. Web: 1.4.1.1 - Fibonacci and nature

### Week 5-Sept 28 and 30

##### Lecture #8:
1. Algorithms for computing the Fibonacci function
1. Exponential - O(2^n)
2. Linear - O(n)
3. Logarithmic - O(log n)
2. More induction
1. Triangulating sets of points
2. Two-ears theorem
##### Lecture #9: QUIZ #2, homework #2 due, homework #3 out (due Oct 14)
1. Binary search
2. A master theorem of recursion
3. Divide and conquer
4. Sorting
1. Insertion sort
2. Selection sort
3. Bubble sort
4. Divide and conquer (merge sort)
5. Bucket sort with floor functions
##### Problem Assignment #3
1. Text: 9.2 - Exponentiation
2. Text: 5.6 - The skyline problem (divide and conquer)
3. Text: Chapter 6 up to and including 6.4.3
4. Web: 1.4.1.1 - Fibonacci algorithms (David Eppstein)
5. Web: 20.1.2.3 - Two-Ears theorem (Ian Garton)
6. 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 5 and 7

##### Lecture #10:
1. Lower bounds on the complexity of problems (comparison model of computation)
1. Searching in a list (optimality of sequential search)
2. Searching in an ordered list (optimality of binary search)
3. Optimality of merge-sort (decision trees)
##### Lecture #11:
1. Proof that bucket-sort takes O(n) expected time
2. Searching data bases:
1. Range search
2. Nearest neighbor search
1. Text: 6.4.6 - Lower bound for sorting
2. Web: 1.4.2 - Lower bounds (Luc Devroye's class notes)
3. Handout: Range searching (geometric searching)
4. Web: 6.7.1 - Projection methods for nearest neighbor search
##### Suggested Play
1. Web: 1.4.2 - MasterMind applet (decision trees)
2. Web: 6.7.1 - Nearest neighbor search applet

### Week 7 - Oct 12 and 14

##### Lecture #12:
1. Prune-and-search methods:
1. Finding an ear of a polygon in linear time
1. Point-in-polygon problems
2. Area of a polygon
3. The geometric series
4. Proof that a reflex vertex admits a diagonal
##### Lecture #13: homework #3 due, homework #4 out (due Oct 28 but postponed to Nov 2)
1. Finding the closest pair:
1. By brute force
2. By induction
3. Via repeated nearest neighbor searches
4. The nearest neighbor graph
5. The closest-pair via divide and conquer
1. In one dimension in O(n log n) time
2. In two dimensions
1. In O(n log^2 n) time
2. In O(n log n) time
##### Problem Assignment #4
1. Handout: Area of a polygon
2. Text: 8.2 - Point-in-polygon testing
3. Web: 14.1 - The geometric series
4. Web: 14.2 - Finding an ear in linear time with prune-and-search
5. Text: 8.5 - Closest pair
##### Suggested Play
1. Web: 14.2 - Ear-cutting applet

### Week 8 - Oct 19 and 21

##### Lecture #14:
1. Binary search trees:
1. Inserting and deleting items from BST's
2. The Euler-Tour traversal of a tree
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
2. One-dimensional range searching
3. Balanced multi-way search trees I:
1. 2-4 trees
2. Inserting items in 2-4 trees
##### Lecture #15: QUIZ #3
1. Balanced multi-way search trees II:
1. Deleting items from 2-4 trees
2. Applications:
1. Plane-sweep algorithm for closest-pair searching
1. Text: 4.3.3 - Binary search trees
2. Web: 5.1.2 - Tree traversals (preorder, inorder and postorder)
3. Web: 5.1 - Introduction to trees (Luc Devroye's class notes)
4. Web: 5.3.3 - Binary search trees (Luc Devroye's class notes)
5. Web: 5.5.1 - (2,3,4)-trees
##### 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)
3. Web: 6.8.1 - Closest-pair applet

### Week 9 - Oct 26 and 28

##### Lecture #16:
1. Review solutions to quiz #3
2. Graph isomorphism
3. Graph planarity
4. Eulerian tours and the Konigsberg bridge problem
##### Lecture #17:
1. The Euler-Hierholzer Theorem
2. Searching mazes and labyrinths
2. Gaston Tarry's algorithm (1895)
1. Web: 4.2 - Introduction to graphs (Luc Devroye's class notes)
2. Web: 4.3 - Graph isomorphism
3. Web: 4.4 - Graph planarity
4. Web: 4.14 - The Bridges of Konigsberg Problem
5. Web: 4.6.2 - Euler circuits
6. Text: 7.2 - Eulerian graphs
7. Text: 4.6 - Adjacency matrix
8. Handout: Doubly-connected edge list
9. Web: 6.3.1 - Depth-first search (Luc Devroye's class notes)
10. Web: 6.4 - Breadth-first search (Luc Devroye's class notes)
##### 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 10 - Nov 2 and 4

##### Lecture #18: homework #4 due, homework #5 out (due Nov 16)
1. Data structures for graphs
3. Doubly-connected edge lists for plane graphs
2. Depth-first search in a graph
3. Breadth-first search in a graph
4. Hill climbing algorithms
5. Greedy algorithms
1. The diameter of a convex polygon
1. Via depth-first search
##### Lecture #19:
1. Hamiltonian graphs
1. Relation to Eulerian graphs
2. Digraphs and tournaments
1. Proof that tournaments are Hamiltonian
3. Dense graphs
1. Proof of Ore's theorem on Hamiltonicity of dense graphs
4. The diameter of a convex polygon
1. Via rotating caliper graph
2. Proof that the diameter is an antipodal pair
1. Text: 7.3 - Depth-first search and breadth-first search
2. Web: 4.16 - Rotating caliper graph
3. Handout: Multiway trees: 2-4-trees
4. Text: 7.12 - Hamiltonian tours
##### Suggested Play
1. Web: 20.6 - Polygonization applet

### Week 11 - Nov 9 and 11

##### Lecture #20:
1. Simple Hamiltonian cycles in point sets:
1. Polygonizing planar sets of points
1. Star-shaped polygonizations
2. Monotonic polygonizations
3. Spiral polygonizations
2. Orthogonal polygonizations
1. Reconstructing simple polygons from their vertex set
2. Testing self-intersections in polygons
3. Computing segment intersections via plane-sweep technique and balanced search trees
##### Lecture #21: QUIZ #4
1. Map and graph coloring:
1. Dual graphs
2. Two-colorability
1. Maps determined by arrangements of lines and circles
2. Closed-curve maps
3. The scheduling problem as graph coloring
1. Cromatic number of a graph
1. Handout: Rotating calipers and diameter
2. Text: 8.3 - Constructing simple polygons
3. Text: 8.6 - Intersections of horizontal and vertical segments
4. Web: 4.13.1 to 4.13.5 - Map coloring

Suggested Play

1. Web: 20.6 - Polygonization applet
2. Web: 20.6.1 - Polygon reconstruction applet (orthogonal connect-the-dots)
3. Web: 4.11.1 - Minimum spanning tree applet

### Week 12 - Nov 16 and 18

##### Lecture #22: homework #5 due, homework #6 out (due Dec 2)
1. Induction proof of 5-color theorem
2. Three-colorability
1. Triangulated polygons
2. Line-arrangement graphs
3. O(n^2 log n) time algorithm
3. Minimum spanning trees
1. Kruskal's algorithm
2. Baruvka's algorithm
##### Lecture #23:
1. Convex hulls of points:
1. Rosenberg & Landgridge algorithm - O(n^3)
2. Jarvis Algorithm (gift wrapping) - O(nh)
1. Expected number of points on the convex hull
3. Beneath-beyond algorithm - O(n^2)
4. Divide-and-conquer - O(n log n)
5. Graham's algorithm - O(n log n)
1. The 3-coins algorithm for monotone polygons and chains in O(n) time
6. Lower bound on the complexity of the convex hull problem via reduction from sorting
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 algorithm tutorial
5. Text: 8.4 - Convex hulls
6. Web: 20.10 - Convex hulls of points

Suggested Play

1. Web: 4.11.3 - Kruskal algorithm applet
2. Web: 20.10 - Convex hull applets

### Week 13 - Nov 23 and 25

##### Lecture #24:
1. Priority queues via the heap data structure
1. application to sorting (heapsort)
2. application to minimum spanning trees (Kruskal's algorithm)
2. More convex hulls
1. Throw-away principle - O(n) expected time (Quickhull)
##### Lecture #24: Course Evaluations
1. Prune-and-search methods revisited:
1. Quicksort
2. Randomized quicksort
3. Selection
1. Via sorting
2. Via heaps
3. Randomized selection
4. Finding the median of a set of numbers in linear time