Differences

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

--- courses:cs211:winter2011:journals:camille:chapter2 [2011/01/25 15:05] – [Section 4: A Survey of Common Running Times] cobbc
+++ courses:cs211:winter2011:journals:camille:chapter2 [2011/01/31 02:47] (current) – [Section 1: Computational Tractability] cobbc
@@ Line 12: / Line 12: @@
 Again, this section was very readable. I thought that they did a great job of explaining why we need the mathematical definition of efficiency and how we get to it. And I read this after our classes on t, and I think that was good for me, because I already knew what to expect.
+    * **Sara Says:**
+"Wait I thought our algorithm for the stable matching problem took O(N^2) time?" --> Yes,
+that's correct.  They are saying the simplest algorithm is "Given all possible perfect
+pairings (N!), find one that is stable and that's the solution."  So, that's O(N!).  But,
+Gale-Shapley is a more efficient algorithm.
 ===== Section 2: Asymptotic Order of Growth =====
@@ Line 62: / Line 67: @@
     * **Summary:**
+Good algorithms are important to get efficient solutions, but sometimes you need more complex data structures in order to implement the algorithms efficiently (or make improvements to the algorithm). Some data structures are designed for specific problems, but some are more broadly applicable - like the priority queue, which is a data structure that "must perform some nontrivial processing each time it is invoked." Priority queues are useful for when you need to maintain a changing set (like the free men in our stable matching problem) and be able to add, delete and select certain elements. Elements in a priority queue have a priority value (key). Priority queues allow you to add to the set, delete from the set, and select the element with the smallest key. Useful for scheduling real-time events (ex. processes on a computer). Each operation (add, delete, select min) should take O(logn) time. The problem of using the priority queue to sort elements in O(nlogn) time shows/"proves" that O(logn) per operation is the right thing to aim for. We use a heap to implement a priority queue because using lists or arrays doesn't work (something has to take O(n) time instead of O(logn) time). A heap is like a balanced binary tree with every parent smaller than either of its children (but it's actually usually maintained in an array - explanation for how that works is in our class notes or on p.60). Operations: heapify-up and heapify-down work in O(logn) time (explanations for how that works are on p.61-63 and in our notes). Priority queues are implemented using heaps - insert uses heap's heapify-up. The minimum element (highest priority) is always at the root of the heap. Delete uses heapify-down. (Running times and a few more operations are on p.64 and in our notes).
     * **Insights and Questions:**
+Interesting distinction between arrays/lists and "complex" data structures like priority queues/heaps/etc. I never really thought of these as being considerably more complex. I am really curious about other complex data structures. When is it ever useful to make up a data structure just for one type of problem (like the book suggests happens occasionally)? I feel like I need an example of how that could happen.
     * **Readability:**
+This section was a little harder to read than others. It flowed well, but the logic of jumping from arrays to priority queues to heaps wasn't quite as clear or as seamless as other sections or as clear as it was in class. I think that actually seeing someone do heapify-up/down is really important and you just can't get that from diagrams that don't move.