Brandon Bray's Contribution to Chaos
I originally found this on a website at Cambridge University. I've taken
the liberty of updating it to reflect a more Cornellian understanding of
Attempt five questions, including not more than two
from Section A, not less than three from Section B,
and exactly log2ne-kt from Section C,
where n is the number of people who seem to have written more than you, and t
is the temperature in the examination hall.
Answers must be tied up in separate bundles, marked J or X,
as you think appropriate.
Write on one line of each sheet of paper only, and attach five
blank sheets to each of the bundles, in order to waste as many trees as
There are twelve questions in this paper.
There are nine planets in the Solar System.
There is more than one way to skin a cat.
- Present an architecture for a simple mainframe, explaining the purpose
of the little lights on the front. Illustrate your answer by describing in
terms of fetch-execute cycles the execution of a small accounting package.
- A Boolean function F is given by
F = A v B
Give an expression for F in its simplest form. Now spend half an hour
wondering why this question is so much easier than all the others, and
trying to work out what you have missed.
- A self-starting two-up two-down JK flip-flop asynchronous decade ripple
counter is required. Discuss.
- Explain the operation of a NAND gate in each othe following
Which one causes there to be slightly more electron-positron pairs in the
valence band? Given that you're meant to be doing a Computer Science and
not a Physics degree, does it really matter?
- Explain what is meant by a stream (or lazily evaluated list).
Show how streams can be used in ML with monotonous regularity to produce
difficult Tripos questions.
- Consider the following ML functions:
fun p f s (t::h) = (f h) t s @ p (f p (r f))::q h
and q a b = (b a p (p q) a) b :: (q b);
(a) What is the ML type associated with p?
(b) What does the function p do?
(c) Why does it do it?
(d) How long does it take?
Show how much easier it would have been to write the function in C.
- Explain what it means for an ML function to be curried. Explain
what it means for a piece of lamb to be curried. Give the definition of an
ML function spicy that exhibits both these properties.
- Show how higher order functions can be used in ML to model
(a) the natural numbers,
(b) the fission process inside a nuclear reactor,
(c) just about anything you care to mention.
- Give a Stirling number of the second kind S(m,k)
image goes here
where j is an arbitrary integer, introduced to confuse you, and n
is the number of lines required to prove the result. You may assume n
to be large.
- State the principal of mathematical induction.
Use induction on the question numbers on this paper to show that the fact
that you can't do the first question means that you probably won't be able
to do any of the others either.
- The University President and his wife invite n Fellows and their
spouses to a party. After the party the President asks everyone (including
his own wife) how many people they shook hands with, and receives 2n+1
different answers. Derive expressions for
(a) the number of Fellows that get pissed off with the
President for asking stupid questions,
(b) the number of bottles of port they manage to get through at
the tax-payers' expense.
- Show that there is no known algorithm for answering exam questions.
Deduce that you are wasting your time trying.