Homework 1. Possible answer


Frank E. Ritter

16 August 2000

Revised 27 August 2000

Design a computer. If you find the specification unclear, note that it unlear, how it is unclear, and propose clarifying information of your choice.

Your document is graded in a binary mode, either 1 point or 0 points, so please approach this assignment as a treat, not as a burden. It is designed to get you to think about the math involved in such decisions, and motivate the use of the math in the module. Your document should be prepared online so you can keep a copy, and could be as short as 1 page, may be up to two.

This exercise was designed to provide some useful context about what you would need to know to design a computer. It might also teach you a bit about open ended assignements. Everyone was told if they turned something in, that they would get credit, and they will or did. The better answers practiced their turning in home work skills. The really good answers looked at the syllabus and saw that there might be some application of the material to computer design. Poor answers fretted over the fact that the problem was open ended and that they could not possibly know the full, complete, and singularly correct answer.


There must be 10 different tones that can be used to alert the user. For saftey, they must be different in at at least two ways that you can prove.

We can note in passing that to do this we would have to know about the user, and how they hear. It turns out that you could find stuff on the web, for example, http://hyperphysics.phy-astr.gsu.edu/hbase/sound/db.html, which neatly ties in logrithms, the first topic of the course. Just about the same math applies to differences in pitch. Finding these results might take about 30 min. on the web or a similar time in the library, particularly if you asked a librarian. The results indicate that nearly any way of generating noise besides a buzzer with a fixed frequency will work.

The display must be able to display a map of the US showing the largest 100 towns.

A good answer here might note that there are displays common now with 800x1000 pixels. This gives the ability to put a dot up for each town, and there is enough space to put labels up as well.

The computer must be able to sort the largest 1,000, 10,000, and 100,000 towns on a variety of dimensions, and compute the fastest path between sets of them.

This turns out to be difficult to impossible to do with today's computers. The 1,000, and possibly the 10k are doable. The 100k is almost certainly not doable. The algorithms to solve this problem, end up taking time exponentially related to the size of the list. 2^1000 I can imagine being doable (but probably not in a reasonable time). at 2^10k and 2^100k, I think it can't be done. We will cover this problem, which is called formally the traveling salesman problem, in the section on graphs and algorithms.

The computer must be able to store, at lowest cost, ten million pages of text.

A good answer would measure how big the pages were in characters or as gifs, and then compute the size. If the pages were 500 words each, and each word was 10 characters, then 5k/page x 10M = 50 gig disk is needed. Compression might allow a smaller disk, but that would assume that the pages were not random characters, which is hard or impossible to compress.