MATH 455, Spring 2006

Hao Wu     Office: LGRT 1546     Office Hours:     TuTh 4:00 - 5:00 and by appointment     Phone: 545-1709     Email :

Susanna S. Epp, Discrete Mathematics with Applications, Third (3rd) edition

1. Multiple evening and/or final exams at the same time: By Official University Regulations, you should go to the Registrar's Office for a statement of conflict. The Registrar will determine which course has precedence. If I am required to give you a makeup, you should then give Registrar's form to me. Two weeks notice is required; failure to complete this procedure in timely fashion may result in a ZERO on the examination.
2. Medical problems: For these you must submit a statement from a medical professional. It is your right not to disclose any details, but we must be assured that you are medically incapable of performing the activity for which you are requesting a makeup; a statement from a medical professional to this effect will suffice. If advance notice is possible and not given I may refuse your request.
3. Emergency absences from campus: Notify the Dean of Students (5-2684), who will then centrally verify the details and notify each of your instructors (including me). This is more efficient than going to each instructor separately and verifying your reason.
4. Religious observances: State Law and University regulations require that a student be excused from academic pursuits on days of religious observances. The University provides a list of major observances, of which there are none on the days of the tests. The regulations also require that the student notify instructors, in writing, at the beginning of the semester or the student may not be excused. The deadline for notification is February 6, 2006.
5. Other circumstances: Contact me and explain the problem. (You should provide a written statement.) I will evaluate the reasons that you have given and come to a decision. Note that it will not be possible to give makeups to accommodate travel plans.

• See me in class.
• Go to my office hours.
• Email me.
• Call me.
• The excuse that it was impossible to find me will not be accepted.

• Homework problem sets will be assigned and collected on a weekly basis. Late problem sets will not be accepted for any reason.
  Homework Grading Policies:
  • Each problem set is worth 5 points;
  • 3 of these 5 points are for "general impression";
  • In each problem set, two or three problems will be graded in detail. The remaining 2 points are assigned according to a student's performance on these problems.
• Several one-problem-quizzes will be given during the semester.
  Quiz Grading Policies:
  • Each quiz is worth 2 points;
  • 1 of these 2 points is for simply handing in the quiz;
  • The other point is for the right solution of the problem.

• Counting
  • 6.1 - Counting and probability
  • 6.2 - Possibility Trees and the Multiplication Rule
  • 5.1 - Basic definition of set theory; 5.2 Properties of sets
  • 6.3 - Counting Elements of disjoint sets: The Addition Rule
  • 6.4 - Counting Subsets of a set: Combinations
  • 6.5 - r-Combinations with Repetition allowed
  • 6.6 - The Algebra of Combinations
  • General form of Inclusion/Exclusion, Mismatching Letters (Page 1, Page 2, Page 3)
  • 6.7 - The Binomial theorem
• Induction and Recursion
  • 4.1 - Sequences
  • 4.2 - Mathematical Induction I
  • 4.3 - Mathematical Induction II
  • 4.4 - Strong Mathematical Induction and the Well-Ordering Principle
  • 8.1 - Recursively defined sequences
  • 8.2 - Solving recurrence relations by Iteration
  • 8.3 - Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients
• Functions and O-notation
  • 7.1 - Functions defined on General sets
  • 7.2 - One-to-One and Onto, Inverse functions
  • 7.3 - Application: The Pigeonhole Principle
  • 7.4 - Composition of functions
  • 7.5 - Cardinality (Notes)
  • 9.1 - Real-valued functions of a real variable and their graphs
  • 9.2 - O-notation (Notes)
  • 9.3 - Application: Efficiency of Algorithms I. Sequencial search, insertion sort
  • 9.4 - Exponential and logarithmic functions: graphs and orders (Notes)
  • 9.5 - Application: Efficiency of Algorithms II. Binary search, merge sort (Notes)
• Graphs and Finite State Automata
  • 11.1 - Graphs, degree
  • 11.2 - Paths, circuits. Connectedness. Euler circuits
  • 11.2 - Euler circuits. Hamiltonian circuits. Euler's formula
  • 11.3 - Counting paths. Adjacency matrix.
  • 12.2 - Finite state automata
• Error-correcting codes
  • Codewords, Hamming distance. Hamming 4-7 code
  • More Hamming codes, t-error correcting codes
  • Check sum for ISBN, American banking system, barcodes

Due Date	Problems
02/10	6.1 # 1, 4, 10, 14, 19, 22, 29, 32 6.2 # 5, 7, 16, 36 (b,d) Prove using "element argument": (A \ B)(B \ A) = (AB) \ (AB), for any two sets A and B.
02/17	6.3 # 10, 18 (b,c), 22, 27 6.4 # 5, 7, 20, 22
02/24	6.5 # 6, 13, 16 6.6 # 16, 18 4.1 # 56 4.2 # 11, 20, 28
03/03	6.7 # 17, 18, 22, 32 (hand in) Practice Exam 1 and Practice Exam 2 (do not hand in)
03/10	4.3 # 3, 7, 25 4.4 # 6, 7, 17
03/17	8.1 # 4, 6, 14, 23, 30, 37 8.2 # 7, 32, 13, 38, 52
04/07	8.3 # 9, 15, 26 7.1 # 2, 5(b,c), 6(b,c), 27(b,d), 34, 41, 46 7.2 # 9 (b,c,d), 13, 23 7.3 # 4, 13, 19, 33
04/14	7.4 # 2, 6, 22 (hand in) Practice Exam 1 and Practice Exam 2 (do not hand in)
04/21	7.5 # 5, 9, 11, 23, 38
04/28	9.1 # 5, 6, 18, 19 9.2 # 9, 27, 45, 48
05/05	9.3 # 19, 21, 38, 42 9.4 # 13, 23, 36
05/12	9.5 # 3, 5, 20, 22 11.1 # 4, 7, 17, 18, 20, 21, 24(b)
05/17	11.2 # 2, 5, 15, 17, 24, 47 11.3 # 4(b), 5(b), 19, 23

Last updated on May 18, 2006.