Write-Once-Memory.writetwice/writetwice.html
[Present in class, starting with a brief description and the table.
Try to get them to figure it out.
Give them access to the page above.
Questions in Rec01.]
Fitting bolts and nuts together.
Use partitioning in a way similar to quicksort.
See ../bolts/bolts.html
Fake coin weighing problem.
Start with n coins, all the same except for one
which is lighter than the others. We have a scale which will
compare any two piles of coins. Obvious binary division
problem, with time bound of log2 n,
but not obvious that it is a ternary division
problem, with time bound of log3 n.
[From Levitin's book. See
fakecoin/fakecoin.html.]
Fibonacci Matrices, Part 1. The matrix {{0, 1} {1, 1}} and how powers of it
give the Fibonacci numbers:
fibmat/fibmat.html
[Talk about in class. Multiply it a couple of times in class,
and have them discover the Fibonacci numbers
in powers of the matrix. In a rec, perhaps Rec02, ask
them to prove the result by induction. Supply the
multiply 2 x 2 matrices code, and ask them to use it
to calculate the powers from 1 to 10. Talk about returning
a matrix in C, Java, C++. The page to give them about multiplying
matrices is: fibmatj/matmul.html.
Ask them if the matrix {{1, 1} {1, 0}} would work just as well
for producing Fibonacci numbers.]
Newton's Method, Part 1.
Newton's Method in calculating the square root of 2:
[Go over basic idea in class. Have them write a program for it.
Have them try initial guesses that lead to bad behavior.
Show them that you get double the digits at each iteration.
See newton/newtons.html.]
Transmitting half a bit, Part 1.halfbit/halfbit.html
[Talk about in class, and then give them access to the page.
Add a few questions to the current rec. Talk about other
cryptographic protocols. Talk about how difficult protocols
are, how prone to disaster, how hard to prove correct, and
how necessary that is.
Ask them if one could start with either "not 00" or "not 11"
and get also get a protocol that works.]
Balanced Ternary Numbers.
[Start by imagining 3-state computer storage:
flip-flap-flop instead of flip-flop. Introduce this weird version
of base 3 and state some of its amazing properties.
See ../ternary/baltern.html.]
Fibonacci Matrices, Part 2. Special formulas come
from squares of Fibonacci matrices:
See ../fib/fibweird2.html.
[Go over the idea in class. Have them use previous code to
try selected squares. Have them work on the formula
itself for some rec. Really cool formulas fall out.]
Newton's Method, Part 2.
Newton's Method for the golden ratio:
[Go over basic idea in class. Tell them that the same
crazy formulas for Fibonacci numbers will fall out.
See newton/fibonacci.html.]
Transmitting half a bit, Part 2.
Use of exclusive-or and random numbers. [Go over formulas for xor.
Show how to transmit a bit in two stages. Extend to files,
to more than two stages. Cryptography in the cold war.]
Exclusive-or and von Neumann's biased coin flip.
[Go over formulas for xor. Show how you can get unbiased
random numbers from a biased coin.]
Merkle's puzzles. ... as a prelude to public-key cryptography:
Test Comparing Binary, Ternary, and
Fibonacci Search:
With Ternary Search,
the idea is to mimic binary search, but divide the
array into 3 parts. Then decide which third of the
array has the desired element.