Differences

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

--- courses:cs211:winter2018:journals:devlinn:chapter2 [2018/01/09 23:22] – devlinn
+++ courses:cs211:winter2018:journals:devlinn:chapter2 [2018/01/28 02:17] (current) – devlinn
@@ Line 1: / Line 1: @@
 ====== Chapter 2: Basics of Algorithm Analysis ======
-==== 2.1 Computational Tractability ====
+===== 2.1 Computational Tractability =====
 Several factors are key in the design of algorithms, including understanding the discrete nature of many problems as well as addressing the efficiency and space of an algorithm. The text gives one definition of efficiency: "An algorithm is efficient if, when implemented, it runs quickly on real input instances." Unfortunately, this definition fails to consider //where// and //how well// the algorithm is implemented.
-To be more specific, we can argue that an algorithm is efficient if it, at the bare minimum, performs in the worst case better than would a brute-force search. To narrow the definition even further, we could classify an 'efficient algorithm' as one with a //polynomial running time//, meaning its running time is bounded by //cN<sup>d</sup>// where c and d are constants > 0 and every input instance is size N.
+To be more specific, we can argue that an algorithm is efficient if it, at the bare minimum, performs in the worst case better than would a brute-force search. To narrow the definition even further, we could classify an 'efficient algorithm' as one with a //polynomial running time//, meaning its running time is bounded by //cN<sup>d</sup>// where c and d are constants > 0 and every input instance is size N. I found it beneficial to learn more about //what// exactly makes an algorithm efficient and I would rate this section a 10 for its ability to be clearly understood, since concepts were explained very straightforwardly.
-==== 2.2 Asymptotic Order of Growth ====
+===== 2.2 Asymptotic Order of Growth =====
-For the purposes of simplicity and clarity, classifying running times should be done in terms of constant factors; for example instead of calculating a run time as an<sup>2</sup> + bn + c, we would consider this run time to be simply n<sup>2</sup>. Assume //T(n)// is the worst-case run time for an algorithm with //n// referring to the size of the input. Let //f(n)// refer to a function. T is //asymptotically upper-bounded// and //T(n)// is //order f(n)// if:
+For the purposes of simplicity and clarity, classifying running times should be done in terms of constant factors; for example instead of calculating a run time as an<sup>2</sup> + bn + c, we would consider this run time to be simply n<sup>2</sup>. Assume //T(n)// is the worst-case run time for an algorithm with //n// referring to the size of the input. Let //f(n)// refer to a function. T is //asymptotically upper-bounded by f// and //T(n)// is //O(f(n))// if:
   * there exists a constant //c// > 0
-  * there exists and a constant n<sub>0</sub> ≥ 0 such thatn all n ≥ n<sub>0</sub>, and
+  * there exists and a constant n<sub>0</sub> ≥ 0 such that all n ≥ n<sub>0</sub>, and
-  * //T(n)// ≤ //c//.
+  * //T(n)// ≤ //c • f(n)//.
+Suppose //T(n)// ≥ //d • f(n)//, for a fixed constant //d// > 0; then T is //asymptotically lower-bounded by f// and Ω//(f(n))//. Finally, if //T(n)// is both //O(f(n))// and Ω//(f(n))//, then //T(n)// is considered //asymptotically tight bound// for //T(n)// and //T(n)// is θ(//f(n)//).
+The growth rates //O//, Ω, and θ share some basic properties:
+  * //transitivity//: if a function //f// is asymptotically upper-bounded by a function //g// and //g// is asymptotically upper-bounded by a function //h//, then //f// is asymptotically upper-bounded by //h//.
+  * if //f// = θ(//g//) and //g// = θ(//h//) then //f// = θ(//h//)
+  * if //f// = //O//(//h//) and //g// = //O//(//h//) then //f// + //g// = //O//(//h//)
+  * if //g// = //O//(//h//) then //f// + //g//
+  * if //g// = //O//(//f//) then //f// + //g// = θ(//f//)
+Logarithms, polynomials, and exponential functions are various ways to classify running time, with logarithms growing the slowest and exponentials growing the fastest. It was interesting to learn more deeply about run time order, for it has been frequently discussed throughout many of my courses. This section provided a deeper understanding on the variety of run time functions. I would have liked more information on how algorithms' run times are calculated. The readability of this section was around a 7, because the various variables, rules, and terms were somewhat complicated to keep straight.
+===== 2.3 Implementing the Stable Matching Problem Using Lists and Arrays =====
+Deciding how data will be represented in an algorithm is critical in the calculation of running time. In the Gale-Shapley algorithm, the only data structures needed are lists and arrays. Using arrays has several benefits, including constant-time access for the i<sup>th</sup> item, linear running time for searching if an item is in the array, and O(log//n//) for binary search of a sorted array. In contrast, a list will benefit us when we are dealing with a group of elements that are //changing//, since adding and deleting items is more efficient with a list than with an array.
+In order to attain a preferable run time for the Gale-Shapley algorithm, we must choose data structures to model our data which will be most beneficial for their use. For example, we will store the preference lists of the men and the preference lists for the women in arrays, since this data structure is ideal for accessing the i<sup>th</sup> item. While some data structure decisions seem clear, such as using a linked list to denote the free men, since items will be added and removed from this structure, but other choices are more difficult. Maintaining a woman's preferences can be done most efficiently by using an //n// x //n// array which stores the rank of a man for a particular woman. The most important result of this is allowing constant-time for this step, and therefore establishing the run-time for the entire algorithm as O(//n//<sup>2</sup>).
+I did not find this section as easy to follow as our discussion in class about the same decisions. If we had not worked through these questions prior to this reading I would have had a very hard time understanding their logic, since it was weakly justified. I rate this section a 5 for readability. I would also have liked a more in-depth explanation of the method to ensure O(//n//<sup>2</sup>) running time as opposed to O(//n//<sup>3</sup>), which we discussed in class.
+===== 2.4 A Survey of Common Running Times =====
+As we learned earlier, when creating algorithms a goal is to have a more efficient running time than a brute-force algorithm would have. There are several common run times that appear frequently in algorithms, including linear time, //nlogn// time, quadratic time, cubic time, and //n<sup>k</sup>//. Linear time means the running time is at most C • n, where C is a constant and n is the input size. Some examples of algorithms with linear running time is one which computes the maximum of n numbers and merging two sorted lists. In terms of algorithms that have O(//nlogn//), this can be used to describe algorithms which split their inputs into two pieces and solve each half recursively, then combine each solution in linear time. Most commonly, this procedure is seen in the merge sort algorithm. One example of an algorithm with quadratic time is one with nested loops, such as an algorithm which iterates over items of two arrays, performing a constant operation inside the loops. For cubic time, algorithms which perform more complex operations inside nested loops typically follow this pattern. An example of O(//n<sup>k</sup>//) running time is one which finds independent sets in a graph.
+There are some running times that are worse than polynomial running time, including 2//<sup>n</sup>// and //n//!. These functions grow faster than polynomials and therefore are not ideal running times for algorithms. Algorithms which search through all subsets have a running time of 2//<sup>n</sup>//. Algorithms which pair //n// items with //n// items or those which consider the ways to arrange //n// items in order have a running time of //n//!, which is worse than 2//<sup>n</sup>//. In addition, some algorithms run in log//n// time, which is slightly better than linear time.
+===== 2.5 A More Complex Data Structure: Priority Queues =====
+A priority queue is considered one of the most applicable data structures for use in algorithms. These structures are useful when a group of elements have a priority, which we call a key, and we seek to obtain the element with the highest priority. Ideally, we would hope to implement a priority queue which can perform insertion and deletion operations with O(//logn//) running time and can sort //n// numbers in O(//nlogn//) running time. A heap can be used to implement a priority queue, which means each element in the priority queue at node //i//, the element at //i//'s parent has a key that is less than or equal to the element. It is important to node that for a heap H, H[1] is the root. In addition, for a given position //i//, the left child for //i// is 2//i// and the right child of //i// is 2//i// + 1.
+In order to maintain a heap's structure after the insertion of an element, the algorithm Heapify-up will be useful. This algorithm can be roughly sketched as follows:
+    Heapify-up(//H//, i):
+        if i > 1 then
+            let j = parent(i) = ⌊i/2⌋
+            if key[//H//[i]] < key[//H//[j]] then
+                swap array entries //H//[i] and //H//[j]
+                Heapify-up(//H//,j)
+            endif
+        endif
+Deleting an element must also consider how to maintain the order in the heap. The algorithm of Heapify-down can be useful for this, which is sketched as follows:
+    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//[j]] then
+            swap array entries //H//[i] and //H//[j]
+            Heapify-down(//H//, //j//)
+        endif