As promised, here (exam_20110114_v2) is a sample exam from 2011. The exam has a total value of 46 points because only 4 points from exercise 2 are mandatory, and the extra 2 points value 6 more points. The minimum grade to pass the exam is 18/40 points.
On your request, a brief solution (Solutions_brief_ADC) written in 30 minutes. In 80 minutes, you have time to expand it.
Is it possible to show us also the solutions for the exercises, to know how should we answer them?
Thank you!
I shall not provide you with the complete answers, just with hints:
A1. You have to compute which is the sum between any function g(n) <= c*f(n) and any function c1 * f(n) <= h(n) <= c2 * f(n). By summing up, you obtain:
(c+c1)*f(n)=<g(n) + h(n) 1 and j > 1
A[i][j] + best[i][j-1] if i == 1 and j > 1
A[i][j] + best[i-1][j] if i > 1 and j == 1
A[i][j] if i==1 and j==1
WordPress has truncated my comment so I have added a bried solution as a pdf. This is all I can offer.
It is ok. Thank you very much!