Data Structures and Algorithm Analysis in C (2nd Edition)

3.77 avg rating
( 100 ratings by Goodreads )
 
9780201498400: Data Structures and Algorithm Analysis in C (2nd Edition)

In this second edition of his best-selling book, Data Structures and Algorithm Analysis in C, Mark Allen Weiss, continues to refine and enhance his innovative approach to algorithms and data structures. Using a C implementation, he highlights conceptual topics, focusing on ADTs and the analysis of algorithms for efficiency as well as performance and running time. Dr. Weiss also distinguishes Data Structures and Algorithm Analysis in C with the extensive use of figures and examples showing the successive stages of an algorithm, his engaging writing style, and a logical organization of topics.

"synopsis" may belong to another edition of this title.

From the Inside Flap:

Purpose/Goals

This book describes data structures, methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms. As computers become faster and faster, the need for programs that can handle large amounts of input becomes more acute. Paradoxically, this requires more careful attention to efficiency, since inefficiencies in programs become most obvious when input sizes are large. By analyzing an algorithm before it is actually coded, students can decide if a particular solution will be feasible. For example, in this text students look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from 16 years to less than a second. Therefore, no algorithm or data structure is presented without an explanation of its running time. In some cases, minute details that affect the running time of the implementation are explored.

Once a solution method is determined, a program must still be written. As computers have become more powerful, the problems they must solve have become larger and more complex, requiring development of more intricate programs. The goal of this text is to teach students good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency.

This book is suitable for either an advanced data structures (CS7) course or a first-year graduate course in algorithm analysis. Students should have some knowledge of intermediate programming, including such topics as pointers and recursion, and some background in discrete math. Approach

I believe it is important for students to learn how to program for themselves, not how to copy programs from a book. On the other hand, it is virtually impossible to discuss realistic programming issues without including sample code. For this reason, the book usually provides about one-half to three-quarters of an implementation, and the student is encouraged to supply the rest. Chapter 12, which is new to this edition, discusses additional data structures with an emphasis on implementation details.

The algorithms in this book are presented in ANSI C, which, despite some flaws, is arguably the most popular systems programming language. The use of C instead of Pascal allows the use of dynamically allocated arrays (see, for instance, rehashing in Chapter 5). It also produces simplified code in several places, usually because the and (&&) operations is short-circuited.

Most criticisms of C center on the fact that it is easy to write code that is barely readable. Some of the more standard tricks, such as the simultaneous assignment and testing against 0 via

if (x=y)

are generally not used in the text, since the loss of clarity is compensated by only a few keystrokes and no increased speed. I believe that this books demonstrates that unreadable code can be avoided by exercising reasonable care.

Overview

Chapter 1 contains review material on discrete math and recursion. I believe the only way to be comfortable with recursion is to see good uses over and over. Therefore, recursion is prevalent in this text, with examples in every chapter except Chapter 5.

Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an in-depth explanation of logarithms running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer programs are introduced, but some of the analysis (solving recurrence relations) is implicitly delayed until Chapter 7, where it is performed in detail.

Chapter 3 covers lists, stacks, and queues. The emphasis here is on coding these data structures using ADTs, fast implementation of these data structures, and an exposition of some of their uses. There are almost no programs (just routines), but the exercises contain plenty of ideas for programming assignments.

Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX file system and expression trees are used as examples. AVL trees and splay trees are introduced but not analyzed. Seventy-five percent of the code is written, leaving similar cases to be completed by the student. More careful treatment of search tree implementation details is found in Chapter 12. Additional coverage of trees, such as file compression and game trees, is deferred until Chapter 10. Data structures for an external medium are considered as the final topic in several chapters.

Chapter 5 is relatively short chapter concerning hash tables. Some analysis is performed, and extendible hashing is covered at the end of the chapter.

Chapter 6 is about priority queues. Binary heaps are covered, and there is additional material on some of the theoretically interesting implementations of priority queues. The Fibonacci heap is discussed in Chapter 11, and the pairing heap is discussed in Chapter 12.

Chapter 7 covers sorting. It is very specific with respect to coding details and analysis. All the important general-purpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. The analysis of the average-case running time of heapsort is new to this edition. External sorting is covered at the end of the chapter.

Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a short and specific chapter that can be skipped if Kruskal's algorithm is not discussed.

Chapter 9 covers graph algorithms. Algorithms on graphs are interesting, not only because they frequently occur in practice but also because their running time is so heavily dependent on the proper use of data structures. Virtually all of the standard algorithms are presented along with appropriate data structures, pseudocode, and analysis of running time. To place these problems in a proper context, a short discussion on complexity theory (including NP-completeness and undecidability) is provided.

Chapter 10 covers algorithm design by examining common problem-solving techniques. This chapter is heavily fortified with examples. Pseudocode is used in these later chapters so that the student's appreciation of an example algorithm is not obscured by implementation details.

Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter, are analyzed.

Chapter 12 is new to this edition. It covers search tree algorithms, the k-d tree, and the pairing heap. This chapter departs from the rest of the text by providing complete and careful implementations for the search trees and pairing heap. The material is structured so that the instructor can integrate sections into discussions from other chapters. For example, the top-down red black tree in Chapter 12 can be discussed under AVL trees (in Chapter 4).

Chapters 1-9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NP-completeness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book on NP-completeness can be used to augment this text.

Exercises

Exercises, provided at the end of each chapter, match the order in which material is presented. The last exercises may address the chapter as a whole rather than a specific section. Difficult exercises are marked with an asterisk, and more challenging exercises have two asterisks.

A solutions manual containing solutions to almost all the exercises is available to instructors from the Addison-Wesley Publishing Company.

References

References are placed at the end of each chapter. Generally the references either are historical, representing the original source of the material, or they represent extensions and improvements to the results given in the text. Some references represent solutions to exercises.

Code Availability

The example program code in this book is available via anonymous ftp at aw. It is also accessible through the World Wide Web; the URL is aw/cseng/authors/weiss/dsaac2/dsaac2e.sup.html (follow the links from there). The exact location of this material may change.

Acknowledgments

Many, many people have helped me in the preparation of books in this series. Some are listed in other versions of the book; thanks to all.

For this edition, I would like to thank my editors at Addison-Wesley, Carter Shanklin and Susan Hartman. Teri Hyde did another wonderful job with the production, and Matthew Harris and his staff at Publication Services did their usual fine work putting the final pieces together.

M.A.W.
Miami, Florida
July, 1996

0201498405P04062001

About the Author:

Mark Allen Weiss is a Professor in the School of Computer Science at Florida International University. He received his Ph.D. in Computer Science from Princeton University where he studied under Robert Sedgewick. Dr.Weiss has received FIU's Excellence in Research Award, as well as the Teaching Incentive Program Award, which was established by the Florida Legislature to recognize teaching excellence. Mark Allen Weiss is on the Advanced Placement Computer Science Development Committee. He is the successful author of Algorithms, Data Structures, and Problem Solving with C++ and the series Data Structures and Algorithm Analysis in Pascal, Ada, C, and C++, with Addison-Wesley.



0201498405AB04062001

"About this title" may belong to another edition of this title.

Top Search Results from the AbeBooks Marketplace

International Edition
International Edition

1.

Weiss, Mark A.
Published by Pearson
ISBN 10: 0201498405 ISBN 13: 9780201498400
New Softcover Quantity Available: 20
International Edition
Seller:
Sunshine Book Store
(Wilmington, DE, U.S.A.)
Rating
[?]

Book Description Pearson. Book Condition: New. 0201498405 This is an International Edition. Brand New, Paperback, Delivery within 6-14 business days, Similar Contents as U.S Edition, ISBN and Cover design may differ, printed in Black & White. Choose Expedited shipping for delivery within 3-8 business days. We do not ship to PO Box, APO , FPO Address. In some instances, subjects such as Management, Accounting, Finance may have different end chapter case studies and exercises. International Edition Textbooks may bear a label "Not for sale in the U.S. or Canada" and "Content may different from U.S. Edition" - printed only to discourage U.S. students from obtaining an affordable copy. The U.S. Supreme Court has asserted your right to purchase international editions, and ruled on this issue. Access code/CD is not provided with these editions , unless specified. We may ship the books from multiple warehouses across the globe, including India depending upon the availability of inventory storage. Customer satisfaction guaranteed. Bookseller Inventory # HU_9780201498400

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 19.25
Convert Currency

Add to Basket

Shipping: FREE
Within U.S.A.
Destination, Rates & Speeds
International Edition
International Edition

2.

Mark Allen Weiss
ISBN 10: 0201498405 ISBN 13: 9780201498400
New Soft cover Quantity Available: > 20
International Edition
Seller:
LOW COST_FAST SHIP
(Scottsdale, AZ, U.S.A.)
Rating
[?]

Book Description Soft cover. Book Condition: New. NEW - International Edition - ISBN 9788177583588 - Same Contents as in US edition - in english - 2ed - - SHRINKwrapped BOXpacked - Printed in Asia - Cover image is different from US edition - There is no CD or Access Code, unless specified above - Ships from various locations - Expedited 2 to 4 day Delivery option available -Standard shipping takes 5 to 10 business days - Tracking number is emailed for every order -You get same study contents at a fraction of US edition cost - Save Hard earned money. Bookseller Inventory # DH7

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 13.32
Convert Currency

Add to Basket

Shipping: US$ 5.99
Within U.S.A.
Destination, Rates & Speeds
International Edition
International Edition

3.

Mark Allen Weiss
ISBN 10: 0201498405 ISBN 13: 9780201498400
New Softcover Quantity Available: > 20
International Edition
Seller:
LowPriceBookDeals
(Wilmington, DE, U.S.A.)
Rating
[?]

Book Description Softcover. Book Condition: New. 2nd edition. Brand NEW, Paperback International Edition. Black & White or color, Cover and ISBN may be different but similar contents as US editions. Standard delivery takes 5-9 business days by USPS with tracking number. Choose expedited shipping for superfast delivery 2-4 business days by DHL/FEDEX. We also ship to PO Box addresses but by Standard delivery. International Edition Textbooks may bear a label -Not for sale in the U.S. or Canada- etc. printed only to discourage U.S. students from obtaining an affordable copy. Legal to use despite any disclaimer on cover as per US court. No access code or CD included unless specified. In some instances, the international textbooks may have different exercises at the end of the chapters. Printed in English. We may ship the books from multiple warehouses across the globe, including India depending upon the availability of inventory storage. 100% Customer satisfaction guaranteed! Please feel free to contact us for any queries. Bookseller Inventory # LPBD31424450

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 16.48
Convert Currency

Add to Basket

Shipping: US$ 3.95
Within U.S.A.
Destination, Rates & Speeds
International Edition
International Edition

4.

Mark A. Weiss
ISBN 10: 0201498405 ISBN 13: 9780201498400
New Paperback Quantity Available: 20
International Edition
Seller:
Bookstore99
(Wilmington, DE, U.S.A.)
Rating
[?]

Book Description Paperback. Book Condition: NEW. This is an International Edition. Brand New Paperback- Same Title Author and Edition as listed. ISBN and Cover design differs. Similar Contents as U.S Edition. Delivery within 3-7 business days ACROSS THE GLOBE. We can ship to PO Box address in US. International Edition Textbooks may bear a label "Not for sale in the U.S. or Canada" or "For sale in Asia only" or similar restrictions- printed only to discourage students from obtaining an affordable copy. US Court has asserted your right to buy and use International edition. Access code/CD may not provided with these editions. We may ship the books from multiple warehouses across the globe including Asia depending upon the availability of inventory. Printed in English. Customer satisfaction guaranteed. Choose expedited shipping for Express delivery. Tracking number provided for every order. Bookseller Inventory # RU_9780201498400

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 17.54
Convert Currency

Add to Basket

Shipping: US$ 2.99
Within U.S.A.
Destination, Rates & Speeds
International Edition
International Edition

5.

Weiss, Mark A.
Published by Pearson
ISBN 10: 0201498405 ISBN 13: 9780201498400
New PAPERBACK Quantity Available: 5
International Edition
Seller:
Book Arsenal
(Delhi, DELHI, India)
Rating
[?]

Book Description Pearson. PAPERBACK. Book Condition: New. 0201498405 We ship from India. PAPERBACK INTERNATIONAL EDITION Brand New Copy. The ISBN-13 or Cover might be different but content is extactly same. We deliver in 5 - 9 days and actively resolve customer issues. Bookseller Inventory # 0201498405-ABAB

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 20.82
Convert Currency

Add to Basket

Shipping: FREE
From India to U.S.A.
Destination, Rates & Speeds
International Edition
International Edition

6.

Weiss, Mark A.
Published by Pearson
ISBN 10: 0201498405 ISBN 13: 9780201498400
New PAPERBACK Quantity Available: 10
International Edition
Seller:
WFL
(Holtsville, NY, U.S.A.)
Rating
[?]

Book Description Pearson. PAPERBACK. Book Condition: New. 0201498405 New ,International edition , softcover ,Same text as US edition , ISBN /Cover may be different , Ready to ship, 5-8 business days worldwide delivery. Bookseller Inventory # INFFGK1191

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 16.42
Convert Currency

Add to Basket

Shipping: US$ 4.60
Within U.S.A.
Destination, Rates & Speeds
International Edition
International Edition

7.

M.A. Weiss
Published by Pearson
ISBN 10: 0201498405 ISBN 13: 9780201498400
New Paperback Quantity Available: 1
International Edition
Seller:
Campustexxts
(Vicksburg, MI, U.S.A.)
Rating
[?]

Book Description Pearson. Paperback. Book Condition: New. International Edition. Very fast shipping. Receive your book in 2-7 business days if you checkout with expedited shipping. We take pride in our customer service, please contact us if you have any questions regarding the listing. Bookseller Inventory # in-us-9780201498400

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 17.87
Convert Currency

Add to Basket

Shipping: US$ 3.50
Within U.S.A.
Destination, Rates & Speeds
International Edition
International Edition

8.

WEISS
ISBN 10: 0201498405 ISBN 13: 9780201498400
New Softcover Quantity Available: 10
International Edition
Seller:
bookscollection
(Delhi, DELHI, India)
Rating
[?]

Book Description Book Condition: Brand New. PAPERBACK,Book Condition New, International Edition. We Do not Ship APO FPO AND PO BOX. Cover Image & ISBN may be different from US edition but contents as US Edition. Printing in English language.NO CD AND ACCESS CODE. Quick delivery by USPS/UPS/DHL/FEDEX/ARAMEX ,Customer satisfaction guaranteed. We may ship the books from Asian regions for inventory purpose. Bookseller Inventory # ABEADH*##2005

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 18.05
Convert Currency

Add to Basket

Shipping: US$ 4.13
From India to U.S.A.
Destination, Rates & Speeds
International Edition
International Edition

9.

Weiss,M.A.
ISBN 10: 0201498405 ISBN 13: 9780201498400
New Softcover Quantity Available: 20
International Edition
Seller:
Unique Bookseller
(Delhi, India)
Rating
[?]

Book Description Softcover. Book Condition: Brand New. .. Black & White or color International Edition. ISBN and front cover may be different, but contents are same as the US edition. Book printed in English. Territorial restrictions may be printed on the book. GET IT FAST within 3-5 business days by DHL/FedEx/Aramex and tracking number will be uploaded into your order page within 24-48 hours. Kindly provide day time phone number in order to ensure smooth delivery. No shipping to PO BOX, APO, FPO addresses. 100% Customer satisfaction guaranteed!. . Bookseller Inventory # UBS04178

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 26.17
Convert Currency

Add to Basket

Shipping: FREE
From India to U.S.A.
Destination, Rates & Speeds
International Edition
International Edition

10.

Weiss
ISBN 10: 0201498405 ISBN 13: 9780201498400
New Paperback Quantity Available: 5
International Edition
Seller:
PRIORITY BOOKS
(Springfield, VA, U.S.A.)
Rating
[?]

Book Description Paperback. Book Condition: New. Softcover Book, New Condition, Fast Shipping. Ready in Stock. 2nd Edition. [Please Read Carefully Before Buying], This Is An International Edition. Printed In Black and White. , Book Cover And ISBN No May Be Different From US Edition. Restricted Sales Disclaimer Wordings Not For Sales In USA And Canada May Be Printed On The Cover Of The Book. Standard Shipping 7-14 Business Days. Expedited Shiping 4-8 Business Days. ***WE DO NOT ENTERTAIN BULK ORDERS.*** The Books May Be Ship From Overseas For Inventory Purpose. Bookseller Inventory # 432902

More Information About This Seller | Ask Bookseller a Question

Buy New
US$ 22.37
Convert Currency

Add to Basket

Shipping: US$ 3.99
Within U.S.A.
Destination, Rates & Speeds

There are more copies of this book

View all search results for this book