Math 482: Discrete Math II, Spring 2009

INSTRUCTOR: Vivek Dhand, dhand@math.msu.edu

OFFICE HOURS: Wells Hall A-300. Mon. 3-4pm, Tues. 1-3pm, and by appointment.

LECTURE: MWF, 12:40-1:30, Wells Hall C-205.

NOTES: The main textbook for this class will be your class notes. However, I will post some summary lecture notes below.

              1/12: Overview

              1/14: Integers mod n

              1/16: Modular arithmetic

              1/21: Multiplicative inverses

              1/23: Chinese remainder theorem

              1/26: Euler function

              1/28: Order of elements in Z_n

              1/30: Cyclotomic polynomials

              2/2: Fermat's little theorem, Euler's theorem

              2/4: Counting necklaces

              2/6: Public key encryption, Mobius function

              2/9: Mobius inversion formula

              2/11: First order logic

              2/13: Propositional calculus

              2/16: Wilson's theorem, knights and knaves

              2/18: Irreducible polynomials

              2/20: Finite fields and Latin squares

              2/23: Finite projective planes

              2/25: Finite projective planes and orthogonal Latin squares

              2/27: Hadamard Matrices

              3/2: Construction of Hadamard Matrices, Hadamard codes

              3/4: Paley's construction

              3/6: The probability that two positive integers are relatively prime

              3/16: Graphs

              3/18: Ramsey Theory

              3/20: Paley graphs

              3/23: Review of linear algebra

              3/25: The adjacency matrix

              3/27: The adjacency matrix (cont.) and expander graphs

              3/30: The Laplacian matrix

              4/1: The matrix tree theorem

              4/3: The matrix tree theorem (cont.) and Cayley graphs

              4/6: Ramanujan graphs as expanders

              4/8: Edge expansion

              4/10: Two constructions of Ramanujan graphs

              4/13: Partitions

              4/15: Partitions

              4/17: Partitions

HOMEWORK: There will be 12 homework assignments, each worth 50 points. Homework will usually be due every Wednesday. You are encouraged to work in groups, but the final writeup must be your own. You should acknowledge the contributions of others, when appropriate. I will post homework sets and solutions below.

              Homework 1 Due Jan. 21

              Homework 2 Due Jan. 28

              Homework 3 Due Feb. 4

              Homework 4 Due Feb. 11

              Homework 5 Due Feb. 18

              Homework 6 Due Feb. 25

              Homework 7 Due Mar. 4

              Homework 8 Due Mar. 25

              Homework 9 Due Apr. 1

              Homework 10 Due Apr. 10

              Homework 11 Due Friday Apr. 24

              Homework 12 Due Friday May 1

FINAL EXAM: The final exam will be worth 200 points. It will be held on Tuesday, May 5, in Wells Hall C-205, 12:45pm - 2:45pm.

GRADES: In most cases, your final course grade will be primarily determined by the total out of 800 points from homework (600 points) and the final exam (200 points). Approximate grade-lines for the course are as follows:

720-800 is 4.0
640-720 is 3.5
560-640 is 3.0
480-560 is 2.5
400-480 is 2.0
320-400 is 1.5
240-320 is 1.0
below 240 is 0.0

If your total is near a border line, it will be handled individually with consideration of other factors such as attendance, classroom contributions, improvement over time, clarity of homework, etc.