AMCS 603, Spring 2019

Dr. Jim Haglund,
Course webpage:

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

Lecture: MWF 11-11:50am in DRL 4C8

Homework Assignments: There will be several 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 available time, 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 Wednesday, Feb. 20 from 11-11:50am in DRL 4C8, and Hour exam 2 will be on Wednesday, April 3, also from 11-11:50am in DRL 4C8. The final exam will probably be a take-home exam.

Midterm 1: Covers material from Lectures 1 through 6 in "Algebra and Applications" lecture notes by R. Calderbank, except pages 9-10 from Lecture 1, pages 10-12 from Lecture 4, and pages 3-4 of Lecture 6. Also includes the game of Nim and the RSA cryptosystem, as discussed in class.

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

Homework Assignments:

HW1, due Monday, 2/11

1. 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.

2. Problem set "Introduction to Finite Groups", problems 1-4.
3. Say we are using an RSA public key cryptosystem as described in class on 1/1. 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 Friday, 3/1: Problem set "Group Theory and Finite Dimensional Lattices", problems 1, 2, 3, 5. (Do the Challenge for extra credit).

HW3, due Monday, April 8: Problem set "Finite Groups of Rotations and the Sylow Theorems", problems 1, 3, 4, 5. Do the challenge for extra credit.