Steve Homer

Room 281 MCS, 353-8927, homer@cs.bu.edu

Office Hours: Tuesday 11-12 and Thursday 12-2

Teaching Assistant: Maryam Ghasemi, Room PHY 223, phone: 358-2359

Office Hours: wednesday 5-6 and Thursday 12-2.

Text: A Concrete Introduction to Higher Algebra by Lindsay Childs, Springer Press

The course home page is located at: http://www.cs.bu.edu/~homer/235

Prerequisites: To handle this material you need to know basic mathematical concepts concerning sets, logic, integers and induction (basically CS 131), and the programming and data structures covered in CS 112.

Course description: Basic concepts and algorithms for manipulation of algebraic objects, such as residues, matrices, polynomials. Applications to some areas of computer science (cryptography, fault-tolerance). The course emphasizes rigorous reasoning and analysis, and the skills for manipulating abstractions.

We will focus on the algebraic properties of algebraic structures (integers, polynomials, matrices) and on several algorithmic applications of these properties to specific problems in computer science. These include the ideas underlying error correcting codes, simple cryptosystems and interpolation and approximation of numeric functions.

There will be about 6 problem sets, two quizzes and a final. The course grade will be based on homework: 40%, 2 1-hour quizzes: 15% each, and final: 30%.

Points will be taken off for late homework and incompletes will not be given.

Course Outline:

Week 0: Introduction and examples

Week 1: Division and congruences

Week 2: More congruences and arithmetic mod m

Week 3: Applications of congruences and prime numbers

Week 4: Rings and fields

Week 5: Applications of Rings and Fields

Week 6: Error-correcting codes

Week 7: The Theorems of Fermat And Euler

Week 8: Groups

Week 9: The Chinese remainder theorem and applications

Week 10: Polynomials

Week 11: Cryptography and more error-correction Week 12: Interpolation and approximation

Week 13: Factoring polynomials

Week 14: Wrap-up and review