Answers to COS 109 Practice Problems

Thu Jan 6 15:54:10 EST 2005

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.

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? 2^32 = 4*2^30 = 4 billion
  • How many IP addresses of the form 128.112.137.x are there? 2^8 = 256
  • How many Ethernet addresses are there? 2^48 = 256 * 2^40 = 256 * 10^12
  • How many DES keys are there? 2^56 = 64 * 2^50 = 64 * 10^15
  • How many IPv6 addresses (128 bits) are there? 256 * 2^120 = 256 * 10^36
  • How many 256-bit AES keys are there? 2^256 = 64 * 2^250 = 64 * 10^75

    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 2^32 = 4.3 billion, so 33
  • 280 million Americans 2^28 < 280M < 2^29
  • 2000 grad students 2^10 < 2000 < 2^11 = 2048, so 11
  • 700 faculty 2^9 < 700 < 2^10, so 10
  • 11 eating clubs 2^3 < 11 < 2^4, so 4
  • residential colleges (before Whitman, after Whitman) 4 colleges = 2 bits, 5 = 3 bits
  • 4-digit local telephone extension 609-986-.... 10000 numbers, so 14
  • 7-digit local telephone number 10 million numbers, so 2^4 * 1 million, or 2^24: 24 bits
  • 3-digit area code 1000 numbers, so 10 bits
  • the 50 items on the menu at Hoagie Haven 6 bits
  • 24 hours in a day 5 bits
  • 365 days in a year 9 bits
  • 100 years in a century 7 bits
  • human age in years 7 bits up to age 127

    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 33
  • 280 million 29
  • 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 2^5 = 32
  • fingers and toes 2^20
  • fingers and toes if you were a 3-toed sloth 2^12 (assuming sloths have 4 3-fingered legs)
  • optical telegraph with 6 shutters 2^6
  • optical telegraph with 9 shutters 2^9
  • a pair of signal lights, each on or off 2^2
  • n signal lights, each on or off 2^n
  • 16-bit port number in a TCP packet 2^16
  • 16-bit length field in an IP packet 2^16
  • 8-bit instruction field for some machine: how many instructions can the machine have? 2^8
  • 6-bit instruction field for some machine 2^6
  • 32-bit addresses used in some computer: how many bytes of memory 2^32 can it reference?

    Bit patterns and arithmetic

    How many 1-bits are there in the binary representation of
  • 2^n 1
  • 2^n - 1 n
  • 2^n + 1 if n > 1 2
  • 2^m + 2^n if n is not equal to m 2

    What can you say about the binary representation of a number divisible by 2? 4? 8? ends in 0, 00, 000

    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? F
  • EE or EF? EF
  • ED or EE or EF? Put these in numeric order. they are already
  • DE or EE or FE? ditto
  • A9 or 9A? 9A A9
  • A9 or 9B or 9F? 9B 9F A9
  • DEADBEEF or CAFEBABE or F000BAAA? CAFE..., DEAD... F000...

    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 r, g
  • ACCEDE b, r
  • DECADE r or b, g
  • C0FFEE g, r
  • B1FFED g, r
  • 10D1DE b, r
  • 0FF1CE g, r
  • CADD1E g, b
  • BA0BAB r, g
  • B0D1CE g, b

    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? min(x,y) 

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

    What value does this store in w? absolute value of x 

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

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

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

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

    	n = 1			n = 2
	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.