University of California, Berkeley – College of Engineering Department of Electrical Engineering and Computer Sciences Spring 2011 Instructor: Dan Garcia 2011-03-31 CS10 Paper Midterm Last Name First Name Student ID Number cs10- Login First Letter a b c d e f g h i j k l m cs10- Login Last Letter a b c d e f g h i j k l m n o p q r s t u v w x y z The name of your LAB TA (please circle) Glenn Luke Navin Name 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. ● 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 1 2 3 4 5 6 7 8 9 10 11 12 13 Online Total Points 2 2 2 2 2 2 2 2 2 6 6 10 10 10 60 ScoreShort-answer Questions Question 1 : Here’s a friend’s position: “The young people of today of today use computers all the time. They are ‘digital natives’, comfortable with sending text messages, playing online games, browsing the web, and interacting with digital media. They have achieved ‘digital fluency’ ”. In one sentence, respond to this as if you were one of the authors of Scratch. Question 2: Multicore computers shift the burden of software performance from chip designers and processor architects to ___________________________. Question 3: GWAPs serve multiple purposes. The real measure of utility of a GWAP is both __________________________________ and ______________________________________. Question 4: “Theory” and “experimentation” were known, for years, as the twin pillars of science. What is the third pillar of science that Prof Yelick demonstrated? _________________ Question 5: The personal computer, laserwriter, graphic design software and the Postscript language combined to be remarkably democratizing, putting professional-quality print output (once reserved to pros in print houses) in the hands of the masses. Name another important democratizing technology (aside from those mentioned here), and who used to hold the power. Question 6: How would you best respond to your friend who says: “What’s the big fuss Raffi Krikorian from Twitter was making about his engineering team’s challenges? Sheesh! Tweets are only 140 characters … how hard can it be to send these around?” Question 7: Your non-technical friend asks how it’s possible that a generic search engine “Jen” can search the entire web and have an answer in a split-second, even though when they visit their OWN website it takes 5 seconds to load. How does Jen do it so fast? Question 8: Your friend says: “I host a few thousand illegally-downloaded songs on my server so others can listen to it. I’m not worried, how would anyone be able to find me, since there are so many others like me doing the same thing?”. Respond with some facts from Blown to Bits. Question 9: One of the things we’ve talked about in this class a fair bit is the unexpected consequences of technology. In 2001, Dean Kamen touted his Segway self-balancing electric vehicle (shown on the right, perhaps you’ve seen these around campus) as a personal transporter that would revolutionize transportation, especially in cities. If the general public widely adopted the technology, what do you believe is the worst possible negative consequence?Login: cs10-____ Question 10: Beethoven wasn’t the only great composer… We’ve provided some helper reporter blocks that work on both words and sentences. Block Description Word example Sentence example Middle Report the middle item of a word / sentence Unend Remove the ends of a word / sentence. Triple Triplicate a word / sentence Right Rotate a word / sentence to the right Left Rotate a word/sentence to the left Fill in the blanks below with only calls to the reporter blocks above: Middle, Unend, Triple, Right and Left so that the expressions evaluate correctly. Use the techniques from “Writing Scratch/BYOB code on paper”. E.g., would be written Right(Triple(Bears)) a) _______________________________(Go Bears and Beat Stanford)___ è ear b) _______________________________________________(ihigh)____ è highigh …you may use at most 5 reporter blocks for your answer to part (b)…Question 11: So there were these three brothers… Three brothers (A, B and C) go off into the world to earn money for the family, and earn 1, 2, and 4 dollars respectively. Their parents want to find out how much money the family now has (they start with $0), so they put a scrap of paper on the kitchen table that reads $0 and go up to bed. Each brother (when he returns home) is to add his amount to the amount on the paper and write the new sum on the paper. The problem is these brothers are bad at math and need to do the addition on a temporary scratch paper. The brothers take a random amount of time to copy the current amount onto their scratch paper and another random amount of time to do the math before copying the sum back over. We’ve tried to simulate this situation with code below: a) What is the name we give to this type of situation? ______________________________ b) What are ALL the possible final values of on the scrap of paper? _____________Login: cs10-____ Question 12: Respect the family… You are interested in finding the number of a person’s ancestors, that is, them, their parents, their parents' parents, etc. In their family, everyone has a unique name and couples are always recorded together -- if you find one parent, you've found the other. You are provided with three helper blocks (which access some global family tree): , and . All three take as input a single argument, a (however that is represented): • reports or depending on whether the system has found that person's parents (mother and father) or not. • reports that person's