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).

Chapter 1 Introduction 1
1.1 Whats 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 Pre-Java 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 ADTBinary 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 Average-Case 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 B-Trees 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 ...