Differences

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

--- courses:cs211:winter2014:journals:deirdre:chapter2 [2014/01/21 23:32] – [Section 2.3 -] tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter2 [2014/01/22 04:03] (current) – [Section 2.4 - A Survey of Common Running Times] tobind
@@ Line 48: / Line 48: @@
 ====== Section 2.3 -  ======
+(Study note: Just look at slides for arrays and lists.)
 We need to consider each step of the algorithm and understand what data structure allows us to implement it efficiently. Essentially, we need to be able to each of four things in constant time.
-  - We need to be able to idenntify a free man.
+  - We need to be able to identify a free man.
   - We need, for a man //m// to be able to identify the highest-ranked woman to whom he has not yet proposed.
   - For a woman //w//, we need to decide if //w// is currently engaged, and if she is, we need to identify her current partner.
   - For a woman //w// and two men //m// and //m'//, we need to be able to decide, again in constant time, which of //m// or //m'// is preferred by //w//.
+First, we will select a free man from the set of free men represented by a linked list. We take the first man off of the list and delete him from the list if he gets engaged. If another man //m'// becomes free, we can insert him at the front of the list. This is all constant time.
+Then, consider a man //m//. We need to find the highest-ranked woman on his pref list to whom he has not already proposed to. We can use an array to represent the woman he will propose to in order. Starting at the first position, we will increase the index each time he proposes to a woman, whether or not she accepts his proposal.
+Next, we need to have an array that keeps track of a woman //w//'s current partner, //m'//. If a woman is not engaged, we use a special null symbol. These first three steps can all be done in //O(1)//.
+The trickiest part is maintaining women's preferences to keep the fourth step efficient. Consider a step where man //m// proposes to a woman //w//. Assume //w// is already engaged and her current partner is //m'//. We need to decide whether //w// prefers //m// or //m'//. We can do this by creating a //n// x //n// array that contains the rank of man //m// in the sorted order of //w//'s preferences. WE can create this array in linear time, for a total initial time investment proportional to //n//^2. Then we simply have to compare the values. This allows us to do the 4th step in constant time.
+All of the above data structures allow us to implement the GS algorithm in //O(n^2)//.
+I thought this section was interesting (9) and made a lot of sense when combined with lecture.
 ====== Section 2.4 - A Survey of Common Running Times ======
 **Linear Time**
@@ Line 70: / Line 79: @@
 There are cases where one encounters running times that are asymptotically smaller than linear. Since it takes linear time just to read the input, these situations tend to arise in a model of computation where the input can be "queried' indirectly rather than read completely and the goal is to minimize the amount of querying that must be done. Example, binary search algorithm -> running time of //O(log n)//.
+I give this section a 8.5.
+====== Section 2.5 - A More Complex Data Structure: Priority Queues ======
+**The Problem**
+For the Stable Matching algorithm, we want to be able to easily add and delete elements from a set //S// and to be able to select an element when the algorithm calls for it. A priority queue is designed for applications in which elements have a priority value, or key, and each time we need to select an element from //S//, we want to take the one with highest priority.
+A priority queue is a data structure tha maintains a set of elements //S//, where each element //v∈S// has an associated value key(//v//) that denotes the priority of element //v//; smaller keys represent higher priorities. Priority queues support the addition and deletion of elements from the set, and also the selection of the element with smallest key. A motivating application for priority queues and one that is useful to keep in mind when considering their general function is the problem of managing real-time events. Each process has a priority or urgency but processes do not arrive in order of their priority. This allows us to both select the element with minimum key while inserting new processes as they arrive.
+We will show how to implement a pq containing at most //n// elements at any time so that elements can be added and delted and the element with minimum key selected, in //O//(log //n//) time per operation.
+- A sequence of //O(n)// pq operations can be used to sort a set of //n// numbers. -> With a pq that can perform insertion and the extraction of minima in //O//(log //n//) per operation, we can sort //n// numbers in //O//(//n//log //n//).
+**A Data Structure for Implementing a PQ**
+We will use a data structure called a heap to implement a pq.  The heap data structure combines the benefits of a sorted array and list for purposes of this application. Conceptually, we think of a heap as a balanced binary tree, with a root and where each node can have up to two children, a left and a right child. The keys in such a binary tree are said to be in heap order if the key of any element is at least as large as the key of the element at its parent node in the tree. In other words,
+       Heap order: For every element v, at a node i, the element w at i's parent satisfies key(w) ≤ key(v).
+Before we discuss how to work with a heap, we need to consider what data structure should be used to represent it. We can use pointers: each node at the heap could keep the element it stores, its key and three pointers pointing to the two children and the parent of the heap node. We can avoid using pointers, however, if a bound //N// is known in advance on the total number of elements that will ever be in the heap at any one time. Such heaps can be maintained in an array //H// indexed by //i// = 1,...,//N//. We will think of the heap nodes as corresponding to the positions in this array. //H//[1] is the root, and for any node at position //i//, the children are the nodes at positions leftChild(//i//) = 2//i// and rightChild(//i//) = 2//i// + 1. The parent of a node at position //i// is at position parent(//i//) = [//i///2]. If the heap has //n// < //N// elements at some time, we will use the first //n// positions of the array to store the //n// heap elements and use length(//H//) to denote the number of elements in //H//. This representation keeps the heap balanced at all times.
+**Implementing the Heap Operations**
+The heap element with smallest key is at the root, so it takes //O(1)// time to identify the minimal element.
+Consider adding a new heap element //v// and assume that our heap  //H// has //n < N// elements so far. We can add the new element //v// to the final position //i = n + 1// by setting H[//i//] = //v//. Unfortunately, this does not maintain the heat property because the key of element //v// may be smaller than the key of its parent. We will use the procedure Heapify-Up to fix our heap. We will call the process recursively until the heap is fixed.
+     Heapify-up(H, i):
+        If i > 1 then
+            let j = parent(i) = (i/2)
+            If key[H[i]] < key[H[j]] then
+                 swap the array entries H[i] and H[j]
+                 Heapify-up(H, j)
+            Endif
+        Endif
+To see why ^that works and eventually fixes the heap, let's look more fully at the not-fixed heap. Assume that //H// is an array and //v// is the element in position //i//. We say that "H is almost a heap with the key of //H[i]// too small" if there is a value α ≥ key(//v//) such that raising the value of key(//v//) to α would make the resulting array satisfy the heap property.
+-Heapify-up(//H, i//) fixes the heap property in //O//(log //i//) time. Using heapify we can insert a new element in a heap of //n// elements in //O(//log //n//) time.
+Consider deleting an element. After deleting an element at position //i//, there will be a "hole" at position //i//. So, as a patch, we move element //w// to position //i//. However, this probably isn't where //w// goes and violates the heap property...So, we run Heapify-down.
+     Heapify-down(H, i):
+         Let n = length(H)
+         If 2i > n then
+             Terminate with H unchanged
+         Else if 2i < n then
+             Let left = 2i and right = 2i + 1
+             Let j be the index that minimizes key[H[left]] and key[H[right]]
+         Else if 2i = n then
+             Let j = 2i
+         Endif
+         If key[H[j]] < key[H[i]] then
+             swap the array entries H[i] and H[j]
+             Heapify-down(H,j)
+         Endif
+Assume that //H// is an array and //w// is the element in postion //i//. We say that "H is almost a heap with the key of //H[i]// too big", if there is a value α ≤ key(//w//) such that lowering the value of key(//w//) to α would make the resulting array satisfy the heap property.
+- The procedure Heapifydown(//H,i//) fixes the heap property in //O//(log //n//) time, assuming that //H// is almost a heap with the key value of //H[i]// too big. Using Heapify-up or Heapify-down, we can delete a new element in a heap of //n// elements in //O//(log //n//) time.
+**Implementing PQs with Heaps**
+The heap data structure with the Heapify-down and Heapify-up operations can efficiently implement a pq that is constrained to hold at most //N// elements at any point in time. Here is a summary of operations we will use:
+  * StartHeap(//N//) returns an empty heap //H// that is set up to store at most //N// elements. This operation takes //O(N)// time, as it involves initializing the array that will hold the heap.
+  * Insert(//H, v//) inserts the item //v// into heap //H//. If the heap currently has //n// elements, this takes //O//(log //n//) time.
+  * FindMin(//H//) identifies the minimum element in the heap //H// but does not remove it. This takes //O//(1) time.
+  * Delete(//H, i//) deletes teh element in heap position //i//. This is implemented in //O//(log //n//) time for heaps that have //n// elements.
+  * ExtractMin(//H//) identifies and deletes an element with minimum key value from a heap. This is a combination of the preceding two operations and so it takes //O//(log //n//) time.
+I thought this section was really clear and helped my understanding a lot. On a readibility/interesting scale, I'd give it a 10.
-====== Section 2.5 - A More Complex Data Structure: Priority Queues ======