Lecture

C++ Libraries - Standard Libraries

This module introduces C++ standard libraries, including:

  • CS106 Libraries and the random.h library
  • String types and operations
  • Differences between C++ string and C string
  • Console I/O operations

Live coding examples demonstrate string manipulation and library usage.


Course Lectures
  • This module introduces the Introduction to Computer Science series at Stanford, discussing the philosophy behind the courses, the benefits of taking CS106B, and the logistical aspects of the course. Students will be introduced to C++ and its fundamental principles.

  • This module discusses the similarities between C++ and Java in terms of syntax, variable types, and control structures. It includes:

    • Example C++ code with comments and preprocessor directives
    • Function prototypes and main() function definitions
    • User-defined data types like enums and records
    • Parameter passing techniques: by value and by reference
  • This module introduces C++ standard libraries, including:

    • CS106 Libraries and the random.h library
    • String types and operations
    • Differences between C++ string and C string
    • Console I/O operations

    Live coding examples demonstrate string manipulation and library usage.

  • C++ Console I/O
    Julie Zelenski

    This module focuses on C++ console and file input/output operations. Topics include:

    • Stream operations
    • Live coding examples for file operations
    • Error handling functions
    • Introduction to object-oriented features in C++
    • Container and template classes

    Students will learn how to manage data input and output effectively in their programs.

  • Client Use of Templates
    Julie Zelenski

    This module explores client use of templates in C++. Key topics include:

    • The Vector Class and its client interface
    • Type safety in templates
    • Grid and Stack classes
    • Learning new APIs through CS106B library documentation

    Students will gain insights into how templates enhance code reusability and safety.

  • More Containers
    Julie Zelenski

    This module continues the discussion on data containers in C++. It covers:

    • Map Class and its uses
    • Live coding examples with Map and Set classes
    • Iterators and higher-level operations on Set
    • Fundamental differences between Set and other container types

    Students learn about various container classes and their practical applications.

  • This module discusses the concept of treating functions as data. Key topics include:

    • Generic and specific plot functions
    • Client callback functions
    • Nested ADTs (Abstract Data Types)
    • Recursion and recursive decomposition

    Students will engage in live coding examples to solidify their understanding of these concepts.

  • This module addresses common mistakes encountered in programming, particularly in recursion. Topics include:

    • Concatenating strings and its pitfalls
    • Functional recursion and examples like calculating powers
    • Palindromes and binary search
    • Managing base cases efficiently

    Students will learn to identify and avoid these common programming errors.

  • Thinking Recursively
    Julie Zelenski

    Students will learn to think recursively in this module, covering:

    • Differences between procedural and functional recursion
    • Fractal graphics and their code implementations
    • Classic recursion examples like Hanois Towers
    • Permutations and their recursive structures

    Live demos will illustrate the principles discussed in the module.

  • Refresh: Permute Code
    Julie Zelenski

    This module revisits permutation code, focusing on:

    • Tree of recursive calls
    • Live demos testing different cases
    • Strategies for eliminating duplicates
    • Exhaustive recursion and backtracking techniques

    Students will learn how to apply these techniques in practical coding scenarios.

  • Backtracking Pseudocode
    Julie Zelenski

    This module introduces backtracking pseudocode, emphasizing:

    • Sudoku and cryptarithmetic problem-solving
    • Identifying patterns in problem-solving
    • Introduction to pointers and single pointer operations

    Students will engage in practical examples to understand backtracking concepts effectively.

  • Pointer Movie
    Julie Zelenski

    This module focuses on pointer operations in C++. Key aspects include:

    • Pointer memory diagrams and basic operations
    • Dynamic arrays and their relationship with pointers
    • Recursive data structures
    • Live demos working with linked lists

    Students will gain a comprehensive understanding of pointers and their applications in programming.

  • Coding with Linked List
    Julie Zelenski

    This module dives into coding with linked lists, discussing:

    • Printing linked lists and using recursion
    • Memory deallocation for linked lists
    • Prepend function and passing pointers by reference
    • Comparative analysis of arrays and linked lists
    • Inserting elements in sorted order

    Students will engage in practical coding exercises to strengthen their skills with linked lists.

  • Selection Sort
    Julie Zelenski

    This module covers sorting algorithms, including:

    • Selection Sort with live demos
    • Insertion Sort analysis and comparison
    • Quadratic vs linear growth of algorithms
    • Merge Sort and its execution
    • Introduction to Quick Sort and its strategies

    Students will learn how to analyze and compare various sorting techniques.

  • This module focuses on the partitioning strategy for Quick Sort, discussing:

    • Quick Sort code and its execution
    • Bad split examples and strategies to avoid them
    • Execution time tabulation and performance comparisons
    • Towards generic functions and templates

    Students will engage in live demos to understand the implications of different input scenarios.

  • This module explores the implementation of sort templates with callbacks, focusing on:

    • Supplying and using callback functions
    • Class design principles in object-oriented programming
    • Encapsulation, constructors, and destructors in classes

    Students will learn about internal vs external representation and how to maintain object consistency.

  • Abstract Data Types
    Julie Zelenski

    This module introduces Abstract Data Types (ADTs) and their importance in programming. Key topics include:

    • The concept of abstraction and its applications
    • Creating and managing the Vector Class
    • Dynamic memory management and private data members
    • Operations for inserting and removing elements

    Students will learn to design and implement their own abstract data types.

  • This module discusses the rules of template implementation in C++, including:

    • Consequences of contiguous memory allocation
    • Implementing the Stack class and its member functions
    • Midterm post mortem for assessing student progress

    Students will gain insights into effective template design and implementation strategies.

  • This module is a recap of vector-based implementation for stacks, discussing:

    • Linked list implementation for stacks
    • Push/pop function analysis
    • Queue implementation and alternative methods
    • Case studies including text editor implementations

    Students will engage in live coding to compare different implementations.

  • Buffer: Vector vs Stack
    Julie Zelenski

    This module compares buffer implementations using vectors and stacks, focusing on:

    • Cursor design and linked list buffer management
    • Comparative analysis of doubly linked lists
    • Space-time trade-offs in data structures
    • Implementing maps and performance implications

    Students will learn to evaluate the efficiency of different buffer strategies.

  • Map as Vector
    Julie Zelenski

    This module discusses the implementation of maps as vectors, introducing:

    • Binary Search Trees (BST) and their operations
    • Tree traversals and adding to BST
    • Impacts of tree height and balancing

    Students will engage in practical coding to implement and evaluate maps as trees.

  • Pathfinder Demo
    Julie Zelenski

    This module presents a Pathfinder demo, exploring:

    • Graph representations and implementation strategies
    • Depth First Search (DFS) and Breadth First Search (BFS) algorithms
    • Graph search algorithms and weighted arcs

    Students will learn to implement and analyze graph algorithms in C++.

  • This module compares different map implementations, focusing on:

    • Hashtable concepts and hash functions
    • Handling hash collisions and performance implications
    • Real-world examples of hashing strategies

    Students will engage in live demos to solidify their understanding of hashing in programming.

  • Lexicon Case Study
    Julie Zelenski

    This module features a Lexicon case study, highlighting:

    • Implementing lexicons as sorted vectors, BSTs, and hash tables
    • Exploring letter tries and directed acyclic word graphs (DAWG)
    • Dynamic arrays of children and exploiting prefixes

    Students will analyze and implement efficient lexicon data structures.

  • Final Showdown
    Julie Zelenski

    This module concludes with a final showdown, discussing:

    • Design considerations and runtime performance
    • Memory usage and code complexity
    • Trade-offs between different data structures
    • Key takeaways and future considerations after CS106B

    Students will reflect on their learning journey and prepare for future programming challenges.

  • This module features a guest lecture by Keith Schwarz, covering:

    • A history of the C++ language and its philosophy
    • Alternatives to genlib.h and other CS106 headers
    • Standard Template Library (STL) algorithms and features
    • Operator overloading and next steps in programming

    Students will gain insights into C++'s evolution and its practical applications in programming.