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).

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)

Log2(4)

Log2(16)

Log2(-16)

e(loge 23)

10^1

102 ^-2

3 mod 3

5 mod 3

15 mod 3

10 mod 3

150 mod 3

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

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

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

(c) Compute how long it will take.

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

(a) Fibonacci series

(b) Bernoulli numbers

(c) Fitts' law

(d) Shannon's H

(e) Tower of Hanoi

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

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

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?

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

(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?

(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.

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

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.

(b) (6 points) Power sets

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

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

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

Given

1 1

2 1 1 1

3 1 2 3 2 1

4 1 3 6 7 6 3 1

5 1 4 10 .....

(a) Complete row 4.

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

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

(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.

(ii) What is the value of this sum?

(iii) Prove it using induction.

(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)

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