Table of Contents
Course Description
The course description from the CSE 373 Course Website:
Fundamental algorithms and data structures for implementation. Techniques for solving problems by programming. Linked lists, stacks, queues, directed graphs. Trees: representations, traversals. Searching (hashing, binary search trees, multiway trees). Garbage collection, memory management. Internal and external sorting.
Introduction
Coming into this class, I knew that CSE 373 was very important to passing the technical interview. Taught in Java like CSE 142 and 143, 373 was very familiar at this point in terms of the language. In Winter 2020, the offering of the course was recently redesigned and taught by Hannah Tang. The class content was very fulfilling because it helped change the way I approach programming in that it made me realize the importance of choosing the right abstract data types (ADTs) and data structures for different situations. Additionally, I learned different algorithms and how to use them to effectively solve problems.
This post will outline my experience for the Winter 2020 CSE 373 course. It will be structured and organized very similar to my CSE 142 and CSE 143 posts. Compared to CSE 142 and 143, 373 was somewhat different in terms of structure and logistics. However, the two courses are prerequisites to the course, so it might be useful to read my previous reflections. This post will also allow me to reflect on the course and its material. I will be discussing my learning and hope that it will be useful to other students as well.
The code I have written for this class will not be publicly available. This is to prevent others from plagiarizing. Instead, I will try and offer the important lessons that I learned from each assignment. Prior to posting this publicly, on March 26, 2020, I emailed my instructor to read over this article in order to check for anything that might be deemed as academic misconduct. After not receiving a response from my instructor, I emailed my TA on April 6, 2020. On the same day, I got approval from my TA.
Homework
In my quarter, there were eight total homework assignments. Similar to 142 and 143, each assignment had their own page outlining what tasks we had to accomplish. The assignments were really interesting and seemed relevant to different applications used in the real world. Although 142 and 143 were important courses to learn from, the assignments from 373 seemed significant and useful.
For the homework, we used IntelliJ as our IDE and committed through Git into GitLab. Submission and grading was not based on internal correctness like good style, but strictly on external correctness. Although there was a small portion dedicated to checking our code, it was automated and built into Checkstyle. This allowed us to easily detect stylistic errors directly in IntelliJ. Although style was not an important part of our homework, it is still an important thing to keep in mind and I definitely made an effort to maintain the internal correctness that I had learned from 142 and 143.
Although I had some experience with unit testing, CSE 373 was the first time where I had seen how useful automated testing truly was. In each assignment, we were given JUnit tests that would check some of our functionality. However, the given tests did not check all the edge cases, so it also taught us to write our own tests. Submitting homework to the autograder gave (almost) immediate feedback and it showed me the importance of testing. Even though I think the course should have emphasized more on making us write tests, it still did a good job of showing how testing could lead to less bugs and better code quality.
Assignments
Here is the link for information on all the homework assignments for my quarter: CSE 373 Homework.
Homework 1: LinkedIntList
For this assignment, it was fairly easy and focused on setting up our computers for the rest of the homework assignments. The actual programming portion was very short and primarily to refresh the 143 concepts we had learned.
Homework 2: Deques
This assignment focused on creating different implementations of an ADT by using different data structures. An abstract data type (ADT) is a specification or model that defines rules for some data that does not specify any one implementation. In Java, the concept of ADTs are represented by interfaces. Data structures are the actual implementations of an ADT.
We were also introduced to writing tests in this assignment. I thought that it was really interesting that the tests were written in a way that tested the actual interface and not necessarily the individual implementations. By writing a single test for the interface, we were able to test different implementations for the same input and output.
Homework 3: Autocomplete
In this assignment, we were introduced to time complexity and its significance. Creating the autocomplete functionality, speed is important, so we needed to be able to efficiently find the terms that match.
The naive implementation would be to search through each individual item in the list and select the matching items. Although this implementation works for unsorted and sorted lists, the runtime would be linear. To speed this up, the important thing is to sort the list initially and use binary search to find the range that matches. Since we sorted our input already, if we find the first and last matches, we can assume that everything in between will also match. By using two modified binary searches, we can implement autocomplete with logarithmic time complexity.
This assignment was really interesting because it was the first one that showed me the importance of pruning unnecessary items. The idea of pruning on each recurrence allows us to have logarithmic time and is a really important concept that I realized during this course. This idea can be seen in binary search trees and how finding an item is done by pruning one branch and continuing down the other.
Homework 4: Heap
This assignment focused on implementing a heap efficiently by incorporating different data structures and algorithms. The heap data structure is tree-based and completely filled with the exception of the bottom level which is filled from left-to-right. In this assignment, we made a minimum priority queue. This meant that everything at the top or start of the heap had to be the smallest of all items.
Through this assignment, I learned a lot about the invariants of data structures and how to maintain them. Invariants are the things that define what data structures are and must be fulfilled in order to maintain the data type. The invariant where a heap is almost always a complete tree allows us to represent a heap as an array and find the children through an mathematical expression with the index. To make the heap efficient, we had to maintain the invariants. However, if we were to check every single item in the heap every time we wanted to add an item, it would make it really inefficient. However, by pruning items that already maintained the heap's invariants, we could make the runtime logarithmic. The idea of percolating up and down allows us to maintain our invariants in logarithmic time.
An issue that I had during this assignment was implementing the changePriority method. This method allowed the user to change the priority in logarithmic time. The main idea for this part was that the items in the heap were assumed to be unique. To solve this in linear time, we could iterate through each index until we found the item we wanted to change. However, this would not fit the requirements. To do this, we had to use another data structure that allowed us to link these unique items with the actual array indices where the values were. This assignment made me realize the difference between runtime and space complexity. By using this extra data structure, we were able to speed up our runtime at the cost of using more space.
Homework 5: k-d Tree
For this assignment, we implemented a k-d Tree that could store points and give the closest point according to a target point. A k-d Tree can work for multiple dimensions by having each node/point own two subspaces. The subspaces would depend on what depth it was at and the number of dimensions. At each nth recursive decision, it partitions by the nth dimension.
In our third homework, we implemented autocomplete where it did a one-dimensional lexicographical range search. However, to implement the main functionality for this assignment, we had to do a two-dimensional range search and by using a k-d tree, we could recursively partition. This recursive partitioning allows us to prune in multiple dimensions similar to how we would prune in one dimension using a binary search tree. This allowed us to implement the method that found the nearest point to a specific target in logarithmic time.
The main difficulty in this homework was deciding when we could actually prune. Since we wanted to improve efficiency, it was essential to prune, but not at the cost of accuracy. To determine whether we could prune one side of the node, we had to create a potential ideal point and compare it to the best point so far. Depending on which depth we were at, we would create the most ideal point for that specific node and target points.
Although we were not graded on writing tests, we were not given a lot of tests for this assignment. To ensure correctness, we were recommended to write our own randomized tests. Since we were given a naive working implementation, we could compare the outputs of the two implementations. This showed me the significance of randomized testing since it allows us to check edge cases without actually writing them out explicitly.
Homework 6: A* Search
In this assignment, we implemented a memory-optimized A* search path finder. This was our introduction into implementing a graph algorithm that found the shortest path. To save memory, we did not have all the vertices in the priority queue and instead we only had the starting vertex. The main difficulty in this assignment was how to process each edge of a node. Since we had multiple different data structures that we had to maintain, we it was important to know what they represented and which to update. For this assignment, it helped for me to write simple steps and the pseudocode. For each edge of the current vertex, choose a neighbor, calculate distances, update the mappings, and finally update the fringe.
One thing that was really interesting to me was the iterative design moving up towards A* Search. Starting from breadth-first search, the algorithm moves outwards to all the neighbors in a systematic way using a queue. However, to modify this algorithm to find the shortest path, we need to emphasize the differences in distances. To do this, we use a priority queue in Dijkstra's algorithm that uses the edge weights of the vertices. This would allow us to focus our search towards the smallest edge weights first. Finally, to get to the A* search algorithm, we add a heuristic that influences the priorities of the edge weights in Dijkstra's algorithm. Now, the priorities of the edges are the combination of the heuristic and the edge weights. By doing so, this allows us to have a search that is directed towards the end vertex instead of moving through in strictly edge weight order. I thought it was really interesting to see how this development allowed us to have different ways of finding the shortest path depending on our objectives.
Homework 7: HuskyMaps Server
This assignment was really interesting because we were extending an already existing code base. Instead of starting clean, we were given a project where we needed to write code for someone elses code. The final product was really cool because it was an application that combined a lot of our previous assignments. This assignment had us implement autocomplete, pathing, and rasterizing functionality.
For the autocomplete and pathing functionality, it was fairly simple since we had already completed our implementations in previous assignments. In this part of the assignment, we were essentially connecting our previous implementations in a way that worked with the existing code that we were given. The autocomplete part was fairly simple since we just imported our autocomplete from Homework 3 and manipulated the output so that it fit the right format. Similarly, the pathing functionality used the code we had created in Homework 5 and 6. However, we had to make sure that our inputs and outputs matched since our implementations took points as inputs, but the existing code base gave us coordinates.
The most difficult part of the assignment for me was rasterizing the entire image of the map together from smaller tile images. However, once I figured the first corner and the last corner of the tiles, it was easy to fill in the tiles in between. The next step was to ensure that the code worked for the different edge cases. This meant that I had to create bounds for my tiles so that the full image would be bounded to the tiles that we actually had.
Homework 8: Seam Carving
The final assignment was really cool because it showed us the techniques for seam carving an image. Seam carving an image involves with analyzing the images to determine the seam or path with the lowest energy or importance and removing it in a way so that the image does not become distorted. This assignment introduced reduction and graph augmentation as a way to solve different problems. Reduction is a way where we can reduce a problem so that it works with an algorithm. To do this, we modify the inputs and outputs so that it can work with the algorithm. Graph augmentation is where we manipulate the graph by adding additional nodes or edges so that we can solve graph problems.
To calculate the energy of a pixel, it was fairly simple since we were given the formulas for the closed-form expressions. A closed-form expression is a mathematical expression using a set number of operations. This means that the runtime for it should be constant.
The main functionality of finding a seam was to find the path between the horizontal and vertical seams that had the lowest total path energy. By reducing the seam carving problem to a shortest path problem, we could use Dijkstra's algorithm and use our A* search path finder that we had implemented in Homework 6. However, the main issue was that we had multiple starting and end vertices while our path finder only took one start vertex and a single end vertex. This meant that we had to somehow combine a set of vertices together. By augmenting our graphs by combining this set of vertices, we could easily use our path finder implementation on this new augmented graph.
Exams
The midterm for this course was really different compared to CSE 142 and 143. For this course, it focused mainly on the conceptual ideas and choosing specific implementations for different scenarios. For me, it was somewhat difficult to prepare for the exam. Since my quarter was only the second time since the redesign of the course, it meant that there were not many previous exams that I could prepare with. However, they did release practice exams and as the course continues, there will definitely be more previous exams available.
In my quarter, there was no final because of unforeseen circumstances. However, my guess is that the final exam would have been very similar and more focused on post-midterm content.
Overall Thoughts and Conclusion
The class was really enjoyable and fulfilling because of what I learned especially through the homework assignments. The homework and the concepts that it covered seemed really relevant in terms of the functionality that we see in real-world applications. The main thing that I thought was significant about CSE 373 was how we learned to choose different data structures and algorithms as a way to improve the time and space complexities in different scenarios. Another important thing was the method of partitioning as a way to prune subspaces and speed up time complexity.