COMPUTER SCIENCE PROJECTS
RELATIONAL DATABASE
Developed parts of a fully functional database in Java by :
-
managing the way records are stored on pages and the way B+ Tree indices are structured.
-
implementing several of the join algorithms covered in class (like Page and Block Nested Loop Joins and Grace Hash Join) using an Iterator interface, as well as a cost‐based query optimizer to enable efficient query execution.
-
implementing a concurrency control manager with deadlock prevention while using table-level shared and exclusive locking, to make the database capable of supporting multiple concurrent transactions.
Pintos is a simple operating system framework for the 80x86 architecture and this project was entirely implemented in C. The first part of this project explored concurrency and scheduling, which involved implementing priority scheduling of threads and priority donation from high-priority threads to blocking threads holding locks. It was interesting to read through the source code for the OS and see how things like locks, semaphores, and threads were represented.
The second part of this project involved understanding how the OS interacts with user programs as we implemented many common syscalls like exec (Pintos version of UNIX fork + exec), wait, read, write, etc. It was interesting to study a simple view of the file system and read an implementation of file descriptors.
The third and final part of this project involved implementing parts of a distributed key-value store, using Two-Phase Commit as a protocol to track and log interactions between client, master, and slave servers. This project helped us appreciate complicated distributed systems and how they deal with consistency, availability, and partition tolerance.
PINTOS OPERATING SYSTEM
Artificial Intelligence Projects
Reinforcement Learning - Implemented value iteration and Q-learning and then tested the learning agents first on a simple Gridworld domain (from class), then applied them to a simulated robot controller (Crawler) and Pacman.
BayesNets - Implemented inference algorithms for Bayes' Nets, specifically variable elimination and value-of-perfect-information computations. These inference algorithms enabled reasoning about the existence of invisible pellets and ghosts.
Ghostbusters - Designed Pacman agents that use sensors to locate and eat invisible ghosts. The agents advance from locating single, stationary ghosts to hunting packs of multiple moving ghosts with ruthless efficiency.
PAGERANK WITH SPARK
Utilized the MapReduce programming paradigm to implement two different variations of the classic PageRank algorithm, in the Apache Spark framework. Transformed an input Resilient Distributed Dataset of a list of edges into an output RDD of a list of nodes and their PageRank scores. Then ran the implementation on several large networks using a cluster of Amazon EC2 servers.
Designed and implemented a version control system in Java from scratch, with strict runtime and memory requirements, that mimics some of Git’s basic features like initialize, add, commit, remove, log, global log, find, status, checkout, branch, remove branch, reset, merge, rebase and interactive rebase. Developed serializable Java classes to store metadata, account for the failure cases of Gitlet commands and issue user warnings about “dangerous” commands that overwrite files. Developed a similar project, called " BearGit", in C for my computer architecture course.
Version Control System - Gitlet
Implemented a two-pass assembler in C, that translates a subset of the MIPS instruction set (22 instructions and 9 pseudo-instructions) to machine code. The functionality of the assembler was divided as follows:
Pass 1: Read the input file, strip the comments, expand the pseudo instructions after input validation, and record the address of each label into the symbol table. Finally, write the output to an intermediate file .
Pass 2: Read the intermediate file and translate each instruction to machine code after validating instruction syntax and arguments. Then generate the relocation table and write the instructions, symbol table, and relocation table to an object file.
MIPS Assembler
Implemented a linker in MIPS, which processes object files (input) and generates an executable file (output). The linker has two main tasks, combining code and relocating symbols. Code from each input file’s text segment is merged together to create an executable. The Linker works by creating an empty global symbol table (which contains absolute addresses) and creating a separate relocation table for each input file (which contain relative addresses). Then by the Linker iterates line-by-line through each input file and looks for .text, .symbol, and .relocation sections to determine the number of bytes the instructions will take, read each symbol and store it into the symbol table for .symbol section or into the input file's relocation table for .relocation section. Finally, the linker reads one instruction at a time from the .text section of each input file and writes it to the output file after checking if the instruction requires relocation.
MIPS Linker
Twitter Trends
Developed a parser for tweets and captured key components of a tweet (location, text, time etc) in Python. Performed detailed sentiment analysis on each tweet to determine degree of positivity and negativity of a tweet. Utilized Natural Language Processing (NLP) and location-based aggregation techniques.
NGordnet
Implemented generic abstract data structures in Java to analyze the hyponyms, relative popularity of words, categories & lengths of words over time using Zipf's law. This project explores how the volume of printed works in English has changed over time, as well as the structure of the is-a relationships of words in English language. I effectively utilized the semantic lexicon WordNet, Google's Ngram dataset and TimeSeries with an YearlyRecord to aid the NGordNet User Interface.
Developed a Scheme Language Interpreter in Python to read Scheme expressions, evaluate primitive procedure calls, define and evaluate symbols, define and evaluate lambda expressions, call user-defined procedures, evaluate special forms and allow an unbounded number of tail recursive calls in constant space. I learned a lot about parsing and syntactic analysis from this project.
Scheme Interpreter
Implemented Autocomplete feature and AlphabetSort in Java, with runtime that's linear in the length of the files, using ternary search tries combined with priority queue.