Introduction and Motivation

Around 1.5 years ago, when I was teaching CS2040S, I once joked with my students that since I taught CS1101S and CS2040S, a natural career progression would be to teach CS3230 next. I truly meant it as a joke, but little did I know back then that I would eventually go on to do it.

CS3230 Design and Analysis of Algorithms was taught by Prof Arnab Bhattacharrya in the recent semester (AY21/22 Sem 1). The module is part of the graduation requirements for computer science majors, and I believe computer engineering majors have the option to take this module to fulfill their requirements. It builds on CS2040S, providing more advanced tools and techniques to design (divide & conquer, greedy, dynamic programming) and analyse (amortisation, randomised analysis) algorithms. Theoretical content such as the famous “P vs NP” problem is also briefly touched upon.

I was initially not even thinking of teaching the module. How it came to be was that my previous CS3230 tutor was offered by Prof Arnab to teach, but he could not due to his commitments. My tutor then asked if I would be willing to teach in his place. I happened to have sat in Prof Arnab’s other classes before, and felt like I could be confident in the quality of his teaching (which was a complaint for other instructors in previous semesters). Moreover, I also have gained confidence in my own abilities over the semesters. Lack of confidence was one of the reasons I had not taken it up sooner. The final reason was because in the same semester, I was going to take CS5234 Algorithms at Scale. I thought CS3230 would be a good way for me to revise my fundamentals as well. A little fun fact is that when I taught CS1101S, I took CS2040S. When I taught CS2040S, I took CS3230. Then when I taught CS3230, I took CS5234. It’s almost as if I taught things in order to solidify my fundamentals in the same semester. All things considered, I decided that it would be a good time and opportunity for me to take up the role.

Introduction

The time is 7PM. Your software project is due at 11:59PM. You have yet to write the developer guide to document your software which is part of the submission. You are writing a testing plan which also serves as a guide for your graders to assess your software. As you were writing the steps to test, you discovered a regression. This feature that was working just 3 hours ago is now causing the application to crash! What happened? What would you do?

I was in this exact situation recently for a school project. I had to decide whether it was worth identifying this bug and writing a patch for it (and potentially breaking other features for whatever reason it might be), or whether I should continue with the rest of the submission documents. I panicked really hard. In that moment of desperation, from a deep region in my memory, I suddenly recalled: git bisect.

I had known the principle of git bisect – it essentially performs a binary search for the first commit which caused a particular bug. It was going to be the first time I was using it. I quickly looked up tutorials and documentation online. 10 minutes later, I found the commit which caused the bug. Quickly patched it up (whether there were further bugs is another story altogether), and went back to writing my other submission documents.

In that one usage, git bisect easily became my favourite git command. In this post, I hope to provide a simple use case and guide to use git bisect, while demonstrating how fast it can help you identify the violating commit.

A basic understanding of data structures and algorithms (array/linked lists and linear/binary search) and git (e.g. committing, checking-out commits) is preferred, but I think the concepts are intuitive enough and I will try to make it as accessible as I can.

Introduction

This is a reflection that is quite overdue! I was a little busy throughout the May-July vacation period, and could only find time to update my blog now. Better late than never, I suppose! Just a warning though, there is a lot of text, and almost no pictures in this post.

CS2040S is NUS’ Data Structures and Algorithms course. Originally, there were only two variants of the module, CS2040 and CS2040C. The CS2040S variant is introduced this recent academic year (AY19/20) as a means for module management of the growing computing cohort (or so I heard). More specifically, it is compulsory for Computer Science undergraduates matriculating in AY19/20 to take this variant of the module. The module uses Java for the problem sets, but written exams allow usage of pseudocode.

This recent semester (AY19/20 Semester 2), the module is taught under Prof Seth Gilbert, Prof Ben Leong, and Prof Soo Yuen Jien (also known as Uncle Soo). Prof Seth does the main delivery of content, while Prof Ben and Uncle Soo handle the administrative matters of the module. The module does not always have the same lecturer(s). When I was taking the module in AY19/20 Sem 1, it was taught under Prof Harold Soh. Future semesters might also be different.

I was a teaching assistant (TA) who taught a weekly 2-hour tutorial (discussion group) sessions of 12 students. I’ll write about my experience in this blog, while making some comparisons with my experience teaching CS1101S in the previous semester. Take note that this post is not meant to be a review of the module.