BU CAS Computer Science 235
Algebraic Algorithms









2014-09-02lecture:
logic & sets
  • lecture notes
  • introduction and motivation
  • review of logical formulas
  • review of set theory
2014-09-04lecture:
logic & sets
  • lecture notes
  • logical quantifiers
  • comprehensions
  • set products & relations
  • equivalence relations
2014-09-09lecture:
modular
arithmetic
  • lecture notes
  • set quotients
  • congruence classes of integers
  • operations on congruence classes
2014-09-10
11:59 PM EDT
assignment
2014-09-11lecture:
modular
arithmetic
  • lecture notes
  • algebra of congruence classes
  • solving equations over ℤ/m
  • Euclid's lemma
2014-09-16lecture:
modular
arithmetic
  • lecture notes
  • ℤ/pℤ as a set of permutations
  • generating random numbers
  • greatest common divisor
  • more on random numbers
2014-09-18lecture:
modular
arithmetic
2014-09-23lecture:
modular
arithmetic
  • lecture notes
  • Fermat primality test
  • detecting probable primes
  • generating probable primes
  • multiplicative inverses in ℤ/m
2014-09-25lecture:
modular
arithmetic
  • lecture notes
  • Chinese remainder theorem (CRT)
  • applications of CRT
  • computing CRT solutions
2014-09-26
11:59 PM EDT
assignment
2014-09-30lecture:
modular
arithmetic
  • lecture notes
  • more on CRT solutions
  • Bézout's identity
  • extended Euclidean algorithm
  • computing CRT solutions
2014-10-01
  • all sections and OHs cancelled
2014-10-02lecture:
modular
arithmetic
  • lecture notes
  • more applications of CRT
  • Euler's totient function
  • Euler's theorem
2014-10-07lecture:
modular
arithmetic
  • lecture notes
  • applications of Euler's theorem
    • computing inverses
    • efficient exponentiation
2014-10-09lecture:
complexity
  • lecture notes
  • efficient arithmetic algorithms
    • addition and multiplication
    • gcd and inversion
    • modular exponentiation
    • solving CRT systems
2014-10-10
  • extra OHs: 2 - 4 PM (CS lab)
2014-10-14
11:59 PM EDT
(Monday sched.)
assignment
2014-10-16lecture:
review
2014-10-21
Tuesday
3:35-4:35 PM
midterm
exam
    2014-10-23lecture
    • review of midterm solutions
    • efficiency vs. intractability
    2014-10-28lecture:
    complexity
    • lecture notes
    • efficiency vs. intractability
    • intractable problems
      • factoring
      • computing φ
      • RSA problem (e roots)
      • discrete logarithm problem
    • computing square roots in ℤ/m
    2014-10-30lecture:
    complexity
    2014-11-04lecture:
    complexity
    • lecture notes
    • applications of intractability
      • basic proof of identity
      • Diffie-Hellman protocol
      • RSA encryption protocol
      • Rabin encryption protocol
    2014-11-06lecture:
    algebraic
    structures
      2014-11-10
      11:59 PM EDT
      assignment
      2014-11-11lecture:
      algebraic
      structures
        2014-11-12
        Wednesday
        sections
        quiz
          2014-11-13lecture:
          algebraic
          structures
            2014-11-18lecture:
            algebraic
            structures
              2014-11-20lecture:
              algebraic
              structures
                2014-11-25lecture:
                algebraic
                structures
                  2014-11-27recess
                    2014-12-02lecture:
                    algebraic
                    structures
                      2014-12-04lecture:
                      review
                        2014-12-09lecture:
                        review
                          2014-12-18
                          Thursday
                          3:00-5:00 PM
                          final
                          exam