MAT 243, Discrete Mathematical Structures , Summer 2011
(5/317/1. MF 10:40am12:15pm at PSA 304)
Dr. Bin Cheng
Email: [my last name]_at_math_dot_asu_dot_edu
Office hours: Tu,W,Th 9:30am10:30am at PSA841
Academic Integrity and
Student Obligations
Final Exam Room is at Pablo 105. Time is 9:20am12:10pm, Friday, July 1st!. A doublesided 8" by 11" sheet of notes is allowed in the exam. 
Sections to be covered in the Final
$1.11.6, $2.12.4, $3.13.6,$4.14.4, $5.15.3, 5.5, $6.1

Course description: Logic, sets, functions, elementary number theory and combinatorics, recursive algorithms, and mathematical reasoning, including induction. Emphasizes connections to computer science.
 Textbook. Discrete Mathematics and Its Applications (Author: Kenneth H. Rosen; Publisher: McGrawHill; 6th Ed.)
 Exams: Midterm I June 10 ( Chapter 1,2); Midterm II June 24 ( Chapter 3,4,5); Final July 1 ( Comprehensive).
 Prerequisite: 1 semester of calculus or computer programming.
 Grades. Homework 20%; Midterm I 20%; Midterm II 20%; Final 40%.
 Communications. Please check your emails at least once a day for class announcements and individual correspondence.
 Tentative time line. Please read corresponding sections before each class.
 Week 1. [5/31 $1.11.2] [6/1 $1.3] [6/2 $1.41.5] [6/3 $1.61.7]
 Week 2. [6/6 $2.12.2] [6/7 $2.32.4] [6/8 $3.1] [6/9 $3.23.3] [6/10 $3.43.5]
 Week 3. [6/13 $3.63.7] [6/14 $4.1] [6/15 $4.2] [6/16 $4.3] [6/17 $4.4]
 Week 4. [6/20 $5.15.2] [6/21 $5.3] [6/22 $5.5] [6/23 $5.4] [6/24 $6.1]
 Week 5. [6/27 $7.1] [6/28 $7.2] [6/29 $7.3] [6/30 Review] [7/1 Final]
 Homework (The due time is at midnight for both hard copy and electronic copy. The ONLY acceptable electronic format is a single PDF file with your name and HW number in the title.)
 HW1 Due June 6. Answers to oddnumbered excercises can be found on Page S1 through S5.
$ 1.1: Please do
 Subproblem (a)(c)(e) of Problem 4,5,9,10,18,19,28;
 Subproblem (c)(d) of Problem 13,14,21,22;
 and Subproblem (c) of Problem 23,24,38.
$ 1.2: Please do
 Problem 6,16,31,32;
 and Subproblem (b)(d) of Problem 7,8,10,12.
From here on, assignments like the one above will be stylishly denoted as
$1.1: (ace)*(4.5.9.10.18.19.28)+(cd)*(13.14.21.22)+(c)*(23.24.38)
$1.2: (6.16.31.32)+(bd)*(7.8.10.12)
 HW2 Due June 10. Answers to oddnumbered excercises can be found on Page S5 through S10.
$ 1.3: (ad)&(5.6.8.10)+(e)*(18.20.28.32.33)+d*(22)+(f)*(12.25)+(c)*(52.53)  show steps for Problem 52,53.
$ 1.4: (ab)*(1.2)+(def)*(4.6)+(e)*(8.9)+(j)*(12)+(d)*(24.25.26.27.28.30.31)+(40.46)
$ 1.5: (abcde)*4+(de)*(10)+(ac)*(13.14)+(b)*(19.20)+(7.8.28.30)
$ 1.6: (2.6.15.16.18.24.30)
20% bonus points if you can use proper logic to show that it is impossible to satisfy this kid's requests regarding the weekend's activities.
 HW3 Due June 14.
$ 2.1: (6.14.23.34).
$ 2.2: A useful identity is A  B = A intersect (complement B)
(2.4.12.14.25.29{use Venn Diagrams}.31.50)+(a)*(15)+(be)*(18).
Also, prove that A and B are disjoint iff A union B = A + B
$ 2.3: (2.4.10.11.12.16.32.33.36)+(ab)*(18.26)+(ac)*(38)
$ 2.4: Use formulas even for a short summation
(2.14)+(b)*(16.18)+(e)*(6)
 HW4 Due June 20. Please try to make the file size under 1M; this could be done by NOT using the "color" option in you scanner software. Using a lower resolution could also help. Thanks!
Problems outside the textbook are here. Problem A3, as discussed in class, will be similar to this pseudocode algorithm  sorry, corrected version is here.
$ 3.1: 6,20, 36, 40
$ 3.2: 6, 8(a), 18(hint: each term in the sum is no greater than n^k), 24(b), 44
$ 3.3: 4, 10
$ 3.4: 4, 6, 10(c), 16(d), 18, 20
$ 3.5: 2, 4(ab), 10, 14(a), 24
 HW5 Due June 24.
$ 3.6: 1a), 4a), 6, 10, 30.
$ 4.1: 6 14, 18, 32(hint: (n+1)^3=n^3+3n^2+3n+1), 38(Hint: first show that: (A1 subset B1) and (A2 subset B2) implies (A1 union A2) subset (B1 union B2)).
$ 4.2: 4, 10.
$ 4.3: 4b),8c), 24a)b)c).
$ 4.4: 2, 8, 24, 32.
 HW6 Due June 28.
 HW7 Due July 1.
$ 5.1: (you can use formulas from $ 5.3) 4, 22(efg), 26, 46.
$ 5.2: 2, 6, 18.
$ 5.3: 4, 12, 22(a), 30.
$ 5.5: 2, 4, 6, 8, 10.
$ 6.1: 2, 4, 6, 8, 10.
 Other materials
 Hints for some problems in HW4 and HW5, in HW6 (i.e. extension of HW5) and a possible pseudocode for Problem A3 of HW4.
 Practice problems for Chapter 1.
 Practice problems for Chapter 2.
 Test 2 is postponed to Monday (Note that the Testing Center closes at 4:45, according to past experiences).
There will be no practice this time. Please study HW 4 and 5 and I will write solutions to SOME hard problems.
Only Chapter Three (3.1  3.6) and Four (4.1  4.4) will be covered in this test. Chapter Five will not be included thought it was originally planned so.