Computer Science 111 Due Wed April 6, 5pm. Problem Set 7 1. [Finding the largest and smallest and both] In class, we talked about sorting elements in a list. A simpler task is to find the largest (or smallest) element in a list. We will assume throughout this problem that we have a list of records that are integers. A) Describe (in English) a method for finding the largest element in a list. B) Give psuedo-code for the algorithm you specified in part A). C) Suppose that we wanted to find i) both the largest and smallest elements in the list ii) the 2 largest elements in the list For each case, give pseudo-code for an algorithm that would do the task. D) [Extra Credit] For the problems in part C), can you propose algorithms that achieve greater efficiency than merely finding the largest and then i) finding the smallest ii) finding the second largest If your algorithms in 1C) already do this, explain why. Give psuedo-code and an argument about why your algorithms are more efficient. 2. [QuickSort] In class we discussed 2 sorting algorithms. A third algorithm that is popular in practice is QuickSort. If we have a list of N elements to sort, QuickSort works by finding the correct location of the 1st element of the (unsorted) list. While doing this, QuickSort divides the other elements of the list into those larger than and those smaller than this element. Then, recursion is used to sort the list by sorting the elements that are smaller and sorting those that are larger. In terms of an example, if we wanted to sort the numbers 6 5 10 3 8 9 2 7 4 We'd first find the correct location of the number 6 and by switching elements that are larger and smaller would get this list 5 3 2 4 6 10 8 9 7 Now we know that the element 6 is in its proper place. We would then recursively sort the first part of the list 5 3 2 4 and the second part of the list 10 8 9 7 For example, 5 3 2 4 would become 3 2 4 5 and then 2 3 4 5 . For now, we won't worry about the details of the data movement. Just assume that there is a black box procedure that takes a list and puts the first element in its proper place with the smaller elements before it and the larger elements after it. It returns a number indicating the position where the first element ended. ie, a call like position = blackbox([6 5 10 3 8 9 2 7 4]) will convert the list given to [5 3 2 4 6 10 8 9 7] and set position to 4. Note: 6 becomes the 5th element of the list but list positions are numbered starting from 0, so the 5th element has position index = 4. A) Write the pseudo-code for QuickSort. Your pseudocode should give enough details that a knowledgeable COS 111 student would be able to understand the algorithm from your code. [Warning: be sure to worry about ending conditions for the recursion] B) QuickSort can run at different speeds depending on the nature of its input. In particular, if the first element is the largest (or smallest) in the array, then we end up with an algorithm that recursively sorts a list of 1 fewer element and looks like our Simple sort (Insertion sort) from class. On the other hand, if the first element has a value in the middle of those on the list, then we end up with an algorithm that does recursion on 2 problems of half the original size and looks a bit like our SortMerge algorithm. Explain this paragraph in simple terms, that is, give examples of inputs and tell which inputs will make the algorithm run faster/slower. C) [Extra Credit] If we were to implement QuickSort and measure running times, do you think it would look more like our simple Insertion sort or SortMerge. Explain your reasoning. 3. [A Transportation Problem] A different realm where algorithms are popular is in the area of networks. We consider here a simple problem in this realm. We consider the road map of an airline given as a collection of pairs of cities (A,B) such that there is a flight from A to B (Note: A pair (A,B) also means there is a "return" flight from B to A). A simple list would look something like this (Princeton, New Haven), (New Haven, Cambridge), (Cambridge, London), (Princeton, New York), (New York, San Francisco), (San Francisco, Seattle) (Seattle, Los Angeles), (Tucson, Phoenix), (Phoenix, Albuquerque) Given such a collection of pairs and 2 cities, we want to determine if there is a way to get between the cities? We will build up to this in the first parts of this problem. Notice that in the list above we can get from Princeton to Los Angeles (via New York, San Francisco, Seattle) but we cannot get from Princeton to Phoenix. A) Given a city, how would we determine those cities to which we could get directly? Specify your method in English or as pseudo-code as you wish. B) Given a city, how would we determine those cities to which we could get in one hop. That is, we are allowed to pass through an intermediate city (e.g. Princeton --> New Haven --> Cambridge). Specify your method in English or as pseudo-code as you wish. C) Given a city, how would we determine those cities to which we could get in an arbitrary number of hops. Specify your method in English or as pseudo-code as you wish. 4. [Numeracy] In class, we talked about algorithms that behaved linearly and quadratically. For an input of size N, a linear algorithm has a running time that is proportional to N. For a quadratic algorithm, the running time is proportional to the square of N. To simplify idea, assume that you have a computer that has a clock rate of 1 GHz which means that it can do 1 billion operations in a second. So, for a linear algorithm it can handle an input of size 1 billion in 1 second. And, for a quadratic algorithm it can handle an input of size about 31,622 in 1 second. A) Explain where the number 31,622 above comes from. B) Moore's Law tells us that computing power is doubling every 18 months. How many doublings are necessary before the quadratic algorithm will be able to do in 1 second what the linear algorithm currently does in 1 second? When will this happen? Please show your work.