COS 116 The Computational Universe Midterm This exam is 3 hours long and closed book and closed notes, except that you may refer to the pseudocode handout available from the course webpage. (You may wish to print it out before you start the exam.) No collaboration is allowed. Print and sign the honor pledge on the front page of your answers: "I pledge my honor that I have not violated the Honor Code during this examination." Your answers are due by Friday, March 17, at 5pm. You must give them to Ms. Donna O’Leary in Room 410 in the Computer Science building. If she isn’t there, slide your answerbook under the door. If you have any questions during the exam, you may contact the course staff at [email protected]. We can also be reached by phone: Prof. Arora: (609) 933-1050 (11am-9pm) Umar: (215) 584-5212 Dave: (617) 921-0813 For some questions, we suggest the number of lines in the answer to give you an idea of the level of detail we expect. You may exceed this suggested limit. Q1) Mention three distinct ways in which Brooks’ design of his robot Genghis differed from the robotics work until that point. (4-5 lines) Q2) Explain briefly what a universal Turing-Post program does. Give two other examples of universal programs or universal machines. A few were mentioned in class. (2-3 lines) Q3) Explain in 2-3 lines why the industry standard for CD-quality sound uses a sampling rate of 44.1 kHz. Why not less and why not more? Q4) What points were illustrated using snowflakes in class? (2-3 lines) Q5) How is citation analysis similar to web search? Why is traditional citation analysis not applicable straightaway to web search, and how does the CLEVER algorithm differ from it? (3-4 lines) Q6) Your physics friend is excited that she is learning the laws that govern the behavior of elementary particles. She explains her excitement thus: “Everything in the world is composed of these elementary particles. Once we understand the behavior of theseparticles, we should be able to predict everything in the world.” Explain in 2-3 lines how you would react to this. (You can leave out the issue of randomness.) Q7) Recall the spectrogram from Lab 4 (see figure below). Recall that the horizontal x-axis denotes time. Describe what the vertical y-axis represents, and describe what the colors appearing in such diagrams mean. (2-3 lines) Q8) Suppose we want to make the Scribbler move around the room indefinitely. It should move forward as long as it does not detect an obstacle. Each time it senses an obstacle, it should spin right for 0.5 seconds, and then continue moving forward. Does the following Scribbler pseudocode produce this behavior? If yes, explain why briefly. If no, explain why not, and provide the correct pseudocode together with any English explanation if necessary. Move Forward indefinitely If <Obstacle on Either Side> Then { Spin Right for 0.5s } Else { Move Forward indefinitely } END Q9) a) Define the binary logarithm (denoted in class by ). n2logb) What is the binary logarithm of 42? c) Give pseudocode to compute the binary logarithm. Assume the input is an integer stored in a variable called n. Your program has to print . n2logd) Estimate the running time of your
View Full Document