CSCI2110 Assignment 2
Instructor: Alex Brodsky
Due: 11:59 pm, Thursday, January 30, 2020
The purpose of this assignment is to practice your analysis of algorithm complexity. In the second part of this assignment you will be asked to empirically test the performance of four different data structures for storing and searching.
For each of the algorithms below:
1. State the size of the input in big-Oh. For example, if the input to an algorithm is an array of size k, then the input size is O(k). (1 mark)
2. Derive the cost function for the algorithm. Be sure to show your work like we do in lectures. You can use O(1) to denote all constants. (2 marks)
3. State the complexity of the algorithm in Big-Oh. The complexity MUST be stated in terms of input-size. (2 marks)
Example: Multiplication
input: A[k] // A vector (1D array) of size k
B[k] // A vector (1D array) of size k
output:AB //Amatrixofkxkinsize
R = array[k][k]
for j = 0 … k
for i = 0 … k
R[i][j] = A[j] * B[i]
return R
Solution
1. The inpput size is O(k) + O(k) ∈ O(k) 2. f(k)=O(1)+k×O(k)+k2 ×O(1) 3. f(k) ∈ O(k2)
// new array of size k x k
[O(1)]
[k]
[k] x [k]
[k] x [k] x [O(1)]
[O(1)]
O(1) + k + k × k + k × k × O(1) + O(1) = O(1) + O(k) + O(k2) = O(k2)
1
CSCI2110 Winter 2020 Assignment 2 1 Problem: IsFib
input: F[n] // An array of integers
output: index of integer that is not the sum of the preceding two integers
for j = 2 … n
if F[i-2] + F[i-1] != F[i]
return i
return -1
2
CSCI2110 Winter 2020 Assignment 2 2 Problem: Intersection
input: A[m] // 1D array of size m
B[n] // 1D array of size n
output: Array C all values that are in both A and B
C = array()
size = 0
for i = 0 … m
for j = 0 … n
if A[i] == B[j]
for k = 0 … size
if C[k] == A[i]
break
if k == size
C[k] = A[i]
size = size + 1
return C
3
CSCI2110 Winter 2020 Assignment 2 3 Problem: Longest Sequence
input: A[k] // 1D array of size k
output: index of start of longest sequence
max = 1
max_index = 0
for i = 1 … k
length = 1
for j = i … k
if A[j] != A[j-1] + 1
if max < length
max = length
max_index = i - 1
break
return max_index
4
CSCI2110 Winter 2020 Assignment 2 4 Problem: Sort Of
input: A[k] // 1D array of size k
output: sorted array A
unsorted = true
while unsorted
unsorted = false
for i = 1 ... n
if A[i] < A[i-1]
unsorted = true
tmp = A[i]
A[i] = A[i-1]
A[i-1] = tmp
return A
5
CSCI2110 Winter 2020 Assignment 2 5 Problem: Root of the Problem
input: integer n
output: closest integer that is the square root of n
l=1 h=n
while l < h
r = (1 + n) / 2 s=r*r
if s == n
break if s < n
l=s else
h=s return s
6
CSCI2110 Winter 2020 Assignment 2 6 Problem: Last Resort?
input: A[k] // 1D array of size k, k is a power of 2
output: sorted array A
B = array(k)
size = 1
while size <= k / 2
count = (k / 2) / size
for i = 0 ... count
combine(A, i * size * 2, size, B)
for i = 0 ... k
A[i] = B[i]
size = size * 2
return A
def combine(A, start, size, B)
h = start
i = start
j = start + size
end = start + size
while (i < end) and (j < end + size)
if A[i] <= A[j] B[h] = A[i] i=i+1
else
B[h] = A[j] j=j+1
h=h+1
if j < end + size i=j
end = end + size
while i < end B[h] = A[i] i=i+1 h=h+1
7
CSCI2110 Winter 2020 Assignment 2 7 Justify It!
For each of the following cost functions:
1. Determine the Big-Oh of the cost functions (1 mark) 2. Justify your answer (4 marks)
Example: f(n) = 7 + 42n + 13n3 1. f(n) ∈ O(n3)
2. Letg(n)=n3. Sincen3 ≥n≥1foralln≥1,
f(n)=7+42n+13n3 <7n3 +42n3 +13n3 =62n3 =f′(n)
Therefore,
f′(n)=62n3 ≤c·n3 =c·g(n)
where c ≥ 62 and n ≥ 1. Hence, by the definition of big-Oh, f(n) ∈ O(n3).
(a) Don’t Sweat the Small Stuff: f (n) = 0.0001n4 + 1000n2 + 1000000n
8
CSCI2110 Winter 2020 Assignment 2 (b) It’s Logical: f(n)=n2 +2nlogn+(logn)2
(c) Faster, Higher, Stronger: f(n) = 2n + 3n + n2(log n)2 n2 (log n)3
9
CSCI2110 Winter 2020 Assignment 2 8 Empirical Evaluation of Four Data Structures
In this exercise you will be asked to empirically evaluate four different data structures (im- plemented by the JDK). You will download a Java program called Pam, which allows you to run a performance test on any data structure that is a subclass of the AbstractCollection class. Subclasses of this class include:
• java.util.ArrayList • java.util.LinkedList • java.util.TreeSet
• java.util.HashSet
When you run Pam, it will ask you to specify which data structure to use (one of the above) and the number of operations (N) to perform e.g., 5000. It will then instantiate an object from the specified class, insert N items into the object, and then perform N operations which are a mixture of add(), contains(), and remove(). The program times how long it took to perform these operations, and reports the time. By running the program on the same class for 1000, 2000, 3000, up to 10000 operations, it is possible to visualize the performance of the data structure implemented in the class. By running the program on different classes we can compare the performance of the various data structures.
You will need to run Pam for each of the above classes, with the number of operations ranging from 1000 to 10000 in steps of 1000. Each run should be repeated five times and the total time for each run should be entered into the provided spreadsheet Results.xlsx. As you may notice, you will need to perform 4 × 10 × 5 = 200 runs of the program. You can either do this by hand from your IDE (not advisable), or use the provided script run.sh and run the tests on the csci2110.cs.dal.ca or bluenose.cs.dal.ca unix servers. See the README.txt in the Pam.zip file for instructions how to do this.
Submit the Results.xlsx file as part of the assignment. Using a couple paragraphs, describe what you observe from the tests and any conclusions that you draw. For example, which data structures would you use in the future to keep track of items?
10
CSCI2110 Winter 2020 Assignment 2 Hints and Suggestions
• Use a PDF viewer to annotate the pseudocode to show the questions.
• Feel free to use O(1) instead of specific constants when analyzing the algorithms. • Be sure to show your work!
Marks
Problem 1
Problem 2
Problem 3
Problem 4
Problem 5
Problem 6
Problem 7a
Problem 7b
Problem 7c Empirical Evaluation
5 5 5 5 5 5 5 5 5 5
Total
50
Table 1: Marking scheme for Assignment 2.
What to Hand In
Submit a PDF of your assignment and the Results.xlsx in Brightspace.
11