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

- Introduce course
- Introduction to induction proofs
- Example of 3-coloring triangulated polygons
- Induction proof (triangles in arrangements of lines)
- Induction proof (sum of squares of numbers)
- Induction proof (circle map coloring)
- The collapsing compass computer (translate a segment)
- Text: Preface and Chapter 1
- Web: 2.1 - Notes on methods of proof
- Web: 1.1.3 - Pythagoras proof applets
- Web: 1.2.1 - Straight-edge-and-compass constructions applet of Francois Labelle

- The collapsing compass computer
- Euclid's second proposition
- Constructive (direct) proofs
- Case-analysis in proofs

- The sum of the first n natural numbers
- Constructive direct proof
- Induction proof
- Proof by contradiction
- Number of prime numbers
- Diameter of a convex polygon
- Constructive case analysis
- 3-coloring the plane
- Counting regions in the plane
- Arrangement of lines
- Text: 2.1 - 2.6, 2.13, 2.14, 7.1
- Web: 1.2.10.2 - A New Look at Euclid's Second Proposition (Handout)
- Web: 2.1 - Notes on methods of proof
- Web: 1.2.7.1 - Euclid's second proposition applet
- Web: 1.1.3.1 - Pythagoras' theorem applet
- Web: 1.2.3 - The straight edge and compass
- Web: 2.2 - Classical fallatious proofs

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

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

- Algorithms for computing the Fibonacci function
- Exponential - O(2^n)
- Linear - O(n)
- Logarithmic - O(log n)
- More induction
- Triangulating sets of points
- Two-ears theorem
- Binary search
- A master theorem of recursion
- Divide and conquer
- Sorting
- Insertion sort
- Selection sort
- Bubble sort
- Divide and conquer (merge sort)
- Bucket sort with floor functions
- Turing machines
- Matrix powering and the Fibonacci function
- The skyline problem (Divide and Conquer)
- Graphs (properties of vertices of odd degree)
- Text: 9.2 - Exponentiation
- Text: 5.6 - The skyline problem (divide and conquer)
- Text: Chapter 6 up to and including 6.4.3
- Web: 1.4.1.1 - Fibonacci algorithms (David Eppstein)
- Web: 20.1.2.3 - Two-Ears theorem (Ian Garton)
- Web: 19.2.1.6 - Bucket sorting with floor functions
- Web: 1.4.1.6 - Fibonacci numbers and domino tilings
- Web: - 19.2.1.1 - Sorting animation applets

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

**Prune-and-search methods:**- Finding an ear of a polygon in linear time
- Point-in-polygon problems
- Area of a polygon
- The geometric series
- Proof that a reflex vertex admits a diagonal
**Finding the closest pair:**- By brute force
- By induction
- Via repeated nearest neighbor searches
- The nearest neighbor graph
- The closest-pair via divide and conquer
- In one dimension in O(n log n) time
- In two dimensions
- In O(n log^2 n) time
- In O(n log n) time
- Number of comparisons in binary search
- Element uniqueness
- Non-collinearity of points
- Computing maximal points of a set
- Handout: Area of a polygon
- Text: 8.2 - Point-in-polygon testing
- Web: 14.1 - The geometric series
- Web: 14.2 - Finding an ear in linear time with prune-and-search
- Text: 8.5 - Closest pair
- Web: 14.2 - Ear-cutting applet

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

- Review solutions to quiz #3
- Graph isomorphism
- Graph planarity
- Eulerian tours and the Konigsberg bridge problem
- The Euler-Hierholzer Theorem
- Searching mazes and labyrinths
- Ancient Greek algorithm (Ariadne's thread)
- Gaston Tarry's algorithm (1895)
- Web: 4.2 - Introduction to graphs (Luc Devroye's class notes)
- Web: 4.3 - Graph isomorphism
- Web: 4.4 - Graph planarity
- Web: 4.14 - The Bridges of Konigsberg Problem
- Web: 4.6.2 - Euler circuits
- Text: 7.2 - Eulerian graphs
- Text: 4.6 - Adjacency matrix
- Handout: Doubly-connected edge list
- Web: 6.3.1 - Depth-first search (Luc Devroye's class notes)
- Web: 6.4 - Breadth-first search (Luc Devroye's class notes)
- Web: 4.2 - Adjacency matrix and list applet
- Web: 6.1.1 - A Maze Game
- Web: 6.1.2 - 3D Maze Applet
- Web: 6.3.1.1 - Depth-first search applet
- Web: 6.4.1 - Breadth-first search applet

- Data structures for graphs
- Adjacency matrices
- Adjacency lists
- Doubly-connected edge lists for plane graphs
- Depth-first search in a graph
- Breadth-first search in a graph
- Hill climbing algorithms
- Greedy algorithms
- The diameter of a convex polygon
- Via depth-first search
- Hamiltonian graphs
- Relation to Eulerian graphs
- Digraphs and tournaments
- Proof that tournaments are Hamiltonian
- Dense graphs
- Proof of Ore's theorem on Hamiltonicity of dense graphs
- The diameter of a convex polygon
- Via rotating caliper graph
- Proof that the diameter is an antipodal pair
- Text: 7.3 - Depth-first search and breadth-first search
- Web: 4.16 - Rotating caliper graph
- Handout: Multiway trees: 2-4-trees
- Text: 7.12 - Hamiltonian tours
- Web: 20.6 - Polygonization applet

**Simple Hamiltonian cycles in point sets:**- Polygonizing planar sets of points
- Star-shaped polygonizations
- Monotonic polygonizations
- Spiral polygonizations
- Orthogonal polygonizations
- Reconstructing simple polygons from their vertex set
- Testing self-intersections in polygons
- Computing segment intersections via plane-sweep technique and balanced search trees
**Map and graph coloring:**- Dual graphs
- Two-colorability
- Maps determined by arrangements of lines and circles
- Closed-curve maps
- The scheduling problem as graph coloring
- Cromatic number of a graph
- Handout: Rotating calipers and diameter
- Text: 8.3 - Constructing simple polygons
- Text: 8.6 - Intersections of horizontal and vertical segments
- Web: 4.13.1 to 4.13.5 - Map coloring
- Web: 20.6 - Polygonization applet
- Web: 20.6.1 - Polygon reconstruction applet (orthogonal connect-the-dots)
- Web: 4.11.1 - Minimum spanning tree applet

**Suggested Play**

- Induction proof of 5-color theorem
- Three-colorability
- Triangulated polygons
- Line-arrangement graphs
- O(n^2 log n) time algorithm
- Minimum spanning trees
- Kruskal's algorithm
- Baruvka's algorithm
- Greedy algorithms and least-cost Hamiltonian cycles in graphs
- Hamiltonian cycles in dense graphs (Ore's theorem)
- Convex hulls of points
**Convex hulls of points:**- Rosenberg & Landgridge algorithm - O(n^3)
- Jarvis Algorithm (gift wrapping) - O(nh)
- Expected number of points on the convex hull
- Beneath-beyond algorithm - O(n^2)
- Divide-and-conquer - O(n log n)
- Graham's algorithm - O(n log n)
- The 3-coins algorithm for monotone polygons and chains in O(n) time
- Lower bound on the complexity of the convex hull problem via reduction from sorting
- Text: 7.6 - Minimum-cost spanning trees
- Web: 4.11.1 - Minimum spanning trees (Luc Devroye's class notes)
- Web: 4.11.2 - Minimum spanning trees (David Eppstein's class notes)
- Web:4.11.3 - Kruskal's algorithm tutorial
- Text: 8.4 - Convex hulls
- Web: 20.10 - Convex hulls of points
- Web: 4.11.3 - Kruskal algorithm applet
- Web: 20.10 - Convex hull applets

**Suggested Play**

- Priority queues via the
**heap**data structure - application to sorting (heapsort)
- application to minimum spanning trees (Kruskal's algorithm)
- More convex hulls
- Throw-away principle - O(n) expected time (Quickhull)
**Prune-and-search methods revisited:**- Quicksort
- Randomized quicksort
- Selection
- Via sorting
- Via heaps
- Randomized selection
- Finding the median of a set of numbers in linear time
- Text: 4.3.2 - Heaps
- Web: 5.6 - Tutorial on heaps
- Web: 19.2.1.4 - Heapsort tutorial
- Web: 19.2.2 - Selection and order statistics
- Web: 14.3 - Linear time selection (Luc Devroye's course notes)
- Web: 14.4 - Linear time selection (David Eppstein's course notes)
- Web: 5.6 - Heap applet