University of California, Berkeley – College of Engineering Department of Electrical Engineering and Computer SciencesFall 2010 Instructors: Dan Garcia and Brian Harvey 2010-10-27CS10 Paper MidtermLast Name First Name Student ID Number cs10- Login First Lettera b c d e f g h i j k l mcs10- Login Last Lettera b c d e f g h i j k l m n o p q r s t u v w x y zThe name of your LAB TA (please circle) Jon LukeName of the person to your Left Name of the person to your Right All my work is my own. I had no prior knowledge of the exam contents nor will I share the contents with others in CS10 who have not taken it yet. (please sign) Instructions● Don’t Panic!● This booklet contains 6 pages including this cover page. Put all answers on these pages; don’t hand in any stray pieces of paper.● Please turn off all pagers, cell phones and beepers. Remove all hats and headphones.● Question 0 (1 point) involves filling in the front of this page and putting your login on the top of every sheet of paper.● You have 110 minutes to complete this exam. The midterm is closed book, no computers, no PDAs, no cell phones, no calculators, but you are allowed two double-sided sets of notes. There may be partial credit for incomplete answers; write as much of the solution as you can. When we provide a blank, please fit your answer within the space provided. Question 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Online TotalPoints 1 3 2 2 3 3 3 3 2 2 3 5 10 8 10 60ScoreShort-answer QuestionsQuestion 1 : A “sea-change” in CPU design occurred around 2004 and most agreed the “free lunch” was over. In one sentence, what caused it and what did manufacturers do in response? Question 2: You have a piece of code, half of which is executed serially, the other half is executed in parallel. In the ideal case with an infinite number of “helpers” dividing up the parallel portion, what is the overall speedup of your code? ______ Question 3: Let us imagine Twitter mandated that every one of their users “follow” every other user. How does the total number of “connections” between people (connections were visualized as arrows, or links in the graph) scale with the number of users? (a) It remains relatively constant, regardless of the number of people.(b) It scales linearly with the number of people.(c) It scales quadratically with the number of people.(d) It scales exponentially with the number of people. Question 4: In one sentence, how are search engines (e.g., Google) able to have a tweet available in their search results in less than a second after the tweet happens? (It normally takes a search engine hours to “crawl” the web and update their search index.) Question 5: Fill in the blanks with the appropriate technology that has changed the world. a) ___________________ is revolutionizing the way people collaboratively author documents. b) ___________________ and ________________ are a hardware and software combination that put professional-quality document production in the hands of the masses. c) The Internet was “invented” in 1962, but it wasn’t until 1993 when Marc Andreesen at NCSA introduced ___________________________ (known as its first “Killer App”) did its use explode. Question 6: Give an argument why educational microworlds might be preferable to either pure tools or pure courseware. Question 7: Besides obeying local laws, name one reason why Google makes deliberate (non-automatic) interventions in the display of search results. Question 8: Why did the writers of the US Constitution require a limit to the duration of patents?Login: cs10-____Question 9: The Giants win the Pennant! The Giants win the Pennant!Provide a single, simple expression that reports SF from the nested list playoffs. On the right is a screen capture of the Variables tab if that helps. Question 10: Faster, Puppydog! Live! Live! You wish to fill a list nums with the numbers from 1-100 (you don’t care about order). So, you write the following (the for block simply goes through like a repeat block with a built-in index, called i in this case): which works perfectly, but it’s a little slow. However, your friend asks “why don’t you break the problem into two parts and fill the list in parallel!” So, you duplicate that script, and adjust the numbers in the for loop like so: In the best case, this works! What happens (or could happen) in the worst case and why?Question 11: Talking’ about my gggggeneration... If you’ve ever spilled soda into a keyboard, you know that keys start to stick and repeat. We want to write a block to remove the extra consecutive repeat character we request, leaving only one. E.g., if the sentence were: I love CS10....... Me too....... Me three!!! ...and we asked our block to remove the extra “.”s, we would get: I love CS10. Me too. Me three!!! (We’ll limit this to punctuation, since the meaning could be lost if we used it on letters and numbers. Imagine: “The national debt is $10000000000000!!” would become “The national debt is $10!!”) We’ve tried to write code to do this for us, but we believe it has a bug. Briefly, answer and lastletter initialize to the empty character, and then the for loop (these were explained in question 10) sets letter to every character as we walk forward in the sentence. We only add that letter to the answer (which we report at the end) if the letter is not the character to remove and not the same as the previous character lastletter (to prevent the repeats). a) Describe all sentences that don’t trigger the bug, i.e., our program returns a correct answer. b) Briefly describe the small change(s) needed to fix the bug.Login: cs10-____Question 12: Two roads diverged in a wood... You’re lost in the forest. Every in the forest is either a dead-end or has exactly 2 one-way paths: left and right. Your goal is to find out if there is a way home. We introduce a new data type called a , but you don’t know (and you don’t need to know) how it is represented; it could be a string, a number, or a list. You are presented with four new blocks, two predicates and two reporter blocks (all take a place as an argument):● returns if the is your home, otherwise. ● returns is the place is a dead-end (i.e., no paths from it). ● follows the left path, returning a new . ● follows the right path, returning a new .It is an error to or if is a dead-end