Task 1:

Which statements are correct about these following seven runtime functions :

T(N) = 999 T(N) = log2N T(N) = N T(N) = N + 999 T(N) = 5 * N T(N) = N * log2N T(N) = N2 Hints: Take a look at the growth rate of these seven functions (growth rate of T(N) is defined as (T(N2) - T(N1))/T(N1) or (T(N2) - T(N1))/(N2-N1):

O(1) O(logN) O(N) O(Nlog N) O( N2) N Alg. A T(N)=999 Alg. B T(N)=log2N Alg. C T(N)=N Alg. D T(N)=N+999 Alg. E T(N)=5*N Alg. F T(N)=Nlog2N Alg. G T(N)=N2 10000 999 13.287712 10000 10999 50000 132877.1238 1E+08 20000 999 14.287712 20000 20999 100000 285754.2476 4E+08 40000 999 15.287712 40000 40999 200000 611508.4952 1.6E+09 80000 999 16.287712 80000 80999 400000 1303016.99 6.4E+09

Multiple Correct Answers:

a) With the input size N increasing, all these runtime functions grows.

b) With the input size N increasing, some of these runtime functions grow at the same rate.

c) With the input size N increasing, some of these runtime functions grow at the different rates.

d) With the input size N increasing, runtime functions T(N) = N, T(N) = N + 999, and T(N) = 5 * N grow at the same scale.

e) With the input size N increasing, the growth rate of runtime function T(N) = 999 is constant.. With the input size N increasing, the growth rate of T(N) = 999 is constant.

f) Based on the scalability of growth rates of all these functions, we could use big O notation to categorize or classify these functions: T(N) = 999 = O(1) (The growth function is constant)

T(N) = log2N = O(log2N) (The growth function is logarithmic)

T(N) = N = O(N) (The growth function is linear)

T(N) = N+999 = O(N)

T(N) = 5*N= O(N)

T(N) = 5*N + 999 = O(N)

All these N+999, N, 5*N, 5*N + 999 belong to the same group of growth functions which asymptotic order is linear, according to input size N.

T(N) = N log2N = O(N log2N) (The growth function is log-linear)

T(N) = N2 = O(N2) (The growth function is quadratic)

The asymptotic order of the growth functions is

The group functions represented by O(N2) have higher growth order than O(N log2N) , O(N log2N) is larger than O(N), O(N) is larger than O(log2N), and O(log2N) is larger than O(1).

Task 2:

What is the order of the following growth function?

77 n3 + 93 n10 + 37 n2 + 90 + 5nlogn

Answer choices:

a) O(n10)

b) O(90)

c) O(n3)

d) O(n2)

e) O(n)

f) O(1)

Task 3:

Which of the following choices demonstrates increasing levels of complexity in Big O notation?

Answer choices:

a) O(1) --> O(logN) --> O(N) --> O(NlogN) --> O(N2)

b) O(1) --> O(N) --> O(N2) --> O(logN) --> O(NlogN)

c) O(logN) --> O(NlogN) --> O(1) --> O(N) --> O(N2)

c) O(logN) --> O(NlogN) --> O(1) --> O(N) --> O(N2)

Task 4:

Take a look at the following pseudocode. Discuss with your team members about the Follow the guideline and discuss with your team members about time complexity for the following pseudocodes. Note that in pseudocode, we ignore the data type declaration. Find the matching runtime complexity for each pseudocode (A, B, C, D): A) findMin(x, y) { if (x < y) { return x } else { return y } } B) LinearSearch(numbers, N, key) { for (i = 0; i < N; ++i) { if (numbers[i] == key) { return i } } return -1 // not found }

C) SelectionSort(number, N) { for (i = 0; i < N; ++i) { indexSmallest = i for (j = i + 1; j < N; ++j) { if (numbers[j] < numbers[indexSmallest]) { indexSmallest = j } } temp = numbers[i] numbers[i] = numbers[indexSmallest] numbers[indexSmallest] = temp }

D) BinarySearch(sortedNumbers, N, key) { mid = 0; low = 0; high = 0; high = N - 1; while (high >= low) { mid = (high + low) / 2 if (sortedNumbers [mid] < key) { low = mid + 1 } else if (sortedNumbers [mid] > key) { high = mid - 1 } else { return mid } } return -1 // not found }

Task 5:

A List represents a data structure which allows to dynamically add, access and remove objects of the same type. Adding objects to the list is usually done via the add() method. The get(int i) method allows to retrieve the element at position i.

Read the sample code:

import java.util.Arrays;

public class MyArrayList {

private int size = 0; private static final int DEFAULT_CAPACITY = 10; private E elements[];

public MyArrayList() {

elements = (E [])(new Object[DEFAULT_CAPACITY]);

}

public void add(E e) { if (size == elements.length) expandCapacity();

elements[size++] = e; }

public int size(){ return this.size; }

private void expandCapacity() { int newSize = elements.length * 2; elements = Arrays.copyOf(elements, newSize); }

@SuppressWarnings("unchecked") public E get(int i) { if (i>= size || i <0) throw new IndexOutOfBoundsException("Index: " + i + ", Size " + i );

return (E) elements[i]; }

}

What is the time complexity of each method?

Which function or branch is not verified in the following unit test function?

public void testMyList() { MyArrayList list = new MyArrayList(); list.add(1); list.add(2); list.add(3); list.add(3); list.add(4); assertEquals(new Integer(4), list.get(4)); assertEquals(new Integer(2), list.get(1)); assertEquals(new Integer(3), list.get(2)); assertEquals(5, list.size());

list.get(6); }

Multiple answer choices

a) The negative input for the get() method

b) expandCapacity(). The function would be invoked when the number of elements reaches to the capacity.

c) Constructor method

d) size() method