CST 370: Week 7

This week we learned two new sorting techniques, counting sort and radix sort, both of which sort a set of inputted values without needing to compare them to one another. The counting sort finds the frequency of each value within the set then determines how they must be distributed by calculating the accumulation of the frequencies from the lowest end of the range to the highest end. Instead of evaluating each value as a whole, the radix sort involves looking at the individual digits of each value and distributes them based on a range of 0 to 9, repeating the process until each value has been distributed from their least significant digit (LSD) to their first (or leading) digit. We also learned about dynamic programming, which is where we can save computations when solving a problem that involves recalculating it's subproblems multiple times by saving the solutions to those subproblems in an array that can be referred to later rather than recalculating. We learned to apply this technique to graphs using Warshall's algorithm, which computes the transitive closure of a graph, and Floyd's algorithm, which finds the shortest path between all pairs of vertices. Lastly, we learned about the greedy technique, which makes locally optimal choices throughout various steps without changing those choices to potential reach the overall most optimal result. We used Prim's algorithm to view this in practice which grows a tree based on the cheapest available edge.

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