Graded out of 28; median 21.5; graded by Taewook -------------------------- 1. Plus ca change... (a) The one and only integrated circuit chip that I ever designed, in around 1980, used feature sizes of about 3.5 micrometers; today's chips have feature sizes of about 32 nanometers. (The feature size measures the width of wires or the length and width of a transistor on an integrated circuit; you can think of the area of a transistor as feature size x feature size.) If my original chip had about 10,000 transistors, very roughly how many would fit in the same area using today's feature sizes? 10,000 or 12,000 roughly. The ratio of feature sizes is 3500/32, which is about 100 or 110, so the area of a feature is about 10,000 or 12,000 times smaller, so there are about 10^8 in the same space; 1.2 * 10^8 is ok, but not too much precision. (b) My Macbook Pro has a 13.3 inch screen (measured diagonally), while the iMac in my office has an almost 27 inch screen. Assume that the pixels are the same size and the ratio of height to width is the same on both displays. (i) If the smaller display has 1 M pixels, approximately how many pixels are there on the bigger display? 4M. The area is 4 times as big. (ii) If it uses the standard RGB representation of colors, how many MB of memory is required to hold the image of what's on the screen of the larger display? 12M. 4M pixels , 3 bytes each. + Full credit if students multiplies 3 to his/her answer for (b)(i), even if the answer is wrong (c) This video says that a new fiber optic cable transmits at 14 Tbps, equivalent to "2660 CDs or 210 million phone calls". + For simple arithmetic mistake, bit/byte error, and unit error, give 1 point. (i) Is the number of CDs much too big, much too small, or about right? About right. 2660 cd's * 600 MB/CD * 8 bits/byte = 12.8 Tbits. A CD is something between 600 and 700 MB, so anything in this range is fine. (ii) Assuming that 210 M is correct, what is the approximate rate in bits per second required by a single phone call? Explain your answers quantitatively. 14 * 10^12 / 210 * 10^6 = 66666, so call it 66 Kbps or 65 Kbps or the like. 2. Algorithm Analysis (a) Last month I programmed a version of an experimental algorithm that handles data in chunks of 100 items. It only took 10 seconds to process 100 data items, but 80 seconds for 200 data items, about 270 seconds for 300 data items, and 640 seconds for 400 data items. (i) How long is it likely to take for 500 data items? 1250 seconds (ii) How does its running time appear to be growing as a function of N, the number of items (e.g., N, log N, ...)? N^3 (b) Suppose that a particular algorithm took 10 milliseconds to process N items in the year 1990. Assuming that Moore's Law (speed doubles roughly every 18 months) applied smoothly to the improvement of computer speeds and ignoring all other factors, in what year might you expect the same algorithm to take 10 nanoseconds for the same N items? In what year might it take 10 picoseconds? Explain your answers briefly but in enough detail that we can tell how you got them. Speed increases by factor of 1000 every 15 years (10 doublings), so in 30 years (2020) we get from milliseconds to nanoseconds. In 45 years (2035) we get from milliseconds to picoseconds. + Give 1 point with good reasoning and simple mistakes. + Give 1 point for correct answer but no justification (c) If it takes one eon to play the Towers of Hanoi with 40 disks, about how many eons will it take to play with 60 disks? An expression is fine; there's no need to do arithmetic. 2^20 == 2^60 / 2^40 (d) Sports teams often perform a post-game ritual in which each member of one team shakes hands with each member of the other team. If there are N players on each team, how many handshakes are there? N^2 3. Bits, bytes, bases (a) Facebook claims 800 million users in October 2011. If each user is given a unique identifying number, how many bytes are necessary to store the id of an individual user? 4 bytes (30 bits) (b) "The surging popularity of the Twitter messaging service has broken at least one Twitter client application and affected another as a part of what is being called 'the Twitpocalypse.' Each message on Twitter is assigned a unique identification number. On Friday evening, the number of tweets exceeded 2,147,483,647" and as a result some programs stopped working properly. (Macworld.com, 6/13/09) (i) Computers often store and process integers with one bit to represent the sign (positive or negative) and the remaining bits to represent the value. What is the likely size of the integers being used by Twitter's computers, in bytes? 4 bytes (2^31-1) (ii) If the computer used a representation that assumed all numbers were positive (no sign bit), what would be the number where the value becomes too big? Use an expression; you don't need to compute it exactly. 2^32 - 1 (Or 2^32. This has to be exact.) (c) How old is Cecilia, in decimal, binary and hexadecimal? 27, 11011, 1B + 1 point for 28, 11100, 1C + 1 point if only gives one number among them.