Discrete Mathematics

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

at Tufts University taught by Godfried Toussaint

Chapter Index:

### 2.  Proof Techniques:

1. Notes on methods of proof
2. Classic fallacies
3. Constructive Proofs:
5. Induction Proofs:
6. More on Proofs:
3. Graphs:
1. Graph Theory lessons
2. Graph isomorphism
3. Graph planarity
4. Graph data structures:
5. Graph Theory Web Tutorials
6. Proximity graphs:
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
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:
9. 19 Proofs of Euler's Theorem
10. Graph and Map Coloring:
11. The Konigsberg Bridge Problem
12. Planarity and the Torus
13. The rotating-caliper graph
14. The Travelling Salesman Problem:
15. Graph drawing
4. Trees:
1. Introduction to Trees:
2. Tree Algorithm Animations
3. Binary trees.
5. Balanced trees:
1. Tutorial on 2-4 trees
2. 2-4 Trees (also AVL and Red-Black trees)
6. Heaps:
7. Huffman trees and data compression:
1. Data compression
2. Text compression (Steve Skiena)
3. Morse Code
4. Introduction to probability and information theory
5. Entropy
6. Markov models of natural language (monkeys and typewriters)
7. Spelling correction programs.
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
5. Greedy Methods and Hill-Climbing: 6.  The Geometric Series and Prune & Search Methods: 7. Discrete Optimization and Linear Programming: 8.  Probability:
1. Randomization
2. Monte-Carlo Methods
3. Las-Vegas Methods
4. Randomized convex hull
5. Probability and Random Number Generation
6. Monte Carlo Simulation:
9.  Approximation Methods:

## 11.1 Numbers

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
4. The one-mouth theorem:
3. Diagonal insertion
4. Prune-and-Search:
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:
7. The area of a polygon.
8. Determining if a point is inside a polygon.
9. Smoothing polygons and polygonal waveforms.
10. Convex Hulls:
11. Voronoi Diagrams:
13.  Sequence Comparison: 14.  Discrete Mathematical Aspects of Musical Rhythm: 15.  Arithmetic Operations and Fast Fourier Transforms: