Learn CS

CS 61B Data Structures

Website

Overview

The CS 61 series is an introduction to computer science, with particular emphasis on software and machines from a programmer’s point of view. CS 61A covered high-level approaches to problem-solving, providing you with a variety of ways to organize solutions to programming problems as compositions of functions, collections of objects, or sets of rules. In CS 61B, we move to a somewhat more detailed (and to some extent, more basic) level of programming.

In 61A, the correctness of a program was our primary goal. In CS61B, we’re concerned also with engineering. An engineer, it is said, is someone who can do for a dime what any fool can do for a dollar. Much of 61B will be concerned with the tradeoffs in time and memory for a variety of methods for structuring data. We’ll also be concerned with the engineering knowledge and skills needed to build and maintain moderately large programs.

Prerequisite: CS 61A Structure and Interpretation of Computer Programs

Schedule

  1. Intro, Hello World Java vid1 vid2 slides guide
  2. Defining and Using Classes video slides guide
  3. References, Recursion, and Lists video slides guide
  4. SLLists, Nested Classes, Sentinel Nodes video slides guide
  5. DLLists, Arrays video slides guide
  6. ALists, Resizing, vs. SLists video slides guide
  7. Testing video slides guide
  8. Inheritance, Implements video slides guide
  9. Extends, Casting, Higher Order Functions video slides guide
  10. Subtype Polymorphism vs. HoFs video slides guide
  11. Exceptions, Iterators, Object Methods video slides guide
  12. Coding in the Real World, Review slides
  13. Asymptotics I video slides guide
  14. Disjoint Sets video slides guide
  15. Asymptotics II video slides guide
  16. ADTs, Sets, Maps, BSTs video slides guide
  17. B-Trees (2-3, 2-3-4 Trees) video slides guide
  18. Red Black Trees video slides guide
  19. Hashing video slides guide
  20. Heaps and PQs video slides guide
  21. Prefix Operations and Tries video slides guide
  22. Range Searching and Multi-Dimensional Data video slides guide
  23. Tree and Graph Traversals video slides guide
  24. Graph Traversals and Implementations video slides guide
  25. Shortest Paths video slides guide
  26. Minimum Spanning Trees video slides guide
  27. Reductions and Decomposition video slides
  28. No Lecture
  29. Basic Sorts video slides guide
  30. Quick Sort video slides guide
  31. Software Engineering I video slides guide
  32. More Quick Sort, Sorting Summary video slides guide
  33. Sorting and Algorithmic Bounds video slides guide
  34. Software Engineering II video slides guide
  35. Radix Sorts video slides guide
  36. Sorting and Data Structures Conclusion video slides guide
  37. Software Engineering III video slides guide
  38. Compression video slides guide
  39. Compression, Complexity, and P=NP? video slides
  40. Summary, Fun slides

Assignment

What's Next