MAT 243, Spring 2012 (meet: MWF 10:45am  11:35am at LL 60)
Dr. Bin Cheng (email: [first name] dot [last name] at asu dot edu)
Office hours M,W,Th 910am at PSA 836.
Academic Integrity and
Student Obligations
Academic Calendar
Announcement: Final exam: Monday, April 30. 9:50  11:40 AM. in the regular classroom LL 60..
No notes or books. Calculator OK! 
Range (percentage):
$1.1, 1.31.7 (25%)
$2.12.4, 3.13.3 (25%)
$4.1, 4.3, 5.15.4 (25%)
$6.16.3 (25%)


Course description (PDF updated Jan 13).
Please bookmark this link to WebWork. This moodle website has record of your HW and test scores.
 Exams
 Test 1. M. Jan 30. in class
 Test 2. M. Mar. 5 in class.
 Test 3. M. Apr. 9 in class. date changed
 Final. Monday, April 30. 9:50  11:40 AM. Room TBA
 Written homework
Instructions.
 HW1. Due, W 1/18.
(K. Rosen, 7th ed.) $1.1: 6(d)(e), 8(f)(g)(h), 14(f), 16, 28, 32(d), 42
$1.3: 8(c)(d), 12(a)(c)
 HW2. Due, F 1/27. All problems need brief explanations rather than a oneword answer, especially those followed by "briefly explain".
(K. Rosen, 7th ed.)
$1.4: 6(e)(f), 10(b)(c), 16, 28(d)(e), 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) 28, 30.
 HW3. Due, M 2/6.
$1.7: 2, 6, 16, 24, 28
Chapter 1 Supplementary Exersices (page 112): 4a), 20, 32.
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.
 HW4. Due, M 2/13.
$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)
 HW5. Due, M 2/20. Instructions.
$2.3: Briefly explain 12, 14(a,c,e), 22(a,b), 28, 32, 36, 42(c).
$2.4: 6(d,e), 10(a,b,c), 14(b,d,h), 18, 30(c,d).
Compute using formulas (not termbyterm):  (A1) 741+2+5+8+...+998+1001.
 (A2) 26+1854+....+2*(3)^n for any positive integer n
 HW6. Due, F 3/2. Instructions.
Problems are ordered following the lectures.
 $3.1: (use pseudocode for algorithms) 4,6, 18 (hint: similar to finding the min, but need small change to the comparison operation), 36
 (A1) Discuss the worsecase complexity of algorithms you wrote for $3.1: Problems 4,6.
 $3.3: 2,4, 20(bdfg)
 $3.2: 4 (find witnesses), 8(bc) (find witnesses), 10 (hint: prove x^4 is not O(x^3) by contradiction), 22.
 (A2): Compare the worstcase complexity of the linear search and binary search algorithm. Briefly explain.
 HW7. Due, W 3/14. Instructions.
Problems are ordered following the lectures.
 $4.1: 4,6, 14(de), 22(ab), 26, 28, 30.
 $4.3: 4, 32.
 HW8. Due, F 3/30. Instructions.
Problems are ordered following the lectures.
 A1: write a pseudocode to determine if an integer n>1 is a prime. The complexity can be at most O(n^(1/2)).
 $5.1: 14, 16, 18.
 HW9. Due, F 4/06. Instructions.
Problems are ordered following the lectures.
 $5.1: 20.
 $5.2: 4, 10.
 $5.3: 12,22, 24(b).
 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.
 A2: follow Definition 5 on page 353 to construct a full binary tree T4 using these steps (plot all intermediate trees T0, T1, T2, T3 ... in this process)
T0 consists of a single vertex.
Use a common root and connect it to a T0 and another T0; name this tree T1.
Use a common root and connect it to a T1 and a T0; name this tree T2.
Use a common root and connect it to a T1 and another T1; name this tree T3.
Use a common root and connect it to a T2 and a T3; name this tree T4.
 HW10. Due, F 4/20 (postponed). Instructions.
Problems are ordered following the lectures.
 $5.4: 4, 10, 24, 32.
 $6.1: 8, 12, 14, 24(e)(f)(h), 46.
 HW 10 is the last set of written homework; but there are a few
WebWork problems.
 Other materials