BU CAS CS 235 Spring 2014

BU CAS Computer Science 235
Algebraic Algorithms

lectures:
   Tue. & Thu., 2 PM - 3:30 PM in GCB 207
   lecturer: Andrei Lapets (lapets@bu.edu, MCS 178)
   OH: Wed. 3:30-5:30 PM; Thu. 12:45-1:45 PM (CS lab)
sections:
   Fri., 10 AM - 11 AM in MCS B21
   Fri., 12 PM - 1 PM in MCS B33
   Fri., 1 PM - 2 PM in CAS 228
   teaching fellow: Qinxun Bai
   OH: Tue. 3:30-5:30 PM; Fri. 2-3 PM (MCS B24)
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, 5 days maximum

course grade:
50% homework + 50% max{final, avg{mid, final}}

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-01-16	lecture: logic & sets	lecture notes introduction and motivation review of logical formulas review of set theory
2014-01-21	lecture: logic & sets	lecture notes review of quantifiers comprehensions set products & relations
2014-01-23	lecture: modular arithmetic	lecture notes equivalence relations set quotients congruence classes of integers operations on congruence classes
2014-01-28	lecture: modular arithmetic	lecture notes operations on congruence classes algebra of congruence classes solving equations over ℤ/mℤ
2014-01-29		assignment #1 due
2014-01-30	lecture: modular arithmetic	lecture notes solving equations over ℤ/mℤ Euclid's lemma ℤ/pℤ as a set of permutations generating random numbers greatest common divisor
2014-02-04	lecture: modular arithmetic	lecture notes greatest common divisor more on random numbers generating prime numbers
2014-02-06	lecture: modular arithmetic	lecture notes Fermat's little theorem Fermat primality test detecting probable primes generating probable primes
2014-02-11	lecture: modular arithmetic	lecture notes Chinese remainder theorem (CRT) applications of CRT
2014-02-13	lecture: modular arithmetic	lecture notes multiplicative inverses in ℤ/mℤ computing CRT solutions Bézout's identity
2014-02-14		assignment #2 due
2014-02-18	lecture: modular arithmetic	lecture notes Bézout's identity extended Euclidean algorithm more applications of CRT
2014-02-20	lecture: modular arithmetic	lecture notes more applications of CRT practice computing CRT solutions Euler's totient function Euler's theorem applications of Euler's theorem computing inverses efficient exponentiation
2014-02-25	lecture: complexity	lecture notes practice with Euler's theorem intractable problems applications of intractability
2014-02-26		assignment #3 due
2014-02-27	lecture: review	lecture notes
2014-03-04 Tuesday 2:05-3:05 PM	midterm exam
2014-03-06	lecture	review of midterm solutions
2014-03-11	recess
2014-03-13	recess
2014-03-18	lecture: complexity	lecture notes efficiency vs. intractability efficient arithmetic algorithms addition and multiplication gcd and inversion modular exponentiation solving CRT systems
2014-03-20	lecture: complexity	lecture notes computing square roots in ℤ/mℤ congruent squares problem Hensel's lemma
2014-03-25	lecture: complexity	lecture notes more on roots and Hensel's lemma
2014-03-27	lecture: complexity	lecture notes applications of intractability RSA encryption protocol Rabin encryption protocol
2014-03-31		assignment #4 due
2014-04-01	lecture: algebraic structures	lecture notes history of algebraic structures algebra of permutations swap permutations decomposing into swaps shift permutations on ℤ/mℤ multiplication-induced
2014-04-03	lecture: algebraic structures	lecture notes isomorphisms homomorphic encryption
2014-04-08	lecture: algebraic structures	lecture notes compression as an isomorphism generators linear congruence theorem products of algebraic structures
2014-04-10	lecture: algebraic structures	lecture notes CRT as an isomorphism CRT isomorphism applications CRT, generators, and closures generalizing CRT
2014-04-15	lecture: algebraic structures	lecture notes more on generalized CRT other algebraic structures common algebraic properties
2014-04-17	lecture: algebraic structures	lecture notes algebra of data structures distributed storage compression fundamental theorem of arithmetic
2014-04-18		assignment #5 due
2014-04-22	lecture: algebraic structures	lecture notes more on data structures operating on data structures other applications
2014-04-24 Monday sched.
2014-04-29	lecture: review	lecture notes
2014-05-01	lecture: review	assignment #6 due late penalty for Fri., 5/2 waived only three late days available
2014-05-06 Tuesday 3-5 PM GCB 207	final exam