Nevertheless, she persisted

This was during Spring 2022, when I made the wise decision to take 3 CS courses. Next semester I took 4 math classes and 1 cs class. Clearly my decision making was sound.

I my first midterm in Data Structures, taught by David Mount, we received the following question.[1]

Imagine a tree, where nodes alternate between having 2 and 3 children. The root has 2 children. The left child of the root has 2 children, the right child of the root has 3.

Calculate a recurrence for the number of nodes at depth \(i\) (hint: work two levels at a time, express \(n\left(i\right)\) in terms of \(n\left(i-2\right)\)), and an an explicit formula for the same.

alternating tree

Being stubborn, I decided to write \(n\left(i\right)\) in terms of \(n\left(i-1\right)\). The professor found this unexpected and recommended I appeal (he gave me a 0 and left a comment). There was a back and forth between us where I convinced his I was right, straight out of one of those rhetoric of teaching manuals. I got full points.

I then proceeded to barely pass the class, whippee!

  1. See problem 4 of