Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:cantrella:chapter_2 [2018/01/28 20:29] – cantrella
+++ courses:cs211:winter2018:journals:cantrella:chapter_2 [2018/01/29 00:32] (current) – [Section 2.5] cantrella
@@ Line 23: / Line 23: @@
 I would say this chapter was 6 on an interesting scale (seeing as we had already discussed it), but an 8 on the readability scale. Breaking each function down by how it was implemented made a lot of sense to me. While we did do the same thing in class, it was a bit harder to follow simply because erroneous answers kept being proposed which threw me off a little bit.
 ===== Section 2.4 =====
+Section 2.4 describes the most commonly found algorithmic run-times, which include; O(//n//, O(//n//^//k//) , O(//n//log//n//), O(log//n//). It also discusses some of the largest run-time found, which are O(2^//n//) and O(//n//!). For all of the runtimes, example problems were given and most had examples of the actual algorithms themselves. While I have seen most of the runtimes before, it was good to reinforce my knowledge of them after our in-class discussion.
+The one algorithm runtime I have always struggled with the most has been O(//n//log//n//). Reading this chapter helped me garner a much better understanding of why this seemingly strange runtime arises so often and how it is implemented in different settings.
+I would give this section a 6 on the interesting scale and an 8 on the readability scale.
+===== Section 2.5 =====
+Section 2.5 introduces the first truly complex data structure, the priority queue. A priority queue is container type that organizes elements based on their size. When values are pulled from the queue, they are taken based on their priority. Lower values have a higher priority. The actual data structure that implements said priority queue is called a heap. A heap can be visualized as a kind of binary array, in which every node has one parent and two children, and the parent node is always greater than both child nodes.
+The advantages of a heap are that it can add and remove elements in O(log//n//) time, making it more efficient than both lists and arrays. It does this by utilizing the heapify-up and heapify-down functions, both of which we covered in class.
+This chapter helped to reinforce my understanding of priority queues and their heap-like implementation. I am curious if a priorit queue could be implemented using a different kind of data structure.
+I give this chapter a 7 on the interesting scale and 7 on the readability scale.