Homework 3: Read § 5.
Excercises § 4.6 # 1.a,d,j,m, § 5.9 # 4,7,9
Problem A: The Enigma Machine (watch) was used during WWII to encrypt messages character by character. Decrypting a message requires using the same machine setting as the encryption.
Determine the bigO complexity class of decrypting an Enigma encoded message by trying every possible setting in terms of the input alphabet size n=2k. (For English letters n=26, k=13). The setting cosists of 1) a choice of 1st, 2nd, and 3rd rotor from 5 rotors, each of which has n-rotary starting positions corresponding to the letters and 2) a 'plug setting' which swaps 10 pairs of letters with exactly one partner.
Due 15 Feb.
Homework 2: Read § 3 & 4.
Excercises: § 3.11 #3,4,12.
Problem A: Ten points are chosen inside a square with sidelength 1.
Prove that it is always possible to find a pair of points that are at most √2/3 apart.
(Hint: Make some square holes for your pigeon-points.)
Due 1 Feb.