CS131 Refresher Tutorial

1

Value, Reference, and Pointer Semantics

Why this matters

This refresher is meant to help you review concepts from CS31, CS32, and CS35L before we start CS131. We’ll begin with parameter passing: which changes inside a function affect the caller, and why?

This is optional practice. You don’t need to turn anything in. The tests and knowledge checks provide feedback; you can continue without passing them and return to a problem later.

🎯 You will learn to

Work out whether an assignment inside a function is visible to the caller
Tell the difference between changing a pointer and changing what it points to
Write the reference and pointer versions of a function that modifies its argument

The Point class

Everything on this step uses the following Point class, which makes all of its members public for simplicity:

class Point {
public:
    Point(int x = 0, int y = 0) { x_ = x; y_ = y; }
    void display() const { cout << "(" << x_ << ", " << y_ << ")" << endl; }
    int x_, y_;
};

Here’s how each version below gets used:

Point pt(10, 10);
modify(pt);       // or modify(&pt) for the pointer versions
pt.display();

Each version sets x_ to 50 on line A. Line B either assigns a new Point(20, 30) to an object or reassigns the local pointer. Compare both the parameter declaration and the left side of line B:

// Version A - pass by value
void modify(Point p) {
    p.x_ = 50;          // line A
    p = Point(20, 30);  // line B
}

// Version B - pass by reference
void modify(Point &p) {
    p.x_ = 50;          // line A
    p = Point(20, 30);  // line B
}

// Version C - pass by pointer, reassigning the pointer
void modify(Point *p) {
    p->x_ = 50;             // line A
    p = new Point(20, 30);  // line B
}

// Version D - pass by pointer, writing through the pointer
void modify(Point *p) {
    p->x_ = 50;         // line A
    *p = Point(20, 30); // line B
}

✏️ Predict before you read on

For each version, figure out what will be printed and try to explain why you get that result. Don’t just compile and run the code to get answers, but try to understand what’s really happening under the hood.

Write down all four answers before you open the reveal. Each one is:

(a) (10, 10) — the caller sees neither line
(b) (50, 10) — the caller sees line A but not line B
(c) (20, 30) — the caller sees both lines

Versions C and D are the interesting ones. Their parameter lists are identical and their line A is identical. Only line B is different.

Reveal — all four answers

A prints (10, 10). Why? Because when we pass by value we make a copy of the original pt variable and pass that in. Both lines modify a temporary copy, and the copy dies at the closing brace, so no changes are made to the original pt.

B prints (20, 30). Why? Because when you pass by reference, the formal parameter p is essentially an alias for the passed-in variable pt. Any change, including assigning a whole new value to p, modifies the original pt as if you'd referred to it instead of p.

C prints (50, 10). Why? Because here we're passing the address of pt into modify. Think of pt as a house that holds some stuff (the values x_ and y_), and think of p as a piece of paper where we wrote down the address of that house. Line A uses the address on the paper to find the house and change its x_ to 50, so that change sticks. But line B only scratches out the address on our paper and writes down the address of a brand new house. That does nothing to the contents of the original house, so pt.y_ is still 10. We also have a memory leak, since we never delete the memory we allocated with new.

D prints (20, 30). Why? Because *p = Point(20, 30); creates a temporary new Point at 20, 30 and copies its contents into the memory pointed to by p, which is the pt variable. Using our analogy again: we read the address on the paper, drive to that address (that's what the * means), and update the contents of the house.

C and D are the whole lesson. p = ... changes where the arrow points. *p = ... changes what it points at.

🔧 Now write two of them yourself

Use Run to compile and run the current C++17 program in the browser. The output panel shows compiler messages and anything your program prints. After editing, choose Run again to compile the new version. If compilation fails, fix the first reported error and try again.

Open param_passing.cpp. modify_by_value is already written for you as a worked example. Fill in the other two so that both leave the caller’s point at (20, 30).

modify_by_reference — you pick how the parameter is declared.
modify_by_pointer — the parameter is already Point *p. Reach the caller’s object on every assignment. Don’t point p somewhere else.

The supplied main() creates a separate Point(10, 10) for each call and displays the result. Run the starter once, then compare its output with your prediction as you complete the two functions. You can change the starting coordinates in main() to try more examples.

Check your work

Choose Test My Work to compile and call each function on separate Point(10, 10) and Point(-4, 7) objects. The automatic checks verify that:

modify_by_value leaves the caller’s coordinates unchanged.
modify_by_reference leaves the caller’s point at (20, 30).
modify_by_pointer, called with the point’s address, leaves it at (20, 30).

The checks inspect the actual coordinates, so changing the display format or printing the expected answers cannot change the result. They do not require particular parameter names or a particular way of assigning the coordinates. You can continue without passing these checks.

For each assignment, explain whether its left side names a local copy, the caller’s object, or the local pointer. This reflection is for your own review; the automatic checks do not grade your explanation.

Starter files

cs131/param_passing.cpp

#include <iostream>
using namespace std;

class Point {
public:
    Point(int x = 0, int y = 0) {
        x_ = x;
        y_ = y;
    }
    void display() const {
        cout << "(" << x_ << ", " << y_ << ")" << endl;
    }

    int x_, y_;
};

// Version A - by value. Finished for you.
// The caller still sees (10, 10) after this returns.
void modify_by_value(Point p) {
    p.x_ = 50;
    p = Point(20, 30);
}

// Version B - by reference.
// Goal: after this returns, the CALLER's point is (20, 30).
// You choose how the parameter is bound.
void modify_by_reference(Point p) {
}

// Version D - by pointer, written so the caller sees both lines.
// Goal: after this returns, the CALLER's point is (20, 30).
// The parameter is already a pointer. Do not make it point elsewhere.
void modify_by_pointer(Point *p) {
}

int main() {
    Point by_value(10, 10);
    modify_by_value(by_value);
    cout << "by value: ";
    by_value.display();

    Point by_reference(10, 10);
    modify_by_reference(by_reference);
    cout << "by reference: ";
    by_reference.display();

    Point by_pointer(10, 10);
    modify_by_pointer(&by_pointer);
    cout << "by pointer: ";
    by_pointer.display();
    return 0;
}

Solution

cs131/param_passing.cpp

#include <iostream>
using namespace std;

class Point {
public:
    Point(int x = 0, int y = 0) {
        x_ = x;
        y_ = y;
    }
    void display() const {
        cout << "(" << x_ << ", " << y_ << ")" << endl;
    }

    int x_, y_;
};

// Version A - by value. Finished for you.
// The caller still sees (10, 10) after this returns.
void modify_by_value(Point p) {
    p.x_ = 50;
    p = Point(20, 30);
}

// Version B - by reference. `p` is a second NAME for the caller's
// object, so both statements land on the caller's point.
void modify_by_reference(Point &p) {
    p.x_ = 50;
    p = Point(20, 30);
}

// Version D - by pointer. Every assignment goes THROUGH the
// address, so the caller sees both statements.
void modify_by_pointer(Point *p) {
    p->x_ = 50;
    *p = Point(20, 30);
}

int main() {
    Point by_value(10, 10);
    modify_by_value(by_value);
    cout << "by value: ";
    by_value.display();

    Point by_reference(10, 10);
    modify_by_reference(by_reference);
    cout << "by reference: ";
    by_reference.display();

    Point by_pointer(10, 10);
    modify_by_pointer(&by_pointer);
    cout << "by pointer: ";
    by_pointer.display();
    return 0;
}

Both bodies do exactly what modify_by_value does: set x_, then replace the whole object. The reference version changes the parameter binding. The pointer version also uses dereferencing so that its assignments reach the object.

Point &p makes p an alias. There is no second object, so p = Point(20, 30) really is pt = Point(20, 30).

Point *p gives you a copy of an address. Both p->x_ and *p follow that address to the caller’s object, so both reach pt. The tempting wrong move is p = new Point(20, 30), which only rewrites the address on our piece of paper. That leaves pt at (50, 10) and leaks the memory we allocated.

Keep versions C and D in mind for the next two steps. Python has exactly one parameter passing scheme, and it behaves like one of these four.

Step 1 — Knowledge Check

Practice target: 80% (optional)

1. A function is declared void bump(Point *p) and its whole body is the single line p = new Point(0, 0);. The caller runs:

Point pt(7, 7);
bump(&pt);
pt.display();

What gets printed, and what happens to the heap object?

(7, 7); the heap object is leaked
(0, 0); the heap object becomes pt
Assigning to p only rewrites the address the parameter holds. pt still lives at the old address and never gets written to, so its members keep their original values.
(7, 7); the heap object is freed at the closing brace
C++ frees local variables at the closing brace, but new allocates on the heap. Only a matching delete frees that, and there isn’t one here.
(0, 0); the heap object is leaked
The leak half is right, but not the printed half. The only thing the assignment changed was the parameter’s own copy of the address.

The parameter is a copy of an address. Overwriting it points the local copy somewhere else and leaves the caller’s object alone, and the new Point is never freed, so it leaks.

2. You want resize to be able to replace the caller’s whole Point, and you’d rather write resize(pt) at the call site than resize(&pt). Which parameter list does that?

void resize(Point &p)
void resize(Point p)
A by-value parameter is a copy. Replacing it replaces the copy, and the copy is thrown away when the function returns.
void resize(Point *p)
This one can replace the caller’s object, but only through *p, and it forces the call site to say resize(&pt), which is what the question rules out.
void resize(const Point &p)
const is the problem. It makes the alias read-only, so the compiler rejects any assignment to p or its members.

A non-const reference parameter is an alias for the caller’s object, so assigning to it replaces that object. And references need no & at the call site.

3. void f(Point *p) is called as f(&pt), with Point pt(1, 1). Consider each option independently as the entire function body. Which bodies change the caller’s point? (select all that apply)

p->y_ = 9;
This is the most common write of all. The arrow follows the address to the caller’s object before assigning, so the caller sees it.
*p = Point(4, 4);
This is the version C versus version D difference again. Dereferencing on the left side copies the new Point into the caller’s object.
p = new Point(4, 4);
This only rewrites the parameter’s own copy of the address. The caller’s object never gets written to.
Point q = *p; q.y_ = 9;
Point q = *p; makes a brand new local copy. Changes to q never travel back through p.

Only statements that go through the address change the caller’s object: p->member and *p on the left side. Assigning to p itself, or to a copy made from *p, stays local.

2

The Point Class in Python

Why this matters

For this step we’ll explore classes and parameter passing in Python to get a feel for how it’s similar to and different from C++. As it turns out, Python has one parameter passing scheme: object references. Compare the caller-visible behavior with the four C++ examples from Step 1.

🎯 You will learn to

Write a C++ class in Python 3.x syntax
Explain which C++ example has the same caller-visible behavior

From C++ to Python

Same class, different syntax. Three things change:

C++	Python	Why
`Point(int x = 0, int y = 0) { ... }`	`def __init__(self, x=0, y=0):`	The constructor has a fixed name, and the object it’s working on is an explicit first parameter
`x_ = x;`	`self.x_ = x`	This assignment creates an instance attribute; assigning to bare `x_` inside the method would create a local variable
`public:` / `private:`	(nothing)	In Python, everything is public by default

✏️ Predict before you run

point_lab.py already contains the Python version of the driver from Step 1:

def modify(p):
    p.x_ = 50          # line A
    p = Point(20, 30)  # line B

pt = Point(10, 10)
modify(pt)
pt.display()

Once you’ve written the class and pressed Run, what gets printed?

(a) (10, 10) — like C++ version A, Python copies the object
(b) (50, 10) — like C++ version C, line A lands but line B doesn’t
(c) (20, 30) — like C++ version B or D, both lines land
(d) A TypeError — you can’t assign to a parameter in Python

Pick a letter before you press Run, then see whether the machine agrees with you.

🔧 Your task

Open point_lab.py and write an equivalent version of the Point class in Python 3.x syntax. Fill in __init__ and display.

Store the coordinates as self.x_ and self.y_, keeping the C++ names so the two files are easy to compare. Preserve the default values so Point() creates a point at (0, 0).
display must print the point’s two coordinates, separated by a comma, and return None. Parentheses and whitespace are up to you: (50, 10) and 50, 10 are both accepted.

Run your Python code here

Finish your edits in point_lab.py, then click Run above the output panel. There is no separate compile command for these Python steps. Run executes the file, including the driver at the bottom; once your class is complete, this driver should print (50, 10).

After each edit, click Run again to see the new result. If Python reports an error, use the file name and line number in the traceback to find the problem, then fix it and rerun. Clear clears the output; it does not change your code.

Use the same workflow on the later Python steps. Test My Work runs additional checks on different inputs, so matching the driver’s output alone does not mean every case is correct. Both running your code and passing the checks are optional; Next lets you continue.

Starter files

point_lab.py

class Point:
    """Python twin of the C++ Point from Step 1."""

    def __init__(self, x=0, y=0):
        # TODO: give this instance its two coordinates, named x_ and y_
        pass

    def display(self):
        # TODO: print this point in the same format as the C++ version,
        # e.g. a point at x=50, y=10 prints as:  (50, 10)
        pass


def modify(p):
    p.x_ = 50          # line A
    p = Point(20, 30)  # line B


# The Python twin of the C++ driver from Step 1.
pt = Point(10, 10)
modify(pt)
pt.display()

Solution

point_lab.py

class Point:
    """Python twin of the C++ Point from Step 1."""

    def __init__(self, x=0, y=0):
        self.x_ = x
        self.y_ = y

    def display(self):
        print(f"({self.x_}, {self.y_})")


def modify(p):
    p.x_ = 50          # line A
    p = Point(20, 30)  # line B


# The Python twin of the C++ driver from Step 1.
pt = Point(10, 10)
modify(pt)
pt.display()

self.x_ = x and self.y_ = y store the coordinates on this instance. The default arguments let Point() create a point at (0, 0).

The driver prints (50, 10), matching C++ version C. Python binds the local parameter to the supplied object through an object reference; it does not copy the point. p.x_ = 50 changes that shared object. p = Point(20, 30) rebinds the local name and leaves pt referring to the original point. Object references explain the similar behavior; Python does not expose C++ pointer dereferencing or pointer arithmetic.

Step 2 — Knowledge Check

Practice target: 80% (optional)

1. Consider the unchanged modify(p) driver. Which C++ example predicts the same effect on the caller’s point as Python?

Version C, pass by pointer, then reassign the pointer
Version A, pass by value, copying the whole object
If Python had copied the object, line A would have been hidden too and we’d have seen (10, 10). The 50 got through, so no copy was made.
Version B, pass by reference, an alias for the caller
An alias would have let line B through too, printing (20, 30). Line B got lost, so p isn’t a second name for pt.
Version D, pass by pointer, writing through the pointer
Writing through a pointer gets both lines across. Line B here reassigns the local name instead of writing into the caller’s object.

Python hands the function a copy of a reference to the object. Attribute writes travel through that reference to the caller’s object, but assigning to the parameter only points the function’s own name somewhere else. That’s exactly what version C did.

2. Suppose line B becomes p = Point(20, 30). Without global, nonlocal, or direct access to the name pt, what does this assignment change?

The local parameter binding only
The caller’s variable binding too
A parameter is a local name bound to the supplied object. Assigning to that name does not rebind the caller’s name.
The coordinates of the original point
An attribute assignment such as p.x_ = 20 would change the original object. p = ... changes which object the local name refers to.
Both points’ coordinates
Constructing a new point does not copy its coordinates into the old point. The two objects remain separate.

Assignment to p rebinds that local name. Python can assign to other scopes with explicit mechanisms such as global and nonlocal, but those do not turn a parameter into an alias for an arbitrary caller variable.

3. Back to Step 1 for a moment. C++ wrote x_ = x; inside the constructor with nothing in front of it. Why does Python need self.x_ = x instead?

Without self., x_ is just a local that dies at the return
self is a keyword Python requires before every assignment
self is an ordinary parameter name, not a keyword, and you only need it when you mean an attribute rather than a local variable.
self. marks the attribute public, like C++’s public: label
self.x_ names an attribute on an instance. Python does not use a public: declaration to make that attribute accessible.
Python needs it to allocate storage for the attribute in advance
For this ordinary class, assigning to self.x_ creates the instance attribute. No separate storage declaration is needed.

Inside this method, x_ = x would bind a local variable. self.x_ = x instead writes an attribute of the instance passed as self. C++ permits an unqualified member name to refer to the current object’s member.

3

Mutation Versus Rebinding

Why this matters

In Homework 0, the Python function changes a point’s attribute but cannot replace the caller’s variable by assigning to its parameter. Let’s try the same distinction with a swap: what changes when we swap attributes, and what changes when we swap local names?

🎯 You will learn to

Apply the change-it versus reassign-it rule to say which changes survive a call
Explain why rebinding parameters does not swap the caller’s variables

The rule

A call binds the function’s parameter names to the same objects the caller passed in. Two very different things can happen next:

You change the object. p.x_ = 50, items.append(3), d["k"] = 1. You reach through the name to the object itself. The caller is holding that same object, so the caller sees the change.
You reassign the name. p = Point(20, 30), items = []. You point the function’s own name at a different object. The caller’s name never moved.

🔧 Your task

Open references_lab.py and write two functions.

swap_coords(p) — swap one point’s own x_ and y_ in place. The caller has to see the change without reassigning anything.
swap_points(a, b) — write the naive version on purpose: the one you’d write in a language where parameters are aliases for the caller’s variables. Reassign a and b to each other and nothing else. Don’t touch their attributes.

Writing the broken one deliberately is the point of this step. The checker verifies that swap_coords works, that swap_points really does attempt the swap, and that the caller’s variables come back unswapped.

✏️ Predict before you run

After swap_coords(first) and then swap_points(first, second), what do the three display() calls print?

Reveal — after you have run it

(2, 1), then (2, 1) and (3, 4).

swap_coords changes the object, so the change sticks. swap_points reassigns two local names that disappear at the return, so first and second in the caller never move. During the call, a and b really were pointing at the caller's objects. Python just gives you no way to reach back through a parameter to the caller's variable.

To swap the caller's names, write first, second = second, first in the caller, or return a pair and assign that result there.

Starter files

references_lab.py

class Point:
    def __init__(self, x=0, y=0):
        self.x_ = x
        self.y_ = y

    def display(self):
        print(f"({self.x_}, {self.y_})")


def swap_coords(p):
    """Swap this point's own x_ and y_, in place.

    The caller must see the swap without reassigning anything.
    """
    # TODO
    pass


def swap_points(a, b):
    """Deliberately naive: rebind a and b to each other.

    Write the version you would write in a language where parameters
    are aliases for the caller's variables. Do not touch .x_ or .y_ —
    watching this one fail is the point of the exercise.
    """
    # TODO
    pass


first = Point(1, 2)
second = Point(3, 4)

swap_coords(first)
first.display()

swap_points(first, second)
first.display()
second.display()

Solution

references_lab.py

class Point:
    def __init__(self, x=0, y=0):
        self.x_ = x
        self.y_ = y

    def display(self):
        print(f"({self.x_}, {self.y_})")


def swap_coords(p):
    """Swap this point's own x_ and y_, in place."""
    p.x_, p.y_ = p.y_, p.x_


def swap_points(a, b):
    """Deliberately naive: rebind a and b to each other."""
    a, b = b, a


first = Point(1, 2)
second = Point(3, 4)

swap_coords(first)
first.display()

swap_points(first, second)
first.display()
second.display()

swap_coords reads both coordinate values before assigning either attribute. Both writes change the shared point, so the caller sees them. A temporary-variable solution works too if it preserves both old values.

a, b = b, a really does exchange the local parameter bindings inside swap_points. It does not change the caller’s bindings or either point’s attributes. To exchange the caller’s variables, the assignment must happen in that caller, possibly using a pair returned by a function.

Step 3 — Knowledge Check

Practice target: 80% (optional)

1. def f(xs, d, n) receives a list, an empty dictionary, and an integer. Consider each option independently as the entire body. Which bodies change an object the caller supplied? (select all that apply)

xs.append(4)
append changes the list object itself, and both names refer to that same object.
d["key"] = 4
Assigning to a key changes the dictionary object itself. It doesn’t reassign d.
xs = xs + [4]
+ builds a brand new list, and = points the local name at it. The caller’s list is never touched. xs += [4] would be the version that does change it.
n += 1
Integers can’t be changed in place, so += computes a new one and points the local name at it.

A change survives the call when it changes the shared object. Any statement that just points a parameter name at a different object is invisible to the caller.

2. Back to Step 1 again. A C++ function is declared void f(Point p) and its body is p.x_ = 99;. The caller runs Point pt(1, 1); f(pt); pt.display(); How does that compare with the Python call f(pt), where def f(p): p.x_ = 99?

C++ keeps (1, 1); Python gets (99, 1)
Both leave the caller’s point at (1, 1)
Python never copies the object on a call, so the write lands on the caller’s object.
Both set the caller’s x_ to 99
A C++ by-value parameter is a real copy made by the copy constructor, so the write lands on that copy and is thrown away.
C++ sets x_ to 99, but Python leaves it at 1
This has the two languages backwards. Copying is what C++ does when you pass by value, and Python is the one that shares the object.

Passing by value in C++ copies the object, so the function edits a copy. Python has no such mode. The function always gets a reference to the same object, so attribute writes are shared.

3. A colleague fixes the broken swap like this:

def swap_points(a, b):
    a.x_, b.x_ = b.x_, a.x_
    a.y_, b.y_ = b.y_, a.y_

Does the caller now see first and second swapped?

Their coordinates swap; their identities do not
Their identities swap; their coordinates do not
The assignments write into the existing objects. Neither assignment changes which object a caller variable refers to.
Neither their identities nor their coordinates change
Attribute assignments change the shared objects, so the caller sees the exchanged coordinates.
Both their identities and their coordinates swap
The coordinates change, but object identity stays fixed. Other aliases still refer to the same objects and see their new coordinates.

Changing attributes reaches the shared objects, so the printed coordinates really do swap. What didn’t happen is a swap of the caller’s names. first still refers to the object it always did. To swap the names you need first, second = second, first at the call site.

4

Recursion With No Loops Allowed

Why this matters

In this step we’ll review basic recursion. Recursive definitions will be important in the functional programming part of CS131, so we’ll practice solving a smaller problem and using its answer without writing a loop.

🎯 You will learn to

Write a recursive function whose base case covers every permitted input
Break an array traversal into “the first item” plus “the rest”

Recursion on the Rest of an Array

An int arr[] function parameter is treated as a pointer, so these functions also receive an element count. arr + 1 points one element later in the same array. This is the pointer arithmetic from CS31, and it’s how you say “the rest of the array” without copying anything:

Concept	C++	Python
the first item	`arr[0]`	`values[0]`
everything but the first	`arr + 1, n - 1`	`values[1:]`
is there only one item left?	`n == 1`	`len(values) == 1`

Here’s one way to organize both functions:

Base case. What’s the answer when there’s exactly one item left? Both functions here are guaranteed at least one item, so n == 1 is a safe place to stop.
Recursive case. Ask the same function for the answer to arr + 1, n - 1, then combine that answer with arr[0].

✏️ Predict before you write

For index_of_biggest, the recursive call answers a question about the sub-array starting at arr + 1. If that call returns 2, what is that 2 an index into?

(a) The original array, so use it as is
(b) The sub-array, so the original index is one higher
(c) The sub-array, so the original index is one lower

This is the classic off-by-one in this exact problem, so it’s worth deciding before you type.

Reveal

(b). The recursive call knows nothing about the element you sliced off. Index 2 of arr + 1 is index 3 of arr. So every index that comes back from recursion needs + 1 before you can compare it against arr[0] or return it. Compare arr[rest] with arr[0], where rest is the adjusted index.

That's why find_biggest is easier than index_of_biggest. Values mean the same thing no matter which sub-array they came from. Indices don't.

🔧 Your task

Open recursion.cpp and write both functions. Given an array that is guaranteed to have at least one item, find_biggest returns the largest value in the array, and index_of_biggest returns the index of the largest value, where the first item is at index zero. Both functions receive at least one item. For index_of_biggest, assume there are no duplicate numbers. No looping allowed! Recursive helpers are welcome.

int arr[] = {-1, 10, 3};
find_biggest(arr, 3);      // 10
index_of_biggest(arr, 3);  // 1

Choose Run to compile and run recursion.cpp as C++17 in the browser. The supplied main() prints the largest value and its index for {-1, 10, 3}. Replace the placeholder returns as you implement each function, and edit the array in main() to try the cases below. Update the element count in both calls when you change the array’s length.

This step uses manual review: compare the output with the expected answers and trace your recursive calls. Step 5 has automatic checks for the Python versions; those checks do not grade this C++ implementation.

Check your work (manual review)

For each input, write the returned value and the returned index:

Array	`find_biggest`	`index_of_biggest`
`{5}`	`5`	`0`
`{-5, -2, -9}`	`-2`	`1`
`{9, 2, 3}`	`9`	`0`
`{1, 2, 9}`	`9`	`2`

Check that every recursive call receives a smaller problem, that the base case is checked before recursing, and that an index is measured from the right starting address. For the array {7, 7, 2}, find_biggest should return 7; the no-duplicates guarantee applies only to index_of_biggest.

Starter files

cs131/recursion.cpp

#include <iostream>

// Return the largest value in arr[0..n-1].
// Guaranteed: n >= 1. No loops allowed.
int find_biggest(int arr[], int n) {
    // TODO: base case, then combine arr[0] with the answer for the rest
    return 0; // Placeholder: replace this with your recursive implementation.
}

// Return the INDEX (into arr) of the largest value in arr[0..n-1].
// Guaranteed: n >= 1, no duplicate values. No loops allowed.
int index_of_biggest(int arr[], int n) {
    // TODO: remember that an index from the sub-array needs adjusting
    return 0; // Placeholder: replace this with your recursive implementation.
}

int main() {
    int arr[] = {-1, 10, 3};
    std::cout << "largest value: " << find_biggest(arr, 3) << "\n";
    std::cout << "index of largest: " << index_of_biggest(arr, 3) << "\n";
    return 0;
}

Solution

cs131/recursion.cpp

#include <iostream>

// Return the largest value in arr[0..n-1].
// Guaranteed: n >= 1. No loops allowed.
int find_biggest(int arr[], int n) {
    if (n == 1) return arr[0];
    int rest = find_biggest(arr + 1, n - 1);
    if (rest > arr[0])
        return rest;
    else
        return arr[0];
}

// Return the INDEX (into arr) of the largest value in arr[0..n-1].
// Guaranteed: n >= 1, no duplicate values. No loops allowed.
int index_of_biggest(int arr[], int n) {
    if (n == 1) return 0;
    int rest = index_of_biggest(arr + 1, n - 1) + 1;
    if (arr[rest] > arr[0])
        return rest;
    else
        return 0;
}

int main() {
    int arr[] = {-1, 10, 3};
    std::cout << "largest value: " << find_biggest(arr, 3) << "\n";
    std::cout << "index of largest: " << index_of_biggest(arr, 3) << "\n";
    return 0;
}

Both functions have the same shape. Check the base case first, make one recursive call on a smaller problem, then combine the two answers.

The only real difference is the + 1. find_biggest can use the recursive answer as is, because a value means the same thing no matter which sub-array it came from. index_of_biggest can’t. The index it gets back is measured from arr + 1, so we have to shift it before we compare or return it. The other place this problem trips people up is the comparison: we compare arr[rest] > arr[0], which compares values, not indices.

Step 4 — Knowledge Check

Practice target: 80% (optional)

1. A student writes:

int find_biggest(int arr[], int n) {
    int rest = find_biggest(arr + 1, n - 1);
    if (n == 1) return arr[0];
    return rest > arr[0] ? rest : arr[0];
}

What happens when this runs on a three-element array?

It keeps recursing before it can check the base case
It returns arr[0], because the base case fires immediately
The n == 1 check is never reached, because the recursive call above it runs first and drives n past 1 on the way down.
It returns the largest value correctly
The combining logic is right, but it never runs. The function recurses before it ever checks whether it should stop.
It returns the largest value in arr + 1 and misses arr[0]
That would be a mistake in the comparison. The problem here happens earlier, because the recursion never reaches a stopping point.

The recursive call runs before the stopping condition, so no invocation reaches that condition. The code has no valid terminating recursion; on a typical run it exhausts resources, and advancing beyond the array also makes its C++ behavior undefined.

2. index_of_biggest(arr + 1, n - 1) returns 0. What does that 0 mean, and what should you do with it?

It identifies arr[1]; add 1 to translate the index
The biggest of the rest is at index 0 of arr, so use it as is
The call was given a different starting address, so the index it returns is counted from arr + 1, not from arr.
The rest is empty, so return 0 immediately
A return value of 0 just means “the first one”. An empty array never reaches this code, because the base case stops the recursion first.
The biggest of the rest is arr[0], so the answer is already found
arr[0] is exactly the element we sliced off before the recursive call, so the recursion couldn’t have been talking about it.

Every index that comes back from a recursive call is counted from the sub-array that call received. To turn it into an index into the original array, add 1 for each element you sliced off, which is exactly one here.

3. Back to Steps 1 through 3. find_biggest(int arr[], int n) is called as find_biggest(scores, 5). Which statements are true? (select all that apply)

arr inside the function is a pointer, not a copy of the array
An array parameter is silently rewritten as a pointer. That’s also why n has to be passed separately, since the pointer doesn’t know the length.
Writing arr[0] = 99 inside the function changes the caller’s array
The function is holding the caller’s address, so writing through a subscript reaches the caller’s array.
arr + 1 creates a copy of the array minus its first element
Pointer arithmetic produces a new address, not new storage. arr + 1 is a different starting point into the same array.
Passing the array copies all 5 elements onto the stack
With this built-in array parameter, the call passes a pointer to the first element. It does not copy the five elements.

This array argument supplies a pointer to its first element, so the function shares the caller’s array. arr + 1 computes an address within that storage; it does not create a smaller array.

5

The Same Recursion in Python

Why this matters

Now write the same two algorithms in Python and try them on different inputs. If a result differs from your prediction, trace the base case and the value returned by each recursive call. Compare that reasoning with your C++ version.

🎯 You will learn to

Turn pointer-and-count recursion into slice-based recursion
Check a recursive algorithm against inputs chosen to break it

Slices replace pointer arithmetic

Here are some hints to help you if you haven’t worked with lists in Python before. Python lists know their own length, so the count parameter goes away:

C++	Python
`find_biggest(arr + 1, n - 1)`	`find_biggest(values[1:])`
`n == 1`	`len(values) == 1`
`arr[0]`	`values[0]`

Given a list x, to obtain everything but the first item (that is, the tail of the list) you write x[1:]. To get the length of a list, use len(). One real difference from C++: values[1:] builds a new list every call, where arr + 1 was just an address. That makes the translation easy to read, but adds copying work. An index-based recursive helper can avoid those repeated slices.

🔧 Your task

Open recursion_lab.py and implement both functions using recursion. Each receives a non-empty list of numbers. find_biggest returns the largest value, including when values repeat. index_of_biggest returns its zero-based index; for that function, assume there are no duplicates.

No loops or comprehensions. You may write recursive helpers, use a slice or an index to describe the remaining input, and compare two candidates with max. The traversal must be recursive; a call to max(values) or sorted(values) alone does not meet the task.

find_biggest([-1, 10, 3])      # 10
index_of_biggest([-1, 10, 3])  # 1

The tests run your functions on all-negative lists, single-element lists, and lists whose largest value sits at the front, the middle, and the end. Before you test, explain why [1, 2, 3] alone would miss a solution that starts its largest value at zero, or always returns the last element.

Starter files

recursion_lab.py

def find_biggest(values):
    """Return the largest value in values. Assumes at least one item.

    Use recursion, directly or through a helper; no loops or comprehensions.
    """
    # TODO
    pass


def index_of_biggest(values):
    """Return the index of the largest value in values.

    Assumes at least one item and no duplicates.
    No loops, no comprehensions.
    """
    # TODO
    pass


print(find_biggest([-1, 10, 3]))      # expect 10
print(index_of_biggest([-1, 10, 3]))  # expect 1

Solution

recursion_lab.py

def find_biggest(values):
    """Return the largest value in values. Assumes at least one item."""
    if len(values) == 1:
        return values[0]
    rest = find_biggest(values[1:])
    if rest > values[0]:
        return rest
    return values[0]


def index_of_biggest(values):
    """Return the index of the largest value in values."""
    if len(values) == 1:
        return 0
    rest = index_of_biggest(values[1:]) + 1
    if values[rest] > values[0]:
        return rest
    return 0


print(find_biggest([-1, 10, 3]))      # expect 10
print(index_of_biggest([-1, 10, 3]))  # expect 1

Line for line, this is the C++ from Step 4 with arr + 1, n - 1 replaced by values[1:] and n == 1 replaced by len(values) == 1. The algorithm didn’t change at all. Only the way we say “the rest of the list” changed.

There are two details the test inputs are built to catch. Starting from values[0] instead of from 0 is what makes the all-negative case work. And the + 1 on the recursive index is what makes [1, 2, 3] return 2 instead of an index measured from a smaller slice, which is the same off-by-one you thought about before writing any code.

Step 5 — Knowledge Check

Practice target: 80% (optional)

1. Why does find_biggest store the recursive result in a variable first, rather than writing this?

return find_biggest(values[1:]) if find_biggest(values[1:]) > values[0] else values[0]

It may solve the same subproblem twice
It causes an immediate recursion error
Two calls in an expression are legal. The problem is repeated work, not an immediate recursion error.
It compares positions instead of values
find_biggest returns values, so the comparison is between values. Computing one of those values twice is unnecessary.
It changes the input before comparing
The shown slice-based calls do not write into the original list. They do repeat the work of making slices and finding their maxima.

The condition always makes one recursive call, and the true branch makes another. For inputs where that branch wins at each level, the call count grows exponentially. Saving the result gives one recursive call per level; repeated Python slicing still adds quadratic copying work.

2. Put together a recursive count_items(values) that returns the length of a list without calling len() on the whole list, and without loops or comprehensions. (arrange in order)

Correct order:

def count_items(values):
if not values:
return 0
return 1 + count_items(values[1:])

Distractors (not used):

return count_items(values[1:])
for item in values:

3. Back to Steps 2 and 3. Inside index_of_biggest, we pass values[1:] to the recursive call. If that call appended to the list it received, would the caller’s list change?

No; appending changes only the new outer list
Yes; parameter passing shares the original list
The function does get a reference, but to the slice, not to the original. values[1:] already built a separate list before the call happened.
Yes; appending also extends the original list
A slice copies the references into a brand new list. Appending to that list only changes its own length, and the original list is untouched.
No; every function call deep-copies its argument
Python never copies arguments. The call copied nothing here. The copy was made by the slicing expression, before the call happened.

Slicing builds a new outer list containing references to the same elements. Appending to that outer list does not affect the original list. Mutating a shared mutable element would be different; a shallow slice does not copy the elements themselves.

6

Building New Lists Recursively

Why this matters

This problem asks you to transform a list without changing the original. The recursive solution is similar to one we’ll use in functional programming: decide what to keep, then build the result from those values.

🎯 You will learn to

Build a new list recursively instead of changing an existing one
Pick a base case for a function that can legitimately be handed an empty list

A New List From the Remaining Values

One approach is to ask whether the first item belongs in the output, then combine that decision with the result for the rest. These operations can help you build a separate list:

x = [10, 20, 30]
x[1:]        # [20, 30]          the rest of the list
[5] + x      # [5, 10, 20, 30]   a NEW list, x is untouched
len(x)       # 3

Note the difference between [5] + x and x.append(5). The first builds a new list and leaves x alone. The second changes the list the caller is holding. You may change a new output list while building it; the restriction is that the input list must stay unchanged.

🔧 Your task

Open del_item_lab.py and write del_item(values, item), which takes a list of values as its first parameter and an item to delete as its second. Without changing the values list, and without using loops of any kind, your function must return an output list that removes all of the occurrences equal to item from the input list. Preserve the order of the remaining values, and return a new list even when the input is empty or nothing matches. Recursive helpers are welcome:

x = [1, 2, 3, 1, 4]
y = del_item(x, 1)
print(y)   # prints [2, 3, 4]
print(x)   # still prints [1, 2, 3, 1, 4]

No comprehensions either. Three cases decide the whole function: the list is empty, the first item matches, and the first item doesn’t.

✏️ Predict before you run

Suppose the only base case is if len(values) == 1: return values. What happens for del_item([], 7) and del_item([7], 7)?

Reveal

The empty input misses this base case and then fails if the function tries to read values[0]. The singleton input incorrectly returns [7] instead of removing the match.

Checking the empty list first handles both cases naturally. A solution can also special-case a singleton, but it still needs to handle empty input and decide whether that last item should be kept.

Starter files

del_item_lab.py

def del_item(values, item):
    """Return a NEW list with every occurrence of item removed.

    values must come back unchanged.
    No loops or comprehensions. Helpers are allowed; do not change values.
    """
    # TODO: three cases - empty, first item matches, first item doesn't
    pass


x = [1, 2, 3, 1, 4]
y = del_item(x, 1)
print(y)  # expect [2, 3, 4]
print(x)  # expect [1, 2, 3, 1, 4]

Solution

del_item_lab.py

def del_item(values, item):
    """Return a NEW list with every occurrence of item removed."""
    if len(values) == 0:
        return []

    if values[0] != item:
        return [values[0]] + del_item(values[1:], item)

    return del_item(values[1:], item)


x = [1, 2, 3, 1, 4]
y = del_item(x, 1)
print(y)  # expect [2, 3, 4]
print(x)  # expect [1, 2, 3, 1, 4]

Read the three returns as three sentences. An empty list has nothing to delete, so the answer is a new empty list. If the first item is a keeper, the answer is that item glued onto whatever the rest produces. Otherwise the answer is just whatever the rest produces, and the item gets dropped simply by not being glued back on.

Nothing is ever removed from values. values[1:] reads, [a] + b builds, and we never assign to the original list or call a method that changes it. That’s why print(x) still shows [1, 2, 3, 1, 4] after the call, and it’s the same habit functional programming will ask for on every data structure, not just lists.

Step 6 — Knowledge Check

Practice target: 80% (optional)

1. A recursive del_item skips a matching first item and prepends a kept first item to the recursive result. Which empty-input base case also meets the requirement to return a new list?

if not values: return []
if len(values) == 1: return values
Stopping at one item never looks at that last element, so a match at the end gets returned instead of removed. It also crashes when called with an empty list.
if not values: return values
This terminates, but for an empty input it returns that same input list. The stated task asks for a new list even in the empty case.
if values[0] == item: return []
This throws away the entire rest of the list the moment it finds a match, instead of removing just that one item.

if not values: return [] handles empty input and creates a separate result list. Each nonempty call can then decide whether to include its first item. Returning the input itself would terminate too, but would not meet the new-list requirement.

2. Start with a fresh x = [1, 2, 3] for each option. Which expressions leave x unchanged? (select all that apply)

x[1:]
Slicing is the workhorse of this step. It reads from x and builds a separate list.
[0] + x
+ builds a third list and never writes into either of the two it was given.
x.append(4)
append changes the list in place. It returns None precisely so you don’t treat it as producing a new list.
x.pop()
pop removes the last element from x and returns it, so the list is one shorter afterwards.

Slicing and concatenation create new lists without changing x. Both append and pop change x; a method’s return value alone does not tell you whether it mutates its receiver.

3. Which feature of this solution illustrates the approach to immutable data we will practice in functional programming?

It builds a result while preserving the input
It uses recursion rather than a loop
Recursion does not by itself prevent mutation. A recursive function can still change a shared list.
It takes the item to delete as a parameter
Taking a parameter is ordinary good design in any language and says nothing about how the function treats state.
It returns a list rather than printing one
Returning rather than printing is a step in the right direction, but a function can return a value and still have changed something on the way.

Preserving the input and returning a result illustrates working with immutable data. Recursion is a way to express the traversal; it is not by itself a guarantee that a function has no side effects.

7

Virtual Dispatch and Object Slicing

Why this matters

In this step we’ll explore inheritance and polymorphism using C++. The question is which function body runs when a base-class reference refers to a derived object. Keep the parameter passing rules from Step 1 in mind as you work through the calls.

🎯 You will learn to

Trace which version of a function runs when a base-class reference names a derived object
Evaluate how a parameter’s declared form changes that choice
Add a new subclass to an existing hierarchy

The comedy club

Consider the following classes, which represent regular people and people who giggle (a subclass of people) when they attend a comedy club:

class Person {
public:
  Person(const std::string& name) { name_ = name; }
  void listen_to_joke() { laugh(); }
  virtual void laugh()  { cout << "haha!\n"; }
  virtual void heckle() { cout << "that's dumb!\n"; }
private:
  std::string name_;
};

class GigglyPerson : public Person {
public:
  GigglyPerson(const std::string& name) : Person(name) { }
  virtual void laugh()  { cout << "giggle giggle!\n"; }
  virtual void heckle() { cout << "that's... giggle... dumb... giggle!\n"; }
};

Now consider the following code that uses our classes:

void comedy_club(Person& p) {
  p.listen_to_joke();
  p.heckle();
}

int main() {
  Person p("Leia");
  comedy_club(p);

  GigglyPerson g("Sanjay");
  comedy_club(g);
}

Notice what listen_to_joke is: a non-virtual function, defined only on Person, that calls laugh(). Nobody overrides it. Keep that in mind for the prediction.

✏️ Predict before you read on

What will this program print? Why? Don’t just compile and run this code. Instead, try to reason out what is printed and why that’s the case. If you get a different answer, trace the call that surprised you. Four lines come out, so write all four down before you open the reveal.

(a) haha!, that's dumb!, haha!, that's... giggle... dumb... giggle!
(b) haha!, that's dumb!, giggle giggle!, that's... giggle... dumb... giggle!
(c) haha!, that's dumb!, haha!, that's dumb!

Reveal

(b).

haha!
that's dumb!
giggle giggle!
that's... giggle... dumb... giggle!

Line 3 is the interesting one. comedy_club(g) binds the reference p to the GigglyPerson object g. There's no copy and nothing gets sliced off, because p is a reference, which is version B from Step 1. p.listen_to_joke() runs Person's only copy of that function, and inside it the bare call laugh() means this->laugh(). this points at a GigglyPerson and laugh is virtual, so the overridden version in GigglyPerson is the one that runs.

The non-virtual function didn't need to be overridden. It only needed to call something virtual. This dynamic method dispatch is a key feature of object-oriented programming.

🔧 Your task

Open comedy_club.cpp and add a third kind of audience member: StonePerson, who is unimpressed by everything.

Inherit publicly from Person.
Forward the name to the Person constructor in an initializer list. Person has no default constructor, so this isn’t optional.
Override both laugh and heckle. The joke gets ...silence..., and the heckle gets something equally deadpan. The exact strings are up to you.
In main, send a StonePerson through comedy_club alongside the other two.

Predict your program’s six output lines, then choose Run to compile and run comedy_club.cpp as C++17 in the browser. Compare the output with your prediction. This step uses the manual review below; it has no automatic code tests.

Check your work (manual review)

The first four lines should match the original program. The final two should come from your StonePerson overrides, even though comedy_club still takes Person&. Check that the constructor and both overrides are public, and that the override signatures match void laugh() and void heckle(). Adding override after each signature lets the compiler catch a mismatch when you choose Run.

Now consider replacing Person& p with Person p. Passing g then copies only its Person base part into a new Person object. This is called object slicing. The original g stays a GigglyPerson, but the local copy prints haha! and that's dumb!. A reference or pointer can refer to the original derived object without making that copy.

Starter files

cs131/comedy_club.cpp

#include <iostream>
#include <string>
using namespace std;

class Person {
public:
  Person(const std::string& name) { name_ = name; }
  void listen_to_joke() { laugh(); }
  virtual void laugh()  { cout << "haha!\n"; }
  virtual void heckle() { cout << "that's dumb!\n"; }
private:
  std::string name_;
};

class GigglyPerson : public Person {
public:
  GigglyPerson(const std::string& name) : Person(name) { }
  virtual void laugh()  { cout << "giggle giggle!\n"; }
  virtual void heckle() { cout << "that's... giggle... dumb... giggle!\n"; }
};

// TODO: add StonePerson here.
// Inherit publicly from Person, forward the name to Person's
// constructor, and override both laugh() and heckle().

void comedy_club(Person& p) {
  p.listen_to_joke();
  p.heckle();
}

int main() {
  Person p("Leia");
  comedy_club(p);

  GigglyPerson g("Sanjay");
  comedy_club(g);

  // TODO: build a StonePerson and send it to comedy_club too.
}

Solution

cs131/comedy_club.cpp

#include <iostream>
#include <string>
using namespace std;

class Person {
public:
  Person(const std::string& name) { name_ = name; }
  void listen_to_joke() { laugh(); }
  virtual void laugh()  { cout << "haha!\n"; }
  virtual void heckle() { cout << "that's dumb!\n"; }
private:
  std::string name_;
};

class GigglyPerson : public Person {
public:
  GigglyPerson(const std::string& name) : Person(name) { }
  virtual void laugh()  { cout << "giggle giggle!\n"; }
  virtual void heckle() { cout << "that's... giggle... dumb... giggle!\n"; }
};

class StonePerson : public Person {
public:
  StonePerson(const std::string& name) : Person(name) { }
  virtual void laugh()  { cout << "...silence...\n"; }
  virtual void heckle() { cout << "i've heard better.\n"; }
};

void comedy_club(Person& p) {
  p.listen_to_joke();
  p.heckle();
}

int main() {
  Person p("Leia");
  comedy_club(p);

  GigglyPerson g("Sanjay");
  comedy_club(g);

  StonePerson s("Wren");
  comedy_club(s);
}

StonePerson is GigglyPerson with different strings, and that’s the point. Adding a third behavior meant changing nothing in Person and nothing in comedy_club. That’s what dynamic method dispatch buys you.

Two details are easy to miss, and both are about matching. The class header needs public, because a class inherits privately by default and a private base makes Person& unreachable. And each override needs the exact signature of the virtual function it replaces: void laugh(), no parameters. A near miss like void laugh(int) defines a different function and does not override laugh(). Adding override catches that mismatch at compile time.

The initializer list isn’t a style choice here. Person declares a constructor that takes a name, so it has no default constructor, and the base part can’t be built without : Person(name).

Step 7 — Knowledge Check

Practice target: 80% (optional)

1. listen_to_joke is not virtual, and GigglyPerson never overrides it. So why does comedy_club(g) still print giggle giggle!?

listen_to_joke calls laugh(), which is virtual, on a GigglyPerson
Any function called on a derived object dispatches dynamically
Only functions declared virtual in the base class are chosen at run time. A non-virtual call is decided at compile time, from the declared type.
GigglyPerson inherits listen_to_joke and recompiles it against its own laugh
Inheritance shares one compiled function. It doesn’t make a separate copy per subclass. The choice happens at run time, through the virtual call inside it.
Passing by reference makes every member function behave as if virtual
References do prevent slicing, which is what gives dispatch anything to choose between, but the choosing itself still requires virtual.

The bare laugh() inside listen_to_joke means this->laugh(). this points at a GigglyPerson and laugh is virtual, so the overridden version runs even though the function around it is an ordinary one.

2. Back to Step 1. Someone changes the signature to void comedy_club(Person p), by value instead of by reference. What does comedy_club(g) print now?

haha! then that's dumb!, because the GigglyPerson part is sliced off
giggle giggle! then that's... giggle... dumb... giggle!, unchanged
Passing by value builds a Person-sized object using Person’s copy constructor, so the overrides don’t come along.
Nothing, because the call no longer compiles
It compiles without complaint, because a GigglyPerson is a Person and the copy is perfectly legal. That silence is what makes this bug so hard to spot.
haha! then that's... giggle... dumb... giggle!
Both calls are still virtual, but their receiver is now a plain Person copy. Neither dispatch can select a GigglyPerson override.

This is object slicing. The copy constructor builds a plain Person out of the Person part of g and throws the rest away. The parameter really is a Person, so both virtual calls find Person’s bodies.

3. Which parameter types preserve a GigglyPerson object for virtual dispatch when it is passed to comedy_club? Assume the call and member access use the appropriate reference or pointer syntax.

Person& and Person* only
All three of Person, Person& and Person*
Passing by value is exactly the one that can’t. It copies a Person-shaped object and loses the subclass part before any call happens.
Person* only, because dispatch needs an address
A reference can name the original derived object without copying it. A pointer can do the same; dynamic dispatch works through either.
Person and Person&, but not Person*
This has it backwards. A pointer keeps the real type, and passing by value is the one that destroys it.

Dynamic dispatch needs the original subclass object to still be there behind the parameter. References and pointers both name it. A by-value parameter is a new, smaller object with no subclass part left to dispatch to.

4. Consider each change independently. Which changes prevent the StonePerson call in main from producing both intended overrides? (select all that apply)

Declaring the class as class StonePerson : Person
A class inherits privately unless you say public, and a private base means the conversion to Person& isn’t allowed.
Naming the override void laugh(int volume)
Signatures have to match. Adding a parameter defines an unrelated function, so the base version keeps winning the virtual call.
Writing void laugh() { cout << "...silence...\n"; } without virtual
An override is virtual whether or not you repeat the keyword. Writing it again is a readability choice, not a behavior change.
Giving StonePerson a constructor that forwards the name to Person
That’s required for the class to compile at all, since Person has no default constructor. It enables the overrides rather than blocking them.

Private inheritance makes this conversion to Person& inaccessible, so the call fails to compile. Changing laugh’s parameter list instead creates a different function; the inherited laugh() still runs. An override remains virtual without repeating the keyword.

5. Back to Steps 2 and 3. If you translated this hierarchy to Python, which C++ mechanism would you no longer have to worry about?

Object slicing on assignment or parameter passing
Calling a base-class method from a subclass
Python writes this as super().method(), which does the same job as the qualified Person::method() call.
Overriding a method in a subclass
Python supports overriding instance methods in subclasses. Ordinary instance calls look up the method on the object’s class.
Constructing the base part of a subclass instance
A Python subclass may need to call super().__init__(...) to establish attributes expected by inherited methods. That initialization concern remains.

Slicing happens because C++ objects have a fixed size and get copied by value. Python names always refer to whole objects and never copy on assignment or on a call, so there’s no way to lose the subclass part.

8

Linked Lists Without a Destructor

Why this matters

Consider the linked list class below. Translating it to Python brings together classes, object references, and traversal. The chain has the same structure in both languages, but Python manages node memory automatically.

🎯 You will learn to

Write a singly linked list in Python with a nested node class
Explain why this Python linked list needs no manual node cleanup

The C++ original

class List {
private:
  struct Node {
    Node(int v) { val = v; next = nullptr; }
    int val;
    Node *next;
  };

  Node *head_;
public:
  List() { head_ = nullptr; }
  ~List() {
    while (head_ != nullptr) {
      Node *temp = head_->next;
      delete head_;
      head_ = temp;
    }
  }
  void add_to_front(int val) {
    Node *new_node = new Node(val);
    new_node->next = head_;
    head_ = new_node;
  }
  void print() {
    Node *p = head_;
    while (p) {
      cout << p->val << endl;
      p = p->next;
    }
  }
};

The constructor, insertion, and traversal have Python equivalents. The explicit node cleanup is unnecessary: Python can reclaim nodes when they are no longer reachable. The timing depends on the Python implementation, so we do not rely on immediate collection.

C++	Python
`struct Node { ... };` nested and private	a `class Node:` nested inside `List`
`Node *head_;` set to `nullptr`	`self.head = None`
`new Node(val)`	`self.Node(val)`
`~List()` walking the chain calling `delete`	nothing at all

🔧 Your task

Open linked_list_lab.py and finish the class:

Node stays nested inside List, with attributes val and next, mirroring the C++ layout. A new node stores its supplied value and starts with next = None.
List.__init__ starts with self.head = None.
add_to_front(val) links a new node in at the front. It returns nothing.
values() returns a plain Python list of the values, front to back, by walking the chain.
print_items() prints one value per line, front to back.

Both values() and print_items() must leave the nodes and their links unchanged so the list can be read again.

Loops are allowed again here. The no-loops requirement applies to the recursion problems. This interactive version adds values() so you can inspect the chain and names the printing method print_items(); it does the same job as print() in Homework 0.

✏️ Predict before you run

You add 1, then 2, then 3, each to the front. What does values() return, and which end of the chain is head?

Reveal

[3, 2, 1]. Every insertion goes in front of whatever was already there, so the newest item is always head and the list comes out in reverse insertion order. That's why add_to_front is so cheap, and why a stack is the natural thing to build out of one of these.

A Later Review

After a break, try three small variations without looking at the reveals: explain a pointer reassignment, trace an index returned by recursion, and insert a node into a two-node chain. Use any gap in your explanation to choose the step to revisit. That’s all for this refresher!

Starter files

linked_list_lab.py

class List:
    """Python port of the C++ singly linked list."""

    class Node:
        def __init__(self, v):
            # TODO: a node holds a value and a link to the next node
            pass

    def __init__(self):
        # TODO: an empty list points at nothing
        pass

    def add_to_front(self, val):
        # TODO: build a node, link it ahead of the current front,
        # then make it the new front
        pass

    def values(self):
        # TODO: walk the chain and collect the values, front to back
        pass

    def print_items(self):
        # TODO: print one value per line, front to back
        pass

    # No destructor needed - see the quiz below for why.


lst = List()
lst.add_to_front(1)
lst.add_to_front(2)
lst.add_to_front(3)
print(lst.values())  # expect [3, 2, 1]
lst.print_items()

Solution

linked_list_lab.py

class List:
    """Python port of the C++ singly linked list."""

    class Node:
        def __init__(self, v):
            self.val = v
            self.next = None

    def __init__(self):
        self.head = None

    def add_to_front(self, val):
        new_node = self.Node(val)
        new_node.next = self.head
        self.head = new_node

    def values(self):
        result = []
        p = self.head
        while p is not None:
            result.append(p.val)
            p = p.next
        return result

    def print_items(self):
        for val in self.values():
            print(val)

    # No destructor needed - see the quiz below for why.


lst = List()
lst.add_to_front(1)
lst.add_to_front(2)
lst.add_to_front(3)
print(lst.values())  # expect [3, 2, 1]
lst.print_items()

Line for line, add_to_front and the chain walk are the C++ originals with -> becoming . and nullptr becoming None. The algorithm didn’t change, because the algorithm was never the C++-specific part.

A few key things to note:

In Python, everything is public by default. There’s no need for the public or private specifiers, and the Node class is nested purely to say where it belongs.
Memory management in Python is done automatically using a garbage collector, so there’s no need for explicit memory deallocation as in C++. No new, no delete, and no destructor is needed.
The nested Node class in Python is defined similarly to how it’s done in C++, but we use the conventional self parameter name in methods to refer to instance variables or other methods.

That’s the whole refresher in one class: same structure, same traversal, and a completely different answer to who is responsible for the memory.

Step 8 — Knowledge Check

Practice target: 80% (optional)

1. The C++ List needs ~List() to walk the chain calling delete. Why does the Python version need nothing like it?

Python automatically manages unreachable node objects
Python allocates nodes on the stack, so they die with the function
Python manages the lifetime of these node objects automatically; they are not local C++ stack objects that disappear when a method returns.
Python’s garbage collector runs at exit and frees everything then
Python can reclaim unreachable objects during execution, not only at program exit. The exact collection time is implementation-dependent.
Nested classes are freed together with the class that contains them
Nesting just says where the class lives. It has nothing to do with how long the objects made from it stick around.

The list does not need to call delete on its nodes. Python manages their memory and can reclaim them when they are no longer reachable. Code should not depend on immediate collection; another reference to a node can also keep it alive.

2. Inside add_to_front, does the order of these two lines matter?

new_node.next = self.head
self.head = new_node

Yes; reversing them makes the new node point to itself
No, both assignments happen before the method returns
Both lines do run, but the second one reads a value the first one already overwrote, so the old chain is gone before we can hang on to it.
Yes, swapping them raises an AttributeError on the first call
It fails quietly rather than loudly. self.head is a perfectly valid node by then, so nothing raises. The list just becomes a one-element loop.
No, Python evaluates both right sides before assigning
That’s how assigning a pair works, but these are two separate statements, so the first one’s effect is visible to the second.

The first line saves the old front in new_node.next. Reversing the order replaces self.head first, so new_node.next is assigned the new node itself. The existing chain is no longer reachable through this list.

3. Back to Steps 1 through 3. Two variables refer to the same List:

a = List()
b = a
b.add_to_front(5)
print(a.values())

What is printed?

[5]
[]
b = a copies a reference, not the object. There’s only one list here, and add_to_front changes it.
[5, 5]
Only one node was added, and only one list exists, so there’s nothing to duplicate.
An AttributeError
Both names refer to a fully built List, so every attribute access works normally.

Assignment between names never copies an object. a and b are two names for one list, so a change through either one is visible through both. It’s the same shared-object rule from Step 3, one level up from attributes.

4. Which responsibilities from the C++ example do we omit in this ordinary Python translation? (select all that apply)

delete on each node
Python manages these nodes’ memory automatically. Python’s del removes a binding or item; it is not C++’s explicit object deallocation.
private: hiding head_ and Node from callers
Python has a naming convention for “please don’t touch this”, but nothing enforces it, so everything stays reachable.
The while loop that walks the chain
The walk ports over unchanged. while exists in both languages and means the same thing.
Node *next; linking one node to the next
The link ports over as an ordinary attribute holding either another node or None. The structure is identical, and only the syntax changes.

The two things that vanish are both about control that C++ gives you: freeing memory yourself, and enforced access restrictions. The data structure itself, a node holding a value and a link and walked by a loop, survives the translation intact.

5. Put add_to_front together so that the existing chain survives. (arrange in order)

Correct order:

def add_to_front(self, val):
new_node = self.Node(val)
new_node.next = self.head
self.head = new_node

Distractors (not used):

new_node.next = new_node
return self.head

CS131 Refresher: Parameter Passing, Recursion & Objects

Value, Reference, and Pointer Semantics

Why this matters

🎯 You will learn to

The Point class

✏️ Predict before you read on

🔧 Now write two of them yourself

Check your work

Solution

Step 1 — Knowledge Check

The Point Class in Python

Why this matters

🎯 You will learn to

From C++ to Python

✏️ Predict before you run

🔧 Your task

Run your Python code here

Solution

Step 2 — Knowledge Check

Mutation Versus Rebinding

Why this matters

🎯 You will learn to

The rule

🔧 Your task

✏️ Predict before you run

Solution

Step 3 — Knowledge Check

Recursion With No Loops Allowed

Why this matters

🎯 You will learn to

Recursion on the Rest of an Array

✏️ Predict before you write

🔧 Your task

Check your work (manual review)

Solution

Step 4 — Knowledge Check

The Same Recursion in Python

Why this matters

🎯 You will learn to

Slices replace pointer arithmetic

🔧 Your task

Solution

Step 5 — Knowledge Check

Building New Lists Recursively

Why this matters

🎯 You will learn to

A New List From the Remaining Values

🔧 Your task

✏️ Predict before you run

Solution

Step 6 — Knowledge Check

Virtual Dispatch and Object Slicing

Why this matters

🎯 You will learn to

The comedy club

✏️ Predict before you read on

🔧 Your task

Check your work (manual review)

Solution

Step 7 — Knowledge Check

Linked Lists Without a Destructor

Why this matters

🎯 You will learn to

The C++ original

🔧 Your task

✏️ Predict before you run

A Later Review

Solution

Step 8 — Knowledge Check