"Computer science is no more about computers than astronomy is about telescopes."
E. W. Dijkstra
Useful General Links
251 -
Godfried Toussaint's Course Topics on the Web
251-Mike Hallet's web page
Virtual Library of Algorithms and Data Structures
Algorithms and Data Structures Research & Reference Material
Algorithms Courses on the WEB
Graph Theory Lessons
David Eppstein's course on algorithms
Algorithms Course at the University of Aberdeen
Specific Course Material for COMP-251
as taught by Godfried Toussaint
Chapter Index:
The Complexity of Algorithms
The Correctness of Algorithms
Linear Data Structures
Graphs
Trees
Searching Algorithms
Plane-Sweep Algorithms
Greedy Algorithms
Divide-and-Conquer Algorithms
On-Line Algorithms
Real-Time Algorithms
Elimination Algorithms
Distributive Algorithms
Prune-and-Search Methods
Linear Programming
Probabilistic Algorithms
Approximation Algorithms
Parallel Algorithms
Numerical Algorithms
Geometric Algorithms
Sequence Comparison
1. The Complexity of Algorithms:
Models of Computation (Old and New)
(1) Knotted Strings, the Abacus and other Models of Computation
Gravity as a Computer:
Computing the Centroid of a Polygon with a Plumbline
Centers of Gravity of Polygons
The Knotted String Computer
Pythagoras' Theorem:
Pythagoras' Theorem
(An award winning proof and interactive Java applet demo)
Animated Proof of the Pythagoream Theorem by M. D. Meyerson
A Hinged Dissection Proof of the Pythagorean Theorem
Other Dissection Proof
s
(with interactive Java applets)
More than forty other proofs of the Pythagorean theorem
The Converse of Pythagoras' Theorem
The Abacus
The Abacus in various number systems
Napier's Bones in Various Bases
The Virtual Museum of Computing
Links to History of Computing
(2) The Straight Edge and Compass
Francois Labelle's Tutorial on the Complexity of Ruler and Compass Constructions
(with interactive Java applet)
GRACE
(A graphical ruler and compass editor)
The straight-edge and compass
Constructive geometry of the Greeks
Geometric constructions
Geometrography and the Lemoine simplicity of geometric constructions
Euclid's Elements
Second Proposition (Java applet)
Euclid of Alexandria
More Euclid on the Web
Relative computing power of models of computation:
The Collapsing Compass
A New Look at Euclid's Second Proposition (
PostScript
) (
PDF
)
The Compass without straight edge (Mohr-Mascheroni)
Heron's Shortest Path via a Line
(with interactive Java applet)
More on Heron's problem and other constrained shortest path problems
(with interactive Java applets)
More about Heron of Alexandria
The Lunes of Hippocrates
More about Hippocrates of Chios
Wonders of Ancient Greek Geometry
(3) Modern Models of Computation
Introduction to Turing machines
Fantastic Turing machine applet!
The Turing Machine and Random Access Machine
(Luc Devroye's class notes)
More about Alan Turing
Ceiling and Floor Functions
Logarithmic functions
The harmonic series
Big "Oh" Notation
(Luc Devroye's class notes)
Basic analysis tools (Goodrich & Tamassia text)
Computability theory
What computers can't do (Turing and the Halting Problem)
(4) The Complexity of Algorithms and Problems:
Recursion
(Luc Devroye's class notes)
Algorithms for computing the Fibonacci function (David Eppstein)
Fibonacci numbers (mathematical properties)
Fibonacci numbers and nature
Fibonacci Home Page
Biography of Leonardo Fibonacci from Pisa
Fibonacci numbers and domino tilings
Vibonacci numbers
Recursion solving applet
Proofs of Binet's formula
Lower Bounds
(Luc Devroye's class notes)
2.
The Correctness of Algorithms (Proof Techniques):
Notes on methods of proof
Notes on how to do proofs
More on proof methods
Classic fallacies
Constructive Proofs:
3-coloring all the points in the plane
Proofs by Contradiction:
Euclid's Proof of the infinitude of prime numbers
Induction Proofs:
The Technique of Proof by Induction
More on induction
Induction Algorithm Design:
Polynomial evaluation
Many nice examples of different types of proofs
On Proofs in Mathematics
How to read proofs
Writing Down Proofs
The Nuts and Bolts of Proofs
Logical systems
Common errors in mathematics
Proofs and proof strategies
3.
Linear Data Structures:
Linear Data Structures (Luc Devroye's class notes)
University of Aberdeen Notes
Stack
Queue
Array
Linked list
Priority Queue
Deque
Data Structure Animations
4.
Graphs:
Interactive Introduction to Graph Theory
Graph Theory Tutorials (Euler and Hamilton circuits, Coloring, Spanning and Steiner Trees)
Applied Graph Theory Course
Introduction to Graphs (Luc Devroye's Notes)
Graph isomorphism
Graph planarity
Graph data structures:
Adjacency lists
Adjacency matrices
Doubly-Connected-Edge-List (DCEL)
Graph Algorithm Animations
Graph Theory Web Tutorials
Introduction to graph theory
Euler and Hamiltonian circuits
Graph theory
Graph Theory and Enumeration
Paths and Circuits
Algorithm for Constructing an Eulerian Circuit
Euler Tours: Fleury's Algorithm
Applet for Euler tours
Ethan's notes
More on Fleury's algorithm
(postscript)
Great tutorial on Euler tours and Fleury's algorithm
Graph Glossary
Proximity graphs:
Minimal spanning trees (Luc Devroye's class notes)
David Eppstein's class notes
Java applet of Euclidean minimal spanning tree
The Relative Neighborhood Graph
Hamiltonian Tours:
Hamiltonian paths in tournaments
Hamiltonian cycles in dense graphs:
Ore's Theorem
Backward induction proof
Dirac's Theorem
Posa's proof of Dirac's theorem by contradiction
The Hamiltonian Page
Great tutorial on Hamilton circuits
Sufficient conditions for Hamiltonian cycles
Hamiltonian circuits of point sets with specific properties (polygonizations)
Minimum Spanning Trees:
Minimum spanning trees (Luc Devroye's class notes)
Minimum spanning tree algorithms: Kruskal, Prim & Baruvka (David Eppstein's class notes)
Minimum Spanning Trees (Steve Skiena)
Kruskal's Algorithm with applet
Least Cost Networks: Kruskal's Algorithm
Another applet for Kruskal's algorithm
Prim's algorithm with pointers and appl
et
Prim's algorithm with adjacency matrices and applet
Baruvka's Algorithm (David Mount's notes) PostScript file
19 Proofs of Euler's Theorem
Graph and Map Coloring:
Graph and map coloring
Dual Graphs
Graph Coloring
Map coloring WEB tutorial
The scheduling problem
Two-Colorable Maps
Applications of graph coloring
The four-color theorem
History of the problem
A new proof of the 4-color theorem
The Graph Coloring Page
David Eppstein's Coloring Page
The Five-Color Theorem for planar graphs
The Konigsberg Bridge Problem
Planarity and the Torus
The rotating-caliper graph
The Travelling Salesman Problem:
An introduction to the TSP problem
A pictorial history of the TSP problem
An elastic-band approach to the TSP problem (JAVA applet)
The Polygon Counting Applet
The Travelling Salesman Home Page
Different heuristics for the TSP problem
Approximate TSP algorithm via MST yields twice optimal tour
Graph drawing
5.
Trees:
Introduction to Trees:
Luc Devroye's class notes with tree traversal (applet)
Tree traversals (preorder, inorder and postorder)
Introduction to trees (Goodrich & Tamassia text)
Tree Algorithm Animations
Binary trees.
More information on binary trees.
Logarithms
Binary search trees (Luc Devroye's class notes)
Quad trees
Balanced trees:
Tutorial on 2-4 trees
2-4 Trees
(also AVL and Red-Black trees)
Heaps:
Tutorial on heaps with applet
Heaps (Luc Devroye's class notes)
Huffman trees and data compression:
Data compression
Introduction to Data Compression
Fundamental Concepts
Shannon-Fano Coding
More about
Claude Shannon
The Significance of Claude Shannon's Work
Pictures of Shannon
More about Robert Fano
Huffman coding
Optimality of Huffman codes
Huffman trees and applications (Luc Devroye's course notes)
Huffman coding applet
Huffman coding tutorial and another applet
More About
David Huffman
David Huffman dies at 74
Geometric paper folding
Lempel-Ziv Compression (Luc Devroye's notes)
Lempel-Ziv Data Compression Schemes
More about Abraham Lempel
Animation of Welch variant of Lempel-Ziv compression
Text compression (Steve Skiena)
Morse Code
Morse Code basics
The International Morse Code
More about Samuel Morse
Introduction to probability and information theory
Entropy
Markov models of natural language (monkeys and typewriters)
The Shannonizer
Spelling correction programs.
Spell checkers are wonderful but
.....
Decision trees
Game trees:
Play
Checkers
with
Chinook
(The World Champion)
Play
Othello
with
Keyano and other programs
Play
Chess
with
The Turk
Game trees
Other Games, Toys and Puzzles
Clever games for clever people
Tetris
6.
Searching Algorithms:
Sequential search
Binary search:
Creating Binary Search Trees
(Java applet)
Searching in a Binary Search Tree
(Java applet demo)
The Number-Guessing Game
Maze searching:
Depth-first search (Luc Devroye's class notes)
DFS applet
A Maze Game (interactive Java applet)
3D Mazes in Java
The mathematics of mazes
Theseus and the Minotaur
The Minotaur Legend
The mad maze of Theseus and the Minotaur
THE MYTH OF THE MINOTAUR
Breadth-first search (Luc Devroye's class notes)
BSF applet
BSF and DFS (David Eppstein's class notes)
Graph traversal (Goodrich & Tamassia text)
Interpolation search
Orthogonal range searching
Nearest Neighbor Search:
Projection methods
Access Trees
Voronoi diagram methods
Closest-pair searching in the plane
Tutorial with applets
Animation applet of divide-and-conquer algorithm
!
Closest pairs (Goodrich & Tamassia text)
Branch-and-bound
The A* algorithm
7.
Plane-Sweep Algorithms:
Closest pair problem
Line segment intersections
8.
Greedy Algorithms, Hill-Climbing, and Diameter Algorithms:
Greedy algorithms
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
Complexity, convexity and unimodality
Hill climbing algorithms
Quick sort
Quick hull
9.
Divide & Conquer Algorithms:
Sorting
Finding closest pair
Convex hulls
10.
On-Line Algorithms:
Convex hulls of polygons
Convex hulls of points
11.
Real-Time Algorithms:
Convex hulls of polygons
Convex hulls of points
12.
Elimination Methods:
Convex hulls of point sets
13.
Distributive Methods:
Distributive sorting
Bucketing methods
Bucket sort
Radix sort
14.
Prune & Search Methods:
The geometric series
Ear-cutting and polygon triangulation
Linear time median finding and selection (Luc Devroye's course notes)
Linear time median finding and selection (David Eppstein's course notes)
Convex hulls
15.
Linear Programming:
Introduction to Linear Programming and the Simplex Algorithm
Megiddo's linear time algorithm
Linear programming and optimization problems
(with Java applet)
16.
Probabilistic Algorithms:
Randomization
Monte-Carlo Algorithms
Las-Vegas Algorithms
Randomized convex hull
Probability and Random Number Generation
Visualizing randomness
More on generating random numbers
Monte Carlo Simulation:
Simulating random knots in a lattice
Self-avoiding walks in polymer physics and molecular biology
Polymer Java applet
Protein folding
Bouncing balls
Buffon's Needle
Rolling Dice
17.
Approximation Algorithms:
Approximation algorithms
The vertex-cover problem
Approximation algorithm
The bin-packing problem
The travelling salesman problem
18.
Parallel Algorithms:
Parallel Algorithm Animations
Real and Artificial Neurons
Threshold logic units.
Dr. Gurney's course on neural networks.
Perceptrons & neural network
s (learning machines).
Sharpening, the Laplacian and lateral inhibition in neural networks
(PDF)
19. Numerical Algorithms:
19.1 Numbers
What is a Number?
More on irrational numbers
Two proofs of the irrationality of the diagonal of the unit cube
Elementary number theory
Numbers: Real, rational, integer and binary numbers (bits and bytes)
Floating Point Numbers
Newton's Method:
Introduction to Newton's method
Computing approximate square roots with Newton's Method
The Euclidean factorization algorithm
Prime Numbers:
Prime numbers (FAQ's)
Historical introduction to primes
The Prime Number Home Page
Euclid's Proof of the Infinitude of Primes
Prime Number Generator
Prime Curios!
19.2 Sorting Algorithms
Sorting Numbers:
Sorting Algorithm Animations
Selection sort tutorial
Bubble sort tutorial
Heap sort tutorial
Merge sort tutorial (Divide and Conquer)
Bucket-Sorting and Floor Functions (
PostScript file
), (
PDF file
)
Quicksort with nice applet!
(in place version and comparison to heapsort)
Expected analysis of randomized quicksort
Random binary search trees and Quicksort
Selection and order statistics
More Sorting Algorithm Animations
(Applets also sort your own set of numbers!)
Sorting Code
20. Geometric Algorithms:
Polygon Triangulation:
History of Triangulation Algorithms
Ears and Mouths of Polygons:
Ian Garton's Tutorial on cutting ears and stuffing mouths
(with interactive Java applets)
Simple polygons
have
ears
and
mouths
Meisters' Two-Ears Theorem
More about Gary Meisters
The one-mouth theorem:
Ian Garton's Tutorial
PostScript file
Diagonal insertion
Prune-and-Search:
Finding an ear in linear time (PostScript)
Finding an ear in linear time (HTML)
The Graham Scan triangulates simple polygons
(PostScript)
Fast Polygon Triangulation in Practice:
Efficient polygon triangulation algorithms.
Includes counter-examples to many published algorithms. (PostScript)
The Art-Gallery Theorem (with interactive applet)
The Minimal Spanning Tree applet
Geometric Algorithm Animations
Polygons: crossing, simple and convex.
Polygonizing Sets of Points
:
Uniqueness of orthogonal connect-the-dots
The area of a polygon.
Determining if a point is inside a polygon.
Smoothing polygons and polygonal waveforms.
Convex Hulls:
Rosenberg & Landgridge algorithm (extreme edges)
Convex hulls, segment intersections and closest pairs (Goodrich & Tamassia text)
Convex hulls in 2 and 3 dimensions
(interactive Java demos)
The Gift-Wrapping Algorithm
(Jarvis' March)
The Quick-Hull Algorithm
(stretching an elastic band)
Divide & Conquer (nice tutorial) and other methods
Divide & Conquer (applet)
The Graham Scan Algorithm
3-Coins Algorithm Tutorial (Greg Aloupis and Bohdan Kaluzny)
More convex hull animations
Voronoi Diagrams:
Introduction to Voronoi diagrams
Great Voronoi diagram applet
21.
Sequence Comparison:
Edit distance with dynamic programming (with applet)
Fast Fourier Transforms
22.
Computational Aspects of Musical Rhythm:
Neclaces, Bracelets, Homometric Rhythms, Flat Rhythms, Deep Rhythms, The Hexachordal Theorem and Patterson's Theorems (more proofs by induction).
21.
Arithmetic Operations:
Addition, Multiplication and Fast Fourier Transforms