Skip to main content
SpringerLink
Log in

The Design and Analysis of Algorithms

  • Textbook
  • © 1992

Overview

Authors:
  1. Dexter C. Kozen

    1. Department of Computer Science, Cornell University, Ithaca, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Monographs in Computer Science (MCS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 69.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (40 chapters)

  1. Front Matter

    Pages i-x
    Download chapter PDF

  2. Lectures

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Algorithms and Their Complexity

      • Dexter C. Kozen
      Pages 3-8

    3. Topological Sort and MST

      • Dexter C. Kozen
      Pages 9-12

    4. Matroids and Independence

      • Dexter C. Kozen
      Pages 13-18

    5. Depth-First and Breadth-First Search

      • Dexter C. Kozen
      Pages 19-24

    6. Shortest Paths and Transitive Closure

      • Dexter C. Kozen
      Pages 25-27

    7. Kleene Algebra

      • Dexter C. Kozen
      Pages 28-33

    8. More on Kleene Algebra

      • Dexter C. Kozen
      Pages 34-39

    9. Binomial Heaps

      • Dexter C. Kozen
      Pages 40-43

    10. Fibonacci Heaps

      • Dexter C. Kozen
      Pages 44-47

    11. Union-Find

      • Dexter C. Kozen
      Pages 48-51

    12. Analysis of Union-Find

      • Dexter C. Kozen
      Pages 52-57

    13. Splay Trees

      • Dexter C. Kozen
      Pages 58-64

    14. Random Search Trees

      • Dexter C. Kozen
      Pages 65-70

    15. Planar and Plane Graphs

      • Dexter C. Kozen
      Pages 71-76

    16. The Planar Separator Theorem

      • Dexter C. Kozen
      Pages 77-83

    17. Max Flow

      • Dexter C. Kozen
      Pages 84-89

    18. More on Max Flow

      • Dexter C. Kozen
      Pages 90-95

    19. Still More on Max Flow

      • Dexter C. Kozen
      Pages 96-100
Back to top

Keywords

About this book

These are my lecture notes from CS681: Design and Analysis of Algo­ rithms, a one-semester graduate course I taught at Cornell for three consec­ utive fall semesters from '88 to '90. The course serves a dual purpose: to cover core material in algorithms for graduate students in computer science preparing for their PhD qualifying exams, and to introduce theory students to some advanced topics in the design and analysis of algorithms. The material is thus a mixture of core and advanced topics. At first I meant these notes to supplement and not supplant a textbook, but over the three years they gradually took on a life of their own. In addition to the notes, I depended heavily on the texts • A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975. • M. R. Garey and D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness. w. H. Freeman, 1979. • R. E. Tarjan, Data Structures and Network Algorithms. SIAM Regional Conference Series in Applied Mathematics 44, 1983. and still recommend them as excellent references.

Authors and Affiliations

  • Department of Computer Science, Cornell University, Ithaca, USA

    Dexter C. Kozen

Bibliographic Information

  • Book Title: The Design and Analysis of Algorithms

  • Authors: Dexter C. Kozen

  • Series Title: Monographs in Computer Science

  • DOI: https://doi.org/10.1007/978-1-4612-4400-4

  • Publisher: Springer New York, NY

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag New York, Inc. 1992

  • Hardcover ISBN: 978-0-387-97687-7Published: 03 December 1991

  • Softcover ISBN: 978-1-4612-8757-5Published: 07 October 2011

  • eBook ISBN: 978-1-4612-4400-4Published: 06 December 2012

  • Series ISSN: 0172-603X

  • Series E-ISSN: 2512-5486

  • Edition Number: 1

  • Number of Pages: X, 322

  • Topics: Algorithm Analysis and Problem Complexity

Publish with us

Policies and ethics

Back to top

Search

Navigation