Topic: Numeric types and algorithm complexity

Task 1: Numeric data representation and Conversion
All calculation/calculation must be shown in order to gain maximum marks. While you can discuss aspects of the assignment with your classmates, all submitted material

for marking should be unique to each student. Question 1: [30 marks] An ECU student identification number, sID, is an 8-digit number, d7 d6 d5 d4 d3 d2 d1 d0 i where

di is the multiplier for 10 : i = 0, 1, 2, 3, 4, 5, 6, 7. The integer value of the sID can be calculated using the formula sID =

?d
i ?0

7

i

? 10 i

For instance, if sID = 10163587, then the integer value of sID can be calculated as sID = d0*100 +d1*101 + d2 *102 + d3 *103 +d4 *104 + d5 *105 + d6 *106 + d7 *107 =

7*100+8*101 + 5*102 + 3*103 + 6*104 + 1*105 + 0*106 + 1*107 = 1*107 + 0*106 + 1*105 + 6*104 + 3*103 + 5*102 + 8*101 + 7*100 Assume that your student identification

number is d7 d6 d5 d4 d3 d2 d1 d0. We now define an integer uID and a real number uIDf: uID = (d0 d1 d2 d3 d4 d5), and uIDf = (d7 d6 d5 d4 d3 d2 d1 d0)/500. You are

requested to manually do the following (using you own sID number):
a) b) c) d) Compute the integer value of uID. Calculate the 32-bit two’s complement sequence for (-uID). Compute the real value uIDf. Calculate the 32-bit floating-

point normalized sequence for (-uIDf).

Question 2: [20 marks] Produce a Java code to implement the requirements of Question 1. That is, given your sID, derive/calculate and output (a) uID; (b) the 32-bits

two’s complement of -uID; (c) uIDf; and (d) the 32-bit floating-point normalized sequence of -uIDf.

Due: Friday 12/09/2014 @5:00 PM

Page 2

CSG2245 Computer Science Methods

Semester 2, 2014

Task 2: Algorithm complexity: analysis and varification
Question 3: [30 marks] Three methods are defined by the following Java-like code. You are requested to manually calculate their time complexities using big-O notation.
##

Algorithm1

void algorithm_1(int n) { if (n < 1) return; System.out.println(q(1, n)*n); System.out.println(r(n)); System.out.println(q(1, n+n) + r(n+n));
}

01 02 03 04 05 06 01 02 03

int q(int i, int n) { return i+(i >= n ? 0 : q(i+i, n)); } int r(int n) { int sum = 0; for (int i=1; i <= n+n; i++) sum+=i + q(1,n); return sum; } Assume n >0.

01 02 03 04 05 06

a) What is the time complexity of the method q(1, n). Show the details of your calculation of O(q(1, n). (Hint: calculate q(1, n) for n = 0, 1, 2, …, 10 to illustrate

the time complexity calculation, thus to work out the time complexity formula.) b) What is the time complexity of the r(n) method. Show the details of you calculation

of O(r(n)). c) What is the time complexity of the algorithm_1(int n) method? Show the details of you calculation of O(algorithm_1(n)).

Question 4: [20 marks] A search algorithm is given by the following Java-like code.

Algorithm2
int binarySearch(int[] array, int key) { int lo = 0, mid, hi = array.length-1; while (lo <= hi) { mid = (lo + hi)/2; if (key < array[mid]) hi = mid – 1; else if

(array[mid] < key) lo = mid + 1; else return mid; // success } return -1; // failure }

(a) For n ??0, what is the time complexity of the binarySearch(array[n], key) algorithm in big-

O notation? Show the details of your analysis. (b) Write a Java program that counts the number of operations the binarySearch algorithm executes to search a given

array of size n. Your program should output two variables n (i.e., the array size) and iterated (i.e., the number of iterations the binarySearch has executed),

respectively. Illustrate your result using the following array:
array[] = {1, 2, 4, 8, 16, 32, 64, 92, 120, 128, 184, 216, 240, 248, 254, 258, 260, 262, 263, 264}