COS 109 Practice Problems

Sun Oct 22 19:14:52 EDT 2006

A number of people have asked for more practice problems, to help with the kinds of questions that seem to recur on problem sets and exams. As I've said to several of you, it's so hard to invent good exam questions that I hate to give away professional secrets, but at the same time, the goal is for people to learn the material. So I will try to put things in this file that might be helpful. Most are sketchily explained, and just for drill.

And this list is for the whole year, so some of these won't make sense until later. Give them a shot anyway.

I'll try to add to this page as things occur to me, so check it out from time to time.

Powers of two and ten

Powers of two and of ten recur, often in questions about how long it takes for something to become 1000 or 1000000 times bigger or smaller, or to figure out how big some binary number is. These are all easily done with almost no computation if you are completely familiar with the fact that

2^10 = 1024 ~ 1000 = 10^3

2^20 = 1024^2 ~ 1000000 = 10^6

etc.

Count by 10 on the one side and by 3 on the other. The approximation gets worse as the exponents get bigger, but it's good enough for any question that will arise in this class. For practice, give approximate decimal answers for these:

How many IPv4 addresses are there?

How many IP addresses of the form 128.112.137.x are there?

How many Ethernet addresses are there?

How many DES keys are there?

How many IPv6 addresses (128 bits) are there?

How many 256-bit AES keys are there?

Don't forget that you can factor; for example, 2^24 is 2^4 * 2^20, or close to 16 * 10^6.

Bits, bytes and binary

A lot of questions are basically the same thing: how many bits does it take to hold numeric values up to a maximum value (number of freshmen, number of undergrads, 7-segment display, fingers of both hands, IP addresses, ...). These are all the same question! Figure out how many things there are (given or computed), then figure out what's the largest power of two that is at least that big.

For practice, how many bits for

6.5 billion people

280 million Americans

2000 grad students

700 faculty

11 eating clubs

residential colleges (before Whitman, after Whitman)

4-digit local telephone extension 609-986-....

7-digit local telephone number

3-digit area code

the 50 items on the menu at Hoagie Haven

24 hours in a day

365 days in a year

100 years in a century

human age in years

The value you are computing here -- how many bits does it take -- is also the log (base 2, and rounded up) of the number of items. So what is the log base 2 of

6.5 billion

280 million

etc.

If the question also asks for bytes, then round up the number of bits to the next multiple of 8 (e.g., 1-8 bits = 1 bytes, 9-16 bits = 2 bytes, and so on).

Sometimes the specific assignment of bits to values has numeric significance -- you really do want to do arithmetic or compare smaller and bigger. In that case, remember that n bits stores 2^n distinct values which will take on the numeric values 0 through 2^n - 1 inclusive.

The other way around is to compute how many and what values you can represent with something that uses bits. How many different values can you represent with

fingers of one hand using a binary encoding

fingers and toes

fingers and toes if you were a 3-toed sloth

optical telegraph with 6 shutters

optical telegraph with 9 shutters

a pair of signal lights, each on or off

n signal lights, each on or off

16-bit port number in a TCP packet

16-bit length field in an IP packet

8-bit instruction field for some machine: how many instructions can the machine have?

6-bit instruction field for some machine

32-bit addresses used in some computer: how many bytes of memory can it reference?

Bit patterns and arithmetic

How many 1-bits are there in the binary representation of

2^n

2^n - 1

2^n + 1 if n > 1

2^m + 2^n if n is not equal to m

What can you say about the binary representation of a number divisible by 2? 4? 8?

Hexadecimal

Hex is just a notational shorthand for binary! It uses a distinct "digit" to represent each of the 16 values that are possible with 4 bits (see above). The digits are 0..9, A..F. Honest, that's all there is to it.

Write out the decimal numbers from 1 to 100 in binary and in hexadecimal. Observe the patterns.

At what decimal value does a binary odometer of N digits wrap around? Try it for N = 2..10.

At what decimal value does a hexadecimal odometer of N digits wrap around? Try it for N = 2..5.

Just as binary has a numeric value, so does hex, derived from the binary value, or treated as a number in base 16.

What's bigger as a hex number, E or F?

EE or EF?

ED or EE or EF? Put these in numeric order.

DE or EE or FE?

A9 or 9A?

A9 or 9B or 9F?

DEADBEEF or CAFEBABE or F000BAAA?

Hex is used as a shorthand for binary values in places like RGB colors, ASCII and Unicode tables, instruction encodings for computers, and so on.

Which color is the strongest in each of these? Which is least?

FACADE

ACCEDE

DECADE

C0FFEE

B1FFED

10D1DE

0FF1CE

CADD1E

BA0BAB

B0D1CE

Programming

I won't ask you to write code, but I will ask you to figure out what simple code does, and I will ask you to identify and fix errors in short code sequences. I won't worry about syntax details so long as what you write is clear.

What value does this store in w?

	if (x < y)
		w = x
	else
		w = y

What value does this store in w?

	if (x < 0)
		w = -x
	else
		w = x

This is supposed to print 1, 2, 3, ..., 10. Fix it.

	n = 0
	while (n < 10) {
		print n
	}

This is supposed to print even numbers from 1 to 10 inclusive:

	n = 1
	while (n < 10) {
		print n
		n = n + 2
	}

Algorithms

There are only a handful of core algorithms and only a handful of running time expressions: log n, n, n log n, n^2, 2^n.

There are some physical properties that also depend on a linear dimension, notably area and volume. Don't forget that area grows in proportion to the square of the linear dimension, while volume grows in proportion to the cube.