CSE 21: Mathematics for Algorithm and System Analysis (Spring, 2006)

Home | Syllabus | Schedule | Exams | Homework

Homework

Homework is essential to understanding and learning the material. Exams will be similar to the homework problems. Homework will be assigned, but will not be collected or graded. If you'd like your homework to be graded, turn it in to the TA or the Instructor.

The quizzes will be at the beginning of class and will consist of several of the homework problems assigned for that day. For example, the quiz on April 11 will be comprised of several of the homework problems assigned for April 11.

These assignments are a minimum; you'll be well-rewarded by doing additional problems. You need to have lots of practice in solving problems. Consider doing at least every other odd problem in Tucker, and all odd problems in Bender.

There are a few corrections to the Tucker book. There are also corrections to the Bender book. I suggest you make corrections to the book at the beginning of the quarter; it's frustrating trying to figure out why you got a problem wrong only to realize the solution is incorrect.

Day homework is due Homework from Tucker Homework from Bender Homework solutions
April 11 5.1: 1, 9, 11, 15, 19, 25, 35, 45 (see corrections); 5.2: 3, 7, 11, 17, 27, 41 CL: 1.5, 2.1, 2.2, 2.7 ps pdf
April 18 5.3: 9, 13, 19, 29
5.4: 1, 3, 5, 11, 19, 27, 29, 59		 CL: 3.1, 3.2, 3.5 ps pdf
April 25 5.5: 2(b), 3(c), 9(b)
8.1: 13, 17, 19, 25, 33
8.2: 1, 7, 15, 21, 31, 38		 CL: Multiple choice review (pp 41-44): 1-13, 17, 25 ps pdf
May 2 6.1: 3, 11, 17, 21
6.2: 3, 7, 11a, 11b, 15a, 15c, 19, 27 		ps pdf
May 9 6.4: 5, 9, 10 CL: 4.2, 4.6, 4.9, 4.11, ps pdf
May 16 CL: 4.13
DT:1.3, 3.1-3.4, 3.6, 3.7 		See Bender for soln's
May 23 7.1: 7,11, 15, 17, 29, 35
7.2: 1, 9 (when solving, find answer to within a constant factor using the master method
7.3: 2, 3, 5
ps pdf
May 25
  • Solve the recurrence relation T(n) = 2T(sqrt(n)) + 1 with T(1) = 1. Use a change of variable with m = lg n. Don't worry about whether sqrt(n) is integral
  • Show by induction that the following recurrence relation: T(n) = T(n/4) + T(n/2) + T(n/8), T(i) = 3 (i <= 8) has a linear solution (is a constant multiple of n). What is the constant?
  • In the Josephus problem, what is J(39)? J(77)?
  • In the actual Josephus story, every third person died, rather than every second. What is a reccurence relation J' for that problem?
June 6 1.1:2, 25, 36
1.2: 5(a)-(d)
1.3: 2, 3, 5
1.4: 3(a)-(d)
2.1:5, 7
2.2: 1, 2, 17,
3.1: 2, 10, 15, 16, 23
3.2: 6, 7 		ps pdf
June 13 GT 4.1, 4.3, 4.4, 4.5(b) See Bender for soln's