BU CAS Computer Science 235
Algebraic Algorithms









2015-09-03lecture:
logic & sets
  • lecture notes
  • introduction and motivation
  • review of logical formulas
  • review of set theory
2015-09-08lecture:
logic & sets
  • lecture notes
  • logical quantifiers
  • comprehensions
  • set products & relations
  • equivalence relations
2015-09-10lecture:
modular
arithmetic
  • lecture notes
  • set quotients
  • congruence classes of integers
  • operations on congruence classes
  • solving equations over ℤ/m
2015-09-14
11:59 PM EDT
assignment
2015-09-15lecture:
modular
arithmetic
  • lecture notes
  • algebra of congruence classes
  • Euclid's lemma
  • ℤ/pℤ as a set of permutations
  • generating random numbers
2015-09-17lecture:
modular
arithmetic
  • lecture notes
  • greatest common divisor
  • generalized Euclid's lemma
  • finding coprimes
  • more on random numbers
2015-09-22lecture:
modular
arithmetic
  • lecture notes
  • generating prime numbers
  • Fermat's little theorem
  • Fermat primality test
  • detecting probable primes
  • generating probable primes
2015-09-24lecture:
modular
arithmetic
  • lecture notes
  • multiplicative inverses in ℤ/m
  • Chinese remainder theorem (CRT)
  • applications of CRT
2015-09-29lecture:
modular
arithmetic
  • lecture notes
  • computing CRT solutions
  • more on CRT solutions
  • Bézout's identity
  • extended Euclidean algorithm
2015-09-30
11:59 PM EDT
assignment
2015-10-01lecture:
modular
arithmetic
  • lecture notes
  • practice computing CRT solutions
  • efficiency of Euclidean algorithm
  • using Bézout's identity
  • more applications of CRT
2015-10-06lecture:
modular
arithmetic
  • lecture notes
  • Euler's totient function
  • Euler's theorem
  • applications of Euler's theorem
    • computing inverses
    • efficient exponentiation
2015-10-08lecture:
complexity
  • lecture notes
  • problem complexity
  • efficient arithmetic algorithms
    • addition, multiplication
    • modular exponentiation
    • division
2015-10-13
Monday sched.
    2015-10-14
    11:59 PM EDT
    assignment
    2015-10-15lecture:
    complexity
    • lecture notes
    • efficient arithmetic algorithms
      • modulus
      • gcd and inversion
      • solving CRT systems
    • efficiency vs. intractability
    • intractible problems
      • RSA problem (e roots)
      • discrete logarithm problem
    2015-10-20lecture:
    review
    2015-10-22
    Thursday
    3:35-4:35 PM
    midterm
    exam
      2015-10-27lecture
      • review of midterm solutions
      • lecture notes
      • computing square roots in ℤ/m
      • congruent squares problem
      2015-10-29lecture:
      complexity
      • lecture notes
      • Hensel's lemma
      • complexity reductions
      • other intractable problems
        • factoring
        • computing φ
      2015-11-03lecture:
      complexity
      • lecture notes
      • more complexity reductions
      • applications of intractability
        • basic proof of identity
        • Diffie-Hellman protocol
        • RSA encryption protocol
        • Rabin encryption protocol
      2015-11-05lecture:
      complexity
      • lecture notes
      • RSA and Diffie-Hellman examples
      • more on the Rabin protocol
      • more on random number generators
      • other protocol variants
      2015-11-10lecture:
      algebraic
      structures
      • lecture notes
      • algebra of permutations
        • swap permutations
        • decomposing into swaps
        • shift permutations on ℤ/m
        • multiplication-induced
      • examples of isomorphisms
      2015-11-11
      11:59 PM EDT
      assignment
      2015-11-12lecture:
      algebraic
      structures
      • lecture notes
      • more on isomorphisms
      • homomorphic encryption
      • compression as an isomorphism
      • generators of algebraic structures
      2015-11-17lecture:
      algebraic
      structures
      2015-11-18
      Wednesday
      sections
      quiz
        2015-11-19lecture:
        algebraic
        structures
        • lecture notes
        • linear congruence theorem
        • CRT as an isomorphism
        • generalized CRT
        2015-11-24lecture:
        algebraic
        structures
        • lecture notes
        • more on generalized CRT
        • groups and subgroups
        • hidden subgroup problem
        2015-11-26recess
          2015-11-30
          11:59 PM EDT
          assignment
          2015-12-01lecture:
          algebraic
          structures
          • lecture notes
          • more on groups and subgroups
          • direct products of groups
          • more applications
          2015-12-03lecture:
          algebraic
          structures
          • lecture notes
          • other algebraic structures
          • algebra of data structures
            • distributed storage
            • compression
          • structural induction
          • fundamental theorem of arithmetic
          2015-12-08lecture:
          review
          2015-12-10lecture:
          review
          2015-12-15
          11:59 PM EDT
          assignment
          2015-12-17
          Thursday
          3:00-5:00 PM
          CAS 316
          final
          exam