CST370 - Week 6

CST370 Week 6

This week, we learned more about tree balancing and hashing.

    AVL trees are self-balancing binary search trees where the balancing factor of each node is either 1 (left), 0, or -1 (right). The balancing factor is calculated by how many 'edges' traveled from the node to the last leaf it can reach (or the height of the subtree):
Balancing factor = height of left subtree - height of right subtree
    To maintain AVL trees, rotations may need to be made on nodes. For left-heavy trees (or subtrees), R-rotations are typically used, while right-heavy trees (or subtrees) use L-rotations. Rotations can be used multiple times in a row, like two R-rotations needed.

    2-3 trees are binary search trees that must have at least 2 or 3 children to each node. Each node can contain one value or two values - if it has one value, it will have 2 children, and if it has two values, it will have 3 children. The children can contain one or two values regardless of the parent. It is also height-balanced where all leaves are at the same level. 

    Heaps are complete binary trees (all levels besides the last level must be filled). There are two variations: min heap has the smallest value as its root node, and each subtree node must be smaller than its children. Max heap has the largest value as its root node, and each subtree node must be larger than its children. In heaps, the children do not necessarily need to be sorted.

    Hashing is the process of taking a value, hashing it against an algorithm, and then placing it in a hash table using the generated hash. We can store and retrieved hashed data from the table using that algorithm. A big issue hashing can run into is collisions, where different entries are given the same hash (leading to the same index in the hash table) through the algorithm. We can handle collisions by either creating a linked list of all entries with the same hash (chaining), or by finding the next open slot in the hash table for the entry (linear probing). To maintain an optimal time complexity in hash tables, we use a load factor: 
Load factor = (number of current entries) / (number of total slots in the hash table).
    The optimal hash table size is a prime number. We maintain this load factor by resizing the table to twice its size, then find the next largest prime number. Then, we rehash the values if needed to maintain the hash table (usually for situations where the size of the table is used in the hash algorithm).

Isopod Update: They are in a new room currently so I have to monitor over time if anything's different.

Comments

Post a Comment

Popular posts from this blog

CST300 - Week 4

Week 4 has been busy! I have gotten work done a lot later than I would have liked. Part 1: Education Goals My educational goals would be to expand my knowledge about Javascript. The most tangible project to put this in practice would be to create a simple interactable website, possibly using React as a frontend. One of my ideas for a capstone project would be to create a website for a tabletop game I am developing, so the practice would be great for it.   The first step would be to learn about networking -- CST311: Intro to Computer Networking and CST336: Internet Programming would be where I hone these skills. Before these classes, I would like to create a single-task web app as a practice. It would have a starting list of about 20 items, and allow the user to arrange them into 6 specific item slots, like a digital pin board. Then, once I am in these classes, I will look back at this project and see what I can do differently or what I have learned since then.   My web develop...
Read more

CST334 - Week 6

Week 6 Reflection This week, we learned more about semaphores, and the bugs that are commonly faced in concurrency, such as deadlocks.  Semaphores are a synchronization primitive that has a modifiable integer value. The behavior of the semaphore is determined by this value. They can be used as both locks and condition variables for concurrency.  sem_wait() and sem_post() are used to interact with a semaphore. sem_wait() waits for a condition to be met, while sem_post() increments the value of the semaphore, then wakes a waiting thread. If a semaphore's value is negative, this number is equal to the number of waiting threads. For example, -4 equals four waiting threads, incrementing by 1 will change it to -3, waking one thread and now resulting in three waiting threads. Concurrency creates bugs that are difficult or costly to fix correctly. Non-deadlock bugs include atomicity violations and order violations. Atomicity violations occur when instructions that sho...
Read more

CST334 - Week 5

Week 5 Reflection      In this week, I learned a great deal about concurrency, threads, and best practices on how to keep threads managed efficiently. A thread is seen as a process that can share the same address space as another thread, and access the same data, rather than needing to occupy a different address space. Multi-threading is handling multiple threads in the same address space using thread control blocks (TCBs) to store thread states. For multi-threaded processes, each thread has its own stack, called the thread-local storage.       In the aside, four key terms are highlighted:  critical section: Code that accesses a shared resource, like a data structure or variable.  race condition (aka data race): If multiple threads enter the critical section at the same time, a race condition occurs. These threads could be executed in any order, leading to the program becoming indeterminate. indeterminate program: A program with one or more r...
Read more