SpecialHeap

Hello everyone,

This week we are going to be looking into binary min-heaps, and how they can be used to find the k smallest elements within an given array of numbers and a given k value. As always, feel free to leave a comment and lets get right into this.

What is a Binary (min) Heap?

A binary heap is a data structure that takes the form of a binary tree. A binary heap has two different properties that defines what it is: a structure property and a heap-order property.

Structure wise, a binary heap takes the form of a complete binary tree. The heap-order property depends on the kind of binary heap we want to implement.

Since we are going to using a binary min-heap in our program, our heap-order property will be as follows: the root of the tree (or the subtree) is the smallest node in the tree (or subtree). Basically, the smallest value in the entire is at the root of the tree.

We will be able to take advantage of this heap-order property when finding the k smallest elements in a given array. In our implementation, we will be returning an array with the k smallest elements at the k greatest indices (for example we have an array [1, 2, 3, 4, 5, 6] and k = 2, then the result array would be [3, 4, 5, 6, 2, 1]).

The Implementation

In this lab, we will be implementing to kinds of template classes: a Heap class and a SpecialHeap class. Our Heap class will be our base binary min-heap class, while the SpecialHeap class inherits our Heap class. SpecialHeap will contain one unique method called get_k_smallest(), which will find the k smallest elements the array and format it as mentioned in the last paragraph of the "What is a Binary (min) Heap?" section.

Our Heap class will represent a complete binary tree in the form of a vector. This is possible by having our root node be at index 1 of the vector, our parent nodes being at k/2, our left child at 2k, and our right child at 2k+1. This can be seen below:

The reason why we are using a vector in our implementation of a binary min-heap instead of a binary tree is because it is simpler than implementing a binary tree, while also mimicking what a binary tree does. We can not use a binary search tree either because the heap-order property will violate the binary search tree order property.

Our vector in our Heap class will have a size of (2^N), where N is some value, so we have enough room to store a complete binary tree. Our vector will be initialized with the appropriate size in our default and parameterized constructor. Within our Heap class we will also have a "size" data member, which will keep track of the number of items that exist within our heap.

Our Heap class will have two private methods called _heapify() and _percolate_down(). _percolate_down() takes a vector index as input and ensures that the given element at the given index is in the correct place in the heap according to the heap-order property. _heapify() will be used in our parameterized constructor, and it ensures that an unordered heap becomes ordered. This is done by calling _percolate_down() starting from index N/2 and ending at 0.

We have two constructors: one default constructor and one parameterized constructor that takes in a vector as input. The default constructor initializes our internal vector to a default value of 128 (because of the 2^N requirement) and our size as 0. The parameterized constructor will set the size data member to the size of the input vector, set our internal vector to have a size of the input vector + 1, copy all the items from the input vector into our internal vector, and then call _heapify() to order our heap.

In both of the constructors, since the root starts at position 1, we fill position 0 with a sentinel value. The sentinel value is the lowest possible value for the data type that our template class is initialized for.

The rest of the methods are as follows:

• is_empty(): Tells user if the heap is empty
• insert(): Inserts an element into the heap
• delete_min(): Deletes the smallest element in the heap (basically the root)
• peek_min(): Returns the smallest element from the heap
• to_string(): Returns a string representation of the heap.

Now for our SpecialHeap. Since our SpecialHeap class inherits from our Heap class, we don't really have much to implement. All we have to do is implement our get_k_smallest() method, which is pretty easy to implement. Within our get_k_smallest() method, we do the following steps k times:

1. Get the smallest element through peek_min().
2. Delete the smallest element through delete_min().
3. Copy the smallest element we have to the just vacated cell of the heap (index size + 1).

Once we are done with this, we set the size to 0 and return our internal heap vector. Now we are able to return an array (or vector in this case) where the k smallest elements are at the k greatest indices.

Lab Questions

Q: Why you would use Quickselect (or Quicksort) at all instead of simply using a special heap (or Heapsort)?

A: I would say you would use Quickselect (or Quicksort) instead of using a special heap (or Heapsort) because it uses less memory while still achieving similar times alongside Heapsort. Although both our SpecialHeap and our Quicksort method from last week both do in-place operations, SpecialHeap uses more memory because it has to store the heap, data members, and class methods, while Quicksort can be implemented using two methods (as seen from last week's post).

Q: Why no use a balanced binary search tree for your backing store? Which of our original requirements (on page 1) would this implementation satisfy? What is the tradeoff, if any?

A: We do not use a balanced binary search tree because our heap-order property will conflict with the order property of a binary search tree. If it were possible to use this kind of implementation would probably satisfy the run-time complexity requirement of achieving O(k log N), but not the space requirement of O(1). The tradeoff would probably be same speed as the vector implementation, but uses more memory.

Conclusion

As we can see, a binary min-heap allows us to find the k smallest elements in an array, given a value of k. Although we only talked about binary min-heaps,  we can modify our Heap class in such a way that allows for the create of binary max-heaps, which have a heap-order property that states the root of a tree (or subtree) is the biggest node in the tree (or subtree). I hope you enjoyed this week's post. Feel free to leave a comment and I will see you next week!

K'th Smallest Element

Hello everyone,

This week we will be looking into the K'th Smallest Element problem. This week's lab gives us a break from implementing data types, allowing us to look into some sorting algorithms. The sorting algorithm we will be discussing is the Quick Sort algorithm. As always, feel free to leave a comment below and now lets get right into it.

The K'th Smallest Element Problem

Given an array and a value of K, we need to find the K'th smallest element within the array. An example would be if I have a K = 4, then I need to find the 4th smallest element within the array. The solution to this problem would be to sort the array in ascending order and return the K'th element in that array (since it is our K'th smallest element).

However, the run time of this solution will be slow because we are doing a complete sort before returning the K'th smallest value in the array. We can speed this up by not doing a complete sort. We will see this in the implementation section. For now lets get into what Quick Sort is, since we are going to use it to solve this problem.

What is Quick Sort?

Quick Sort is a sorting method where we choose a number call a pivot, and we split the array of elements into two sub arrays; the left sub array containing elements < pivot and the right sub array containing elements > pivot.

Quick Sort Visualized

The act of splitting a single array into two sub arrays in quick sort is called partitioning. The idea behind quick sort is that it is a recursive sorting function. Each quick sort calls results in one call to a partition function, and two more quick sort calls; each one address the left and right sub arrays we created. With each recursive call, we get smaller and smaller sub arrays but also getting closer and closer to a sorted array. Once all the recursive calls return back to the very first quick sort call, we get a sorted array.

Now, there are different ways you can go about partitioning the given array. The method we are going to be using is called the Lomuto Partitioning Scheme, and it is considered to be one of the simplest partitioning methods out there for quick sort.

What is the Lomuto Partitioning Scheme?

The Lomuto Partitioning Scheme starts out with a pivot, a cursor, and a scanner. Our cursor and scanner both start on the left side of a given array, with the scanner moving from the left side to the right side of the array. When the scanner finds a value less than the pivot, it will swap its position with that of the element at the cursor. After the swap, the cursor moves one index up and the scanner keeps moving along the array. After the scanner is done traversing the array, we do a final swap of the element located at the cursor with our pivot.

The idea behind this method is that we create the two sub arrays as mentioned before. The final swap in the end makes sure that our pivot is in a spot where the elements on its left is less than the pivot and the elements on its right is greater than the pivot.

Here is a nice video that does a pretty good job at explaining and showing what the Lomuto Partitioning Scheme is and how it behaves:

The Implementation

This lab we are going to implement three different functions; one will be our partitioning function (we will call partition()) while the other two will be used to find the K'th smallest element (both will be called find_kth_least() but each have different parameters.

Our partition() function will take in three parameters: a vector, and a start and end input. We have a start and end parameter because of the two sub arrays created with every call to the partition function. The partition() function will be an implementation of the Lomuto Partitioning Scheme. The only difference is that the pivot will be the element in the middle of each sub array (meaning (start + end) / 2) instead of the right most element of the sub array as seen with typical implementations of the Lomuto Partitioning Scheme. However, to keep our partition() inline with the typical Lomuto Partitioning Scheme, we will swap the location of our pivot with the element at the right of the sub array.

Now for our two find_kth_least() functions. One of them will be considered as our "public API" function, which takes in a vector and a k value. Within this "public API" function, it will filter the inputs and then make a call to our second find_kth_least() function. This second find_kth_least() function utilizes recursion to determine what the K'th smallest element is in the array.

Our recursive find_kth_least() function takes in four parameters, a vector, a start value, an end value, and a k value. Within our recursive find_kth_least(), we first check that a valid sub array was passed in by checking that our start value is less than or equal to our end value. From there, we call our partition() function, which will return the location of the pivot. If the location of the pivot is equal to k, then we found our kth smallest element. Otherwise, we see if the location of the pivot is bigger or smaller than k, which determines what the next recursive call will do.

The reason we want our pivot to be in the kth index of the array is because of the properties of the pivot. All the elements on the left of the pivot is less than the pivot itself. By having the pivot be in the kth location of the array, it tells us that it is the kth smallest element of the entire array without sorting the entire array.

Lab Questions

Q: Suppose you want to calculate the median of a given array of integers, how would you use your pivoting strategy to do it?

A: To calculate the median of a given array of integers, I would probably partition the array until the location of the pivot is in the middle of the given array. The reason being that the median of a list of numbers can be seen as a pivot, since the numbers to the left of the median is smaller than the median and everything to the right of the median is bigger than the median. So, we just need to partition our array until the location of the pivot is in the middle of the array.

Q: Does your strategy yield the k smallest elements or the kth smallest element?

A: This strategy yields both the k smallest element and the K'th smallest element. The K'th smallest element, as said before, is a pivot whose location is kth index of the array. Everything to the left of that pivot is smaller than the pivot itself, meaning they too are the k smallest elements in the array.

Q: We saw that this algorithm is O(N) in the number of elements. Can you do better (meaning sub-linear)? Why or why not?

A: I would say that is it not possible to have an algorithm that can do this with a sub-linear time complexity. The reason I have at this moment is is because of our partition() function, which requires a linear traversal of the entire sub array when partitioning, even though the sub arrays themselves get smaller and smaller by some amount.

Q: Since sorting solves the problem in O(N log N) time, your algorithm probably doesn't sort the input (otherwise you can get a sub-log-linear sort algorithm, right)? What is the trade-off? What are you giving up to get the run-time advantage? Looking at this from the other direction, ask what more a sorting algorithm does that goes unused by you (and is thus safe to omit)? What is the time complexity of just this "omitted" operation in a full fledged sort?

A: I would say the trade-off of not doing a complete sort to increase speed is a unsorted array. Our algorithm at the moment will return the K'th smallest element of the array and a partially sorted array as well (since our vector parameters are actually references). The draw back of this is that we could be completing two tasks at the same time, finding a K'th smallest element and sorting the array. If we were to find another K'th smallest element on the same array while it is partially sorted, it will take more time than finding another K'th smallest element on the same array when it is completely sorted.

Q: How can you get the k smallest elements in the array? What is the time complexity of that procedure? What if you wanted these elements in sorted order?

A: With our current implementation, to find the k smallest elements in an array you would have to find the K'th smallest element in the array (as discussed in the second question of this list). The time complexity of this procedure would be around the same as our current implementation of find_kth_least(). If you wanted these elements in sorted order, the easy way would just to sort those elements only; however, it could affect the overall run time.

Q: Why is it important to make sure that Quicksort does not degrade to O(n^2) on an array of identical values?
A: It is important to make sure that Quicksort does not degrade to O(n^2) on an array of identical values because we are wasting time and resources on an array that is technically already sorted. We can figure out if an array is filled with the same value by doing a quick O(n) traversal check before starting Quicksort.

Conclusion

 The solution to the K'th Smallest Element problem in this case is similar to the implementation of Quicksort. The only difference is that we are not looking to sort an array given to us, rather we are looking for a pivot that is the K'th smallest element. I hope you guys enjoyed reading this post. Feel free to leave a comment and I will see you guys later!

Hash Tables

Hello everyone,

This week I we are going to be looking into a lab that investigates the implementation of Hash Tables. This lab is what I consider a little bit more challenging compared to the other labs I have touched on. Without further adieu, lets start with learning what a hash table is.

What is a Hash Table?

A Hash Table is an ADT that uses a key to determine where in an array to store data. A good example of this is a phone book, where each person's name (the key) corresponds to their phone number (the data). The Hash Table would turn the key into a hash, using a hashing function, to determine where in an array is data located.

Hash Tables are used mainly for quick access to data, with a worst case of O(1). However, hashing functions would sometimes give an index that is already in use, causing a collision. There are some solutions to the collision problem, with some common ones being separate chaining, linear probing, and quadratric probing.

A Hash Table that uses separate chaining contains an array of linked lists. The idea is that if the hashing function gives a location already occupied with a piece of data, it adds a new node to the linked list in that location (as shown in the image below)

The issue with separate chaining occurs when there is clustering: where data starts gathering is a portion of the array. Clustering causes the traversal times of linked lists to grow and also wastes some memory due to unused slots in the array.

A better alternative to separate chaining is called open addressing, where we have an array with no linked lists within them. This is where linear and quadratic probing comes into play. With open addressing, if a spot given by the hash function is taken, the hash table will check the spot next to it and see if it is empty until it finds a vacant spot (solving both access time and collisions). Linear probing causes our hash table to check the next spot if there is a collision, while quadratic probing checks the index + k^2th spot.

Linear and Quadratic Probing

Linear probing causes more clustering than quadratic probing, since, as shown in the image above, linear probing have smaller probing intervals than quadratic probes.

There is a lot more things behind hash tables, some will be mentioned in the implementation section, but this is a general idea of what a hash table is and the different implementations of hash tables. Here are two sites that does a better job at describing linear and quadratic probing. Now lets get into the implementation.

Linear probing: http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/05/linear-probing.html
Quadratic probing: https://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture16/sld019.htm

The Implementation

In this lab we implemented two hash tables: one that uses linear probing and another that uses quadratic probing. Since the two probing methods utilizes similar functions, our quadratic probing hash table is inherited from our linear probing hash table.

Both hash tables have an inner class called Entry and a vector of these Entry's to be used to store data. Each Entry will store the data given to it and the state of the entry: active, vacant, or deleted. States are important when it comes to inserting and removing data from the table.

Our hash tables will calculate a value known as a load factor whenever it is approriate; the load factor is found by dividing load_size with the size of the vector. The load factor determines when to resize our hash tables to make sure that our linear/quadratic probing finds us a vacant spot.

Our hash function uses the C++ STL "hash" class template, so we do not have to spend time figuring out how to make an effective hashing function

Besides the usual insert() and remove() methods, we have a set of methods that are very important to our hash tables:
hash_and_index() and find_pos(): hash_and_index() calls our hashing function and returns the result that our hashing function provides to use. This method is called within find_pos(), which is where our linear or quadratic probing occurs (depends on how find_pos() is overriden).

rehash() and grow_capacity(): rehash() is called when the load factor we mentioned earlier exceeds a set max load factor. Within rehash(), it will call grow_capacity() to grow the vector and moves all non-deleted Entry's from the old vector to the newly resized vector.

default_max_load_factor(): Essentially returns the default max load factor value whenever the user decides to set a max load factor that may end up breaking our hash table. 0.75 is typically used for linear probing hash tables while quadratic probing hash tables uses 0.5.

The methods we override in our quadratic probing hash table class were just default_max_load_factor(), find_pos(), and grow_capacity().

Within our quadratic probing hash table implementation, we added a helper method called next_prime() which returns the smallest prime number after a given value we pass into the method. These prime numbers are used as the size of the vector in a quadratic probing hash table to ensure that that empty spots are being found and used quickly.

I believe this is pretty much it when it comes to implementing linear and quadratic hash tables. I would suggest watching videos about them because reading will cause confusion for some (especially for me the first time I read about them!).

Lab Questions

Q: How can you be sure that if the QP probing strategy won't get stuck in a cycle of fruitless examinations (i.e. there exist vacant cells in your table, but you never encounter them)?
A: I would say that the QP probing strategy won't get stuck in a cycle because of the size of the table are prime numbers. I forgot to mention that within hash_and_index(), there is a line of code that takes the result of C++ STL's hash functor and applies a modulus to it of the table size (Hash(x) % vector.size()). As mentioned in these set of notes, the prime numbers are used to make sure that the even value indices are not the only ones being used, allowing for more spots to be used. The thing with prime numbers is that they can get big pretty fast, meaning more space within our vectors to act as a buffer to prevent our quadratic probing from being stuck in a cycle.

Q: How is the average element access time affected by the probing strategy?
A: I conducted some tests involving inserting up to 1 million elements into a hash table, and based on the results it seems that both linear and quadratic probing have similar insertion times. As I was increasing the number of elements inserted into the hash table, the average times were increasing by small amounts. Same thing occurs when I was decreasing the max load factor value. I even tested to see what happens if I set my max load factor close to 0 (such as 0.00000000001), with the result being that it hangs the program.

Q: What happens when you delete an element by setting its VACANT flag instead of the DELETED flag?
A: Deletion in hash tables is essentially similar to the lazy deletion mentioned in the Lazy BST post. How deletion work in hash tables is that you would use find_pos() to find the item we want to delete and mark it's associated Entry object as DELETED. If we were to set the state of the entry to VACANT, it would produce a gap in between our data that can result in elements to the right of that location to "go missing" in our algorithm.

Conclusion

Hash tables are great when it comes to quick data access. However, implementing them is very tricky and confusing as we see here. Though, we can overcome this trickiness and confusion with the vast amount of resources available to use. One site I posted, which belongs to RMIT in Australia, does a pretty good job in explaining what linear probing is and provide the source code for the methods associated with linear probing, with some of the code being highlighted in different colors to be more visual friendly. Overall, hash tables are complicated but fast ADTs when it comes to accessing data. I hope you enjoyed reading this post, and, as always, feel free to leave a comment and have a good day!

Top Down Splaying

Hello everyone,

This week we will be talking about Splay Trees, a varient of binary search trees that uses some algorithms associated usually with AVL trees. In this lab, we used the BST class we coded last week to make our Splay_BST lab this week. As always, feel free to leave a comment and lets get into this.

What are AVL and Splay Trees?

Before we begin, we need to know what an AVL tree is. AVL trees are self-balancing binary search trees. AVL trees are seen as unbalanced when the height of each node in the left and right subtrees differ more than 1. AVL trees are designed to keep the worst case of operations done on the tree (such as searching) closer to O(log N), since most operations of binary search trees are dependent on the height of the tree. AVL trees balance themselves automatically when operations such as insert() and remove() are called, using a technique called "rotation". I suggest doing your own personal study on rotation as it is a tricky topic to understand, but it is used in our Splay Trees.

Now, Splay Trees are a form of binary search trees that have the most recently accessed or inserted element as the root of the tree. The idea behind Splay Trees is to have faster access times for recently used items, since they will be either at or close to the top of the tree. Downside of Splay Trees is that operations like insert and remove will be a bit slower, as the tree needs to be restructured every time it is splayed.

The Implementation

Our Splay_BST class will be inherited from our BST class, since Splay Trees IS-A binary search tree. There are many different kinds of implementations of a Splay Tree out there. What was different about this lab is that we were given the pseudo code of the splay() algorithm and we had to write the code for it.

The algorithm we had to code up utilizes Top-Down Splaying, which essentially is splaying from the top of the tree to the bottom. There is another method called Bottom-Up Splaying, but it is more difficult to code than Top-Down Splaying. 

The splay() algorithm utilizes the same kind of rotation as AVL trees, except we are not worry about the height of the nodes in our Splay_BST class. splay() also utilizes three kinds of trees: the main tree, and a left and right tree. The left and right trees are used in the restructuring of the tree, which is assembled at the end of the splaying. 

Now, splay() will be a private method that is used in operations such as insert(), remove(), and find(). The reason for it is that the user does not need to know or use splay(), and the functions I just listed need to call splay() to insure that our Splay Tree stays as a Splay Tree.

Lab Questions

Q: How can you tell if splaying has resulted in any benefits? What kind of experiments can you do to test for it?

A: You can probably tell if splaying has resulted in any benefits by comparing the runtimes of insert(), remove(), find() in binary search trees, AVL trees, and the Splay trees. If you were to do tests on these three trees, AVL trees and Splay trees will be somewhat close to each other since the balancing in both of them will result in worst cases being close to O(log N). However, Splay trees will be a little bit faster in tests that result in multiple accesses of the same item, since recently accessed items are at the top of the tree.

Q: Does splaying preserve tree balance according to the AVL criterion? Or any other criterion?

A: I forgot to mention this above, but Splay Trees are essentially AVL trees with another condition. AVL trees have three conditions: a structure condition (from binary search trees), an ordering condition (also from binary search trees), and the AVL balancing condition (which states that the height of each node in the left and right subtrees differ by at most 1). Splay Trees just add one more condition to AVL trees, which is the Splay condition (the most recently inserted or accessed node is at the root of the tree). Since Splay Trees just add one more condition to AVL trees, and the fact that Splay Trees IS-A AVL tree, then splaying should preserve tree balance according to the AVL criterion.

Q: Since find() and contains() will trigger splaying, they cannot be const methods anymore.

A: This is essentially true because since splaying modifies the tree object itself and const methods do not allow the modification of the object calling the method, it will always result in compiler errors.

Conclusion

The lab was focused discovering how Splay Trees operate, using inheritance on generics, and getting a feel of implementing an algorithm for clients (something that is done in the world of software). In short, Splay Trees are great for fast access of recently used items. The downside of Splay trees is that there will be a little more overhead in some operations due to splaying. Hope you guys enjoyed reading about Splay Trees and such. Leave a comment if you like and thank you for reading!

Lazy BST

Hello everyone,

I am bringing you another lab this week, this one working closely with binary search trees. This lab involves the implementation of two types of binary search trees; a general binary search trees and a lazy deletion binary search trees. As always feel free to leave a comment at the end and without further adieu, lets get into this.

What is a Binary Search Tree?

A binary search tree is an abstract data structure that stores items in a "sorted" format. Binary search trees are made up of nodes, with each node containing two pointers, a left child pointer and a right child pointer, and the data.

Source: GeeksforGeeks.com

Each node has an ordering condition imposed: the left sub tree of a parent node is less than the data in the parent node, while the right sub tree of a parent node is greater than the data in the parent node.

Based on the programming language you are implementing a binary search trees in, it is assumed that the data being inserted into the tree is comparable.

What makes binary search trees useful is that it allows for fast operations, such as searching, because searching through a binary search tree involves you going down either the left subtree or the right subtree over and over again, each time reducing the search space by at most half.

The Lab

The lab itself is essentially the implementation of a regular binary search tree (class name = BST) and a "lazy" binary search tree (class name = LazyBST). LazyBST is built off of BST, but with a few minor additions.

The LazyBST class utilizes a deletion technique known as "lazy deletion," which is essentially marking a node as deleted instead of going through the process of actually deleting the node and restructuring the tree. The advantage of lazy deletion is that it allows for fast deletion of nodes, but the downside is that it increases search and insert times (since the nodes marked as "deleted" are not actually gone) and wastes memory (again, because the marked nodes are not gone).

The Implementation

Starting off with BST, almost all of BST's methods will be utilizing recursion to traverse through the BST and do things like inserting nodes, deleting nodes, deleting the entire tree, etc. BST will include its own dedicated node class, which will store the pointers to the left and right children and the user data. BST's protected members include a size member, which represents the amount of nodes in the tree, and a pointer to the root node. BST also have methods such as insert(), remove(), find(), findMin(), getters, and much more; which uses recursion.

LazyBST is essentially BST, but has a few more things to take care off. LazyBST's nodes now contain a "is_deleted" flag in order to implement "lazy deletion." LazyBST itself also has a "real_size" member, which stores the real amount of nodes within LazyBST (valid and "deleted" nodes) while "size" stores the amount of valid nodes. You can essentially recycle the methods within BST, but you have to modify them to keep the lazy deletion in mind.

Lab Questions

Q: What changes will you have to make to turn LazyBST into a subclass of BST?

A: In LazyBST, we would have to have its node contain a flag of sorts to allow for lazy deletion and implement another "size" member that tells us the actually number of nodes within a LazyBST object. The methods inherited from BST will need to be overloaded in LazyBST such that it not only checks for null pointers, but also checks for marked nodes. To deallocate some memory after marking many nodes as "deleted," we would also require a garbage collection system of sorts.

Q: What is the tradeoff in using LazyBST? What are you trying to minimize?

A: With LazyBST, we are trying to minimize the time for deleting nodes within the tree, but we end up having to increasing the amount of time it takes to find nodes, insert nodes, and also waste memory.

Q: Does Laziness help change the Big-O of any of the other common operations?

A: I would say laziness does not really help change the Big-O of other common operations, since most operations involves "splitting" the tree in half in each iteration, resulting in a worst case O(log N).

Q: BST<T>::find() returns a reference to the payload. But remember you need to pass it the payload in order to find() it. Why do you need to invoke find() on the tree if you already have the payload in your hands?

A: Looking into this, I believe the reason why we need to invoke find on the tree, even if we already have what we want, is because we want to change something about the element that is stored within the tree itself. The payload we have in our hands may contain the bare minimum to find the data we want to change that is stored in the tree itself (I believe this occurs with pairs within C++ STL).

Conclusion

Overall, this lab is mainly about implementing the binary search tree abstract data type. Most of the methods within both BST and LazyBST involves the use of recursion. The methods themselves usually have a worst case runtime of O(log N) since some operations involves splitting the tree in half in each iteration. LazyBST is essentially BST, but requires a "deleted" flag in each of its nodes and the methods need to be modified to handle the situation where it lands on a "deleted" node.

That is pretty much all for this week. As always please leave a comment and thank you for reading!

Multiplying Sparse Matrices

Hello everyone,

This week we will be building upon last week's Sparse Matrix lab with the Multiplying Sparse Matrices lab. As the name implies, this week's lab will be about multiplying two sparse matrices. As always feel free to leave a comment that is related to this week's lab and lets get right into this lab.

The Lab

Continuing on from the Sparse Matrices lab, we create two new classes that inherit from Matrix and SparseMatrix called MatrixWithMult and SparseMatrixWithMult. In each of these classes, we define a multiple() method that takes in two matrices. In MatrixWithMult::multiply(), we implement the slow, naive solutions, while in SparseMatrixWithMult::multiply(), we implement a more optimized solution.

The Implementation

In SparseMatrixWithMult::multiply(), we need to implement a solution that takes advantage of what we know about matrix multiplication and the sparse matrices themselves. Starting off with the sparse matrices themselves, we need to avoid utilizing SparseMatrix::get() because it takes time to traverse the given SparseMatrix and return something. Since our SparseMatrix class stores the data internally using an array of linked lists, we can just retrieve the list from a given row and traverse it instead of using get().

However, traversing a list is not enough to quickly multiply sparse matrices. This is where we start exploiting what we know about matrix multiplication. Matrix multiplication is essentially the dot product of a given row in one matrix and a given column in the other matrix. Dot product is founded by summing the products of the corresponding terms, meaning if one of the terms is 0, the product will be 0. With this in mind, we can use this to make our algorithm faster by skipping rows of empty values and skipping multiplication operations that we know will result in 0.

A summary of the optimizations are as followed:

• Traverse the linked-lists in a designated row instead of using the get() method.
• Skip rows that are entirely empty (which means the value is 0)
• Skip multiplication if the value in a given column is 0.

Lab Questions

Q: Compare your Matrix's multiply() and SparseMatrix's multiply() methods. Is there a relation between the number of elements and the time taken to multiply()?

A: If we multiply two matrices of 500 x 500, the Matrix's multiply() will take longer since it will process each element in the two matrices. SparseMatrix's multiply(), however, will be faster since it will ignore elements that are considered to be default values (or 0 in some cases).

Q: What is the effect of the EDD (effective data density) on the time taken to multiply two sparse matrices? What about the non-sparse matrices?

A: As the number of non-default values becomes closer to the total number of values, the time it takes to multiply two sparse matrices would probably end up taking the same amount of time it takes to multiply a non-sparse matrix, since the more non-default values we have in a sparse matrix, the closer SparseMatrixWithMult::multiply() will behave as Matrix::multiply()

Q: Does it make sense to keep the lists sorted by column number?

A: It is not practical to keep the lists sorted by column number if your are iterating through them within multiply() since dot product is the sum of the products of the corresponding terms, meaning you can multiply the pair of terms in any order. 

Q: Does it matter if the lists have duplicate cells (i.e. same column number)?

A: I would not say that having duplicate cells will do much in the sense of multiplying sparse matrices. It would still undergo the same process as if it was not a duplicate cell, so nothing special would happen.

Q: There is significant scope for further optimization. Discuss such ideas.

A: Besides the ones that I have just mentioned, there was one algorithm I read about (the Strassen algorithm) that would split up the matrix into smaller parts and do the multiplication operations on them.

Conclusion

Overall, the multiplying sparse matrices lab is all about limiting the number of times we need to access a sparse matrix and exploiting the rules of matrix multiplication. There are some algorithms out there that provide faster matrix multiplication than the one I was explaining here, but utilizes advance ideas out of my scope. Thank you for reading and feel free to leave a comment.

Sparse Matrices

Hello everyone,

This week I am bringing you another discussion of a recent lab I was doing for CS class. This week I will be discussing about Sparse Matrices. As always, feel free to leave a comment on any questions you may have and and conceptual mistakes I may have made while writing this post.

What is a Sparse Matrix?

A sparse matrix is essentially a matrix with most of its elements being zero. An example would be that I have a 500 by 500 matrix to store integer values, but I only use about 100 spots out of the possible 250000. A sparse matrix in a computer program is looked down upon because we are wasting a lot of memory on a few values. There are some ways to lower the amount of memory used on sparse matrices, with one involving the use of arrays and linked lists.

An Ideal Implementation for Matrices

Since the lab I was doing was for a C++ course, I will be referring to the vector data type in the C++ Standard Template Library (STL). I will also be referring to the list data type in C++ STL as it is a linked list implementation.

Starting off, a typical matrix would be stored in a two-dimensional array. What is beneficial about this implementation is that it allows for quick, random access to elements within the matrix. The downside is that if the matrix is sparse, we are wasting memory.

In the implementation I will be discussing about, we will be utilizing an array and a linked list. The array will be initialized to be an array of linked lists, meaning each element within the array represents a row in the matrix. The linked lists will represent the columns, whose nodes will contain the column number and the data value being stored.

The idea behind this implementation is that we are only spending memory on a one-dimensional array. From there, our linked list will contain nodes for data values that are nonzero (or if you are doing a template approach, not a default value). If the linked list for a given row does not contain a node with a given column number, it is the equivalent of saying there is a zero at the given (row, column) coordinates.

The downside of this implementation is that access speed to elements is a bit slow, because even if we are given coordinates, we need to traverse the linked list at a given row searching for the given column value. But this implementation does save memory in the end.

Questions Given in the Lab

Just like the last post, this lab includes a few questions regarding to the kinds of things we can do in software to save memory:
Q: What is the trade-off of using software to give save resources instead of using better hardware?
A: If we utilize algorithms and software to save on the amount of resources used computers, I would say that we will be trading off speed for resource efficiency. I believe this is being done with zip files, where the software needs time to compress and package given files and uncompressed them when unzipped.

Q: vector::at() returns a reference that you can use as both an rvalue (RHS of assignment) as well as an lvalue. Is it possible to implement such an accessor for SparseMatrices (the class I was implementing)?
A: I would say it is possible to implement such an accessor for SparseMatrices. If vector::at() is returning the reference of an object and it is being called on the right-hand side of an assignment, then we are just assigning that object to another one. If we want our SparseMatrices accessor be used on the left-hand side of an assignment, the objects SparseMatrices contains need to have an overloaded assignment operator.

Q: In C++ two different functions cannot differ in their return types only. Discuss why you think this restriction exists in the language standard.
A: I believe this restriction exists in the language standard because of ambiguity. If we have two functions with the same name, amount of parameters, but different return type, how can it tell which return type to use.

Q: Does it make sense to keep your lists sorted?
A: If the nodes within a linked list were sorted such that columns on the left-most side appear first, then it would provide faster access time in the ideal case, since it will not have to search to far for a certain column number. However, in the worst case it may still require a traversal through the entire list.

Conclusion

This lab is a pretty interesting lab since we get to see how we can use simple techniques to effectively save on that sweet precious memory. Although there are probably more methods of implementing an efficient matrix, the implementation is considered to be a pretty simple one. I hope you enjoy this post. As mentioned before, feel free to leave a comment on anything relevant to the material presented here, questions, and mistakes that I have made when writing this post so I can fix them.

Thank you so much for reading!