BU CAS Computer Science 235
Algebraic Algorithms









2014-01-16lecture:
logic & sets
  • lecture notes
  • introduction and motivation
  • review of logical formulas
  • review of set theory
2014-01-21lecture:
logic & sets
  • lecture notes
  • review of quantifiers
  • comprehensions
  • set products & relations
2014-01-23lecture:
modular
arithmetic
  • lecture notes
  • equivalence relations
  • set quotients
  • congruence classes of integers
  • operations on congruence classes
2014-01-28lecture:
modular
arithmetic
  • lecture notes
  • operations on congruence classes
  • algebra of congruence classes
  • solving equations over ℤ/m
2014-01-29
2014-01-30lecture:
modular
arithmetic
  • lecture notes
  • solving equations over ℤ/m
  • Euclid's lemma
  • ℤ/pℤ as a set of permutations
  • generating random numbers
  • greatest common divisor
2014-02-04lecture:
modular
arithmetic
  • lecture notes
  • greatest common divisor
  • more on random numbers
  • generating prime numbers
2014-02-06lecture:
modular
arithmetic
  • lecture notes
  • Fermat's little theorem
  • Fermat primality test
  • detecting probable primes
  • generating probable primes
2014-02-11lecture:
modular
arithmetic
2014-02-13lecture:
modular
arithmetic
  • lecture notes
  • multiplicative inverses in ℤ/m
  • computing CRT solutions
  • Bézout's identity
2014-02-14
2014-02-18lecture:
modular
arithmetic
  • lecture notes
  • Bézout's identity
  • extended Euclidean algorithm
  • more applications of CRT
2014-02-20lecture:
modular
arithmetic
  • lecture notes
  • more applications of CRT
  • practice computing CRT solutions
  • Euler's totient function
  • Euler's theorem
  • applications of Euler's theorem
    • computing inverses
    • efficient exponentiation
2014-02-25lecture:
complexity
  • lecture notes
  • practice with Euler's theorem
  • intractable problems
  • applications of intractability
2014-02-26
2014-02-27lecture:
review
2014-03-04
Tuesday
2:05-3:05 PM
midterm
exam
    2014-03-06lecture
    • review of midterm solutions
    2014-03-11recess
      2014-03-13recess
        2014-03-18lecture:
        complexity
        • lecture notes
        • efficiency vs. intractability
        • efficient arithmetic algorithms
          • addition and multiplication
          • gcd and inversion
          • modular exponentiation
          • solving CRT systems
        2014-03-20lecture:
        complexity
        • lecture notes
        • computing square roots in ℤ/m
        • congruent squares problem
        • Hensel's lemma
        2014-03-25lecture:
        complexity
        2014-03-27lecture:
        complexity
        • lecture notes
        • applications of intractability
          • RSA encryption protocol
          • Rabin encryption protocol
        2014-03-31
        2014-04-01lecture:
        algebraic
        structures
        • lecture notes
        • history of algebraic structures
        • algebra of permutations
          • swap permutations
          • decomposing into swaps
          • shift permutations on ℤ/m
          • multiplication-induced
        2014-04-03lecture:
        algebraic
        structures
        2014-04-08lecture:
        algebraic
        structures
        • lecture notes
        • compression as an isomorphism
        • generators
        • linear congruence theorem
        • products of algebraic structures
        2014-04-10lecture:
        algebraic
        structures
        • lecture notes
        • CRT as an isomorphism
        • CRT isomorphism applications
        • CRT, generators, and closures
        • generalizing CRT
        2014-04-15lecture:
        algebraic
        structures
        • lecture notes
        • more on generalized CRT
        • other algebraic structures
        • common algebraic properties
        2014-04-17lecture:
        algebraic
        structures
        • lecture notes
        • algebra of data structures
          • distributed storage
          • compression
        • fundamental theorem of arithmetic
        2014-04-18
        2014-04-22lecture:
        algebraic
        structures
          2014-04-24
          Monday sched.
            2014-04-29lecture:
            review
            2014-05-01lecture:
            review
            2014-05-06
            Tuesday
            3-5 PM
            final
            exam