CST 370: Week 6

 This week we learned about two more trees: AVL and 2-3, as well as about heaps and hashing. AVL trees are balanced binary search trees that have a difference between the left and right subtrees of -1, 0, or 1. This difference is referred to as the balance factor (or balancing factor) and is specifically defined by the height of the left subtree minus the height of the right subtree. 2-3 trees on the other hand have subtrees with the same height and each node can have one or two values, where most other trees we've worked with have only one value per node. Heaps are complete binary trees, which consist of every level but the last needing to be completely filled and the last level orienting the existing nodes as far to the left as possible. Heaps are also defined by how the parent nodes relate to the child nodes, where each node in max heaps are greater than or equal to the numbers of its children and each node in min heaps are less than or equal to the numbers of its children. We learned to apply a couple of operations to max heaps and how to use arrays to store the values of a heap and how to use the HeapBottomUp algorithm to construct them. Lastly. we learned about hashing, which consists of creating functions that map variables of a larger set of numbers to a smaller fixed set of values. We also learned how to handle collisions, which consists of two variables with the same fixed hash value, by applying linear probing or separate chaining and how to decide or adjust the hash function by determining the load factor. 

Comments

Post a Comment

Popular posts from this blog

CST 334: Week 4

  Write a 1 - 2 paragraph journal post, of at least 250 words, of what you learned this week in CST 334. As an alternative to base-and-bounds, we learned this week that we can implement a technique called paging. This technique breaks virtual address space up into sections of equal size. In comparison to base-and-bounds, paging is simpler to implement and much more flexible in use and it allows us to avoid fragmentation. On the downside, paging needs larger data structures for translation, so more space is used, and translation info does not fit into the MMU registers, which makes paging slower than using base-and-bounds.  Each process will have a page table, which logs a page frame number, or PFN, that corresponds with a virtual page number, or VPN. Virtual addresses are made up of the VPN and then what is referred to as the offset. During address translation, we retrieve the PFN using the VPN in the page table and replace the VPN in the virtual address with the PFN, and we e...
Read more

Week 4 Learning Journal Post

Part 1: Educational Goals A goal I am working to achieve within this or next term is to finish an O'Rilley online course on the basics and fundamentals of Python programming. I will then be working on a similar course that pertains to Java programming. Simultaneously to these courses, I have a goal of creating an online study hour with those within our cohort. Two long-term goals I have are to obtain my bachelor's degree in computer science and to graduate with honors. After obtaining my bachelor's degree, I plan to then go for my master's so I can teach at a college level if I choose later on in my career. Part 2: Career Goals A goal I have for my career is to obtain at least two professional certifications before I graduate my bachelor's degree program, CompTIA Security+ and Cisco Certified Network Associate. Additionally, I have a goal of securing a cybersecurity internship with a local company before I graduate. Once I have gained enough experience and obtained ...
Read more

CST 363: Week 5

  If indexes are supposed to speed up performance of query,  what does the author mean by a slow index?  The author indicates that a slow index occurs when a query performs slower than expected despite using an index. To ensure a query has found all entries matching the search criteria, the database will need to read all the nodes within the final chain, which will consist of a large number of operations and slow the process. In addition to the database's need to read all the nodes within the chain, the database will also need to read data from different table blocks, which will only slow the process even more. The author specifies that though a slow index can consist of slower than normal queries, it doesn't necessarily mean the index is broken or useless. 
Read more