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

• 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 $\gcd(a,b)=1$ then $a^{-1}{\pmod {p}}$ 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 and proof of Fermat's Little Theorem
  • Proof of Euler Theorem and RSA
• Recursions
  • Recursive definition and counting
  • Recursive algorithms, divide and conquer