Discrete Mathematics

"The Way begets one; one begets two; two begets three; three begets the myriad creatures." - Lao Tse



Additional Reference Material for COMP-22

at Tufts University taught by Godfried Toussaint


Chapter Index:
  1. Complexity
  2. Proof Techniques
  3. Graphs
  4. Trees
  5. Greedy Methods and Hill Climbing
  6. The Geometric Series and Prune-and-Search Methods
  7. Discrete Optimization and Linear Programming
  8. Probability
  9. Approximation Methods
  10. Number Theory
  11. Geometry
  12. Sequence Comparison
  13. Discrete Mathematical Aspects of Musical Rhythm
  14. Arithmetic Operations and Fast Fourier Transforms

1. Complexity:

2.  Proof Techniques:

  1. Notes on methods of proof
  2. Classic fallacies
  3. Constructive Proofs:
    1. 3-coloring all the points in the plane
  4. Proofs by Contradiction:
    1. Euclid's Proof of the infinitude of prime numbers
  5. Induction Proofs:
    1. The Technique of Proof by Induction
    2. More on induction
  6. More on Proofs:
    1. On proofs in mathematics
    2. How to read proofs
    3. Logical systems
    4. Common errors in proofs
    5. Proofs and proof strategies
3. Graphs:
  1. Graph Theory lessons
  2. Graph isomorphism
  3. Graph planarity
  4. Graph data structures:
    1. Adjacency matrices
  5. Graph Theory Web Tutorials
    1. Introduction to graph theory
    2. Graph theory
      1. Applet for Euler tours
      2. Ethan's notes
    3. More on Fleury's algorithm (postscript)
    4. Great tutorial on Euler tours and Fleury's algorithm
  6. Proximity graphs:
    1. David Eppstein's class notes
    2. Java applet of Euclidean minimal spanning tree
    3. The Relative Neighborhood Graph
  7. 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)
  8. Minimum Spanning Trees:
    1. Minimum spanning tree algorithms: Kruskal, Prim & Baruvka (David Eppstein's class notes)
    2. Minimum Spanning Trees (Steve Skiena)
    3. Kruskal's Algorithm with applet
      1. Least Cost Networks: Kruskal's Algorithm
      2. Another applet for Kruskal's algorithm
    4. Prim's algorithm with pointers and applet
    5. Prim's algorithm with adjacency matrices and applet
    6. Baruvka's Algorithm (David Mount's notes) PostScript file
  9. 19 Proofs of Euler's Theorem
  10. 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
  11. The Konigsberg Bridge Problem
  12. Planarity and the Torus
  13. The rotating-caliper graph
  14. 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
  15. Graph drawing
4. Trees:
  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
  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
  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 coding applet
      7. Huffman coding tutorial and another applet
      8. More About David Huffman
        1. David Huffman dies at 74
        2. Geometric paper folding
      9. Lempel-Ziv Compression (Luc Devroye's notes)
      10. 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
5. Greedy Methods and Hill-Climbing:
  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. Convexity
  4. Unimodality
  5. Symmetry
6.  The Geometric Series and Prune & Search Methods:
  1. The geometric series
  2. Ear-cutting and polygon triangulation
7. Discrete Optimization and Linear Programming:
  1. Introduction to Linear Programming and the Simplex Method
  2. Linear programming and optimization problems (with Java applet)
8.  Probability:
  1. Randomization
  2. Monte-Carlo Methods
  3. Las-Vegas Methods
  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
9.  Approximation Methods:
  1. Approximation methods
  2. The vertex-cover problem
    1. Approximate solution
  3. The bin-packing problem
  4. The travelling salesman problem

11. Number Theory:

11.1 Numbers

  1. What is a Number?
  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!
11.2 Sorting
  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
12. Geometry:
  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
      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
13.  Sequence Comparison:
  1. Edit distance with dynamic programming (with applet)
  2. Fast Fourier Transforms
14.  Discrete Mathematical Aspects of Musical Rhythm:
  1. Neclaces, Bracelets, Homometric Rhythms, Flat Rhythms, Deep Rhythms, The Hexachordal Theorem and Patterson's Theorems (more proofs by induction).
15.  Arithmetic Operations and Fast Fourier Transforms:
  1. Addition, Multiplication and Fast Fourier Transforms