"Computer science is no more about computers than astronomy is about telescopes."

E. W. Dijkstra

1. 251 - Godfried Toussaint's Course Topics on the Web
2. 251-Mike Hallet's web page
3. Virtual Library of Algorithms and Data Structures
4. Algorithms and Data Structures Research & Reference Material
5. Algorithms Courses on the WEB
6. Graph Theory Lessons
7. David Eppstein's course on algorithms
8. Algorithms Course at the University of Aberdeen

Specific Course Material for COMP-251
as taught by Godfried Toussaint

1. The Complexity of Algorithms
2. The Correctness of Algorithms
3. Linear Data Structures
4. Graphs
5. Trees
6. Searching Algorithms
7. Plane-Sweep Algorithms
8. Greedy Algorithms
9. Divide-and-Conquer Algorithms
10. On-Line Algorithms
11. Real-Time Algorithms
12. Elimination Algorithms
13. Distributive Algorithms
14. Prune-and-Search Methods
15. Linear Programming
16. Probabilistic Algorithms
17. Approximation Algorithms
18. Parallel Algorithms
19. Numerical Algorithms
20. Geometric Algorithms
21. Sequence Comparison

1. The Complexity of Algorithms:

Models of Computation (Old and New)

(1) Knotted Strings, the Abacus and other Models of Computation

1. Gravity as a Computer:
1. Computing the Centroid of a Polygon with a Plumbline
2. Centers of Gravity of Polygons
2. The Knotted String Computer
3. Pythagoras' Theorem:
1. Pythagoras' Theorem (An award winning proof and interactive Java applet demo)
2. Animated Proof of the Pythagoream Theorem by M. D. Meyerson
3. A Hinged Dissection Proof of the Pythagorean Theorem
4. Other Dissection Proof s (with interactive Java applets)
5. More than forty other proofs of the Pythagorean theorem
6. The Converse of Pythagoras' Theorem
4. The Abacus
1. The Abacus in various number systems
5. Napier's Bones in Various Bases
6. The Virtual Museum of Computing
7. Links to History of Computing

(2) The Straight Edge and Compass

1. Francois Labelle's Tutorial on the Complexity of Ruler and Compass Constructions (with interactive Java applet)
2. GRACE (A graphical ruler and compass editor)
3. The straight-edge and compass
4. Constructive geometry of the Greeks
5. Geometric constructions
6. Geometrography and the Lemoine simplicity of geometric constructions
7. Euclid's Elements
1. Second Proposition (Java applet)
8. Euclid of Alexandria
9. More Euclid on the Web
10. Relative computing power of models of computation:
1. The Collapsing Compass
2. A New Look at Euclid's Second Proposition (PostScript) (PDF)
3. The Compass without straight edge (Mohr-Mascheroni)
11. Heron's Shortest Path via a Line (with interactive Java applet)
1. More on Heron's problem and other constrained shortest path problems (with interactive Java applets)
2. More about Heron of Alexandria
12. The Lunes of Hippocrates
1. More about Hippocrates of Chios
13. Wonders of Ancient Greek Geometry

(3) Modern Models of Computation

1. Introduction to Turing machines
1. Fantastic Turing machine applet!
2. The Turing Machine and Random Access Machine (Luc Devroye's class notes)
1. More about Alan Turing
2. Ceiling and Floor Functions
3. Logarithmic functions
4. The harmonic series
3. Big "Oh" Notation (Luc Devroye's class notes)
4. Basic analysis tools (Goodrich & Tamassia text)
5. Computability theory
1. What computers can't do (Turing and the Halting Problem)
(4) The Complexity of Algorithms and Problems:
1. Recursion (Luc Devroye's class notes)
1. Algorithms for computing the Fibonacci function (David Eppstein)
2. Fibonacci numbers (mathematical properties)
3. Fibonacci numbers and nature
4. Fibonacci Home Page
5. Biography of Leonardo Fibonacci from Pisa
6. Fibonacci numbers and domino tilings
7. Vibonacci numbers
8. Recursion solving applet
9. Proofs of Binet's formula
2. Lower Bounds (Luc Devroye's class notes)

2.  The Correctness of Algorithms (Proof Techniques):

1. Notes on methods of proof
2. Notes on how to do proofs
3. More on proof methods
4. Classic fallacies
5. Constructive Proofs:
1. 3-coloring all the points in the plane
6. Proofs by Contradiction:
1. Euclid's Proof of the infinitude of prime numbers
7. Induction Proofs:
1. The Technique of Proof by Induction
2. More on induction
8. Induction Algorithm Design:
1. Polynomial evaluation
9. Many nice examples of different types of proofs
10. On Proofs in Mathematics
11. How to read proofs
12. Writing Down Proofs
13. The Nuts and Bolts of Proofs
14. Logical systems
15. Common errors in mathematics
16. Proofs and proof strategies

1. Linear Data Structures (Luc Devroye's class notes)
2. University of Aberdeen Notes
1. Stack
2. Queue
3. Array
4. Linked list
5. Priority Queue
6. Deque
3. Data Structure Animations

1. Interactive Introduction to Graph Theory
1. Graph Theory Tutorials (Euler and Hamilton circuits, Coloring, Spanning and Steiner Trees)
2. Applied Graph Theory Course
2. Introduction to Graphs (Luc Devroye's Notes)
3. Graph isomorphism
4. Graph planarity
5. Graph data structures:
1. Adjacency lists
2. Adjacency matrices
3. Doubly-Connected-Edge-List (DCEL)
6. Graph Algorithm Animations
7. Graph Theory Web Tutorials
1. Introduction to graph theory
2. Euler and Hamiltonian circuits
3. Graph theory
4. Graph Theory and Enumeration
5. Paths and Circuits
6. Algorithm for Constructing an Eulerian Circuit
7. Euler Tours: Fleury's Algorithm
1. Applet for Euler tours
2. Ethan's notes
   
8. More on Fleury's algorithm (postscript)
9. Great tutorial on Euler tours and Fleury's algorithm
8. Graph Glossary
9. Proximity graphs:
1. Minimal spanning trees (Luc Devroye's class notes)
1. David Eppstein's class notes
2. Java applet of Euclidean minimal spanning tree
2. The Relative Neighborhood Graph
10. Hamiltonian Tours:
1. Hamiltonian paths in tournaments
2. Hamiltonian cycles in dense graphs:
1. Ore's Theorem
1. Backward induction proof
3. Dirac's Theorem
1. Posa's proof of Dirac's theorem by contradiction
4. The Hamiltonian Page
5. Great tutorial on Hamilton circuits
6. Sufficient conditions for Hamiltonian cycles
7. Hamiltonian circuits of point sets with specific properties (polygonizations)
11. Minimum Spanning Trees:
1. Minimum spanning trees (Luc Devroye's class notes)
2. Minimum spanning tree algorithms: Kruskal, Prim & Baruvka (David Eppstein's class notes)
3. Minimum Spanning Trees (Steve Skiena)
4. Kruskal's Algorithm with applet
1. Least Cost Networks: Kruskal's Algorithm
2. Another applet for Kruskal's algorithm
5. Prim's algorithm with pointers and applet
6. Prim's algorithm with adjacency matrices and applet
7. Baruvka's Algorithm (David Mount's notes) PostScript file
12. 19 Proofs of Euler's Theorem
13. Graph and Map Coloring:
1. Graph and map coloring
2. Dual Graphs
3. Graph Coloring
4. Map coloring WEB tutorial
5. The scheduling problem
6. Two-Colorable Maps
7. Applications of graph coloring
8. The four-color theorem
1. History of the problem
2. A new proof of the 4-color theorem
9. The Graph Coloring Page
10. David Eppstein's Coloring Page
11. The Five-Color Theorem for planar graphs
14. The Konigsberg Bridge Problem
15. Planarity and the Torus
16. The rotating-caliper graph
17. The Travelling Salesman Problem:
1. An introduction to the TSP problem
2. A pictorial history of the TSP problem
3. An elastic-band approach to the TSP problem (JAVA applet)
4. The Polygon Counting Applet
5. The Travelling Salesman Home Page
6. Different heuristics for the TSP problem
7. Approximate TSP algorithm via MST yields twice optimal tour
18. Graph drawing

1. Introduction to Trees:
1. Luc Devroye's class notes with tree traversal (applet)
2. Tree traversals (preorder, inorder and postorder)
3. Introduction to trees (Goodrich & Tamassia text)
2. Tree Algorithm Animations
3. Binary trees.
1. More information on binary trees.
2. Logarithms
3. Binary search trees (Luc Devroye's class notes)
4. Quad trees
5. Balanced trees:
1. Tutorial on 2-4 trees
2. 2-4 Trees (also AVL and Red-Black trees)
6. Heaps:
1. Tutorial on heaps with applet
2. Heaps (Luc Devroye's class notes)
7. Huffman trees and data compression:
1. Data compression
1. Introduction to Data Compression
2. Fundamental Concepts
3. Shannon-Fano Coding
1. More about Claude Shannon
2. The Significance of Claude Shannon's Work
3. Pictures of Shannon
4. More about Robert Fano
4. Huffman coding
5. Optimality of Huffman codes
6. Huffman trees and applications (Luc Devroye's course notes)
7. Huffman coding applet
8. Huffman coding tutorial and another applet
9. More About David Huffman
1. David Huffman dies at 74
2. Geometric paper folding
10. Lempel-Ziv Compression (Luc Devroye's notes)
11. Lempel-Ziv Data Compression Schemes
1. More about Abraham Lempel
2. Animation of Welch variant of Lempel-Ziv compression
2. Text compression (Steve Skiena)
3. Morse Code
1. Morse Code basics
2. The International Morse Code
3. More about Samuel Morse
4. Introduction to probability and information theory
5. Entropy
6. Markov models of natural language (monkeys and typewriters)
1. The Shannonizer
7. Spelling correction programs.
1. Spell checkers are wonderful but .....
8. Decision trees
9. Game trees:
1. Play Checkers with Chinook (The World Champion)
2. Play Othello with Keyano and other programs
3. Play Chess with The Turk
4. Game trees
5. Other Games, Toys and Puzzles
6. Clever games for clever people
1. Tetris

1. Sequential search
2. Binary search:
1. Creating Binary Search Trees (Java applet)
2. Searching in a Binary Search Tree (Java applet demo)
3. The Number-Guessing Game
3. Maze searching:
1. Depth-first search (Luc Devroye's class notes)
1. DFS applet
2. A Maze Game (interactive Java applet)
3. 3D Mazes in Java
4. The mathematics of mazes
5. Theseus and the Minotaur
6. The Minotaur Legend
7. The mad maze of Theseus and the Minotaur
8. THE MYTH OF THE MINOTAUR
4. Breadth-first search (Luc Devroye's class notes)
1. BSF applet
2. BSF and DFS (David Eppstein's class notes)
3. Graph traversal (Goodrich & Tamassia text)
5. Interpolation search
6. Orthogonal range searching
7. Nearest Neighbor Search:
1. Projection methods
2. Access Trees
3. Voronoi diagram methods
8. Closest-pair searching in the plane
1. Tutorial with applets
2. Animation applet of divide-and-conquer algorithm!
3. Closest pairs (Goodrich & Tamassia text)
9. Branch-and-bound
10. The A* algorithm

1. Closest pair problem
2. Line segment intersections

1. Greedy algorithms
2. The Rotating Calipers
      1. The Rotating Caliper Page of Hormoz Pirzadeh (with an awsome Java applet!)
      2. The Reuleaux triangle (Eric's Treasure Trove)
      3. The Reuleaux triangle (The Geometry Junkyard
   
3. Complexity, convexity and unimodality
4. Hill climbing algorithms
5. Quick sort
6. Quick hull

1. Sorting
2. Finding closest pair
3. Convex hulls

1. Convex hulls of polygons
2. Convex hulls of points

1. Convex hulls of polygons
2. Convex hulls of points

1. Convex hulls of point sets

1. Distributive sorting
2. Bucketing methods
1. Bucket sort
2. Radix sort

1. The geometric series
2. Ear-cutting and polygon triangulation
3. Linear time median finding and selection (Luc Devroye's course notes)
4. Linear time median finding and selection (David Eppstein's course notes)
5. Convex hulls

1. Introduction to Linear Programming and the Simplex Algorithm
2. Megiddo's linear time algorithm
3. Linear programming and optimization problems (with Java applet)

1. Randomization
2. Monte-Carlo Algorithms
3. Las-Vegas Algorithms
4. Randomized convex hull
5. Probability and Random Number Generation
1. Visualizing randomness
2. More on generating random numbers
6. Monte Carlo Simulation:
1. Simulating random knots in a lattice
2. Self-avoiding walks in polymer physics and molecular biology
1. Polymer Java applet
3. Protein folding
4. Bouncing balls
5. Buffon's Needle
6. Rolling Dice

1. Approximation algorithms
2. The vertex-cover problem
1. Approximation algorithm
3. The bin-packing problem
4. The travelling salesman problem

1. Parallel Algorithm Animations
2. Real and Artificial Neurons
3. Threshold logic units.
4. Dr. Gurney's course on neural networks.
5. Perceptrons & neural networks (learning machines).
6. Sharpening, the Laplacian and lateral inhibition in neural networks (PDF)

19. Numerical Algorithms:

19.1 Numbers

1. What is a Number?
• More on irrational numbers
• Two proofs of the irrationality of the diagonal of the unit cube
2. Elementary number theory
3. Numbers: Real, rational, integer and binary numbers (bits and bytes)
4. Floating Point Numbers
5. Newton's Method:
1. Introduction to Newton's method
2. Computing approximate square roots with Newton's Method
6. The Euclidean factorization algorithm
7. Prime Numbers:
1. Prime numbers (FAQ's)
2. Historical introduction to primes
3. The Prime Number Home Page
4. Euclid's Proof of the Infinitude of Primes
5. Prime Number Generator
6. Prime Curios!

1. Sorting Numbers:
1. Sorting Algorithm Animations
2. Selection sort tutorial
3. Bubble sort tutorial
4. Heap sort tutorial
5. Merge sort tutorial (Divide and Conquer)
6. Bucket-Sorting and Floor Functions (PostScript file), (PDF file)
7. Quicksort with nice applet! (in place version and comparison to heapsort)
8. Expected analysis of randomized quicksort
9. Random binary search trees and Quicksort
2. Selection and order statistics
3. More Sorting Algorithm Animations (Applets also sort your own set of numbers!)
4. Sorting Code

1. Polygon Triangulation:
1. History of Triangulation Algorithms
2. Ears and Mouths of Polygons:
1. Ian Garton's Tutorial on cutting ears and stuffing mouths (with interactive Java applets)
2. Simple polygons have ears and mouths
3. Meisters' Two-Ears Theorem
1. More about Gary Meisters
4. The one-mouth theorem:
1. Ian Garton's Tutorial
2. PostScript file
3. Diagonal insertion
4. Prune-and-Search:
1. Finding an ear in linear time (PostScript)
2. Finding an ear in linear time (HTML)
5. The Graham Scan triangulates simple polygons (PostScript)
6. Fast Polygon Triangulation in Practice:
1. Efficient polygon triangulation algorithms. Includes counter-examples to many published algorithms. (PostScript)
2. The Art-Gallery Theorem (with interactive applet)
3. The Minimal Spanning Tree applet
4. Geometric Algorithm Animations
5. Polygons: crossing, simple and convex.
6. Polygonizing Sets of Points:
1. Uniqueness of orthogonal connect-the-dots
7. The area of a polygon.
8. Determining if a point is inside a polygon.
9. Smoothing polygons and polygonal waveforms.
10. Convex Hulls:
1. Rosenberg & Landgridge algorithm (extreme edges)
2. Convex hulls, segment intersections and closest pairs (Goodrich & Tamassia text)
3. Convex hulls in 2 and 3 dimensions (interactive Java demos)
4. The Gift-Wrapping Algorithm (Jarvis' March)
5. The Quick-Hull Algorithm (stretching an elastic band)
6. Divide & Conquer (nice tutorial) and other methods
7. Divide & Conquer (applet)
8. The Graham Scan Algorithm
9. 3-Coins Algorithm Tutorial (Greg Aloupis and Bohdan Kaluzny)
10. More convex hull animations
11. Voronoi Diagrams:
1. Introduction to Voronoi diagrams
2. Great Voronoi diagram applet

1. Edit distance with dynamic programming (with applet)
2. Fast Fourier Transforms
   

1. Neclaces, Bracelets, Homometric Rhythms, Flat Rhythms, Deep Rhythms, The Hexachordal Theorem and Patterson's Theorems (more proofs by induction).

1. Addition, Multiplication and Fast Fourier Transforms
   

Teaching Activities Homepage