My Experience in CSS 342: Data Structures, Algorithms, And Discrete Mathematics I

Autumn 2020

During my Autumn 2020 quarter, I took CSS 342 at the University of Washington Bothell. I had taken a data structures and algorithms class before but I did not have much experience with C++. From this course, I learned more about class design and object-oriented programming. My main focus during this class was learning more about C++ and the language-specific details. Overall, the course was a great introduction into C++ and a chance for me to relearn the data structures I had learned before.

Table of Contents

Course Description

The course description from MyPlan:

Integrating mathematical principles with detailed instruction in computer programming. Explores mathematical reasoning and discrete structures through object-oriented programming. Includes algorithm analysis, basic abstract data types, and data structures.

CSS 342 MyPlan Page

Introduction

I took CSS 342 in Autumn 2020 which was taught by Robert Dimpsey at the University of Washington Bothell. CSS 342 is the first course in the Data Structures, Algorithms, and Discrete Mathematics series at UW Bothell.

Coming into this class, I had already taken CSE 373: Data Structures and Algorithms, a course that covered many different advanced data structures and algorithms. Compared to CSE 373, CSS 342 was much slower and covered the basic data structures like linked lists, stacks, queues, and binary trees.

The introductory classes (CSE 142 & 143) and CSE 373 were taught in Java. My main focus coming into the course was to learn C++ and the specifics of the language. Having very little C++ knowledge, I struggled with pointers, references, and dynamic memory allocation.

In CSE 373, we only focused on the basics of Big O notation. CSS 342 covered computational complexity and algorithm analysis in a more formal way. In addition to that, the course covered propositional logic. CSS 342 covered basic data structures and algorithms but also focused more on the math-related topics.

The Autumn 2020 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 342.

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 January 3, 2021, I emailed my instructor to read this article for anything that might be deemed as academic misconduct. On January 6, 2021, I got approval from my instructor.

Homework

There were five total homework assignments with the fourth assignment being completely optional. The assignments were mainly based on having the correct output given some sample input. Some points were also allocated to style points and the overall design of the solution.

For the class, we were told to use the Google C++ Style Guide. This was really helpful in terms of having a resource to use whenever I was stuck on how my code should look. Following a style guide is helpful so that code can be easily understood by yourself and others.

Another resource that was helpful for some assignments were the example code snippets on the course website. They were a good starting point for me to see the big ideas and how to implement them in C++.

Program 1

The first homework assignment had two problems to complete. We had to design the coin-operated bank in a vending machine (VendingBank) by writing the C++ header file. Next, we had to design and implement a TimeSpan class that represented a duration of time.

This assignment had many design aspects that allowed us to think about objects and classes. The important thing was to determine what an object can store (as data members) and what they can do (operators and member functions).

Coming from a background in Java, I thought the operator overloading in C++ was a great way to make code easier to understand. However, operator overloading introduces complexity with references and other keywords like const. Throughout the quarter, I had to remember when variables were passed as values and when they were passed as references. I think it is a great exercise to look at code and understand how things are passed throughout a program.

  • Pass by value: creates a copy of the object
  • Pass by reference: allows us to access the actual object instead of making a new copy.
  • Pass by const reference: allows us to access the actual object, but does not allow modifications

For example, overloading the + and += operators:

// operator+ adds two objects
// returns a new object (as the sum)
MyObject operator+(const Object& other) const;

// operator+= adds the other 
// object to the current object
MyObject& operator+=(const Object& other);

In the operator+ function, the two objects being added together should not be modified. The const at the end of the function shows that the underlying object associated with the function is not modified. The other object is passed as a const reference. This allows us to access the actual objects without allowing modifications (since we do not need to change the original two objects). By passing things in as a reference, we can avoid unnecessary copies of a large object. The returned object is a copy, since the one created within the function would be out of scope after it exits.

In the operator+= function, only the current object should be modified. We can see the difference since the function does not have the const keyword at the end. However, the other parameter is still passed in a const reference since we only need access and do not need to do any modifications to it. The return value is passed as a reference because we are making modifications on the current object and do not need a new/copy of it.

Program 2

Program 2 also had two separate problems. First, we had to write a recursive program to compute the n-th Catalan number. Then, we had to write a program to find all the unique shortest possible paths from a start location to a end location given that we cannot move in the same direction more than a specific times in a row.

The first part of the assignment was not too difficult since we were given a recursive formula that calculated the n+1-th Catalan number. What helped for me was to change the formula so that it would calculate the n-th number instead of the n+1-th number.

The pathfinding portion was more difficult. Since we wanted to find all unique paths, I started with a depth-first search which would begin at the start and track whenever it reached the end location. Through each of the function calls, my program would track each step and build the path until it reached the end. Now that I had the basic approach, I could modify my code so that it would stop moving in a direction if we had moved too many times in a row. Since I stored my path in the function calls, I could see the history of my path and determine if I should traverse in a specific direction.

This assignment showed me to approach problem-solving in an iterative fashion. First, I noticed that a depth-first search would be appropriate to find all the unique paths. Then, since the problem asked for the unique paths given that we cannot move in the same direction, I adapted my code so that it would factor in the history of the path.

Program 3

The third assigment covered linked lists and dynamically allocated memory. I had used linked lists in Java before so my main difficulty was in allocating memory. For this assignment, we had to implement a templatized class that used a linked list to maintain a sorted order.

Since we were dealing a lot with pointers in this assignment, it was important for me to understand the types of different variables I was accessing. Pointers allow for us to have a variable that stores the address of another variable.

// construct my_obj
MyObject my_obj;

// points to address/reference
MyObject* my_obj_ptr = &my_obj; 

// dereferences ptr and set var to copy of object
MyObject my_new_obj = *my_obj_ptr; 

// dereferences ptr and set var to object
MyObject& my_obj_ref = *my_obj_ptr;

This assignment had us implement a list that stored dynamic memory so it was necessary to have proper memory management. It was important to eventually have a delete for each new that I wrote in my code. When using the new keyword, the program allocates memory on the heap which persists until it gets deleted or the program ends.

Whenever you use dynamically allocated memory, it is also important to overload the copy constructor, assignment operator, and destructor. These three functions are usually handled by the compiler since it can copy over the data members. However, with dynamically allocated memory, your program may be trying to access memory that belongs to a different object. By overloading the copy constructor and assignment operator, you can ensure that any copies of your object are unique to themselves and will not modify other objects. The destructor is important to implement as well because the memory will not be released until you delete it or the program ends. By implementing the destructor, you can avoid memory leaks in your program.

Program 4 (Optional)

The fourth assignment was optional during my quarter and covered various sorting algorithms. Although I did not do this assignment, I think it would have been good practice to implement each algorithm. We did cover each algorithm in class and it was a good opportunity to talk about computational complexity and Big O notation.

Efficient algorithms are important because as the dataset grows bigger, algorithms will take longer and longer to compute. Using the Big O notation allows us to talk about the efficiency of algorithms and how the performance behaves as the data grows bigger.

The sorting algorithms that we covered this quarter were:

  • Bubble sort
  • Insertion sort
  • Selection sort
  • Merge sort
  • Quicksort
  • Shellsort
  • Radix sort

Program 5

This last assignment had us create a banking application that processes transactions. It also had a portion for us to design the different classes/objects we needed and how the program would work as a whole. The program flow was broken into three main stages: reading transactions, processing transactions, and printing balances.

We used queues to store each transaction so that the order would be when the transaction was read in. We also used a binary search tree to store the accounts so that searching for a specific account was efficient. In this assignment, we only needed to implement the binary search tree ourselves.

The main difficulty that I had was making sure that all my classes made sense and could integrate with each other easily. Overall, this assignment was a combination of what we had learned throughout the quarter. The main thing I learned from this assignment was the importance of abstraction and encapsulation through objects and classes.

Exams

In this quarter, we took three different exams.

Test 1

For this first test, the main topics covered were:

  • C++ basics
    • pass by const, const&, and value
  • class design
  • operator overloads

Midterm

The midterm covered:

  • recursion
  • dynamic memory allocation
  • sorting algorithms
  • various data structures
    • linked lists
    • vectors

Final

The final exam was mostly discrete math which covered:

  • Big O notation
  • propositional logic

Overall Thoughts and Conclusion

CSS 342 was a great introduction to C++, basic data structures, and other sorting algorithms. Although I had learned these data structures before, it was a great experience learning C++ and using what I had learned before in a new language. This course taught me a lot about memory allocation and how it works with references and pointers in C++.

Resources