1.a. (11 pts) Compute the sum of base sixteen numbers $829 + $CA8.
Give your answer in base sixteen.
b. (22 pts) Compute the product of binary numbers 11011 x 1011.
Give your answer in binary AND base sixteen.
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?
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.
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.
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?