Data Structures and Algorithm Analysis in Java

by Weiss, Mark A.

• ISBN13: 9780201357547
• ISBN10: 0201357542
• Edition: 2nd
• Format: Paperback
• Copyright: 2007-01-01
• Publisher: Addison Wesley

Summary

In this text, readers are able to look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from several years to less than a second. This new edition contains all the enhancements of the new Java 5.0 code including detailed examples and an implementation of a large subset of the Java 5.0 Collections API. 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 object-based programming and recursion, and some background in discrete math.

Table of Contents

Chapter 1 Introduction	1	(28)
1.1. What's the Book About?	1	(1)
1.2. Mathematics Review	2	(5)
1.2.1. Exponents	2	(1)
1.2.2. Logarithms	3	(1)
1.2.3. Series	3	(2)
1.2.4. Modular Arithmetic	5	(1)
1.2.5. The P Word	5	(2)
1.3. A Brief Introduction to Recursion	7	(4)
1.4. Generic Objects in Java	11	(5)
1.4.1. The IntCell Class	11	(2)
1.4.2. The MemoryCell Class	13	(2)
1.4.3. Implementing Generic findMax	15	(1)
1.5. Exceptions	16	(3)
1.6. Input and Output	19	(5)
1.6.1. Basic Stream Operations	19	(1)
1.6.2. The StringTokenizer Object	20	(1)
1.6.3. Sequential Files	20	(4)
1.7. Code Organization	24	(1)
1.7.1. Packages	24	(1)
1.7.2. The MyInteger Class	24	(1)
1.7.3. Efficiency Considerations	24	(1)
Summary	25	(1)
Exercises	25	(2)
References	27	(2)
Chapter 2 Algorithm Analysis	29	(26)
2.1. Mathematical Background	29	(3)
2.2. Model	32	(1)
2.3. What to Analyze	32	(3)
2.4. Running Time Calculations	35	(13)
2.4.1. A Simple Example	35	(1)
2.4.2. General Rules	35	(2)
2.4.3. Solutions for the Maximum Subsequence Sum Problem	37	(6)
2.4.4. Logarithms in the Running Time	43	(4)
2.4.5. Checking Your Analysis	47	(1)
2.4.6. A Grain of Salt	48	(1)
Summary	48	(1)
Exercises	49	(5)
References	54	(1)
Chapter 3 Lists, Stacks, and Queues	55	(44)
3.1. Abstract Data Types (ADTS)	55	(1)
3.2. The List ADT	56	(19)
3.2.1. Simple Array Implementation of Lists	56	(1)
3.2.2. Linked Lists	57	(1)
3.2.3. Programming Details	58	(5)
3.2.4. Doubly Linked Lists	63	(1)
3.2.5. Circular Linked Lists	63	(1)
3.2.6. Examples	64	(5)
3.2.7. Cursor Implementation of Linked Lists	69	(6)
3.3. The Stack ADT	75	(13)
3.3.1. Stack Model	75	(1)
3.3.2. Implementation of Stacks	76	(5)
3.3.3. Applications	81	(7)
3.4. The Queue ADT	88	(6)
3.4.1. Queue Model	88	(1)
3.4.2. Array Implementation of Queues	89	(3)
3.4.3. Applications of Queues	92	(2)
Summary	94	(1)
Exercises	94	(5)
Chapter 4 Trees	99	(56)
4.1. Preliminaries	99	(6)
4.1.1. Implementation of Trees	100	(1)
4.1.2. Tree Traversals with an Application	101	(4)
4.2. Binary Trees	105	(4)
4.2.1. Implementation	105	(1)
4.2.2. An Example: Expression Trees	106	(3)
4.3. The Search Tree ADT--Binary Search Trees	109	(9)
4.3.1. find	110	(1)
4.3.2. findMin and findMax	111	(1)
4.3.3. insert	112	(1)
4.3.4. remove	113	(3)
4.3.5. Average-Case Analysis	116	(2)
4.4. AVL Trees	118	(12)
4.4.1. Single Rotation	120	(3)
4.4.2. Double Rotation	123	(7)
4.5. Splay Trees	130	(8)
4.5.1. A Simple Idea (That Does Not Work)	130	(2)
4.5.2. Splaying	132	(6)
4.6. Tree Traversals (Revisited)	138	(1)
4.7. B-Trees	139	(5)
Summary	144	(1)
Exercises	145	(7)
References	152	(3)
Chapter 5 Hashing	155	(28)
5.1. General Idea	155	(1)
5.2. Hash Function	156	(2)
5.3. Separate Chaining	158	(4)
5.4. Open Addressing	162	(9)
5.4.1. Linear Probing	162	(2)
5.4.2. Quadratic Probing	164	(6)
5.4.3. Double Hashing	170	(1)
5.5. Rehashing	171	(3)
5.6. Extendible Hashing	174	(2)
Summary	176	(2)
Exercises	178	(3)
References	181	(2)
Chapter 6 Priority Queues (Heaps)	183	(42)
6.1. Model	183	(1)
6.2. Simple Implementations	184	(1)
6.3. Binary Heap	184	(11)
6.3.1. Structure Property	185	(1)
6.3.2. Heap Order Property	186	(2)
6.3.3. Basic Heap Operations	188	(4)
6.3.4. Other Heap Operations	192	(3)
6.4. Applications of Priority Queues	195	(3)
6.4.1. The Selection Problem	195	(1)
6.4.2. Event Simulation	196	(2)
6.5. d-Heaps	198	(1)
6.6. Leftist Heaps	198	(8)
6.6.1. Leftist Heap Property	199	(1)
6.6.2. Leftist Heap Operations	200	(6)
6.7. Skew Heaps	206	(2)
6.8. Binomial Queues	208	(7)
6.8.1. Binomial Queue Structure	208	(1)
6.8.2. Binomial Queue Operations	208	(5)
6.8.3. Implementation of Binomial Queues	213	(2)
Summary	215	(3)
Exercises	218	(4)
References	222	(3)
Chapter 7 Sorting	225	(44)
7.1. Preliminaries	225	(1)
7.2. Insertion Sort	226	(1)
7.2.1. The Algorithm	226	(1)
7.2.2. Analysis of Insertion Sort	226	(1)
7.3. A Lower Bound for Simple Sorting Algorithms	227	(1)
7.4. Shellsort	228	(4)
7.4.1. Worst-Case Analysis of Shellsort	229	(3)
7.5. Heapsort	232	(3)
7.5.1. Analysis of Heapsort	232	(3)
7.6. Mergesort	235	(5)
7.6.1. Analysis of Mergesort	237	(3)
7.7. Quicksort	240	(12)
7.7.1. Picking the Pivot	241	(2)
7.7.2. Partitioning Strategy	243	(2)
7.7.3. Small Arrays	245	(1)
7.7.4. Actual Quicksort Routines	245	(1)
7.7.5. Analysis of Quicksort	246	(4)
7.7.6. A Linear-Expected-Time Algorithm for Selection	250	(2)
7.8. A General Lower Bound for Sorting	252	(2)
7.8.1. Decision Trees	252	(2)
7.9. Bucket Sort	254	(1)
7.10. External Sorting	255	(5)
7.10.1. Why We Need New Algorithms	255	(1)
7.10.2. Model for External Sorting	255	(1)
7.10.3. The Simple Algorithm	255	(2)
7.10.4. Multiway Merge	257	(1)
7.10.5. Polyphase Merge	258	(1)
7.10.6. Replacement Selection	259	(1)
Summary	260	(1)
Exercises	261	(4)
References	265	(4)
Chapter 8 The Disjoint Set ADT	269	(22)
8.1. Equivalence Relations	269	(1)
8.2. The Dynamic Equivalence Problem	270	(1)
8.3. Basic Data Structure	271	(3)
8.4. Smart Union Algorithms	274	(2)
8.5. Path Compression	276	(3)
8.6. Worst Case for Union-by-Rank and Path Compression	279	(6)
8.6.1. Analysis of the Union/Find Algorithm	279	(6)
8.7. An Application	285	(2)
Summary	287	(1)
Exercises	287	(2)
References	289	(2)
Chapter 9 Graph Algorithms	291	(62)
9.1. Definitions	291	(3)
9.1.1. Representation of Graphs	292	(2)
9.2. Topological Sort	294	(3)
9.3. Shortest-Path Algorithms	297	(17)
9.3.1. Unweighted Shortest Paths	299	(5)
9.3.2. Dijkstra's Algorithm	304	(6)
9.3.3. Graphs with Negative Edge Costs	310	(1)
9.3.4. Acyclic Graphs	311	(3)
9.3.5. All-Pairs Shortest Path	314	(1)
9.4. Network Flow Problems	314	(5)
9.4.1. A Simple Maximum-Flow Algorithm	315	(4)
9.5. Minimum Spanning Tree	319	(6)
9.5.1. Prim's Algorithm	320	(3)
9.5.2. Kruskal's Algorithm	323	(2)
9.6. Applications of Depth-First Search	325	(12)
9.6.1. Undirected Graphs	326	(1)
9.6.2. Biconnectivity	327	(4)
9.6.3. Euler Circuits	331	(3)
9.6.4. Directed Graphs	334	(2)
9.6.5. Finding Strong Components	336	(1)
9.7. Introduction to NP-Completeness	337	(4)
9.7.1. Easy vs. Hard	338	(1)
9.7.2. The Class NP	339	(1)
9.7.3. NP-Complete Problems	339	(2)
Summary	341	(1)
Exercises	341	(8)
References	349	(4)
Chapter 10 Algorithm Design Techniques	353	(76)
10.1. Greedy Algorithms	353	(17)
10.1.1. A Simple Scheduling Problem	354	(3)
10.1.2. Huffman Codes	357	(5)
10.1.3. Approximate Bin Packing	362	(8)
10.2. Divide and Conquer	370	(14)
10.2.1. Running Time of Divide and Conquer Algorithms	371	(2)
10.2.2. Closest-Points Problem	373	(4)
10.2.3. The Selection Problem	377	(3)
10.2.4. Theoretical Improvements for Arithmetic Problems	380	(4)
10.3. Dynamic Programming	384	(11)
10.3.1. Using a Table Instead of Recursion	384	(3)
10.3.2. Ordering Matrix Multiplications	387	(2)
10.3.3. Optimal Binary Search Tree	389	(4)
10.3.4. All-Pairs Shortest Path	393	(2)
10.4. Randomized Algorithms	395	(8)
10.4.1. Random Number Generators	396	(3)
10.4.2. Skip Lists	399	(3)
10.4.3. Primality Testing	402	(1)
10.5. Backtracking Algorithms	403	(12)
10.5.1. The Turnpike Reconstruction Problem	405	(4)
10.5.2. Games	409	(6)
Summary	415	(1)
Exercises	415	(8)
References	423	(6)
Chapter 11 Amortized Analysis	429	(24)
11.1. An Unrelated Puzzle	430	(1)
11.2. Binomial Queues	430	(5)
11.3. Skew Heaps	435	(2)
11.4. Fibonacci Heaps	437	(9)
11.4.1. Cutting Nodes in Leftist Heaps	438	(2)
11.4.2. Lazy Merging for Binomial Queues	440	(3)
11.4.3. The Fibonacci Heap Operations	443	(1)
11.4.4. Proof of the Time Bound	443	(3)
11.5. Splay Trees	446	(3)
Summary	449	(1)
Exercises	450	(2)
References	452	(1)
Chapter 12 Advanced Data Structures and Implementation	453	(46)
12.1. Top-Down Splay Trees	453	(7)
12.2. Red-Black Trees	460	(8)
12.2.1. Bottom-Up Insertion	461	(1)
12.2.2. Top-Down Red-Black Trees	462	(5)
12.2.3. Top-Down Deletion	467	(1)
12.3. Deterministic Skip Lists	468	(6)
12.4. AA-Trees	474	(7)
12.5. Treaps	481	(2)
12.6. k-d Trees	483	(3)
12.7. Pairing Heaps	486	(6)
Summary	492	(1)
Exercises	492	(3)
References	495	(4)
Appendix A Some Library Routines	499	(14)
A.1. Classes in Package java.lang	499	(7)
A.1.1. Character	499	(1)
A.1.2. Integer	500	(1)
A.1.3. Object	501	(1)
A.1.4. String	502	(1)
A.1.5. StringBuffer	503	(2)
A.1.6. System	505	(1)
A.1.7. Throwable	506	(1)
A.2. Classes in Package java.io	506	(4)
A.2.1. BufferedReader	506	(1)
A.2.2. BufferedWriter	507	(1)
A.2.3. File	507	(1)
A.2.4. FileReader	508	(1)
A.2.5. FileWriter	508	(1)
A.2.6. InputStreamReader	509	(1)
A.2.7. PrintWriter	509	(1)
A.2.8. PushbackReader	509	(1)
A.3. Classes in Package java.util	510	(3)
A.3.1. Random	510	(1)
A.3.2. StringTokenizer	511	(2)
Appendix B The Collections Library	513	(18)
B.1. Introduction	513	(1)
B.2. Basic Classes	514	(2)
B.2.1. Collection	514	(1)
B.2.2. Iterator	514	(1)
B.2.3. Comparable	515	(1)
B.2.4. Comparator	515	(1)
B.3. Lists	516	(1)
B.3.1. ArrayList vs. LinkedList	516	(1)
B.3.2. Stacks and Queues	517	(1)
B.3.3. ListIterator	517	(1)
B.4. Sets	517	(1)
B.5. Maps	517	(2)
B.5.1. put, get, remove, and contains	518	(1)
B.5.2. Getting a Collection from the Map	518	(1)
B.5.3. Map.Entry Pairs	518	(1)
B.6. Example: Generating a Concordance	519	(4)
B.6.1. Collections API Version	519	(1)
B.6.2. Version Using Package DataStructures	519	(4)
B.7. Example: Shortest-Path Calculation	523	(7)
B.7.1. Collections API Implementation	523	(3)
B.7.2. Version Using Package DataStructures	526	(4)
B.8. Priority Queues	530	(1)
Summary	530	(1)
Index	531