Preparing for week 11

Please do the following in preparation for week 11:

• Read chapter 11 on Limitations of Algorithm Power (skip 11.4); NB this is chapter 10 in the first edition
• Attempt these problems before the tute: 11.1: 2, 5 (10.1: 1, 4); 11.2: 2, 6; 11.3: 1, 2, 6, 7a, 10;
• Read the week 11 lab exercise on dynamic programming
• Submit project 2

Answers to tutorial exercises from chapters 7 and 8

7.1: 4: yes; 7.2: 3a: 996, 3b: 4980, 3c: 996, 6: by the entry t[c] in the shift table for the text's character c aligned against the last character of the pattern; 7.3: 1b: 3, 1c: 10/6, 2b: 6 (for K=19), 2c: 14/6; 8.1: 2b: yes.

Preparing for week 10

Please do the following in preparation for week 10:

• Read chapter 9 (skip 9.4)
• Attempt these problems before the tute: 9.1: 2, 7b, 8 (2, 6b, 7 in first edition); 9.2: 1b, 7; 9.3: 2b;
• Finish the query system and start writing the product sheets

Answers to tutorial exercises from chapters 5 and 6

5.1: 6: yes, 9: Θ(n log n); 5.4: 4b: C(n)=n!, 4c: S(n)=Θ(n!); 5.5: 3b: W(n)=log3(n), 3c: log2(3) = ~1.6; 5.6: 7b: linear (worst case), logarithmic (average case); 6.1: 3a: O(nm); 6.3: 7b: 25/9; 6.6: 5: is convex hull a triangle?