BU CAS CS 235 Fall 2013

BU CAS Computer Science 235
Algebraic Algorithms

lectures:
   Tue. & Thu., 3:30-5:00 PM in GCB 209
   lecturer: Andrei Lapets (lapets@bu.edu)
   OH: Wed. 1 - 3 PM; Thu. 2:15 - 3:15 PM (CS lab)
sections:
   Wed., 4 - 5 PM in MCS B19
   Wed., 5 - 6 PM in MCS B31
   teaching fellow: Qinxun Bai
   OH: Mon. & Thu. 5-6 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):

   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.

   A Concrete Introduction to Higher Algebra.
     Lindsay Childs.

academic conduct code

2013-09-03	lecture: logic & sets	lecture notes introduction and motivation review of logical formulas review of set theory
2013-09-05	lecture: logic & sets	lecture notes review of quantifiers relations & equivalence relations
2013-09-10	lecture: modular arithmetic	lecture notes congruence classes of integers operations on congruence classes algebra of congruence classes
2013-09-12	lecture: modular arithmetic	lecture notes solving equations over ℤ/mℤ ℤ/pℤ as a set of permutations generating random numbers
2013-09-16 11:59 PM EDT		assignment #1 due
2013-09-17	lecture: modular arithmetic	lecture notes generating random numbers greatest common divisor generating prime numbers
2013-09-19	lecture: modular arithmetic	lecture notes generating prime numbers Fermat's little theorem detecting probable primes
2013-09-24	lecture: modular arithmetic	lecture notes more practice with gcd more on probable primes Chinese remainder theorem
2013-09-26	lecture: modular arithmetic	lecture notes applications of CRT computing CRT solutions
2013-09-30 11:59 PM EDT		assignment #2 due
2013-10-01	lecture: modular arithmetic	lecture notes multiplicative inverses in ℤ/mℤ computing CRT solutions Bézout's identity extended Euclidean algorithm
2013-10-03	lecture: modular arithmetic	lecture notes practice computing CRT solutions more applications of CRT Euler's totient function
2013-10-08	lecture: modular arithmetic	lecture notes Euler's totient function Euler's theorem more on multiplicative inverses applications of Euler's theorem efficient arithmetic algorithms
2013-10-10	lecture: complexity	lecture notes efficient arithmetic algorithms intractable problems applications of intractability
2013-10-14		assignment #3 due
2013-10-15 Monday sched.
2013-10-17	lecture: complexity	lecture notes intractable problems applications of intractability
2013-10-22	lecture: review	lecture notes
2013-10-24 Thursday 3:35-4:35 PM	midterm exam
2013-10-29	lecture: complexity	review of midterm solutions
2013-10-31	lecture: complexity	lecture notes computing square roots in ℤ/mℤ congruent squares problem
2013-11-05	lecture: complexity	lecture notes more on congruent squares Hensel's lemma
2013-11-07	lecture: algebraic structures	lecture notes history of algebraic structures permutations shift permutations and ℤ/mℤ algebra of permutations swap permutations
2013-11-11		assignment #4 due
2013-11-12	lecture: algebraic structures	lecture notes adjacent swap permutations decomposing permutations algebraic structures
2013-11-14	lecture: algebraic structures	algebraic structures generators isomorphisms
2013-11-19	lecture: algebraic structures	lecture notes more on isomorphisms homomorphic encryption
2013-11-21	lecture: algebraic structures	lecture notes more on isomorphisms CRT and isomorphisms
2013-11-26	lecture: algebraic structures	lecture notes isomorphisms and compression using generators and closures solvability of congruences linear congruence theorem
2013-11-27		assignment #5 due
2013-11-28	recess
2013-12-03	lecture: algebraic structures	lecture notes CRT, generators, and closures generalizing CRT
2013-12-05	lecture: algebraic structures	lecture notes algebra of data structures distributed storage compression
2013-12-10	lecture: review	lecture notes
2013-12-11		assignment #6 due
2013-12-17 Tuesday 3-5 PM GCB 209	final exam