Table of Contents
Course Description
The course description from MyPlan:
Develops competencies associated with problem-solving, algorithms, and computational models. Covers abstract data types and data structures, efficiency of algorithms, binary tree representations and traversals, searching, dictionaries, priority queues, hashing, directed graphs and graph algorithms, and language grammars.
Introduction
In my Winter 2021 quarter, I took CSS 343 which was taught by Michael Stiber at the University of Washington Bothell. This class is the second course in the Data Structures, Algorithms, and Discrete Mathematics series.
Prior to taking the two courses in this series, I had already taken CSE 373: Data Structures and Algorithms. Compared to CSE 373, I would say that the two courses (CSS 342 & 343) in this series were much slower and allowed us to learn more in-depth about the topics covered. Since CSE 373 was only one quarter long, it had to cover a lot of content in a shorter amount of time. This offered me a great introduction to the topics that were covered in CSS 342 and 343.
The Winter 2021 quarter at the University of Washington was completely remote. This might have made my experience different to what the class usually would be like. I outlined what I learned from a previous online quarter in another blog post here.
This post will outline what I learned from CSS 343 and will be structured similarly to my CSS 342 post.
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 25, 2021, I emailed my instructor to read this article for anything that might be deemed as academic misconduct. On the same day, I got approval from my instructor.
Homework
In this quarter, there were four programming assignments. Each program was split into two parts with the first week being dedicated to writing a design document and the second week for actually implementing the C++ code for the assignment. For the design document, we had to write what the program did and the different classes we would use to implement it. I think having a week dedicated for the design document helped many of us think carefully about how the program should be designed. It taught me how proper design and planning can help make the programming aspects easier. However, the majority of the work for each assignment was still in the programming and implementation. Overall, the homework assignments were really interesting and showed how problems could be solved with specific data structures and algorithms.
Program 1
The first assignment was using binary search trees to construct concordances. Given an input file of text, we were to take each valid word and take the five words before and after it to be stored as the context. The program would then output each word alphabetically and the different contexts that the word had in the original text.
Since we used binary search trees, it allowed us to insert a node quickly and still maintain the alphabetical order. This is because a binary search tree allows for us to effectively ignore an entire side. For each node in the tree, we can assume that the left child is less than the current node and the right child is greater than the current node. Once we determine which way to go, the nodes that we still need to search is cut in half.
Another difficulty during this program was creating the actual nodes to store each word and the relevant context information. This is where a good design document would be useful. Each node in the binary search tree should have a key that is unique to a specific word. However, since each word can have multiple occurrences in the original text, the node should also include the different occurrences. Additionally, for each occurrence, we still need to store the context information. These nested data structures can be confusing but by doing the design document before I implemented it, I had enough time to think about how I wanted my classes to be structured.
Program 2
Program 2 used a graph to compute Bacon numbers. We were given a substantial movie database as input and needed to parse it so that we could compute each person's Bacon number. A person's Bacon number is calculated by the number of links to Kevin Bacon via shared movie roles.
In this program, I had trouble parsing and cleaning the input. What helped me solve this was to look at the input and find patterns in each entry. The program specification also told us how each entry was formatted. To parse the input, I just had to isolate each section according to how each entry was formatted. For example, every movie title followed a series of tab characters. This meant that whenever I found tab characters, I could assume that a movie name would follow after the last tab.
Once I had parsed the input file, I had to create adjacency lists for each person. To solve this problem, I decided to discard the movie information after building the graph. However, I still needed to maintain the connections between the movies and the people who had a role in the movie. When I build the graph, I keep track of a specific movie and the people that I have already parsed. So if a new person has a movie that I have already seen, I can go back to that movie and update the people that have already been added to the graph. This means that I just need to worry about the current person and the people in the same movie before them. For example, when I first see a movie, I only know that one person is associated with it. However, when I see the same movie again, I can look at the people already in the graph with that movie and make the connection at that point.
To compute the Bacon numbers, I conducted a breadth-first search on the graph I had created. Starting at Kevin Bacon, I could increment a count depending on what level in the search I was at. Since the connections in the graph represented shared movies, I could use that count to determine the Bacon numbers for all the people in the graph.
Program 3
For Program 3, we simulated a distributed denial of service attack on 911 emergency services with a priority queue. We were supposed to simulate calls from legitimate and bot callers and output the average total service time for a legitimate call.
The main difficulty that I had was understanding how time was processed in an event-based simulation. We had two types of events in the simulation: call-placed and service-ended events. At the beginning of each simulation, legitimate and bot call-placed events are generated and added to the priority queue with different times. In this case, the times were the priority since we wanted to sort the events in the order that they were placed. This was somewhat straightforward to me.
When a call-placed event is processed from the priority queue, a service-ended event would be created. This represented the ending of a call-placed event and would be how we tracked the simulation statistics. It was somewhat confusing to me because I did not really understand why the service-ended events would work. This is because these events can be added anywhere in the timeline of events. Given a specific priority, the event will be added to the priority queue in the spot that maintains the ordering. The time in the simulation only jumps when the next event is processed. However, during the simulation, events can still be added anywhere in the ongoing timeline because of the priority queue.
Program 4
The last assignment was to take in an initial Sudoku puzzle and use a genetic algorithm to solve the puzzle. This program was really interesting because it showed how a randomized algorithm could solve a problem through mutation. The program would generate a population and for each item in the population, the board squares could have a chance of mutating into a different number. By having a class to calculate the "fitness" of a puzzle, we could determine when we had a better or worse solution. After each generation, the worst percentage of the population would be removed and the mutation would happen again.
My main takeaway from this specific assignment was the use of interfaces and design patterns. Interfaces allow for subclasses to implement the functions that they define. By using interfaces, we can enforce a specific shape for a subclass. In terms of this specific assignment, the interfaces could allow us to reuse the genetic algorithm for a different type of puzzle. We would have to write the code for that specific puzzle but the overall shape and function signatures would be provided already.
The specification for this assignment was very thorough since it was an introduction into the different design patterns. Design patterns allow for a developer to reuse a more generalized idea or concept for a specific application. In this particualar assignment we mainly used the abstract factory and strategy design patterns.
Exams
In this quarter, we had two exams. However, for my specific quarter, the final was optional.
Midterm
The midterm covered:
- trees
- graphs
- heaps
Instead of programming questions, the midterm was mostly conceptual. For example, a question required us to draw diagrams of a specific data structure before and after an item was added/removed.
Final
The final for this quarter was optional, so I decided to opt-out.
However, I think the final exam would have covered:
- balanced search trees
- hash tables
- object-oriented programming and design patterns
- finite state machines and grammars
Overall Thoughts and Conclusion
Although I had learned these data structures before, the course was still really interesting. The homework assignments were a great way for me to apply my knowledge of these data structures in a different application. The main thing that I learned from this class was the importance of design and how it can help developers build programs easier. By taking the time to design properly, a lot of problems can be avoided when actually implementing the program.