CS61B - Data Structures

_{Written 8-23-19}

A class all about data structures. I learned so many things in this class that I didn’t know before. We covered so many different data structures, their applications, and run times among other things. All of our homeworks, labs, and projects served to apply what we learned and they really were particularly fun challenges to solve. I can’t really post any code, but I’ll just write a little about the more interesting homeworks and projects we did. Mostly the stuff with graphics because then I can post pictures.

Project 0: NBody

Simulating bodies in space to provide a crash course Java. Pretty much just followed the instructions, but it was still pretty cool.

HW2: Percolation

This was a particularly fun and challenging homework to get all the points for. The premise of the homework is to find when a system percolates, which you can imagine as water flowing from the top to bottom through openings. It was a pretty cool application of Disjoint Sets. The gist of the solution is to connect the top and bottom rows to virtual points and whenever these virtual points are connected the system percolates. One issue that I ran into was preventing backflow, which is when the liquid flows through the virtual bottom point and back up. My solution was to use another Disjoint Set to keep track of backflow, which was actually a pretty popular solution. It used more memory, but worked perfectly.

HW3: Hashing

One of the more conceptually interesting data structures, well they’re all interesting actually, are those that involves hash codes. It’s pretty crazy to have a data structure that has an O(1) average search and insert and delete. We also learned more about hash functions and how there must be an overlap so hash functions should be chosen to have an even spread.

HW4: AStarSolver

Using MinPQs to help implement the A* algorithm, we were able to solve a bunch of cool puzzles that from a certain point of view could be viewed as trying to get from one place to another with the minimum cost. We also made it memory efficient by only ever adding neighbors as they came along. We were using A*, but a lot of times we had a constant heuristic function so it reduced to good old Dijkstra’s algorithm. There’s no fancy graphics this one, but solving puzzles was pretty dang cool.

Proj2C: Bear Maps

Combining a lot of what we learned before from MinPQs to A* to Tries, we implemented a basic maps system. The biggest challenge of this part of the project was to pick all the images to display based on the zoom level. It was a bit tricky working out all the bugs, but I got it eventually.

Proj3: BYOW

Last but not least and perhaps the most fun project of the semester, we got to make our own game, complete with randomized world generation, a save system, and enemies that chase you around. We were given a lot of flexibility with this project, including many different challenges we could complete for various amounts of points. Since this was quite a big project, my partner and I spent a lot of time thinking about the implementation. Some of the included methods pointed us into the right direction of well organized code that was easily modifiable to do a lot of the ambition points.

The world generation was probably the most complicated part of the project. We started by making rooms of various sizes and then connecting them with hallways. We were inspired by a friend of our’s idea to do something like raytracing to do hallway generation. Taking this idea and adding a couple of our own randomizations, we ended up with a nice world generator.