CRM Proceedings & Lecture Notes
Volume: 10;
1997;
74 pp;
Softcover
MSC: Primary 68;
Secondary 05; 90
Print ISBN: 978-0-8218-0603-6
Product Code: CRMP/10
List Price: $25.00
AMS Member Price: $20.00
MAA Member Price: $22.50
Electronic ISBN: 978-1-4704-3924-8
Product Code: CRMP/10.E
List Price: $25.00
AMS Member Price: $20.00
MAA Member Price: $22.50
Supplemental Materials
Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms
Share this pageDonald E. Knuth
A co-publication of the AMS and Centre de Recherches Mathématiques
“This is a very stimulating book!”
—N. G. de Bruijn
“This short book will provide extremely enjoyable reading to
anyone with an interest in discrete mathematics and algorithm
design.”
—Mathematical Reviews
“This book is an excellent (and enjoyable) means of sketching a
large area of computer science for specialists in other fields: It
requires little previous knowledge, but expects of the reader a degree
of mathematical facility and a willingness to participate. It is
really neither a survey nor an introduction; rather, it is a paradigm,
a fairly complete treatment of a single example used as a synopsis of
a larger subject.”
—SIGACT News
“Anyone would enjoy reading this book. If one had to learn French
first, it would be worth the effort!”
—Computing Reviews
The above citations are taken from reviews of the initial French
version of this text—a series of seven expository lectures that
were given at the University of Montreal in November of 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 is one of the most prominent figures of modern computer
science. His works in The Art of Computer Programming are classic. He is also
renowned for his development of &tex; and METAFONT. In 1996, Knuth won the
prestigious Kyoto Prize, considered to be the nearest equivalent to a Nobel
Prize in computer science.
Titles in this series are co-published with the Centre de Recherches Mathématiques.
Readership
Advanced undergraduates, graduate students, and researchers interested in mathematical patterns.
Table of Contents
Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms
- Cover Cover11
- Title page iii4
- Dedication v6
- Contents vii8
- List of figures x11
- Foreword to the original french edition xi12
- Translator’s note xiii14
- Lecture 1. Introduction, definitions, and examples 116
- Lecture 2. Existence of a stable matching: the fundamental algorithm 924
- Lecture 3. Principle of deferred decisions: coupon collecting 1732
- Lecture 4. Theoretical developments: application to the shortest path 2540
- Lecture 5. Searching a table by hashing; mean behavior of thefundamental algorithm 3752
- Lecture 6. Implementing the fundamental algorithm 4560
- Lecture 7. Research problems 5570
- Annotated bibliography 6681
- Appendix A. Later developments 6984
- Appendix B. Solutions to exercises 7186
- Index 7388
- Back Cover Back Cover190