MAT 243 (class no. 72370, M,W 4:30-5:45pm at LL 14), Fall 2012

Dr. Bin Cheng (email: [first name] -dot- [last name] -at- asu -dot- edu)

Office hours M,W 10-11am at PSA 836; Tu 10-11am at PSA 116.

 Final Exam is comprehensive. Friday, Dec 14, 12:10 - 2:00 PM Approximate distribution of points for each chapter \$1.1, 1.3-1.7 (15%) \$2.1-2.4 (10%) \$3.1-3.3 (10%) \$4.1-4.3 (10%) \$5.1-5.4 (20%) \$6.1-6.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(d-f), 10(c-f), 20, 26(d-f)(briefly explain) 30(c)(e), 38(b)(c).
\$1.6: 4, 10(c-e), 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 term-by-term):
(A2) -7-4-1+2+5+8+...+998+1001.
(A3) 2-6+18-54+....+2*(-3)^n for any positive integer n
• HW6. Due, M 10/22.
\$3.1: (use pseudo-code 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 worse-case complexity of algorithms you wrote for \$3.1 Problems 4,6.
(A2): Compare the worst-case 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 pseudo-code 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(n-1) 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