2019 Term 2
Term 2 --- Week 1
Term 2 --- Week 1
8 : Peter : Proofs, Deduction, e.g. AM-GM inequality Ellen Contradiction, e.g. AM-GM inequality Contradiction, e.g. infinite number of primes Deduction, e.g. sum of 1+2+3+...+n=n(n+1)/2 Induction, e.g. the sum 1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6 Euclidean geometry proofs starting from axioms 9 : William : Introduction to algorithms, sorting (proof of correctness) Bubble sort, quick sort, Complexity10 : David : Analysing the game of covering rectangles with arbitrary size squares. Last person to move loses.11+12 : Kifan : Preliminary description of RSA. Ralph : History and creation of public key cryptography RSA encryption and decryption RHB encryption and decryption (multiplication vs exponentiation) Euclid's algorithm to break the latter Euler phi function, Euler's Theorem Magma experiments with RSA and Factorisation. Term 2 --- Week 2
Term 2 --- Week 2
8 : Peter : Observation that sum_{i=1..n} i^3 = T(n)^2. Proof by induction. Proof by deduction summing a standard nxn multiplication table two ways. (i) sum across rows then sum rows to get RHS (ii) sum i-th gnomon, (1), (2,4,2), (3,6,9,6,3), ... , to get i^3. Note that each gnomon divided by i is the sum of NW-SE diagonals of ixi squares filled with 1s ... hence i^2. Proof that n^2 = sum of 1st n odd numbers by picture. Doing algebra mentally : (k+1)^4 (16 product terms to be grouped, Pascal triangle) Inductive "proof" that in all groups of n people everyone has the same gender. Elementary Euclidean geometry proofs : parallelograms exist. 9 : William : Quicksort example exploring complexity Binary search complexity (depends on quicksort) Minimum spanning tree algorithms (Prim, Kruskal)10 : Ellen : Worked on problems involving invariants. Colouring, parity, modular and numerical invariants. Problems 1,7,10,11,12,14 from invariants worksheet.11 : Liam : Towers of Hanoi patterns. The traditional variant and a new sliding/rotating version.12 : Ralph : History of factoring algorithms. Lookup table, trial division, mod 6 residues, Fermat method, Eratosthenes sieve. Comparison of sieve methods using CEP.Term 2 --- Week 3
Term 2 --- Week 3
8 : Ellen : Worked on introductory problems involving invariants. For example, can one tile a chessboard with two opposite corners missing with 31 dominoes.9 : Peter : Proofs, Deduction, e.g. AM-GM inequality Contradiction, e.g. AM-GM inequality Contradiction, e.g. infinite number of primes Deduction, e.g. sum of 1+2+3+...+n=n(n+1)/2 Induction, e.g. the sum 1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6 Euclidean geometry proofs starting from axioms10 : William : Quicksort example exploring complexity Binary search complexity (depends on quicksort) Minimum spanning tree algorithms (Prim, Kruskal)11 : Kifan : Cyclic groups focussing on (Z/p)* Zoltan Discrete logarithm problem Diffie-Hellman key exchange and encryption scheme with security analysis Man-in-the-middle attack, key reuse, authentication. Comparison to RSA. Brief description of elliptic curves.12 : Liam : Towers of Hanoi and other 2^n puzzles. David The traditional variant and a new sliding/rotating version. Term 2 --- Week 4
Term 2 --- Week 4
8 : Tamiru : Proof that congruence is an equivalence relation. Solution to linear modular congruences.9 : Peter : Observation that sum_{i=1..n} i^3 = T(n)^2. Proof by induction. Proof by deduction summing a standard nxn multiplication table two ways. (i) sum across rows then sum rows to get RHS (ii) sum i-th gnomon, (1), (2,4,2), (3,6,9,6,3), ... , to get i^3. Note that each gnomon divided by i is the sum of NW-SE diagonals of ixi squares filled with 1s ... hence i^2. Proof that n^2 = sum of 1st n odd numbers by picture. Doing algebra mentally : (k+1)^4 (16 product terms to be grouped, Pascal triangle) Inductive "proof" that in all groups of n people everyone has the same gender. Elementary Euclidean geometry proofs axiom based. Axioms of a group, proof that identity and inverses are unique by contradiction.10 : William : Encoding - detecting errors, (parity, modulo prime, mention LFSR) Correcting errors - majority vote, Hadamard codes. Measures of encodings - size of codewords, "extra information" detect/correct-ability.11 : Zoltan : Redux of Diffie-Hellman key exchange, GCDs, Dlogs.12 : David : Goedel's Theorem Term 2 --- Week 5
Term 2 --- Week 5
8 : Tamiru : If a=c (mod m) and b=d (mod m) then a+b = c+d (mod m) ab = cd (mod m) Solution of linear congruence followed by example of Chinese Remainder Theorem9 : David + : Discussion of Goedel's Theorem William10 : Zoltan : 1992 Telecom AMOC Junior Contest.11 : Ellen : Colouring, parity, modular and numerical invariants. Problems 1,5,10,11,13 from the invariants sheet as a class.12 : Peter : Calculus. Fundamental Theorem. Exponential function and its power series. Solution to simple 2nd order differential equation. Meaning of exp(x), definition of pi by e^(i+pi)+1=0. Term 2 --- Week 6
Term 2 --- Week 6
8 : Ralph : Worked of problems 1, 2 and 4 of Structure of the Reals as a class. Discussed N, Z, Q, algebraics, transcendentals, Cantor and Liouville's number L=1/2^0! + 1/2^1! + 1/2^2! + ...9 : Peter : Axioms and examples of groups, rings and fields. When is Z/NZ a field. Matrices as an example of a non-commutative ring.10 : Zoltan : 1992 Telecom AMOC Junior Contest.11+12 : William : Turing machines. Computability/ Hilbert's problems, definition, state machines, clearing, busy beavers, numerical operations, addition, unary, binary, multiplication, Universal Turing machines, halting problem and solution to Hilbert's 10th problem.