{"version":1,"pages":[{"id":"09AshKGGQ6zLJqgttJba","title":"Contributors","pathname":"/cs61b-textbook","siteSpaceId":"sitesp_6S6Kc","description":"61B Course Staff who helped contribute to this amazing 61Book!"},{"id":"w7jaaRivKx4pU5a5k8Ed","title":"DISCLAIMER","pathname":"/cs61b-textbook/disclaimer","siteSpaceId":"sitesp_6S6Kc","description":""},{"id":"xzi8HsBYVRknNsxdKQIT","title":"1. Introduction","pathname":"/cs61b-textbook/1.-introduction","siteSpaceId":"sitesp_6S6Kc","description":""},{"id":"aHESSwpRA92LvPWxQGTo","title":"1.1 Your First Java Program","pathname":"/cs61b-textbook/1.-introduction/1.1-your-first-java-program","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"1. Introduction"}]},{"id":"ZUJTxQoij0E2011hBa8D","title":"1.2 Java Workflow","pathname":"/cs61b-textbook/1.-introduction/1.2-java-workflow","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"1. Introduction"}]},{"id":"fMcv8eJxQgSzFjMXzDEB","title":"1.3 Basic Java Features","pathname":"/cs61b-textbook/1.-introduction/1.3-basic-java-features","siteSpaceId":"sitesp_6S6Kc","breadcrumbs":[{"label":"1. Introduction"}]},{"id":"K9xubkV6fLoxKjLnOH2Y","title":"1.4 Exercises","pathname":"/cs61b-textbook/1.-introduction/1.4-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"1. Introduction"}]},{"id":"UbyNJlwIbNSbvvAnqOZf","title":"2. Defining and Using Classes","pathname":"/cs61b-textbook/2.-defining-and-using-classes","siteSpaceId":"sitesp_6S6Kc"},{"id":"oIF8cbG5QiJ0LtmKliJb","title":"3. References, Recursion, and Lists","pathname":"/cs61b-textbook/3.-references-recursion-and-lists","siteSpaceId":"sitesp_6S6Kc"},{"id":"SDMU5fbQ1uhasLqqSPdo","title":"4. SLLists","pathname":"/cs61b-textbook/4.-sllists","siteSpaceId":"sitesp_6S6Kc"},{"id":"ODZTpixVW0UD7QAxTYOD","title":"5. DLLists","pathname":"/cs61b-textbook/5.-dllists","siteSpaceId":"sitesp_6S6Kc"},{"id":"22kNGqQmBHjsqgZ6v7kq","title":"6. Arrays","pathname":"/cs61b-textbook/6.-arrays","siteSpaceId":"sitesp_6S6Kc"},{"id":"lj7sxyrOrTBu43B4MBBd","title":"7. Testing","pathname":"/cs61b-textbook/7.-testing","siteSpaceId":"sitesp_6S6Kc"},{"id":"vtjmdPqibFuwlNHLV743","title":"8. ArrayList","pathname":"/cs61b-textbook/8.-arraylist","siteSpaceId":"sitesp_6S6Kc"},{"id":"MX4oUnhHGpgbdDPOdBl1","title":"9. Inheritance I: Interface and Implementation Inheritance","pathname":"/cs61b-textbook/9.-inheritance-i-interface-and-implementation-inheritance","siteSpaceId":"sitesp_6S6Kc"},{"id":"3opc7zaSBb3Bpz8Lue5O","title":"10. Inheritance II: Extends, Casting, Higher Order Functions","pathname":"/cs61b-textbook/10.-inheritance-ii-extends-casting-higher-order-functions","siteSpaceId":"sitesp_6S6Kc","description":"By Vanessa Teo"},{"id":"kDfo7hlAbbkvt0WiX0Qv","title":"10.1 Implementation Inheritance: Extends","pathname":"/cs61b-textbook/10.-inheritance-ii-extends-casting-higher-order-functions/10.1-implementation-inheritance-extends","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"10. Inheritance II: Extends, Casting, Higher Order Functions"}]},{"id":"1JE5eTJgf3zl4a6zPP86","title":"10.2 Encapsulation","pathname":"/cs61b-textbook/10.-inheritance-ii-extends-casting-higher-order-functions/10.2-encapsulation","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"10. Inheritance II: Extends, Casting, Higher Order Functions"}]},{"id":"yRIIS462nsy2GyNSjkYg","title":"10.3 Casting","pathname":"/cs61b-textbook/10.-inheritance-ii-extends-casting-higher-order-functions/10.3-casting","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"10. Inheritance II: Extends, Casting, Higher Order Functions"}]},{"id":"XHS5yLvdu08qtgkXFAAm","title":"10.4 Higher Order Functions in Java","pathname":"/cs61b-textbook/10.-inheritance-ii-extends-casting-higher-order-functions/10.4-higher-order-functions-in-java","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"10. Inheritance II: Extends, Casting, Higher Order Functions"}]},{"id":"3PThsrhJvCXeXFs3rNWd","title":"10.5 Exercises","pathname":"/cs61b-textbook/10.-inheritance-ii-extends-casting-higher-order-functions/10.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"10. Inheritance II: Extends, Casting, Higher Order Functions"}]},{"id":"78dzaCmpDEcvqmItVD9W","title":"11. Inheritance III: Subtype Polymorphism, Comparators, Comparable","pathname":"/cs61b-textbook/11.-inheritance-iii-subtype-polymorphism-comparators-comparable","siteSpaceId":"sitesp_6S6Kc","description":""},{"id":"2YY0ILIRIdrlf0fSarGJ","title":"11.1 A Review of Dynamic Method Selection","pathname":"/cs61b-textbook/11.-inheritance-iii-subtype-polymorphism-comparators-comparable/11.1-a-review-of-dynamic-method-selection","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"11. Inheritance III: Subtype Polymorphism, Comparators, Comparable"}]},{"id":"YFrg9bWCs0dwCc1FWQpI","title":"11.2 Subtype Polymorphism vs Explicit Higher Order Functions","pathname":"/cs61b-textbook/11.-inheritance-iii-subtype-polymorphism-comparators-comparable/11.2-subtype-polymorphism-vs-explicit-higher-order-functions","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"11. Inheritance III: Subtype Polymorphism, Comparators, Comparable"}]},{"id":"cFqkT8OOWhSWXDRpW1yt","title":"11.3 Comparables","pathname":"/cs61b-textbook/11.-inheritance-iii-subtype-polymorphism-comparators-comparable/11.3-comparables","siteSpaceId":"sitesp_6S6Kc","description":"One Sizable Application of Subtype Polymorphism","breadcrumbs":[{"label":"11. Inheritance III: Subtype Polymorphism, Comparators, Comparable"}]},{"id":"Gx0cZPAPLSgdKOwdCcyw","title":"11.4 Comparators","pathname":"/cs61b-textbook/11.-inheritance-iii-subtype-polymorphism-comparators-comparable/11.4-comparators","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"11. Inheritance III: Subtype Polymorphism, Comparators, Comparable"}]},{"id":"1IAbof7sJZooiSS5Zjy1","title":"11.5 Chapter Summary","pathname":"/cs61b-textbook/11.-inheritance-iii-subtype-polymorphism-comparators-comparable/11.5-chapter-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"11. Inheritance III: Subtype Polymorphism, Comparators, Comparable"}]},{"id":"7aL0QrYTrQOR1SzVEfSj","title":"11.6 Exercises","pathname":"/cs61b-textbook/11.-inheritance-iii-subtype-polymorphism-comparators-comparable/11.6-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"11. Inheritance III: Subtype Polymorphism, Comparators, Comparable"}]},{"id":"UMDPYGxNfmRJC0YsueVE","title":"12. Inheritance IV: Iterators, Object Methods","pathname":"/cs61b-textbook/12.-inheritance-iv-iterators-object-methods","siteSpaceId":"sitesp_6S6Kc","description":""},{"id":"5yZUXtA3PaKafDa7nIrD","title":"12.1 Lists and Sets in Java","pathname":"/cs61b-textbook/12.-inheritance-iv-iterators-object-methods/12.1-lists-and-sets-in-java","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"12. Inheritance IV: Iterators, Object Methods"}]},{"id":"encSArvCA7yvv7x3iLrc","title":"12.2 Exceptions","pathname":"/cs61b-textbook/12.-inheritance-iv-iterators-object-methods/12.2-exceptions","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"12. Inheritance IV: Iterators, Object Methods"}]},{"id":"FDfzSBvqtkKWJOHujxR0","title":"12.3 Iteration","pathname":"/cs61b-textbook/12.-inheritance-iv-iterators-object-methods/12.3-iteration","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"12. Inheritance IV: Iterators, Object Methods"}]},{"id":"zlbHFMe9RkLtyu2g5HgY","title":"12.4 Object Methods","pathname":"/cs61b-textbook/12.-inheritance-iv-iterators-object-methods/12.4-object-methods","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"12. Inheritance IV: Iterators, Object Methods"}]},{"id":"zGF883m4gD6qoia4i5Nu","title":"12.5 Chapter Summary","pathname":"/cs61b-textbook/12.-inheritance-iv-iterators-object-methods/12.5-chapter-summary","siteSpaceId":"sitesp_6S6Kc","description":"Summary of the main points in this chapter.","breadcrumbs":[{"label":"12. Inheritance IV: Iterators, Object Methods"}]},{"id":"05W5fx7ouVW9e4EAjHRI","title":"12.6 Exercises","pathname":"/cs61b-textbook/12.-inheritance-iv-iterators-object-methods/12.6-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"12. Inheritance IV: Iterators, Object Methods"}]},{"id":"On1GuhRpHJEMdsb7vJNA","title":"13. Asymptotics I","pathname":"/cs61b-textbook/13.-asymptotics-i","siteSpaceId":"sitesp_6S6Kc","description":"By: Thomas Lee"},{"id":"keWNe1IIgpDDwSLOS72f","title":"13.1 An Introduction to Asymptotic Analysis","pathname":"/cs61b-textbook/13.-asymptotics-i/13.1-an-introduction-to-asymptotic-analysis","siteSpaceId":"sitesp_6S6Kc","description":"We always have to start somewhere.","breadcrumbs":[{"label":"13. Asymptotics I"}]},{"id":"anYZi6X0sgWVVulmoIHo","title":"13.2 Runtime Characterization","pathname":"/cs61b-textbook/13.-asymptotics-i/13.2-runtime-characterization","siteSpaceId":"sitesp_6S6Kc","description":"Techniques for Measuring Computational Cost.","breadcrumbs":[{"label":"13. Asymptotics I"}]},{"id":"1fGEJyFKAlXJiYFjhrtk","title":"13.3 Checkpoint: An Exercise","pathname":"/cs61b-textbook/13.-asymptotics-i/13.3-checkpoint-an-exercise","siteSpaceId":"sitesp_6S6Kc","description":"Some much needed practice.","breadcrumbs":[{"label":"13. Asymptotics I"}]},{"id":"wZj9uiQVGACuzJ6eFhAI","title":"13.4 Asymptotic Behavior","pathname":"/cs61b-textbook/13.-asymptotics-i/13.4-asymptotic-behavior","siteSpaceId":"sitesp_6S6Kc","description":"Be on your best behavior!","breadcrumbs":[{"label":"13. Asymptotics I"}]},{"id":"pxOim75LRUe5woRCLeGz","title":"13.6 Simplified Analysis Process","pathname":"/cs61b-textbook/13.-asymptotics-i/13.6-simplified-analysis-process","siteSpaceId":"sitesp_6S6Kc","description":"It's not that simple.","breadcrumbs":[{"label":"13. Asymptotics I"}]},{"id":"Qlrn4m7Uq8Ek0kl7ueBB","title":"13.7 Big-Theta","pathname":"/cs61b-textbook/13.-asymptotics-i/13.7-big-theta","siteSpaceId":"sitesp_6S6Kc","description":"Not to be confused with Big-O.","breadcrumbs":[{"label":"13. Asymptotics I"}]},{"id":"xTOORBruvynMwXdWCTED","title":"13.8 Big-O","pathname":"/cs61b-textbook/13.-asymptotics-i/13.8-big-o","siteSpaceId":"sitesp_6S6Kc","description":"Not to be confused with Big-Theta.","breadcrumbs":[{"label":"13. Asymptotics I"}]},{"id":"fwqTTAMdipkSNEznsZz2","title":"13.9 Summary","pathname":"/cs61b-textbook/13.-asymptotics-i/13.9-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"13. Asymptotics I"}]},{"id":"uwJRwFF0Dzh2eqbtKwT8","title":"13.10 Exercises","pathname":"/cs61b-textbook/13.-asymptotics-i/13.10-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"13. Asymptotics I"}]},{"id":"x3inTzzfiia5Tc3raX9j","title":"14. Disjoint Sets","pathname":"/cs61b-textbook/14.-disjoint-sets","siteSpaceId":"sitesp_6S6Kc","description":"By Dhruti Pandya and Mihir Mirchandani"},{"id":"HLATbgzCdsfFDNwdevAw","title":"14.1 Introduction","pathname":"/cs61b-textbook/14.-disjoint-sets/14.1-introduction","siteSpaceId":"sitesp_6S6Kc","description":"🚨 New Data Structure Alert 🚨: Disjoint Sets","breadcrumbs":[{"label":"14. Disjoint Sets"}]},{"id":"KjENWO0SSZl5KnJT7llT","title":"14.2 Quick Find","pathname":"/cs61b-textbook/14.-disjoint-sets/14.2-quick-find","siteSpaceId":"sitesp_6S6Kc","description":"Keeping track of set membership...","breadcrumbs":[{"label":"14. Disjoint Sets"}]},{"id":"sUZ7TJClEW5i1XzUaqnL","title":"14.3 Quick Union","pathname":"/cs61b-textbook/14.-disjoint-sets/14.3-quick-union","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"14. Disjoint Sets"}]},{"id":"HExITk5kJ8LPdWAj4JHX","title":"14.4 Weighted Quick Union (WQU)","pathname":"/cs61b-textbook/14.-disjoint-sets/14.4-weighted-quick-union-wqu","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"14. Disjoint Sets"}]},{"id":"DW3NfdLjVIgVnV4W4Q6a","title":"14.5 Weighted Quick Union with Path Compression","pathname":"/cs61b-textbook/14.-disjoint-sets/14.5-weighted-quick-union-with-path-compression","siteSpaceId":"sitesp_6S6Kc","description":"Weighted Quick Union is pretty good, but we can do even better!","breadcrumbs":[{"label":"14. Disjoint Sets"}]},{"id":"BGkYfFuETUexa32ZXShj","title":"14.6 Exercises","pathname":"/cs61b-textbook/14.-disjoint-sets/14.6-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"14. Disjoint Sets"}]},{"id":"buNADJbPWsYviYgCYHmT","title":"15. Asymptotics II","pathname":"/cs61b-textbook/15.-asymptotics-ii","siteSpaceId":"sitesp_6S6Kc","description":"There's no magic shortcut."},{"id":"zeMXqPZaR9LlNhkQc44G","title":"15.1 For Loops","pathname":"/cs61b-textbook/15.-asymptotics-ii/15.1-for-loops","siteSpaceId":"sitesp_6S6Kc","description":"Count, count, count...","breadcrumbs":[{"label":"15. Asymptotics II"}]},{"id":"PovYb8ZA0JZ5HXBWjal0","title":"15.2 Recursion","pathname":"/cs61b-textbook/15.-asymptotics-ii/15.2-recursion","siteSpaceId":"sitesp_6S6Kc","description":"Here we go again...","breadcrumbs":[{"label":"15. Asymptotics II"}]},{"id":"3YUXuZzeMGi1Fk1a0dnu","title":"15.3 Binary Search","pathname":"/cs61b-textbook/15.-asymptotics-ii/15.3-binary-search","siteSpaceId":"sitesp_6S6Kc","description":"hi-lo!","breadcrumbs":[{"label":"15. Asymptotics II"}]},{"id":"EXT1SPFxJPRaaEtQvi2J","title":"15.4 Mergesort","pathname":"/cs61b-textbook/15.-asymptotics-ii/15.4-mergesort","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"15. Asymptotics II"}]},{"id":"IrlTvPd1Tv12jqohSgqp","title":"15.5 Summary","pathname":"/cs61b-textbook/15.-asymptotics-ii/15.5-summary","siteSpaceId":"sitesp_6S6Kc","description":"Wrapping up our asymptotics adventures.","breadcrumbs":[{"label":"15. Asymptotics II"}]},{"id":"c5sFgNSq0GesKGrs0xpx","title":"15.6 Exercises","pathname":"/cs61b-textbook/15.-asymptotics-ii/15.6-exercises","siteSpaceId":"sitesp_6S6Kc","description":"Doing more practices is the best way to gain intuition when it comes to asymptotics!","breadcrumbs":[{"label":"15. Asymptotics II"}]},{"id":"cWIJvpvBuPoGbox0HCdq","title":"16. ADTs and BSTs","pathname":"/cs61b-textbook/16.-adts-and-bsts","siteSpaceId":"sitesp_6S6Kc","description":""},{"id":"KKnYBy8vQfrvMxIBEtp2","title":"16.1 Abstract Data Types","pathname":"/cs61b-textbook/16.-adts-and-bsts/16.1-abstract-data-types","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"16. ADTs and BSTs"}]},{"id":"QzXHgJEZPasn3mb3SZIo","title":"16.2 Binary Search Trees","pathname":"/cs61b-textbook/16.-adts-and-bsts/16.2-binary-search-trees","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"16. ADTs and BSTs"}]},{"id":"ZOY6qf0LKLkl5058upb7","title":"16.3 BST Definitions","pathname":"/cs61b-textbook/16.-adts-and-bsts/16.3-bst-definitions","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"16. ADTs and BSTs"}]},{"id":"kKQJFIemqCkIYOqh4oBf","title":"16.4 BST Operations","pathname":"/cs61b-textbook/16.-adts-and-bsts/16.4-bst-operations","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"16. ADTs and BSTs"}]},{"id":"PAbGQWCnQd3qTKjHNRrE","title":"16.5 BSTs as Sets and Maps","pathname":"/cs61b-textbook/16.-adts-and-bsts/16.5-bsts-as-sets-and-maps","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"16. ADTs and BSTs"}]},{"id":"CBOi4CyykPDdTSK2eE29","title":"16.6 Summary","pathname":"/cs61b-textbook/16.-adts-and-bsts/16.6-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"16. ADTs and BSTs"}]},{"id":"sSkEMKMX38hLHnOnMdTP","title":"16.7 Exercises","pathname":"/cs61b-textbook/16.-adts-and-bsts/16.7-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"16. ADTs and BSTs"}]},{"id":"9xDkjWxi9Edt5A2IL5sr","title":"17. B-Trees","pathname":"/cs61b-textbook/17.-b-trees","siteSpaceId":"sitesp_6S6Kc","description":""},{"id":"KQi8PASuUxlalrWCdQLj","title":"17.1 BST Performance","pathname":"/cs61b-textbook/17.-b-trees/17.1-bst-performance","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"17. B-Trees"}]},{"id":"rlTJ4bUm0lQ5q2zkBc7O","title":"17.2 Big O vs. Worst Case","pathname":"/cs61b-textbook/17.-b-trees/17.2-big-o-vs.-worst-case","siteSpaceId":"sitesp_6S6Kc","description":"A short digression on asymptotics","breadcrumbs":[{"label":"17. B-Trees"}]},{"id":"H1ceSZ0D35SvsrD3tTeU","title":"17.3 B-Tree Operations","pathname":"/cs61b-textbook/17.-b-trees/17.3-b-tree-operations","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"17. B-Trees"}]},{"id":"OJN2Krebxc6Avmv4tolA","title":"17.4 B-Tree Invariants","pathname":"/cs61b-textbook/17.-b-trees/17.4-b-tree-invariants","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"17. B-Trees"}]},{"id":"VA5EX9APfoyg5bXHj6Oa","title":"17.5 B-Tree Performance","pathname":"/cs61b-textbook/17.-b-trees/17.5-b-tree-performance","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"17. B-Trees"}]},{"id":"6UDOxF1IxP4YucN7nmoL","title":"17.6 Summary","pathname":"/cs61b-textbook/17.-b-trees/17.6-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"17. B-Trees"}]},{"id":"dofuV8IUIHvHsJjK8SmH","title":"17.7 Exercises","pathname":"/cs61b-textbook/17.-b-trees/17.7-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"17. B-Trees"}]},{"id":"PRBPm9bH6mEtidUAMa4t","title":"18. Red Black Trees","pathname":"/cs61b-textbook/18.-red-black-trees","siteSpaceId":"sitesp_6S6Kc","description":"Time for some colors."},{"id":"1HAeZjiqtOY3Ym9Pb78J","title":"18.1 Rotating Trees","pathname":"/cs61b-textbook/18.-red-black-trees/18.1-rotating-trees","siteSpaceId":"sitesp_6S6Kc","description":"Just like Ferris Wheels.","breadcrumbs":[{"label":"18. Red Black Trees"}]},{"id":"yqnUEwuHZ7fCUnVkUP8n","title":"18.2 Creating LLRB Trees","pathname":"/cs61b-textbook/18.-red-black-trees/18.2-creating-llrb-trees","siteSpaceId":"sitesp_6S6Kc","description":"Software Engineers? More like Tree Engineers","breadcrumbs":[{"label":"18. Red Black Trees"}]},{"id":"QQCtVwfvlzN3qkvsEQRj","title":"18.3 Inserting LLRB Trees","pathname":"/cs61b-textbook/18.-red-black-trees/18.3-inserting-llrb-trees","siteSpaceId":"sitesp_6S6Kc","description":"Some Tree Maintenance.","breadcrumbs":[{"label":"18. Red Black Trees"}]},{"id":"WaFvXEpoj2uLtvg2Kx15","title":"18.4 Runtime Analysis","pathname":"/cs61b-textbook/18.-red-black-trees/18.4-runtime-analysis","siteSpaceId":"sitesp_6S6Kc","description":"Short and Sweet.","breadcrumbs":[{"label":"18. Red Black Trees"}]},{"id":"WMQJ3iP9OrhLduVg9ZuV","title":"18.5 Summary","pathname":"/cs61b-textbook/18.-red-black-trees/18.5-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"18. Red Black Trees"}]},{"id":"FAq7B32WQoJbYTChs5MD","title":"18.6 Exercises","pathname":"/cs61b-textbook/18.-red-black-trees/18.6-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"18. Red Black Trees"}]},{"id":"WujlGFxRNEMsgnM2zAoW","title":"19. Hashing I","pathname":"/cs61b-textbook/19.-hashing-i","siteSpaceId":"sitesp_6S6Kc","description":"By William Lee and Angel Aldaco"},{"id":"5Th4bUPPPQO6b1xUpB4L","title":"19.1 Introduction to Hashing: Data Indexed Arrays","pathname":"/cs61b-textbook/19.-hashing-i/19.1-introduction-to-hashing-data-indexed-arrays","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"19. Hashing I"}]},{"id":"hIEoMMq71zEx5jJYLbl5","title":"19.1.1 A first attempt: DataIndexedIntegerSet","pathname":"/cs61b-textbook/19.-hashing-i/19.1-introduction-to-hashing-data-indexed-arrays/19.1.1-a-first-attempt-dataindexedintegerset","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"19. Hashing I"},{"label":"19.1 Introduction to Hashing: Data Indexed Arrays"}]},{"id":"j6KOL90E6qjmm8QEzcvb","title":"19.1.2 A second attempt: DataIndexedWordSet","pathname":"/cs61b-textbook/19.-hashing-i/19.1-introduction-to-hashing-data-indexed-arrays/19.1.2-a-second-attempt-dataindexedwordset","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"19. Hashing I"},{"label":"19.1 Introduction to Hashing: Data Indexed Arrays"}]},{"id":"bGcmoXvDFuOiWPquPywA","title":"19.1.3 A third attempt: DataIndexedStringSet","pathname":"/cs61b-textbook/19.-hashing-i/19.1-introduction-to-hashing-data-indexed-arrays/19.1.3-a-third-attempt-dataindexedstringset","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"19. Hashing I"},{"label":"19.1 Introduction to Hashing: Data Indexed Arrays"}]},{"id":"t9eh5phKoRh6UkdDqX5u","title":"19.2 Hash Code","pathname":"/cs61b-textbook/19.-hashing-i/19.2-hash-code","siteSpaceId":"sitesp_6S6Kc","description":"The core mechanism of hashing!","breadcrumbs":[{"label":"19. Hashing I"}]},{"id":"CIUnvPFbfqx5GcF8PVwP","title":"19.3 \"Valid\" & \"Good\" Hashcodes","pathname":"/cs61b-textbook/19.-hashing-i/19.3-valid-and-good-hashcodes","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"19. Hashing I"}]},{"id":"3y8GMfobc7wx51joAZTg","title":"19.4 Handling Collisions: Linear Probing and External Chaining","pathname":"/cs61b-textbook/19.-hashing-i/19.4-handling-collisions-linear-probing-and-external-chaining","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"19. Hashing I"}]},{"id":"3wfKAyhv4e5HNOu3GbF4","title":"19.5 Resizing & Hash Table Performance","pathname":"/cs61b-textbook/19.-hashing-i/19.5-resizing-and-hash-table-performance","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"19. Hashing I"}]},{"id":"tZ8f86eFtO0NE9jwlgbk","title":"19.6 Summary","pathname":"/cs61b-textbook/19.-hashing-i/19.6-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"19. Hashing I"}]},{"id":"SX33GDFEbPK9a60YkMdN","title":"19.7 Exercises","pathname":"/cs61b-textbook/19.-hashing-i/19.7-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"19. Hashing I"}]},{"id":"EUJfec28onb73YRxoitB","title":"20. Hashing II","pathname":"/cs61b-textbook/20.-hashing-ii","siteSpaceId":"sitesp_6S6Kc","description":"By Mihir Mirchandani and William Lee"},{"id":"yqeEF4WPMQwLPw6TVUEB","title":"20.1 Hash Table Recap, Default Hash Function","pathname":"/cs61b-textbook/20.-hashing-ii/20.1-hash-table-recap-default-hash-function","siteSpaceId":"sitesp_6S6Kc","description":"\"The whole point is that we have a bunch of lists that are all short.\" - Professor Hug.","breadcrumbs":[{"label":"20. Hashing II"}]},{"id":"IdBppVnjVAd8tjAkBgro","title":"20.2 Distribution By Other Hash Functions","pathname":"/cs61b-textbook/20.-hashing-ii/20.2-distribution-by-other-hash-functions","siteSpaceId":"sitesp_6S6Kc","description":"HashMaps/Tables have fast lookup times, but behind that \"superpower\" is a hash function.","breadcrumbs":[{"label":"20. Hashing II"}]},{"id":"emLkhWfQz0lrQKfhhyWW","title":"20.3 Contains & Duplicate Items","pathname":"/cs61b-textbook/20.-hashing-ii/20.3-contains-and-duplicate-items","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"20. Hashing II"}]},{"id":"SRLZtdHdRgqTofV7QaVl","title":"20.4 Mutable vs. Immutable Types","pathname":"/cs61b-textbook/20.-hashing-ii/20.4-mutable-vs.-immutable-types","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"20. Hashing II"}]},{"id":"iQI5V3qsodlEtSDJXHEF","title":"21. Heaps and Priority Queues","pathname":"/cs61b-textbook/21.-heaps-and-priority-queues","siteSpaceId":"sitesp_6S6Kc","description":"By Dhruti Pandya and Angel Aldaco"},{"id":"bVFFfTiAtxqZG3IfnNIJ","title":"21.1 Priority Queues","pathname":"/cs61b-textbook/21.-heaps-and-priority-queues/21.1-priority-queues","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"21. Heaps and Priority Queues"}]},{"id":"NLqcaZXh68PQ0tFf0Gq1","title":"21.2 Heaps","pathname":"/cs61b-textbook/21.-heaps-and-priority-queues/21.2-heaps","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"21. Heaps and Priority Queues"}]},{"id":"QoK15qCEg6nr4B7OlQsM","title":"21.3 PQ Implementation","pathname":"/cs61b-textbook/21.-heaps-and-priority-queues/21.3-pq-implementation","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"21. Heaps and Priority Queues"}]},{"id":"QCLMLW0SPjI45AyOl6CP","title":"21.4 Summary","pathname":"/cs61b-textbook/21.-heaps-and-priority-queues/21.4-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"21. Heaps and Priority Queues"}]},{"id":"jstHJzyg9n3uQdTVzo5b","title":"21.5 Exercises","pathname":"/cs61b-textbook/21.-heaps-and-priority-queues/21.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"21. Heaps and Priority Queues"}]},{"id":"C36bdpcdFCBg1uT9QbBH","title":"22. Tree Traversals and Graphs","pathname":"/cs61b-textbook/22.-tree-traversals-and-graphs","siteSpaceId":"sitesp_6S6Kc","description":"By Mihir Mirchandani and Dhruti Pandya"},{"id":"S2sVt2Pps1TpKv76TChO","title":"22.1 Tree Recap","pathname":"/cs61b-textbook/22.-tree-traversals-and-graphs/22.1-tree-recap","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"22. Tree Traversals and Graphs"}]},{"id":"UDHhAgKmR7KkO9gJf2zx","title":"22.2 Tree Traversals","pathname":"/cs61b-textbook/22.-tree-traversals-and-graphs/22.2-tree-traversals","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"22. Tree Traversals and Graphs"}]},{"id":"2jKSTR1eRfsuwHfUtcwQ","title":"22.3 Graphs","pathname":"/cs61b-textbook/22.-tree-traversals-and-graphs/22.3-graphs","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"22. Tree Traversals and Graphs"}]},{"id":"ywhzJsJjIvL7ViTo5iJa","title":"22.4 Graph Problems","pathname":"/cs61b-textbook/22.-tree-traversals-and-graphs/22.4-graph-problems","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"22. Tree Traversals and Graphs"}]},{"id":"fDn7P7bgT7s7LZp1w3Pw","title":"23. Graph Traversals and Implementations","pathname":"/cs61b-textbook/23.-graph-traversals-and-implementations","siteSpaceId":"sitesp_6S6Kc","description":"By William Lee and Mihir Mirchandani"},{"id":"EG2HGlCJEDqVEKQGrm4r","title":"23.1 BFS & DFS","pathname":"/cs61b-textbook/23.-graph-traversals-and-implementations/23.1-bfs-and-dfs","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"23. Graph Traversals and Implementations"}]},{"id":"j8s0e7gJB9VC2Tkpaxxr","title":"23.2 Representing Graphs","pathname":"/cs61b-textbook/23.-graph-traversals-and-implementations/23.2-representing-graphs","siteSpaceId":"sitesp_6S6Kc","description":"How do we create a graph in Java?","breadcrumbs":[{"label":"23. Graph Traversals and Implementations"}]},{"id":"i896Qc9eL3RC3NTDmFpx","title":"23.3 Summary","pathname":"/cs61b-textbook/23.-graph-traversals-and-implementations/23.3-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"23. Graph Traversals and Implementations"}]},{"id":"2AQhUvG38tyYAb154yFG","title":"23.4 Exercises","pathname":"/cs61b-textbook/23.-graph-traversals-and-implementations/23.4-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"23. Graph Traversals and Implementations"}]},{"id":"JyWIGRppLONRnrjgahK5","title":"24. Shortest Paths","pathname":"/cs61b-textbook/24.-shortest-paths","siteSpaceId":"sitesp_6S6Kc","description":"By: Mihir Mirchandani and Teresa Luo"},{"id":"1E4vVKMfi8G0TbHq4WS6","title":"24.1 Introduction","pathname":"/cs61b-textbook/24.-shortest-paths/24.1-introduction","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"24. Shortest Paths"}]},{"id":"DA6Z8wSqK2CR3E6Bn5cs","title":"24.2 Dijkstra's Algorithm","pathname":"/cs61b-textbook/24.-shortest-paths/24.2-dijkstras-algorithm","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"24. Shortest Paths"}]},{"id":"zUjLnnc8dSUTvWLRRtfr","title":"24.3 A* Algorithm","pathname":"/cs61b-textbook/24.-shortest-paths/24.3-a-algorithm","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"24. Shortest Paths"}]},{"id":"4nRS0O2XJBGUA1S51VBd","title":"24.4 Summary","pathname":"/cs61b-textbook/24.-shortest-paths/24.4-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"24. Shortest Paths"}]},{"id":"pRqdWLlG2RdZlpXZu7Uz","title":"24.5 Exercises","pathname":"/cs61b-textbook/24.-shortest-paths/24.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"24. Shortest Paths"}]},{"id":"6qCLZjCZFOmr5yBg5AS4","title":"25. Minimum Spanning Trees","pathname":"/cs61b-textbook/25.-minimum-spanning-trees","siteSpaceId":"sitesp_6S6Kc","description":"By Teresa Luo and Mihir Mirchandani"},{"id":"UCwwhXZT7SrbkB3x8ObV","title":"25.1 MSTs and Cut Property","pathname":"/cs61b-textbook/25.-minimum-spanning-trees/25.1-msts-and-cut-property","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"25. Minimum Spanning Trees"}]},{"id":"HBOLzQF7cJzMkFvkCh4E","title":"25.2 Prim's Algorithm","pathname":"/cs61b-textbook/25.-minimum-spanning-trees/25.2-prims-algorithm","siteSpaceId":"sitesp_6S6Kc","description":"Finding MST.","breadcrumbs":[{"label":"25. Minimum Spanning Trees"}]},{"id":"UB6ka2isf6ve22zfGxnO","title":"25.3 Kruskal's Algorithm","pathname":"/cs61b-textbook/25.-minimum-spanning-trees/25.3-kruskals-algorithm","siteSpaceId":"sitesp_6S6Kc","description":"Finding MST.","breadcrumbs":[{"label":"25. Minimum Spanning Trees"}]},{"id":"jEs2qRnDHcUIrnm6aAAu","title":"25.4 Chapter Summary","pathname":"/cs61b-textbook/25.-minimum-spanning-trees/25.4-chapter-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"25. Minimum Spanning Trees"}]},{"id":"NBollUXRjwPqemsKAKWi","title":"25.5 MST Exercises","pathname":"/cs61b-textbook/25.-minimum-spanning-trees/25.5-mst-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"25. Minimum Spanning Trees"}]},{"id":"HfzrPSVAkzc9Zjtl0Iyd","title":"26. Prefix Operations and Tries","pathname":"/cs61b-textbook/26.-prefix-operations-and-tries","siteSpaceId":"sitesp_6S6Kc","description":"By: Thomas Lee"},{"id":"kWzwjQHY73ZleBxGnXfu","title":"26.1 Introduction to Tries","pathname":"/cs61b-textbook/26.-prefix-operations-and-tries/26.1-introduction-to-tries","siteSpaceId":"sitesp_6S6Kc","description":"Do or do not. There is no Trie.","breadcrumbs":[{"label":"26. Prefix Operations and Tries"}]},{"id":"GWI0uC7EGE4yHJjTno1F","title":"26.2 Trie Implementation","pathname":"/cs61b-textbook/26.-prefix-operations-and-tries/26.2-trie-implementation","siteSpaceId":"sitesp_6S6Kc","description":"Giving it the old college Trie.","breadcrumbs":[{"label":"26. Prefix Operations and Tries"}]},{"id":"JNZYWEM99rzV21IJSmyZ","title":"26.3 Trie String Operations","pathname":"/cs61b-textbook/26.-prefix-operations-and-tries/26.3-trie-string-operations","siteSpaceId":"sitesp_6S6Kc","description":"Trie, Trie again.","breadcrumbs":[{"label":"26. Prefix Operations and Tries"}]},{"id":"8oGtowGUkFNgLYUyGiMI","title":"26.4 Summary","pathname":"/cs61b-textbook/26.-prefix-operations-and-tries/26.4-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"26. Prefix Operations and Tries"}]},{"id":"PR00Wvsj9MSUh8ys5S3K","title":"26.5 Exercises","pathname":"/cs61b-textbook/26.-prefix-operations-and-tries/26.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"26. Prefix Operations and Tries"}]},{"id":"oDZLWgAGH0RPIZ4vilDE","title":"27. Software Engineering I","pathname":"/cs61b-textbook/27.-software-engineering-i","siteSpaceId":"sitesp_6S6Kc","description":"By Aniruth Narayanan"},{"id":"Kyp2VBZLm8SvrwjaTyrr","title":"27.1 Introduction to Software Engineering","pathname":"/cs61b-textbook/27.-software-engineering-i/27.1-introduction-to-software-engineering","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"27. Software Engineering I"}]},{"id":"yMhcVhAiR5zNfULib6hH","title":"27.2 Complexity","pathname":"/cs61b-textbook/27.-software-engineering-i/27.2-complexity","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"27. Software Engineering I"}]},{"id":"6f7fWaeSgyrnzl2DZR8H","title":"27.3 Strategic vs Tactical Programming","pathname":"/cs61b-textbook/27.-software-engineering-i/27.3-strategic-vs-tactical-programming","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"27. Software Engineering I"}]},{"id":"yC8GxOJyOvFpLe5rzo68","title":"27.4 Real World Examples","pathname":"/cs61b-textbook/27.-software-engineering-i/27.4-real-world-examples","siteSpaceId":"sitesp_6S6Kc","breadcrumbs":[{"label":"27. Software Engineering I"}]},{"id":"Lfot4hmiube4DZQVtNrc","title":"27.5 Summary, Exercises","pathname":"/cs61b-textbook/27.-software-engineering-i/27.5-summary-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"27. Software Engineering I"}]},{"id":"it8WFti07sJ8woYuAklq","title":"28. Reductions and Decomposition","pathname":"/cs61b-textbook/28.-reductions-and-decomposition","siteSpaceId":"sitesp_6S6Kc","description":"By Mihir Mirchandani"},{"id":"n9c34yocQpulGU63zR68","title":"28.1 Topological Sorts and DAGs","pathname":"/cs61b-textbook/28.-reductions-and-decomposition/28.1-topological-sorts-and-dags","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"28. Reductions and Decomposition"}]},{"id":"kS04k6adyjZZ9gaQmmgY","title":"28.2 Shortest Paths on DAGs","pathname":"/cs61b-textbook/28.-reductions-and-decomposition/28.2-shortest-paths-on-dags","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"28. Reductions and Decomposition"}]},{"id":"YYCwZwk2KvOjGvfu5Act","title":"28.3 Longest Path","pathname":"/cs61b-textbook/28.-reductions-and-decomposition/28.3-longest-path","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"28. Reductions and Decomposition"}]},{"id":"fsjSzSWfpJ6lvLu7zuF3","title":"28.4 Reductions and Decomposition","pathname":"/cs61b-textbook/28.-reductions-and-decomposition/28.4-reductions-and-decomposition","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"28. Reductions and Decomposition"}]},{"id":"cTpaoAth5jmlwMjLJ2wh","title":"28.5 Exercises","pathname":"/cs61b-textbook/28.-reductions-and-decomposition/28.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"28. Reductions and Decomposition"}]},{"id":"p5qAKlVcoxxJpxkJHza2","title":"29. Basic Sorts","pathname":"/cs61b-textbook/29.-basic-sorts","siteSpaceId":"sitesp_6S6Kc","description":""},{"id":"PXmgWV59cYhqCPNsPjN1","title":"29.1 The Sorting Problem","pathname":"/cs61b-textbook/29.-basic-sorts/29.1-the-sorting-problem","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"29. Basic Sorts"}]},{"id":"M57GFhWEVYqb46RUJLxD","title":"29.2 Selection Sort & Heapsort","pathname":"/cs61b-textbook/29.-basic-sorts/29.2-selection-sort-and-heapsort","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"29. Basic Sorts"}]},{"id":"JagkrGimGHi9aCNl33DY","title":"29.3 Mergesort","pathname":"/cs61b-textbook/29.-basic-sorts/29.3-mergesort","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"29. Basic Sorts"}]},{"id":"JuN2hcmau0I04gYrknJF","title":"29.4 Insertion Sort","pathname":"/cs61b-textbook/29.-basic-sorts/29.4-insertion-sort","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"29. Basic Sorts"}]},{"id":"WMmdtz5MmxuJ0QMT0nN2","title":"29.5 Summary","pathname":"/cs61b-textbook/29.-basic-sorts/29.5-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"29. Basic Sorts"}]},{"id":"I7d1B3UgUCmssLrDs3ca","title":"29.6 Exercises","pathname":"/cs61b-textbook/29.-basic-sorts/29.6-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"29. Basic Sorts"}]},{"id":"ZFjdGVDPvnzoyy7AU8d1","title":"30. Quicksort","pathname":"/cs61b-textbook/30.-quicksort","siteSpaceId":"sitesp_6S6Kc","description":""},{"id":"nz3gFRIxoUJ4aJdorEgy","title":"30.1 Partitioning","pathname":"/cs61b-textbook/30.-quicksort/30.1-partitioning","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"30. Quicksort"}]},{"id":"j9Xn3PG9rojovRpWidJu","title":"30.2 Quicksort Algorithm","pathname":"/cs61b-textbook/30.-quicksort/30.2-quicksort-algorithm","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"30. Quicksort"}]},{"id":"q0uoTOGUOIzZlGCSQ6Tu","title":"30.3 Quicksort Performance Caveats","pathname":"/cs61b-textbook/30.-quicksort/30.3-quicksort-performance-caveats","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"30. Quicksort"}]},{"id":"7SuW4Zj0We02dT4OFTeh","title":"30.4 Summary","pathname":"/cs61b-textbook/30.-quicksort/30.4-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"30. Quicksort"}]},{"id":"siGbzLAy6IaqozBCjH9M","title":"30.5 Exercises","pathname":"/cs61b-textbook/30.-quicksort/30.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"30. Quicksort"}]},{"id":"8pYS2vU8Y54VrXzDILuG","title":"31. Software Engineering II","pathname":"/cs61b-textbook/31.-software-engineering-ii","siteSpaceId":"sitesp_6S6Kc","description":"By Thomas Lee and Mihir Mirchandani"},{"id":"zEg2GnEwKHnUVV8vdudn","title":"31.1 Complexity II","pathname":"/cs61b-textbook/31.-software-engineering-ii/31.1-complexity-ii","siteSpaceId":"sitesp_6S6Kc","description":"Complexity comshmexity.","breadcrumbs":[{"label":"31. Software Engineering II"}]},{"id":"oDiPoYh1XLll83LnMYb6","title":"31.2 Sources of Complexity","pathname":"/cs61b-textbook/31.-software-engineering-ii/31.2-sources-of-complexity","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"31. Software Engineering II"}]},{"id":"VAJ5SnrmvgiD4M2GDvoM","title":"31.3 Modular Design","pathname":"/cs61b-textbook/31.-software-engineering-ii/31.3-modular-design","siteSpaceId":"sitesp_6S6Kc","description":"A tool for managing complexity.","breadcrumbs":[{"label":"31. Software Engineering II"}]},{"id":"VErFaQb97nFjsOiGB8Tm","title":"31.4 Teamwork","pathname":"/cs61b-textbook/31.-software-engineering-ii/31.4-teamwork","siteSpaceId":"sitesp_6S6Kc","description":"\"There is no I in TEAM\"","breadcrumbs":[{"label":"31. Software Engineering II"}]},{"id":"7j6jxTZCNsz8Jvh1Nqbk","title":"31.5 Exerises","pathname":"/cs61b-textbook/31.-software-engineering-ii/31.5-exerises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"31. Software Engineering II"}]},{"id":"7aWKUK4Ae4MvPjRijlwn","title":"32. More Quick Sort, Sorting Summary","pathname":"/cs61b-textbook/32.-more-quick-sort-sorting-summary","siteSpaceId":"sitesp_6S6Kc","description":"By Teresa Luo and Nathalys Pham"},{"id":"tKJl6HPv86IKi2HCoeAF","title":"32.1 Quicksort Flavors vs. MergeSort","pathname":"/cs61b-textbook/32.-more-quick-sort-sorting-summary/32.1-quicksort-flavors-vs.-mergesort","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"32. More Quick Sort, Sorting Summary"}]},{"id":"qiYm3A3KSL1kuQT3atJG","title":"32.2 Quick Select","pathname":"/cs61b-textbook/32.-more-quick-sort-sorting-summary/32.2-quick-select","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"32. More Quick Sort, Sorting Summary"}]},{"id":"O086mDqW7x81P1PEwG0B","title":"32.3 Stability, Adaptiveness, and Optimization","pathname":"/cs61b-textbook/32.-more-quick-sort-sorting-summary/32.3-stability-adaptiveness-and-optimization","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"32. More Quick Sort, Sorting Summary"}]},{"id":"diCoZdF5QIxpIqJLR3Xl","title":"32.4 Summary","pathname":"/cs61b-textbook/32.-more-quick-sort-sorting-summary/32.4-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"32. More Quick Sort, Sorting Summary"}]},{"id":"8DPk0HMg0HGwO87UyTri","title":"32.5 Exercises","pathname":"/cs61b-textbook/32.-more-quick-sort-sorting-summary/32.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"32. More Quick Sort, Sorting Summary"}]},{"id":"YksNtIRqE9LZf5gxTZUs","title":"33. Software Engineering III","pathname":"/cs61b-textbook/33.-software-engineering-iii","siteSpaceId":"sitesp_6S6Kc","description":"By William Lee and Teresa Luo"},{"id":"05lQzjBNgVahOYaNo8Zh","title":"33.1 Candy Crush, SnapChat, and Friends","pathname":"/cs61b-textbook/33.-software-engineering-iii/33.1-candy-crush-snapchat-and-friends","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"33. Software Engineering III"}]},{"id":"Bit0vWVDZaMyyljL19Nv","title":"33.2 The Ledger of Harms","pathname":"/cs61b-textbook/33.-software-engineering-iii/33.2-the-ledger-of-harms","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"33. Software Engineering III"}]},{"id":"B6VW86k2kA63eg6RhpY0","title":"33.3 Your Life","pathname":"/cs61b-textbook/33.-software-engineering-iii/33.3-your-life","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"33. Software Engineering III"}]},{"id":"ErIOVHLYEaqjg32HjFWb","title":"33.4 Summary","pathname":"/cs61b-textbook/33.-software-engineering-iii/33.4-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"33. Software Engineering III"}]},{"id":"rlh8BMN3GIF8Y3D7DMly","title":"33.5 Exercises","pathname":"/cs61b-textbook/33.-software-engineering-iii/33.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"33. Software Engineering III"}]},{"id":"BfoKs96juP4k17J2KRol","title":"34. Sorting  and Algorithmic Bounds","pathname":"/cs61b-textbook/34.-sorting-and-algorithmic-bounds","siteSpaceId":"sitesp_6S6Kc","description":"By William Lee and Angel Aldaco"},{"id":"hmMmX5WP4gb4Taw88QPd","title":"34.1 Sorting Summary","pathname":"/cs61b-textbook/34.-sorting-and-algorithmic-bounds/34.1-sorting-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"34. Sorting  and Algorithmic Bounds"}]},{"id":"DqAnYTdSe00KDSi31JTJ","title":"34.2 Math Problems Out of Nowhere","pathname":"/cs61b-textbook/34.-sorting-and-algorithmic-bounds/34.2-math-problems-out-of-nowhere","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"34. Sorting  and Algorithmic Bounds"}]},{"id":"ir7qZONtqkHPZkemJC7e","title":"34.3 Theoretical Bounds on Sorting","pathname":"/cs61b-textbook/34.-sorting-and-algorithmic-bounds/34.3-theoretical-bounds-on-sorting","siteSpaceId":"sitesp_6S6Kc","description":"What is the best time we can get for sorting?","breadcrumbs":[{"label":"34. Sorting  and Algorithmic Bounds"}]},{"id":"bfFliuTDubjtr6FWk1k6","title":"34.4 Summary","pathname":"/cs61b-textbook/34.-sorting-and-algorithmic-bounds/34.4-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"34. Sorting  and Algorithmic Bounds"}]},{"id":"siAIfbrI0SIqRXNeJqPH","title":"34.5 Exercises","pathname":"/cs61b-textbook/34.-sorting-and-algorithmic-bounds/34.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"34. Sorting  and Algorithmic Bounds"}]},{"id":"xnBNnHFYddjR29cAm4Z0","title":"35. Radix Sorts","pathname":"/cs61b-textbook/35.-radix-sorts","siteSpaceId":"sitesp_6S6Kc","description":"By Mihir Mirchandani"},{"id":"1xqu4H24EYs5oDfOhvn6","title":"35.1 Counting Sort","pathname":"/cs61b-textbook/35.-radix-sorts/35.1-counting-sort","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"35. Radix Sorts"}]},{"id":"gBb045WtBepzzwDDs7zW","title":"35.2 LSD Radix Sort","pathname":"/cs61b-textbook/35.-radix-sorts/35.2-lsd-radix-sort","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"35. Radix Sorts"}]},{"id":"zyqpwkh7WOzziXg0cjSx","title":"35.3 MSD Radix Sort","pathname":"/cs61b-textbook/35.-radix-sorts/35.3-msd-radix-sort","siteSpaceId":"sitesp_6S6Kc","description":"Basic idea: Just like LSD, but sort from leftmost digit towards the right.","breadcrumbs":[{"label":"35. Radix Sorts"}]},{"id":"OJu9ASIyPHfB0tFLzKXm","title":"35.4 Summary","pathname":"/cs61b-textbook/35.-radix-sorts/35.4-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"35. Radix Sorts"}]},{"id":"bsJK1F8XRJwK4TdPs5HB","title":"35.5 Exercises","pathname":"/cs61b-textbook/35.-radix-sorts/35.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"35. Radix Sorts"}]},{"id":"c9qlqdnCDpjjeDFqR50B","title":"36. Sorting and Data Structures Conclusion","pathname":"/cs61b-textbook/36.-sorting-and-data-structures-conclusion","siteSpaceId":"sitesp_6S6Kc","description":"By Mihir Mirchandani and William Lee"},{"id":"zrhNBGVOOqQOi4HTpbOH","title":"36.1 Radix vs. Comparison Sorting","pathname":"/cs61b-textbook/36.-sorting-and-data-structures-conclusion/36.1-radix-vs.-comparison-sorting","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"36. Sorting and Data Structures Conclusion"}]},{"id":"eE4m8CQmjrZ3iylGWfWA","title":"36.2 The Just-In-Time Compiler","pathname":"/cs61b-textbook/36.-sorting-and-data-structures-conclusion/36.2-the-just-in-time-compiler","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"36. Sorting and Data Structures Conclusion"}]},{"id":"ytQMdZxD4UFjaUm7afdd","title":"36.3 Radix Sorting Integers","pathname":"/cs61b-textbook/36.-sorting-and-data-structures-conclusion/36.3-radix-sorting-integers","siteSpaceId":"sitesp_6S6Kc","description":"ft. Obama","breadcrumbs":[{"label":"36. Sorting and Data Structures Conclusion"}]},{"id":"ysf6ejaHJaEAVVHbCCj2","title":"36.4 Summary","pathname":"/cs61b-textbook/36.-sorting-and-data-structures-conclusion/36.4-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"36. Sorting and Data Structures Conclusion"}]},{"id":"76cuXaKMkVYOgj3FtaI6","title":"36.5 Exercises","pathname":"/cs61b-textbook/36.-sorting-and-data-structures-conclusion/36.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"36. Sorting and Data Structures Conclusion"}]},{"id":"0ntbK5YRT7RbGNrwtTEq","title":"37. Software Engineering IV","pathname":"/cs61b-textbook/37.-software-engineering-iv","siteSpaceId":"sitesp_6S6Kc","description":"By Mihir Mirchandani"},{"id":"vMjBeQaoQOsUQy7bWFfW","title":"37.1 The end is near","pathname":"/cs61b-textbook/37.-software-engineering-iv/37.1-the-end-is-near","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"37. Software Engineering IV"}]},{"id":"Pnr2IA3crNHLCsXdR7Ku","title":"38. Compression and Complexity","pathname":"/cs61b-textbook/38.-compression-and-complexity","siteSpaceId":"sitesp_6S6Kc","description":"By Dhruti Pandya and Stella Kaval"},{"id":"R5gqa8BGtiyHrYGTn3z3","title":"38.1 Introduction to Compression","pathname":"/cs61b-textbook/38.-compression-and-complexity/38.1-introduction-to-compression","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"38. Compression and Complexity"}]},{"id":"3bnd3yPCRvC8D1m6ubuR","title":"38.2 Prefix-free Codes","pathname":"/cs61b-textbook/38.-compression-and-complexity/38.2-prefix-free-codes","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"38. Compression and Complexity"}]},{"id":"1EYt4MtctzqcyhLe5y9j","title":"38.3 Shannon-Fano Codes","pathname":"/cs61b-textbook/38.-compression-and-complexity/38.3-shannon-fano-codes","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"38. Compression and Complexity"}]},{"id":"AcON0vmD2PL0gu1DQX0D","title":"38.4 Huffman Coding Conceptuals","pathname":"/cs61b-textbook/38.-compression-and-complexity/38.4-huffman-coding-conceptuals","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"38. Compression and Complexity"}]},{"id":"NXiNue4ruSMXFeV3UJo9","title":"38.5 Compression Theory","pathname":"/cs61b-textbook/38.-compression-and-complexity/38.5-compression-theory","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"38. Compression and Complexity"}]},{"id":"0lfLgSsUuRuDusBIX6Iu","title":"38.6 LZW Compression","pathname":"/cs61b-textbook/38.-compression-and-complexity/38.6-lzw-compression","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"38. Compression and Complexity"}]},{"id":"YgoywTuUw87itK2rx0lh","title":"38.7 Summary","pathname":"/cs61b-textbook/38.-compression-and-complexity/38.7-summary","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"38. Compression and Complexity"}]},{"id":"gQE3I04fk9EHEBObc057","title":"38.8 Exercises","pathname":"/cs61b-textbook/38.-compression-and-complexity/38.8-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"38. Compression and Complexity"}]},{"id":"yvKcARjPKKBIQRX2wWqt","title":"39. Compression, Complexity, P = NP","pathname":"/cs61b-textbook/39.-compression-complexity-p-np","siteSpaceId":"sitesp_6S6Kc","description":""},{"id":"AQAMQLak54QwxDzTX8sm","title":"39.1 Models of Compression","pathname":"/cs61b-textbook/39.-compression-complexity-p-np/39.1-models-of-compression","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"39. Compression, Complexity, P = NP"}]},{"id":"7YH2IHKQAHCHooen82g0","title":"39.2 Optimal Compression, Kolmogorov Complexity","pathname":"/cs61b-textbook/39.-compression-complexity-p-np/39.2-optimal-compression-kolmogorov-complexity","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"39. Compression, Complexity, P = NP"}]},{"id":"j3r5EedoeTq8vKPd3wJt","title":"39.3 Space/Time-Bounded Compression","pathname":"/cs61b-textbook/39.-compression-complexity-p-np/39.3-space-time-bounded-compression","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"39. Compression, Complexity, P = NP"}]},{"id":"k7M8tW7VBogreqFJCM3Q","title":"39.4 P = NP","pathname":"/cs61b-textbook/39.-compression-complexity-p-np/39.4-p-np","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"39. Compression, Complexity, P = NP"}]},{"id":"jlNG3PQ2OflOGGEC2pum","title":"39.5 Exercises","pathname":"/cs61b-textbook/39.-compression-complexity-p-np/39.5-exercises","siteSpaceId":"sitesp_6S6Kc","description":"","breadcrumbs":[{"label":"39. Compression, Complexity, P = NP"}]}]}