This page contains links to archived versions of the Stanford CS106B (Programming Methodology) webpage in the quarters I've taught it.
This quarter, which ran remotely due to the COVID-19 pandemic, was in many ways a continuation and refinement of the version of CS106B I piloted last winter. The basic outline of the lectures was essentially unchanged (though with a lot of tweaks and edits; more on that later), and the panel of assignments was more or less what we did last Winter (with a bunch of updates, of course). In that sense, it seems like I really am converging on a formula that works for the class, and at least for the immediate future I think the work that needs to be done is mostly targeted, focused updates rather than a system review of how to structure things. It's been quite a process to get here, and it feels really good to have things feeling polished!
On the assignment front, the major changes this offering included dramatically expanded test coverage, the introduction of "demo barriers," improvements to SimpleTest and MiniGUI, and the introduction of a framework for mixing in console-based assignments with a single switch. I'll address each of these in order.
From students' perspectives, perhaps the single biggest change was the expansion of the provided test coverage. In past offerings of CS106B, we included an initial set of tests that covered many but not all of the important cases. This quarter, I decided to significantly ramp that up, providing fairly thorough and detailed tests intended to target specific classes of errors. For example, let's take the perenially popular but challenging Disaster Planning assignment. In the past, the test coverage consisted of a few sample transportation grids and checks to make sure the student code passed those grids. The problem was that these tests could sometimes be sensitive to the order in which cities were picked. In recent offerings of CS106B, I'd switched from using tree (sorted) containers to using hash (unsorted) containers. This meant that you'd sometimes see tests passing with broken code because the order in which cities were considered purely coincidentally happened to work, whereas other times the tests would fail when a bad ordering was detected. To address this, I rolled back the use of hash containers early on and instead focused on tree containers. I then added tests that took a small (six-city) grid, then ran all possible permutations of the labels of the cities in the grid to ensure that the student code worked regardless of the order in which cities were processed. This exposed more errors than in past offerings, and led to students writing much better code.
Another example was the introduction of "invasive tests." Through some template shenanigans, I extended SimpleTest so that the test cases, once granted permission to do so, could access private members of a class. That allowed me to overhaul Assignment 7 (The Great Stanford Hash-Off) by specifying the exact internal representation of the hash tables, then writing tests that read private fields to ensure that the hash table contents matched what they were supposed to at each point. This dramatically cut back on the number of errors made in that assignment and led to much better coding and learning outcomes. I'm thinking I might want to expand this into Assignment 6's priority queue!
Finally, I started introducing more targeted stress tests into the assignments, each of which was designed to hang unless the implementation made "smart" decisions about how to proceed. For the recursion assignments, this meant writing test cases that would pass if the runtime was, say, O(2n) but not, say, O(n!). For the priority queue and hashing assignments, this meant constructing specific inputs that would trigger pathological behavior if, say, the Robin Hood search optimization wasn't enabled.
Because I was able to expand on the test coverage, I was able to introduce "testing barriers" that block access to the code demos until all of the relevant tests pass. This completely changes the dynamic about how students validate things. Rather than doing a mix of running tests and running demos to validate things, students could only use the "run tests" option until everything was working, at which point they could start running the demos. This was especially helpful in the recursion assignments (A3/A4), the priority queue assignment (A6), and the hashing assignment (A7). In those assignments, it was previously common to worry about code crashing right out of the box due to missing implementations or to have tests pass but demos either crash or break in unexpected ways. With the test barriers in place, this entire class of concern points go away!
I also (finally!) managed to isolate the cause of the "populating font family" warning message on macOS that used to give students a headache early in the quarter. Turns out we had a bad default font specified for graphical rendering. The fix was easy - just change the default font when you're on macOS to be something else. That in turn required me to do some patching up of the MiniGUI framework to replace all previous uses of font string literals with a new font package that selects fonts based on the OS.
The other big change to MiniGUI was support for assignments that ship with both graphical and console-based demos, a huge boost for accessibility. The basic idea is that the core MiniGUI system now has two hooks to specify demos: GRAPHICS_HANDLER, which replaces the old "return a shared_ptr" system, and CONSOLE_HANDLER, which (as the name suggests) does everything from the command-line. By adding the line #define MG_CONSOLE_MODE to Demos/GUIConfig.h, the program switches into console mode. This makes it much, much easier to build accessible assignments: we simply make one set of files that go out to students, then, when needed, instruct students how to make the change to console mode. It also unifies the starter files for graphical and console modes, eliminating the need to maintain two parallel sets of files that had to be manually synced.
On the SimpleTest front, in addition to the new invasive test support, I fixed a longstanding issue where the EXPECT_EQUAL macro would fail spectacularly when literals with commas were provided as the second argument. This new version allows for code like EXPECT_EQUAL(v, {1, 2, 3}), which previously wasn't supported. I also boosted the performance of the library by having the validation macros not generate their error strings until an actual error occurred, which saves students a lot of time. I've made a note for myself to consider adding in an ASSERT macro or something similar to it that would let students write assertions to check invariants, a suggestion from the SLs that I really, really like.
Turning back to the assignments: I mentioned one of the biggest changes to the assignments, which was the revision to the hashing assignment in which we gave students the internal representations to use in their implementations. This, I think, dramatically cut down the difficulty of the assignment without sacrificing much rigor. That, plus the addition of test barriers and more expansive stress tests made it so that students could be confident that their solutions were correct before jumping into the timing analysis. It looks like there's still some more work to be done here (the chained hashing code needs to be cleaned up to make apples-to-apples comparisons easier, and there's a need to be clearer about how the load factor varies as insertions are performed), but overall I think this assignment is likely here to stay.
I did some major surgery on the "You Got Hufflepuff!" problem from Assignment 2 as well. Previously, we had students build an end-to-end implementation, which seemed to be a bit too challenging for them at the start of the quarter. The new version I put together decomposed the problem for them into a series of milestones. However, I'm now not as convinced that this assignment actually hits the learning goals I want it to hit (working with maps and sets). I think I'm going to need to replace that with something else, and I'll have to do some exploration to figure out exactly what to replace it with.
I also decided to split what was one large assignment from last time into two smaller assignments. The new Assignment 5, dubbed "Bag'O Big-O," had a mix of big-O analysis questions and the recursive combine problem. The new Assignment 6 consisted of just the heap priority queue and streaming top-k. I think this split is good, but I think the new A5 needs a bit of work. The recursive combine problem might not be the best example of how big-O analysis leads to better / faster code. Maybe it would be better to have students code something up two ways, one slow and one fast, and viscerally feel the difference? And while I think it's good to give students code samples to analyze, I think there may be a bit more need to tune how that's framed so that students don't just read the runtime plot and form their conclusions from there, instead diving deeper into the code to see what's up.
On the linked list front, the "Splicing and Dicing" assignment seems solid, but isn't as flashy as some of the others. Given all the excitement about mRNA vaccines, maybe there's something cool to do there, like "make an mRNA vaccine from a genome?" Or maybe there's some other biological process that would be more exciting to get students working with?
I have some exciting updates staged for next time. I've expanded the terrain maps for Rising Tides to include more areas of the world. I received a bunch of new road networks for Disaster Planning from students, and am planning on shipping those out next time as well. I think these will instantly make the assignments more engaging, and I'm excited to see how they turn out!
Turning to lectures: I was extremely nervous going into this quarter because for years I've been in Hewlett 200, where there are two separate projector screens. That let me use one screen to do code in Qt Creator and another to do slides. I wasn't sure how I was going to get that working on Zoom, where I get exactly one screen to work with! I ended up going with OBS Studio, where I had two screens open (one for slides, one for code), then composited them together with OBS to form a single video stream consisting of me plus whatever other windows I wanted to show off. This seems to have been a huge hit with students, and I'm seriously wondering whether I should keep doing this once we're back in person! It reframes the lecture as a "follow my visuals with me" and keeps things interesting and exciting. This also got me thinking more seriously about how to get the two screens to support one another, and the results seem, so far, to be really great.
The Zoom webinar format also worked really well due to the lovely Q&A feature. This allowed students to ask questions in real time, getting answers from my head TA and section leaders, and then letting me focus on the most interesting ones at points in the lecture where there was a nice break in the action. I love this format and would love to keep it up once we're back in person.
Focusing on the substance of lecture rather than the style: most of the lectures this quarter were more or less the same as in the past, with a few major updates, especially early on. I overhauled the first containers lecture to focus on value and reference semantics, doing more explicit examples of the differences and asking students to make predictions about what was going to happen before running the code. I updated my treatment of maps and sets to more directly explain why they'd be useful compared with other container types, and integrated the question of "what happens if you run the looper with a stack rather than a queue?" into my lecture on stacks and queues.
One set of changes I'm particularly proud of were in the lectures on recursion. At the start of some of those lectures, I added in a "what's wrong with this code?" problem that showcased a common recursion error in a non-recursive context (for example, forgetting to capture a return value, or returning in the middle of a loop). This made it a lot easier, later on, to explain why a piece of recursive code didn't work correctly, and gave a nice vocabulary for helping students out in office hours. Those were clear wins, and I'd love to keep this up going forward.
Perhaps the single biggest change I made was to the lectures on dynamic arrays. For years, I've been using an analogy of "a dynamic array is a building with different floors," but the slides never reflected this. I created a fairly intricate set of animations showing this idea off, and it seems to have dramatically improved student understanding. I'm really proud of how this turned out - even if it took a full day of animating to get it to come out correctly. :-)
The last major experiment of the quarter was with the exams. I decided to try giving 48-hour take-home exams that were open computer, so much so that we provided starter files with test cases for the various problems. I figured this would be enough time for folks to either demonstrate what they'd learned or quickly figure it out. Exam scores were high, and generally people did really, really well. I'd like to experiment with this format more in the future. Is 48 hours too long? Maybe 24 hours would be better. How much testing should we provide, and what sorts of tests should those be?
I'm writing this summary before course feedback is in, but the preliminary midquarter evals were very positive, much more so than I had expected, and I'm getting the sense that I'm on to a winning formula here. The question now is how to tune things to patch up the issues I've identified here.
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 equally 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.