======================================================================== Final Review Questions Spring 2008 ======================================================================== 1. Two programs were defined as being equivalent if, given the same input they always produced the same output. Assume the core of program One consists of x = 2 * x * x + 1 x = x / 2 + 1 print x Assume the core of program Two consists of x = x * x + 1 print x Are these two programs equivalent (ignoring implementation problems like integers getting too large to be stored in a register, etc)? a) They are equivalent. b) They not are equivalent. c) The second program doesn't work for negative numbers. d) The first program can't handle input of zero. 2. Given the function def func(a,list): c = 0 a = list[0\] k = 1 while (k <= 10): if (list[k] == a): c = c + 1 k = k + 1 return c The function above takes a list containing at least 11 integers. It returns c. What is the significance of the value of c in relation to values in the list? a) It is the number of times the logical expression in the if was true. b) It is the number of times the loop body was executed. c) It is the number of times the first number in list matches the next 10 numbers. d) It is both a) and c) but not b). 5. Which of the following statements best indicates what is necessary to avoid writing an infinite while loop? a) The body of the loop must contain an if statement. b) At least one function/method must be called in the body of the loop. c) Something in the body of the loop must cause the value of the logical expression following the "while" to change. d) The statement k = k - 1 must always be present. 6. Lists make it easier to solve certain programming problems. Others don't need lists at all. Check off the following to indicate whether or not arrays are need. (need)(not need) a) Find the larger of two numbers. (need)(not need) b) Sort a list of names. (need)(not need) c) Create a "Used Car" database. (need)(not need) d) Decide whether a number is odd or even. (need)(not need) e) Count the number of data points read. (need)(not need) f) Count the number of factors for a number. 7. Below is part of a Python program. Show what the list "data" will contain after this code is executed by filling in the boxes below. size = 10 data = range(10) k = 0 m = 3 x = 0 while (k < size): data[k] = x if (x > m): x = 0 else: x = x + 1 k = k + 1 0 1 2 3 4 5 6 7 8 9 ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- data: | | | | | | | | | | | ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 10. Assume that the program above continues with the code that follows and that the numbers you just wrote into data are still there. Show what will be displayed after this code runs. k = 10 max = data[0] min = data[0] while (k > 0): k = k - 1 if (data[k] < min): min = data[k] if (data[k] > max): max = data[k] print "Stats: max = " + str(max) + ", min = " + str(min) 12. Assume we have another program which we have run for several moderate test values of N (say 50) and it finishes in a second or two. Now we want to put the program into production with its full load of 500 cases. We notice that program keeps churning away, giving no signs of completing. After eight hours we go home. The next morning it's still grinding away. We stop the program to consider what's gone wrong. What would you suggest has happened. (Mark all that seem plausible at this point.) a) The program uses an exponential algorithm. b) The logarithmic algorithm being used has finally caught up with us. c) It's an example of being too tractable. d) There's a bug in the program and it has gotten into an infinite loop. 14. Add the following binary numbers and give their sum and difference in binary: 1 0 1 0 1 1 0 1 + 0 1 0 1 1 1 1 1 --------------- 1 0 1 0 1 1 0 1 - 0 1 0 1 1 1 1 1 --------------- 16. True/False? (2) Integrated circuits can have over one million transistors on one chip. (3) Many of the modern user interface ideas originally came from Xerox. (5) Most modern operating systems no longer support multi-programming. (6) Virtual memory is a way of simulating extra memory by using disks. (7) Cache is used to keep frequently used information closer to the CPU. 8) Cache memory is larger but slower than main memory (RAM). 9) Modern operating systems worry about not letting the computer be idle because computer time is a precious resource. 10) A word processor is an absolutely essential program for an operating system to provide. 11) Being able to access your files from many different machines is provided by the operating system through a network file system. 12) Cache memory is used to make main memory (RAM) seem faster. 13) For public key encryption, the private decryption key is actually made public rather than being kept a secret. 14) One time pads, properly used, produce code that is absolutely unbreakable (without the proper pad). 15) Using one time pads, only the recipient (not the sender) needs a "pad:. 16) If strong encryption is used and the key (password) is lost, you have to consult with your local hacker to get the data back. 17) How was the Content Scrambling System (CSS) for DVDs fatally flawed as a security scheme from a technological, policy, and legal perspective? 18. Assume we have yet another program which we run for several small values of N. We notice that every time we increase N by one, it takes three times as long to run. Circle the following term that we might reasonably use to describe the behavior of the program for large scale problems. not-suited-for-computer-solution just-right-for-computers 21. What is the difference between Python and Jython? 24. What does acronym HTML stand for? What do the terms mean? 25. What tags can you use to skip to the next line in HTML? 26. #0000FF is a color code for? 27. Briefly discuss the following - HTTP - TCP/IP - IP - DNS What is a - Server - Client 28. What are spatial and temporal locality and describe an application of each? 29. How does the sampling rate affect the fidelity of a digital sound compared to its original analog source? 31. Write a function fadeAway that fades the last second of a sound to silence. You can assume that the sound passed in will be more than 1 second in length. 33. What is patentable? How does a patent differ from a copyright? What does it mean for software to be patentable? How is code copyrighted? 34. Is Free Software copyrighted? 35. Why is there no significant "Free Hardware Movement" analogous to the Free Software Foundation's work? 36. What is base rate fallacy and how does it affect applications of data mining and biometrics for national security? 38. What disadvantages are there for the user for biometrics in comparison to other identification schemes? 39. What is network neutrality? What is the alternate option to a neutral Internet? Who would support each side? 41. How can the following contribute to copyright infringement? - Digital media (audio or video) - P2P file sharing - MP3 42. What is a EULA? What does a user purchase when they purchase software? 43. Since it is impossible to verify completely the accuracy of complex programs, under what circumstances, if any, should the creator of a program be liable for errors? 44. Why have open source projects such as Linux or Mozilla been successful? What do providers of open source software sell? 45. What is Metcalfe's Law and what does it say about the worth of the Internet now as compared to before the mid-1990s? 46. Consider the layers on top of the hardware of a machine: CPU, instruction set architecture, operating system, programming languages, and applications. What is the purpose of each layer? What abstractions does each represent and implement? 47. What limits parallel or distributed computing? Why can't we just add more computers and solve any problem faster? 48. What is a bus? 49. Why is clock speed not a good measure of computer performance? 50. What are the three steps of a CPU clock cycle? ========================================================================