CMPT 125 Assignment 1 – O Notation
This
assignment is intended to give you some practice determining and manipulating O
Notation running times. This assignment is worth 5% of your final grade.
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");
}
}
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);
}
}
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");
}
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);
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.
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.
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.
|
|
A |
B |
|
a) |
n/4 |
8×log2n |
|
b) |
n3/10 |
5×n2 |
|
c) |
n2/2 |
20×n×log2n |
|
d) |
n4 |
16×n2×n |
Find the simplest Big O estimate for the following
functions
a)
f(n)
= 5n3-2n2-n+2
b)
g(n)
= (n/10+30)(2n-600)
c) h(n) = (4n – 2)(log (5n +
3))
d) r(n) = (√n+20log2(n)+n/2)(4n+logn+5)
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
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}
Question 6 – Resource
Collection: 6 marks
Resource collection is a common problem in AI. The
input is a data structure that contains the benefits (or hazards) for each
location on a map. The problem is to plan the best route that maximizes the
collected benefits. Note that locations can contain both positive and negative
rewards.
On a map where each location contains a positive reward
(a benefit) the best route would visit each location. On a map where each
location contains a negative reward (a hazard) the best strategy would be to
not move at all!
For our version of the problem the input is an array
of n integers that represents a 1 dimensional map. Positive numbers represent
benefits while negative numbers represent hazards. You are to write a
pseudo-code algorithm that finds the largest possible sum from visiting a
contiguous sequence of array elements. The route can start at any element of
the array.
Your algorithm should be documented with comments. You
should also 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
§ For A = {5, -6, 7, -5, 10, -1} – the best sum consists
of the values in A[2..4] for a total of 7 + -5 + 10 = 12
§ For A = {1, 2, 4, -6, 4, 2, 1} – the best sum consists
of the values in A[0..6] (the entire array) for a total of 8
§ For A = {-5, 2, -3, 1, -5, 4, -2} – the best sum consists of the value in A[5] for a
total of 4
Note that your algorithm is only required to return
the largest possible sum of the benefits, and not the index of the elements in
which they were found – this information is only included in the examples as
explanation.
Assessment
The assignment is out of 36.
Submission
You should submit your assignment online to the CoursSys submission server. Your solution should consist of a single .pdf
file, please read the documentation on Coursys for further information.
The assignment is due by 11:59pm on Monday the 5th of June.
John Edgar (johnwill@sfu.ca)