BU CAS Computer Science 235
Algebraic Algorithms









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