CS61B Textbook Fall 2025
Ctrlk
GitBook Assistant
GitBook Assistant
Thinking...
GitBook Assistant
Good night

I'm here to help you with the docs.

Ctrli
AI Based on your context
  • Fall 2025 Textbook
  • Contributors
  • DISCLAIMER
  • 1. Introduction
  • 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
  • 10. Inheritance II: Subtype Polymorphism, Comparators, Comparables, Generic Functions
  • 11. There is no chapter 11.
  • 12. Inheritance III: Iterators, Object Methods
  • 13. Asymptotics I
  • 14. Disjoint Sets
  • 15. Asymptotics II
  • 16. ADTs and BSTs
  • 17. Asymptotics III
  • 18. B-Trees
  • 19. Red Black Trees
  • 20. Hashing I
  • 21. Hashing II
  • 22. Heaps and Priority Queues
  • 23. Tree Traversals and Graphs
  • 24. Graph Traversals and Implementations
  • 25. Shortest Paths
  • 26. Minimum Spanning Trees
  • 27. Prefix Operations and Tries
  • 28. Software Engineering I
  • 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
  • 31. Quicksort
  • 32. Software Engineering II
  • 33. More Quick Sort, Sorting Summary
  • 34. Software Engineering III
  • 35. Sorting and Algorithmic Bounds
  • 36. Radix Sorts
  • 37. Sorting and Data Structures Conclusion
  • 38. Software Engineering IV
  • 39. Compression and Complexity
  • 40. Compression, Complexity, P = NP
Powered by GitBook
On this page

29. Reductions and Decomposition

By Mihir Mirchandani

29.1 Topological Sorts and DAGs29.2 Shortest Paths on DAGs29.3 Longest Path29.4 Reductions and Decomposition29.5 Exercises
Previous28.5 Summary, ExercisesNext29.1 Topological Sorts and DAGs

Last updated 1 month ago