BU CAS CS 235 Fall 2014

BU CAS Computer Science 235
Algebraic Algorithms

lectures:
   Tue. & Thu., 3:30 - 5 PM in GCB 209
   lecturer: Andrei Lapets (lapets@bu.edu, MCS 178)
   OH: Tue. 5 - 6:30 PM; Thu. 2 - 3:30 PM (CS lab)
sections:
   Wed., 4 PM - 5 PM in MCS B19
   Wed., 5 PM - 6 PM in CAS 312
   teaching fellow: Yilei Chen (section notes)
   OH: Mon. 6:30-8 PM; Wed. 12:30-2 PM (CS lab)
for questions and discussion:
cascs235a1-l@bu.edu (course mailing list)
Q&A page on Piazza

homework assignment policies:
   submission: by 11:59 PM on due date (gsubmit)
   collaboration: discussion only; list all collaborators
   late policy: -10 points per day, 4 days maximum

course grade:
   50% homework +
   max{
       50% max{fin, avg{mid, fin}},
       40% max{fin, avg{mid, fin}} + 10% quiz
     }

course materials:
   lecture notes (w/ assignments & review problems)
   random exercise generator
   assignment #1
   assignment #2
   assignment #3
   assignment #4
   assignment #5
   assignment #6

software used in the course:
Python 3.3+

other reading materials (not required):

   A Computational Introduction to
   Number Theory and Algebra.
     Victor Shoup.

   Algebraic algorithms.
     Course notes by Péter Gács.

   Mathematics for Computer Science.
     Eric Lehman and Tom Leighton.

   A Concrete Introduction to Higher Algebra.
     Lindsay Childs.

   The Higher Arithmetic:
   An Introduction to the Theory of Numbers.
     H. Davenport.

academic conduct code

2014-09-02	lecture: logic & sets	lecture notes introduction and motivation review of logical formulas review of set theory
2014-09-04	lecture: logic & sets	lecture notes logical quantifiers comprehensions set products & relations equivalence relations
2014-09-09	lecture: modular arithmetic	lecture notes set quotients congruence classes of integers operations on congruence classes
2014-09-10 11:59 PM EDT	assignment	assignment #1 due
2014-09-11	lecture: modular arithmetic	lecture notes algebra of congruence classes solving equations over ℤ/mℤ Euclid's lemma
2014-09-16	lecture: modular arithmetic	lecture notes ℤ/pℤ as a set of permutations generating random numbers greatest common divisor more on random numbers
2014-09-18	lecture: modular arithmetic	lecture notes generating prime numbers Fermat's little theorem
2014-09-23	lecture: modular arithmetic	lecture notes Fermat primality test detecting probable primes generating probable primes multiplicative inverses in ℤ/mℤ
2014-09-25	lecture: modular arithmetic	lecture notes Chinese remainder theorem (CRT) applications of CRT computing CRT solutions
2014-09-26 11:59 PM EDT	assignment	assignment #2 due
2014-09-30	lecture: 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-02	lecture: modular arithmetic	lecture notes more applications of CRT Euler's totient function Euler's theorem
2014-10-07	lecture: modular arithmetic	lecture notes applications of Euler's theorem computing inverses efficient exponentiation
2014-10-09	lecture: 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	assignment #3 due
2014-10-16	lecture: review	lecture notes
2014-10-21 Tuesday 3:35-4:35 PM	midterm exam
2014-10-23	lecture	review of midterm solutions efficiency vs. intractability
2014-10-28	lecture: complexity	lecture notes efficiency vs. intractability intractable problems factoring computing φ RSA problem (e roots) discrete logarithm problem computing square roots in ℤ/mℤ
2014-10-30	lecture: complexity	lecture notes congruent squares problem Hensel's lemma
2014-11-04	lecture: complexity	lecture notes applications of intractability basic proof of identity Diffie-Hellman protocol RSA encryption protocol Rabin encryption protocol
2014-11-06	lecture: algebraic structures	more on the Rabin protocol proving unsolvability encryption & Shamir secret sharing other protocol variants Diffie-Hellman example Hensel's lemma example
2014-11-10 11:59 PM EDT	assignment	assignment #4 due
2014-11-11	lecture: algebraic structures	lecture notes history of algebraic structures algebra of permutations swap permutations decomposing into swaps shift permutations on ℤ/mℤ multiplication-induced examples of isomorphisms
2014-11-12 Wednesday sections	quiz
2014-11-13	lecture: algebraic structures	lecture notes more on isomorphisms homomorphic encryption compression as an isomorphism
2014-11-18	lecture: algebraic structures	lecture notes more on generators linear congruence theorem CRT as an isomorphism CRT, generators, and closures
2014-11-20	lecture: algebraic structures	lecture notes more on generalized CRT CRT isomorphism applications other algebraic structures algebra of data structures distributed storage compression
2014-11-25	lecture: algebraic structures	lecture notes more CRT and applications more on isomorphisms subgroups hidden subgroup problem
2014-11-26 11:59 PM EDT	assignment	assignment #5 due
2014-11-27	recess
2014-12-02	lecture: algebraic structures	lecture notes more on generators & subgroups direct products structural induction fundamental theorem of arithmetic
2014-12-04	lecture: review	lecture notes
2014-12-09	lecture: review
2014-12-15 11:59 PM EDT	assignment	assignment #6 due no late submissions
2014-12-18 Thursday 3:00-5:00 PM	final exam