COS 109: Problem Set 5

Due 5:00 PM, Tuesday, Nov 14 by submission to drop box at
Answers need not be long, merely clear so we can understand what you have done. 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.

1. Estimation

(a) In 1981, I designed an integrated circuit chip that used feature sizes of about 6 micrometers; today's chips have feature sizes trending to 10 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 the original chip had about 10,000 transistors, very roughly how many would fit in the same area using today's feature sizes?

(b) My iPhone has a 5.5 inch screen (measured diagonally), while my desktop machine 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 iPhone has about 2M pixels, approximately how many pixels are there on the desktop machine?

    (ii) If the desktop uses the standard RGB representation of colors, how many MB of memory is required to hold the image of what's on its screen?

    (iii) The desktop actually has about 5M pixels. How much larger is a pixel on my desktop than on my iPhone?

(c) In this problem, we will work up an estimate of the computing power that Princeton undergraduates have

    (i) How much disk capacity do you have on your laptop and how much of this disk is not currently being used?

    (ii) Assume that all Princeton undergraduates have the same amount of available disk as you do and compute an estimate of the amount of free disk on the machines of all Princeton undergraduates.

    (iii) An hour of high definition video requires about 4.5 GB of storage. If we were to use all of the free disk space of Princeton undergraduates for storing video, how many hours of video would we be able to store? Convert this value to appropriate units (days, weeks, months, years, ... ) based on your answer.

    (iv) The Princeton network runs at about 100Mb/second. How long would it take to download all of the videos from student machines to a central server? You can assume that the full capacity of 100Mb/second can be used for this process.


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 40 seconds for 200 data items, about 90 seconds for 300 data items, and 160 seconds for 400 data items.

    (i) How long is it likely to take for 500 data items?

    (ii) How does its running time appear to be growing as a function of N, the number of items (e.g., logarithmic, linear, quadratic, ... )?

(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 over that interval, and ignoring all other factors, ...

    (i) In what year might you expect the same algorithm to take 10 nanoseconds for the same N items?

    (ii) In what year might it take 10 picoseconds?

Explain your answers briefly but in enough detail that we can tell how you got them.


3. A state machine exercise

One of the uses of state machines is to determine whether sentences in a language are valid. This is often used for determining if a statement in a computer language is valid but can also be used to determine if a sentence fits into a structure defined for sentences in English. In this problem, you will create a state machine to determine if sentences have a certain structure. The structure is that the sentence consist of a noun phrase followed by a verb possibly followed by a noun phrase. A noun phrase may begin with an article which is then followed by some number (zero or more) modifiers and then by a noun. A verb is simply that, a verb. Inputs will be identified by what they are: article or modifier or noun or verb. Articles are represented by A, modifiers by M, nouns by N, and verbs by V.

(a) Construct a state machine to determine if a phrase consisting of the characters A, M, N and V is a valid noun phrase.

For example,
AMN , MMMMMN , and AMMMN are valid noun phrases while AMNV , MAN , and AMNM are not.

(b) Construct a state machine to determine if a sentence consists of a noun phrase followed by a verb possibly followed by a noun phrase.

Examples of valid sentences are:

And examples of invalid sentences are:
VAMMN (no initial noun phrase), MANVMN (article comes after modifier in initial noun phrase), and AMVMN (no noun in initial noun phrase).