Problem Solving And Programming

CSC 3110
Problem Solving and Programming
Section 901
Winter Term 2020
Final Exam
Name:____________________________________________________
Please read the following comments before beginning the exam.
The final exam consists of five questions and the allowed time is sixty minutes. The questions
may be worth differing numbers of points, so consider this when answering the questions. The
points for each question are shown below. The exam is worth a total of 265 points. The exam is
closed book /closed notes – NOT the case at this point. To receive full credit, all your answers
must be justified.
Must turn in 1 single document containing all answers, hand writing must be clear/readable/clean!
Question 1 (80 Points) __________________
Question 2 (40 Points) __________________
Question 3 (35 Points) __________________
Question 4 (55 Points) __________________
Question 5 (55 Points) __________________
Total (265 Points) __________________

Question 1 (80 points):
Part a (20 points):
Solution
Only assertion b) is true
n(n+1)/2 = n2/2 + n/2 = O(n2)
O(N^2) would mean (roughly) that the number of steps to calculate it grows like N^2, for large
N
Part b (20 points):
Solution
a. Consider the function –
.
The function is equivalent to .

Formally, it is proved by applying the limit.
Therefore, .
b. Consider the function –
.
Therefore, .
Part c (40 points):
Consider the following algorithm.

a. What does this algorithm compute?
b. What is its basic operation?
c. How many times is the basic operation executed?
d. What is the efficiency class of this algorithm?
e. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency
Solution
a. This algorithm computes difference between array’s largest element and smallest
element.
b. The algorithm’s basic operation is element comparison.
c. Let us denote C(n) the number of times the basic operation (element comparison) is
executed and expressing it as a function of size n.The algorithm makes two comparisons
on each execution of the loop, which is repeated for each value of the loop’s variable i
within the bounds 1 and n-1.Therefore,
This is an easy sum to compute because it is nothing else but 1 repeated n-1 times. Thus,