SUMMARY.md

Table of contents

• Spring 2026 Textbook
• Contributors
• DISCLAIMER
• 1. Introduction
  • 1.1 Your First Java Program
  • 1.2 Basic Java Features
  • 1.3 Java Workflow
• 2. Defining and Using Classes
• 3. References, Recursion, and Lists
• 4. Testing
• 5. SLLists
• 6. DLLists and Arrays
• 7. Resizing ArrayList
• 8. Inheritance I: Interface and Implementation Inheritance
  • 8.1 The Problem of Generality
  • 8.2 Hypernyms, Hyponyms, and the Implements Keyword
  • 8.3 Overriding, Interface Inheritance
  • 8.4 Implementation Inheritance, default
  • 8.5 Implementation vs. Interface Inheritance
  • 8.6 Abstract Data Types
• 9. Inheritance II: Subtype Polymorphism, Comparators, Comparables, Generic Functions
  • 9.1 Polymorphism vs. Function Passing
  • 9.2 Comparables and Comparators
  • 9.3 Writing a Max Function
  • 9.4 Summary
• 10. Inheritance III: Iterators, Object Methods
  • 10.1 Lists and Sets in Java
  • 10.2 Exceptions
  • 10.3 Iteration
  • 10.4 Object Methods
  • 10.5 Chapter Summary
  • 10.6 Exercises
• 11. Asymptotics I
  • 11.1 An Introduction to Asymptotic Analysis
  • 11.2 Runtime Characterization
  • 11.3 Checkpoint: An Exercise
  • 11.4 Asymptotic Behavior
  • 11.5 Simplified Analysis Process
  • 11.6 Summary
  • 11.7 Exercises
• 12. Asymptotics II
  • 12.1 Big Theta
  • 12.2 Big O
  • 12.3 For Loops
  • 12.4 For Loops Print Party
  • 12.5 Summary
  • 12.6 Exercises
• 13. Asymptotics III
  • 13.1 Recursion
  • 13.2 Binary Search
  • 13.3 Mergesort
  • 13.4 B-trees Big O
• 14. Disjoint Sets
  • 14.1 Introduction
  • 14.2 Quick Find
  • 14.3 Quick Union
  • 14.4 Weighted Quick Union (WQU)
  • 14.5 Weighted Quick Union with Path Compression
  • 14.6 Exercises
• 15. Binary Search Trees
  • 15.1 Binary Search Trees
  • 15.2 BST Definitions
  • 15.3 BST Operations
  • 15.4 BSTs as Sets and Maps
  • 15.5 BST Performance
  • 15.6 Big O vs. Worst Case
  • 15.7 Summary
  • 15.8 Exercises
• 16. B-Trees
  • 16.1 B-Tree Operations
  • 16.2 B-Tree Invariants
  • 16.3 B-Tree Performance
  • 16.4 Summary
  • 16.5 Exercises
• 17. Red Black Trees
  • 17.1 Rotating Trees
  • 17.2 Creating LLRB Trees
  • 17.3 Inserting LLRB Trees
  • 17.4 Runtime Analysis
  • 17.5 Summary
  • 17.6 Exercises
• 18. Heaps and Priority Queues
  • 18.1 Priority Queues
  • 18.2 Heaps
  • 18.3 PQ Implementation
  • 18.4 Summary
  • 18.5 Exercises
• 19. Tree Traversals and Graphs
  • 19.1 Tree Recap
  • 19.2 Tree Traversals
  • 19.3 Graphs
  • 19.4 Graph Problems
• 20. Graph Traversals and Implementations
  • 20.1 BFS & DFS
  • 20.2 Representing Graphs
  • 20.3 Summary
  • 20.4 Exercises
• 21. Shortest Paths
  • 21.1 Introduction
  • 21.2 Dijkstra's Algorithm
  • 21.3 A* Algorithm
  • 21.4 Summary
  • 21.5 Exercises
• 22. Minimum Spanning Trees
  • 22.1 MSTs and Cut Property
  • 22.2 Prim's Algorithm
  • 22.3 Kruskal's Algorithm
  • 22.4 Chapter Summary
  • 22.5 MST Exercises
• 23. Reductions and Decomposition
  • 23.1 Topological Sorts and DAGs
  • 23.2 Shortest Paths on DAGs
  • 23.3 Longest Path
  • 23.4 Reductions and Decomposition
  • 23.5 Exercises
• 24. Hashing I
  • 24.1 Introduction to Hashing: Data Indexed Arrays
    • 24.1.1 A first attempt: DataIndexedIntegerSet
    • 24.1.2 A second attempt: DataIndexedWordSet
    • 24.1.3 A third attempt: DataIndexedStringSet
  • 24.2 Hash Code
  • 24.3 "Valid" & "Good" Hashcodes
  • 24.4 Handling Collisions: Linear Probing and External Chaining
  • 24.5 Resizing & Hash Table Performance
  • 24.6 Summary
  • 24.7 Exercises
• 25. Hashing II
  • 25.1 Hash Table Recap, Default Hash Function
  • 25.2 Distribution By Other Hash Functions
  • 25.3 Contains & Duplicate Items
  • 25.4 Mutable vs. Immutable Types
• 26. Prefix Operations and Tries
  • 26.1 Introduction to Tries
  • 26.2 Trie Implementation
  • 26.3 Trie String Operations
  • 26.4 Summary
  • 26.5 Exercises
• 27. Software Engineering I
  • 27.1 Introduction to Software Engineering
  • 27.2 Complexity
  • 27.3 Strategic vs Tactical Programming
  • 27.4 Real World Examples
  • 27.5 Summary, Exercises
• 28. Software Engineering II
  • 28.1 Complexity II
  • 28.2 Sources of Complexity
  • 28.3 Modular Design
  • 28.4 Teamwork
  • 28.5 Exerises
• 29. Basic Sorts
  • 29.1 The Sorting Problem
  • 29.2 Selection Sort & Heapsort
  • 29.3 Mergesort
  • 29.4 Insertion Sort
  • 29.5 Summary
  • 29.6 Exercises
• 30. Quicksort
  • 30.1 Partitioning
  • 30.2 Quicksort Algorithm
  • 30.3 Quicksort Performance Caveats
  • 30.4 Summary
  • 30.5 Exercises
• 31. More Quick Sort, Sorting Summary
  • 31.1 Quicksort Flavors vs. MergeSort
  • 31.2 Quick Select
  • 31.3 Stability, Adaptiveness, and Optimization
  • 31.4 Summary
  • 31.5 Exercises
• 32. Sorting and Algorithmic Bounds
  • 32.1 Sorting Summary
  • 32.2 Math Problems Out of Nowhere
  • 32.3 Theoretical Bounds on Sorting
  • 32.4 Summary
  • 32.5 Exercises
• 33. Radix Sorts
  • 33.1 Counting Sort
  • 33.2 LSD Radix Sort
  • 33.3 MSD Radix Sort
  • 33.4 Summary
  • 33.5 Exercises
• 34. Sorting and Data Structures Conclusion
  • 34.1 Radix vs. Comparison Sorting
  • 34.2 The Just-In-Time Compiler
  • 34.3 Radix Sorting Integers
  • 34.4 Summary
  • 34.5 Exercises
• 35. Software Engineering III
  • 35.1 Candy Crush, SnapChat, and Friends
  • 35.2 The Ledger of Harms
  • 35.3 Your Life
  • 35.4 Summary
  • 35.5 Exercises
• 36. Software Engineering IV
  • 36.1 The end is near
• 37. Compression and Complexity
  • 37.1 Introduction to Compression
  • 37.2 Prefix-free Codes
  • 37.3 Shannon-Fano Codes
  • 37.4 Huffman Coding Conceptuals
  • 37.5 Compression Theory
  • 37.6 LZW Compression
  • 37.7 Summary
  • 37.8 Exercises
• 38. Compression, Complexity, P = NP
  • 38.1 Models of Compression
  • 38.2 Optimal Compression, Kolmogorov Complexity
  • 38.3 Space/Time-Bounded Compression
  • 38.4 P = NP
  • 38.5 Exercises