Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms
 
Donald E. Knuth Stanford University, Stanford, CA
A co-publication of the AMS and Centre de Recherches Mathématiques
Stable Marriage and Its Relation to Other Combinatorial Problems
Softcover ISBN:  978-0-8218-0603-6
Product Code:  CRMP/10
List Price: $29.00
MAA Member Price: $26.10
AMS Member Price: $23.20
eBook ISBN:  978-1-4704-3924-8
Product Code:  CRMP/10.E
List Price: $27.00
MAA Member Price: $24.30
AMS Member Price: $21.60
Softcover ISBN:  978-0-8218-0603-6
eBook: ISBN:  978-1-4704-3924-8
Product Code:  CRMP/10.B
List Price: $56.00 $42.50
MAA Member Price: $50.40 $38.25
AMS Member Price: $44.80 $34.00
Stable Marriage and Its Relation to Other Combinatorial Problems
Click above image for expanded view
Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms
Donald E. Knuth Stanford University, Stanford, CA
A co-publication of the AMS and Centre de Recherches Mathématiques
Softcover ISBN:  978-0-8218-0603-6
Product Code:  CRMP/10
List Price: $29.00
MAA Member Price: $26.10
AMS Member Price: $23.20
eBook ISBN:  978-1-4704-3924-8
Product Code:  CRMP/10.E
List Price: $27.00
MAA Member Price: $24.30
AMS Member Price: $21.60
Softcover ISBN:  978-0-8218-0603-6
eBook ISBN:  978-1-4704-3924-8
Product Code:  CRMP/10.B
List Price: $56.00 $42.50
MAA Member Price: $50.40 $38.25
AMS Member Price: $44.80 $34.00
  • Book Details
     
     
    CRM Proceedings & Lecture Notes
    Volume: 101997; 74 pp
    MSC: Primary 68; Secondary 05; 90

    “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
     
     
    • Chapters
    • Lecture 1. Introduction, definitions, and examples
    • Lecture 2. Existence of a stable matching: the fundamental algorithm
    • Lecture 3. Principle of deferred decisions: coupon collecting
    • Lecture 4. Theoretical developments: application to the shortest path
    • Lecture 5. Searching a table by hashing; mean behavior of the fundamental algorithm
    • Lecture 6. Implementing the fundamental algorithm
    • Lecture 7. Research problems
  • Additional Material
     
     
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Accessibility – to request an alternate format of an AMS title
Volume: 101997; 74 pp
MSC: Primary 68; Secondary 05; 90

“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.

  • Chapters
  • Lecture 1. Introduction, definitions, and examples
  • Lecture 2. Existence of a stable matching: the fundamental algorithm
  • Lecture 3. Principle of deferred decisions: coupon collecting
  • Lecture 4. Theoretical developments: application to the shortest path
  • Lecture 5. Searching a table by hashing; mean behavior of the fundamental algorithm
  • Lecture 6. Implementing the fundamental algorithm
  • Lecture 7. Research problems
Review Copy – for publishers of book reviews
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.