Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of AlgorithmsThe initial French version of this text was a series of expository lectures that were given at the University of Montreal in November 1975. The book uses the appealing theory of stable marriage to introduce and illustrate a variety of important concepts and techniques of computer science and mathematics: data structures, control structures, combinatorics, probability, analysis, algebra, and especially the analysis of algorithms. The presentation is elementary, and the topics are interesting to nonspecialists. The theory is quite beautiful and developing rapidly. Exercises with answers, an annotated bibliography, and research problems are included. The text would be appropriate as supplementary reading for undergraduate research seminars or courses in algorithmic analysis and for graduate courses in combinatorial algorithms, operations research, economics, or analysis of algorithms. Donald E. Knuth was this year's recipient of the prestigious Kyoto Award in the Advanced Technology category for his tremendous contributions to the development of 20th century computer sciences through both research and education. The Kyoto Award is Japan's highest private award for lifetime achievement. |
Contents
Generalization to the problem of admitting n students to m | 4 |
Coupon Collecting | 17 |
Application to the Shortest | 25 |
Searching a Table by Hashing Mean Behavior of | 37 |
Implementing the Fundamental Algorithm | 45 |
Research Problems | 55 |
| 67 | |
Appendix B Solutions to Exercises | 71 |
Other editions - View all
Common terms and phrases
Ajak amnesiac analysis of algorithms begin best choice remaining Chebyshev's inequality clock solitaire coupon-collector's problem D E A B C Dijkstra algorithm discrete random variable Distances from Québec distributive lattice double hashing E(RA example Exercises of Lecture exists a stable fiancé fundamental algorithm goto graph hashing incomplete lists integer Knuth last choice Latin square lattice least favorable list of preferences married matching containing Aa matrices requiring mean number E(N number of boxes number of proposals number of redundant number of steps obtain a stable operation optimal solution order of preference permutation preference list preference matrix print the stable probability mass function problem of stable PROOF random variable redundant proposals result shortest distance shortest path spouse stable marriage stable matching containing stable solution stack structure suitor suppose theorem theory total number trial couple Trois-Rivières Université de Montréal upper bound X's list