Chapter 2

The first major question that needs to be answered in discussing algorithms is how to define what an efficient algorithm is. At first, it can be defined as an algorithm that, when implemented, runs quickly on real input instances. While this definition does highlight an important characteristic of an efficient algorithm, it does not fully encapsulate what it means to be efficient. The first missing piece of information in this definition is where/how well an algorithm is implemented. If an algorithm is run on a very fast processor even if it is poorly designed, it may still run quickly. Oppositely, a good algorithm may still run slowly if it is poorly implemented. Another uncertainty in this definition is what a “real” input instance is, as there is no bound as to what this defines. A final issue with this definition is that it doesn't discuss the scalability of an algorithm. When analyzing an algorithm, it is best to look at the worst-case running time. The best-case running time rarely occurs, and when you need a guaranteed performance time, only the worst-case running time can provide that. For an average-case running time, the same issue applies, along with the notion of what actually defines “average case”. A second possible definition of an efficient algorithm is an algorithm that achieves qualitatively better worst-case performance, at an analytical level, than a brute-force search. A brute-force search first obtains all possible solutions and then looks for a solution that satisfies the requirements. A more specific definition of efficiency further constrains the limitations by saying an algorithm is efficient if it has a polynomial run time. This means that it has a run time proportional to n^k, where k is a constant and n is the size of the input set. Defining such a specific definition of efficiency allows negatability, which means that it becomes possible to state that there is no efficient algorithm for a particular problem. To me, this means that there are simply some problems for which no efficient algorithm is achievable. Overall this section was generally understandable, a 7/10.

Computational Tractability is based upon our ability to define the worst-case run time of an algorithm given an input set of size n. The algorithm's run time the grows at a rate that is at most proportional to some function f(n), which becomes the running time bound for the algorithm. When defining the bounds of the run time for an algorithm, while defining it in very concrete terms provides the most precise definition, it can be a very exhaustive activity, and provides unnecessary information. When we define the run time of an algorithm, we generically base it off of the number of steps in a “pseudo-code specification” of the algorithm, each of which unfolds into a fixed number of primitive steps. When looking at the bounds of the run-time of an algorithm, there are 3 bounds. Asymptotic Upper bounds, Asymptotic lower bounds, and asymptotically tight bounds. Each of these are defined with a different symbol: O, Ω, and Θ respectively. The upper and lower bounds do not specify the exact growth rate of the function that defines the running time of the algorithm; they only express the bounds. These bounds can be as specific or as generic as you desire, although generally we are looking for the most specific. The tight bounds specifies the exact growth rate of the function, and is a conclusion we can draw if O(f(n)) = Ω(f(n)). Understanding this notation wasn't very difficult for me as I had had experience with all three definitions going all the way back to high school, but the formal proofs and notation for the definitions was made much more clearer once I had learned about it in class. Understanding that these bounds are applied only for a certain input set size and above, and may not apply across every single input size was something I had not thought of before. The main functions that come up repeatedly in the analysis of algorithms are logarithmic(logn), polynomial (n^k), and exponential (k^n). Logarithmic functions grow more slowly than polynomial functions, which grow more slowly than exponential functions. My prior experience and understanding of run-time analysis made this section much easier to understand, however understanding the formal definitions became much clearer after learning about it in class. I would give this section a 9/10.

When analyzing the asymptotic bounds of an algorithm, you don't actually need to write and run the program, but instead simply analyze the pseudocode implementation of the algorithm in a step by step fashion. For the Gale-Shapley algorithm, we know that the algorithm will terminate in at most n^2 iterations, as there are n men who can each make proposals to at most n women, thus resulting in a total of n^2 proposals. When thinking about how this algorithm will actually be implemented with data structures, the main things that need to be tracked are the set of men and women, their respective individual preference lists, the set of unmatched men, who each man has proposed to, and the current engagements at any point in time. When implementing these structures we need to decide whether it is more efficient to use arrays or lists. Arrays are a set block of memory that stores a specific preset amount of information. The main properties of arrays are that they have random access and can access the ith element in constant time, they can look for an element within the set in linear time, and if the list is sorted they can look for an element in logarithmic time. However, arrays are also created with a fixed size, and therefore are not dynamically sizable and are not as useful for sets of changing size. A linked list is a collection of blocks of memory that are connected to each other through pointers that point to where the next block of memory is located. The main properties of linked lists are that they are dynamically sizable and therefore don't have a fixed size like arrays, they can delete items from the list in constant time, as well as add items in constant time. However, they do not have random access and therefore require linear time to access the ith item. Converting between an array and list structure can be done in linear time. Returning back to the Gale-Shapley algorithm, the strengths of both arrays and lists can be used. When tracking the individual men and women, they can be represented by integers that are used as their 'ids'. The preference lists of men and women can be tracked using 2D arrays, one for men and one for women. The set of unmatched men is best implemented using a list, as it will change over time. The set of engagements can be tracked using an array, matching the 'ids' of an engaged man and woman. The next woman a man needs to propose to can be tracked by maintaining the integer value of the next woman he needs to propose to on his preference list. Using these data structures, we are able to make sure that every action completed in the pseudocode algorithm is completed in linear time, during at most n^2 iterations of the while loop, and therefore confirms that this algorithm can be implemented in O(n^2) time. I found this section very helpful in understanding why we need to use lists vs arrays and vice versa in order to complete the necessary actions for this algorithm in order to make each step performed in constant time. Overall I would give this section a 9/10.