1.a. (11 pts) Compute the sum of base sixteen numbers $829 + $CA8.
Give your answer in base sixteen.
Remember that $9 + $8 = $11, and $8 + $C = $14.
The answer is $14D1.
b. (22 pts) Compute the product of binary numbers 11011 x 1011.
Give your answer in binary AND base sixteen.
100101001 = $129.
2.a. (11 pts) A machine writes a stream of bits on a paper output.
It has a four bit register. It goes through a process: update the
register, write a bit, and repeats this process indefinitely.
A person observes that the bits repeat in a cycle.
What is the longest possible cycle for a four bit register machine?
16 = 24.
For a classical linear feedback shift register, the register
fill 0000 is always in a cycle of length one by itself, so the
maximum cycle of a four bit LFSR is 15. There are other
machines besides the classical LFSRs.
b. (22 pts)
The output of a certain four bit linear feedback shift register
begins 100111010.
Find the output cycle for this register (both the length and the bits).
3. Consider the following complexity classes relative to d:
I. O( dK), K > 0
II. O( Kd), K > 1
III. O( (log d)K), K > 0
IV. O( 1 )
where, in each case, K is a some constant independent of d.
A certain vault has d doors, one inside the next. Each door has a
single dial with one hundred positions. The combination for the vault
is a setting for the dial on each of the d doors. Each door can be
opened when its dial is set to the correct position, exposing the next
door -- or, ultimately, the fabulous treasure.
a. (11 pts) Let A(d) be the number of combinations available for this vault.
Which of I -- IV is the smallest class containing A(d)? Justify your
answer.
The number of dial positions on each door is 100. Every door has its
own key number. So A(d) = 100d.
A(d) is in class II (exponential functions), with K = 100.
b. (22 pts) Let B(d) be the time The Adversary requires to learn the
vault combination.
(The Adversary may operate the doors it can get to,
but may not use violence.)
Which of I -- IV is the smallest class containing B(d)?
Justify your answer.
The adversary can solve each door separately. Let t be the time to
try all the dial positions for one door. Let m be the time to
try one dial position for one door.
B(d) is between md and td. So B(d) is O(d1). This is
class I (polynomial) with K = 1.
Bonus. (10 pts) When the powers of 2 are written in ordinary decimal
notation,
it can be seen that 29999 has 3010 digits and
210000 has 3011
digits. Let S be the set {1, 2, 4, 8, ..., 29999},
that is, the ten thousand integer powers of two beginning with 20= 1.
Some elements of S begin with the digit 4, such as 4, 4096, and 222 = 4194304.
How many?