BU CAS CS 235 Fall 2012

Computer Science 235 - Algebraic Algorithms

lectures:
   Tue. & Thu., 3:30 - 5:00 PM in CAS 222
   lecturer: Andrei Lapets (lapets@bu.edu, MCS 176)
   OH: Tue. 1-2 PM; Wed. 2-4 PM
sections:
   Wed., 4:00 - 5:00 PM in MCS B19
   Wed., 5:00 - 6:00 PM in MCS B23
   teaching fellow: Jeffrey Finkelstein (jeffreyf@bu.edu)
   OH: Wed. 1-2 PM; Thu. 12-2 PM in undergrad. CS lab
course mailing list (for questions and discussion):
cascs235a1-l@bu.edu

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

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

course materials:
   lecture notes (with assignments and review problems)
   assignment #1 (with solutions)
   assignment #2 (with solutions)
   assignment #3 (with solutions)
   assignment #4 (with solutions)
   assignment #5 (with solutions)
   assignment #6 (with solutions)
   bonus assignment

software used in the course:
Python 3.2
aartifact

other reading materials (not required):

   A Concrete Introduction to Higher Algebra.
     Lindsay Childs.

   Mathematics for Computer Science.
     Eric Lehman and Tom Leighton.

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

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

academic conduct code

2012-09-04	lecture	lecture notes introduction and motivation review of logic, sets, relations
2012-09-06	lecture	lecture notes more review set quotients congruence classes
2012-09-11	lecture	lecture notes more review of logic modular arithmetic
2012-09-13	lecture	lecture notes modular arithmetic example: random no. generator
2012-09-14		assignment #1 due
2012-09-18	lecture	lecture notes generating/testing primes probable primes
2012-09-20	lecture	lecture notes greatest common divisor probable primes chinese remainder theorem (CRT)
2012-09-25	lecture	lecture notes applications of CRT
2012-09-27	lecture	lecture notes Euler's totient function multiplicative inverses in Z/nZ
2012-09-28		assignment #2 due
2012-10-02	lecture	lecture notes more on Euler's totient function more on multiplicative inverses RSA cryptographic protocol
2012-10-04	lecture	lecture notes complexity of intractable problems polynomial-time reductions
2012-10-09	monday schedule
2012-10-11	lecture	lecture notes more on intractable problems RSA problem factoring computing the totient function φ
2012-10-12		assignment #3 due
2012-10-16	lecture	lecture notes quadratic residues congruent squares problem
2012-10-18	lecture	lecture notes complexity of tractable problems efficient bit vector arithmetic
2012-10-23	lecture: review	lecture notes
2012-10-25 Thu. 3:30-5 PM	midterm exam
2012-10-26		assignment #4 due
2012-10-30	lecture	review of midterm solutions
2012-11-01	lecture	lecture notes history of abstract algebra algebraic structures
2012-11-06	lecture	lecture notes properties of algebraic structures algebraic structures in applications
2012-11-08	lecture	lecture notes discussion of homework permutation groups double cosets
2012-11-13	lecture	lecture notes review of algebraic structures structural induction induction over N
2012-11-15	lecture	lecture notes more examples of induction isomorphisms
2012-11-20	lecture	lecture notes isomorphisms fundamental theorem of arithmetic subgroups
2012-11-22	recess
2012-11-27	lecture	lecture notes comments about assignment review of permutation groups group isomorphisms and CRT
2012-11-28		assignment #5 due
2012-11-29	lecture	lecture notes more on CRT and isomorphisms generalizing CRT
2012-12-04	lecture	lecture notes generalizing CRT examples using generalized CRT
2012-12-06	lecture: review	lecture notes
2012-12-11	lecture: review	lecture notes
2012-12-12		assignment #6 due
2012-12-14		bonus assignment due
2012-12-18 Tue. 3-5 PM CAS 222	final exam