BU CAS Computer Science 235
Algebraic Algorithms









2013-09-03lecture:
logic & sets
  • lecture notes
  • introduction and motivation
  • review of logical formulas
  • review of set theory
2013-09-05lecture:
logic & sets
  • lecture notes
  • review of quantifiers
  • relations & equivalence relations
2013-09-10lecture:
modular
arithmetic
  • lecture notes
  • congruence classes of integers
  • operations on congruence classes
  • algebra of congruence classes
2013-09-12lecture:
modular
arithmetic
  • lecture notes
  • solving equations over ℤ/m
  • ℤ/pℤ as a set of permutations
  • generating random numbers
2013-09-16
11:59 PM EDT
2013-09-17lecture:
modular
arithmetic
  • lecture notes
  • generating random numbers
  • greatest common divisor
  • generating prime numbers
2013-09-19lecture:
modular
arithmetic
  • lecture notes
  • generating prime numbers
  • Fermat's little theorem
  • detecting probable primes
2013-09-24lecture:
modular
arithmetic
  • lecture notes
  • more practice with gcd
  • more on probable primes
  • Chinese remainder theorem
2013-09-26lecture:
modular
arithmetic
2013-09-30
11:59 PM EDT
2013-10-01lecture:
modular
arithmetic
  • lecture notes
  • multiplicative inverses in ℤ/m
  • computing CRT solutions
  • Bézout's identity
  • extended Euclidean algorithm
2013-10-03lecture:
modular
arithmetic
  • lecture notes
  • practice computing CRT solutions
  • more applications of CRT
  • Euler's totient function
2013-10-08lecture:
modular
arithmetic
  • lecture notes
  • Euler's totient function
  • Euler's theorem
  • more on multiplicative inverses
  • applications of Euler's theorem
  • efficient arithmetic algorithms
2013-10-10lecture:
complexity
  • lecture notes
  • efficient arithmetic algorithms
  • intractable problems
  • applications of intractability
2013-10-14
2013-10-15
Monday sched.
    2013-10-17lecture:
    complexity
    2013-10-22lecture:
    review
    2013-10-24
    Thursday
    3:35-4:35 PM
    midterm
    exam
      2013-10-29lecture:
      complexity
      • review of midterm solutions
      2013-10-31lecture:
      complexity
      • lecture notes
      • computing square roots in ℤ/m
      • congruent squares problem
      2013-11-05lecture:
      complexity
      2013-11-07lecture:
      algebraic
      structures
      • lecture notes
      • history of algebraic structures
      • permutations
      • shift permutations and ℤ/m
      • algebra of permutations
      • swap permutations
      2013-11-11
      2013-11-12lecture:
      algebraic
      structures
      • lecture notes
      • adjacent swap permutations
      • decomposing permutations
      • algebraic structures
      2013-11-14lecture:
      algebraic
      structures
      • algebraic structures
      • generators
      • isomorphisms
      2013-11-19lecture:
      algebraic
      structures
      2013-11-21lecture:
      algebraic
      structures
      2013-11-26lecture:
      algebraic
      structures
      • lecture notes
      • isomorphisms and compression
      • using generators and closures
      • solvability of congruences
      • linear congruence theorem
      2013-11-27
      2013-11-28recess
        2013-12-03lecture:
        algebraic
        structures
        2013-12-05lecture:
        algebraic
        structures
        • lecture notes
        • algebra of data structures
          • distributed storage
          • compression
        2013-12-10lecture:
        review
        2013-12-11
        2013-12-17
        Tuesday
        3-5 PM
        GCB 209
        final
        exam