Computer Science

Introduction

I had little to no experience with computer science upon entering university. I thought it would be a lot of computer programming—and yes it is—but it is a lot more than just that. Computer science is about problem solving efficiently, and we program computers to help us with that.

After completing university I am hoping to get into software engineering or a related field.

Courses

Intro to Computer Programming
Intro to Computer Science
Software Design
Intro to the Theory of Computation
Software Tools and Systems Programming
Computer Organization
Data Structures and Analysis
Principles of Programming Languages
Operating Systems
Algorithm Design and Analysis
Intro to Databases
Principles of Computer Networks
Computational Complexity and Computability

Languages

Python
Java
C
Racket
Haskell
RISC-V assembly
LaTeX

Tools

git
Unix/Linux/MacOS
Virtual Machines
Microsoft Office
Adobe Creative Cloud

Projects

ext2 File System Commands

November 2022 — December 2022

In this project, I learned about the ext2 file system and implemented (in C) file system commands to operate on an ext2-formatted virtual disk.

The commands I implemented:

mkdir (creating a directory)
cp (copying a file)
rm (removing a file)
ln_hl (creating a hard link)
ln_sl (creating a symbolic link)

Furthermore, I ensured that these commands are synchronized properly by guaranteeing mutual exclusion access to shared file system structures using mutexes.

Although these commands may seem simple and straightforward, in order to implement them for a particular file system is quite challenging. We need to work with binary data and need to have a good understanding of the file system that we are working with.

For example, say we have the following command: rm /folder/myfile. In the ext2 file system, every file and every directory corresponds to an inode. We would start at the root inode and search its data blocks (a linked list of directory entries) for an entry called “folder” and make sure that it is indeed a directory. Then we would search folder’s data blocks for an entry named “myfile” and make sure that it is indeed a file. Once all this has been verified, we can mark the inode and the data blocks (which hold actual file contents) for “myfile” as free so that they can be allocated by some other file or directory. Lastly, in the parent directory’s data blocks we need to reflect that “myfile” has been deleted by marking that entry as deleted in the linked list.

Page Tables and Replacement Algorithms

October 2022 — November 2022

Many students learn about page tables, address translation, and replacement algorithms. I got the opportunity to implement these ideas in practice. There were two parts to this project.

Part 1: Page Tables and Address Translation

In this task we are given virtual addresses and need to translate them into physical addresses using a three-level page table. This included bit manipulation and logical bitwise operations.

Basically, given a virtual address, we use some of the bits as an index into the first-level page table, some of the bits as an index into the second-level page table, some of the bits as an index into the third-level page table, and some of the bits as an entry offset. When we index into the first-level page table, we get a pointer to a second-level page table and when we index into the second-level page table, we get a pointer to the third-level page table. Then we use the offset to index into the third-level page table to retrieve our entry.

Part 2: Replacement Algorithms

In this task I implemented four different page replacement algorithms: FIFO, LRU, CLOCK, and ARC. Page replacement algorithms must be fast, hence I implemented these policies with efficiency in mind.

The idea behind replacement algorithms is that as pages are requested, memory will fill up. Once memory is full and a new page is requested, which old page do we evict to make room for the new requested page?

The FIFO (first in, first out) page replacement algorithm evicts the oldest page in the cache.
The LRU (least recently used) page replacement algorithm keeps tracks of recently used pages and evicts the page that has not been used the longest.
The CLOCK page replacement algorithm is a low overhead approximation to the LRU algorithm. It does not keep track of the least recently used page. Instead, it evicts a page that “old enough” which is done using reference bits.
The ARC page replacement algorithm is an advanced algorithm that keeps track of both recently used pages and frequently used pages plus a recent history of evictions. It is self-tuning, low-overhead, and scan-resistant that responds to changing patterns in memory accesses.

In the end, I also wrote a report in which I compared these replacement algorithms against each other by coming up with memory traces where one outperforms the other. I was able to observe the differences that a policy can make in practice.

Writing a Shell from Scratch

January 2022 — April 2022

In this project I wrote a C program that implemented a fully functional shell. This is the largest project I have worked on; it is also my proudest work.

Writing a shell from scratch is a large and daunting task, but I am glad I got the opportunity to experience it because I gained such a rich understanding of shells and Unix/Linux systems—which are widely used in industry today.

Features

My shell is called mysh and has the following features:

builtin commands such as echo, wc, and cat. Since a shell has so many commands, if I did not create a builtin for a command, I ended up using bash shell’s implementation by forking a child process and using exec.
supports storing an arbitrary number of environment variables by keeping track of them in a linked list data structure allocated on the heap.
manages the file system by implementing builtin commands such as ls and cd.
supports pipes and allows users to start processes in the background and foreground.
keeps track of running processes in a linked list data structure allocated on the heap.
ability to start a server in the background and listen for incoming messages. It can also send messages to other mysh instances with running servers.

Experience Gained

After completing this project I gained experience with

Unix and Linux operating systems
Common shell commands
C programming
Error checking and handling
Dynamic memory allocation on the heap
Working remotely on a different machine using ssh
Implementing functionality on a tight weekly basis
Writing well documented, organized, and extendable code
Thoroughly testing and reasoning code separately before merging it with the main application
git version control
Creating unit tests using pyTest

SIMON Memory Game

February 2022—March 2022

In this project I programmed the famous SIMON Memory Game in RISC-V assembly.

I gained valuable hands on experience with assembly language after completing this project.

In class we learned about certain conventions that need to be followed when working in assembly. For instance, before jumping to a function call we need to save certain registers. I remember when I was working on the project, I encountered a super hard to find bug because I forgot to save the value in one of my registers and the function I was calling kept modifying its value.

I also learned about the programmer’s view of memory. This included learning about the stack and heap and how they grow towards each other. So when I was working on the project I had to keep in mind to lower (and not raise) the stack pointer when saving values.

This project made me appreciate the abstractions that exist today. We are lucky to have high level languages like Python and Java that do most of this super low level work for us.

Furthermore, I wrote an instruction manual for my game. This document concisely explains all the features of the game and walks one through on how to play the game. I put in a lot of effort into this document and thought the final product came out great.

Linear Algebra Calculator

January 2022

I participated in the PyJaC Rebooted Hackathon with two friends. All three of us have interest in math and find the field of linear algebra fascinating. So we decided to challenge ourselves to implement something we learned in class as a computer algorithm.

Our idea was to program a Linear Algebra Calculator in Python with two features:

compute the determinant of a square matrix
row reduce a rectangular matrix

We tried to optimize our algorithms. For instance, for the algorithm that computes the determinant of a matrix, our idea was to search for the row/column containing the most number of zeros before starting the cofactor expansion.

This was a cool experience where I got an opportunity to directly apply both my math and computer science knowledge to achieve a goal.

Three Musketeers Board Game

October 2021—December 2021

This project was broken up into three phases:

Create a command-line interface version of the game using Java
Create a graphical user interface version of the game using the JavaFX framework
Work within a small team to improve code structure by recognizing common design patterns and by applying SOLID software design principles

There are two players: Guards and Musketeers. The Guards win if they manage to get all three Musketeers on the same row or column. The Musketeers win if they cannot capture any Guards (i.e. they cannot move) and if they are all not on the same row or column.

The game is playable in two modes:

Player vs. Player
Player vs. Computer (Random and Greedy strategies)

After completing this project, I gained valuable experience with

designing heuristics for random and greedy strategies
JUnit and JavaFX frameworks
applying object-oriented programming principles and SOLID software design principles in Java
recognizing and applying design patterns to simplify software design
git version control (branching, merging, and poll requests)
coordinating and working within a team to develop software
agile scrum methodologies (which are used by teams of professional software engineers today)

Bitmap Image Compressor

March 2021

This is one of my favourite projects because of its practicality. I programed a bitmap image compressor using Python. The main idea behind this application is recursion and trees.

To store an image in our program, we begin by spliting the image into four quadrants, and then we further split each of those quadrants recursively until we get down to single pixels. We can use a Quadtree (a tree data structure where each node has exactly four children) to store individual pixels as leafs in the tree.

To compress images we introduce something called a loss level which will be inputted by the user. Now when we are storing the image by splitting it into four quadrants, we can calculate the standard deviation and mean of the pixels inside of each quadrant. If the standard deviation is less than the user specified loss level, then we can treat the entire quadrant as a single pixel and its colour value will be given by the mean.

Meepo is You

February 2021

In this project I gained experience with applying object-oriented programming principles, reasoning with code not written by me, and working with the pygame and pytest frameworks.

Meepo is You is written in Python and has a nice graphical user interface (note the GUI was given to me, my task was to implement the game logic).

The player can move around the map using the keyboard. They can push blocks on the map to create and modify the rules of the game.

Phrase Puzzler

October 2020

In this project I was required to implement game functionality and logic for a word puzzle game in Python. It is a command-line interface game with three modes:

One Player
Player vs. Player
Player vs. Computer (Easy and Hard)

The objective of the game is to guess a hidden word. On each turn, you can either:

Guess a vowel (-1 point)
Guess a consonant (+1 point)
Guess the word

So very similar to Hangman, but to guess a vowel you need at least one point. You gain points by guessing consonants in the hidden word correctly. The player that determines the hidden word first wins.