BU CAS CS 235 Spring 2015

BU CAS Computer Science 235
Algebraic Algorithms

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

   course assistant: Nicolas Hinderling
   OH: Thu. 5-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-01-20	lecture: logic & sets	lecture notes introduction and motivation review of logical formulas review of set theory
2015-01-22	lecture: logic & sets	lecture notes logical quantifiers comprehensions set products & relations equivalence relations
2015-01-27
2015-01-29	lecture: modular arithmetic	lecture notes set quotients congruence classes of integers operations on congruence classes
2015-01-30 11:59 PM EDT	assignment	assignment #1 due
2015-02-03	lecture: 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-05	lecture: modular arithmetic	lecture notes greatest common divisor more on random numbers infinitude of primes
2015-02-10
2015-02-12	lecture: 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	assignment #2 due first two late penalties waived
2015-02-17 Monday sched.
2015-02-19	lecture: modular arithmetic	lecture notes multiplicative inverses in ℤ/mℤ Chinese remainder theorem (CRT) applications of CRT computing CRT solutions
2015-02-24	lecture: modular arithmetic	lecture notes Bézout's identity extended Euclidean algorithm more applications of CRT Euler's totient function Euler's theorem
2015-02-26	lecture: review	lecture notes
2015-02-27 11:59 PM EDT	assignment	assignment #3 due
2015-03-03 Tuesday 9:35-10:35 AM	midterm exam
2015-03-05	lecture: modular arithmetic	lecture notes review of midterm solutions more on the totient function more on multiplicative inverses
2015-03-10	recess
2015-03-12	recess
2015-03-17	lecture: complexity	lecture notes computational complexity efficiency vs. intractability intractable problems factoring computing φ RSA problem (e roots) discrete logarithm problem
2015-03-19	lecture: complexity	lecture notes computing square roots in ℤ/mℤ congruent squares problem Hensel's lemma
2015-03-24	lecture: complexity	lecture notes applications of intractability basic proof of identity Diffie-Hellman protocol RSA and Rabin encryption
2015-03-26	lecture: 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	assignment #4 due
2015-03-31	lecture: 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-02	lecture: algebraic structures	lecture notes algebraic closures algebra of permutations swap permutations decomposing into swaps isomorphisms and examples homomorphic encryption
2015-04-07	lecture: algebraic structures	lecture notes compression as an isomorphism more on generators linear congruence theorem
2015-04-09	lecture: algebraic structures	lecture notes CRT as an isomorphism CRT isomorphism applications generators, and closures generalized CRT
2015-04-13 11:59 PM EDT	assignment	assignment #5 due
2015-04-14	lecture: algebraic structures	lecture notes more on generalized CRT other algebraic structures algebra of data structures distributed storage compression
2015-04-16	lecture: algebraic structures	lecture notes more CRT and applications more on isomorphisms subgroups hidden subgroup problem
2015-04-21	lecture: algebraic structures	lecture notes Shor's algorithm unreliability and errors
2015-04-23	lecture: algebraic structures	lecture notes direct products fundamental theorem of arithmetic other abstract algebra facts
2015-04-28	lecture: review	lecture notes
2015-04-30	lecture: review	assignment #6 due
2015-05-06 Wednesday 9:00-11:00 AM EPC 205	final exam