Winda

Stanford CS106B: Programming Abstractions

Contents · 54

  1. 01-About the CS106 Series at StanfordIntroduces CS106B’s focus on programming abstractions, core topics, course philosophy, student resources and logistics, and the role of C++.
  2. 01-About the CS106 Series at StanfordOverview of Stanford’s CS106 programming sequence, including course goals, prerequisites, logistics, and CS106B topics such as recursion, algorithms, data structures, and abstraction.
  3. 02-Similarity between C++ and JavaCovers C++ and Java syntax similarities, program structure, enumerations and records, parameter passing, and standard and CS106 libraries.
  4. 02-Similarity between C++ and JavaIntroduces similarities and differences between C++ and Java syntax, then walks through a sample C++ program and its include files.
  5. 03-C++ LibrariesC++ libraries, strings, and console I/O, including string operations, C-string conversions, random utilities, and stream classes.
  6. 03-C++ LibrariesIntroduces C++ standard and CS106 libraries, how headers and implementations work, naming conventions, and the random library’s role in generating pseudorandom behavior.
  7. 04-C++ Console I/OCovers C++ console and file streams, class-library abstractions, using Scanner to tokenize input, and Vector containers and templates.
  8. 04-C++ Console I/OC++ stream input and output, including extraction errors, console helpers, and opening files with input and output streams.
  9. 05-Client Use of TemplatesIntroduces the Vector, Grid, Stack, and Queue template classes, their operations and use cases, type specialization, and nested templates.
  10. 05-Client Use of TemplatesExplains C++ templates and type-safe vector usage, including vectors’ list behavior, indexing, resizing, insertion, removal, and deep copying.
  11. 06-More ContainersIntroduces Map and Set containers, including key-value lookup, unique elements, iterators, comparison, and common operations.
  12. 06-More ContainersExplains associative containers, focusing on maps: key-value lookup, insertion and replacement, membership checks, and common applications.
  13. 07-Seeing Functions as DataUsing functions as data and client callbacks for plotting and custom comparisons, with an introduction to recursive problem solving.
  14. 07-Seeing Functions as DataExplains passing functions as data in C++ to create a generic plotting function that accepts different single-argument functions.Passing functions as data in C++ to build a generic plotting function that works with sine, square root, and other single-argument functions.
  15. 08-Solving Problems RecursivelyFunctional recursion, base and recursive cases, recursive exponentiation, palindrome checking, binary search, and counting combinations with n-choose-k.
  16. 08-Solving Problems RecursivelyIntroduces recursive function vocabulary and functional recursion’s base and recursive cases, then begins a C++ example for computing powers.
  17. 09-Thinking RecursivelyExplains recursive problem decomposition, base cases, procedural recursion, fractals, Towers of Hanoi, and generating permutations.
  18. 09-Thinking RecursivelyExplains recursive problem decomposition patterns and procedural recursion, including fractal graphics and how processing order affects results.
  19. 10-Recursion and BacktrackingCovers recursive permutation and subset generation, exhaustive search, backtracking, and the N-Queens problem.
  20. 10-Recursion and BacktrackingExplains recursive string permutation generation, including choosing characters, recursion order, and wrapper functions.
  21. 11-Backtracking PseudocodeExplains recursive backtracking with Sudoku and cryptarithmetic examples, heuristic pruning, and pointer basics, uses, and pitfalls.
  22. 11-Backtracking PseudocodeIntroduces recursive backtracking through a Sudoku solver, showing how candidate choices are tested, undone, and revisited when they lead to dead ends.
  23. 12-Pointer MovieCovers pointer allocation, assignment, and deletion; recursive structs; and building and traversing linked lists.
  24. 12-Pointer MovieExplains pointer initialization and dereferencing, stack versus heap memory, pointer assignment and aliasing, and the need to deallocate heap memory.
  25. 13-Coding with Linked ListRecursive linked-list traversal and insertion, pointer references, array-versus-list tradeoffs, and introductory Big-O analysis.
  26. 13-Coding with Linked ListLinked list construction and traversal, including inserting entries at the front, tracing pointer updates, printing the list, and observing reversed insertion order.Build and traverse linked lists by prepending entries, tracing pointer updates, and printing nodes in reverse insertion order.
  27. 14-Algorithm AnalysisAnalyzes algorithm performance using statement counts, big-O notation, cases, and recurrences; introduces sorting with selection sort.
  28. 14-Algorithm AnalysisIntroduces algorithm design and analysis, comparing approaches by time, memory, accuracy, and implementation effort, with sorting and counting examples.
  29. 15-Selection SortCovers selection and insertion sort algorithms and their performance, quadratic growth, mergesort’s divide-and-conquer analysis, and the quicksort idea.
  30. 15-Selection SortDemonstrates selection sort through animations and sound, explaining how it finds and moves minimum elements and its comparison and movement costs.
  31. 16-Partitioning for QuicksortExplains Quicksort’s partitioning, performance, and pivot choices, then introduces function templates, instantiation errors, and generic sorting.
  32. 16-Partitioning for QuicksortIntroduces quicksort’s divide-and-conquer strategy, pivot selection, and partitioning, contrasting its approach with merge sort.
  33. 17-Sort Template with CallbackExplains generic sorting with comparator callbacks and introduces OOP class design, interfaces, encapsulation, member functions, constructors, destructors, and object consistency.
  34. 17-Sort Template with CallbackTemplate functions for selection sort, client-supplied comparison callbacks, and default ordering with operator comparison.
  35. 18-Abstract Data TypesExplains ADTs through abstraction barriers, public interfaces, private implementation details, and the benefits of encapsulation and implementation independence.
  36. 18-Abstract Data TypesExplains abstraction and abstract data types through the client–implementer boundary, using queues and the Lexicon class to illustrate interfaces and encapsulation.
  37. 19-Rules of Template ImplementationCovers C++ template implementation rules and compilation, finishing a Vector implementation, and implementing stacks and queues.
  38. 19-Rules of Template ImplementationConverting a C++ class to a template: updating type names and member definitions, testing with multiple types, and handling template compilation by including implementation code in the header.
  39. 20-Stack and Queue ImplementationsCompares vector- and stack-based text editor buffers, their cursor operations and performance, then introduces a linked-list implementation.
  40. 20-Stack and Queue ImplementationsCompares vector- and linked-list-based stack implementations, focusing on push and pop efficiency and where to place the stack’s top in the list.
  41. 21-Buffer: Vector vs StackExplains editor buffer implementations using vectors, stacks, linked lists, and chunklists, then introduces map operations and the tradeoffs of vector-based storage.
  42. 21-Buffer: Vector vs StackExplains how to represent a text buffer with a linked list, including cursor positioning and insertion trade-offs.
  43. 22-Map as VectorBinary search trees, tree traversals, and implementing Map lookup and insertion with a tree. Covers runtime, tree balance, degenerate cases, and AVL trees.
  44. 22-Map as VectorIntroduces binary search trees, showing how ordered left and right subtrees enable faster searches than linked lists and avoid the vector’s insertion-shuffling cost. Defines basic tree terminology and structure.
  45. 23-Pathfinder DemoIntroduces graph terminology and representations, then explains depth-first and breadth-first traversal, visited-node tracking, graph search problems, and weighted arcs.
  46. 23-Pathfinder DemoIntroduces graphs as nodes connected by directed or undirected edges, with examples including airline routes, word ladders, course prerequisites, flowcharts, and mazes.
  47. 24-Compare Map ImplementationsCompares vector, sorted-vector, BST, and hash map performance, space costs, hash functions, collisions, chaining, and rehashing; introduces generic map keys and set implementation strategies.
  48. 24-Compare Map ImplementationsHash tables and hashing for fast key-value search and insertion, with comparisons to vectors and binary search trees.
  49. 25-Lexicon Case StudyCompares sorted vectors, binary search trees, hash tables, and trie representations for word lexicons, including their operation costs and memory use. Covers trie space-saving designs and suffix sharing with directed acyclic graphs.
  50. 25-Lexicon Case StudyExplains the Lexicon’s requirements and compares data structures for word lookup, prefix search, insertion, and space efficiency.
  51. 26-Final ShowdownFinal exam expectations and preparation, dynamic data structures, implementation tradeoffs, and options for further study after the course.
  52. 26-Final ShowdownFinal exam preparation, data structures, and design trade-offs in choosing abstractions such as stacks, queues, maps, and vectors.
  53. 27-Guest Lecturer: Keith SchwarzIntroduces C++ philosophy and history, its role beyond CS106B, and how its features build on core programming concepts.
  54. 27-Guest Lecturer: Keith SchwarzIntroduces C++’s purpose and design, connects CS 106B programming concepts to broader problem-solving, and previews the language’s history and core features.