Winda

Berkeley CS 61B: Data Structures

Contents · 87

  1. 01-Welcome to 61B, Intro to JavaIntroduces CS 61B’s focus on implementing data structures, writing efficient code, and developing software engineering skills, including testing, debugging, and Java tools.
  2. 01-Welcome to 61B, Intro to JavaIntroduces CS61B’s goals, course structure and logistics, Java fundamentals, static typing, compilation, and development tools such as IntelliJ and Git.
  3. 02-Defining and Using Classes, ListsCourse logistics, attendance and exam-recovery policies, plus an introduction to Java classes and maps.
  4. 02-Defining and Using Classes, ListsCovers Java class definitions and instantiation, constructors, instance variables and methods, and course announcements, with an introduction to lists and arrays.
  5. 03-Lists, Arrays, Maps, ReferencesCovers Java generics for lists, retrieving list elements, and modernizing list declarations with the diamond operator.
  6. 03-Lists, Arrays, Maps, ReferencesCovers modern Java lists and generics, arrays, and maps, including how to create and access them and why Java offers multiple collection types.
  7. 04-TestingIntroduces software testing, emphasizing writing and evaluating tests to verify your own code.
  8. 04-TestingProject 0 release guidance, course announcements, and Lecture 4’s introduction to unit testing with Truth through a selection sort example.
  9. 05-Packages, Recursion, IntListsExplains Java packages, canonical class names, imports, class paths, and the difference between public and package-private access.
  10. 05-Packages, Recursion, IntListsJava packages, imports, class visibility, and CLASSPATH, followed by list abstractions, recursion strategies, and building linked lists with IntList.
  11. 06-SLLists, Nested Classes, Sentinel NodesExplains singly linked lists, SLList operations, encapsulation and nested classes, efficient size tracking, and sentinel nodes for handling empty lists and preserving invariants.
  12. 06-SLLists, Nested Classes, Sentinel NodesAdds `addFirst` and `getFirst` to `SLList`, demonstrating how a list wrapper simplifies adding and retrieving the first item compared with a naked recursive data structure.
  13. 06-SLLists, Nested Classes, Sentinel NodesCaching list size in an SLList enables constant-time size queries and illustrates how object-oriented structures manage metadata.
  14. 06-SLLists, Nested Classes, Sentinel NodesIntroduces SLList as a wrapper around IntNode, hiding null references and recursive-list implementation details from users.
  15. 06-SLLists, Nested Classes, Sentinel NodesExplains data-structure invariants using sentinel-based linked lists, including how they simplify reasoning and help prevent bugs.
  16. 06-SLLists, Nested Classes, Sentinel NodesAdds an item to the end of an SLList and computes its size using a recursive helper method.
  17. 06-SLLists, Nested Classes, Sentinel NodesRebrands the recursive IntList as a simple IntNode with item and next fields, preparing to restore its list functionality.
  18. 06-SLLists, Nested Classes, Sentinel NodesFixing `addLast` for empty singly linked lists by handling null first nodes and avoiding null-pointer errors.
  19. 06-SLLists, Nested Classes, Sentinel NodesIntroduces sentinel nodes in linked lists to eliminate empty-list special cases and simplify addFirst, getFirst, and addLast.
  20. 06-SLLists, Nested Classes, Sentinel NodesJava’s private access modifier hides implementation details, protects class invariants, and distinguishes stable public interfaces from changeable internals. The discussion also introduces nesting a class.
  21. 07-DLLists, Basic AListsIntroduces doubly linked lists and array-based lists, building on linked-list nodes and comparing how these data structures work.
  22. 07-DLLists, Basic AListsExplains doubly linked lists, sentinel designs, and how backward links enable fast operations at both ends; also introduces generic lists and array-based lists.
  23. 08-Resizing and Circular ArraysAnnouncements on coursework deadlines, project two, and midterm logistics, plus an introduction to CS Mentors and a return to reflections on A-Lists.
  24. 08-Resizing and Circular ArraysCovers array-list advantages and tradeoffs, resizing arrays to support growth, generic lists, and strategies for optimizing performance.
  25. 09-Interface and Implementation InheritanceIntroduces Java method overloading and motivates inheritance as a way to share code across different list implementations.
  26. 09-Interface and Implementation InheritanceExplains Java interface and implementation inheritance, method overloading and overriding, default methods, and collection abstract data types.
  27. 10-Iterators, Iterables, and EqualsMidterm 1 format, signup, and preparation, including coding problems, testing, tools, and practice resources.
  28. 10-Iterators, Iterables, and EqualsCovers Midterm 1 scheduling, format, and preparation, plus Java iterators, enhanced for loops, and ArraySet iteration and object methods.
  29. 11-Subtype Polymorphism, Comparables, ComparatorsIntroduces polymorphism and function passing, using Python operator overloading to compare objects and previewing idiomatic Java’s reliance on polymorphism.
  30. 11-Subtype Polymorphism, Comparables, ComparatorsIntroduces polymorphism and function passing, then explains Java’s Comparable interface for defining object ordering and comparison.
  31. 12-Review, Midterm PracticeMidterm 1 logistics and PrairieLearn practice, including test-writing workflow and linked-list problems.
  32. 12-Review, Midterm PracticeMidterm practice covering add-at-index for linked lists, test-driven development, edge-case testing, and running tests in VS Code.
  33. 13-Asymptotics IIntroduces runtime and space efficiency, using a count-evens example to explain how execution time grows with input size.
  34. 13-Asymptotics IExplains runtime growth, operation counting, ignoring constants and lower-order terms, and Big Theta and Big O notation.
  35. 14-Disjoint SetsIntroduces disjoint sets and their connect and connected operations, reviewing Big O and Big Theta and illustrating how elements join into groups.
  36. 14-Disjoint SetsCovers disjoint-set operations and dynamic connectivity, comparing list, quick-find, quick-union, weighted union, and path-compression implementations with asymptotic analysis.
  37. 15-Asymptotics IILecture 15 covers percolation, disjoint sets, code style expectations, and lecture attendance and participation.
  38. 15-Asymptotics IIReviews Big Theta and Big O, introduces Big Omega as a lower bound, and begins analyzing runtimes of nested loops and disjoint-set operations.
  39. 16-Asymptotics IIIMidterm expectations, retakes, and exam logistics; learning through challenge, course goals, and office hours.
  40. 16-Asymptotics IIIAnalyzes recursive runtimes by counting calls and summing work, using a branching recursion example to derive exponential growth.
  41. 17-Sets, Extends, and BSTsJava class inheritance with `extends`, adding methods to existing classes, and the distinction between `extends` and `implements`.
  42. 17-Sets, Extends, and BSTsJava class inheritance and the TimeSeries ADT, followed by binary search trees and implementing Set and Map operations.
  43. 18-B-TreesInserting values into binary search trees, insertion order’s effect on height, and constructing worst-case and minimum-height trees.
  44. 18-B-TreesExplains BST height and runtime bounds, then introduces B-trees, their invariants, terminology, node splitting, and worst-case performance.
  45. 19-Red-Black TreesIntroduces B-trees and 2-3 trees, explaining their node capacities, search behavior, balance, and logarithmic performance.
  46. 19-Red-Black TreesExplains tree rotations as a way to rebalance binary search trees, then introduces left-leaning red-black trees and their connection to 2-3 trees.
  47. 20-Heaps, Priority Queues, and Tree RepresentationsExplains how rotations preserve the one-to-one mapping between 2–3 trees and left-leaning red-black trees during insertion.
  48. 20-Heaps, Priority Queues, and Tree RepresentationsPriority queue applications and implementations, including heaps, heap operations, tree and array representations, and runtime comparisons.
  49. 21-Tree and Graph TraversalsIntroduces graph traversals after reviewing LLRBs and tree representations, including array-based heaps and parent-index calculation.
  50. 21-Tree and Graph TraversalsTree and graph definitions, tree traversal orders, and depth-first search for graph connectivity.
  51. 22-Graph Traversals and ImplementationsDepth-first search traversal and how parent-edge pointers record a path from the start vertex to a reachable target.
  52. 22-Graph Traversals and ImplementationsCovers graph APIs and representations, DFS and BFS path-finding implementations, and their runtime and memory tradeoffs.
  53. 23-Shortest PathsIntroduces breadth-first search for shortest paths, using a queue to explore vertices in order of distance from the source.
  54. 23-Shortest PathsExplains why BFS fails for weighted graphs, shortest-path trees and edge relaxation, then introduces Dijkstra’s algorithm, its runtime, and A* heuristics.
  55. 24-Minimum Spanning TreesDefines spanning trees and minimum spanning trees, with examples and the cut property.
  56. 24-Minimum Spanning TreesDefines minimum spanning trees, contrasts them with shortest-path trees, and introduces the cut property and Prim’s and Kruskal’s algorithms, including their implementations and runtimes.
  57. 25-Directed Acyclic GraphsAn instructor discusses using Claude agents to review student design projects, the tool’s speed and cost, and concerns about AI’s effect on learning.
  58. 25-Directed Acyclic GraphsExplains DAGs, topological sorting, and shortest- and longest-path algorithms, with examples and graph reductions.
  59. 26-Hashing IIntroduces hashing and hash tables as efficient Map and Set implementations, comparing their motivation with array-based and search-tree approaches.
  60. 26-Hashing IExplains hash tables, including buckets, reduction functions, separate chaining, hash codes, and their performance tradeoffs.
  61. 27-Hashing IIReviews hash tables, including hash codes, array indexing, separate chaining, and resizing, alongside binary search tree operation times.
  62. 27-Hashing IICovers hash table indexing, collisions, resizing, item distribution, and designing effective hashCode functions.
  63. 28-TriesExplains immutability in Java, aliasing through arrays, defensive copying, and why `final` alone does not prevent mutable contents from changing.
  64. 28-TriesIntroduces tries for string-keyed sets and maps, covering character-per-node structure, shared prefixes, implementation strategies, runtime, string operations, and autocomplete.
  65. 29-Software Engineering IJohn Ousterhout discusses software design, maintainable and beautiful code, and advice for exploring computer science careers.
  66. 29-Software Engineering IExplains software complexity and how modular design, deep interfaces, clear names, comments, and simpler code make systems easier to understand and modify.
  67. 30-Midterm 2 ReviewExam philosophy, grading curves, target averages, academic pressure, and balancing coursework with life.
  68. 31-Software Engineering II - BYOW WarmupCompares approaches to sorting strings by frequency in Project 4D, including manual iteration, priority queues, sorting, comparators, and lambdas.
  69. 31-Software Engineering II - BYOW WarmupCovers lessons from Proj4CD and introduces Project 5’s 2D world generator, player movement, and interactive-world design.
  70. 32-Basic SortsIntroduces sorting and its uses, then defines total order through trichotomy and transitivity, with divisibility as a counterexample.
  71. 32-Basic SortsDefines sorting and inversions, then introduces selection sort, heapsort (naive and in-place), and mergesort.
  72. 33-Insertion Sort and Intro to QuicksortStudent Q&A on humanities electives, Data 8 and Data 100, workload and difficulty for CS, math, and physics courses, and a recommendation for Dutch.
  73. 33-Insertion Sort and Intro to QuicksortExplains naive and in-place insertion sort, their runtime, and quicksort’s partitioning strategy.
  74. 34-QuicksortExplains Quicksort’s pivot-based partitioning, including naive and Hoare methods, recursive sorting, runtime analysis, worst-case avoidance, and Quickselect.
  75. 34-QuicksortA computer science lecture reviews quicksort, explaining pivots, partitioning, and how placing each element in its final sorted position sorts the array. It also discusses department budget constraints and shrinking class capacity.
  76. 35-Sorting and Algorithmic BoundsIntroduces comparison-based sorting and analyzes its theoretical lower bounds, reviewing sorting algorithms and applications such as finding medians, duplicates, and three-sum.Introduces sorting applications and reviews common sorting algorithms before examining theoretical lower bounds on sorting.
  77. 35-Sorting and Algorithmic BoundsIntroduces asymptotic bounds and proves that comparison sorting requires Ω(N log N) time in the worst case. Covers the decision-tree argument and examples illustrating the sorting lower bound.
  78. 36-Radix SortsSorting stability preserves the relative order of equivalent items. Stable sorting by digits introduces a way to sort integers one digit at a time.
  79. 36-Radix SortsExplains counting sort, sorting stability, and digit-by-digit radix sorting, including LSD and MSD approaches.
  80. 37-The Social Implications of ComputingA lecture on tech careers, consumer product design, engagement mechanics in games, and the social impact of algorithms.
  81. 37-The Social Implications of ComputingExplores the social impact of computing through tech careers, engagement-driven design, educational platforms, and AI’s growing influence on society and work.
  82. 38-Software Engineering III - AI in Software EngineeringAI’s role in software engineering, from code explanation and generation to debugging, alongside the skills students need to work effectively in an AI-driven industry.
  83. 38-Software Engineering III - AI in Software EngineeringExplores AI-assisted software development, how AI changes the engineering workflow, and why planning, clear specifications, and verification remain essential.
  84. 39-CompressionLossless compression, prefix-free codes, and assigning shorter bit sequences to frequent symbols.
  85. 39-CompressionExplains lossless compression, prefix-free codes, Shannon–Fano and Huffman coding, compression limits, and LZW-style methods.
  86. 40-Summary, FunReviews 61B’s core concepts, including Java, data structures, runtime analysis, implementations, and graph algorithms.
  87. 40-Summary, FunReviews core CS 61B topics and discusses students’ future learning, careers, and course reflections.