Stanford CS106B: Programming Abstractions

Created by: Roger Grosse
Intended for: CS106B students, those new to programming

CS106B, "Programming Abstractions," is the second term of Stanford's introductory programming sequence, taught in C++. It follows upon CS106A, "Programming Methodology," which covers the basics of programming itself (functions, control structures, classes, etc.). 106B is about basic data structures and algorithms, and how they can be encapsulated as abstract data types.

This guide is based on the class as it was taught in 2004, the year I took it. Things may have changed since then.

You can find lecture videos for the 2008 version of the course here.

Week 1: C++ language

The first week or so of the course covers aspects of the C++ language which are needed for the course -- mostly by highlighting the differences from Java, the language taught in 106A. The main new concept is pointers, but the language also has different syntax for things like classes and input/output.

If you haven't programmed before, check out our beginning programming roadmap, which covers comparable material to CS106A.

# Weeks 2-3: recursion

The next two weeks focus on recursion, a programming technique where a function calls itself. Some computations, such as the factorial function or the solution to the Tower of Hanoi puzzle, have a natural recursive structure. Trees, an important data structure, are implemented most elegantly using recursive functions.

A lot of programming tasks can be formulated as search problems, where you want to find an object (e.g. an arrangement of queens on a chess board) which satisfies certain constraints (e.g. no queen can attack any other queen). (Or, sometimes, we want to find all such objects.) Recursive backtracking is a kind of brute-force search algorithm which tries to build solutions one component at a time, backtracking whenever the partial solution violates one of the constraints. One of the early assignments in the course is to use backtracking to find all of the words in a Boggle board.