Differences

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

--- courses:cs211:winter2018:journals:thetfordt:chapter2 [2018/01/28 18:44] – thetfordt
+++ courses:cs211:winter2018:journals:thetfordt:chapter2 [2018/01/29 20:32] (current) – thetfordt
@@ Line 29: / Line 29: @@
 The text then offers a taste of quadratic runtime, citing examples such as finding the largest distance between (x,y) coordinates and the commonality of finding this in the case of nested loops.
-The next few sections: cubic, O(n^k), and "Beyond Polynomial Time" were slightly less straight-forward. It took a little more time to digest these ideas, as we did not cover them as extensively in class. And the author ends with sublinear time, a refreshing conclusion as a easy-to-understand idea. I would rate the readability of this section as 6/10 - I found it very dense at times.
+The next few sections: cubic, O(n^k), and "Beyond Polynomial Time" were slightly less straight-forward. It took a little more time to digest these ideas, as we did not cover them as extensively in class. And the author ends with sublinear time, a refreshing conclusion as an easy-to-understand idea. I would rate the readability of this section as 6/10 - I found it very dense at times.
+===== Section 2.4 - A More Complex Data Structure: Priority Queues =====
+Again, the author begins by laying out the goals for the section - which I truly appreciate as the reader. And here, the goal is to lay out a widely used data structure, one that can achieve superior runtime by capitalizing on implementation details.
+The author then walks through the problem: that we want to be able to add, delete, and select elements quickly when an algorithm calls for it. The author then walks through exactly what a priority queue is and shows that, by using one, a linear sequence of priority queue operations can be used to sort n numbers.
+We then dive into heaps, as a data structure used to implement priority queues, which turns out to be extraordinarily similar to a binary search tree represented as an array. The author then walks through the heap operations, such as adding, deleting, and the respective algorithms necessary to implement these operations: Heapify-Down and Heapify-Up.
+The Heapify-Up algorithm runs in O(log n) time. This algorithm adds an element to the end of a heap, determines if the element needs to be switched with its parent and if so, executes this swap and uses a recursive call.
+The Heapify-Down algorithm also runs in O(log n) time. This algorithm is used to delete an element from a heap while also maintaining the structure of the heap. It deletes the element at a position i, and then promptly places the element at the end of the heap in the deleted position. It then takes this new swapped element, determines which of its children (if it has children) is lower, and swaps with that child. After this, it just executes a recursive call, ultimately resulting in a deleted element and a proper heap structure.
+We covered both of these in class, and after reading the section, I feel that I have a very strong understanding the logic and runtime of each of them. The author then concludes the section by walking through the five primary operations surrounding heaps implementing priority queues: StartHeap, Insert, FindMin, Delete, and ExtractMin, citing the runtimes for each using the details from earlier in the section.
+I would rate the readability of this section at 9/10. It flowed nicely and was a nice refresher from what we covered in class.