Data Structures and Algorithm Analysis in Java

Mark 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 well-known for his highly-acclaimed Data Structures textbooks, which have been used for a generation by roughly a million students.Professor Weiss is the author of numerous publications in top-rated 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 1997-2004 he served as a member of the Advanced Placement Computer Science Development Committee, chairing the committee from 2000-2004. 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 Contents Chapter 1 Introduction 1.1 What’s the Book About?1.2 Mathematics Review 1.2.1 Exponents1.2.2 Logarithms1.2.3 Series1.2.4 Modular Arithmetic1.2.5 The P Word1.3 A Brief Introduction to Recursion1.4 Implementing Generic Components Pre-Java 5 1.4.1 Using Object for Genericity1.4.2 Wrappers for Primitive Types1.4.3 Using Interface Types for Genericity1.4.4 Compatibility of Array Types1.5 Implementing Generic Components Using Java 5 Generics 1.5.1 Simple Generic Classes and Interfaces1.5.2 Autoboxing/Unboxing1.5.3 The Diamond Operator1.5.4 Wildcards with Bounds1.5.5 Generic Static Methods1.5.6 Type Bounds1.5.7 Type Erasure1.5.8 Restrictions on Generics1.6 Function Objects SummaryExercisesReferencesChapter 2 Algorithm Analysis 2.1 Mathematical Background2.2 Model2.3 What to Analyze2.4 Running Time Calculations 2.4.1 A Simple Example2.4.2 General Rules2.4.3 Solutions for the Maximum Subsequence Sum Problem2.4.4 Logarithms in the Running Time2.4.5 A Grain of Salt SummaryExercisesReferencesChapter 3 Lists, Stacks, and Queues 3.1 Abstract Data Types (ADTs)3.2 The List ADT 3.2.1 Simple Array Implementation of Lists3.2.2 Simple Linked Lists3.3 Lists in the Java Collections API 3.3.1 Collection Interface3.3.2 Iterators3.3.3 The List Interface, ArrayList, and LinkedList3.3.4 Example: Using remove on a LinkedList3.3.5 ListIterators3.4 Implementation of ArrayList 3.4.1 The Basic Class3.4.2 The Iterator and Java Nested and Inner Classes3.5 Implementation of LinkedList3.6 The Stack ADT 3.6.1 Stack Model3.6.2 Implementation of Stacks3.6.3 Applications3.7 The Queue ADT 3.7.1 Queue Model3.7.2 Array Implementation of Queues3.7.3 Applications of Queues SummaryExercisesChapter 4 Trees 4.1 Preliminaries 4.1.1 Implementation of Trees4.1.2 Tree Traversals with an Application4.2 Binary Trees 4.2.1 Implementation4.2.2 An Example: Expression Trees4.3 The Search Tree ADT–Binary Search Trees 4.3.1 contains4.3.2 findMin and findMax4.3.3 insert4.3.4 remove4.3.5 Average-Case Analysis4.4 AVL Trees 4.4.1 Single Rotation4.4.2 Double Rotation4.5 Splay Trees 4.5.1 A Simple Idea (That Does Not Work)4.5.2 Splaying4.6 Tree Traversals (Revisited)4.7 B-Trees4.8 Sets and Maps in the Standard Library 4.8.1 Sets4.8.2 Maps4.8.3 Implementation of TreeSet and TreeMap4.8.4 An Example That Uses Several Maps SummaryExercisesReferencesChapter 5 Hashing 5.1 General Idea5.2 Hash Function5.3 Separate Chaining5.4 Hash Tables Without Linked Lists 5.4.1 Linear Probing5.4.2 Quadratic Probing5.4.3 Double Hashing5.5 Rehashing5.6 Hash Tables in the Standard Library5.7 Hash Tables with Worst-Case O(1) Access 5.7.1 Perfect Hashing5.7.2 Cuckoo Hashing5.7.3 Hopscotch Hashing5.8 Universal Hashing5.9 Extendible Hashing SummaryExercisesReferencesChapter 6 Priority Queues (Heaps) 6.1 Model6.2 Simple Implementations6.3 Binary Heap 6.3.1 Structure Property6.3.2 Heap-Order Property6.3.3 Basic Heap Operations6.3.4 Other Heap Operations6.4 Applications of Priority Queues 6.4.1 The Selection Problem6.4.2 Event Simulation6.5 d-Heaps6.6 Leftist Heaps 6.6.1 Leftist Heap Property6.6.2 Leftist Heap Operations6.7 Skew Heaps6.8 Binomial Queues 6.8.1 Binomial Queue Structure6.8.2 Binomial Queue Operations6.8.3 Implementation of Binomial Queues6.9 Priority Queues in the Standard Library SummaryExercisesReferencesChapter 7 Sorting 7.1 Preliminaries7.2 Insertion Sort 7.2.1 The Algorithm7.2.2 Analysis of Insertion Sort7.3 A Lower Bound for Simple Sorting Algorithms7.4 Shellsort 7.4.1 Worst-Case Analysis of Shellsort7.5 Heapsort 7.5.1 Analysis of Heapsort7.6 Mergesort 7.6.1 Analysis of Mergesort7.7 Quicksort 7.7.1 Picking the Pivot7.7.2 Partitioning Strategy7.7.3 Small Arrays7.7.4 Actual Quicksort Routines7.7.5 Analysis of Quicksort7.7.6 A Linear-Expected-Time Algorithm for Selection7.8 A General Lower Bound for Sorting 7.8.1 Decision Trees7.9 Decision-Tree Lower Bounds for Selection Problems7.10 Adversary Lower Bounds7.11 Linear-Time Sorts: Bucket Sort and Radix Sort7.12 External Sorting 7.12.1 Why We Need New Algorithms7.12.2 Model for External Sorting7.12.3 The Simple Algorithm7.12.4 Multiway Merge7.12.5 Polyphase Merge7.12.6 Replacement Selection SummaryExercisesReferencesChapter 8 The Disjoint Set Class 8.1 Equivalence Relations8.2 The Dynamic Equivalence Problem8.3 Basic Data Structure8.4 Smart Union Algorithms8.5 Path Compression8.6 Worst Case for Union-by-Rank and Path Compression 8.6.1 Slowly Growing Functions8.6.2 An Analysis By Recursive Decomposition8.6.3 An O(M log * N) Bound8.6.4 An O( M α (M, N) ) Bound8.7 An Application SummaryExercisesReferencesChapter 9 Graph Algorithms 9.1 Definitions 9.1.1 Representation of Graphs9.2 Topological Sort9.3 Shortest-Path Algorithms 9.3.1 Unweighted Shortest Paths9.3.2 Dijkstra’s Algorithm9.3.3 Graphs with Negative Edge Costs9.3.4 Acyclic Graphs9.3.5 All-Pairs Shortest Path9.3.6 Shortest-Path Example9.4 Network Flow Problems 9.4.1 A Simple Maximum-Flow Algorithm9.5 Minimum Spanning Tree 9.5.1 Prim’s Algorithm9.5.2 Kruskal’s Algorithm9.6 Applications of Depth-First Search 9.6.1 Undirected Graphs9.6.2 Biconnectivity9.6.3 Euler Circuits9.6.4 Directed Graphs9.6.5 Finding Strong Components9.7 Introduction to NP-Completeness 9.7.1 Easy vs. Hard9.7.2 The Class NP9.7.3 NP-Complete Problems SummaryExercisesReferencesChapter 10 Algorithm Design Techniques 10.1 Greedy Algorithms 10.1.1 A Simple Scheduling Problem10.1.2 Huffman Codes10.1.3 Approximate Bin Packing10.2 Divide and Conquer 10.2.1 Running Time of Divide-and-Conquer Algorithms10.2.2 Closest-Points Problem10.2.3 The Selection Problem10.2.4 Theoretical Improvements for Arithmetic Problems10.3 Dynamic Programming 10.3.1 Using a Table Instead of Recursion10.3.2 Ordering Matrix Multiplications10.3.3 Optimal Binary Search Tree10.3.4 All-Pairs Shortest Path10.4 Randomized Algorithms 10.4.1 Random Number Generators10.4.2 Skip Lists10.4.3 Primality Testing10.5 Backtracking Algorithms 10.5.1 The Turnpike Reconstruction Problem10.5.2 Games SummaryExercisesReferencesChapter 11 Amortized Analysis 11.1 An Unrelated Puzzle11.2 Binomial Queues11.3 Skew Heaps11.4 Fibonacci Heaps 11.4.1 Cutting Nodes in Leftist Heaps11.4.2 Lazy Merging for Binomial Queues11.4.3 The Fibonacci Heap Operations11.4.4 Proof of the Time Bound11.5 Splay Trees SummaryExercisesReferencesChapter 12 Advanced Data Structures and Implementation 12.1 Top-Down Splay Trees12.2 Red-Black Trees 12.2.1 Bottom-Up Insertion12.2.2 Top-Down Red-Black Trees12.2.3 Top-Down Deletion12.3 Treaps12.4 Suffix Arrays and Suffix Trees 12.4.1 Suffix Arrays12.4.2 Suffix Trees12.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees12.5 k-d Trees12.6 Pairing Heaps SummaryExercisesReferencesIndex

1. 4/5

   En bra bok för att lära sig datastrukturer och algoritmer. Det är inte som vissa andra recenssionsskribenter på andra sidor verkar tro en introduktionsbok i Java. För att ha någon egentlig användning av denna bok måste du redan kunna programmera objektorienterat. Det är ingen bok för nybörjare. Däremot om du kan programmera och kan räkna gymnasiematte E (eller universitetsmatte) så kommer du ha ganska stor vinning av att läsa boken.

   Emil C

   15 april 2013