CST 370: Week 5

 This week we learned about the quicksort algorithm, binary tree traversal, and decrease and conquer algorithms. The quicksort algorithm uses the divide and conquer approach like merge sort, but partitions based on a particular value referred to as the pivot. The pivot is typically the first element within a given array, but sometimes we apply the median of three rule instead, which involves comparing and sorting the order of the first, middle, and last elements with the array and selecting the middle one as the pivot. As for binary tree traversal, we learned the three order variations using for moving through a tree (preorder, inorder, and postorder) and how to determine a tree's height (the length of the longest path from the root to the leaf node in the tree). In terms of decrease and conquer, the technique is based on the idea that smaller problems are solved more easily and we learned there are three variations: decrease by a constant, decrease by a constant factor, and variable size decrease. We also learned how to apply these variations in techniques such as binary search, which searches for a value within an array but checking the array's middle value and deciding whether or not we need to look further in the half before that value or after it, and topological sorting, which defines an order of dependency for vertices within a directed acyclic graph, or DAG. 

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