CST 370 - Module 6

 Week 6,

This week's module covered more material on tree structures. We previously talked about binary search trees, however, a problem with that is that it can become unbalanced, making the operation take linear time. To solve this problem, we just make sure we keep the binary search tree balanced. To do this, we make use of an AVL Tree, where we keep track of the levels below each node. In short, (and probably with lack of detail) we keep the number of children to each node equal from one side to the other as much as possible, within a difference of 1. If any of the nodes are unbalanced, we rotate the node with the first violation with its children, either left or right.

Another way of keeping a tree balanced is by using a 2-3 tree. Using a 2-3 tree is different from your usual tree as each node can contain either 1 or 2 values, and either 2 or 3 children. You insert values in a binary fashion. However, if you insert a third value into a node, the value between moves to the parent node. The result of the 2-3 tree has all leaf nodes on the same level.

The next data structure that was introduced was the Max Heap. The max heap is a complete binary tree, where every level, except possible the last is completely filled, and all nodes in the last level are as far left as possible. In addition, for a max heap, the number of each node is greater than or equal to the numbers of its children. When inserting a number to the max heap, you insert the value to the left most leaf. Next, you compare its number with its parent. We want the parent to be larger than the child. So, if necessary, we swap the nodes. The swap keeps chaining if necessary. There are other operations discussed, however, that will be left for you to research.

Hashing and using a Hash Table is the final bit of material covered for the week. This is an interesting way of keeping data, as accessing a value can be done in constant time O (1). To access or insert an item, you use a hashing function to determine where in the table the value goes to. In our case, we used the value mod table size, where the table size is a prime number. However, because we are using the modulo operation, there can be scenarios where two different values can be assigned the same index, causing a collision. To solve this issue, we have two solutions. One solution is using separate chaining, where the hash table is made using linked lists, so if there is a collision, we simply have the value already located in the index, point to the value with the same index. The other solution is linear probing, where the hash table is made using an array, however, instead of assigning to values in the same index, we simply insert the conflicting value to the next free index.

Comments

Post a Comment

Popular posts from this blog

CST 338 - Module 4

 This week in CST 338, there were few assignments to complete. This time we got to get our hands on Android Studio, where we created very simple app where android users can convert temperature °c to temperature °f, or vice versa. We also got to complete our first project, where we practiced inheritance using an abstract class, and concrete classes. However, besides that, we were also allowed to go back to our previous assignment, Markov, and have our teammates review each other's code. I worked with my teammate Ryan Matsuo  and after reviewing his code, I learned a few things that could help me in the future, like splitting a string using str.split() with a regex of "\\s+" instead of what I did which was more complicated. My strategy with solving the Markov assignment was that I started writing the code right away. I didn't put anything to practice into paper because I feel I can do the same thing in the code. I would read the prompt, create stubs for the methods to b...
Read more

CST 363 - Module 7

 Week 7! This week involved involves us using a NoSQL database called MongoDB. After using both MySQL and MongoDB and the instructions that came with it, I can certainly say that there are a few differences between MySQL and MongoDB.  For instance, MongoDB is not relational, whereas SQL is. Mongo and SQL use different query languages. And Mongo doesn't use transactions but SQL does. Some similarities however, include both SQL and Mongo supporting things like query projection, unique keys, and indexes. One thing that is strengthened on Mongo, is replication, which increases reliability which can be useful when an error occurs. When it comes to my preferred choice of the two databases, it depends. MySQL's language is more human based or easier to read, but it doesn't make it easier to find very specific data from multiple schemas. However, if you are already familiar with coding in JavaScript, or coding in general, then MongoDB can be strong choice as it is easier to support ...
Read more

CST 363 Module - 1

 CST 363! This is the start of the next course in CSUMB's Computer Science Online program. It is an introduction to databases using SQL. Thankfully due to the previous course in software design, I had a small introduction to using databases.  I have also come to understand the more distinct difference between relational databases and spreadsheets. One major difference is the fact that databases are more useful for working with large amounts of data, working with other tables of data, and can perform queries faster. Reasons as to why this is important, or beneficial compared to using spreadsheets or writing into a file is more related in how you use it. For instance, instead of looking through a large portion of data to find a small number of rows, you have the option to search through a subset of data, making tasks much easier to complete. Databases can also have additional security, only allowing certain data to be seen by different programs. Especially if you have multiple p...
Read more