Home > Store

Algorithms in C++

Register your product to gain access to bonus material or receive a coupon.

Algorithms in C++

Premium Website

  • Sorry, this book is no longer in print.
Not for Sale

Description

  • Copyright 1992
  • Edition: 1st
  • Premium Website
  • ISBN-10: 0-201-51059-6
  • ISBN-13: 978-0-201-51059-1

The latest addition to Robert Sedgewick's popular series of bookscarries his comprehensive collection of algorithms into anobject-oriented programming (OOP) environment with implementationin the C++ programming language. These algorithms cover a broadrange of fundamental and more advanced methods: sorting,searching, string-processing, geometric, graph, and mathematicalalgorithms. The algorithms are all expressed in terms of conciseimplementations in C++, so that readers can both appreciate theirbasic properties and test them on real applications.

The treatment of analysis of algorithsm is carefully developed. When appropriate, analytic results are discussed to illustratewhy certain algorithms are prefered, and in some cases, therelationship of the proactical algorithms being discussed topurely theoretical results is also described.

The ultimate aim of the book is to improve programming practice,whatever the environment, whatever the implementation language. Sedgweick describes the basic methods to be considered in everycase.

Features
  • Hundreds of detailed, innovative figures clearly demonstratehow important algorithms work.
  • Throughout the book, "properties" sections encapsulatespecific information on the performance characteristics ofalgorithms.
  • Six chapters discuss fundamental concepts, including a briefintroduction to data structures.

Algorithms in C++ provides readers with the tools to implement,run, and debug useful algorithms with confidence. This book is ahelpful guide for users engaged in the transition to orexperimentation with OOP and/or the C++ language. It may be usedfor self study, or as a reference for developers or computersystems or applications programs.



0201510596B04062001

Downloads

Source Code

Click below for Source Code related to this title:
Source Code

Extras

Author's Site

Click below for Web Resources related to this title:
Author's Web Site

Sample Content

Preface

This book is intended to survey the most important computeralgorithms in use today and to teach fundamental techniques tothe growing number of people in need of knowing them. It can beused as a textbook for a second, third, or fourth course incomputer science, after students have acquired some programmingskills and familiarity with computer systems, but before theyhave taken specialized courses in advanced areas of computerscience or computer applications.

Additionally, the book may be useful for self-study or as areference for those engaged in the development of computersystems or applications programs, since it contains a number ofimplementations of useful algorithms and detailed information ontheir performance characteristics. The broad perspective takenin the book makes it an appropriate introduction to the field.

The algorithms are expressed in the C++ programming language(versions of the book in Pascal and C are also available). Nospecific knowledge about the language is assumed--the treatmenthere is self-contained (though fast-paced). Readers who havesome familiarity with C++ will find the language a useful vehiclefor learning a variety of methods of practical interest. Readerswho have some familiarity with basic algorithms will find thetreatment here a useful vehicle for learning a variety offeatures of the C++ language, while at the same time learningsome new algorithms.

SCOPE

The book contains forty-five chapters grouped into eight majorparts: fundamentals, sorting, searching, string processing,geometric algorithms, graph algorithms, mathematical algorithmsand advanced topics. A major goal in developing this book hasbeen to bring together the fundamental methods from these diverseareas, in order to provide access to the best methods known forsolving problems by computer. Some of the chapters giveintroductory treatments of advanced material. It is hoped thatthe descriptions here can give readers some understanding of thebasic properties of fundamental algorithms ranging from priorityqueues and hashing to simplex and the fast Fourier transform.

One or two previous courses in computer science or equivalentprogramming experience are recommended for a reader to be able toappreciate the material in this book: one course in programmingin high-level languages such as C++, C or Pascal, and perhapsanother course which teaches fundamental concepts of programmingsystems. This book is thus intended for anyone conversant with amodern programming language and with the basic features of moderncomputer systems. References that might help fill in gaps inone's background are suggested in the text.

Most of the mathematical material supporting the analytic resultsis self-contained (or labeled as "beyond the scope" of thisbook), so little specific preparation in mathematics is requiredfor the bulk of the book, though a certain amount deal withalgorithms related to more advanced mathematical material--theseare intended to place the algorithms in context with othermethods throughout the book, not to teach the mathematicalmaterial. Thus the discussion of advanced mathematical conceptsis brief, general, and descriptive.

USE IN THE CURRICULUM

There is a great deal of flexibility in how the material here canbe taught. To a large extent, the individual chapters in thebook can be read independently of the others, though in somecases algorithms in one chapter make use of methods from aprevious chapter. The material can be adapted for use forvarious courses by selecting perhaps 25 or 30 of the 45 chapters,according to the taste of the instructor and the preparation ofthe students.

The book begins with an introductory section on data structuresand the design and analysis of algorithms. This sets the tonefor the rest of the book and provides a framework within whichmore advanced algorithms are treated. Some readers may skip orskim this section; others may learn the basics there.

An elementary course on "data structures and algorithms" mightomit some of the mathematical algorithms and some of the advancedtopics, then emphasize how various data structures are used inthe implementations. An intermediate course on "design andanalysis of algorithms" might omit some of the more practicallyoriented sections, then emphasize the identification and study ofthe ways in which algorithms achieve good asymptotic performance. A course on "software tools" might omit the mathematical andadvanced algorithmic material, then emphasize how to integratethe implementations given here into large programs or systems. Acourse on "algorithms" might take a survey approach and introduceconcepts from all these areas.

Some instructors may wish to add supplementary material to thecourses described above to reflect their particular orientation. For "data structures and algorithms," more mathematical analysiscould be added; and for "software tools", software engineeringtechniques could be covered in more depth. In this book,attention is paid to all these areas, but the emphasis is on thealgorithms themselves.

Earlier versions of this book have been used in recent years atscores of colleges and universities around the country as a textfor the second or third course in computer science and assupplemental reading for other courses. At Princeton, ourexperience has been that the breadth of coverage of material inthis book provides our majors with an introduction to computerscience that can be expanded upon in later courses on analysis ofalgorithms, systems programming and theoretical computer science,while at the same time providing all the students with a largeset of techniques that they can immediately put to good use.

There are 450 exercises ten following each chapter, thatgenerally divide into one of two types. Most are intended totest students' understanding of material in the next and askstudents to work through an example or apply concepts describedin the text. A few of them, however, involve implementing andputting together some of the algorithms, perhaps runningempirical studies to compare algorithms and to learn theirproperties.

ALGORITHMS OF PRACTICAL USE

The orientation of the book is toward algorithms likely to be ofpractical use. The emphasis is on teaching students the tools oftheir trade to the point that they can confidently implement, runand debug useful algorithms. Full implementations of the methodsdiscussed are included in the text, along with descriptions ofthe operations of these programs on a consistent set of examples. Indeed, as discussed in the epilog, hundreds of figures areincluded in the book that have been created by the algorithmsthemselves. Many algorithms are brought to light on an intuitivelevel through the visual dimension provided by these figures.

Characteristics of the algorithms and situations in which theymight be useful are discussed in detail. Though not emphasized,connections to the analysis of algorithms and theoreticalcomputer science are not ignored. When appropriate, empiricaland analytic results are discussed to illustrate why certainalgorithms are preferred. When interesting, the relationship ofthe practical algorithms being discussed to purely theoreticalresults is described. Specific information performancecharacteristics of algorithms is encapsulated throughout in"properties," important facts about the algorithms that deservefurther study.

Some algorithms are used in relatively small programs to solvespecific problems. Others play an integral part in relativelylarge systems. Many fundamental algorithms find application inboth domains. We indicate as appropriate how algorithms might bespecialized for use as problem-solving tools or generalized forintegration into much bigger programs. Such considerations areof particular interest for algorithms expressed in anobject-oriented language such as C++. In this book we providerelevant information that can be used to make intelligenttradeoffs between utility and performance in implementing widelyapplicable algorithms.

While there is little direct treatment of specific uses of thealgorithms in science and engineering applications, the potentialfor such use is mentioned when appropriate. Our experience hasbeen that when students learn good algorithms in a computerscience context early in their education, they are able to applythem to solve problems when warranted later on.

PROGRAMMING LANGUAGE

The programming language used throughout the book is C++ (Pascaland C versions of the book are also available). Any particularlanguage has advantages and disadvantages--our intention here isto provide access to the fundamental algorithms that have beendeveloped over the years to the growing number of people who aremoving to C++ as a primary language and using it forapplications. The programs can easily be translated to othermodern programming languages, since they are written in astylized form that are relatively language-independent. Indeed,many of the programs have been translated from Pascal, C, andother languages, though we try to use standard C++ idioms whenappropriate. On the other hand, C++ is particularly well-suitedto our task, because its basic support for data abstraction andmodular programming allows us to clearly express relationshipsamong algorithms and data structures.

Some of the programs can simplified by using more advancedlanguage feature, but this is true less often than one might think. Although language features are discussed when appropriate, thisbook is not intended to be reference work on C++ or onobject-oriented programming. While we use C++ classes heavily,we do not use templates, inheritance or virtual functions. Butthe algorithms are coded so as to ease the process of embeddingthem in large systems where such features can be used toadvantage in an object-oriented programming approach. Whenforced to make a choice, we concentrate on the algorithms, notlanguage feature or implementations details.

A goal of this book is to present the algorithms in as simple anddirect a form as possible. The programs are intended to be readnot by themselves, but as part of the surrounding text. Thisstyle was chosen as an alternative, for example, to having inlinecomments. The style is consistent whenever possible, so thatprograms that are similar look similar.

ACKNOWLEDGMENTS

Many people gave me helpful feedback on earlier versions of thisbook. In particular, students at Princeton and Brown sufferedthrough preliminary versions ofthe material in this book in the1980's. Special thanks are due to Trina Avery, Tom Freeman andJanet Incerpi for their help in producing the first edition. Iwould particularly like to thank Janet for converting the bookinto TeX format, adding the thousands of changes I made after the"last draft" of the first edition, guiding the files throughvarious systems to produce printed pages and even writing thescan-conversion routine for TeX used to produce draftmanuscripts, among many other things. Only after performing manyof these tasks myself for later versions do I truly appreciateJanet's contribution. I would also like to thank the manyreaders who provided me with detailed comments about the secondedition, including Guy Almes, Jay Gischer, Kennedy Lemke, UdiManber, Dana Richards, John Reif, M. Rosenfield, Stephen Seidman,and Michael Quinn.

Many of the designs in the figures are based on joint work withMarc Brown in the "electronic classroom" project at BrownUniversity in 1983. Marc's support and assistance in creatingthe designs (not tomention the system with which we worked) aregratefully acknowledged. I would like to acknowledge SarantosKapidakis' help in producing the endpapers.

This C++ version owes its existence to the persistence of KeithWollman who convinced me to proceed, and the patience of PeterGordon, who was confident that I would get around to doing so. Dave Hanson's willingness to answer questions about C and C++ wasinvaluable. I also would like to thank Darcy Cotten and SkipPlank for their help in producing the book.

Much of what I've written here I've learned from the teachingsand writings of Don Knuth, my advisor at Stanford. Though Donhad no direct influence on this work, his presence may be felt inthe book, for it was he who put the study of algorithms on ascientific footing that makes a work such as this possible.

I am very thankful for the support of Brown University and INRIAwhere I did most of the work on the book, and the Institute forDefense Analyses and the Xerox Palo Alto Research Center, where Idid some work on the book while visiting. Many parts of the bookare dependent on research that has been generously supported bythe National Science Foundation and the Office of Naval Research.Finally, I would like to thank Bill Bowen, Aaron Lemonick, andNeil Rudenstine at Princeton University for their support inbuilding an academic environment in which I was able to preparethis book, despite numerous other responsibilities.



0201510596P04062001

Updates

Submit Errata

More Information

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

Overview


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information


To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information


Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.

Security


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

Children


This site is not directed to children under the age of 13.

Marketing


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information


If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

Choice/Opt-out


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information


Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents


California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure


Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

Links


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact


Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice


We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020