BU CAS CS 235 Fall 2015

BU CAS Computer Science 235
Algebraic Algorithms

lectures:
   Tue. & Thu., 3:30 - 5 PM in CAS 316
   lecturer: Andrei Lapets (lapets@bu.edu, MCS 173)
   OH: Wed. 5 - 7 PM; Thu. 2 - 3 PM (CS lab)
sections and other assistance:
   Wed., 4 PM - 5 PM in MCS B19
   Wed., 5 PM - 6 PM in MCS B19
   teaching fellow: Maryam Ghasemi
   OH: Wed. 9:30-11:30 AM (CS lab)
   tutoring: Tue. 5 - 7 PM (CS lab)

   course assistant: Sandra Lefdal
   OH: Mon. 4 - 6 PM (CS lab)
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

2015-09-03	lecture: logic & sets	lecture notes introduction and motivation review of logical formulas review of set theory
2015-09-08	lecture: logic & sets	lecture notes logical quantifiers comprehensions set products & relations equivalence relations
2015-09-10	lecture: 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	assignment #1 due
2015-09-15	lecture: modular arithmetic	lecture notes algebra of congruence classes Euclid's lemma ℤ/pℤ as a set of permutations generating random numbers
2015-09-17	lecture: modular arithmetic	lecture notes greatest common divisor generalized Euclid's lemma finding coprimes more on random numbers
2015-09-22	lecture: modular arithmetic	lecture notes generating prime numbers Fermat's little theorem Fermat primality test detecting probable primes generating probable primes
2015-09-24	lecture: modular arithmetic	lecture notes multiplicative inverses in ℤ/mℤ Chinese remainder theorem (CRT) applications of CRT
2015-09-29	lecture: 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	assignment #2 due
2015-10-01	lecture: modular arithmetic	lecture notes practice computing CRT solutions efficiency of Euclidean algorithm using Bézout's identity more applications of CRT
2015-10-06	lecture: modular arithmetic	lecture notes Euler's totient function Euler's theorem applications of Euler's theorem computing inverses efficient exponentiation
2015-10-08	lecture: 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	assignment #3 due
2015-10-15	lecture: 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-20	lecture: review	lecture notes
2015-10-22 Thursday 3:35-4:35 PM	midterm exam
2015-10-27	lecture	review of midterm solutions lecture notes computing square roots in ℤ/mℤ congruent squares problem
2015-10-29	lecture: complexity	lecture notes Hensel's lemma complexity reductions other intractable problems factoring computing φ
2015-11-03	lecture: complexity	lecture notes more complexity reductions applications of intractability basic proof of identity Diffie-Hellman protocol RSA encryption protocol Rabin encryption protocol
2015-11-05	lecture: complexity	lecture notes RSA and Diffie-Hellman examples more on the Rabin protocol more on random number generators other protocol variants
2015-11-10	lecture: 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	assignment #4 due
2015-11-12	lecture: algebraic structures	lecture notes more on isomorphisms homomorphic encryption compression as an isomorphism generators of algebraic structures
2015-11-17	lecture: algebraic structures	lecture notes generators and closures linear congruence theorem
2015-11-18 Wednesday sections	quiz
2015-11-19	lecture: algebraic structures	lecture notes linear congruence theorem CRT as an isomorphism generalized CRT
2015-11-24	lecture: algebraic structures	lecture notes more on generalized CRT groups and subgroups hidden subgroup problem
2015-11-26	recess
2015-11-30 11:59 PM EDT	assignment	assignment #5 due
2015-12-01	lecture: algebraic structures	lecture notes more on groups and subgroups direct products of groups more applications
2015-12-03	lecture: algebraic structures	lecture notes other algebraic structures algebra of data structures distributed storage compression structural induction fundamental theorem of arithmetic
2015-12-08	lecture: review	lecture notes
2015-12-10	lecture: review	lecture notes
2015-12-15 11:59 PM EDT	assignment	assignment #6 due
2015-12-17 Thursday 3:00-5:00 PM CAS 316	final exam