Exemplary Undergraduate Work
This repository contains an assortment of exemplary coursework completed as an undergraduate student at Tufts University. To maintain the academic integrity of these assignments, my work is only available to prospective employers upon request.
If you have a gitlab.com account, you can sign in and and request access. Alternatively, you may email me to request a deploy token or ZIP archive for this repository.
Note: All coursework was developed on Tufts' remote development servers and may not work on your system.
For your convenience, I have briefly summarized all included courses and projects. You may find these summaries useful even without access to the source material. Projects marked with a
Data Structures
Data Structures is the second course in the CS major sequence at Tufts. I opted to take this course in my first semester, skipping the introductory course. Critical topics include: dynamic arrays, recursive structures like BSTs and AVL trees, sorting, hashtables, and graph traversal.
-
In this assignment I implement a grep-like utility program, which is capable of searching for human-readable words in plaintext files within a filesystem. When executed, the program recursively populates a chained hashtable with the location of every instance of each unique word in the user-specified filesystem. After initialization, the program will accept queries and output all instances of query words.
Data Structures (TA)
After taking Data Structures, I was hired by the CS department to be a TA for the course. I have included a small collection of assignments/materials to which I have made significant contributions over the past year. Not represented are my contributions to the autograding framework used to assess the functional correctness of student submissions.
-
⭐ I developed this assignment from an existing lab to highlight the functional and structural differences between two different hashtable implementations and introduce students to abstract classes and inheritance. The code provided to students demonstrates how thoughtful inheritance maximizes code reuse, maintains a "single point of truth", and allows for polymorphic algorithms.
-
I developed this assignment from an existing project to gently introduce students to graph theory and empower them to explore several algorithmic strategies for traversal and path discovery. The code provided to students demonstrates an exemplary graph implementation and several C++ compiler optimizations (like the inclusion of a move assignment-overload and copy-constructor).
Algorithms
Algorithms is one of four upper-level core courses in the CS major sequence at Tufts, which I took in my second semester. Critical topics include: sorting, asymptotic analysis, dynamic programming, amortization, and graph theory.
-
In this assignment, I investigate the runtime complexity of a search algorithm on an augmented AVL and design a constant-time solution for the heap memory manager of an operating system that uses two hashtables. My solution is formatted entirely in LaTeX.
-
In this assignment, I demonstrate how indicator random variables can be used to represent complicated probabilistic systems and provably determine expected outcomes. Using this technique, I prove that, with a slight modification, the runtime of Quicksort is
O(nlogn)
. My solution is formatted entirely in LaTeX.
Machine Learning & Structure
Machine Structure and Programming is one of four upper-level core courses in the CS major sequence at Tufts, which I took in my second semester. Critical topics include: computer hardware, system architecture, language runtime, operating systems, and data representation.
-
In this pair programming assignment, I collaborated with a peer to investigate the effect of different approaches to data blocking on the runtime of several memory-intensive large-image transformations. After implementing the image transformation program, I used automated bash scripts to collect runtime data, and explained how runtime anomalies correlated to cache performance.
-
In this pair programming assignment, I collaborated with a peer to design and implement modular algorithms for lossy image compression and decompression. Rigorous testing indicated that, in most cases, our implementation had notably higher information retention after repeated compression and decompression cycles than the course reference implementation.
-
⭐ In this pair programming assignment, I collaborated with a peer to design a universal machine emulation. The emulator supports a sparse set of 14 instructions and is responsible for the management of a segmented memory system. Of particular note is the optimized emulator implemented in "fastum.c", which is the fastest single-threaded solution to this assignment ever submitted.
-
In this pair programming assignment, I collaborated with a peer to implement a reverse polish notation calculator in UMASM, an instructional assembly language designed for the universal machine implemented earlier in the course.
Programming Languages
Programming Languages is one of four upper-level core courses in the CS major sequence at Tufts, which I took in my third semester. Critical topics include: operational semantics, metatheory, type systems, Hindley–Milner type inference, pure OOP, and functional programming.
-
⭐ In this pair programming assignment, I collaborated with a peer to design a concise object-oriented implementation of arbitrary precision arithmetic in an instructional language (uSmallTalk). In the spirit of SmallTalk and pure OOP, our solution makes effective use of double dispatch to avoid unnecessary conditional logic.
-
In this pair programming assignment, I collaborated with a peer to implement a type system and static type-checker in SML for two sparse instructional languages. After we verified the functional correctness of our type system, we extended the languages with additional features like primitive arrays and mutable reference cells.
-
This project implements an arbitrary precision arithmetic module for SML using functors and opaque ascription. I use a recursive datatype to represent individual digits of an arbitrary base, which allows for elegant pattern matching and a concise recursive implementation.
-
⭐ In this assignment, I implement a SAT solver using continuation-passing style and investigate the runtime consequences of alternate operational semantics for lambda closures.