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 9-10am at PSA 836.

 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.3--1.7 (25%) \$2.1--2.4, 3.1--3.3 (25%) \$4.1, 4.3, 5.1--5.4 (25%) \$6.1--6.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 one-word 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(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) 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 term-by-term):
• (A1) -7-4-1+2+5+8+...+998+1001.
• (A2) 2-6+18-54+....+2*(-3)^n for any positive integer n
• HW6. Due, F 3/2. Instructions.
Problems are ordered following the lectures.
• \$3.1: (use pseudo-code for algorithms) 4,6, 18 (hint: similar to finding the min, but need small change to the comparison operation), 36
• (A1) Discuss the worse-case 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 worst-case 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 pseudo-code 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(n-1) 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