PROFESSOR: Dr. Catherine Yan

OFFICE: Milner 220

TELEPHONE: (979) 862-4476

E-MAIL: cyan@math.tamu.edu,

CLASS: TR 3:55--5:10p.m. in CE 223

OFFICE HOUR: Tuesday 11:00-12:00 p.m. and Thursday 2:30--3:30 p.m.

TEXT: Discrete Mathematics and Its Applications, 6th ed. by Kenneth H. Rosen, MaGraw Hill.
Reading the text is strongly encouraged.

The First-day Handout is available here.

TEST

The first test will be given on February 14, Thursday, 4-5 p.m.

We will cover the first two chapters, and sections 3.1, 3.2 of the text book. This is a closed-book test. Each student is allowed to bring one sheet (8.5in * 11 in) of notes to the test. You can not share your note with others in the test.

The second test will be given on March 27, Thursday, 4-5 p.m.

This test will cover Chapters 4, 5.1-5.4 and 7.1-7.3 of the textbook. This is a closed-book test. Each student is allowed to bring one sheet (8.5in * 11 in) of notes to the test. You can not share your note with others in the test. You may use the calculator if you want.


The third test will be given on May 6th, Tuesday, 1-2 p.m. (the final exam period assigned by the university. )

This test will cover Chapters 5.4--5.5, 8 and 12, except Section 8.6. This is a closed-book test. Each student is allowed to bring one sheet (8.5in * 11 in) of notes to the test. You can not share your note with others in the test. You may use the calculator if you want.



---

Tentative Syllabus.
Math 302 is a course on discrete mathematics. As described in the Course Catalog, we will cover formal structures for describing data, algorithms and computing devices. We will also study the theory and applications of sets, graphs, and algebraic structures.

More specifically, we will cover Chapters 1, 2, 3 (sections 2,4,8), 4 (Sections 1-2), 5 (Sections 1-5), 7, and 8 of the textbook.



Homework Assignment


In each assignment, there are 10 specified problems. You must do all the problems assigned. Your homework will be graded by the completeness, and the correctness for the specific problems.

Homework 1. Assign on 1/22/08. Due on 1/29/2008.

Homework 2. Assign on 1/29/2008. Due on 2/5/2008.

Homework 3. Assign on 2/05/2008. Due on 2/12/2008.

Homework 4. Assign on 2/12/2008. Due on 2/26/2008.

Homework 5. Assign on 2/26/2008. Due on 3/4/2008.

Homework 6. Assign on 3/4/2008, Due on 3/18/2008.

Homework 7. Assign on 3/18/2008, Due on 3/25/2008.

Homework 8. Assign on 3/25/2008, Due on 4/8/2008.

Homework 9. Assign on 4/8/2008 Due on 4/15/2008.

Homework 10. Assign on 4/15/2008, Due on 4/22/2008.

Homework 11. Assign on 4/22/2007. This homework won't be graded.

Extra Credit Assignment

Extra Credit Assignment 1 , posted January 25, 2008. Due on 2/21/2008, in class. Solution

Extra Credit Assignment 2 . posted February 29, 2008. Due on 4/03/2008, in class. Solution

Extra Credit Assignment 3 . posted on April 7, 2008. Due on 5/06/2008, in final exam.

Solution for Quizzes

Quiz 1. 1. contradiction. 2. If he wears white kid gloves, then he is not an opium eater.
Quiz. 2.
1. (a) If 1+1=3, then 2 is even or 6 is prime.
(b) If 2 is odd and 6 is not a prime, then 1+1 is not 3.
(c) If 1+1 is not 3, then 2 is odd and 6 is not a prime.
2. Premises: p -- > (r -- >q), p "and" ( "not" r).
Conclusion: "not" q.
It is invalid. For example, when p and q are True and r is False, both premises are true, but the conclusion is false.
Quiz 3. 1. A={1,3,4,7,9,11}, B={2,4,6,8,9}. 2. C={1,2,4,5,9}, D={5,7,8,9}. 3. True. Using A-B=A "intersects" "complement of "B, de Morgan's law, and the distributive law.
Quiz 4. 1 (a) {0,1,-1}. (b) the union of 4 intervals (0,1], [-1,0), (2,3) and (-3, -2). 2. There are many possibilities. For example, f(n)=1/n, or f(n)=1/2^n.
Quiz 5.
1. Assume there exist real numbers x and y such that x+y >=100, but x <50 and y <50. Then x+y < 50+50=100, contradiction!
2. (It is a standard induction).
Quiz 6.
1. f(n)=big-Theta(n^{2.7} n!). 2. See Textbook, page 188, Theorem 2.
Quiz 7.
(1) 25. If we select 25 books, at most 4 of them can be APL, hence at least 21 of them are on Pascal, FORTRAN, COBOL, or BASIC. By the generalized pigeonhole principle, at least [21/4]+1=6 are on the same computer language. 24 wouldn't be enough, since we may have 4 on APL, and 5 each on Pascal, FORTRAN, COBOL, and BASIC.
(2) (a). Consider the first digit of the integers, and use pigeonhole principle. (b) 111, 222, 333, 444, 555, 666, 777, 888, 999.
Quiz 8. 1. 10*9*8. 2. 6*5*4. 3. C(10, 3), 4. C(6, 3)+C(6,2)*C(4,1).
Quiz 9. 1. C(10, 3). 2. C(6,3), 3. C(9,2)+C(7,2)+C(5,2)+C(3,2).
Quiz 10. 1. See Textbook, page 416, Example 4. 2. (a) a_n^{(p)}=-n2^{n+1}. (b) a_n=A 2^n+B 3^n-n2^{n+1}, where A, B are arbitrary real numbers.
Quiz 11. 1. f(n) =\Theta(n^{\log_2 3}). 2. C(202, 2)-3C(142, 2)+3C(82, 2)- C(22,2).
Quiz 12. 1. R={(1,1), (1, 3), (1, 4), (2,2), (3,1), (3,3), (4,1), (4,4)}. 2. R^2=R\cap {(3,4), (4,3)}. 3. reflexive and symmetric.

MAKE-UP POLICY: Make-ups for missed quizzes and exams will only be allowed for a university approved excuse in writing. Wherever possible, students should inform the instructor before an exam or quiz is missed. Consistent with University Student Rules , students are required to notify an instructor by the end of the next working day after missing an exam or quiz. Otherwise, they forfeit their rights to a make-up.

POLICY FOR ABSENCES: Attendance on a regular basis is expected. While there are occasionally good reasons for you to choose to miss class, my experience has been that there is a strong correlation between attendance (as long as you are awake and listening) and performance in the course.

For absence related to injure or illness, students who are absent from class three or more days should provide instructors with confirmation from a medical provider for an excused absence.

SCHOLASTIC DISHONESTY: Copying work done by others, either in-cl ass or out of class, is an act of scholastic dishonesty and will be prosecuted to the full extent allowed by University policy. Collaboration on assignments, either in-class or out-of-class, is forbidden unless permission to do so is granted by your instructor. For more information on university policies regarding scholastic dishonesty, see University Student Rules .

COPYRIGHT POLICY: All printed materials disseminated in class or on the web are protected by Copyright laws. One xerox copy (or download from the web) is allowed for personal use. Multiple copies or sale of any of these materials is strictly prohibited.