| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:melkersonr:chapter2 [2018/01/25 16:42] – [Section 2.5] melkersonr | courses:cs211:winter2018:journals:melkersonr:chapter2 [2018/01/30 02:43] (current) – melkersonr |
|---|
| ====== Wiki for Chapter 2 ====== | ====== Chapter 2 - Basics of Algorithm Analysis ====== |
| |
| ===== Section 2.1 ===== | ===== Section 2.1 ===== |
| |
| * **Summary:** Section 2.1 is Computational Intractability. The title is a little misleading, though, because the section is really about efficiency. Either that, or I don't know the definition of computational intractability. The authors talk about time and space efficiency, and then they progress through increasingly precise and robust definitions for efficiency, dispelling any misconceptions readers might have along the way. After the first iteration of an attempt to define efficiency, they establish that there needs to be a "mathematical view" to find a definition for efficiency that is "platform-independent, instance-independent, and of predictive value with respect to increasing input sizes" because the other definitions are too vague (p31). Then, the authors talk about worst-case running time and brute-force search. They conclude that a worst-case analysis is best because it does "a reasonable job of capturing [an algorithm's] efficiency in practice" (p31), and that brute force solutions are lazy because they do not account for the problem's structure. The section includes a helpful table that give runtimes for different algorithms and input sizes. The section closes with a conclusion that having a polynomial runtime is a good enough definition for when an algorithm is considered efficient. | * **Summary:** Section 2.1 is Computational Intractability. The title is a little misleading, though, because the section is really about efficiency. Either that, or I don't know the definition of computational intractability. The authors talk about time and space efficiency, and then they progress through increasingly precise and robust definitions for efficiency, dispelling any misconceptions readers might have along the way. After the first iteration of an attempt to define efficiency, they establish that there needs to be a "mathematical view" to find a definition for efficiency that is "platform-independent, instance-independent, and of predictive value with respect to increasing input sizes" because the other definitions are too vague (p31). Then, the authors talk about worst-case running time and brute-force search. They conclude that a worst-case analysis is best because it does "a reasonable job of capturing [an algorithm's] efficiency in practice" (p31), and that brute force solutions are lazy because they do not account for the problem's structure. The section includes a helpful table that give runtimes for different algorithms and input sizes. The section closes with a conclusion that having a polynomial runtime is a good enough definition for when an algorithm is considered efficient. |
| * **Motivations:** There is no given problem in this section, but I think it's valid to say that the section was motivated by the necessity to understand efficiency before diving into algorithm implementation. | |
| * **About the Algorithm:** There are no algorithms studied in this section. | |
| * **My Questions:** This doesn't pertain to motivation/solution/proofs/analysis, but I'd ask the authors why they ended with a third "proposed" definition for efficiency and didn't include a final, concrete definition. | * **My Questions:** This doesn't pertain to motivation/solution/proofs/analysis, but I'd ask the authors why they ended with a third "proposed" definition for efficiency and didn't include a final, concrete definition. |
| * **Second Time Around:** I like that this section references the Stable Matching Problem when addressing the concept of a "size parameter" (p31). It spelled out that N = 2n^2, where n is the number of men (or women), and how to arrive at that figure. I don't believe we addressed that explicitly in lecture, and it's always helpful when an author/instructor makes connections //for// you or uses previous concepts when introducing new ones. | * **Second Time Around:** I like that this section references the Stable Matching Problem when addressing the concept of a "size parameter" (p31). It spelled out that N = 2n^2, where n is the number of men (or women), and how to arrive at that figure. I don't believe we addressed that explicitly in lecture, and it's always helpful when an author/instructor makes connections //for// you or uses previous concepts when introducing new ones. |
| * **Note To Self:** I want to remember the second proposed definition for efficiency: "An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search." I know it's not the final definition of efficiency, but it's a good way to remember that the brute-force solution is usually not the best. It's an "intellectual cop-out," as the authors say (p32). | * **Note to Self:** I want to remember the second proposed definition for efficiency: "An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search." I know it's not the final definition of efficiency, but it's a good way to remember that the brute-force solution is usually not the best. It's an "intellectual cop-out," as the authors say (p32). |
| * **Readability:** I give this section a score of 9. It's short and fairly simple. I like that the authors started basic, in a "one might initially think..." scenario, and then progressed to a better, more complete picture. | * **Readability:** I give this section a score of 9. It's short and fairly simple. I like that the authors started basic, in a "one might initially think..." scenario, and then progressed to a better, more complete picture. |
| |
| |
| * **Summary:** Section 2.2 is Asymptotic Order of Growth. This section is where we first see big-O notation. In addition to big-O notation, which is used for asymptotic upper bounds, the authors address Ω-notation (asymptotic lower bounds) and Θ-notation (asymptotically tight bounds). Then, the authors give properties of upper, lower, and tight asymptotic bounds, with associated proofs. Finally, the authors address asymptotic bounds for common functions: polynomials (all three bounds associated with highest degree (p40)), logarithms (base isn't important), and exponentials ("every exponential grows faster than every polynomial" (p42)). When addressing bounds for polynomial functions, the authors go back to polynomial time to "formalize the more elusive concept of efficiency" (p41), since they left that open-ended in Section 2.1. | * **Summary:** Section 2.2 is Asymptotic Order of Growth. This section is where we first see big-O notation. In addition to big-O notation, which is used for asymptotic upper bounds, the authors address Ω-notation (asymptotic lower bounds) and Θ-notation (asymptotically tight bounds). Then, the authors give properties of upper, lower, and tight asymptotic bounds, with associated proofs. Finally, the authors address asymptotic bounds for common functions: polynomials (all three bounds associated with highest degree (p40)), logarithms (base isn't important), and exponentials ("every exponential grows faster than every polynomial" (p42)). When addressing bounds for polynomial functions, the authors go back to polynomial time to "formalize the more elusive concept of efficiency" (p41), since they left that open-ended in Section 2.1. |
| * **Motivations:** There is no given problem in this section, but I think it's valid to say that the section was motivated by the necessity to also understand orders of growth and how they can show that an algorithm is feasible or not. | |
| * **About the Algorithm:** There are no algorithms studied in this section. | |
| * **My Questions:** This is more of a math question, but I'd ask for an explanation of why "it follows from the definition of a limit that there is some n_0 beyond which the ratio is always between (1/2)c and 2c" (p38). It's not immediately obvious to me where the (1/2) and 2 come from. | * **My Questions:** This is more of a math question, but I'd ask for an explanation of why "it follows from the definition of a limit that there is some n_0 beyond which the ratio is always between (1/2)c and 2c" (p38). It's not immediately obvious to me where the (1/2) and 2 come from. |
| * **Second Time Around:** I don't believe asymptotically tight bounds were discussed in lecture, so upon reading the section that's a concept I understand. | * **Second Time Around:** I don't believe asymptotically tight bounds were discussed in lecture, so upon reading the section that's a concept I understand. |
| * **Note To Self:** It's helpful to have in my notes that "one step will consist of assigning a value to a variable, looking up an entry in an array, following a pointer, or performing an arithmetic operation on a fixed-size integer" (p35). It's not a new concept, but it's nice to put it in writing. I also want to remember the trick the authors give for determining if an asymptotically tight bound exists: if the ratio of functions f(n) and g(n) converges to a positive constant as n goes to infinity, then f(n) = Θ(g(n)) (p38). | * **Note to Self:** It's helpful to have in my notes that "one step will consist of assigning a value to a variable, looking up an entry in an array, following a pointer, or performing an arithmetic operation on a fixed-size integer" (p35). It's not a new concept, but it's nice to put it in writing. I also want to remember the trick the authors give for determining if an asymptotically tight bound exists: if the ratio of functions f(n) and g(n) converges to a positive constant as n goes to infinity, then f(n) = Θ(g(n)) (p38). |
| * **Readability:** I think this section should get a 9. There is some mathematical notation, but it's well-written and not confusing. | * **Readability:** I think this section should get a 9. There is some mathematical notation, but it's well-written and not confusing. |
| |
| * **My Questions:** Why do they authors say finding the ith item in a linked list is O(i) runtime? I see how that is true, but I haven't seen Big-O runtimes talked about in terms of something other than n before. I think I would have expected it to be presented as: "finding an item in the linked list is O(n) in the worst case," or something like that. | * **My Questions:** Why do they authors say finding the ith item in a linked list is O(i) runtime? I see how that is true, but I haven't seen Big-O runtimes talked about in terms of something other than n before. I think I would have expected it to be presented as: "finding an item in the linked list is O(n) in the worst case," or something like that. |
| * **Second Time Around:** I like that the book explicitly lists what needs to happen in constant time in order for the algorithm to have O(n^2) runtime overall (p 46). I think reading the implementation with array notation spelled out and specifics on how to add and remove men from the linked list of unmatched men made it easier to understand the implementation. For example, "he'll propose to w = ManPref[m,Next[m]]" is a whole lot easier for me to comprehend than talking out loud about abstract ideas. One thing that did not make more sense the second time around is how to implement the women's rankings to determine if she prefers m or m'. I think the figure from the class slides helped a lot for that topic. | * **Second Time Around:** I like that the book explicitly lists what needs to happen in constant time in order for the algorithm to have O(n^2) runtime overall (p 46). I think reading the implementation with array notation spelled out and specifics on how to add and remove men from the linked list of unmatched men made it easier to understand the implementation. For example, "he'll propose to w = ManPref[m,Next[m]]" is a whole lot easier for me to comprehend than talking out loud about abstract ideas. One thing that did not make more sense the second time around is how to implement the women's rankings to determine if she prefers m or m'. I think the figure from the class slides helped a lot for that topic. |
| * **Note To Self:** I hadn't thought before about pre-processing data in order to make the algorithm more efficient later. I'll definitely want to keep that trick in my back pocket. | * **Note to Self:** I hadn't thought before about pre-processing data in order to make the algorithm more efficient later. I'll definitely want to keep that trick in my back pocket. |
| * **Readability:** I give this section an 8, deducting points for not explaining the preprocessing of the womens' preference lists thoroughly enough. | * **Readability:** I give this section an 8, deducting points for not explaining the preprocessing of the womens' preference lists thoroughly enough. |
| |
| * **My Questions:** In the subsection about cubic time, we're told to suppose that we can check in constant time whether or not a given number p belongs to a set. That sounds like a big pill to swallow, because in the sublinear time section the authors say that binary search, an improvement upon the brute force search, is O(log n). How, then, can we check that p is in the set in //constant// time? Also, do we still say that two nested loops are O(n^2) (if the work inside is constant) even if the inner loop doesn't iterate over everything? For example, if the inner loop is for something less than the first loop: for i in range n, for j in range(i,n). | * **My Questions:** In the subsection about cubic time, we're told to suppose that we can check in constant time whether or not a given number p belongs to a set. That sounds like a big pill to swallow, because in the sublinear time section the authors say that binary search, an improvement upon the brute force search, is O(log n). How, then, can we check that p is in the set in //constant// time? Also, do we still say that two nested loops are O(n^2) (if the work inside is constant) even if the inner loop doesn't iterate over everything? For example, if the inner loop is for something less than the first loop: for i in range n, for j in range(i,n). |
| * **Second Time Around:** The discussions pertaining to graphs (O(n^k) and O(n^2 2^n) runtimes) were easier to digest the second time around, I think mainly because I could read the pseudocode multiple times, on paper. | * **Second Time Around:** The discussions pertaining to graphs (O(n^k) and O(n^2 2^n) runtimes) were easier to digest the second time around, I think mainly because I could read the pseudocode multiple times, on paper. |
| * **Note To Self:** I want to remember the following: "In general, O(log n) arises as a time bound whenever we're dealing with an algorithm that does a constant amount of work in order to throw away a constant //fraction// of the input" (p56). I like that phrasing, and it might help for remembering what causes O(log n) runtime. | * **Note to Self:** I want to remember the following: "In general, O(log n) arises as a time bound whenever we're dealing with an algorithm that does a constant amount of work in order to throw away a constant //fraction// of the input" (p56). I like that phrasing, and it might help for remembering what causes O(log n) runtime. |
| * **Readability:** I like that this section has example algorithms for some of the runtimes. That helps with understanding. But I do not like the issue mentioned in My Questions. For these reasons, I give the section an 8. | * **Readability:** I like that this section has example algorithms for some of the runtimes. That helps with understanding. But I do not like the issue mentioned in My Questions. For these reasons, I give the section an 8. |
| |
| ===== Section 2.5 ===== | ===== Section 2.5 ===== |
| |
| * **Summary:** Section 2.5 is A More Complex Data Structure: Priority Queues. The authors describe the priority queue as "on of the most broadly useful sophisticated data structures" (p57). | * **Summary:** Section 2.5 is A More Complex Data Structure: Priority Queues. The authors describe the priority queue as "one of the most broadly useful sophisticated data structures" and "a data structure that, unlike lists and arrays, must perform some nontrivial processing each time it is invoked" (p57). A priority queue maintains a set S of elements, where each element has an associated key that gives the element's priority. The smaller the key, the higher the priority. The authors state that "O(log n) time per operation is the best we can hope for" with priority queues, leaving the specifics for later in the section. They give a short survey of ways to implement a priority queue, but conclude that a heap is the best option because the other options have at least one operation that will take O(n) time. A heap is a balanced binary tree where all children are greater than or equal to their parents in terms of the magnitudes of the keys. That means the root always has the highest priority. There are two ways to implement the heap, according to the authors: either with pointers, where each node has the element, the key, and a pointer to its parent and two children; or with an array if we know ahead of time the maximum number of elements that'll be in the heap. |
| * **Problem Motivations:** | * **Problem Motivations:** The motivation given for using a priority queue comes out of the need to maintain a "dynamically changing set S" and to be able to add elements, delete elements, and get to the element with the highest priority. The authors provide an example of such a situation: scheduling computer processes when they all have a priority but do not arrive in priority order. |
| * **About the Algorithm:** | * **About the Algorithms:** There are two heap algorithms in this section, and they help with adding and/or deleting elements. "Heapify-up" helps with adding elements (and deleting as I'll explain momentarily). You add the new element to the final position, but it can then violate the Heap order if its key is smaller than its parent's key. So, you switch the two and call Heapify-up recursively with the node's new location. The recursion ends when the key is no longer smaller than its parent's key, or the element is at the root. The other algorithm is called "Heapify-down," and it helps with deleting elements. When you delete an element at position i, you take the element at the last filled position and put it in position i. The Heap order can be violated if the moved element's key is smaller than its parent's key (in which case you Heapify-up), or if it is larger than either of its children's keys. In the latter case, you would Heapify-down, which involves switching the element with its smaller child, and calling Heapify-down recursively with the element's new location. The recursion ends when the key is no longer larger than either of its children's keys or the element is a leaf node. Both adding and deleting elements to a priority queue with a heap structure have O(log n) runtime because of the balanced binary characteristic of the heap. |
| * **My Questions:** | * **My Questions:** I'm still, after class //and// reading, confused about the difference between w = H[j], key(w), and j. I thought i and j represent positions in the heap. The book seems to use both w and key(w) to represent the elements, which are the values in the node's circle. Is it that elements are more complex than I'm thinking and the figures with tree representations do not show their values, but rather only the keys in the circles of the nodes? |
| * **Second Time Around:** | * **Second Time Around:** Unfortunately, not a lot makes more sense based on reading this section. I think the chart on slide 27 or 28 from Monday 1/22 class might have cleared things up, if the answer to my question above is "yes" ("...the figures with tree representations do not show their values...?"). |
| * **Note To Self:** | * **Note to Self:** I didn't know before that you could do a proof by reverse induction (p64). |
| * **Readability:** | * **Readability:** 5, because I'm still confused, and I shouldn't still be confused after class + reading. |
