CMPT 125 Assignment 1 Solution
For each of the following code
fragments determine the worst-case O notation running time and briefly justify
your answer. In each case your answer should be a function of n. If the question refers to an array
you can assume that the size of that array is n. Note that you are not expected to derive a detailed cost
function, just the Big O notation running time.
Example
for (i = 1; i <= n; i++) {
sum = sum + i;
}
Answer: The loop body runs in
a
for (int i = 0; i
< n; i++) {
for (int
j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
printf("%d", arr[i]);
}
printf("\n");
}
}
Answer: O(n) - the inner loops executes a constant
number of operations and the outer loop is executed n times.
b
for (int i = 2; i
<= n; i++) {
int
j;
printf("\n%d:", i);
for(j = 2; j <= i; j = j
* 2){
printf("%d ", j);
}
printf("\n%d:", i);
for(int k = j/2; k >= 2;
k = k / 2){
printf("%d
", k);
}
}
Answer: O(n log n) - the two inner loops perform O(log n) operations each (and one inner loop is not nested within the
other), the outer loop is executed O(n)
times.
c
int i = 0;
int j = 0;
while(i < n){
while(j < n){
printf("{%d,%d}",arr[i],arr[
j++;
}
i++;
j = 0;
printf("\n");
}
Answer: O(n2) - the inner loop executes
n times and the outer loop executes n times
d
int
result = 0;
int i = 0;
while (i < n / 2){
result += arr[i];
i += 1;
while (i >= n / 2 && i <
n){
result += arr[i];
i
+= 1;
}
}
printf("%d\n", result);
Answer: O(n) - this one is fiddly, the inner loop
executes n/2 times and the outer loop
executes n/2 times (suggesting n2) however the entry
condition for the inner loop is true for only one iteration of the outer loop
For each of the following
algorithm descriptions determine the worst-case O notation running time and
briefly justify your answer.
a) A law
firm retains forms recording personal information about their n clients (where n is a positive integer). There is one form for each client. The
forms are kept in a large filing cabinet and are ordered by the client’s last
name. Conveniently, the firm has no two clients with the same last name –
except when the two clients are married to each other. Also conveniently, if a
client is married to another client the two clients always have the same last
name.
Bob, a junior associate, needs
to find all the forms for clients who are married to other clients. His plan is
to go through the entire filing cabinet one form at a time. Starting with the
first form he looks at the client’s last name and compares it with the name on
the next form. If they are the same then the two clients must be married so Bob
takes both forms out of the cabinet. If the two names are different he does nothing.
He then looks at the next form in the cabinet and repeats the process until he
has looked at all of the forms.
O(n) Bob looks at each form once
b) It is a
year later and Kate has re-organized the client files by ordering them by SIN.
Bob again has to find the forms for all clients that are married to other
clients, but his old strategy isn’t going to work anymore since the forms are
no longer ordered by last name. Bob looks at the first file and remembers the
last name. He also puts a yellow post-it note on the form so that he can easily
find it again. He then goes through all of the forms in the filing cabinet
until he either finds another form with the same last name or he gets to the
last form in the cabinet. If he finds a form with the same last name he removes
that form, moves the post-it note to the next form in the cabinet and removes
the form that used to have the post-it note on it (since he has found two forms
for clients that are married to each other). If he doesn’t find a form with the
same name he simply removes the post-it note and puts it on the next form in
the cabinet. He repeats this process until the post-it note is on the last form
in the filing cabinet.
O(n2)
Bob looks at each form in turn and compares it to each of the other forms
Find the smallest positive
integer for which algorithm B out-performs algorithm A. Note: this is referring
to the point from which algorithm B will always perform better than algorithm A
as n gets larger. Unfortunately the
question is slightly unclear if it is looking for the point at which B is
always greater than A or greater than or equal to A.
|
|
A |
B |
solution |
|
a) |
n/4 |
8×log2n |
256
(257) |
|
b) |
n3/10 |
5×n2 |
50 (51) |
|
c) |
n2/2 |
20×n×log2n |
336 |
|
d) |
n4 |
16×n2×n |
16 (17) |
Find the simplest Big O estimate for the following
functions
a)
f(n) = 5n3-2n2-n+2: solution: O(n3)
b)
g(n) = (n/10+30)(2n-600): solution: O(n2)
c) h(n) = (4n – 2)(log (5n
+ 3)): solution: O(n log n)
d) r(n) = (√n+20log2(n)+n/2)(4n+logn+5): solution: O(n2)
In class we looked at an
algorithm to determine whether or not an array contained duplicate values. This
is a related problem. You are to write an algorithm that takes an array of
integers as input and whose output is an array that contains the values in the
input array with the duplicates removed. That is, each distinct value in the
input array should appear once and only once in the output array. The order of
values in the original array does not have to be preserved in the output array.
Write your algorithm using
pseudo-code and document it with comments. Determine the running time of your
algorithm using O notation, as a function of the size of the input array, n.
There are marks assigned to efficiency so the faster your algorithm runs, the
better your grade.
Examples
§
Input:
{1 ,2, 3, 4, 5} – output {1, 2, 3, 4, 5}
§
Input:
{4, 1, 5, 4, 2, 7, 4, 2} – output {4, 1, 5, 2, 7}
§
Input: {12, 3, 12, 12, 12} –
output {12, 3}
Write your algorithm using
pseudo-code and document it comments. Determine the running time of your
algorithm using O notation, as a function of the size of the input array, n.
There are marks assigned to efficiency so the faster your algorithm runs, the
better your grade.
remove_duplicates(arr, n)
Sample Solution
remove_duplicates(arr, n) // n is length of arr
result = empty array
sort(arr)
// using n log n sort
append arr[0]
to result
for(i = 1
to n-1)
if(arr[i] != arr[i-1]
append arr[i] to result
end for
return result
Running time: O(n log n)
Question 6 – Resource
Collection: 6 marks
Solution not provided
John Edgar (johnwill@sfu.ca)