This is the first of two posts that are reflections on college. This focuses on teaching, and the next one will be about the gap year that I took.

Nearly two years ago, when I first started this blog, I wrote a post about writing exam questions for 61B back in Spring 2022. This is a follow-up post, in which I do three things: first, I have some random thoughts, second, I give some lore of a few questions that I wrote in the past two semesters, and third, I have some short closing thoughts.

Table of Contents

• Joining Course Staff
• Questions
  • Fall 2023
    • Midterm 1: Printer Problems
    • Final: Asymptotics
  • Spring 2024
    • Midterm 1: MC, Lost in Pointers
    • Midterm 2: Awesometotics
    • Final: Polynomials
• Closing Thoughts

Joining Course Staff

I used to describe 61B as a really fun club where you get paid to be in it. There's a large emphasis on working hard - this might be outdated soon, but TAs are expected to know basically everything - discussions, labs, projects, exams, and what's happening in lecture since we staff office hours where questions can be about any subject. At the same time, we have fun, and people have a good time being on staff. I'll elaborate on this in a later post, but not being able to teach was probably the thing I missed the most on my gap year.

Frequently, I'm asked how to join course staff. I started by applying to be an academic intern the summer right after I took the class. The class got last-minute expansion funding, and I got an interview to be a tutor (an hourly role, usually the step before becoming a teaching assistant). I remember practicing for it nonstop for a week, and I got the role. I tutored that summer, and it was quite challenging since I had struggled in the class, but I learned a lot. I applied to be a TA for the spring semester, referencing the work I had done in the summer, and managed to stay on staff.

There are two things I want to point out:

1. Luck plays a huge role. If there wasn't expansion funding that summer, I may not have taught, and I may not have gotten an interview in the future. I'm grateful for these opportunities, and recognize that it's not all me.
2. Don't count yourself out. I applied to CSM (Computer Science Mentors), a club that does free mentoring for small groups of students (similar to discussion sections). I unfortunately couldn't get an interview, and was quite discouraged. Having been in clubs leading recruitment, the process is largely imperfect and subjective. If you're interested in teaching, keep applying.

Questions

Every exam, I suggested a number of questions to be included. Sometimes, these made it to the exam, but more often than not, they didn't. I have omitted all questions that were not included in the exam, as they could potentially be used later.

Fall 2023

Midterm 1: Printer Problems

Solution

I came up with a different version of this question at first.

Final: Asymptotics

Solution

The initial idea for this question came from Spring 2022. The goal was to design an airline system that had bugs in it. Part of the question was runtime analysis. Specifically, how long does the checkIn method take to run with respect to the number of flights N?

The code for this is below, but note that there was also an interface called Guaranteed and classes called NewDataStructure, Passenger, Ticket, and Flight with much of these files omitted for space.

package com.airlinecompany;
import java.lang.Math;
class AirlineSystem implements Guaranteed {
    private List<Flight> _flights;
    // constructor, other instance variables omitted
    /** Checks in a user to the Airline System.
     * @return -1 if passenger is being checked in; otherwise return a value.
     */
    public Integer checkIn(Ticket t) {
        _newDataStructure.include(t);
        int N = 0;
        int value = 0;
        for (Flight f : _flights) {
            N += 1;
            if (f._flightNumber == t.getFlightNumber()) {
                f.addPassenger(t.getPassenger());
                return -1;
            }
            value += confusing(N);
        }
        return value;
    }
    void addFlight(Flight f) {
        // omitted
    }
    void confusing(int N) {
        if (N <= Math.random().nextInt(150)) {
            return (int) Math.random() * flights.size();
        }
        // Version 1 (easier), uses Math.sqrt(N)
        // assume constant time arithmetic for Math.sqrt(N) calculation
        return confusing(Math.sqrt(N)) + confusing(Math.sqrt(N));
        // Version 2 (harder), uses bit shifts to estimate sqrt
        // logarithmic time with respect to input
        // works by right shifting away half of the bits each time
        int C = N;
        while (C > 0) {
            N = N >> 1;
            C = C >>> 2;
        }
        System.out.print(N);
        return confusing(N) + confusing(N);
    }
}

This question is a little tricky, since initially it seems to be constant time with the if statement. However, take a look at the Flight class below:

package com.flightcompany;
class Flight {
    public String _flightNumber;
    // omitted
}

It's easy to miss this detail, but two strings being compared with == compares the memory addresses, not the values. This means the if statement is always false, which then triggers the two versions. Here are the answers if you're curious per version:

1. The confusing recursive calls are confusing(N) = confusing(Math.sqrt(N)) + confusing(Math.sqrt(N)). This creates a tree of height $log log N$. The work done at every layer follows the pattern $1 + 2 + 4 + ... + 2^k$ where $k$ is the layer number since printing takes constant time. Thus, the overall runtime is (from geometric sum) $\frac{1(1-2^{log log N})}{1-2}=logN-1=\Theta(logN)$.
2. The bit shifts are like having a "fast" and a "slow" pointer through $N$ and it's copy $C$. This means half of the bits are discarded from $N$, so it becomes an estimate of square rooting to a power of 2. This allows for similar analysis for the height of the tree being $log log N$ but means the work done at every layer is logarithmic with respect to the size of $N$. The sum is $1logN + 2log(sqrt(N)) + ... + 2^klog(N^\frac{1}{2^k})=logN+logN+...+logN=\Theta(logNloglogN)$ where $k$ is the layer number.

The version that was ultimately included in the exam was a heavily simplified version of this question. It's challenging, but part of that comes from obscurity (the question was very long) and the trickiness of the question to recognize the effect of the bit shifts. The difficulty ideally does not come from these things, but rather from the concepts being tested.

Spring 2024

Midterm 1: MC, Lost in Pointers

note: I only suggested part (e) of question 1, not the rest of question 1.

I suggested two multiple choice questions, one of which was included at the end of this question. Thinking of these questions was quite hard, as I was just coming up with weird scenarios.

Solution

Technically, I didn't suggest this question. But I had a similar idea that I was working on in parallel. The question was about finding a node in a doubly linked list that was corrupted. The problem I was running into was infinite loops (see if you can figure out the cases that trigger that with the following code):

public class DLList {
    // constructor and other methods omitted
    public Node findWrongNode() {
        Node curr = sentinel;
        int forwardLength = 0;
        int backwardLength = 0;
        while (curr != sentinel) {
            forwardLength++;
            curr = curr.next;
        }
        curr = sentinel;
        while (curr != sentinel) {
            backwardLength++;
            curr = curr.prev;
        }
        curr = sentinel;
        if (forwardLength > backwardLength) {
            while (curr != sentinel) {
                if (curr.next.prev != curr) {
                    return curr;
                }
                curr = curr.next;
            }
        } else {
            while (curr != sentinel) {
                if (curr.prev.next != curr) {
                    return curr;
                }
                curr = curr.prev;
            }
        }
    }
}

The solution that we went with in the exam used the size method instead of doing this technique and only computed the length in one direction.

Midterm 2: Awesometotics

Solution

I had nothing to do with this question; my suggested runtime question was deemed too challenging. This did have my name (in part (f)), however, so it's worth including here.

Final: Polynomials

Solution

This question was one I initially proposed for midterm 1. It had these two parts (without the runtime portions) as well as the add and multiply methods below:

// add takes in two polynomials and returns a new polynomial
public static Polynomial add(Polynomial a, Polynomial b) {
    Polynomial result = new Polynomial();
    Term currA = a.sentinel.nextTerm;
    Term currB = b.sentinel.nextTerm;
    Term currResult = result.sentinel;
    while (currA != null && currB != null) {
        if (currA.exponent == currB.exponent) {
            currResult.nextTerm = new Term(currA.coefficient + currB.coefficient, currA.exponent);
            currA = currA.nextTerm;
            currB = currB.nextTerm;
        } else if (currA.exponent > currB.exponent) {
            currResult.nextTerm = new Term(currA.coefficient, currA.exponent);
            currA = currA.nextTerm;
        } else {
            currResult.nextTerm = new Term(currB.coefficient, currB.exponent);
            currB = currB.nextTerm;
        }
        currResult = currResult.nextTerm;
    }
    if (currA != null) {
        currResult.nextTerm = currA;
    } else {
        currResult.nextTerm = currB;
    }
    return result;
}

// multiply takes in two polynomials and returns a new polynomial
public static Polynomial multiply(Polynomial a, Polynomial b) {
    Polynomial result = new Polynomial();
    Term currA = a.sentinel.nextTerm;
    Term currB = b.sentinel.nextTerm;
    while (currA != null) {
        while (currB != null) {
            Term nextTerm = new Term(currA.coefficient * currB.coefficient,
            currA.exponent + currB.exponent);
            result.addTerm(nextTerm.coefficient, nextTerm.exponent);
            currB = currB.nextTerm;
        }
        currA = currA.nextTerm;
    }
    return result;
}

The question was made more formal by the instructors in terms of definitions and some changes to the wording, but the core question idea was the same - an interesting use of Linked Lists.

Closing Thoughts

I'm incredibly grateful for the opportunity to have been on staff over the past few years. I've learned a lot, met some great people, and had a lot of fun. There are only a few things in life that give a sense of satisfaction, and teaching has been one of those things for me.