**Text Book:** Introduction to
Algorithms *by* Udi Manber

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

- Introduce course
- The collapsing compass computer
- Euclid's second proposition through the ages
- Constructive (direct) proofs
- 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)
- Euclid's second proposition cont.
- Case analysis in proofs
- Introduction to induction proofs
- Example 2:
*2-coloring*the faces of an arrangement of lines in the plane - Example 1:
*3-coloring*the vertices of a triangulated polygon - Text: Chapter 1 and Sections 2.1, 2.1 and 2.3.
- Web: 1.2.10.2 - A New Look at Euclid's Second Proposition (Handout)
- Web: 2.1 - Notes on methods of proof
- Web: 2.2 - Notes on how to do proofs
- Web: 1.1.3 - Pythagoras proof applets
- Web: 1.2.1 - Straight-edge-and-compass constructions applet of Francois Labelle
- 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.3 - Classical fallatious proofs

**Lecture 1: Ancient Models of
Computation**

**Lecture 2: Induction Proofs**

- If and only if
- Proofs by contradiction
- The infinitude of primes
- Existence proofs
- Coloring the points of the plane with two colors
- Strong induction: triangulating polygons via diagonal insertion
- Graph theory terminology
- Double induction
- Proof of Euler's formula for connected planr graphs
- Abstract graphs and geometric graphs
- Proximity graphs
- Trees
- Minimal spanning trees
- Relative neighborhood graphs
- Applications of MST to text-line orientation estimation
- Text: 2.4-2.7, 2.11, 2.13-2.14
- Web: 4.1 - Interactive introduction to graph theory
- Web: 4.2 - Introduction to graph theory (Luc Devroye's notes)
- Web: 4.4 - Web Tutorials: Introduction to Graph Theory
- Web: 20.3 - Minimal spanning tree applet
- Web: 4.12 - Euler's theorem
- Web: 20.2 - Art Gallery Theorem (applet)

- Digital models of computation
- Turing machines
- Random access machines
- Ceiling and floor functions
- Big "Oh" notation
- Comparing functions
- L'Hospital's rule
- Little "oh" notation
- Running time of an algorithm
- Worst case
- Average case
- Best case
- Running time: constant, logarithmic, linear, n log n, quadratic, cubic, polynomial, exponential, factorial
- Examples
- Binary search
- Sorting: insertion sort, selection sort, bubble sort, merge sort
- Travelling salesman problem
- Proof that solution must be a simple circuit
- Polygon triangulation in cubic time
- 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.1.2.3 - Two-ears theorem, diagonals and polygon triangulation
- Web: 1.3.1.1 - Turing machine applet
- Web: 4.17.3 - Elastic band approach to TSP applet
- Web: 4.17.4 - Simple polygon counter applet

- Recurrence Relations and Fibonacci sequences
- Algorithms for computing the Fibonacci function
- Exponential - O(2^n)
- Linear - O(n)
- Logarithmic - O(log n)
- Polygon triangulation in quadratic time
- Geoff's algorithm

- Solving the Fibonacci recurrence relation by induction
- Approximately
- Exactly (Binet's formula)
- Divide & conquer recurrence relations
- Merge sort
- The master theorem
- Text: Chapter 3
- Text: 6.4.3 - Merge sort
- Web: 1.4.1 - Recursion (Luc Devroye's class notes)
- Web: 1.4.1.1 - Fibonacci algorithms
- Web: 1.4.1.9 - Proofs of Binet's formula
- Web: 1.4.1.2 - Fibonacci math
- Web: 1.4.1.3 - Fibonacci and nature
- Web: 1.4.1.4 - Fibonacci home page

- Algorithms for computing the Fibonacci function
- Binary search
- The skyline problem in computer graphics
- Analysis of heap-sorting
- Computing the maximum gap in O(n) time with floor functions
- Bucketsort and radix sort
- Bucket sorting real numbers in O(n) expected time
- Text: 5.1 and 5.2 - Polynomial evaluation
- Text: 9.2 - Exponentiation
- Text: 5.6 - The skyline problem (divide and conquer)
- Text: Chapter 6 up to and including 6.4.3
- 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

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

- Priority queues via the
**heap**data structure - Insertion and deletion in heaps in O(log n) time
- Building a heap in O(n) time
- Application to sorting (heapsort)
- Non-crossing Hamiltonians of point sets
- Convex hull algorithm of Rosenberg & Landgridge - O(n^3)
- Monotone simple Hamiltonian circuits in O(n log n) time - The double-comb algorithm
- Star-shaped Hamiltonian circuits in O(n log n) time
- Text: 4.3.2 - Heaps
- Web: 5.6.2 - Heaps (Luc Devroye's class notes)
- Web: 5.6 - Tutorial on heaps
- Web: 19.2.1.4 - Heapsort tutorial
- Text: 6.4.5 - Heapsorting
- Web: 5.6 - Heap applet

**Problem Assignment 4 "due" November
2, 2000**

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

**Data compression:**- Prefix codes
- Minimal prefix codes
- Shannon-Fano coding
- Huffman coding
- Hu-Tucker algorithm with heaps
- Schwartz-Kallick algorithm
**Huffman trees:**- Applications
- Merging sorted files
- Random number generation
**Closest-pair searching:**- In 1-D via divide and conquer in O(n log n) time
- In 2-D via divide and conquer algorithms
- O(n log^2 n)
- O(n log n)
- Text: 6.6 - Data compression
- Web: 5.7.6 - Huffman trees (Luc Devroye's class notes)
- Web: 7.1.3 - Shannon-Fano coding
- Web: 7.1.4 - Huffman coding
- Text: 8.5 - Closest pair searching
- Web: 6.8.1 - Closest-pair searching tutorial
- Web: 5.7.7 and 5.7.8 - Huffman coding applets
- Web: 6.8.1 - Closest-pair applet

- Orthogonal Hamiltonians
- Reconstructing simple polygons from their vertex set
- Testing self-intersections in polygons
- Computing orthogonal-segment intersections via line-sweep technique and balanced search trees
**Closest-pair searching:**- Line-sweep algorithm with (2,4) trees in O(n log n) time
- Text: 8.6 - Orthogonal segment intersections
- Web: 6.7.1 - Projection methods for nearest neighbor search
- Web: 4.2 - Introduction to graphs (Luc Devroye's class notes)
- Web: 6.7.1 - Nearest neighbor search applet

- Basic definitions of graphs
- Data structures for graphs
- Adjacency matrix
- Adjacency lists
- Searching mazes and labyrinths
- Ancient Greek algorithm (Ariadne's thread)
- Gaston Tarry's algorithm (1895)
- Depth-first search in a graph
- Breadth-first search in a graph
- Complexity analysis of DFS and BFS
**Map and graph coloring:**- Planarity
- Proof of non-planarity of K5 using Euler's formula
- Dual graphs
- The four-color theorem and its history
- Induction proof of 5-color theorem
- Algorithm for coloring a plane graph
- Greedy algorithms and least-cost Hamiltonian cycles in graphs
- Hamiltonian cycles in dense graphs (Ore's theorem)
- Prim's minimum spanning tree for graphs
- Text: 4.6 - Adjacency matrix
- Web: 6.3.1 - Depth-first search (Luc Devroye's class notes)
- Web: 6.4 - Breadth-first search (Luc Devroye's class notes)
- Text: 7.3 - Depth-first search and breadth-first search
- Web: 4.16 - Rotating caliper graph
- Text: 8.6 - Intersections of horizontal and vertical segments
- Web: 4.13.1 to 4.13.5 - Map coloring

- 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

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

- Hill climbing algorithms
- Greedy algorithms
- Minimum spanning trees (MST)
- Kruskal's algorithm via heaps
- Prim's algorithm
- Baruvka's algorithm
- Travelling salesman problem
- Nearest neighbor heuristic yields O(log n) times optimal
- Approximation algorithm via MST yields twice optimal
**Selection:**- Via sorting
- Via heaps
- Finding the median of a set of numbers in linear time
- The median of medians algorithm
- 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 and Prim's algorithms tutorial
- Web: 4.17.1 and 4.17.2 - Travelling saleman problem
- Web: 4.17.7 - Twice-optimal approximate TSP algorithm
- 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: 4.11.3 - Kruskal algorithm applet
- Web: 4.17.3 and 4.17.4 - Great applets for travelling salesman problem
- Web: 4.17.6 - Great applet for TSP heuristics
- Web: 5.6 - Selection applet

**Lecture 27: No lecture due to Study Day**