5.1 26, 5.1 37

## Partial Suggested Review Starts here

• 1-8, P88 11, 12, 14, 16, 18, 20, 41,42

• Ch. 1 suppl., P92 14e,f, 15, 17, 20

• 2.1 P103: 7, 9, 12 and big-O, 17 and big-O, 21 (determine divide and conquer), 25

• 2.2 P111: 15, 16, 19

Write an algorithm for the division algorithm and determine number of steps (in terms of inputs). Then find a divide and conquer algorithm to compute gcd(a,b). Compute it's complexity using 5.3 where you could set f(n) to be the maximum number of steps needed to compute gcd(a,b) for any a,b at most n. You should be able to get f(n)=f(n/2) + g(n) (with g(n) not too big) by going two steps at a time.

• 2.3 P124: 9, 15, 16, 25, 27

• 25 P149: 2, 3, 4, 8, 24

• Review P164: 10, 11, 13

• 3.2 P198: 4, 6, 11, 12, 17, 20, 25, 31, 43

• 3.3 P209 4, 5, 12, 15, 35

• 3.4 P217: 4 but ensure O(log n), 15, 18, 23

• Review P228: 40, 41 then use A3 to test, 42, 43, 44

• 4.2 P248: 4, 5, 7, 8, 20, 23, 29

• 4.3 P258: 8, 11, 15, 16, 24, 29, 36, 38, 48, 50, 51

• 4.6 P290: 6, 8, 16, 27, 28, 33

• 5.1 P315: 3 (look over your answers to compare with 5.2 method), 4, 14, 15, 17 (also work these next few in reverse, use your counting recurrence to give you an idea of inductive definition in the sense of 3.3), 19, 21, 31 (hint: take your n-th line and start at one end and walk along counting regions that are changed = split by it).

• 5.2 P324: 4, 8, 15, 20 (check with A3 technique), 21, 22

## Review ends here

Let's move the old problems..