====== Chapter 2 ====== Analyzing algorithms involves thinking about how their resource requirements—the amount of time and space they use—will vary with increasing input size, N. This input size is used to describe efficiency in terms of Big-O notation (to be discussed later). ===== 2.1 Computational Tractability ===== We want algorithms that run quickly. In other words, they are efficient with respect to time. But, it is important that the algorithms be efficient in their use of other resources—in particular, memory—as well. Efficiency in terms of running time is measured with respect to the size of the input, N. The idea is to look for a bound on the largest possible running time the algorithm could have over all inputs of a given size N, and see how it scales with N—this approach is called the worst-case analysis. The alternative to this approach is called the average-time analysis. It studies the performance of an algorithm averaged over “random” instances, but can be difficult and often impractical to implement. Revisiting our example of the Stable Matching Problem, we can see that the use of brute-force search (i.e., try all possibilities and see if any of them works) over the search space of possible solutions is extremely inefficient in terms of runtime. There are n! possible perfect matchings between n men and n women. The brute-force algorithm typically takes 2^N time or worse for an input of size N. In contrast, the Gale-Shapley algorithm solves this problem in O(N^2) runtime. ==== 2.1.1 Effectively Defining Efficiency ==== We can then say that //an algorithm is efficient if it has a polynomial running time//. It should be noted, however, that problems for which polynomial-time algorithms exist almost invariably turn out to have algorithms with running times (almost) proportional to polynomials like n, n logn, n^2, or n^3. The use of polynomial-time bounds is only an abstraction of practical situations. Hence, with our definition of efficiency, it is possible to express the notion that there is no efficient algorithm for a particular problem. ===== 2.2 Asymptotic Order of Growth ===== When we provide a bound on the running time of an algorithm, we will generally be counting the number of pseudo-code steps that are executed. In this context, 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. We want to express the growth rate of running times and other functions in a way that is insensitive to constant factors and low-order terms. For example, for a running time like 1.62n^2 + 12n + 6, we want to say that the algorithm grows like n^2. ==== 2.2.1 Asymptotic Upper Bounds ==== Let T(n) be the worst-case running of an algorithm on an input size of n. Given another function f(n), we say that T(n) is O(f(n)) if there exist constants c > 0 and n’ ≥ 0 such that for all n ≥ n’, it is the case that T(n) ≤ c·f(n). In this case, T is asymptotically upper-bounded by f. It is important to note that O(//x//) only expresses an upper bound, and not the rate of growth, of the function. Therefore, something that is O(n^2) is, by definition, also O(n^3). Ideally, we want the lowest upper bound to best analyze and compare the running times of algorithms. ==== 2.2.2 Asymptotic Lower Bounds ==== We want to express the notion that for arbitrarily large input sizes n, the function T(n) is at least a constant multiple of some function f(n). We say that T(n) is Ω(f(n)) if there exist constants ε > 0 and n' ≥ 0 so that for all n ≥ n', it is the case that T(n) ≥ ε·f(n). We refer to T in this case as being asymptotically lower-bounded by f. This definition works just like O(//x//), except that we are bounding the function T(n) from below instead of from above. ==== 2.2.3 Asymptotically Tight Bounds ==== If a function T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n)). In other words, f(n) is an asymptotically tight bound for T(n). Such bounds can be found by closing the gaps between upper bounds and lower bounds. ===== 2.3 Implementing the Stabling Matching Algorithm Using Arrays and Lists ===== When designing an algorithm, one has to think about how the data will be represented and manipulated, so as to bound the number of computational steps it takes. In the Stable Matching Problem, each man and each woman has a ranking of all members of the opposite gender. The very first question we need to discuss is how such a ranking will be represented. Further, the algorithm maintains a matching and will need to know at each step which men and women are free, and who is matched with whom. In order to implement the algorithm, we need to decide which data structures we will use for all these things. We can use arrays and linked lists to implement the Stable Matching algorithm. If we actually want to implement the G-S algorithm so that it runs in time proportional to n^2, we need to be able to implement each iteration in constant time. We can define an array indexed by all men or all women (by ordering the men or women--e.g. alphabetically). We need to have a preference list for each man and for each woman. To do this we will have two arrays, one for women’s preference lists and one for the men’s preference lists. To select a free man, we will maintain the set of free men as a linked list. We need to identify the highest-ranked woman to whom a man //m// has not yet proposed. To do this we will need to maintain an extra array //Next// that indicates for each man //m// the position of the next woman he will propose to on his list. We need to be able to identify the man //m’// that //w// is engaged to (if there is such a man). We can do this by maintaining an array //Current// of length //n//, where //Current[w]// is the woman //w//’s current partner //m’//. We would like to decide in O(1) time if woman //w// prefers //m// or //m’//. Keeping the women’s preferences in an array //WomanPref//, analogous to the one we used for men, does not work, as we would need to walk through //w//’s list one by one, taking //O(n)// time to find //m// and //m’// on the list. At the start of the algorithm, we create an n x n array //Ranking//, where //Ranking[w, m]// contains the rank of man //m// in the sorted order of //w//’s preferences. By a single pass through //w//’s preference list, we can create this array in linear time for each woman, for a total initial time investment proportional to n^2. Then, to decide which of //m// or //m’// is preferred by //w//, we simply compare the values //Ranking[w, m]// and //Ranking[w, m’]//. These data structures allow us to implement the Gale-Shapley algorithm in O(n^2) time. Personally, I found it really cool how we used the restriction of having O(n^2) running time on the G-S algorithm to reverse-engineer the implementation for the algorithm and then decide what data structures to use. One thing I found particularly interesting was the use of the n x n array to initialize and keep track of the women's preference lists, as opposed to just using an array of size n, to reduce this step from O(n) to O(1) in order to keep the run time O(n^2) overall. I read this section before covering it in class, and it didn't really make much sense at the time. Having heard class discussions on //why// certain data structures are best for the algorithm, I went back to read this section again--and it made //much// more sense. ===== 2.4 A Survey of Common Running Times ===== There are several running time bounds that appear over and over again in algorithm analysis. A few of these are given below: ==== 2.4.1 Linear Time ==== An algorithm that runs in O(n) time has a running time that is at most a constant factor times the size of the input. Such algorithms often involve processing the input in a single pass, and performing constant time operations on each item of the input. Examples of such algorithms include computing the maximum of n numbers, and merging two //sorted// lists. ==== 2.4.2 O(n log n) Time ==== O(n log n) is the running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time. One of the most well known problems that can be solved in O(n log n) time is sorting--more specifically, the //efficient// sorting algorithms. One such sorting algorithm is Mergesort, which divides the set of input numbers into two equal-sized pieces, sorts each half recursively, and then merges the two sorted halves into a single sorted output list. ==== 2.4.3 Quadratic Time ==== Quadratic time naturally arises from a pair of nested loops: An algorithm consists of a loop with O(n) iterations, and each iteration of the loop launches an internal loop that takes O(n) time. Multiplying these two factors of n together gives the running time of O(n^2). The less efficient sorting algorithms, e.g. insertion sort, also fall under this category of running time. ==== 2.4.4 Cubic Time ==== More elaborate sets of nested loops often lead to algorithms that run in O(n^3) time. For example, consider a problem involving nested for-loops that iterate over the input. Each level of the loop will be O(n) running time, making the for-loops O(n^2). If, inside the inner nest for-loop, there are statements that run in linear time, for example indexing a linked list, the entire algorithm will end up being O(n^3). ==== 2.4.5 O(n^k) Time ==== We obtain a running time of O(n^k) for any constant k when we search over all subsets of size k. An example of problems that run in O(n^k) time is the Independent Set problem, which can be solved by the algorithm (from the textbook) below: For each subset S of k nodes Check whether S constitutes an independent set If S is an independent set then Stop and declare success Endif Endfor If no k-node independent set was found then Declare failure Endif ==== 2.4.6 Beyond Polynomial Time ==== O(n!) is a running time that belongs to the set of running times beyond polynomial time. The function n! arises in problems where the search space consists of all ways to arrange n items in order. A basic problem in this genre is the Traveling Salesman Problem: given a set of n cities, with distances between all pairs, what is the shortest tour that visits all cities? We can assume that the salesman starts and ends at the first city, so the crux of the problem is the implicit search over all orders of the remaining n-1 cities, leading to a size (n-1)! search space. ==== 2.4.7 Comments ==== This section was pretty intuitive. Sections 2.4.1 through 2.4.4 were basically a recap of things we learned in CSCI-112 (or other Computer Science classes). However, sections 2.4.5 and 2.4.6 were less intuitive for me. Probably due to the nature of the problems involved. It took me several attempts at reading and a few online searched to fully understand what is happening in the Independent Set problem. The Traveling Salesman Problem was more intuitive (it is basically just about permutations), but I had trouble trying to come up with //practical// problems in every day Computer Science that would have a running time of O(n!). ===== 2.5 A More Complex Data Structure: Priority Queues ===== 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 a set S, we want to take the one with highest priority. ==== 2.5.1 What is a Priority Queue? ==== A priority queue is a data structure that 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. Examples of applications that motivate the need for priority queues includes scheduling processes on a computer, and scheduling print jobs for a network printer. ==== 2.5.2 Heaps: A Data Structure for Implementing Priority Queues ==== We could use a list to implement a priority queue, with a pointer labeled //Min// to the one with minimum key. This makes adding new elements easy, but extraction of the minimum hard. Specifically, finding the minimum is quick--we just consult the //Min// pointer--but after removing this minimum element, we need to update the //Min// pointer to be ready for the next operation, and this would require a scan of all elements in O(n) time to find the new minimum. To get better running times for its operations, we can use a heap for the implementation of a priority queue. 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. The tree will have a root, and 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. === 2.5.2.1 Implementing a Heap === We can use an array H to represent a heap if we know of a upper bound //N// of the number of elements, or nodes, that would ever be in the heap at a given time. H[1] will always correspond to the root node, and for any node at position i, the left child and the right child of the node are at positions 2i and 2i+1 respectively. === 2.5.2.2 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. First consider adding a new heap element v, and assume that our heap H has n < N elements so far. Now it will have n+1 elements. To start with, 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 heap property, as the key of element v may be smaller than the key of its parent. So we now have something that is almost-a-heap, except for a small "damaged" part where v was pasted on at the end. We can use the following algorithm, Heapify-up, to fix this broken heap: 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 Thee procedure Heapify-up(H,i) fixes the heap property in O(log i) time, assuming that the array H is almost a heap with the key of H[i] too small. Using Heapify-up we can insert a new element in a heap of n elements in O(log n) time. We can also implement the operation Delete(H, i), which will delete the element in position i. Assume the heap currently has n elements. After deleting the element H[i], the heap will have only n-1 elements; and not only is the heap-order property violated, there is actually a "hole" at position i, since H[i] is now empty. So as a first step, to patch the hole in H, we move the element w in position n to position i. After doing this, H at least has the property that its n - 1 elements are in the first n-1 positions, as required, but we may well still not have the heap-order property. We can fix this using a similar algorithm, called 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 + l Let j be the index that minimizes key[H[left]] and key[H[right]] Else if 2i = n then Let i = 2i Endif If key[H[j]] < key[H[i]] then swap the array entries H[i] and H[j] Heapify-down (H, k) Endif All the steps in Heapify-down, except the recursive call to itself, are O(1) operations. The recursive call is O(log n). Therefore, Heapify-up and Heapify-down are O(log n) algorithms, allowing us to add to or delete from a heap in log n time. ==== 2.5.3 Operations for Priority Queues ==== Below is a summary of the operations that we can use with a priority queue implemented with a heap: * StartHeap(N): O(N) time * Insert(H, v): O(log n) time * FindMin(H): O(1) time * Delete(H, i): O(log n) time * ExtractMin(H): O(log n) time ==== 2.5.4 Comments ==== The motivation for priority queues was pretty intuitive. The description of heaps and the operations that can be performed on heaps was easy to read and follow, since heaps look similar to binary search trees. I found the application of using heaps to implement a priority queue very interesting--it looked like a very effective way of getting a better runtime of O(log n) on heap operations, as opposed to the O(n) that list-based implementations offer. The logic behind the Heapify-up and Heapify-down algorithms was easy to understand as well. Overall, I feel like I enjoyed reading about how priority queues work under the hood. I had a question though: is there a reason why one would prefer using priority queues to sort a list of items, as opposed to something like Mergesort, since both run in O(n log n) time, and MergeSort is arguably less complicated to implement (compared to implementing a heap and then using it to represent a priority queue)?