MAT 243 (class no. 72370, M,W 4:305:45pm at LL 14), Fall 2012
Dr. Bin Cheng (email: [first name] dot [last name] at asu dot edu)
Office hours M,W 1011am at PSA 836; Tu 1011am at PSA 116.
Academic Integrity and
Student Obligations
Academic Calendar
Final Exam is comprehensive. Friday, Dec 14, 12:10  2:00 PM
Approximate distribution of points for each chapter
 $1.1, 1.31.7 (15%)
 $2.12.4 (10%)
 $3.13.3 (10%)
 $4.14.3 (10%)
 $5.15.4 (20%)
 $6.16.4 (25%)
 $7.1 (10%)


Course description (PDF ).
Please bookmark this link to WebWork. This moodle website has record of your HW and test scores.
 Written homework.
All problems are taken from the textbook by K. Rosen, 7th ed.
Instructions.
 HW1. Due, W 9/5.
$1.1: 6(d)(e), 8(f)(g)(h), 14(f), 16, 28, 32(d)
$1.3: 8(c)(d), 10(a)(c)
 HW2. Due, W 9/12.
$1.3: 12(a) note: the statement is given in Problem 10(a).
$1.4: 6(e)(f), 10(b)(c), 28(d)(e).
 HW3. Due, W 9/19. $1.4: 16, 34, 36.
$1.5: 4, 6(df), 10(cf), 20, 26(df)(briefly explain) 30(c)(e), 38(b)(c).
$1.6: 4, 10(ce), 18, 20(briefly explain).
 HW4. Due, M 10/01.
$1.6: 28, 30
$1.7: 2, 6, 16, 24, 28(note this is an "if and only if" problem)
Chapter 1 Supplementary Exersices (page 112): 4a), 20, 32(pay special attention to (a)).
Please also do these 2 problems.
(A1) Prove that for any real numbers a,b,c, if a+b+c>40, then a>10 or b>10 or c>20.
(A2) Prove that for any real, positive numbers x,y,z, if x*y=z^2, then x>=z or y>=z.
 HW5. Due, M 10/08.
$2.1: 16, 20, 26, 32(b), 42(b)(d), also (A1) Find the power set of {a,b,{a,b}}.
$2.2: 4, 14, 18(c)(d).
$2.3: Briefly explain 12, 14(a,c,e), 22(a,b), 28, 32, 36.
$2.4: 6(d,e), 10(a,b,c), 14(b,d,h), 18, 30(c,d).
$3.2: 4 (find witnesses), 8(bc) (find witnesses), 22, 10 (hint: prove x^4 is not O(x^3) by contradiction).
Compute using formulas (not termbyterm):
(A2) 741+2+5+8+...+998+1001.
(A3) 26+1854+....+2*(3)^n for any positive integer n
 HW6. Due, M 10/22.
$3.1: (use pseudocode for algorithms) 4,6, 36, 18 (hint: similar to finding the min, but need small change to the comparison operation)
$3.3: 2,4, 20(bdfg)
(A1) Discuss the worsecase complexity of algorithms you wrote for $3.1 Problems 4,6.
(A2): Compare the worstcase complexity of the linear search and binary search algorithm. Briefly explain.
 HW7. Due, W 10/31.
$4.1: 4,6, 14(de), 22(ab), 26, 28, 30.
$4.3: 4, 32
A1: write a pseudocode to determine if an integer n>1 is a prime. The complexity can be at most O(n^(1/2)).
 HW8. Due, W 11/07.
Suggestion: if time allows, work on the blue problems in HW9 (but still submit them along with the rest of HW9).
$5.1: 14, 16, 18, 20
$5.2: 4, 10
 HW9. Due, W 11/14.
$5.1: 34
$5.2: 14
Page 379 (Supplementary exercises): 4
$5.3: 8(a)(c), 12, 24(b)
$5.4: 4, 10, 24, 32
A1: define f(n) recursively as: f(0)=1, f(1)=3, and f(n+1)=4f(n)3f(n1) for n>0. Use strong induction to prove that f(n)=3^n.
 HW10. Due, M 12/10.
$6.1: 8, 12, 14, 24(e)(f)(h), 46
$6.2: 2, 4, 18
$6.3: 12. (Remember the big Webwork sets for practice and for points)
$6.4: 8
A1: write your work in details for Problem 1 of Webwork set named "7_Prob".
 Other materials
2012 is Alan Turing Year