BU CAS CS 235 Spring 2016

BU CAS Computer Science 235
Algebraic Algorithms

lectures:
   Tue. & Thu., 9:30 - 11 AM in EPC 205
   lecturer: Andrei Lapets (lapets@bu.edu, MCS 176)
   OH: Tue. 4 - 6 PM; Thu. 11 AM - 12 PM (CS lab)
sections and other assistance:
   Wed., 3 PM - 4 PM in CAS 220
   Wed., 4 PM - 5 PM in PSY B55
   Wed., 5 PM - 6 PM in PSY B55
   teaching fellow: Maryam Ghasemi
   OH: Wed. 10 AM - 12 PM (CS lab)
   tutoring: Fri. 3 - 4 PM (CS lab)

   course assistant: Sandra Lefdal
   course assistant: Jacqueline You
   OH: Fri. 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)
   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

2016-01-19	lecture: logic & sets	lecture notes introduction and motivation review of logical formulas review of set theory
2016-01-21	lecture: logic & sets	lecture notes logical quantifiers comprehensions set products & relations
2016-01-26	lecture: logic & sets	lecture notes reflexivity, symmetry, & transitivity equivalence relations set quotients
2016-01-28	lecture: modular arithmetic	lecture notes congruence classes of integers operations on congruence classes solving equations over ℤ/mℤ algebra of congruence classes
2016-02-01 11:59 PM EST	assignment	assignment #1 due
2016-02-02	lecture: modular arithmetic	lecture notes more algebra of congruence classes Euclid's lemma solving equations & Euclid's lemma
2016-02-04	lecture: modular arithmetic	lecture notes ℤ/pℤ as a set of permutations generating random numbers greatest common divisor generalized Euclid's lemma finding coprimes
2016-02-09	lecture: modular arithmetic	lecture notes more on finding coprimes linear congruential generators infinitude of primes Fermat's little theorem Fermat primality test
2016-02-11	lecture: modular arithmetic	lecture notes detecting probable primes generating probable primes multiplicative inverses in ℤ/mℤ Chinese remainder theorem (CRT) applications of CRT
2016-02-16 11:59 PM EST Monday sched.	assignment	assignment #2 due
2016-02-18	lecture: modular arithmetic	lecture notes more applications of CRT computing CRT solutions
2016-02-23	lecture: modular arithmetic	lecture notes Bézout's identity extended Euclidean algorithm Euler's totient function Euler's theorem
2016-02-25	lecture: review	lecture notes
2016-02-26 11:59 PM EST	assignment	assignment #3 due
2016-03-01 Tuesday 9:35-10:35 AM	midterm exam
2016-03-03	lecture: modular arithmetic	review of midterm solutions lecture notes more on Euler's totient function closure of (ℤ/mℤ)*
2016-03-08	recess
2016-03-10	recess
2016-03-15	lecture: complexity	lecture notes problem complexity efficient arithmetic algorithms addition, multiplication modular exponentiation
2016-03-17	lecture: complexity	lecture notes efficient arithmetic algorithms division and modulus gcd and inversion solving CRT systems efficiency vs. intractability
2016-03-22	lecture: complexity	lecture notes complexity reductions intractable problems factoring computing φ RSA problem (e roots) discrete logarithm problem computing square roots in ℤ/mℤ
2016-03-24	lecture: complexity	lecture notes congruent squares problem Hensel's lemma Rabin encryption
2016-03-28 11:59 PM EDT	assignment	assignment #4 due
2016-03-29	lecture: complexity	lecture notes applications of intractability RSA and Rabin encryption Diffie-Hellman protocol more random number generators
2016-03-30 Wednesday sections	quiz
2016-03-31	lecture: algebraic structures	lecture notes algebra of permutations swap & adjacent swap shift/cyclic multiplication-induced decomposition into swaps examples of isomorphisms
2016-04-05	lecture: algebraic structures	lecture notes more isomorphisms and examples homomorphic encryption
2016-04-07	lecture: algebraic structures	lecture notes compression as an isomorphism generators and closures linear congruence theorem (LCT)
2016-04-11 11:59 PM EDT	assignment	assignment #5 due
2016-04-12	lecture: algebraic structures	lecture notes more on the LCT CRT as an isomorphism generalized CRT
2016-04-14	lecture: algebraic structures	lecture notes more on the CRT isomorphism generalized CRT practice applications of the LCT unreliability and errors
2016-04-19	lecture: algebraic structures	lecture notes algebraic properties monoids groups subgroups direct products of groups
2016-04-21	lecture: algebraic structures	polynomials in ℤ/mℤ representing groups as functions Shor's algorithm
2016-04-26	lecture: review	lecture notes
2016-04-27 11:59 PM EDT	assignment	assignment #6 due
2016-04-28	lecture: review
2016-05-03 Tuesday 9:00-11:00 AM EPC 205	final exam