Differences

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

--- courses:cs211:winter2018:journals:thetfordt:chapter2 [2018/01/21 18:26] – thetfordt
+++ courses:cs211:winter2018:journals:thetfordt:chapter2 [2018/01/29 20:32] (current) – thetfordt
@@ Line 19: / Line 19: @@
 I found this section very straightforward, and because I was a little sick in class on Friday, I found some of the material from class difficult to follow. But after reading the section, I feel much more comfortable with exactly how and why we made the choices to use specific data structures. I also like the way that the author counters the problem encountered in (4.) on pages 46-47. I thought it was a clever solution to a confusing problem. In terms of further curiosity, I would have liked to see a note from the author on other data structure implementations (if there are any) for the algorithm. For instance, in class, my row discussed using a linked list to maintain the men's preference - allowing a simple chaining operation to figure out who the man should propose to next. Either way, I would rate the readability of this section at 10/10.
+===== Section 2.4 - A Survey of Common Running Times =====
+The section begins by laying out what is to be described up ahead: a walkthrough of common runtime bounds and some of the approaches which lead to them. I found it helpful that the author walked through the two different ways to approach runtime bounds: the bound which we would hope to achieve, and then the runtime of the brute-force search. It helps to conceptualize these problems and their respective runtimes.
+The author begins with the most understandable runtime: linear. This section was very clear, demonstrating linear examples in both finding the maximum of a list and merging two sorted lists. From here, the text moves on to O(n log n) runtime. I found the conceptual basis for when this occurs very helpful: "any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time."
+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 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.