Due 5:00 PM, Wednesday, Oct 8, in the box outside Room 311, CS building, or in class. Answers need not be long, merely clear so we can understand what you have done. Please submit typed material, not hand-written, if at all possible, and keep a copy for yourself just in case something goes astray. Thanks.
|
Collaboration policy for COS 109:
Working together to really understand the material in problem sets and
labs is encouraged, but once you have things figured out, you must part
company and compose your written answers independently. That helps
you to be sure that you understand the material, and it obviates questions
of whether the collaboration was too close.
You must list any other class members with whom you collaborated. |
(a) Suppose (to make the numbers easy) that an integrated circuit chip from 1984 used feature sizes of 3.3 micrometers; today typical chips have feature sizes of about 22 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 a 1984 chip 1 cm x 1 cm had 100,000 transistors, roughly how many would fit in the same area using today's feature sizes?
(b) One of my laptops has a 13.5 inch screen (measured diagonally), while the iMac in my office has a 27 inch screen. Assume that the pixels are the same size on both displays and the aspect ratios are the same.
(i) If the larger display has 6 M pixels, about how many pixels are there on the smaller display?
(ii) If the displays use 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 smaller display?
(c) An article from several years ago reported that IBM planned to build a new factory to make integrated circuits (at a cost of $2.5B). This factory was going to produce wafers that are 12 inches in diameter. Supposing that there are 200 chips of a particular type on an 8-inch wafer, and assuming that everything else is unchanged, approximately how many chips of that type will there be on a 12-inch wafer?
(a) Suppose an algorithm takes 0.79 msec to process two items, 2.71
msec to process three, 6.38 msec to process four, and 12.52 msec to
process five.
(i) About how long is it likely to take to process
one item?
(ii) About how long is it likely to take to process
six items?
(iii) How does the running time appear to be growing
as a function of n, the number of items?
(b) Supreme Conflict, a 2008 book on the Supreme Court,
describes how before each session each of the nine justices shakes hands
with all the others.
(i) What is the total number of handshakes?
(ii) If there are n people doing handshakes,
how does the total number of handshakes grow in proportion to n?
(a) During a WWS talk in February 2014, FTC commissioner Julie Brill said that "a trillion gigabytes is equivalent to every American sending 3 tweets a minute for 27,000 years." Right or wrong, and why?
(b) The US budget for 2014 was $3.77 trillion. How many bits would be required to store this number? How many bytes?
(c) The national debt right now is larger, just over $18 trillion. How many bits and bytes would be required to store that number?
(d) Facebook claimed in December 2013 that 757 million users logged in each day during the month. How many bytes are necessary to store the count of unique logins each day?
(e) "Party like it's 00110001001110010011100100111001". When is that?
(f) "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?
(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.
(g) How old is Cecilia, in decimal, binary and hexadecimal?