Programming Projects

These projects are from a series of programming-oriented courses offered by UC Berkeley covering basic concepts in computer science.  They were completed between between June and October of 2012.

The first course (cs61A: The Structure and Interpretation of Computer Programs) introduces programming concepts such as functions, recursion, and object-oriented programming. The second course (cs61B: Data Structures) focuses on abstract data types, data structures, algorithms, and the analysis of algorithms. The third course (cs61C: Machine Structures) involves lower-level concepts including MIPS assembly language and the representation of numbers.

Each project contains code provided by the instructor. See "project info" for the parts of the project the student is expected to complete. If the links below fail, try googling the course name (e.g. cs61b spring 2012). The readme in each download suggest a way of running the program.

Machine Player for Network Game

A computer player was created for the game Network. The computer can "look" a predetermined number of moves ahead, find which move is "best", and choose this move. This was achieved by implementing the Minimax algorithm, with pruning. This algorithm performs a depth first traversal of a tree made up of recursive calls to find a move. Pruning allows the computer to skip branches of the tree that will not result in a move better than the current move stored. See gametree_example.pdf in the zip file for details. The other major part of the project is identifying when a game has been won. This involves doing a depth first search on a graph (pieces on the board represent nodes of the graph) that determines whether a "winning path" exists between pieces. The rules of Network and how to run Network are in the zip file.

download (.zip)

Machine Player beating

Logo Interpreter

This is an interpreter for the Logo programming language. An interpreter is a function that evaluates expressions of a programming language. There are two main parts of this interpreter: 1.) a collection of evaluative functions which identify and evaluate expressions, 2.) a collection of functions that apply logo procedures. These two parts are mutually recursive. This mutual recursion makes sense in that to apply a function we must evaluate expressions in its body, and while evaluating an expression, we often run into functions. Environment objects played an important role holding name-value bindings for variables and determining the existence of variables and their scope.

download (.zip)

			Simple commands in Logo interpreter

Graph with Kruskal's Algorithm

A weighted, undirected, well-encapsulated graph was implemented using an adjacency list. It was important to keep vertex elements from a calling application separate from the internal vertex objects of the graph. A hash table was used to map application vertices to internal vertices. The second part of the project was to apply Kruskal's algorithm for finding minimum spanning trees. This required familiarity with the union-find abstract data type, as well as a sorting algorithm such as quicksort. Aside from keeping objects well encapsulated and having algorithms run sufficiently fast, this project requires tracking all the references different objects contain.

download (.zip)

			Testing the graph and algorithm

Sudoku Solver

This sudoku solver finds solutions for 4x4 and 9x9 sudokus, and returns "No Solution" if the sudoku is unsolvable. The approach used to solve a sudoku combines an adjacency list graph with a backtracking algorithm.  This backtracking algorithm is similar to the Minimax algorithm in that both do depth first search on a "tree" created by recursive calls.

download (.zip)

			Solving a sudoku

Ant Game

The Ants game is an example of a tower defense game similar to PopCap Games' Plants Vs Zombies. The player places a variety of ants and barriers to stop the bees from reaching the left edge of the screen. The main part of this project was using basic object-oriented programming to implement the different types of ants.

download (.zip)

			Bees attacking

Fish and Sharks Simulation

This is a simulation of an ocean containing fish and sharks. The first part of this project involved creating a representation of the ocean (2 dimensional array) and coding the rules that determine which fish and sharks continue to exist in the "next ocean". In the second part, methods are implemented to compress and decompress an ocean containing sharks and fishes. An ocean is compressed using run-length encoding. For example, if a row of the ocean contains 3 fishes, 2 empty spaces, and 4 sharks, this gets compressed into a linked list 3F->2E->4S.

download (.zip)

			Green fish and red sharks

Pig Game

The first part of this project implements a variation of the game of Pig. In Pig, players take turns rolling a die. The goal is to roll your way to a hundred points.  Each number you roll gets added to your total points for that turn. If you roll a one, your turn is over and you receive one point for that turn. Each turn, a player can choose to hold (end the turn but keep the points obtained) or roll. In the second part of the project, a function is created which tests different playing strategies (e.g. choose hold after obtaining 20 points for a turn) and returns an average win rate for a given strategy. See the project info for further details on the rules, different strategies tested, and how to create and test strategies.

download (.zip)

			Losing at Pig

Twitter Trends

A geographic visualization of twitter data (Americans' opinions of Texas) was developed. This was done by: gathering all tweets tagged with a geographic location, filtering the tweets for the word "texas", assigning a positive or negative sentiment to these tweets based on other words in the tweet, aggregating tweets by location, and coloring each state depending on the average sentiment of tweets closest to it. The main tasks of the projects were: 1.) creating an abstract data type for a tweet, 2.) creating functions that determine the center of a US state, what state a tweet comes from, and the average sentiment of a state. The data for tweets was provided by the instructor, and tweets were represented using Python dictionaries.

download (.zip)

			What the US thinks of Texas