Differences

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

--- courses:cs211:winter2011:journals:david:chapter2 [2011/01/25 20:25] – [2.3 - Implementing the Stable Matching Algorithm Using Lists and Arrays] margoliesd
+++ courses:cs211:winter2011:journals:david:chapter2 [2011/01/25 20:53] (current) – [2.5 - A More Complex Data Structure: Priority Queues] margoliesd
@@ Line 15: / Line 15: @@
 ====2.4 - A Survey of Common Running Times====
-The search space contains all possible solutions to a problem and a brute force search simply looks through all of these solutions to find the one that matches the problem's requirements. We try to use algorithms that are more efficient that a brute force search. The merging of two sorted lists into a final sorted list is O(N). Sorting problems are often O(N*LogN). Quadratic time algorithms are often the result of nested loops, and cubic time algorithms are similar but have another loop. If we call the number of loops "k" then we get algorithms with O(N<sup>k</sup>). For example, if we look for all subsets of size "k" in a set it would be O(N<sup>k</sup>). If instead of looking for a set of size "k" we are looking for the largest independent set, the algorithm becomes O(N<sup>2</sup>2<sup>N</sup). Algorithms that take less than O(N) time but more than constant time can arise when we have a set of input that does not all need to be read.
+The search space contains all possible solutions to a problem and a brute force search simply looks through all of these solutions to find the one that matches the problem's requirements. We try to use algorithms that are more efficient that a brute force search. The merging of two sorted lists into a final sorted list is O(N). Sorting problems are often O(N*LogN). Quadratic time algorithms are often the result of nested loops, and cubic time algorithms are similar but have another loop. If we call the number of loops "k" then we get algorithms with O(N<sup>k</sup>). For example, if we look for all subsets of size "k" in a set it would be O(N<sup>k</sup>). If instead of looking for a set of size "k" we are looking for the largest independent set, the algorithm becomes O(N<sup>2</sup>2<sup>N</sup>). Algorithms that take less than O(N) time but more than constant time can arise when we have a set of input that does not all need to be read.
 I give this section a readability of 5/10.
+====2.5 - A More Complex Data Structure: Priority Queues====
+An efficient algorithm can be improved by using a different kind of data structure. In a priority queue, all elements have an associated key or value, and the lower the value, the higher the priority. Operating systems use priority queues to determine which process gets to use the CPU. In a priority queue, an element can be added, deleted, and the highest priority item can be selected in O(logN) time. Priority queues can be implemented using a heap, which is visually like a "balanced" binary tree, but stored in memory as an array. The key/value of every element is be at least as large (higher priority) as its parent. A node's at array position i has its left child at array position 2i and right child at 2i+1. Adding a new element to the heap is O(logN) because we must Heapify-up the element after adding it to the end of the array. This implies we keep track of the number of elements in our heap, or we would need to iterate through the array every time. The highest priority item is simply the first element in the array, but to remove it, we need to fill in its gap with the last element in the array. Then we Heapify-down this element to maintain the heap, which takes O(logN) time.
+I give this section a readability of 7/10.