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,
Complexity
10 : 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.
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.
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 axioms
10 : 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.
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
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 Theorem
9 : David + : Discussion of Goedel's Theorem
William
10 : 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.
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.