First Year Projects in EE/CS

Instead of using duct tapes and zip ties, you need to compile the code over and over again. Wait, duct tapes and zip ties are still required anyway.

Posted by Boyang Li on 05-17-2020

During my freshman year at UC Berkeley, I was exposed to the world of both electrical engineering and computer science. Computer science classes are self-explanatory as I am a CS major, and the electrical engineering classes, despite being a requirement by the Berkeley EECS Department, definitely provided me with a lot of insights into the world of EE as well as how EE and CS are involved in one another.

Seeing those projects from an industry point of view, they are rather primitive and glitchy. However, considering the fact that those are projects from lower division classes, they serve their purpose of exposing someone new to the field to the world of engineering and moreover, teaching someone how to be an engineer by enforcing them to be both rigorous and creative. They are rigorous as they require the students to actually think about the problems as well as put in effort in order to come up with a solution, and creative because none of the students taking the same class would have the exact solution (given that they did not cheat); in fact, there are always various of ways to solve every problem in every EECS class. However, no matter whether you implemented your solution elegantly or using brute force, as long as it works then you are in good shape. At the end of the day, the autograder would give the same score to a beautifully-designed project and a ugly yet functional program.

Below is a recap of the projects I did in my first year attending Cal. I will explain them from Production(How it works), Concepts covered, and Significance(literal meanings as well as how I struggled on the project).

Disclaimer: In compliance with UC Berkeley’s code of conduct, in particular in terms of academic dishonesty and plagiarism, none of the contents shown below is publically available, exactly the solution, or significantly hinting at the answer.

CS 61A: Ther Structure and Interpretation of Computer Programs

An introductory-level computer science class focusing on ideas such as higher-order functions, layers of abstractions, object-oriented programming, compilers/interpreters, and databases. The first 60% of the class is taught in Python, and later in Scheme(Lisp) and MySQL.

As someone who has some prior coding experience, I still struggled a lot in this class. It does not teach you how to use Python language, but rather the fundamentals of ideas in computer science.

Hog

Hog
We all love some free bacons, don’t we?

A dice-tossing game in which two players alternate turns trying to be the first to end a turn with at least 100 total points with special rules applied. On each turn, the current player can choose up to 10 dice to roll and the sum of the dice outcomes after applying rules is added to the current player’s total points.

Concepts covered: Control statements, Higher-order functions, Artificial Intelligence (I mean, AIs could basically just be control statements…), Machine Learning[1]

Production: A lot of control statements (namely if and else) for applying each rules and higher-order functions to store and update the game progress. As the first project of an intro-level CS class, it was not too conceptually hard while the amount of IFs and ELSEs really familiarized people with how to write control statements. However, the Higher-Order Functions to store and advance the stages of the game could be a bit confusing compared to Object-Oriented Programming.

CATS - CS61A Autocorrected Typing Software

CATS
How fast and accurately can you type?

A program that chooses random quotes and monitors the users’ typing skills as they type in the excerpt. When there is an error, it either attempts to autocorrect based on the word bank and the Levenshtein distance or labels the word as wrong.
A finished product of CATS can be seen here.

Concepts covered: Arrays (data structure), Layers of Abstraction, Recursion, Algorithm [2]

Production: There are a lot of array manipulations and a lot of use of recursions. There are also applications of the Levenshtein distance (very briefly) and particularly in my own solution, the use of a double-layered array (or matrices/charts) to find the minimum edit distance. I understand that I have said the word Levenshtein distance quite a lot; not only because it sounds cool and gives non-CS people the feeling that I am doing something of great significance, but also because the distance-finding function took up 50% of the time for which I worked on the project. Initially I went with the tree-recursion method given by the problem, but after seeing this video on Youtube, I decided to go with the method provided in the video, which is equivalent to the tree-recursion/dynamic programming method yet a bit more straightforward. Also I just noticed that the equivalency on LeetCode for the edit distance function is a Hard question, which makes it interesting.

Ants - (Pl)Ants Vs. SomeBees

ANTS
“Hey mom, can we have PvZ?” “We have PvZ at home” PvZ at home:

A tower defense game similar to PopCap’s Plants vs. Zombies(I mean, just read that name) in which the player needs to place ants with different abilities on grids in order to defend the invading bees from the ant queen.

Concepts covered: Object-Oriented Programming

Production: There were only two objects: ants and bees but a lot of object-oriented programming around them which made the project daunting. Since each different type of ant shared some common traits while having different abilities, there were a lot of uses of inheritance. Functional programming was also used to update the status of both the game and each individual ant/bee. Since Python is a function-oriented script language, using it for object-oriented programming was a bit challenging and very different from Java. However, this was probably one of my favourite projects as you got to actually build something playable. Since there were a lot of sub-classes and inheritances, dealing with the complicated relationship could be a bit challenging and confusing. As DeNero said here, everyone should “be very careful with multiple inheritance”.

Scheme - Lisp Interpreter written in Python

SCHEME
I entered some complicated macro definitions and functions to show that this interpreter works.

An interpreter that can parse, tokenize, and evaluate the Scheme language. With less than 2k lines of code, you can have yourself a whole interpreter – I mean, just look at how powerful and elegant this is. The reason to choose Scheme, despite how annoying it can be when writing functions, is because of the unique and simple structure of the language. After all, you know that each bracket means potentially a new token and the first parameter of the token always defines what actions you need to take.

Concepts covered: Interpreters, Compilers, Lexical Analysis, Syntactic Analysis, Tokenization and Evaluation, Tree-Recursions.

Production: There were a lot of tokenizations of the input and choice of the item to evaluate. Although the lexical analysis and syntactic analysis was partially given by the skeleton code, there was still a lot to learn about how interpreters work. The project also included a tree-recursive function that was used for evaluating recursive functions (recursion, get it?). This was the most challenging project; although there are a lot of hints and handholds provided, I still struggled for hours sitting in the library. Scheme also used different quotes, which required extra effort in parsing the phrase.

CS 61B

A data structure class with the first 1/4 of the semester focusing on the java language and object-oriented programming. The data structures and algorithms covered includes linked lists, trees, hashmaps, sorting algorithms, search structures, graphs, and dynamic programming.

Signpost

Signpost
Instructions on the course website on how to solve a Signpost puzzle.
A board game which is one of Simon Tatham’s collection of GUI games. In the game, the player is given W * H rectangular grid of cells with an arrow on them indicating the direction of their successor. The player needs to connect the grids through dragging such that each adjacent cell represents an adjacent integer.
As mentioned in the introduction, “this initial programming assignment is intended to give you a chance to get familiar with Java and the various tools used in the course.”

Concepts covered: Object-Oriented Programming, (implicit) Software Engineering, How to work on medium-sized projects and reading the comments/requirements.

Production: There were different classes such that we can learn how an actual java program works with classes tied with one another. Different functions, both instance ones and class ones, were implemented in order to meet the specification given by the course website. Although it was defined as one of the “smaller-sized” projects and was supposed to be easier, a lot of time was put into this project due to the petty edge cases and various rules, as well as the complicated linked relation between two tiles. We were also required to write unit tests and integration tests as the autograder was not available 24/7. In hindsight, roughly half of my efforts were put into adjusting the different project style and course load.

Enigma

Enigma
An Enigma with rotors and plugboards (made of actual materials) and an (digital) Enigma with rotors and plugboards (written in the configuration file)

A machine used by Germany during World War II to encrypt its military communications, this digital version of the substitution cipher machine was written in Java and more functional as it supported mapping a letter back to itself (which was not available in the original Enigma). While this project is capable of encrypting messages, it can not replicate the punctuation between words, which makes reading the de-encrypted message more challenging.

Concepts covered: Object-Oriented Programming, (implicit) Software Engineering, File I/O, Regex, Inheritance, Choice of the Proper Data Structures.
Production: There were different classes inheriting from each other of the components of the machine as opposed to the original rotors, plugboards, and wires. I had some struggles understanding the basic structure of the Enigma machine as this was my first time hearing anything about it, yet Numberphile’s video helped me a lot to go through the initial confusion. Besides, the project was hard to debug because of the intertwined relationships among classes, and reading the correct input from the configuration file using Regex as well as from the input message took me a lot of time.

Lines Of Action

LOA
(Ordering from left to right, top to bottom) P1: the initial configuration; P2: AI playing against AI, resulting a draw; P3: the notification interface after I played against the AI; P4: the red(black) player won as all pieces are connected

A board game in which the player moves the pieces in order to capture an opposing piece. The goal of the game is to get all of one’s pieces into one group of pieces that are connected, namely being adjacent horizontally, vertically, or diagonally.

Concepts covered: Game Tree, Search Algorithm, GUIs

Production: While implementing the game logic was quite simple with the skeleton code, writing the game AI was the most challenging part. Although I would call the if/else statements I wrote for Hog an “AI”, this is the first actual AI I have ever made. I tested a lot on the heuristic for the game tree such as how to choose the weight of each choice. Besides, the implementation of the GUI was quite challenging as well.

Gitlet

GitLet
Left: A demonstration that you can use this version control system just like Git; Top Right: the “criss-cross” merge function that I was not able to implement; Bottom Right: the structure of each commit/blob in Gitlet

A simple version-control system written in Java. While Git was very commonly used, especially during CS 61B, not a lot of people fundamentally understood its structure. This project, which had NO skeleton codes, was essentially a SWE project that both tested someone’s coding ability for a medium-sized project and designing ability for a persistant product.

Concepts covered: Design, Choice of the Proper Data Structures, File I/O, Graph Traversal, Hashing

Production: The structure of Git was fairly simple – you have a directed acyclic graph that in a lot of cases (without merging and intensive branching) acts like a linked list. With each node having a unique hash (in most cases), tracing is fairly easy. However, since the project did not provide any guidance, coming up with an elegant and robust solution was quite a challenge. While I did not successfully implement the “criss-cross” merging function, I definitely gained a deeper understanding for how Git worked after trying to implement it myself.

——THE CONTENTS BELOW ARE STILL UNDER DEVELOPMENT——

EE 16A

ELENG 198

MECENG 98

[1]: There is a Hog Contest every semester, which let everyone's implementation of the game "AI" compete against each other to see who has the best strategy. The top 3 ranked teams always uses machine learning(for example, Tabular Q Learning), Game Tree, and Dynamic Programming) to implement their strategies.

[2]: Tree recursion and [Levenshtein distance](https://leetcode.com/problems/edit-distance/) for which you can find on LeetCode.