Built up handful of handy features from a bare bones (single-process, almost no syscalls) operating system.

• Implemented userspace
  • Processes, threads, page faults, and appropriate syscalls
• Implemented thread priority
  • Scheduling, timers, deadlock avoidance in synchronization primitives
• Implemented a file system
  • Inodes, path resolution, caching, and appropriate syscalls

For prospective students: this class is fun, but fun and difficult aren’t mutually exclusive.

Source | Highly Recommended Reading

CS170 (Algorithms) at Berkeley has a long tradition of handing students an NP-complete problem and holding a competition to see who can produce the best computationally tractable approximation. Guavabot rescue gave a two layered problem:

• Faulty sensing
• Steiner-tree approximation

Team “go-bears'; UPDATE Teams SET score = 0 WHERE name != 'go-bears';” got rank 23 out of 320 groups. The important thing, of course, was that countless stranded Guavabots around the world were rescued.

As with other projects I can’t really reveal my group’s approach publicly since this project may resurface in future semesters, but if you’re 1) curious and 2) not planning to enroll then let me know!

Source | Specification

Title is a mouthful but that’s what it was officially labeled as! In addition to being a programming assignment this was a major exercise in secure design, so the source also includes a design document detailing the possible attack vectors and appropriate defenses. In particular the system was designed to allow trusted users to share files with each other using a client and an insecure data server. The goal was to allow for client’s to share arbitrarily large files, update + revoke access privileges, and modify files in such a way that it would be computationally infeasible for an attacker to recover information, modify a file silently, or impersonate another user even with full control over the storage server.

Implementation relies on traditional RSA, Argon2 for key derivation + password hashing, and generous applications of HMAC. Sadly still vulnerable to Rubber-hose Cryptanalysis.

Source | Relevant XKCD | Specification

A close contender for my favorite security project. Students were handed an insecure webserver and tasked to find 7 exploits. It turns out breaking stuff is orders of magnitude more fun than making stuff!

Source | Specification

A two-stage pipelined CPU that runs the RISC-V instruction set (thanks David Patterson!). This was actually a real doozy that would take a while to list out but in summary:

• Full Arithmetic Logic Unit built from ground-up with logic gates
  • Including support for word, half-word, and byte level instructions
• Memory, branching, and instruction decoding
• 2-stage (instruction-fetch, execute) pipelining
  • And cases for all the wonderful side-effects that crop out in conjunction with branching :’ )
• Lifetime supply of unit and integration tests

Source | Specification

While the previous class related post was on the first project of CS61A, this is skipping straight to the second project of CS61B. There were 4 or 5 projects in between the two, but my main problem with them was that for the most part they were nothing more than fancy fill in the blank exercises. This project changed up that format by giving a ton of freedom to the students in terms of implementation.

Picking up where we left off from Part 1, so far we’ve found a way to generate an optimal strategy for the game of Hog by recursively calculating which moves would be the best. While effective, it certainly wouldn’t have made for much of a contest if everyone who came up with this approach were tied for first. Luckily, the professor was likely aware of this possibility, and threw a wrench into the probabilistic method by forcing the strategies to work with incomplete information.

The first project of my first CS class at Berkeley was to write the logic for a modified version of the dice game Hog. The game itself is pretty simple (roll die to score points, first to 100 wins), and the project was more a less just a warm-up to get everyone used to Python syntax and higher order functions. The extra credit option, however, was a bit more interesting.

A fully functioning “Roguelike” game including:

• Procedural dungeon generation
• Tile engine, lighting, and special game mechanics (further details in video)
• Gameplay recording and playback

Blog Post | Source | Video ; ) | Specification

This project consisted of three main parts:

• Rasterize map tiles of backend and serve to the front end
• Modify an XML parser to convert OpenStreetMap data for the city of Berkeley into appropriate data structures on the backend
• Implement A* search to provide navigation directions

Source | Specification

Tools for developing optimal strategies for the game of Hog when complete information is available, and for approximating solutions when there is incomplete information. Includes visualization tools to watch strategies evolve between iterations. More details in this post

A full featured interpreter for the Scheme programming language written in Python. Supports all the beautiful features of Scheme including:

• Tail-call optimization
• Quasiquotes
• Macros

Source | Relevant XKCD | Specification