This page contains links to archived versions of the Stanford CS106B (Programming Methodology) webpage in the quarters I've taught it.
This was a memorable quarter of CS106B. The first nine weeks functioned more or less like any other offering of CS106B, but things went into emergency mode in the last week in response to the emerging COVID-19 pandemic. I imagine that I will probably remember that last detail more than the other changes I made to the course simply because it was a trying time for both students - many of whom had to leave campus on short notice - and staff.
However, this quarter also represents a huge gradient step for me in tuning and improving CS106B. My goal for this quarter was to keep the parts of the Winter 2019 offering of CS106B that worked best while also tuning and tweaking other parts of the course that were in greatest need of improvement. Because course evaluations are delayed due to the COVID-19 emergency end-of-quarter deadline adjustments, I'm writing this without having full knowledge of how the class was received by students, and this assessment is based on conversations with section leaders and individual students throughout the quarter.
Let's begin with the main structural changes. On the course calendar side, I decided to adopt Julie and Marty's week-to-week assignment schedule, where we gave out more, smaller assignments rather than fewer, larger assignments. I am a huge fan of this system! It definitely seemed to keep students more regularly engaged with the course topics and let me give assignments that targeted areas we previously haven't had a chance to explore. It also required me to pay much more attention to assignment length and topic prioritization, since with less time per assignment there's more of a need to keep things on point.
On the topic side, I decided to significantly cut the treatment of graphs and graph algorithms. I had always been a bit confused about what role CS106B's exploration of graphs was meant to play, and in the end I decided to introduce them in the last week of the course and use the extra time freed up that way to cover other topics in more depth. That gave me space to run four new lectures - one on big-O notation, one on hashing strategies, one on linked lists, and one on Huffman coding. (More on these later.) I also dialed back the treatment of a few topics, removing the discussion of recursive enumeration as a standalone concept and cutting tries from the section on linked structures.
The last major change was with the prerequisites. This was one of the first quarters where a large majority (75%) of students were entering the course from Python rather than Java, making the onboarding to C++ a bit trickier than in past quarters. In many ways I think I handled this well (the first assignment was a good warm-up to C++, and there were a couple of lectures where I had "multilingual" coding examples for students to draw from). In others, I could have done a better job anticipating the questions students would have been asking (the use of && and || versus and and or, the missing in operator, returning vs. printing values) and could have slimmed down a few lecture topics by using multilingual examples (particularly, with regard to strings).
To give a rough approximation of the main changes made: the first week mostly ran the same as the first week in Winter 2019, but with a bit more of a focus on C++ syntax given the Python transition. The second week's lectures were similar to the Winter 2019 version, except with a shiny new example for queues, a "looper" device that plays music in a loop. (That example worked pretty well, I think, though maybe I should have seeded it with music that was more recent. ^_^) I also removed the cell towers optimization problem and replaced it with a simpler one involving finding the maximum value in an array several different ways, which I think worked a lot better and was definitely less intimidating. The last big shift here was me moving away from the sorted set and map types to the hash set and hash map types, which was motivated by the fact that hash containers seem to have won the day and deserved a bit more prominence.
The biggest set of changes were to the recursion lectures, where I did some more major surgery. We began with the same general structure of doing graphical recursion with trees, though I did change things up by having that example then explore questions about returning the total number of lines drawn in each tree. I then continued on to do recursive subsets, but did so much more slowly and in more detail, showing a step-by-step progression from a longer-hand version of the code to the more slimmed-down, sleek final version using the overloaded operators. I also showed two different versions of the subsets code - one that works by generating each subset one at a time and printing the result, and a second that returns a collection of all possible subsets. I think I could have done a better job here motivating and introducing wrapper functions, but overall this seemed to go much more smoothly than in Winter 2019.
One major change I made in the recursion lectures was a separate introduction of recursion combined with iteration as an object in and of itself. I used the Sierpinski carpet example to show off a not very controversial graphical recursion with loops, then transitioned from there into generating permutations, which seemed to go over well with students. The next lecture then did combinations, which I think went okay (though people were still a bit confused about making hash sets of hash sets. From there, I explored recursive backtracking more or less in the same way that I've done in the past.
After concluding recursion, I transitioned to big-O notation and sorting algorithms. I added a new lecture here on big-O notation in the abstract that was primarily focused on getting people to think about growth rates in general. This was motivated by the fact that, in Winter 2019, people seemed to be really stuck on the midterm with analyzing big-O of non-coding-related concepts, plus the fact that people tend to think that big-O is specific to algorithms rather than a more general concept. This lecture, surprisingly, seemed to fall flat because too many people thought it was too obvious an idea! That strikes me as a good thing, and in the future I'm planning on keeping that lecture but slimming it down a bit. From there, I continued on with the regular discussion of sorting and searching, aided with new lecture demos that visualize runtime plots. I tried a few experiments there with motivating the sum 1 + 2 + ... + n = Θ(n2), though I think I'll be rolling those back. Stated differently, I'm glad I tried this out, and I was pleasantly surprised that students were so comfortable with these ideas!
The lectures on abstraction design were more or less unchanged from Winter 2019 and worked quite well. Most edits were minor, such as using the "delete bomb" animation more consistently across the slides to reinforce how deallocation works.
The week after this, though, was quite a departure from what we've usually done. At this point, I'd historically moved on to linked lists and BSTs, but instead I decided to bring in hashing and hash tables. I developed a new HashFunction template class that wrapped some of the icky bits about using globally-defined hashCode functions and modding by the table size, and that seemed to work swimmingly. We were able to cover everything I wanted to cover about chained hashing and hash function basics in a single lecture. The next lecture then introduced linear probing and Robin Hood hashing, which seemed to go well and fed into a new hashing assignment (more on that later).
We then switched to talking about linked lists. I broke down linked lists into three lectures: a first lecture on recursive data and recursive linked list processing, a second lecture on iterative linked list manipulations, and a final lecture on pointers by reference and multiple pointers into linked lists. This general breakdown seems like a real winner and seemed to work well, as evidenced by the coding assignment. It still will need some local tuning and editing, such as removing one version of recursive deletion from the first lecture and a few topic shuffles in the second lecture, but I'm generally very happy with how this turned out! I made some new slide animations showing off how the linked list traversals worked, and those seem like real keepers as well. (And, as long as I'm randomly listing minor changes, I decided not to teach for loops over linked lists and to instead cover just basic while loops, and that seemed to give folks one fewer item to worry about.)
Week nine was all about BSTs, and the lectures there were essentially unmodified from Winter 2019. The very last lecture I gave was an improved version of my Huffman coding lecture from Winter 2017, updated with more interactive examples for folks to work through and generally better patter. Around this time, the COVID-19 pandemic was starting to more obviously impact students, with people showing up to class wearing masks and the LaIR switching to being purely online. Later on the Friday after giving this lecture, the university announced that all classes were to be held remotely and that in-person finals were cancelled, at which point I decided to cancel the last week of classes. It's a shame I didn't get to teach those topics - let's hope that I get another shot next time.
On the assignment side, the assignments this quarter were mostly edited versions of ones from Winter 2019, with some major changes. I replaced Flesch-Kincaid readability from Assignment 1 with a new Plotter assignment to help people navigate the jump from Python to C++; if anything, it was too simple! For Assignment 2, I decided to use the Rising Tides assignment from Winter 2019's Assignment 7, plus a new personality quiz assignment "You Got Hufflepuff!" That latter assignment ended up being somewhat tricky for students, mostly due to the fact that it's a decent amount of code and the decomposition wasn't provided. I'm on the fence about whether to reuse it. On the one hand, people seemed to like it and I got a few emails from students later on who found the concepts introduced (particularly, cosine similarity) useful in other contexts. On the other hand, maybe something like the good old fashioned Random Writer would work equall well here. I'm going to need to wait for EOQ feedback before passing judgment on that one.
Assignment 3 was a slightly modified version of the one from Winter 2019. I decided to cut the Riding Circuit problem, both for length and because I knew we weren't going to get to permutations by the time the assignment went out. In its place, I added a "bridge" problem in which students had to enumerate all possible ways of emphasizing the words in a sentence. That problem was designed to help people shift from the easier Sierpinski and Human Pyramids problem to the trickier Shift Scheduling, and it seemed to work quite well in that role. I would be happy using this assignment more or less as-is in future quarters.
For Assignment 4, I used the Doctors Without Orders and Disaster Planning problems from previous offerings. (In retrospect, it is somewhat ironic that there's a global pandemic on now and I used those two assignments). I also added in one of Julie's debugging exercises (exploring Towers of Hanoi and debugging a broken permutations implementation), which was a nice touch. This assignment seemed to go pretty well and likely could be used again with minimal modifications, with the exception of adding more souped-up test cases for the two coding questions.
Assignment 5 was given out around the midterm exam, so I gave people two weeks to complete it. It was basically the Data Sagas assignment from Winter 2020, with the exception of Lower Bound Searches, the addition of a short debugger assignment, and (new for my versions of CS106B) a series of short-answer questions about binary heaps that preceded the HeapPQueue component. In retrospect, I think it would have been better to split this into two assignments: a "lite" Assignment 5 that's just the recursive combine implementation, and a "regular" Assignment 6 made of the binary heap and streaming top-K problems. That would have kept people on a more regular schedule and prevented people from slipping behind after completing the midterm.
Assignment 6 was a new assignment modeled after the hashing assignment Kevin Gibbons and I developed for CS166. We had students code up linear probing hashing with tombstone deletion and compare it against Robin Hood hashing with backward-shift deletion. This assignment also included some brief short-answer questions to ensure students understood the algorithms they'd be coding up. This assignment, I think, could easily enter my regular rotation. It needs a bit of tuning, in particular with regards to the test cases. We found that many people wrote buggy code for either tombstone handling or backward-shift deletion that wasn't caught by the test driver, since the test driver purely used the class interface to check whether things worked. Adding more intrusive tests - such as the ability to explicitly probe what's in a particular cell - would be really useful here. (The current test driver framework I have doesn't play nicely with the friend keyword - maybe there's another way to do this?)
Assignment 7 was designed specifically to push on linked lists and debugging linked structures. I'm really happy with the assignment I developed! The first part generates labyrinths of four-way linked lists based on hashes of student names, then asks students to use the debugger to find three items in the maze. This went over well and was a ton of fun to code up - I got to implement randomized Kruskal's algorithm and an Erdos-Renyi random graph with BFS - but had some pain points. Apparently std::mt19937 is cross-platform compatible, but std::uniform_int_distribution doesn't use the same algorithm on all systems? The second part of the assignment asked students to code up linked list algorithms for manipulating DNA sequences. It was inspired by a related assignment that Owen Astrachan submitted to Nifty, but ended up being its own beast. This assignment seemed very reasonable for students and I'd love to include it in future rotations. Fun fact: apparently Windows does really slow allocations of small objects on some systems, so I put together a custom memory allocator that, in addition to making it really clear when something has been deallocated, makes things run nice and quickly. That was a fun coding project too. :-)
The final assignment, Assignment 8, was Huffman coding. I had been playing around with the idea of using explicit queues rather than bit stream classes for this assignment and put together a version that used a Queue<Bit> type, and I think it turned out nicely. As a finishing touch, I left a congratulatory note for students compressed in the starter files for them to decompress, which I think was well-received. I also set up the starter files so that the OS would open decompressed files using the standard associated application, which made the final demo "pop."
All of the assignments this quarter were assembled using the Stanford C++ Libraries, plus some custom libraries I'd put together for managing events and windowing. I ended up putting those files into a standalone repostitory called MiniGUI that's included as a submodule, so it should be easy to keep using that system in the future. Many of the updates to MiniGUI were simple modifications from before (better handling of dark mode on Mac, bug fixes due to std::chrono::high_resolution_clock not using the same timer as Qt on all systems, etc.), others simplified setting up new assignments (a simpler header file with X-macros to customize the GUI), and the most notable were some touch-ups to the test driver. The test driver now shows all tests that will be run and which tests are running so that it's easier to spot a stalled test, and as of the final version of the starter files they automatically check for leaks of objects tagged with the TRACK_ALLOCATIONS_OF macro. I'm very excited to backport this to the earlier assignments to see how big of a difference they make.
Putting all this together was very much a team effort. A huge thanks to Maya Ziv, Trip Master, and Richard Lin for their excellent preflighting feedback on the new assignments; things definitely would not have turned out this well without their help! I am also deeply indebted to my head TA Katherine Erdman for providing daily updates on the LaIR and for advocating so fiercely on behalf of the SLs to make grading easy and streamlined.
The last two weeks of the quarter, though, were the ones I think I'm going to have to look back and evaluate the most. In response to the COVID-19 pandemic, I cancelled the last week of class (my decision) and converted the exam to an online exam through BlueBook (university decision). A few days later undergraduates were asked to leave campus if possible, and after some heartfelt conversations with the other lecturers and lots of weighing of options I decided to make the final optional and not count against students who didn't take it. (The university then made this mandatory the next day). After the shelter-in-place order came down from the county, the university asked most of the remaining undergraduates to leave campus. After what I will admit was a very rough day of contemplation, I decided to set a C- floor for all students who had earned at least 60% on the assignments and to approve all petitions to change from letter grades to CR/NC. That decision was the best option I could come up with that balanced the needs of students who had to immediately leave campus on short notice (or who were facing far worse situations) with other students' desires to round the quarter out and earn a letter grade for their work. I set and used a very generous grading curve that I think, in conjunction with the previous policies, was a generally reasonable way to handle things. Once the COVID-19 situation is resolved and I have the benefit of hindsight, I'd like to reevaluate these decisions. Could I have made better decisions knowing only what I knew at the time the situation was evolving? Were there decisions I should have made earlier or more aggressively, and did I make any major mistakes in this process? And finally, what lessons should I take away from this, both as an instructor and as a person?
So suffice it to say, it was an interesting and exciting quarter. I am very eager to get another chance to teach CS106B so that I can do the tuning and tweaking necessary to make the course run better and to inspire more students, and I'm hoping that that opportunity happens at a time where people are safe, healthy, and happy.
To all of my students this quarter - I hope that you're safe both physically and mentally, and I hope our paths cross again at some point! Take care.
This quarter's offering was an ambitious overhaul of the course materials from the Winter 2017 offering. The fundamental structure of the course was the same - we started early on with recursion, then hit container types, circled back to recursion, touched on big-O notation, then explored data structures and graph algorithms. Aside from that, most of the content in the course was new or heavily revised from prior iterations.
The most visible change to the course was the new suite of assignments. I redesigned most of the assignments this quarter with the intent of giving students problems to work on that were intrinsically interesting or which touched on real-world data analysis. In many ways, I think this worked. The new assignment that replaced Priority Queue, Data Sagas, put searching and sorting algorithms to work in exploring data sets, including some data sets pulled from public APIs. My replacement for Trailblazer, Calligraphy (which was co-developed with Ashley Taylor), included simulations of the impact of sea level rise, with data pulled from the NOAA. Other assignments, such as a revised introductory recursion assignment that included several interesting fractal patterns and a replacement for Word Ladders that simulated crystal growth, focused on the idea that simple rules can give rise to complex, emergent behaviors. I also replaced our older, console-based starter files with GUI-driven programs and added some highly polished demo apps to showcase what student code did. I'm particularly proud of my visualizations of the Human Pyramids and Sierpinski Triangle problems, as well as the runtime plotter for Data Sagas.
As is always the case with a rollout of new materials, in many ways these assignments will still need some tuning. The MiniBrowser assignment I co-authored with Ashley Taylor was much more difficult than expected, primarily due to me misjudging the difficulty students would face in translating from diagrams into code. The revised version of the Recursion! assignment didn't resonate with students as much as I'd hoped that it would. These are items that will need some attention in future iterations of the course.
One of the more visible changes I made to the assignments was the inclusion of a series of automated unit testing suites. I think this helped expose bugs to students better than before and made it easier for students to write their own test cases. At the same time, I seem to have underestimated the difficulty of learning to write good tests, and that's something I'm going to need to look at more closely in the future. Do we just ship tons of tests with the starter files and tell students that they don't need to write their own? Or do we include a Guide to Testing that helps students figure out what sorts of test cases to write? That's something I'm going to need to think about more in future iterations.
I did a major overhaul of the lectures this quarter with the goal of motivating concepts more from first principles rather than presenting "here's the finished product." I'm really proud of some of these new motivations, such as using the respiratory tree to motivate binary search trees and looking at historical methods of organizing text information to introduce tries. I also improved the quality of the visuals and animations in some key places, such as detailing how the delete keyword operates on the pointee rather than the pointer.
One set of overhauls to the lectures that really surprised me was the presentation of recursion and recursive backtracking. Based on my notes from the past version of the course, I changed the way I introduced recursive exploration and recursive optimization to distinguish between the style of recursion (enumeration, optimization, backtracking, etc.) and the structure being explored (subsets, combinations, permutations, etc.). My hope was that this would help students get a better sense of how to conceptualize the problems they were working on. Surprisingly, this didn't seem to work very well, and many students were very much caught off-guard on the assignments and exams when the problems didn't exactly match these topics. This is something I'm going to need to spend a lot of time thinking about for the future. At the end of the quarter, students seemed to have a phenomenal grasp on recursion, though the process of getting there was tough. Is this due to an overly ambitious set of targets for students to reach, is this because that transition is just plain difficult, or is this due to that teaching model not working particularly well?
In terms of topic coverage, after giving things a lot of thought, I decided to eliminate the discussion of Dijkstra's algorithm and A* search and to focus more on BFS, DFS, and related algorithms. The motivation here was that our coverage of Dijkstra's algorithm and A* primarily consisted of "here's the algorithms, now go code them up" rather than "here's the algorithms, and let's make sure you really understand how they work." This, I think, was a good call. The new Calligraphy assignment did a great job reinforcing BFS and DFS and on the final exam students absolutely nailed the conceptual questions on these algorithms. I was very surprised to see, however, that students were most excited by Kruskal's algorithm and its applications to data clustering, which I'd included simply because I thought it was a fun topic and we had the space in which to present it. In future offerings of the course, I might decide to make that more of a direct focus. I'm considering replacing MiniBrowser with an assignment about data exploration (possibly using random forests and agglomerative clusterig?), in which case we could integrate Kruskal's algorithm more tightly into the course materials.
This quarter, I also did a major overhaul on the Stanford C++ Libraries, replacing our implementations of the container types with the equivalent STL containers to improve the quality of the debugging information generated. I also added in a number of static_assert checks in places where students might get into trouble (using non-comparable or non-hashable types as keys in containers, for example), which probably will save a lot of students a lot of headache in the future. I also massively cleaned up the build system on Windows, reducing compile and run times by as much as 75%. I now know far more about Qt Creator and qmake than any reasonable person should. :-)
I've left copious notes to myself about how to proceed differently next quarter, and I'm excited to see how the revised version ends up going. There are a few spots where there's still a good amount of work to do - I suspect that A1, A2, and A6 might need some major revisions to get into a good working state - and other spots where things are mostly working just great (A4, A5, and A7). There are a lot of missing materials in the course (a Guide to Debugging, a Guide to Recursion, etc.) that could save huge amounts of student and staff time in the LaIR that I'll need to build out. But given the sorts of feedback I heard from students at the end of the quarter - many of whom had no prior programming experience and were blown away by the breadth of the material and how well it connected to other topics - I get the sense that I'm on to something here. The question for the future is how best to strengthen the components that work and tune and tweak the parts that are in need of help.
It had been almost four years since the last time I taught CS106B when I took over this offering of the course, and I decided to use the opportunity to make a number of changes to the course and the assignments.
In this quarter, I also introduced an updated Assignment 0 with an animated Guide to the Debugger based on the animated guides I'd developed for CS103. I also included an "Honor Code Maze" assignment that required students to work through a series of questions about the Honor Code before starting. The number of Honor Code cases emerging from CS106B this quarter was significantly lower than in the past, and I was very happy with how that turned out.
The biggest changes to the assignments were an overhauled Assignment 3 that pushed more on recursive enumeration and optimization than the past, and a completely new Assignment 4 (Recursion to the Rescue!) that explored recursive backtracking in the context of a number of socially-relevant applications (patient scheduling, disaster preparation, pathogen detection, and US Presidential Elections). These assignments were tough, but based on the experience I think that with some small updates and tweaks the assignment could become a mainstay in my offering of the course.
I also invested a lot of time updating the section handouts to provide significantly more coverage of core topics. I'm extremely happy with how those turned out and am definitely looking forward to using them more in the future!
In a break from what I did in previous offerings, I updated many of the assignments to introduce new technical concepts (structures, stack overflows, memoization, etc.) that didn't fit cleanly into lecture. I was pleasantly surprised with how well this worked and will definitely consider doing this again in the future.
In a more visible set of changes, I also updated the lecture examples, assignment starter files, and section handouts to use more C++11 concepts, such as automatic type inference (hugely useful in recursion), const correctness (which I had mistakenly thought was the norm in CS106B... oops), the nullptr keyword, and uniform-intialization syntax (also hugely useful in recursion).
The last set of major updates were to the lectures. While content-wise they were mostly the same, I spent more time talking about big motivating examples, like using recursion to figure out the best team to send to a developing country or big-O notation to analyze the efficiency of grade-school arithmetic. I also pushed much harder on recursion throughout the quarter, using it to dramatically simplify the presentation of linked lists and binary search trees. I think that I still have some work to do at the beginning of the quarter to get stronger motivating examples for elementary recursion.
And I'm really, really proud of the exams from this quarter. I invested a ton of effort building four versions of the midterm (actual, practice, alternate, and yet another alternate) and a final that I think had genuinely interesting questions on them. It will be dramatically easier to teach this class in the future simply because I can fall back on those questions when I need to.
I feel like there's a lot more work to be done - upgrading the earlier lectures and assignments, rethinking the Huffman and Trailblazer assignments, revisiting how we teach graph theory, etc. But I feel like that's going to be a much, much easier task given that I now have a stable set of materials to work with.
A massive thanks to Anton and the CS106B section leaders for making this quarter so easy to teach. It was a pleasure to work with that team and I would be happy to do so again in the future.
My second offering of CS106B was 50% larger than the previous years' offering, but it was a blast! I refined the syllabus to slim down the breadth of material while increasing the depth, and overall students did quite well. This quarter also saw the introduction of a new first assignment (a modified "Welcome to C++" that included Flesch-Kincaid readability) and new final assignment (Trailblazer).
This was my first run teaching CS106B and it was a lot of fun. Although I had given a few CS106B lectures before as an undergrad, I had never actually taught the entire course. It was exciting getting to develop different algorithmic approaches and data structures in lecture, and I'm looking forward to the next iteration of the course.