During my exchange to the University of British Columbia (UBC), I decided to enrol myself in a software engineering course, CPSC319. Working in teams of 6, we were required to build a greenfield project for companies who have kindly sponsored the CPSC319 course. My team had the priviledge to work with Amazon and we were tasked with building a tournament creation web application for them.

Hairless Cats

My team decided to name ourselves Hairless Cats. Why? I don't really know. It was a random name that we all thought was amusing.

As a team of 7 (which eventually became 6), we split ourselves and worked on different components of the web application. I decided to work on the backend server and helped to design the REST API needed for our application.

Over the course of the semester, we managed to build a functional tournament application that could support the creation of tournaments and teams. Teams in a tournament were matched according to their schedules. At the end of each match in real life, our application would record the result of the game. Finally, it would aggregate the results and determine who would be the winner.

Highlights and Challenges

Of course, what is a software engineering project without its challenges? Thankfully, there were plenty of highlights as well that kept me going. The pointers I will be mentioning below will be mainly related to the backend side of things as I did not handle the frontend.

Algorithm design

One of the main reasons why I decided to work on the backend was because of the business requirement of match scheduling. Most of the projects that I've worked on were simple enough – basic sorting algorithms and for loops. When we were briefed about the project, I was very excited to hear that we needed to formulate a design to match teams according to their availabilities. A simple sorting algorithm would not suffice.

One of the first steps I took was to model our problem as a graph problem. Logically, each vertex would represent an entity – a team, a match or a timeslot; each edge would represent some sort of matching or availability. After a bit of brainstorming, I decided to further improve it to be a bipartite graph model. Vertices in the left partition represented each match whereas vertices in the right partition represented timeslots. An edge between match m and timeslot v indicates that match m can be played at timeslot v.

Our scheduling problem can now be effectively modelled as a maximal cardinality matching problem.

We are given a graph G, and the goal is to find a matching containing as many edges as possible, that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

An important special case of the maximum cardinality matching problem is when G is a bipartite graph, whose vertices V are partitioned between left vertices in X and right vertices in Y, and edges in E always connect a left vertex to a right vertex.

https://en.wikipedia.org/wiki/Maximum_cardinality_matching

With a fair bit of googling, I presented to the team a viable solution using the Hopcroft-Karp (HK) algorithm.

The Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of as many edges as possible with the property that no two edges share an endpoint.

https://en.wikipedia.org/wiki/Hopcroft–Karp_algorithm

With limited time on our hands, I did not get to write out the code for the HK algorithm by myself. Thankfully, the people at Princeton University were kindly offering their code to the public. I borrowed their code and adapted it for our use case. The missing piece of the puzzle was to create the match vertices. Depending on the tournament, the types and number of matches created would be different. In a round robin tournament, all teams will have to play each other once. In a bracket style tournament, teams will be paired up and the winners will be able to advance to the next round. I designed simple algorithms to help to create such matches based on the tournament style.

Overall, I was really glad to have had the opportunity to try my hands at designing the algorithm needed for our application. It allowed me to apply the reduction techniques learned in my Algorithm Design class.

REST API design

Designing the API was a huge challenge. I never took any classes on it and did not know of any API design principles. My team mates were also quite clueless, but we learned as we went along.

One of the first few things I did was to seek out various companies and find their publicly documented API endpoints. One company which I took heavy inspiration from was Mailchimp. Their marketing API endpoints were, in my opinion, pretty well documented. Using a simple markdown style, I documented our APIs in similar fashion to theirs.

Working in a team, we definitely had quite a few disagreements or miscommunications about what endpoints to use, their names and their return values. Each one of us had different ideas of what our API should look like. Our API was constantly changing and this was attributed to our poor planning at the start of the project. Such changes frustrated our frontend developers and progress was unnecessarily delayed.

This challenge highlighted to me the importance of proper design planning. It also made me aware of my incompetencies in REST API design and I will definitely be reading up more on them.

Spring Boot and Code Design

Our sponsor Amazon wanted us to design our backend using Java. Naturally, Spring Boot was the framework that came to mind. The only problem? None of us knew how to use Spring Boot. I had to sit through a couple of hours of youtube crash courses on Spring Boot just to understand how to use it.

Thankfully I learned pretty fast and was comfortable with working in Spring Boot. The next challenge was getting the whole backend team on the same page when it came to code design. Similar to our REST API design, we had troubles with code syntax, patterns, naming conventions, formatting etc. Without uniformity and consistency at the code level, it was difficult to scale our application. Of course, we have to cut ourselves some slack as we had to learn Spring Boot and deploy a proper MVP within the span of a few months, on top of our usual school workload. But it was truly a challenge having to work with a different tech stack.

Conclusion

When I was selecting courses to take during my exchange, I was wondering if it was worthwhile to take up CPSC319. Most people would come to exchange and take up easy courses; everything was on a pass/fail basis and easy workloads meant more time enjoying the pleasantries of exchange life. In addition, CPSC319 was a 4 credit course, one credit above the usual 3 credit courses offered at UBC. Considering the circumstances, it would be logical for me to not take the course at all. Throughout the semester, I did hover over the drop course button a few times. The workload was quite intense and seeing all my friends enjoy the ski slopes in Vancouver made me question my decision.

However, I am glad to have persevered through. The course provided me plenty of opportunities to develop my technical skills. It also exposed me to working with people from very different backgrounds. Though we all spoke english, the team was surprisingly quite international – we had 2 koreans, 1 mongolian, 1 singaporean, and 2 canadians. Our differences in technical expertise, cultures and age made communication very challenging. Adding on to the stress, we had to develop an application for the tech giant Amazon. Thankfully, our sponsor from Amazon, Mr Smith, was a very nice mentor and gave us excellent feedback. Our TAs were also decently helpful and pushed us on even when the going got tough.

Would I do it again? Absolutely. Though I will definitely be going at it being more prepared. It was truly an enjoyable course to take, and I don't regret my time spent on it.