204211-src-51-1
Planed
- การนับ
- นับเบื้องต้น เส้นตรง, วงกลม, nCr, nPr
- inclusion-exclusion techniques
- bijections
- advanced counting (placing rods)
- Proof Techniques
- logics
- direct proof
- indirect proof
- proof by contradiction
- Advanced proof techniques
- mathematical induction
- basic induction
- strong induction
- examples used: tiling, placing dominoes, induction on matrices, Fibonacci numbers
- recursive thinking $
- Pigeon-Hole Principle $
- diagonalization
- mathematical induction
- Number theory
- divisibility
- congruence
- gcd, extended gcd
- modular arithematics
- Fermat's Little Theorem
- polynomials $
- secret sharing, coding $
- RSA $
$ --- absence, to be covered
Actual
10 ส.ค. 51
- review basic induction & counting.
- inclusion-exclusion principles.
- using bijection in counting. (without actually define what a bijection is)
- a bijection between subsets and bitstrings
- a bijection between odd-sized subsets and even-sized subsets
- gave out idea of the bijection without proof: will be in homework
- proof of the inclusion-exclusion principle (sketch)
17 ส.ค. 51
- diagonalization
- advanced counting: placing rods
24 ส.ค. 51
- review of modular arithmatics
- basic identities
- if then exists.
- the proof didn't use the fact that a pair $x,y$ such that $ax+by=\gcd(a,b)$ exists
- RSA, Euler's Theorem, and Fermat's Little Theorem (without proofs)
- TODO: (Homework) RSA by hand, Proof of Fermat's Little Theorem
- NEXT: Proof of Euler's Theorem and correctness of RSA
31 ส.ค. 51
- Number Theory
- Primality testing
- Testing in exponential time ($O(p)$ and $O(\sqrt{p})$ for testing $p$)
- Proved (quick): for a composite $a$, one of its factor must be at most $\sqrt{a}$
- Testing based on Fermat's Little Theorem
- Implementation of the test: Repeated squaring
- Success probability of the test and Carmicheal number
- Proof of Fermat's Little Theorem
- Testing in exponential time ($O(p)$ and $O(\sqrt{p})$ for testing $p$)
- Proof of Euler Theorem and RSA
- Primality testing
- Recursions
- Recursive definition and counting
- Recursive algorithms, divide and conquer