Name:__________________ (printed)

Alias :__________________

Section :__________________

Please write your alias on each page. This exam should have 10 pages. Check before starting that it does.

The exam has 81 points (to be scaled to 20% of the course). **NB-- this exam
is about 50% too long, but this gives you additional examples of work.**

Calculators and computers are not allowed nor are they required for these problems. If you think they are, you have done the problem wrong or do not understand logs very well. If this happens, leave your answer with the logs in place. For example, log10(3) rather than 0.48 .

Show your work. Corrent answers with derivations count for little.

If you finish early, you should wait for it to be picked up, and then you may leave.

Question N Value Result

1 6

2 10

3 10

4 10

5 11

6 10

7 9

8 10

9 6

Total 81

Log2(2) = 1

Log2(4) = 2

Log2(16) = 4

Log2(1/16) = -4 (log2(-16) is a typo, but a good answer is that it's undefined, at least for this course)

e^(loge 23) = 23

10^1 = 10

102 ^-2 = 1 / (102*102) or about 1/(100*100) or about 1/10,000

3 mod 3 = 0

5 mod 3 = 2

15 mod 3 = 3 mod 3 * 5 mod 5 or 0 * 5 mod 3 = 0 mod 3

10 mod 3 = 1 mod 3 (by substracting or counting, or making a 3-clock, etc.)

150 mod 3 = 0 mod 3 (by division 150=3*50 + 0, or by 3 mod 3 * 50 mod 3 = 0 * 50 mod 3 = 0

Assume that the user's mouse starts in the middle of a computer screen and has to selet an item on the menu bar (i.e., move and click on a button there).

(a) What else do you have to know to predict how long it will take?

you need the relative sizes of the menu and the screen. their units will cancel out.

(b) Provide some estimates of what those numbers are for your favorite computer.

I would choose about 7.5 fingers from centre of screen to centre of menubar, and about 1 finger of width of the menu bar. (This makes the math easy!)

(c) Compute how long it will take.

Time to move will be 100 ms (log2( 7.5/1 + .5)) = 100 ms (log2(8)) = 100 ms 3= 300 ms,

plus about 150 ms to click, or about 450 ms total.

(d) How much does this time change if you double the size (height and width) of the menu item?

It changes slightly, you might get it to log2(4) which would be 200 ms to move, with the same click time.

(a) Fibonacci series

As per the book, note the equation, and explain the terms.

(b) Bernoulli numbers

See (a)

(c) Fitts' law

The time to move a mouse to a target. There are several versions. T = 100 ms. log2( Distance/width + 0.5) is an early and pretty common version.

It implies that the time to move to a target is proportional to the log of the ratio of the distance divided by the target width. Longer distances lead to longer time, and larger target sizes lead to shorter times. There is a minimum time that the 0.5 is attempting to model.

(d) Shannon's H

A measure of the diversity or information necessary to code an object from a set of objects. Defn mathematically is the negative sum across all objects of the probability of each object times the log2 of the probability.

(e) Tower of Hanoi

A problem often used in discrete math and related mathematically to many others, including the simple task of swapping variable values in a program.

(a) Prove by induction that the sum of the cubes of three consequative integers is divisable by 9.

n^3 + (n+1)^3 + (n+2)^3

Show this is true for n=1 1^3 + 2^3 + 3^3 = 1 + 8 + 27 = 36, which is 4*9, so true for n=1

Assume n^3 + (n+1)^3 + (n+2)^3 = 9w, show that

(n+1)^3 + (n+2)^3 + (n+ 3)^3 = 9x

(n+1)^3 + (n+2)^3 + (n^3+9n^2+9n+9) = 9x

n^3 + (n+1)^3 + (n+2)^3 + 9n^2+9n +9 =9x (move the n^3 around)

9w + 9n^2+9n +9 = 9x (subsitute assumption)

All terms are divisible by 9, so result is divisible by 9.

(b) Prove by induction that the product of any three consequative integers is divisible by 3.

n * (n+1)*(n+2) = 3 w

show this is true for n = 1, 1*2*3 = 6, which is divisble by 3

Assume that

n * (n+1)*(n+2) = 3 w

show that

(n+1) (n+2) (n+3) = 3z

Note that from modulo arithmetic that one of n, n+1, and n+2 must be in the congruence class of 0 mod 3.

With the shifting up of adding one, n+1, n+2,n+3 will either include a 0 mod3 as n+1, or n+2 again, or if the number that is 0 mod 3 was n, then n+3 will be the number that is 0 mod 3. A number that is 0 mod 3 multiplied by other numbers remains 0 mod3 , or thus a number divisible by 3 with no remainder.

There should also be a proof doing the expansion.

The Illinois Alumni Association sells Illini paraphernalia. Over homecoming weekend, they sold 20,000 bumper stickers, 36,000 window decals, and 12,000 Chief key rings. Of 60,000 fans who attended the game, 6,000 bought both decals and key rings; 9,000 bought both decals and bumper stickers; and 5,000 bought both key rings and bumper stickers. We know that 52,000 fans bought at least one item, and no bought more than one of a given item.

(a) (3 points) How many fans bought all three items?

Abs = 20k Awd=36k Ackr=12k Z=60k

|Awd intersect Ackr| = 6k |Awd intersect Abs| = 9k |Ackr instersect Abs| = 5k

|Abs union Awd Union Ackr | = |Abs| + |Awd| + |Ackr| - |Abs intersect Ackr | - |Awd intersect Ackr| + |Abs intersect Awd intersect Ackr |

52k = 20k + 36k + 12k - 6k -9k -5k + |Abs intersect Awd intersect Ackr|

|Abs intersect Awd intersect Ackr| = 4

(b) (3 points) How many fans bought exactly one item?

Total - # of doubles + 2 (# of triples)

= 52k-6k-9k-5k + 2(4k) = 40k

(c) (3 points) There were conflicting reports of the total number of purchasers. We heard that there were either 60,000 purchasers, 52,000 purchasers, or 44,000 purchasers in all. Which of these figures is most likely to be correct and why?

[There are longer explanations noting how these other numbers don't add up, but that 52k does add up. One might also note that this was in the problem but that is hardly demonstrating any knowledge.]

(d) (3 points) 1-1 and onto

Define a set A and set B such that the set of A is 1-1 with the set of B.

A = { 1 2 3} B = {1 2 3 4} Let the relation be A+1, and thus every element in A maps to B and in a unique way.

Define a set A and set B such that the set of A is onto with the set of B.

A = {0 1 2 3 } B = {1 2 3 4} Let the relation be A+1, and thus every element in B has been mapped to by at least one element in A. This set is also 1-1, so they are in a one-one correspondance.

Define a set A and set B such that the set of A is 1-1 and onto the set of B.

(a) (4 points) Assume that the Ritter numbers R1, R2, ... RN have the initial values R0=3 and R1=1 and the recursion RN =R(N-1) + R(N-2). Computer the Ritter numbers for N=0 to 10.

N R(n)

0 3

1 1

2 4

3 5

4 9

5 14

6 23 etc. like the fib series

(b) (6 points) Power sets

(i) Define the power set of a set S.

The set of all subsets of a set S.

(ii) When is the empty set in the power set of of a set S?

The empty set is always a member of the powerset of S.

(iii) How many elements does the power set of a set S with N elements have?

2^n

Given

0 1

1 1 1 1

2 1 2 3 2 1

3 1 3 6 7 6 3 1

4 1 4 10 .....

(a) Complete row 4.

16 19 16 10 4 1

(b) Give a formula or recursive relation that defines element k in row n

( n k) = (n-1 k-1) + (n-1 k) + (n-1 k+1)

(c) Prove by induction that the nth row of this triangle consists of the coefficients of powers of x in the expansion of (x^2 + x + 1) ^n

Show for n=1, 1 1 1 is the same as (x^2 + x + 1) ^n

Assume that it is true for (x^2 + x + 1) ^n, show for (x^2 + x + 1) ^n+1

With paper, it's easier to write out, but the terms for (x^2 + x + 1) ^n+1 will be equal to (x^2 + x + 1) ^n * (x^2 + x + 1), which will effectively generate the equation in (b) above.

(a) (5 points) The sum of binary numbers. You may hear that more computers are available now than in the total of the past.

(i) Use summation notation to express the sum of powers of 2 from 2^0 to 2^N.

Sum from i=0 to N, 2^i (done with symbols)

(ii) What is the value of this sum?

try out 0=> 1

1 => 1 + 2=3

2 -> 1 + 2 +4 =7

3=> 1 + 2 + 4+8 = 15

How about (2^(n +1) - 1)? It works!

(iii) Prove it using induction.

Set up the base case, N=0, 2^0

Assume that 1 + 2 + ...2^n = 2^n+1 - 1

Prove 1 + 2 + ...2^n + 2^(n+1) = 2^n+1 - 1 + 2^(n+1)

= 2^n+1 - 1 + 2^(n+1)

= 2 * 2^n+1 - 1

= 2^((n+1)+1) - 1 you can see that the formula applies, but with n+1 replacing n

(b) (5 points) The moves of the Tower of Hanoii

Compute the number of moves to solve an N disk 3 peg problem. (show your work)

Well, with one disk, it takes 1 move.

with 2 disks, it takes 1 move to move the top disk, and 1 move to move the bottom, and one move to movethe top disk over.

With 3 disks, it takes the number of moves to move 2 disks to clear the bottom disk, one move of the bottom, and Moves(2) again.

So, it looks like Moves(N) = Moves(n-1) + 1 + Moves(n-1)

Moves(n)= 2*Moves(n-1) + 1

Moves(1) = 1

Moves(2) = 3

Moves(3)= 7

Moves(4) = 15 ? looks like 2^n -1 again. [also see p. 15-17 of Washburn!]

Create an interesting knapsack problem (N>3). Show how to solve while finding the best solution.

[see several of the homework web pages]