Programming Resume:
Description:
This resume serves to tell you more about me as a programmer. Not just the classes I’ve taken and the skills I’ve learned but also what type of programmer I am, how I approach and solve problems, and what my strengths and weakness are in programming. I will start by covering the classes I’ve taken and showcase some work from those classes as well as explain what the work represents and why I chose to showcase it. Ill then go through the specific programming skills I’ve acquired since I started coding in 5th grade and again showcase and describe some code that I believe represents those skills. Finally ill end with a paragraph describing my style of programming and talk a bit about myself and personality and how it affects my work life. I would also like to stress I believe my programming is best expressed in both of the large scale personal projects: Osou and Mirror Quest rather than the work I had to complete for school. both projects are accessible from this website (see top right) I will talk more about the specific skills I’ve gained from these projects in the skills section of this resume.
Classes:
data structures was not the first programming class I’ve taken, but it is the first one worth mentioning. This was the weed out class for CS majors at my school. The hw assignments were always in C++ and we typically very difficult (think 3-4 leetcode medium-hard problems at once). As the name suggests we learned about the standard template data structures and their complexity, often being required to remake the data structure from the ground up. Despite taking it 3 years ago this class is why I’m more comfortable with C++ than any other programming language. if you’re interested the file containing all my data structures hw can be found here. It is a lot to look through so to summarize we had homework pertaining to: Pointers, Dynamic Memory, Recursion, Big O Notation, Vectors, Lists, Sets and Maps(Trees), Priority Queues and Hash Tables. Ill include hw 8 which was about trees (specifically a bvh) below as a reference for a typical hw assignment.
Grade: A-
// Partial implementation of binary-tree based set class similar to std::set.
// The iterator increment & decrement operations have been omitted.
#ifndef BVH_h_
#define BVH_h_
#include <iostream>
#include <utility>
#include <algorithm>
// -------------------------------------------------------------------
// TREE NODE CLASS
template <class T>
class Node {
public:
Node() : children(), depth(0) {}
BoundingBox box;
std::vector<T> data;
Node* children[3];
unsigned depth;
};
template <class T> class BVH;
// -------------------------------------------------------------------
// TREE NODE ITERATOR CLASS
template <class T>
class tree_iterator {
public:
tree_iterator() : ptr_(NULL), child_iterator(NULL), i(0) {}
tree_iterator(Node<T>* p, int n) : ptr_(p), i(n) {assign_child(n);}
tree_iterator(const tree_iterator& old) : child_iterator(NULL) {copy_iterator(old);}
~tree_iterator() {destroy();}
tree_iterator& operator=(const tree_iterator& old) {destroy(); copy_iterator(old); return *this; }
// operator* gives constant access to the value at the pointer
const T& operator*() const { int n; const Node<T>* p = get_ptr(n); return p->data[n];}
// comparions operators are straightforward
bool operator== (const tree_iterator& rgt) { int n1; int n2; return (get_ptr(n1) == rgt.get_ptr(n2) && n1 == n2); }
bool operator!= (const tree_iterator& rgt) { int n1; int n2; return (get_ptr(n1) != rgt.get_ptr(n2) || n1 != n2); }
// increment & decrement will be discussed in Lecture 19 and Lab 11
//pre increment
tree_iterator& operator++() {increment(); return *this;}
//post increment
tree_iterator operator++(int) {tree_iterator temp(*this); increment(); return temp;}
//pre decrement
tree_iterator& operator--() {decrement(); return *this;}
//post decrement
tree_iterator operator--(int) {tree_iterator temp(*this); decrement(); return temp;}
private:
// representation
Node<T>* ptr_;
tree_iterator* child_iterator;
int i;
void assign_child(unsigned n) {
//when constructing iterator it auto assings the child to the left most branch
//or right most if iterating backwards which is given in n
if(ptr_->children[0] == NULL) {
child_iterator = NULL;
if(n==2) i = ptr_->data.size()-1;
return;
}
child_iterator = new tree_iterator(ptr_->children[n], n);
}
//recursive function that constructs and manages a hierarchy of chained iterators
//that correspond to the levels of the tree
bool increment() {
if(ptr_->children[0] == NULL) {
//checks to see if there is still space to increment on the leaf node
//if there is just increment the integer i which corresponds to a spot in the leaf node
//if there isnt returns to the parent iterator which the deletes its child and creates a new one
//at the next child
i++;
if(i==(int)ptr_->data.size()) {
i=0;
ptr_ = NULL;
return true;
}
return false;
} else {
//if this is not a leaf node it cascades until it finds a leaf node
if(child_iterator->increment()) {
delete child_iterator;
child_iterator = NULL;
i++;
if(i==3) {
i=0;
ptr_ = NULL;
return true;
}
child_iterator = new tree_iterator(ptr_->children[i], 0);
}
return false;
}
}
//pretty much the same as increment with minor variations
bool decrement() {
if(ptr_->children[0] == NULL) {
i--;
if(i==-1) {
i=0;
ptr_ = NULL;
return true;
}
return false;
} else {
if(child_iterator->decrement()) {
delete child_iterator;
child_iterator = NULL;
i--;
if(i==-1) {
i=0;
ptr_ = NULL;
return true;
}
child_iterator = new tree_iterator(ptr_->children[i], 2);
}
return false;
}
}
//returns a reference to a the leaf node along with an integer that specifies
//which shape on the leaf node its pointing too
const Node<T>* get_ptr(int& n) const {
if(child_iterator==NULL) {
n=i;
return ptr_;
}
return child_iterator->get_ptr(n);
}
//standard recursive copy function
void copy_iterator(const tree_iterator& old) {
i = old.i;
ptr_ = old.ptr_;
if(old.child_iterator != NULL) {
child_iterator = new tree_iterator();
child_iterator->copy_iterator(*(old.child_iterator));
}
}
//recursively calls deletes on the iterators since they are dynamically allocated
void destroy() {
if(child_iterator != NULL) {
delete child_iterator;
}
}
};
// -------------------------------------------------------------------
// BVH CLASS
template <class T>
class BVH {
public:
BVH(unsigned split, unsigned depth) : split_threshold(split), depth_limit(depth), size_(0) {root_ = new Node<T>;}
BVH(const BVH<T>& old) : size_(old.size_), depth_limit(old.depth_limit), split_threshold(old.split_threshold) {
root_ = this->copy_tree(old.root_); }
~BVH() { this->destroy_tree(root_); root_ = NULL; }
BVH& operator=(const BVH<T>& old) {
if (&old != this) {
this->destroy_tree(root_);
root_ = this->copy_tree(old.root_);
size_ = old.size_;
split_threshold = old.split_threshold;
depth_limit = old.depth_limit;
}
return *this;
}
typedef tree_iterator<T> iterator;
int size() const { return size_; }
bool operator==(const BVH<T>& old) const { return (old.root_ == this->root_); }
// COLLISION, INSERT
void insert(T const& shape) { size_++; return insert(shape, root_); }
bool collision(T const& shape) {return collision(shape, root_); }
// ITERATORS
iterator begin() const {
iterator p = iterator(root_, 0);
return p;
}
iterator end() const {
return iterator();
}
iterator rbegin() const {
return iterator(root_, 2);
}
iterator rend() const {
return iterator();
}
//STUFF FROM PARTIAL.H
void statistics(bool print_tree) const;
void render_recolor(std::ostream &ostr) { render_recolor(ostr,root_,Color(128,128,128)); }
//construct hierarchy
void construct(std::vector<T> elements) {build_tree(elements, root_, 0);}
private:
// REPRESENTATION
unsigned split_threshold;
unsigned depth_limit;
Node<T>* root_;
int size_;
//static utility
static bool sortByX(const T& s1, const T& s2) {
if(s1.getCenter().x < s2.getCenter().x) {
return true;
}
return false;
}
static bool sortByY(const T& s1, const T& s2) {
if(s1.getCenter().y < s2.getCenter().y) {
return true;
}
return false;
}
// PRIVATE HELPER FUNCTIONS
void destroy_tree(Node<T>* p) {
if(p == NULL) {
return;
}
for(unsigned i =0; i<3; i++) {
destroy_tree(p->children[i]);
}
delete p;
}
Node<T>* copy_tree(Node<T>* old_root) {
if(old_root == NULL) {
return NULL;
}
Node<T>* new_root = new Node<T>;
new_root->box = old_root->box;
new_root->data = old_root->data;
new_root->depth = old_root->depth;
for(unsigned i = 0; i<3; i++) {
new_root->children[i] = copy_tree(old_root->children[i]);
}
return new_root;
}
bool collision(const T& shape, Node<T>* p) {
//uses the bvh to look for collison recursively
if(!p->box.overlaps(shape.getBox())) {
return false;
}
if(p->data.size() != 0) {
return intersect(p->data, shape);
} else {
for(unsigned i = 0; i<3; i++) {
if(p->children[i] != NULL && collision(shape, p->children[i])) {
return true;
}
}
return false;
}
}
double get_added_area(BoundingBox b1, BoundingBox b2) {
//b1 is box of shape to be added
//b2 is box of branch that will be added to
BoundingBox test_box = b1;
test_box.extend(b2);
double added_area = test_box.getArea() - b2.getArea();
//return area that will be added if the shape is added here
return added_area;
}
void insert(const T& shape, Node<T>* p) {
p->box.extend(shape.getBox());
if(p->children[0] == NULL) {
//checks to see if this leaf node has open slots
//if it does it simply adds the shape to the leaf node
//if it doesnt it splits the leaf node and then continues through the function
if(p->data.size() < 3 || (p->depth == depth_limit && depth_limit != 0) || p->data.size() < split_threshold) {
p->data.push_back(shape);
return;
} else {
//split data into 3 groups in a similiar way that the construct function does
if(p->box.dx() > p->box.dy()) {
std::sort(p->data.begin(), p->data.end(), sortByX);
} else {
std::sort(p->data.begin(), p->data.end(), sortByY);
}
unsigned size = p->data.size();
for (unsigned i =0; i<3; i++) {
Node<T>* new_node = new Node<T>;
new_node->depth = p->depth+1;
new_node->box = p->data.back().getBox();
for(unsigned j = (size*i)/3; j < (size*(i+1))/3; j++) {
new_node->data.push_back(p->data.back());
new_node->box.extend(p->data.back().getBox());
p->data.pop_back();
}
p->children[i] = new_node;
}
}
}
//look at groups and cascade into the one that is closest
Node<T>* closest_node = p->children[0];
double min_added_area = get_added_area(shape.getBox(), p->children[0]->box);
for(unsigned i =1; i<3; i++) {
double added_area = get_added_area(shape.getBox(), p->children[i]->box);
if(added_area < min_added_area) {
min_added_area = added_area;
closest_node = p->children[i];
}
}
insert(shape, closest_node);
}
void build_tree(std::vector<T> elements, Node<T>* n, unsigned depth) {
BoundingBox temp_box = elements[0].getBox();
//uses this list of elements to create and expand an apropriate box that contains them all
for(unsigned i = 1; i<elements.size(); ++i) {
temp_box.extend(elements[i].getBox());
}
n->box = temp_box;
n->depth = depth;
//checks to see if either of the 2 terminal conditions have been met
if(elements.size()<=split_threshold || (depth == depth_limit && depth_limit != 0) || elements.size()==1) {
n->data = elements;
size_ += elements.size();
return;
}
//checks to see if we should split along the horizontal or vertical and then sort the data accordingly
if(temp_box.dx() > temp_box.dy()) {
std::sort(elements.begin(), elements.end(), sortByX);
} else {
std::sort(elements.begin(), elements.end(), sortByY);
}
//splits the data into 3 equal or close to equal groups
for(unsigned i = 0; i<3; i++) {
Node<T>* temp = new Node<T>;
n->children[i] = temp;
std::vector<T> subVect;
unsigned size = elements.size();
for(unsigned j = (size*i)/3; j<(size*(i+1))/3; j++) {
subVect.push_back(elements[j]);
}
build_tree(subVect, temp, depth+1);
}
}
// (private) helper functions
void statistics(bool print_tree,
Node<T>* n,
const std::string &indent,
int &node_count,
int &max_depth,
double &inner_node_area,
double &leaf_node_area) const {
node_count++;
max_depth = std::max((int)n->depth,max_depth);
// scale the area by the area of the scene
double area = n->box.getArea() / double(1000*1000);
if (n->data.size() != 0) {
leaf_node_area += n->data.size() * area;
if (print_tree) {
std::cout << indent + "leaf area=" << std::setprecision(3) << area << " " << n->box << " elements:";
for (unsigned int i = 0; i < n->data.size(); i++) {
std::cout << " " << n->data[i].getBox();
}
std::cout << std::endl;
}
} else {
inner_node_area += area;
if (print_tree) {
std::cout << indent + "inner area=" << std::setprecision(3) << area << " " << n->box << std::endl;
}
statistics(print_tree,n->children[0],indent+" ",node_count,max_depth,inner_node_area,leaf_node_area);
statistics(print_tree,n->children[1],indent+" ",node_count,max_depth,inner_node_area,leaf_node_area);
statistics(print_tree,n->children[2],indent+" ",node_count,max_depth,inner_node_area,leaf_node_area);
}
}
void render_recolor(std::ostream &ostr, Node<T> *n, const Color &color) {
// draw the bounding box of this node as a transparent colored rectangle
n->box.render(ostr,color);
if (n->children[0] != NULL) {
// prepare variations of this node color for the 3 children
Color red(255,0,0);
Color green(0,255,0);
Color blue(0,0,255);
// blend the colors
if (color.r != 128 && color.g != 128 && color.b != 128) {
float m = 0.33;
red.mix(color,m);
green.mix(color,m);
blue.mix(color,m);
}
// recurse to the children
render_recolor(ostr,n->children[0],red);
render_recolor(ostr,n->children[1],green);
render_recolor(ostr,n->children[2],blue);
} else {
// if this is a leaf node, modify the color of all elements to
// match the transparent box color.
for (unsigned int i = 0; i < n->data.size(); i++) {
n->data[i].setColor(color);
}
}
}
};
template <class T>
void BVH<T>::statistics(bool print_tree) const {
// node count & maximum depth can be used to partially evaluate if
// the tree is mostly well-balanced.
int node_count = 0;
int max_depth = 0;
//
// Bittner, Hapala, & Havran, "Incremental BVH construction for ray
// tracing". Computers & Graphics 2014.
//
// summarize the "surface area heuristic" for predicting the
// efficiency of a bounding volume hierarchy.
//
// We calculate the sum of the (surface) area of all inner
// (non-leaf) nodes and divide by the area of the entire scene. It
// is generally better for the inner nodes to have small surface
// area -- which indicates the hierarchy is small and efficient, and
// we can quickly navigate to the relevant leaf nodes.
//
double inner_node_area = 0;
// We also calculate the sum of the leaf node surface area (again
// divided by the scene area). The leaf node area is multiplied
// (penalized) by the number of elements at that leaf node. We hope
// this number is also small.
//
double leaf_node_area = 0;
// sweep over the tree and print the results
statistics(print_tree,root_,"",node_count, max_depth, inner_node_area, leaf_node_area);
std::cout << "node count: " << std::setw(7) << node_count << std::endl;
std::cout << "max depth: " << std::setw(7) << max_depth << std::endl;
std::cout << "inner node area: " << std::fixed << std::setw(7) << std::setprecision(3) << inner_node_area << std::endl;
std::cout << "leaf node area: " << std::fixed << std::setw(7) << std::setprecision(3) << leaf_node_area << std::endl;
}
#endif
FOCS or ‘Foundations of Computer Science’ was essentially a discrete math class. This is usually a typical CS Students least favorite class as there is little to no coding and almost all of the work is theoretical. However, having taken the AMC and AIME in high school, discrete math felt right at home for me. Our homework for this class was weekly latex problem sets. While I did not enjoy using Latex to write the homework I enjoyed doing the problems themselves. I wont include the problems as they don’t include the question they are answering on them, but relevant topics we covered include: Proof by Induction, Proof by contradiction, Set Theory, Graph Theory, Game Theory, Computation.
Grade: A
Comp Org or Computer Organization was my first experience with low level programming. We started with C worked down to x86 and MIPS and then down to just logic gates. Homework for this class were not nearly as demanding as Data Structures, however the final project, which was to make a MIPS microprocessor in C with only logic gates was quite a lot of work, even in groups of 4. Ill include the full code below; I worked on the control bits as well as the final debugging. While I learned a lot about the internal logic of computers from this final project, learning to work and communicate and code with other people has been the most useful take away. Topics covered include: Binary, Big-endian, Little-endian, project pipelines, MIPS, x86, use of the UNIX command line.
Grade: A
/*
Class Project: The logical conclusion (v1.1)
CSCI-2500 Spring 2021
Prof. Slota
*/
/******************************************************************************/
/* Usual suspects to include */
/******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// define BIT type as a char (i.e., one byte)
typedef char BIT;
#define TRUE 1
#define FALSE 0
#define UNDEF -1
// useful constants
BIT ONE[32] = {TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE,
FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE,
FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE,
FALSE};
BIT ZERO[32] = {FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE,
FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE,
FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE,
FALSE};
BIT REG_THIRTY_ONE[5] = {TRUE, TRUE, TRUE, TRUE, TRUE};
BIT THIRTY_TWO[32] = {FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE,
FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE,
FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE,
FALSE};
/******************************************************************************/
/* Function prototypes */
/******************************************************************************/
BIT not_gate(BIT A);
BIT or_gate(BIT A, BIT B);
BIT or_gate3(BIT A, BIT B, BIT C);
BIT and_gate(BIT A, BIT B);
BIT and_gate3(BIT A, BIT B, BIT C);
BIT xor_gate(BIT A, BIT B);
BIT nor_gate(BIT A, BIT B);
BIT nand_gate(BIT A, BIT B);
void decoder2(BIT I0, BIT I1, BIT* O0, BIT* O1, BIT* O2, BIT* O3);
BIT multiplexor2(BIT S, BIT I0, BIT I1);
void multiplexor2_32(BIT S, BIT* I0, BIT* I1, BIT* Output);
BIT multiplexor4(BIT S0, BIT S1, BIT I0, BIT I1, BIT I2, BIT I3);
void copy_bits(BIT* A, BIT* B);
void print_binary(BIT* A);
void convert_to_binary(int a, BIT* A, int length);
void convert_to_binary_char(int a, char* A, int length);
int binary_to_integer(BIT* A);
int get_instructions(BIT Instructions[][32]);
void Instruction_Memory(BIT* ReadAddress, BIT* Instruction);
void Control(BIT* OpCode, BIT* funct,
BIT* RegDst, BIT* Jump, BIT* Branch, BIT* MemRead, BIT* MemToReg,
BIT* ALUOp, BIT* MemWrite, BIT* ALUSrc, BIT* RegWrite, BIT* JAL, BIT* JR);
void Read_Register(BIT* ReadRegister1, BIT* ReadRegister2,
BIT* ReadData1, BIT* ReadData2);
void Write_Register(BIT RegWrite, BIT* WriteRegister, BIT* WriteData);
void ALU_Control(BIT* ALUOp, BIT* funct, BIT* ALUControl);
void ALU(BIT* ALUControl, BIT* Input1, BIT* Input2, BIT* Zero, BIT* Result);
void Data_Memory(BIT MemWrite, BIT MemRead,
BIT* Address, BIT* WriteData, BIT* ReadData);
void Extend_Sign16(BIT* Input, BIT* Output);
void updateState();
/******************************************************************************/
/* Functions provided for your convenience */
/******************************************************************************/
BIT not_gate(BIT A)
{
if (A)
return FALSE;
else
return TRUE;
}
BIT or_gate(BIT A, BIT B)
{
if (A || B)
return TRUE;
else
return FALSE;
}
BIT or_gate3(BIT A, BIT B, BIT C)
{
return or_gate(A, or_gate(B, C));
}
BIT and_gate(BIT A, BIT B)
{
if (A && B)
return TRUE;
else
return FALSE;
}
BIT and_gate3(BIT A, BIT B, BIT C)
{
return and_gate(A, and_gate(B, C));
}
BIT xor_gate(BIT A, BIT B)
{
if (A ^ B)
return TRUE;
else
return FALSE;
}
BIT nor_gate(BIT A, BIT B)
{
return not_gate(or_gate(A, B));
}
BIT nor_gate3(BIT A, BIT B, BIT C)
{
return not_gate(or_gate(or_gate(A,B), C));
}
BIT nand_gate(BIT A, BIT B)
{
return not_gate(and_gate(A, B));
}
void decoder2(BIT I0, BIT I1, BIT* O0, BIT* O1, BIT* O2, BIT* O3)
{
// Note: The input -> output mapping is slightly modified from before
*O0 = and_gate(not_gate(I1), not_gate(I0));
*O1 = and_gate(not_gate(I1), I0);
*O2 = and_gate(I1, not_gate(I0));
*O3 = and_gate(I1, I0);
return;
}
void decoder3(BIT* I, BIT EN, BIT* O)
{
// TODO: implement 3-to-8 decoder using gates
// See lecture slides, book, and/or online resources for logic designs
if(EN == 0) {
for(int i = 0; i<8;i++) {
O[i] = 0;
}
return;
}
O[0] = and_gate3(not_gate(I[2]), not_gate(I[1]), not_gate(I[0]));
O[1] = and_gate3(not_gate(I[2]), not_gate(I[1]), I[0]);
O[2] = and_gate3(not_gate(I[2]), I[1], not_gate(I[0]));
O[3] = and_gate3(not_gate(I[2]), I[1], I[0]);
O[4] = and_gate3(I[2], not_gate(I[1]), not_gate(I[0]));
O[5] = and_gate3(I[2], not_gate(I[1]), I[0]);
O[6] = and_gate3(I[2], I[1], not_gate(I[0]));
O[7] = and_gate3(I[2], I[1], I[0]);
return;
}
BIT multiplexor2(BIT S, BIT I0, BIT I1)
{
BIT x0 = and_gate(not_gate(S), I0);
BIT x1 = and_gate(S, I1);
return or_gate(x0, x1);
}
void decoder5(BIT* I, BIT* O)
{
// TODO: implement 5-to-32 decoder using 2-to-4 and 3-to-8 decoders
// https://fci.stafpu.bu.edu.eg/Computer%20Science/4887/crs-12801/Files/hw4-solution.pdf
BIT Enablers[4] = {0};
BIT Selectors[2] = {0};
BIT SecondaryInput[3] = {0};
BIT Output[8] = {0};
Selectors[0] = I[3]; Selectors[1] = I[4];
SecondaryInput[0] = I[0]; SecondaryInput[1] = I[1]; SecondaryInput[2] = I[2];
decoder2(Selectors[0], Selectors[1], &Enablers[0], &Enablers[1], &Enablers[2], &Enablers[3]);
for(int i = 0; i<4; i++) {
decoder3(SecondaryInput, Enablers[i], Output);
O[0+8*i] = Output[0];
O[1+8*i] = Output[1];
O[2+8*i] = Output[2];
O[3+8*i] = Output[3];
O[4+8*i] = Output[4];
O[5+8*i] = Output[5];
O[6+8*i] = Output[6];
O[7+8*i] = Output[7];
}
return;
}
void multiplexor2_32(BIT S, BIT* I0, BIT* I1, BIT* Output)
{
for (int i = 0; i < 32; ++i) {
BIT x0 = and_gate(not_gate(S), I0[i]);
BIT x1 = and_gate(S, I1[i]);
Output[i] = or_gate(x0, x1);
}
}
BIT multiplexor4(BIT S0, BIT S1, BIT I0, BIT I1, BIT I2, BIT I3)
{
BIT x0, x1, x2, x3 = FALSE;
decoder2(S0, S1, &x0, &x1, &x2, &x3);
BIT y0 = and_gate(x0, I0);
BIT y1 = and_gate(x1, I1);
BIT y2 = and_gate(x2, I2);
BIT y3 = and_gate(x3, I3);
BIT z0 = or_gate(y0, y1);
BIT z1 = or_gate(y2, y3);
return or_gate(z0, z1);
}
BIT multiplexor8(BIT S0, BIT S1, BIT S2, BIT* I)
{
BIT mux1, mux2 = FALSE;
mux1 = multiplexor4(S0, S1, I[0], I[1], I[2], I[3]);
mux2 = multiplexor4(S0, S1, I[4], I[5], I[6], I[7]);
return multiplexor2(S2, mux1, mux2);
}
BIT multiplexor32(BIT S0, BIT S1, BIT S2, BIT S3, BIT S4, BIT* I)
{
BIT mux1, mux2, mux3, mux4 = FALSE;
BIT I0[8]; BIT I1[8]; BIT I2[8]; BIT I3[8];
for(int i = 0; i<8; i++) {
I0[i] = I[i];
I1[i] = I[i+8];
I2[i] = I[i+16];
I3[i] = I[i+24];
}
mux1 = multiplexor8(S0, S1, S2, I0);
mux2 = multiplexor8(S0, S1, S2, I1);
mux3 = multiplexor8(S0, S1, S2, I2);
mux4 = multiplexor8(S0, S1, S2, I3);
return multiplexor4(S3, S4, mux1, mux2, mux3, mux4);
}
/******************************************************************************/
/* Helper functions */
/******************************************************************************/
void copy_bits(BIT* A, BIT* B)
{
for (int i = 0; i < 32; ++i)
B[i] = A[i];
}
void print_binary(BIT* A)
{
for (int i = 31; i >= 0; --i)
printf("%d", A[i]);
}
void convert_to_binary(int a, BIT* A, int length)
{
if (a >= 0) {
for (int i = 0; i < length; ++i) {
A[i] = (a % 2 == 1 ? TRUE : FALSE);
a /= 2;
}
} else {
a += 1;
for (int i = 0; i < length; ++i) {
A[i] = (a % 2 == 0 ? TRUE : FALSE);
a /= 2;
}
}
}
void convert_to_binary_char(int a, char* A, int length)
{
if (a >= 0) {
for (int i = 0; i < length; ++i) {
A[i] = (a % 2 == 1 ? '1' : '0');
a /= 2;
}
} else {
a += 1;
for (int i = 0; i < length; ++i) {
A[i] = (a % 2 == 0 ? '1' : '0');
a /= 2;
}
}
}
int binary_to_integer(BIT* A)
{
unsigned a = 0;
unsigned mult = 1;
for (int i = 0; i < 32; ++i) {
a += A[i]*mult;
mult *= 2;
}
return (int)a;
}
char* check_reg(char* reg)
{
if (strcmp(reg, "zero") == 0)
return "00000";
else if (strcmp(reg, "v0") == 0)
return "00010";
else if (strcmp(reg, "a0") == 0)
return "00100";
else if (strcmp(reg, "t0") == 0)
return "01000";
else if (strcmp(reg, "t1") == 0)
return "01001";
else if (strcmp(reg, "s0") == 0)
return "10000";
else if (strcmp(reg, "s1") == 0)
return "10001";
else if (strcmp(reg, "sp") == 0)
return "11101";
else if (strcmp(reg, "ra") == 0)
return "11111";
return reg;
}
/******************************************************************************/
/* Parsing functions */
/******************************************************************************/
// TODO: Implement any helper functions to assist with parsing
int get_instructions(BIT Instructions[][32])
{
char line[256] = {0};
int instruction_count = 0;
while (fgets(line, 256, stdin) != NULL) {
// TODO: perform conversion of instructions to bianry
// Input: coming from stdin via: ./a.out < input.txt
// Output: Convert instructions to binary in the instruction memory
// Return: Total number of instructions
// Note: you are free to use if-else and external libraries here
// Note: you don't need to implement circuits for saving to inst. mem.
// My approach:
// - Use sscanf on line to get strings for instruction and registers
// - Use instructions to determine op code, funct, and shamt fields
// - Convert immediate field and jump address field to binary
// - Use registers to get rt, rd, rs fields
// Note: I parse everything as strings, then convert to BIT array at end
char instr [5];
char reg1 [5];
char reg2 [5];
char reg3 [5];
char tempReg [32] = {0};
char imm[17] = {0};
sscanf(line, "%s %s %s %s", instr, reg1, reg2, reg3);
if (strcmp(instr, "lw") == 0 || strcmp(instr, "sw") == 0 || strcmp(instr, "beq") == 0 || strcmp(instr, "addi") == 0) { // I-TYPE FORMATTING | lw, sw, beq, addi
if (strcmp(instr, "lw") == 0)
strcat(tempReg, "100011");
else if (strcmp(instr, "sw") == 0)
strcat(tempReg, "101011");
else if (strcmp(instr, "beq") == 0)
strcat(tempReg, "000100");
else if (strcmp(instr, "addi") == 0)
strcat(tempReg, "001000");
if (strcmp(instr, "beq") == 0) { // FLIP FOR BEQ BECAUSE WHY NOT
strcat(tempReg, check_reg(reg1));
strcat(tempReg, check_reg(reg2));
} else {
strcat(tempReg, check_reg(reg2));
strcat(tempReg, check_reg(reg1));
}
convert_to_binary_char(atoi(reg3), imm, 16);
for (int i = 0; i < 8; i++) {
char temp = imm[i];
imm[i] = imm[15 - i];
imm[15 - i] = temp;
}
strcat(tempReg, imm);
} else if (strcmp(instr, "and") == 0 || strcmp(instr, "or") == 0 || strcmp(instr, "add") == 0 || strcmp(instr, "sub") == 0 || strcmp(instr, "slt") == 0 || strcmp(instr, "jr") == 0) { // R-TYPE FORMATTING | and, or, add, sub, slt, jr
strcat(tempReg, "000000");
if (strcmp(instr, "jr") == 0) { // FOR JR ITS DIFFERENT
strcat(tempReg, "11111000001111100000001000");
} else {
strcat(tempReg, check_reg(reg2));
strcat(tempReg, check_reg(reg3));
strcat(tempReg, check_reg(reg1));
}
if (strcmp(instr, "and") == 0)
strcat(tempReg, "00000100100");
else if (strcmp(instr, "or") == 0)
strcat(tempReg, "00000100101");
else if (strcmp(instr, "add") == 0)
strcat(tempReg, "00000100000");
else if (strcmp(instr, "sub") == 0)
strcat(tempReg, "00000100010");
else if (strcmp(instr, "slt") == 0)
strcat(tempReg, "00000101010");
} else if (strcmp(instr, "j") == 0 || strcmp(instr, "jal") == 0) { // J-TYPE FORMATTING | j, jal
if (strcmp(instr, "j") == 0)
strcat(tempReg, "000010");
else if (strcmp(instr, "jal") == 0)
strcat(tempReg, "000011");
convert_to_binary_char(atoi(reg1), imm, 26);
for (int i = 0; i < 13; i++) {
char temp = imm[i];
imm[i] = imm[25 - i];
imm[25 - i] = temp;
}
strcat(tempReg, imm);
}
//printf("%s %s %s %s: %s\n", instr, reg1, reg2, reg3, tempReg); // for test printing
// trying to modify instructions but i messed up lOL
for (int i = 0; i < 32; i++) {
if (tempReg[i] == '0')
Instructions[instruction_count][31 - i] = FALSE;
else if (tempReg[i] == '1')
Instructions[instruction_count][31 - i] = TRUE;
}
instruction_count++;
memset(tempReg, 0, 32);
}
//printf("%s\n", tempReg);
return instruction_count;
}
/******************************************************************************/
/* Program state - memory spaces, PC, and control */
/******************************************************************************/
BIT PC[32] = {FALSE};
BIT MEM_Instruction[32][32] = {FALSE};
BIT MEM_Data[32][32] = {FALSE};
BIT MEM_Register[32][32] = {FALSE};
BIT RegDst = FALSE;
BIT Jump = FALSE;
BIT Branch = FALSE;
BIT MemRead = FALSE;
BIT MemToReg = FALSE;
BIT ALUOp[2] = {FALSE};
BIT MemWrite = FALSE;
BIT ALUSrc = FALSE;
BIT RegWrite = FALSE;
BIT Zero = FALSE;
BIT ALUControl[4] = {FALSE};
//ADDED FOR JAL AND JR
BIT JAL = FALSE; //for JAL
BIT JR = FALSE; //for JR
void print_instruction()
{
unsigned pc = binary_to_integer(PC);
printf("PC: %d\n", pc);
printf("Instruction: ");
print_binary(MEM_Instruction[pc]);
printf("\n");
}
void print_state()
{
printf("Data: ");
for (int i = 0; i < 32; ++i) {
printf("%d ", binary_to_integer(MEM_Data[i]));
}
printf("\n");
printf("Register: ");
for (int i = 0; i < 32; ++i) {
printf("%d ", binary_to_integer(MEM_Register[i]));
}
printf("\n");
}
/******************************************************************************/
/* Functions that you will implement */
/******************************************************************************/
void Instruction_Memory(BIT* ReadAddress, BIT* Instruction)
{
// TODO: Implement instruction memory
// Input: 32-bit instruction address
// Output: 32-bit binary instruction
// Note: Useful to use a 5-to-32 decoder here
for(int i = 0; i<32; i++) {
BIT input[32];
for(int j = 0; j<32; j++) {
input[j] = MEM_Instruction[j][i];
}
Instruction[i] = multiplexor32(ReadAddress[0], ReadAddress[1], ReadAddress[2], ReadAddress[3], ReadAddress[4], input);
}
}
void Control(BIT* OpCode, BIT* funct,
BIT* RegDst, BIT* Jump, BIT* Branch, BIT* MemRead, BIT* MemToReg,
BIT* ALUOp, BIT* MemWrite, BIT* ALUSrc, BIT* RegWrite, BIT* JAL, BIT* JR)
{
// TODO: Set control bits for everything
// Input: opcode field from the instruction
// OUtput: all control lines get set
// Note: Can use SOP or similar approaches to determine bits
//OPCODE CONVERSION CHART:
//I lw 100011, ALUOp: 00
//I sw 101011, ALUOp: 00
//I beq 000100, ALUOp: 01
//I addi 001000, ALUOp: 00
//R and 000000, FUNC: 100100, ALUOp: 10
//R or 000000, FUNC: 100101, ALUOp: 10
//R add 000000, FUNC: 100000, ALUOp: 10
//R sub 000000, FUNC: 100010, ALUOp: 10
//R slt 000000, FUNC: 101010, ALUOp: 10
//J j 000010, ALUOp: 00
//J jal 000011, ALUOp: 00
//R jr 000000, FUNC: 001000, ALUOp: 10
BIT RType = not_gate(or_gate(or_gate3(OpCode[0], OpCode[1], OpCode[2]),
or_gate3(OpCode[3], OpCode[4], OpCode[5])));
*RegDst = RType; //on for all R types
*Jump = or_gate(and_gate(RType, not_gate(funct[5])), and_gate(not_gate(OpCode[5]), OpCode[1])); //on j, jal, jr
*Branch = OpCode[2]; //on for beq
*MemRead = and_gate(not_gate(OpCode[3]), OpCode[5]);//on for lw
*MemToReg = and_gate(not_gate(OpCode[3]), OpCode[5]); //on for lw
ALUOp[0] = OpCode[2]; //on for beq
ALUOp[1] = RType; //on for Rtype
*MemWrite = and_gate(OpCode[3], OpCode[5]); //true for sw
*ALUSrc = or_gate(OpCode[5], OpCode[3]); //true for Addi, lw, sw
*RegWrite = nor_gate3(OpCode[2], and_gate(RType, not_gate(funct[5])),
or_gate(and_gate(not_gate(OpCode[0]), OpCode[1]), and_gate(OpCode[5], OpCode[3]))); //off for jr, j, beq, and sw
*JAL = and_gate(not_gate(OpCode[5]), OpCode[0]);//on when jAL
*JR = and_gate(RType, not_gate(funct[5])); //on when JR
}
void Read_Register(BIT* ReadRegister1, BIT* ReadRegister2,
BIT* ReadData1, BIT* ReadData2)
{
// TODO: Implement register read functionality
// Input: two 5-bit register addresses
// Output: the values of the specified registers in ReadData1 and ReadData2
// Note: Implementation will be very similar to instruction memory circuit
/*
int reg1 = binary_to_integer(ReadRegister1);
int reg2 = binary_to_integer(ReadRegister2);
for(unsigned int i = 0; i < 32; i++)
{
ReadData1[i] = MEM_Register[reg1][i];
ReadData2[i] = MEM_Register[reg2][i];
}
*/
for(int i = 0; i<32; i++) {
BIT input[32];
for(int j = 0; j<32; j++) {
input[j] = MEM_Register[j][i];
}
ReadData1[i] = multiplexor32(ReadRegister1[0], ReadRegister1[1], ReadRegister1[2], ReadRegister1[3], ReadRegister1[4], input);
ReadData2[i] = multiplexor32(ReadRegister2[0], ReadRegister2[1], ReadRegister2[2], ReadRegister2[3], ReadRegister2[4], input);
}
}
void Write_Register(BIT RegWrite, BIT* WriteRegister, BIT* WriteData)
{
// TODO: Implement register write functionality
// Input: one 5-bit register address, data to write, and control bit
// Output: None, but will modify register file
// Note: Implementation will again be similar to those above
/*
if(RegWrite == FALSE)
return;
int reg = binary_to_integer(WriteRegister);
for(unsigned int i = 0; i < 32; i++)
MEM_Register[reg][i] = multiplexor2(RegWrite, MEM_Register[reg][i], WriteData[i]);
*/
BIT selectors[32];
decoder5(WriteRegister, selectors);
for(int i = 0; i<32; i++) {
for(int j = 0; j<32; j++) {
MEM_Register[j][i] = multiplexor2(and_gate(RegWrite, selectors[j]), MEM_Register[j][i], WriteData[i]);
}
}
}
void ALU_Control(BIT* ALUOp, BIT* funct, BIT* ALUControl)
{
// TODO: Implement ALU Control circuit
// Input: 2-bit ALUOp from main control circuit, 6-bit funct field from the
// binary instruction
// Output:4-bit ALUControl for input into the ALU
// Note: Can use SOP or similar approaches to determine bits
//MODIFIED CONTROL TABLE:
//| OPCODE | ALUOP | OPERATION | FUNCT | ALU FUNCT | ALUCONTROL |
//| LW | 00 | LW | | ADD | 0010 |
//| SW | 00 | SW | | ADD | 0010 |
//| ADDI | 00 | ADD | | ADD | 0010 |
//| BEQ | 01 | BEQ | | SUB | 0110 |
//| R | 10 | ADD |100000 | ADD | 0010 |
//| R | 10 | SUB |100010 | SUB | 0110 |
//| R | 10 | AND |100100 | AND | 0000 |
//| R | 10 | OR |100101 | OR | 0001 |
//| R | 10 | SLT |101010 | SLT | 0111 |
//| R | 10 | JR |001000 | ADD | 0010 | //COULD ADD ZERO
//| J | 00 | JAL | | ADD | 0010 | //COULD ADD ZERO
//| J | 00 | J | | ADD | 0010 | //CAN BE WHATEVER
BIT RType = and_gate(not_gate(ALUOp[0]), ALUOp[1]);
BIT beq = and_gate(ALUOp[0], not_gate(ALUOp[1]));
ALUControl[0] = and_gate(RType, or_gate(funct[0], and_gate(funct[3], funct[5])));
ALUControl[1] = nand_gate(RType, funct[2]);
ALUControl[2] = or_gate(beq, and_gate(RType, funct[1]));
ALUControl[3] = FALSE;
}
void adder1(BIT A, BIT B, BIT CarryIn, BIT* CarryOut, BIT* Sum)
{
BIT T0 = xor_gate(A, B);
*Sum = xor_gate(T0, CarryIn);
*CarryOut = or_gate(and_gate(A, B), and_gate(T0, CarryIn));
}
void ALU1(BIT A, BIT B, BIT Binvert, BIT CarryIn, BIT Less,
BIT Op0, BIT Op1, BIT* Result, BIT* CarryOut, BIT* Set)
{
BIT binverted = multiplexor2(Binvert, B, not_gate(B));
BIT T0 = and_gate(A, binverted);
BIT T1 = or_gate( A, binverted);
adder1(A, binverted, CarryIn, CarryOut, Set);
*Result = multiplexor4(Op0, Op1, T0, T1, *Set, Less);
}
void ALU(BIT* ALUControl, BIT* Input1, BIT* Input2, BIT* Zero, BIT* Result)
{
// TODO: Implement 32-bit ALU
// Input: 4-bit ALUControl, two 32-bit inputs
// Output: 32-bit result, and zero flag big
// Note: Can re-use prior implementations (but need new circuitry for zero)
BIT* A = Input1;
BIT* B = Input2;
BIT Binvert = ALUControl[2];
BIT CarryIn = Binvert;
BIT Op0 = ALUControl[0];
BIT Op1 = ALUControl[1];
BIT CarryOut = CarryIn;
BIT Set = FALSE;
for(int i = 0; i < 32; ++i) {
ALU1(A[i], B[i], Binvert, CarryOut, 0, Op0, Op1, &Result[i], &CarryOut, &Set);
}
ALU1(A[0], B[0], Binvert, CarryIn, Set, Op0, Op1, &Result[0], &CarryIn, &Set);
*Zero = TRUE;
for(unsigned int i = 0; i < 32; i++)
*Zero = and_gate(*Zero, not_gate(Result[i]));
}
void Data_Memory(BIT MemWrite, BIT MemRead,
BIT* Address, BIT* WriteData, BIT* ReadData)
{
// TODO: Implement data memory
// Input: 32-bit address, control flags for read/write, and data to write
// Output: data read if processing a lw instruction
// Note: Implementation similar as above
/*
int index = binary_to_integer(Address);
for(unsigned int i = 0; i < 32; i++)
{
ReadData[i] = multiplexor2(MemRead, ReadData[i], MEM_Data[index][i]);
MEM_Data[index][i] = multiplexor2(MemWrite, MEM_Data[index][i], WriteData[i]);
}
*/
BIT selectors[32];
BIT S[5];
for (int i = 0; i < 5; i++) {
S[i] = Address[i];
}
decoder5(S, selectors);
for(int i = 0; i<32; i++) {
BIT input[32];
for(int j = 0; j<32; j++) {
input[j] = MEM_Data[j][i];
MEM_Data[j][i] = multiplexor2(and_gate(MemWrite, selectors[j]), MEM_Data[j][i], WriteData[i]);
}
ReadData[i] = multiplexor2(MemRead, ReadData[i], multiplexor32(S[0], S[1], S[2], S[3], S[4], input));
}
}
void Extend_Sign16(BIT* Input, BIT* Output)
{
// TODO: Implement 16-bit to 32-bit sign extender
// Copy Input to Output, then extend 16th Input bit to 17-32 bits in Output
for(unsigned int i = 0; i < 16; i++)
Output[i] = Input[i];
for(unsigned int i = 16; i < 32; i++)
Output[i] = Input[15];
}
void updateState()
{
// TODO: Implement the full datapath here
// Essentially, you'll be figuring out the order in which to process each of
// the sub-circuits comprising the entire processor circuit. It makes it
// easier to consider the pipelined version of the process, and handle things
// in order of the pipeline. The stages and operations are:
// Fetch - load instruction from instruction memory
// Decode - set control bits and read from the register file
// Execute - process ALU
// Memory - read/write data memory
// Write Back - write to the register file
// Update PC - determine the final PC value for the next instruction
//FETCH
BIT opCode[6] = {FALSE};
int pc = binary_to_integer(PC);
BIT instruction[32] = {FALSE};
//Instruction_Memory(MEM_Instruction[pc], instruction);
copy_bits(MEM_Instruction[pc], instruction);
//DECODE
for(int i = 26; i < 32; i++){
opCode[i - 26] = instruction[i];
}
BIT rs[5] = {FALSE};
BIT rt[5] = {FALSE};
BIT rd[5] = {FALSE};
BIT funct[6] = {FALSE};
BIT immediate[16] = {FALSE};
BIT address[26] = {FALSE};
for(int i = 0; i < 5; i++){
rs[i] = instruction[i + 21];
rt[i] = instruction[i + 16];
rd[i] = instruction[i + 11];
funct[i] = instruction[i];
}
funct[5] = instruction[5];
for(int i = 0; i < 16; i++){
immediate[i] = instruction[i];
}
for(int i = 0; i < 26; i++){
address[i] = instruction[i];
}
Control(opCode, funct, &RegDst, &Jump, &Branch, &MemRead, &MemToReg, ALUOp, &MemWrite, &ALUSrc, &RegWrite, &JAL, &JR);
pc++;
BIT readData1[32] = {FALSE};
BIT readData2[32] = {FALSE};
Read_Register(rs, rt, readData1, readData2);
BIT writeReg[5] = {FALSE};
for(int i = 0; i < 5; i++){
writeReg[i] = multiplexor2(RegDst, rt[i], rd[i]);
}
for(int i = 0; i < 5; i++){
writeReg[i] = multiplexor2(JAL, writeReg[i], REG_THIRTY_ONE[i]);
}
BIT extendedImmediate[32] = {FALSE};
Extend_Sign16(immediate, extendedImmediate);
//EXECUTE
ALU_Control(ALUOp, funct, ALUControl);
BIT ALUSecond[32] = {FALSE};
multiplexor2_32(ALUSrc, readData2, extendedImmediate, ALUSecond);
BIT ALUResult[32] = {FALSE};
ALU(ALUControl, readData1, ALUSecond, &Zero, ALUResult);
//MEMORY
BIT readDataMemory[32] = {FALSE};
Data_Memory(MemWrite, MemRead, ALUResult, readData2, readDataMemory);
//WRITE BACK
BIT writeBackData[32] = {FALSE};
multiplexor2_32(MemToReg, ALUResult, readDataMemory, writeBackData);
BIT writeBackData2[32] = {FALSE};
convert_to_binary(pc, PC, 32);
multiplexor2_32(JAL, writeBackData, PC, writeBackData2);
Write_Register(RegWrite, writeReg, writeBackData2);
//UPDATE PC
BIT jumpALUResult[32] = {FALSE};
BIT temp = FALSE;
BIT add[4] = {FALSE,TRUE,FALSE,FALSE};
ALU(add, PC, extendedImmediate, &temp, jumpALUResult);
BIT jumpMuxResult[32] = {FALSE};
multiplexor2_32(and_gate(Branch, Zero), PC, jumpALUResult, jumpMuxResult);
BIT jrResult[32] = {FALSE};
//multiplexor2_32(JR, address, readData1, jrResult); address is 26 bits
for(int i = 0; i<26; i++) {
jrResult[i] = multiplexor2(JR, address[i], readData1[i]);
}
for(int i = 26; i<32; i++) {
jrResult[i] = multiplexor2(JR, FALSE, readData1[i]);
}
multiplexor2_32(Jump, jumpMuxResult, jrResult, PC);
}
/******************************************************************************/
/* Main */
/******************************************************************************/
int main()
{
setbuf(stdout, NULL);
// parse instructions into binary format
int counter = get_instructions(MEM_Instruction);
// load program and run
copy_bits(ZERO, PC);
copy_bits(THIRTY_TWO, MEM_Register[29]);
while (binary_to_integer(PC) < counter) {
print_instruction();
updateState();
print_state();
//BIT add[4] = {FALSE, TRUE, FALSE, FALSE};
//BIT temp[32]; copy_bits(PC, temp);
//ALU(add, temp, ONE, &Zero, PC);
}
return 0;
}
/*
TOLIST Remaining functions:
None
*/
Intro to Algorithms was the second weed out class for CS majors at my school. It had the work load of Data Structures with conceptual difficulty of FOCS. Homework were long problem sets of leetcode medium-hard level difficulty problems, luckily we didn’t have to actually code our solutions, and instead provided pseudocode. When we did code we used Python which everyone was familiar with at this point. Topics covered include: Sorting, Greedy algorithms, Dynamic Programming, Linear Programming, Completeness. I wont include hw as it was mostly pseudo code.
Grade: B+
This class we a relief after Algo. The only unfortunate thing is we had to use java for the entire class which is a programming language I am all to familiar with now. This class was about software design more than anything else, so homework was lighter. Topics covered include: Loop invariants, good programming practices, Dafny, Java, Java, More Java, inheritance, swing. I won’t include hw because none of it was interesting or challenging.
Grade: A
Skills:
Recursion is a tool I tend to use often when programming, while it has reputation of being slow and inefficient, I appreciate the elegance and cleanness of it. Recursion also has the reputation of being hard to understand or conceptualize, however I tend to find it easier to understand a recursive implementation than an iterative one most of the time. Without a doubt the code that shows my skills with recursion the most would be hw 6 from data structures or recursion_HW as it is labeled in the folder provided in the Data Structures tab above. in the folder there are six versions of the code as I implemented a solution to the problem six times before I got it to run fast enough to complete all the tasks in a reasonable amount of time (the final version in named Recursion_HW)
Summary of solution and problem solving process:
problem handout
My initial approaches failed because they had recursion inside recursion. (recursion to identify all possible paths within the recursion to find the set of paths that fit together). I solved the problem when I (finally) realized to break up the process of finding the paths and the process of finding how they should fit together. So I did one recursive process that created a massive 3d list that contained each set of all possible paths for each number. Then I started smart eliminating possible paths by prioritizing the smallest paths first and removing paths that overlapped. Instead of just recursively trying every combination of paths. By eliminating paths it would reduce the size of other sets of paths, which I could then use to eliminate more paths. Until only one path remained in each set: the final solution.
Dynamic programming is similar to recursion in a lot of ways as they both involve breaking up a problem into a subproblem, so naturally I tend to love using it for the same reason: elegance. Below Ill include one of my favorite leetcode problems that I completed using a 24 line Dynamic programming solution.
Prompt (from leetcode)
I initially struggled a lot with this problem despite realizing right away that I wanted to implement a dynamic programming solution to this problem. I couldn’t figure out how to fit the factory limits into the equation. The task seemed much more approachable if I simply had to match robots to factories without worrying about the number assigned to each factory. Then I realized I could think of each factory as a clump of factories equal to its factory limit i.e a factory that can repair 3 robots becomes 3 factories that repair one robot. Then I plotted each robot against each factory both sorted by distance, and what I was left with was a dynamic programming problem I was all to familiar with from algorithms.
class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
vector<int> factory_dists = vector<int>();
for(int i = 0; i<factory.size(); i++) {
for(int j = 0; j<factory[i][1]; j++){ factory_dists.push_back(factory[i][0]);}
}
robot.push_back(-1e9); factory_dists.push_back(-1e9);
sort(factory_dists.begin(), factory_dists.end()); sort(robot.begin(), robot.end());
long t[factory_dists.size()][robot.size()];
long least = 1e15;
for(int i = 0; i < robot.size(); i++) {
for(int j = i; j < factory_dists.size(); j++) {
if(i == 0) {t[j][i] = abs(factory_dists[factory_dists.size()-j-1] - robot[robot.size()-i-1]);}
else {
least = min(t[j-1][i-1], least);
t[j][i] = least + abs(factory_dists[factory_dists.size()-j-1] - robot[robot.size()-i-1]);
}
}
least = 1e15;
}
return t[factory_dists.size()-1][robot.size()-1];
}
};
This is a skill I did not learn from one of my classes but instead from working on Osou. All in all Osou for the year and a half I’ve been working on it has equated to at least 5 classes of knowledge. No project from school has even come close to the scale of Osou and for that reason alone Osou taught me something you cannot learn in school: Managing Maintainability. Coming into Osou the longest project I had worked on had been Mirror Quest which spanned a little over one summer. Moreover I had luxury of only working on small-medium scale projects and never had to really consider the long term when designing a system. With Osou this carelessness I had initially, came back to bite me time and time again. I designed and redesigned systems all for one new feature. I would comment out hundreds of lines of code to rebuild something from the ground up. There are well over 10,000 lines of code in Osou now and even more logic in massive blueprint webs that amassed over time (picture below). I learned first hand the danger of Spaghetti code, and have had to learn to anticipate future problems in addition to fixing present ones.
This is another one of the many skills I have learned from Osou. While we have technically covered UI in Principles of Software, as is usually the case: I have learned 1000 times more by making it in Osou. I tend to be a perfectionist when working on my own projects, and when it became time to implement the level select screen in Osou I knew I wanted to do something special. After hours of experimenting with different motions and animations to add extra flair that showed quality I finally struck the balance between subtlety and noticeability that clicked instantly. The ‘wave effect’ as I like to call it, is shown below.
Throughout development of Osou I have frequently pushing commits, something I unfortunately did not do with Mirror Quest. Use of Github and Git has become second nature for me now, but I remember struggling with it a great deal when we used it for FRC in high school. There is definitely a learning curve, and as is usually the case for me I really started to learn it once I used it for my own projects. You can see all commits to Osou over the year here.
Miscellaneous useful skills I have learned working on Osou:
-Gimp
-Photoshop
-Audacity
-Unreal Engine
-Web design
-Shotcut
-Promotion Design
Closing Remarks:
As you might have picked up from this resume, I tend to be a little bit of a perfectionist when I am working on something I am passionate about, for better or for worst. I try to not just get something to work but to get it to work in the nicest cleanest way, and this can slow me down sometimes. I personally prioritize the quality of ones code over the speed at which they code. I tend to spend much more time thinking and planning in my head than I do actually coding. This can be a weakness as well as a strength however, and I often have to force myself, especially in interviews, to not get lost in the trying to find the most elegant possible solution. However given ample time and a project I am passionate about I am very confidant in my ability to create efficient and high quality code.