MAT 243, Fall 2011 (meet: MW 3:30pm  4:45pm at PEBW 144)
Dr. Bin Cheng (email: [my last name] at [math] dot [asu] dot [edu])
Office hours M,W,Th 910am at PSA 836.
MCC (Math Community Center) hours Tu 1011am at PSA 303.
Academic Integrity and
Student Obligations
Academic Calendar
Final Exam: 12:10 PM  2:00 PM, W. Dec 14, 2011 at PEBW 144 (regular classroom)
Announcements:
Review session:
10:00 am  11:50am, W. Dec 7, 2011 at PEBW 144 (regular classroom) 
Midterm 3 Range: in the textbook, it's Section
3.3, 4.1, 4.2, 4.3, 5.1, 5.2
Time: unlimited.

Weight of Mid2 will be changed from 15% to 10%; correspondingly, weight of the Final will be changed from 25% to 30%.

Midterm Exams. Notice the different locations!
Mid1: Tu. Sep 20. (2 hours max) at Testing Center
Mid2: W. Oct 19. (3:30  4:45 pm) in class
Mid3: Tu. Nov 22. (2 hours max) at Testing Center

Course description (PDF)
Please bookmark this link to WebWork, where you can find part of this course's assignments. This moodle website has record of your HW and test scores.
 Written 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 "HW_number_Your_Full_Name" in the title. 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!)
 HW1. Due, W 8/31.
(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)
$1.4: 6(e)(f), 10(b)(c), 16, 28(d)(e), 34, 36
 HW2. Due, (postponed) F 9/9 . All problems need brief explanations rather than a oneword answer, especially those followed by "briefly explain".
(K. Rosen, 7th ed.) $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, F 9/16

HW4. Due, M 9/26
 HW5. Due, W 10/5. $2.3: 6, 8, 12, 14, 22, 28, 32, 36, 42. $2.4: 4(cd), 6(de), 10(abc), 12(cd),14(bdh), 18, 30(cd). 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, Th 10/13.
Skip problems on insertion sorting and change finding $ 3.1: 4,6,14(only trace the binary search),18, 22(also trace your algorithm for input string "short is longer than long"), 36, 38, 52(a), 56(a counterexample would be 15 cents).
$ 3.2: 4(find witnesses), 8(bc)(find witnesses), 10(hint: prove x^4 is not O(x^3) by contradiction), 18, 22, 24.
A1: show that log(n^3) is O(log(n)), then show that log(n^2+10) is also O(log(n)).

HW7. Due, M 10/17
 HW8. Due, W 11/2
$3.3: 3(details, not just an answer), 8, 16(abcd), 18(abcd), 20(bdeg)
Review questions starting on page 232: 7(b), 8(c)(also discuss: are the worstcase and averagecase complexity the same, in terms of number of comparisons?), 9(c)(also discuss: are the worstcase and averagecase complexity the same, in terms of number of comparisons?)
Supp. Excercises starting on page 233: 8
$4.1: 4,6, 10(abcd), 14(ace), 16 (hint: use Theorem 2, the Division Algorithm, to express a=mq+r, b=mq'+r'; note that r=r' is not a premise, but rather our *conclusion* in this proof; the premise is a=b (mod m) and can be rewritten using definition of congruence ... ), 20(ab), 22(ab), 24(bc), 26, 28(ac), 30(ab), 34, 38, 40
$4.2: 2, 4(bc), 6(c), 8, 12, 22(bd)
 HW9. Due, W 11/9
$4.2: Trace Algorithm 2 on page 251 for *binary* integers a=(1011011)2 and b=(111001)2,
that is, record every value of d, sj and c in the for loop.
$4.3: 4, 8, 24, 32(de)
$5.1: 4, 12, 14
 HW10. Due, W 11/16
$5.1: 16,18,22,24,32,34,42
$5.2: 2, 4, 10, 14
Also , these fun problems
 HW11. Due, M 11/28
$5.3: 6(acd), 8(ad), 24(ab)
$5.4: 2, 8, 10, 32
 No HW12. However, remember Webwork due T 12/6.
 Other materials
 Some hints on HW 2 (PDF).
 A proof to a set identity (PDF).
 Time line for classes Oct 24  Dec 07.
 Some solutions to Test 2.