cs2223 Exam 1 Solution

[WPI] [cs2223] [cs2223 text] [News] [Syllabus] [Exams] [Exam 1]

cs2223, D97/98 Exam 1 Solution

Question 1.1

From the maximum rule, p81 of the text,

O(A(n)) = O(max(7*sqrt(n)*ln(sqrt(n)), 2*n*ln(n)))

We can tell which term is larger by looking at the limit of their ratio:

r = lim(n->infinity; (7*sqrt(n)*ln(sqrt(n)))/(2*n*ln(n)))

Since both numerator and denominator go to infinity, we can apply L'Hopital's rule:

r = lim(n->infinity; 7*(ln(sqrt(n))/(2*sqrt(n)) + sqrt(n)/(sqrt(n) * 2 * sqrt(n))) / 2*(ln(n) + n/n)) = lim(n->infinity;(7*((1+ln(n))/(2#sqrt(n)))/(2*(1+lg(n))))) = lim(n->infinity; 7 / (4*sqrt(n))) = 0

This shows that the second term is zero, so:

r = O(2*n*ln(n)) = O(n*ln(n))

We obtain the last result by noticing that constants can be removed as a consequence of the threshold rule on p81 of the text.

Question 1.2

The n-th element of this sequence, in a form which does not contain e, is:

E(n) = sum(k = n+1 -> infinity; 1/k!)

The previous element is:

E(n-1) = sum(k=n -> infinity; 1/k!) = 1/n! + sum(k=n+1 -> infinity; 1/k!)

Their difference gives the recurrence relation:

E(n) - E(n-1) = 1/n!

Question 1.3

Each row adds n new numbrs to the triangle so the recurrence relation is:

C(n) - C(n-1) = n

We can confirm that the guess is correct by substituting into the above equation - this is the second part of the proof by induction; the first part, that C₁=1 is also met.

C(n) - C(n-1) = [n^2/2 + n/2] - [(n-1)^2/2 + (n-1)/2] = (n^2 + n - n^2 + 2*n - 1 - n + 1)/2 = 2*n/2 = n

The guess has been proven to be true.

Grading

The grading criteria are available. These are subject to interpretation by the grader. As we stated in class, our primary goal in the grading of these exams is consistency. If your intrepretation differs from the grader's and the grader has applied her/his criteria uniformly, then the grader's interpretation will prevail.