First, I’d like to apologize for the delay in releasing the final homework / programming assignment on B+ trees and performance. It was TBD for much longer than I intended, but I’ve pushed its deadline back a lesson to give you an additional weekend to work on it (and to deconflict the submission date with a GR in Comp Sci 380).

This final assignment has two parts: a short answer portion to be completed individually and a programming portion that should be completed with a partner. (Technically you can complete the programming portion yourself, but I don’t recommend it.) The short answer portion contains a handful of questions that I estimate will require between 30 minutes and an hour to complete. The programming portion requires you to implement a B+ tree, which will probably take 4–7 hours working with a partner.

Implementing a B+ tree is very helpful to understanding how they work. As a student, I also enjoyed implementing a B+ tree much more than self-balancing binary search trees (e.g., AA, AVL, and red-black trees). Given where we are in the semester and recognizing that this course is not focused on data structures, I’ve provided implementation notes with pseudocode for the three operations that you must implement. I hope that the pseudocode will keep your implementation time reasonable, but it won’t make the assignment trivial either – there’s still some tricky parts. (I’m also providing the pseudocode because I nearly ripped my hair out earlier in the week when my implementation wasn’t consistent with several examples, and I finally realized that there was a mistake in the textbook that I was consulting!)

I’ll be releasing the GitHub Classroom assignment tomorrow (link to be published on Blackboard like other programming exercises), which will include automated testing. Though I have high confidence in my current implementation, I’m also planning to reimplement the assignment using another programming language next week in hopes that I’ll be the one to discover any lingering errors in the pseudocode. (Note: Don’t wait to start. There’s big extra credit if you happen to find an implementation mistake before I do!) Because a handful of the tests are randomly generated using my current implementation, I will also throw out these tests if 80% of the submissions do not pass them or I find a mistake, but this scenario is somewhat unlikely given that I’ve achieved 100% statement coverage when testing my current implementation.

As always, let me know if you have questions. I may devote a session of office hours early next week to getting started so stay tuned for calendar updates if interested! Also, to the best of my knowledge, everything is built out for the rest of the course at this point. Expect minimal changes – mostly clarifications – to what’s posted on the website for the remaining lessons.