MATH 342, Section 921: Algebra, Coding Theory, and Cryptography
The final exam will be on Friday, June 16 from 3:00-5:30 PM in the usual classroom, LSK 201. For the exam, all you need to bring is your student ID and something to write with. Remember that there will be no makeup exam. Fair warning: you will not be permitted to leave the exam room during the final exam.
For the exam, all the paper you need will be provided for you. No notes, books, calculators, or other aids are allowed; please do not bring cell phones, pagers, alarm watches, or anything else that would make noise during the midterm. You may wish to ensure that you are familiar with UBC's Academic Regulations pertaining to misconduct during exams.
Reading and homework
- Friday, June 16: FINAL EXAM
- Thursday, June 15: review
- Quiz #5: Wednesday, June 14 on all cryptography material
- Solutions to Quiz #5 are now posted
- Tuesday, June 13: this modular exponentiation applet can help you check your answers to homework problems
- assigned Friday, June 9
- Reading: the rest of the RSA article
- Homework: some problems on RSA specially written for you!
- assigned Thursday, June 8
- Reading: sections I, II, III, V, VI, and VII of this article: R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126. Copyright ACM; reprinting privileges by permission of the Association for Computing Machinery.
- Homework: check your previous homework problem answers using this affine cipher applet
- Quiz #4: Wednesday, June 7 on Chapters 7 (syndrome decoding) and 8
- Solutions to Quiz #4 are now posted
- assigned Tuesday, June 6
- Reading: this excerpt from Ramanujachary Kumanduri and Cristina Romero, Number Theory with Computer Applications, Prentice Hall (Upper Saddle River, New Jersey), 1998, ISBN 0-13-801812-X, pp. 131–134
- Homework: Koshy, page 408, problems 9, 11, 13, 15, 17, 21
- assigned Friday, June 2
- Reading: this excerpt from Thomas Koshy, Elementary Number Theory with Applications, Harcourt/Academic Press (Burlington, Massachusetts), 2002, ISBN 0-12-421171-2, pp. 397–408. Emphasize the last section, on Affine Ciphers.
- Homework: pages 93–94, problems 8.5, 8.7, 8.8, 8.10, 8.11(a)
- assigned Thursday, June 1
- Reading: Hill, pages 86–92
- Homework: pages 93–94, problems 8.1, 8.2, 8.3, 8.6, 8.9
- Quiz #3: Wednesday, May 31 on Chapters 5, 6 (except for calculations of probabilities for error correction/detection), and 7 (except for syndrome decoding)
- Solutions to Quiz #3 are now posted
- assigned Tuesday, May 30
- Reading: Hill, pages 81–86
- Homework:
- page 53, problem 5.3
- pages 78–79, problems 7.3, 7.5, 7.6, 7.7, 7.10
- assigned Friday, May 26
- Reading: Hill, pages 71–78
- Homework: pages 78–80, problems 7.1, 7.2, 7.8, 7.9, 7.11
- assigned Thursday, May 26
- Reading: Hill, pages 67–71
- Homework: catch up on all homework problems already assigned
- Quiz #2: Wednesday, May 24 on Chapters 3–5, except for Equivalence of linear codes
- Solutions to Quiz #2 are now posted
- assigned Tuesday, May 23
- Reading: Hill, pages 60–65 (emphasis on Shannon's Theorem)
- Homework: page 65, problems 6.1 and 6.3
- assigned Friday, May 19
- Reading: Hill, pages 55–59
- Homework: pages 53–54, problems 5.1, 5.2, 5.6, 5.7, 5.10
- assigned Thursday, May 18
- Reading: Hill, pages 47–53
- Homework:
- page 39, problems 3.5, 3.6, 3.7
- pages 44–45, problems 4.2, 4.3, 4.4, 4.5
- Quiz #1: Wednesday, May 17 on Chapters 1–2
- Solutions to Quiz #1 are now posted
- assigned Tuesday, May 16
- Reading: Hill, pages 36–38 and 41–44
- Homework: pages 38–39, problems 3.1, 3.2, 3.3, 3.8
- assigned Friday, May 12
- Reading: Hill, pages 31–36
- Homework:
- page 27, problem 2.1 (2nd, 3rd, and 5th sets of parameters)
- page 27, problems 2.4, 2.6, 2.10, 2.11, 2.12
- assigned Thursday, May 11
- Reading: Hill, pages 18–26
- Homework:
- page 10, problem 1.5
- page 27, problem 2.1 (1st, 2nd, and 4th sets of parameters)
- page 27, problems 2.2, 2.7, 2.8, 2.9
- assigned Wednesday, May 10
- Reading: Hill, pages 11–18
- Homework:
- page 10, problem 1.4
- Show that it's impossible to have: (i) a (6,M,7)-code for any M≥2; (ii) a binary (5,33,d)-code for any d≥1.
- Suppose we want a code C to simultaneously correct up to 3 errors (using nearest-neighbor decoding) and also detect up to 7 errors. Show that having d(C)≥11 is enough to guarantee this. By considering repetition codes of length 10, show that d(C)=10 isn't enough.
- assigned Tuesday, May 9
- Reading: Hill, pages xi–xii and Chapter 1
- Homework: page 10, problems 1.2 and 1.3
Course information
When: Tuesdays, Thursdays, and Fridays, 3:00–4:50 PM and Wednesdays 3:00–3:50 PM
Where: LSK 201 (Leonard S. Klinck building)
Textbook: R. Hill, A First Course in Coding Theory (Oxford University Press)—required
Prerequisites: A passing mark in a linear algebra class: one of MATH 221, MATH 223, or MATH 152. We'll be doing matrix computations quite a bit during the course.
Instructor: Prof. Greg Martin
Office: MATH 212 (Mathematics Building)
Email address: gerg@math.ubc.ca
Phone number: (604) 822-4371
Office hours: Tuesdays and Fridays, 11 PM–noon (note: for those taking MATH 302 this summer, you can come to my office right after that class ends at 11:50—I'll have some time to answer your questions even if it goes past noon)
Course description: This course is an introduction to coding-theory (error-correcting codes) and cryptography, with the necessary mathematical background covered along the way. About two-thirds of the term will be spent on coding theory, and the remaining one-third on cryptography. Students will master both algorithmic techniques (computation) and abstract arguments (proofs).
The coding theory information will come from the textbook by Hill, mainly chapters 1–8, covering topics including vector spaces over finite fields, linear codes, dual codes, parity-check matrices, and Hamming codes. The cryptography information will include affine ciphers, RSA cryptography, and Diffie–Hellman public key exchange; for this part of the course, supplemental notes will be posted on this website for free use by students.
Evaluation: Homework will be given, so that you can practice and verify your understanding and skills, but it will not be collected. There will be five in-class quizzes and a final exam. The course mark will be computed as follows:
- Five in-class quizzes (3:00–3:50 PM, each Wednesday from May 17 to June 14, 2006): 50 percent total
- Final exam (3:00–5:30 PM, Friday, June 16, 2006 in the usual classroom, LSK 201): 50 percent
Your lowest in-class quiz score will automatically be dropped, and the other four quizzes will be averaged together to form the quiz component of your final mark. (So each of your four best quiz scores will count 12.5 percent towards your final mark.)
Please bring your student ID to every quiz and to the final exam. You are required to be present at all quizzes and at the final exam. No makeup tests will be given. Non-attendance at a quiz or exam will result in a mark of zero being recorded. Unavoidable, documented medical emergencies are the only exception to this policy. Travel plans will not be considered a valid excuse.
Advice for success:
- Stay caught up! Mathematics is a very cumulative subject: what we learn one week depends crucially on understanding what we learned the week before. Students who fall behind early struggle to catch up for the rest of the course.
- Do the homework problems! It's so tempting not to, because they won't be graded. However, learning to do mathematics is like learning to do anything else: you can't learn how just by watching someone else do it. Trying, struggling, making mistakes, fixing them—these are all part of the learning process.
- Put in the hours! Remember the 2-to-1 rule for university courses: expect to spend 2 hours outside of class for every 1 hour spent in class. In our extremely condensed version, that means 14 hours per week, in addition to coming to lectures, is quite reasonable (and some students will spend more than that). Jump right in and start spending that time; don't wait until later in the course.