 BROWSE
 USED
 STAFF PICKS
 GIFTS + GIFT CARDS
 SELL BOOKS
 BLOG
 EVENTS
 FIND A STORE
 800.878.7323

$165.40
New Hardcover
Ships in 1 to 3 days
available for shipping or prepaid pickup only
Available for Instore Pickup
in 7 to 12 days
More copies of this ISBNThis title in other editionsData Structures and Algorithm Analysis in Javaby Mark Allen Weiss
Synopses & ReviewsPublisher Comments:Data Structures and Algorithm Analysis in Java is an “advanced algorithms” book that fits between traditional CS2 and Algorithms Analysis courses. In the old ACM Curriculum Guidelines, this course was known as CS7. This text is for readers who want to learn good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. Readers should have some knowledge of intermediate programming, including topics as objectbased programming and recursion, and some background in discrete math.
As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop wellconstructed, maximally efficient programs in Java.
Weiss clearly explains topics from binary heaps to sorting to NPcompleteness, and dedicates a full chapter to amortized analysis and advanced data structures and their implementation. Figures and examples illustrating successive stages of algorithms contribute to Weiss’ careful, rigorous and indepth analysis of each type of algorithm. A logical organization of topics and full access to source code complement the text’s coverage.
About the AuthorMark Allen Weiss is Professor and Associate Director for the School of Computing and Information Sciences at Florida International University. He is also currently serving as both Director of Undergraduate Studies and Director of Graduate Studies. He received his Bachelor’s Degree in Electrical Engineering from the Cooper Union in 1983, and his Ph.D. in Computer Science from Princeton University in 1987, working under Bob Sedgewick. He has been at FIU since 1987 and was promoted to Professor in 1996. His interests include data structures, algorithms, and education. He is most wellknown for his highlyacclaimed Data Structures textbooks, which have been used for a generation by roughly a million students.
Professor Weiss is the author of numerous publications in toprated journals and was recipient of the University’s Excellence in Research Award in 1994. In 1996 at FIU he was the first in the world to teach Data Structures using the Java programming language, which is now the de facto standard. From 19972004 he served as a member of the Advanced Placement Computer Science Development Committee, chairing the committee from 20002004. The committee designed the curriculum and wrote the AP exams that were taken by 20,000 high school students annually. In addition to his Research Award in 1994, Professor Weiss is also the recipient of the University’s Excellence in Teaching Award in 1999 and the School of Computing and Information Science Excellence in Teaching Award (2005) and Excellence in Service Award (2007). Table of ContentsChapter 1 Introduction 1
1.1 What’s the Book About? 1 1.2 Mathematics Review 2 1.2.1 Exponents 3 1.2.2 Logarithms 3 1.2.3 Series 4 1.2.4 Modular Arithmetic 5 1.2.5 The P Word 6 1.3 A Brief Introduction to Recursion 8 1.4 Implementing Generic Components PreJava 5 12 1.4.1 Using Object for Genericity 13 1.4.2 Wrappers for Primitive Types 14 1.4.3 Using Interface Types for Genericity 14 1.4.4 Compatibility of Array Types 16 1.5 Implementing Generic Components Using Java 5 Generics 16 1.5.1 Simple Generic Classes and Interfaces 17 1.5.2 Autoboxing/Unboxing 18 1.5.3 The Diamond Operator 18 1.5.4 Wildcards with Bounds 19 1.5.5 Generic Static Methods 20 1.5.6 Type Bounds 21 1.5.7 Type Erasure 22 1.5.8 Restrictions on Generics 23 1.6 Function Objects 24 Summary 26 Exercises 26 References 28
Chapter 2 Algorithm Analysis 29 2.1 Mathematical Background 29 2.2 Model 32 2.3 What to Analyze 33 2.4 Running Time Calculations 35 2.4.1 A Simple Example 36 2.4.2 General Rules 36 2.4.3 Solutions for the Maximum Subsequence Sum Problem 39 2.4.4 Logarithms in the Running Time 45 2.4.5 A Grain of Salt 49 Summary 49 Exercises 50 References 55
Chapter 3 Lists, Stacks, and Queues 57 3.1 Abstract Data Types (ADTs) 57 3.2 The List ADT 58 3.2.1 Simple Array Implementation of Lists 58 3.2.2 Simple Linked Lists 59 3.3 Lists in the Java Collections API 61 3.3.1 Collection Interface 61 3.3.2 Iterators 61 3.3.3 The List Interface, ArrayList, and LinkedList 63 3.3.4 Example: Using remove on a LinkedList 65 3.3.5 ListIterators 67 3.4 Implementation of ArrayList 67 3.4.1 The Basic Class 68 3.4.2 The Iterator and Java Nested and Inner Classes 71 3.5 Implementation of LinkedList 75 3.6 The Stack ADT 82 3.6.1 Stack Model 82 3.6.2 Implementation of Stacks 83 3.6.3 Applications 84 3.7 The Queue ADT 92 3.7.1 Queue Model 92 3.7.2 Array Implementation of Queues 92 3.7.3 Applications of Queues 95 Summary 96 Exercises 96
Chapter 4 Trees 101 4.1 Preliminaries 101 4.1.1 Implementation of Trees 102 4.1.2 Tree Traversals with an Application 103 4.2 Binary Trees 107 4.2.1 Implementation 108 4.2.2 An Example: Expression Trees 109 4.3 The Search Tree ADT–Binary Search Trees 112 4.3.1 contains 113 4.3.2 findMin and findMax 115 4.3.3 insert 116 4.3.4 remove 118 4.3.5 AverageCase Analysis 120 4.4 AVL Trees 123 4.4.1 Single Rotation 125 4.4.2 Double Rotation 128 4.5 Splay Trees 137 4.5.1 A Simple Idea (That Does Not Work) 137 4.5.2 Splaying 139 4.6 Tree Traversals (Revisited) 145 4.7 BTrees 147 4.8 Sets and Maps in the Standard Library 152 4.8.1 Sets 152 4.8.2 Maps 153 4.8.3 Implementation of TreeSet and TreeMap 153 4.8.4 An Example That Uses Several Maps 154 Summary 160 Exercises 160 References 167
Chapter 5 Hashing 171 5.1 General Idea 171 5.2 Hash Function 172 5.3 Separate Chaining 174 5.4 Hash Tables Without Linked Lists 179 5.4.1 Linear Probing 179 5.4.2 Quadratic Probing 181 5.4.3 Double Hashing 183 5.5 Rehashing 188 5.6 Hash Tables in the Standard Library 189 5.7 Hash Tables with WorstCase O(1) Access 192 5.7.1 Perfect Hashing 193 5.7.2 Cuckoo Hashing 195 5.7.3 Hopscotch Hashing 205 5.8 Universal Hashing 211 5.9 Extendible Hashing 214 Summary 217 Exercises 218 References 222
Chapter 6 Priority Queues (Heaps) 225 6.1 Model 225 6.2 Simple Implementations 226 6.3 Binary Heap 226 6.3.1 Structure Property 227 6.3.2 HeapOrder Property 229 6.3.3 Basic Heap Operations 229 6.3.4 Other Heap Operations 234 6.4 Applications of Priority Queues 238 6.4.1 The Selection Problem 238 6.4.2 Event Simulation 239 6.5 dHeaps 240 6.6 Leftist Heaps 241 6.6.1 Leftist Heap Property 241 6.6.2 Leftist Heap Operations 242 6.7 Skew Heaps 249 6.8 Binomial Queues 252 6.8.1 Binomial Queue Structure 252 6.8.2 Binomial Queue Operations 253 6.8.3 Implementation of Binomial Queues 256 6.9 Priority Queues in the Standard Library 261 Summary 261 Exercises 263 References 267
Chapter 7 Sorting 271 7.1 Preliminaries 271 7.2 Insertion Sort 272 7.2.1 The Algorithm 272 7.2.2 Analysis of Insertion Sort 272 7.3 A Lower Bound for Simple Sorting Algorithms 273 7.4 Shellsort 274 7.4.1 WorstCase Analysis of Shellsort 276 7.5 Heapsort 278 7.5.1 Analysis of Heapsort 279 7.6 Mergesort 282 7.6.1 Analysis of Mergesort 284 7.7 Quicksort 288 7.7.1 Picking the Pivot 290 7.7.2 Partitioning Strategy 292 7.7.3 Small Arrays 294 7.7.4 Actual Quicksort Routines 294 7.7.5 Analysis of Quicksort 297 7.7.6 A LinearExpectedTime Algorithm for Selection 300 7.8 A General Lower Bound for Sorting 302 7.8.1 Decision Trees 302 7.9 DecisionTree Lower Bounds for Selection Problems 304 7.10 Adversary Lower Bounds 307 7.11 LinearTime Sorts: Bucket Sort and Radix Sort 310 7.12 External Sorting 315 7.12.1 Why We Need New Algorithms 316 7.12.2 Model for External Sorting 316 7.12.3 The Simple Algorithm 316 7.12.4 Multiway Merge 317 7.12.5 Polyphase Merge 318 7.12.6 Replacement Selection 319 Summary 321 Exercises 321 References 327
Chapter 8 The Disjoint Set Class 331 8.1 Equivalence Relations 331 8.2 The Dynamic Equivalence Problem 332 8.3 Basic Data Structure 333 8.4 Smart Union Algorithms 337 8.5 Path Compression 340 8.6 Worst Case for UnionbyRank and Path Compression 341 8.6.1 Slowly Growing Functions 342 8.6.2 An Analysis By Recursive Decomposition 343 8.6.3 An O(M log * N) Bound 350 8.6.4 An O( M α (M, N) ) Bound 350 8.7 An Application 352 Summary 355 Exercises 355 References 357
Chapter 9 Graph Algorithms 359 9.1 Definitions 359 9.1.1 Representation of Graphs 360 9.2 Topological Sort 362 9.3 ShortestPath Algorithms 366 9.3.1 Unweighted Shortest Paths 367 9.3.2 Dijkstra’s Algorithm 372 9.3.3 Graphs with Negative Edge Costs 380 9.3.4 Acyclic Graphs 380 9.3.5 AllPairs Shortest Path 384 9.3.6 ShortestPath Example 384 9.4 Network Flow Problems 386 9.4.1 A Simple MaximumFlow Algorithm 388 9.5 Minimum Spanning Tree 393 9.5.1 Prim’s Algorithm 394 9.5.2 Kruskal’s Algorithm 397 9.6 Applications of DepthFirst Search 399 9.6.1 Undirected Graphs 400 9.6.2 Biconnectivity 402 9.6.3 Euler Circuits 405 9.6.4 Directed Graphs 409 9.6.5 Finding Strong Components 411 9.7 Introduction to NPCompleteness 412 9.7.1 Easy vs. Hard 413 9.7.2 The Class NP 414 9.7.3 NPComplete Problems 415 Summary 417 Exercises 417 References 425
Chapter 10 Algorithm Design Techniques 429 10.1 Greedy Algorithms 429 10.1.1 A Simple Scheduling Problem 430 10.1.2 Huffman Codes 433 10.1.3 Approximate Bin Packing 439 10.2 Divide and Conquer 448 10.2.1 Running Time of DivideandConquer Algorithms 449 10.2.2 ClosestPoints Problem 451 10.2.3 The Selection Problem 455 10.2.4 Theoretical Improvements for Arithmetic Problems 458 10.3 Dynamic Programming 462 10.3.1 Using a Table Instead of Recursion 463 10.3.2 Ordering Matrix Multiplications 466 10.3.3 Optimal Binary Search Tree 469 10.3.4 AllPairs Shortest Path 472 10.4 Randomized Algorithms 474 10.4.1 Random Number Generators 476 10.4.2 Skip Lists 480 10.4.3 Primality Testing 483 10.5 Backtracking Algorithms 486 10.5.1 The Turnpike Reconstruction Problem 487 10.5.2 Games 490 Summary 499 Exercises 499 References 508
Chapter 11 Amortized Analysis 513 11.1 An Unrelated Puzzle 514 11.2 Binomial Queues 514 11.3 Skew Heaps 519 11.4 Fibonacci Heaps 522 11.4.1 Cutting Nodes in Leftist Heaps 522 11.4.2 Lazy Merging for Binomial Queues 525 11.4.3 The Fibonacci Heap Operations 528 11.4.4 Proof of the Time Bound 529 11.5 Splay Trees 531 Summary 536 Exercises 536 References 538
Chapter 12 Advanced Data Structures and Implementation 541 12.1 TopDown Splay Trees 541 12.2 RedBlack Trees 549 12.2.1 BottomUp Insertion 549 12.2.2 TopDown RedBlack Trees 551 12.2.3 TopDown Deletion 556 12.3 Treaps 558 12.4 Suffix Arrays and Suffix Trees 560 12.4.1 Suffix Arrays 561 12.4.2 Suffix Trees 564 12.4.3 LinearTime Construction of Suffix Arrays and Suffix Trees 567 12.5 kd Trees 578 12.6 Pairing Heaps 583 Summary 588 Exercises 590 References 594 Index 599
What Our Readers Are SayingBe the first to add a comment for a chance to win!Product Details
Other books you might likeRelated Subjects
Computers and Internet » Computer Languages » Java


