This is a post about how I wrote exam questions for CS 61B, Spring 2022, one of which was selected to go on the final exam. I'm not going to go into too much detail about the questions themselves, but I will talk about how I wrote them and what I learned from the experience.

Table of Contents

• The Question
• Exams at Berkeley
• The Process
• The Results

The Question

I could upload a version without my annotations, but I doubt a reader of this post actually wants to do the question. If you did, you'd probably be using past exams through a more official source. If you want an explanation of the solution for this, click here.

Exams at Berkeley

very important disclaimer: these are my views and only my views regarding exams. this does not reflect the views of any course, other person, or entity! this information may be outdated as well - this is not advice.

Exams are notoriously challenging. Questions rarely test material that could be memorized from a book; instead, they are about application. For a lot of people, this transition proves challenging; it means there isn't necessarily more benefit from studying the material covered in class for more time.

At the time of writing (and at the time this question was written), 61B was one of three courses needed to declare. Students admitted to the College of Letters & Sciences came in as undeclared, were required to take CS 61A, CS 61B (this class, on Data Structures), and CS 70 in order to declare CS. I believe this policy has been changed with intended majors, but I'm not an admissions counselor and the amount I know about the declaration process is very little, so I'll leave it to you to do more research if you'd like.

My point? This is an important class, and students take this class because they want to declare CS. Students thus care and study a lot for exams. And as a member of course staff, I wanted to do my part in creating fair, equitable exams meant to test students' understanding of the material, not gotchas or trick questions.

This isn't a post about how to study more effectively; there's countless resources online (and if you ask your GSI, I'm sure they'd be happy to help and offer their own insight). The purpose of this is to give some insight on the exam question that I wrote that was included in a final exam.

The Process

When exams were coming up, I had the option of submitting suggestions for review. If a given suggestion was seen as a good question, it would be included in the exam. I submitted a lot of questions for both midterms, but none of them made it on. I was a little disappointed, but I knew that I had to keep trying.

I think the biggest thing is that my questions made perfect sense to me - but little sense to anyone else. Exams should be challenging because they test your understanding of the material, not because they're confusing. I think I was trying to be too clever with my questions, and I was trying to be too clever with my solutions.

This particular question came about as a question I asked after a course staff meeting: what if we tried to make a BFS through a LLRB the same as it would be through its corresponding B-Tree? I thought it was a cool question, and I thought it was a good way to test students' understanding of the material. I wrote it up, and I submitted it for review.

If that made no sense, that's okay. I'll explain it in more detail below (marked in "technical talk", totally optional but included for the interested reader).

Technical Talk Starting

Let's say we want to store some information. We want to be able to search for this in an organized manner - maybe we have numbers, or text, or something else. One cool thing we can do is to create nodes where each node contains a value and reference to other nodes - where all the nodes to the left are "less than" and all the nodes to the right are "greater than". This is called a binary search tree, or BST.

The issue is that it's possible, based on the order of insertion, to create trees that are unbalanced. We would ideally like to enforce balance, to create better runtimes to access items. That's why we use a red-black tree, or LLRB. This is a BST where each node has a color, and the colors are used to enforce balance.

To be more precise, we now store multiple pieces of information in each node, creating what's called a B-Tree. This is difficult to implement, so we store different level information using colors.

The whole point of the question is to make going through the tree the same in both representations.

Technical Talk Ending

But here's the key thing: this question wasn't a part of class. No memorization would have helped. It was a question that tested students' understanding of the material, specifically how traversals worked, and how they could be applied to different data structures.

The Results

I don't have direct statistics on how many students answered this question right. Even if I did, I doubt I'd be allowed to post that kind of information on a public site.

Qualitatively, however, I personally felt that this question was challenging but doable - the sweet spot I was trying to hit. Further, there were multiple parts - so even if a student found one of the coding parts hard, there were other parts they could do for points (not to mention a number of other questions testing other concepts on the exam).

If I ever get the chance, I'd love to keep writing exam questions. I think it's a great way to test your understanding of the material, and it's a great way to help others learn. I'm grateful to have had the opportunity to write this question, and I'm grateful to have had the opportunity to teach this class.