AMCS 603, Spring 2018

Dr. Jim Haglund,
Course webpage:

Office hours: Wednesday, 11:00-11:50am in DRL 4E2B.
Office Phone: 215-573-9093

Lecture: TR noon-1:20pm in DRL 4C8

Homework Assignments: There will be recommended HW assignments (not to be turned in) and some required HW assignments (to be turned in and graded). The assignments will be posted at the bottom of this web page. You will occassionally be required to present solutions to select homework problems before your classmates.

Course: Algebraic Techniques for AMCS II: We begin with an introduction to group theory. The emphasis is on groups as symmetries and transformations of space. After an introduction to abstract groups and the basic facts about finite groups, we discuss finite fields and applications to coding theory. We incorporate some examples using Game Theory and Linear Programming. Depending on availablr timre, we may also cover the basics of Grobner basis theory.

Text: We will be using Lecture Notes for "Algebra and Applications" by Robert Calderbank, copies of which will be passed out the first day of class. A companion text is "Algebra", 2nd edition, by Michael Artin, which is on reserve in the math/physics library, 3rd floor DRL. A reference for Game Theory is " Game Theory" by Thomas S. Ferguson, available free online at his UCLA webpage.

Exams and Grades: There will be two hour exams and a final exam. Each hour exam counts 25% of your grade, and the final exam counts 40%. HW and presentations count 10%. Hour exam 1 will be on Thursday, Feb. 15 from noon-1:20pm in DRL 4C8, and Hour exam 2 will be on Thursday, March 29, also from noon-1:20am in DRL 4C8. The final exam will probably be a take-home exam.

Midterm 1: Covers material from Lectures 1 through 5 in "Algebra and Applications" lecture notes by R. Calderbank, except pages 9-10 from Lecture 1 and pages 10-12 from Lecture 4. Also includes other topics discussed in class through the Tuesday, Feb. 6 lecture, including the RSA cryptosystem.

Midterm 2: Covers material from Lectures 6, 7, 8, 9, 11, and 12 (except for pages 1-4 of lecture 6, pages 7-12 of lecture 7, and pages 10-13 of lecture 12) in "Algebra and Applications" lecture notes by R. Calderbank.

Important Dates:
First day of classs: Thursday, January 11
Midterm 1: Thursday, Feb. 15 from 12-1:20pm in DRL 4C8
Drop period ends: Friday, Feb. 16
Spring Break: March 3-11
Midterm 2: Thursday, March 29 from 12-1:20pm in DRL 4C8
Last day to withdraw from a class: Friday, March 30
Last Day of Classes: Wednesday, April 25

Homework Assignments:

HW1, due Tuesday, 1/30:
1. Problem set "Introduction to Finite Groups", problems 1-4.
2. Consider the following game, as described in class. A warden tells seven prisoners that tomorrow they will be placed in a circle, and each given a randomly chosen black or white colored hat. Each prisoner will be able to see the color of all the other prisoners' hats, but not their own hat. Then each prisoner must either guess the color of his/her hat (either black or white), or pass. If any prisoner guesses wrong, or if all prisoners pass, then the prisoners lose and are all returned to jail. Otherwise they win and are all set free. The prisoners will be required to all guess/pass simultaneously, and will not be able to communicate in any way after seeing the hats.
Number the prisoners 1,2,...,7 as you go around the circle. Recall that the Nim sum of a set of positive integers is obtained by expressing each of the numbers in binary, then adding them together using 1+1=0, 1+0=0+1=1, 0+0=0. For example, the Nim sum of 7 and 11 is 12, since in binary 7=0111, 11=1011, and adding 0111 and 1011 we get 1100 which is 12 in binary. Let S be the following strategy: Each player computes the Nim sum of all the numbers of the prisoners with black hats that he/she can see; if this is zero, he/she guesses black. If it equals his/her own number, he/she guesses white. Otherwise, he/she passes.

(a) Show that the probability that the prisoners win is 7/8.
(b) Prove that this strategy is optimal, i.e. that there is no way to do better than 7/8.

3. Say we are using an RSA public key cryptosystem as described in class on 1/23. We publish the public keys m=1591 and s=13. Our friend sends us a secret two-letter message which is encoded as the number sequence y=975. What is the decoded two-letter message?

HW2, due Tuesday, 3/13: Problem set "Group Theory and Finite Dimensional Lattices", problems 1,2,3,5. (Do the Challenge for extra credit).

HW3, due Tuesday, March 27: Problem set "Finite Groups of Rotations and the Sylow Theorems", problems 1, 3, 4, 5. Also, solve the game of Battleship on a 3 by 3 square as described in Part II, section 3.7, problem 15 in the online book "Game Theory" by Tom Ferguson (see link near the top of this webpage). Prove your invariant stategy is optimal.

HW4, due Tuesday, April 24. Problem set "Euclidean Domains, Finite Fields, and Error Correcting Codes": #1 (page 1) , #2 (page 1) , #3, #5, #6

Take-Home Final Exam, due Friday, May 11 by 12 noon. (Can be turned in under my office door or by email as a pdf file.) Problems 1,2,3,5,7 from the "Final Examination" at the back of the Calderbank lecture notes. Also, do problems 3,4 from the "Midterm Examination" at the back of the Calderbank lecture notes.