CS61B Textbook Fall 2025
CtrlK
  • Fall 2025 Textbook
  • Contributors
  • DISCLAIMER
  • 1. Introduction
    • 1.1 Your First Java Program
    • 1.2 Java Workflow
    • 1.3 Basic Java Features
  • 2. Defining and Using Classes
  • 3. References, Recursion, and Lists
  • 4. SLLists
  • 5. DLLists
  • 6. Arrays
  • 7. Testing
  • 8. ArrayList
  • 9. Inheritance I: Interface and Implementation Inheritance
    • 9.1 The Problem of Generality
    • 9.2 Hypernyms, Hyponyms, and the Implements Keyword
    • 9.3 Overriding, Interface Inheritance
    • 9.4 Implementation Inheritance, default
    • 9.5 Implementation vs. Interface Inheritance
    • 9.6 Abstract Data Types
  • 10. Inheritance II: Subtype Polymorphism, Comparators, Comparables, Generic Functions
    • 10.1 Polymorphism vs. Function Passing
    • 10.2 Comparables and Comparators
    • 10.3 Writing a Max Function
    • 10.4 Summary
  • 11. There is no chapter 11.
  • 12. Inheritance III: Iterators, Object Methods
    • 12.1 Lists and Sets in Java
    • 12.2 Exceptions
    • 12.3 Iteration
    • 12.4 Object Methods
    • 12.5 Chapter Summary
    • 12.6 Exercises
  • 13. Asymptotics I
    • 13.1 An Introduction to Asymptotic Analysis
    • 13.2 Runtime Characterization
    • 13.3 Checkpoint: An Exercise
    • 13.4 Asymptotic Behavior
    • 13.5 Simplified Analysis Process
    • 13.6 Summary
    • 13.7 Exercises
  • 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. Asymptotics II
    • 15.1 Big Theta
    • 15.2 Big O
    • 15.3 For Loops
    • 15.4 For Loops Print Party
    • 15.5 Summary
    • 15.6 Exercises
  • 16. ADTs and BSTs
    • 16.1 Binary Search Trees
    • 16.2 BST Definitions
    • 16.3 BST Operations
    • 16.4 BSTs as Sets and Maps
    • 16.5 Summary
    • 16.6 Exercises
  • 17. Asymptotics III
    • 17.1 Recursion
    • 17.2 Binary Search
    • 17.3 Mergesort
    • 17.4 B-trees Big O
  • 18. B-Trees
    • 18.1 BST Performance
    • 18.2 Big O vs. Worst Case
    • 18.3 B-Tree Operations
    • 18.4 B-Tree Invariants
    • 18.5 B-Tree Performance
    • 18.6 Summary
    • 18.7 Exercises
  • 19. Red Black Trees
    • 19.1 Rotating Trees
    • 19.2 Creating LLRB Trees
    • 19.3 Inserting LLRB Trees
    • 19.4 Runtime Analysis
    • 19.5 Summary
    • 19.6 Exercises
  • 20. Hashing I
    • 20.1 Introduction to Hashing: Data Indexed Arrays
      • 20.1.1 A first attempt: DataIndexedIntegerSet
      • 20.1.2 A second attempt: DataIndexedWordSet
      • 20.1.3 A third attempt: DataIndexedStringSet
    • 20.2 Hash Code
    • 20.3 "Valid" & "Good" Hashcodes
    • 20.4 Handling Collisions: Linear Probing and External Chaining
    • 20.5 Resizing & Hash Table Performance
    • 20.6 Summary
    • 20.7 Exercises
  • 21. Hashing II
    • 21.1 Hash Table Recap, Default Hash Function
    • 21.2 Distribution By Other Hash Functions
    • 21.3 Contains & Duplicate Items
    • 21.4 Mutable vs. Immutable Types
  • 22. Heaps and Priority Queues
    • 22.1 Priority Queues
    • 22.2 Heaps
    • 22.3 PQ Implementation
    • 22.4 Summary
    • 22.5 Exercises
  • 23. Tree Traversals and Graphs
    • 23.1 Tree Recap
    • 23.2 Tree Traversals
    • 23.3 Graphs
    • 23.4 Graph Problems
  • 24. Graph Traversals and Implementations
    • 24.1 BFS & DFS
    • 24.2 Representing Graphs
    • 24.3 Summary
    • 24.4 Exercises
  • 25. Shortest Paths
    • 25.1 Introduction
    • 25.2 Dijkstra's Algorithm
    • 25.3 A* Algorithm
    • 25.4 Summary
    • 25.5 Exercises
  • 26. Minimum Spanning Trees
    • 26.1 MSTs and Cut Property
    • 26.2 Prim's Algorithm
    • 26.3 Kruskal's Algorithm
    • 26.4 Chapter Summary
    • 26.5 MST Exercises
  • 27. Prefix Operations and Tries
    • 27.1 Introduction to Tries
    • 27.2 Trie Implementation
    • 27.3 Trie String Operations
    • 27.4 Summary
    • 27.5 Exercises
  • 28. Software Engineering I
    • 28.1 Introduction to Software Engineering
    • 28.2 Complexity
    • 28.3 Strategic vs Tactical Programming
    • 28.4 Real World Examples
    • 28.5 Summary, Exercises
  • 29. Reductions and Decomposition
    • 29.1 Topological Sorts and DAGs
    • 29.2 Shortest Paths on DAGs
    • 29.3 Longest Path
    • 29.4 Reductions and Decomposition
    • 29.5 Exercises
  • 30. Basic Sorts
    • 30.1 The Sorting Problem
    • 30.2 Selection Sort & Heapsort
    • 30.3 Mergesort
    • 30.4 Insertion Sort
    • 30.5 Summary
    • 30.6 Exercises
  • 31. Quicksort
    • 31.1 Partitioning
    • 31.2 Quicksort Algorithm
    • 31.3 Quicksort Performance Caveats
    • 31.4 Summary
    • 31.5 Exercises
  • 32. Software Engineering II
    • 32.1 Complexity II
    • 32.2 Sources of Complexity
    • 32.3 Modular Design
    • 32.4 Teamwork
    • 32.5 Exerises
  • 33. More Quick Sort, Sorting Summary
    • 33.1 Quicksort Flavors vs. MergeSort
    • 33.2 Quick Select
    • 33.3 Stability, Adaptiveness, and Optimization
    • 33.4 Summary
    • 33.5 Exercises
  • 34. Software Engineering III
    • 34.1 Candy Crush, SnapChat, and Friends
    • 34.2 The Ledger of Harms
    • 34.3 Your Life
    • 34.4 Summary
    • 34.5 Exercises
  • 35. Sorting and Algorithmic Bounds
    • 35.1 Sorting Summary
    • 35.2 Math Problems Out of Nowhere
    • 35.3 Theoretical Bounds on Sorting
    • 35.4 Summary
    • 35.5 Exercises
  • 36. Radix Sorts
    • 36.1 Counting Sort
    • 36.2 LSD Radix Sort
    • 36.3 MSD Radix Sort
    • 36.4 Summary
    • 36.5 Exercises
  • 37. Sorting and Data Structures Conclusion
    • 37.1 Radix vs. Comparison Sorting
    • 37.2 The Just-In-Time Compiler
    • 37.3 Radix Sorting Integers
    • 37.4 Summary
    • 37.5 Exercises
  • 38. Software Engineering IV
    • 38.1 The end is near
  • 39. Compression and Complexity
    • 39.1 Introduction to Compression
    • 39.2 Prefix-free Codes
    • 39.3 Shannon-Fano Codes
    • 39.4 Huffman Coding Conceptuals
    • 39.5 Compression Theory
    • 39.6 LZW Compression
    • 39.7 Summary
    • 39.8 Exercises
  • 40. Compression, Complexity, P = NP
    • 40.1 Models of Compression
    • 40.2 Optimal Compression, Kolmogorov Complexity
    • 40.3 Space/Time-Bounded Compression
    • 40.4 P = NP
    • 40.5 Exercises
Powered by GitBook
On this page

40. Compression, Complexity, P = NP

40.1 Models of Compression40.2 Optimal Compression, Kolmogorov Complexity40.3 Space/Time-Bounded Compression40.4 P = NP40.5 Exercises
Previous39.8 ExercisesNext40.1 Models of Compression

Last updated 2 days ago