Unit 4 Lesson 1 Speed Last Modified: 7/2/06 Author: Zachary J. Miller Self-Check 1 1. Which of the following could be an instruction in machine language? a. x = a * b b. x = a + b c. SUM R0, R1 d. 00000011 00000001 00000011 e. None of the above 2. Which of the following is true about assembler language? a. One line of assembler is one line of machine language b. It is harder for a human to understand than machine language c. It is an outdated language that was used to program the first computers d. Assembler is what the computer runs e. None of the above 3. Why are interpreted languages typically slower? a. There is a large initial time cost to interpreting the program b. It is more difficult to write efficient algorithms in interpreted languages c. Java is a slow language d. Interpreted languages are used by students who write bad code e. None of the above 4. Which statement best describes a compiler? a. It groups code fragments into dictionaries that can be used to look up information b. It optimizes and coverts code into machine language c. It converts code into machine language and machine language back into code d. It checks code for syntax and logic errors e. It runs programs that are written in other programming languages by converting them to machine code line by line while the program is running 5. Below is information about two different processors. Processor #1 Processor #2 Pipelined no yes Number of stages N/A 2 Processor Speed 2.0 GHz 3.0 GHz Which processor will run a single instruction the fastest? Which one will run two instructions the fastest? (Hint: this problem is easier if you think of a 2.0 GHz processor as having two clock cycles a second and a 3.0 GHz processor as having three clock cycles a second. In actuality they would have 2 and 3 clock cycles every billionth of a second, but the math works out the same either way) a. #1 runs both one instruction and two instructions faster b. #2 runs both one instruction and two instructions faster c. #1 runs one instruction faster and #2 runs two instructions faster d. #1 runs two instructions faster and #2 runs one instruction faster e. Both processors run two instructions at the same speed and #1 is faster with one instruction Answer Key: To be removed upon publication 1. d 2. a 3. e 4. b 5. e Self-Check 2 1. Which of the following magnitudes of running times is the fastest. a. O(n) b. O(n2) c. O(2n) d. O(n!) e. Cannot be determined 2. Which of the following is a common criterion for comparing algorithms? a. time b. correctness c. space d. language e. both A and C 3. Rank the following storage devices from fastest to slowest I. Ram II. Hard-Drive III. Cache a. I, II, III b. I, III, II c. III, II, I d. III, I, II e. II, I, III 4. What is an intractable algorithm? a. An algorithm that will never end b. An algorithm that can run very fast c. An algorithm that takes a very long time to run d. An algorithm that takes a very long time to run and one which cannot be in class P e. None of the above 5. Which of the following is an example of an algorithm that cannot be written? a. halting program b. bubble sort c. traveling sales person d. binary search e. finding all combinations of a set of data Answer Key: To be removed upon publication 1. a 2. e 3. d 4. d 5. a Lesson Quiz 1. Which of the following statements is true? a. Compiled programs are slower than translated ones b. Compilers often optimize code as they are compiling c. You only need to run the translator once, from then on you can just run the executable produced d. C++ is a translated language e. All of the above are false 2. Below is information about two different processors. Processor #1 Processor #2 Pipelined no yes Number of stages N/A 4 Processor Speed 2.0 GHz 4.0 GHz For a small number of instructions processor #1 will finish first, for a large number of instructions processor #2 will finish first. How many instructions should be run such that the processors both finish at the same time? a. 1 b. 2 c. 3 d. 4 e. 500 3. The following is a non-optimized version of bubble sort. What is it’s time complexity? def bubbleSort(list): for n in range(0, len(list)): for x in range(0, len(list) - 1): temp = list[x] if(temp > list[x + 1]): list[x] = list[x + 1] list[x + 1] = temp a. O(n) b. O(n logn) c. O(n2) d. O(2n) e. O(n!) 4. The following recursive function finds numbers in the Fibonacci sequence. The input n signifies which number in the sequence should be returned. The first Fibonacci number is defined as 1 and the second is also defined as 1. From then on, the next Fibonacci number is defined as the sum of the two before it. Here is the first 15 numbers in the sequence. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 def Fibonacci(n): if( n == 1 ): return 1 if( n == 2 ): return 1 ***** Fill in the last line of code so that the algorithm works properly. a. n = Fibonacci(n - 1) b. return Fibonacci(n) c. return Fibonacci(n – 1) + Fibonacci(n) d. return Fibonacci(n – 2) + Fibonacci(n – 1) e. return Fibonacci(n – 1) 5. While the algorithm in problem 4 may be correct on paper, it is not very time efficient and just as bad at space efficiency. Below is another means of computing the Fibonacci sequence. Why is this one more efficient? (Hint it might help to trace through the program in problem 4 for a small number like 5) def Fibonacci(n): fib = [1, 1] for x in range(2, n): nextNum = fib[x – 1] + fib[x – 2] fib = fib + [nextNum] return fib[n – 1] #n-1 because arrays are zero based a. The recursive function would compute most numbers numerous times b. The second means of finding Fibonacci numbers has no if statements c. The recursive function finds the largest numbers first and therefore causes the computer to have to add larger numbers d. The function with the loop has a definite end while the recursive function doesn’t e. None of the above 6. Which of the following statements is one of the reasons computers have hard drives? a. Hard drives are faster than other means of storage b. The network is connected through the hard drive c. Hard drives can be placed very close to the processor so information is easy to transfer between the two d. Hard drives have less storage and are therefore easier to add or remove from the computer e. None of the above 7. One of the biggest unsolved problems in theoretical computer science is trying to determine that which two categories of algorithms are distinct or not? a. NP algorithms and intractable algorithms b. n2 algorithms and n logn algorithms c. intractable algorithms and class P algorithms d. class P algorithms and class NP algorithms e. None of the above 8. Rank the following running times from fastest to slowest. I. O(n logn) II. O(n) III. O(n!) a. I, II, III b. II, III, II c. II, III, I d. III, II, I e. II, I, III 9. Which of the following statements are true? a. Machine language is composed of binary numbers b. Assembler was developed to make it easier for people to read machine language c. The processor doesn’t run machine code when you use an interpreter instead of a compiler d. Two of the above e. All of the above 10. Why is it best to write code that uses information stored close together? a. It makes programs easier to read b. It minimized data transfer time between memory levels c. It tends to produce algorithms with lower time complexity d. It doesn’t make a difference e. None of the above Answer Key: To be removed upon publication 1. b 2. c 3. c 4. d 5. a 6. e 7. d 8. e 9. d 10. b Justifications 1. Justification (Answer B): A is false, Compiled programs run faster than translated programs because once the initial compilation is complete, the code can be run directly by the processor. Answer B is correct, compilers often optimized code as its converted to machine language. Answer C is incorrect, the reason translated languages are slower is because the translation is done while the program is running every time the program is run. C++ is a compiled language therefore D is also incorrect. 2. Justification (Answer C): The easiest approach to solving this problem is to try each of the answer until you find the correct one. One processor is a 2.0 GHz processor and the other processor is 4.0 GHz, to simplify the math we will only remember that processor #2 has two clock cycles for every one clock cycle processor #1 has. Let’s try option A first: 1 instruction To complete one instruction processor #1 will need only one clock cycle. Processor 2 will therefore be able to run 2 clock cycles in the same amount of time. However, since there are four stages, the instruction would need four clock cycles to make it all the way through. So A in not the correct answer. Processor #1 Processor #2 Results 1 cycle 4 cycles Option B is next: 2 instructions To complete two instructions processor #1 will take two clock cycles to finish which means processor #2 must complete the instructions in four cycles. A four stage processor means that it will take four cycles to move the first instruction through the pipeline. The second instruction, however, starts one cycle behind the first which means it only gets three clock cycles to advance through the pipeline (1 less than it needs) Processor #1 Processor #2 Results 2 cycle 5 cycles Next up is option C: 3 instructions We would follow the same process as the previous two to determine the whether or not three instructions is correct, however you might also notice a trend in the results. Each additional instruction that needs to be processed adds one cycle to each of the processors finishing times, which means we could predict that three instructions would have the following results: Processor #1 Processor #2 Results 3 cycle 6 cycles While processor #2 will always take 3 more clock cycles than processor #1, we have to remember that its clock runs twice as fast. This means that processor #1 will run three clock cycles in the same amount of time that processor #2 will run six. Therefore, answer C is the correct answer. 3. Justification (Answer C): The easiest way to determine the time complexity of an algorithm is to look the loops. There are two loops and one is imbedded within the other so the time complexity is n2. Since we don’t know how big the list is we’ll say it has n elements. We know that the outer loop will run approximately n times, and each time the outer loop runs the inner loop will run n times. Therefore, the code inside the inner loop will run n * n times or n2 times, which is the run time complexity of the algorithm. 4. Justification (Answer D): The nth Fibonacci number is defined as the sum of the two numbers before it (n-1 and n-2). Answer D handles the recursive call properly since it calls the function with parameters n-1 and n-2. 5. Justification (Answer A): Answer A is correct; the recursive function will call itself with the same number multiple times. Let’s trace the function calls starting with the number 6. Fibonacci(6) Fibonacci(5) Fibonacci(4) Fibonacci(4) Fibonacci(3) Fibonacci(2) Fibonacci(3) Fibonacci(2) Fibonacci(3) Fibonacci(2) Fibonacci(1) Fibonacci(2) Fibonacci(1) Fibonacci(2) Fibonacci(1) As you can see, the function was called to compute the value of the 3rd Fibonacci number 3 times and the 4th Fibonacci number 5 times. One interesting thing is that if you count the number of times the function is called with value 6, then the number of times with value 5 and so on, you end up with the sequence: 1, 1, 2, 3, 5 Another Fibonacci sequence! If you do this for even larger starting values you would see that the Fibonacci sequence continues just as we would expect. This means that if we called the function to find the value of the 19th Fibonacci number, it would compute the value of the 5th Fibonacci number 610 times! 6. Justification (Answer E): Hard drives can hold a lot of information and are very cheap (relative to ram and cache) but they are also very slow. Because of how slow hard drives are, the memory hierarchy was created. Hard-drives are still needed today because they are a cheap means of storing masses of information. 7. Justification (Answer D): Class P algorithms are algorithms that can find a solution to a problem in polynomial time ( O(n), O(n2), …). Class NP is a class of algorithms that do not complete in polynomial time (O(2n), O(n!), …). Many people are working on finding algorithms that solve the problems in the NP class but complete in polynomial time. Determining whether or not this is possible for all the NP algorithms in therefore very important. 8. Justification (Answer E): O(n) is one of the fastest category of algorithms. O(n!) is one of the slowest categories. While O(n logn) is still a fast group of algorithms, they have a larger time complexity than the O(n) group) A simple way of determining which category is faster is to plug in a number, say 7. O(n): 7 O(n logn): 19.6 O(n!) 5040 9. Justification (Answer D): Answer choices A and B are both correct. Answer C is incorrect. When you use an interpreter, there is no machine code executable created. The translator must still translate the code into machine language. It simply does this on the fly each time the program is run. 10. Justification (Answer B): Since the memory transfers data between different levels in blocks, writing code that uses information close together will minimize the number of blocks that need to be loaded. However, this does not affect the time complexity of your algorithm as far as big-oh notation is concerned.