Introduction.
What This Book Is About. What's Different About This Book. Who This Book Is For. What You Need to Know Before You Read This Book. The Software You Need to Use This Book. How This Book Is Organized. Enjoy Yourself! Conventions Used in This Book.
I. INTRODUCING DATA STRUCTURES AND ALGORITHMS.
Hour 1. Overview of Data Structures and Algorithms.
Some Uses for Data Structures and Algorithms. Overview of Data Structures. Overview of Algorithms. Some Initial Definitions. A Quick Introduction to Object-Oriented Programming. New C++ Features. Software Engineering. Summary. Q&A. Workshop.
Hour 2. Arrays.
The Array Workshop Applet. An Array Example. Dividing a Program into Classes. Class Interfaces. Summary. Q&A. Workshop.
Hour 3. Ordered Arrays.
The Ordered Workshop Applet. C++ Code for an Ordered Array. Logarithms. Storing Objects. Big O Notation. Why Not Use Arrays for Everything? Summary. Q&A. Workshop.
Hour 4. The Bubble Sort.
Sorting. Inventing Your Own Sorting Algorithm. Bubble-Sorting the Baseball Players. The bubbleSort Workshop Applet. Implementing C++ Code for a Bubble Sort. Invariants. Efficiency of the Bubble Sort. Summary. Q&A. Workshop.
Hour 5. The Insertion Sort.
Insertion Sort on the Baseball Players. The insertSort Workshop Applet. Implementing the Insertion Sort in C++. Efficiency of the Insertion Sort. Sorting Objects. Another Feature of Sorting Algorithms: Stability. Comparing the Simple Sorts. Summary. Q&A. Workshop.
II. ABSTRACT DATA TYPES.
Hour 6. Stacks.
A Different Way to Think About Data Structure. Understanding Stacks. Implementing a Stack in C++. Stack Example 1: Reversing a Word. Stack Example 2: Delimiter Matching. Efficiency of Stacks. Summary. Q&A. Workshop.
Hour 7. Queues and Priority Queues.
Queues. Priority Queues. Summary. Q&A. Workshop.
Hour 8. Linked Lists.
Understanding Links. The LinkList Workshop Applet. Implementing a Simple Linked List. Finding and Removing Specified Links. The Efficiency of Linked Lists. Summary. Q&A. Workshop.
Hour 9. Abstract Data Types.
A Stack Implemented By a Linked List. Double-Ended Lists. Implementing a Queue Using a Linked List. Data Types and Abstraction. Using ADTs as a Design Tool. Abstract is a Relative Term. Summary. Q&A. Workshop.
Hour 10. Specialized Lists.
Sorted Lists. List Insertion Sort. Doubly Linked Lists. Summary. Q&A. Workshop.
III. RECURSION AND QUICKSORT.
Hour 11. Recursion.
Demonstrating Recursion with Triangular Numbers. Characteristics of Recursive Functions. Demonstrating Recursion with Anagrams. Demonstrating Recursion in a Binary Search. Recursion Versus Stacks. Summary. Q&A. Workshop.
Hour 12. Applied Recursion.
The Towers of Hanoi. Mergesort. Summary. Q&A. Workshop.
Hour 13. Quicksort.
Partitioning. Basic Quicksort. Summary. Q&A. Workshop.
Hour 14. Improving Quicksort.
Problems with Inversely Sorted Data. Handling Small Partitions. Efficiency of Quicksort. Summary. Q&A. Workshop.
IV. TREES.
Hour 15. Binary Trees.
Why Use Binary Trees? What Is a Tree? Basic Binary Tree Operations. Finding a Node. Inserting a Node. Deleting a Node. Summary. Q&A. Workshop.
Hour 16. Traversing Binary Trees.
Traversing the Tree. Finding Maximum and Minimum Values. The Efficiency of Binary Trees. Duplicate Keys. Implementing a Binary Search Tree in C++. Summary. Q&A. Workshop.
Hour 17. Red-Black Trees.
Our Approach to the Discussion. Balanced and Unbalanced Trees. Using the RBTree Workshop Applet. Experimenting. Rotations. Summary. Q&A. Workshop.
Hour 18. Red-Black Tree Insertions.
Inserting a New Node. Deletion. Efficiency of Red-Black Trees. Implementing the Insertion Process. Other Balanced Trees. Summary. Q&A. Workshop.
Hour 19. 2-3-4 Trees.
Introduction to 2-3-4 Trees. The Tree234 Workshop Applet. Summary. Q&A. Workshop.
Hour 20. Implementing 2-3-4 Trees.
Implementing a 2-3-4 Tree in C++. 2-3-4 Trees and Red-Black Trees. Efficiency of 2-3-4 Trees. Summary. Q&A. Workshop.
V. HASH TABLES.
Hour 21. Hash Tables.
Introduction to Hashing. Linear Probing. C++ Code for a Linear Probe Hash Table. Summary. Q&A. Workshop.
Hour 22. Quadratic Probing.
Quadratic Probing. Double Hashing. Efficiency of Open Addressing. Summary. Q&A. Workshop.
Hour 23. Separate Chaining.
The HashChain Workshop Applet. C++ Code for Separate Chaining. Efficiency of Separate Chaining. Open Addressing Versus Separate Chaining. Hash Functions. Summary. Q&A. Workshop.
Hour 24. When to Use What.
General-Purpose Data Structures. Special-Purpose Data Structures. Sorting. Onward.
VI. APPENDIXES.
Appendix A. Quiz Answers.
Hour 1, "Overview of Data Structures and Algorithms." Hour 2, "Arrays." Hour 3, "Ordered Arrays." Hour 4, "The Bubble Sort." Hour 5, "The Insertion Sort." Hour 6, "Stacks." Hour 7, "Queues and Priority Queues." Hour 8, "Linked Lists." Hour 9, "Abstract Data Types." Hour 10, "Specialized Lists." Hour 11, "Recursion." Hour 12, "Applied Recursion." Hour 13, "Quicksort." Hour 14, "Improving Quicksort." Hour 15, "Binary Trees." Hour 16, "Traversing Binary Trees." Hour 17, "Red-Black Trees." Hour 18, "Red-Black Tree Insertions." Hour 19, "2-3-4 Trees." Hour 20, "Implementing 2-3-4 Trees." Hour 21, "Hash Tables." Hour 22, "Quadratic Probing." Hour 23, "Separate Chaining."
Appendix B. How to Run the Workshop Applets and Sample Programs.
The Workshop Applets. The Sample Programs.
Appendix C. Further Reading.
Data Structures and Algorithms. Object-Oriented Programming Languages. Object-Oriented Design and Software Engineering. Programming Style.
Index.
