Free Online OCR Home Comments Free Online OCR Convert JPEG, PNG, GIF, BMP, TIFF, PDF, DjVu to Text Select pages from 1 to 4 Recognition language English English Afrikaans Albanian Arabic Azerbaijani Basque Belarusian Bengali Bulgarian Catalan Cherokee Chinese, Simplified Chinese, Traditional Croatian Czech Danish Dutch Esperanto Estonian Finnish Frankish French Galician German Greek Hebrew Hebrew #2 Hebrew #3 Hindi Hungarian Icelandic Indonesian Italian Japanese Kannada Korean Latin Latvian Lithuanian Macedonian Malay Malayalam Maltese Norwegian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Tagalog Tamil Telugu Thai Turkish Ukrainian Vietnamese Rotate image 0° CCW 90° 180° CW 90° Page layout analysis “ split multi-column text into columns Page of 4 Download Copy to Clipboard Google Translate Bing Translator Paste Online Edit Online Assignment 1 to œHow to submit your Assignment online” Due: Friday Page Download Google Translate Bing Translator Edit Online CSG2245 Computer Science Methods Semester 2, 2014 CSG2245 Computer Science Method Assignment 1 Topic: Numeric types and algorithm complexity Related objectives from the unit outline: ? To apply complexity theory to algorithms; ? To discuss the relative merits of search techniques using various abstract data types; Assignment type: Individual work Mark/value: Due date: 100 marks, which will be converted to 20% of unit mark Friday in Week 7 @5:00 PM (12/09/2014) Submission Requirements: o Submit your assignment work via Blackboard electronic assessment facility by the submission due date. For detailed assignment submission procedure, please refer to œHow to submit your Assignment online item in the Assignment section of your Blackboard. o Java code files must be in either .java or .txt format, and all other files must be in Word or PDF format. As you may need to submit multiple files, please zip all your files before submission. Please rename the zip file to be in a format of

_

_A1_CSG2245.zip. For example, if your student ID was 12345678, your full name was Abcd XYZ, then the zip file would be named 12345678_Abcd XYZ _A1_CSG2245.zip. Submit the .zip file via Blackboard. o No hard copy is required unless you are allowed to do so. o Remember to keep a copy of your assignment. o Your attention is drawn to the university rules governing cheating and referencing. In general, cheating is the inclusion of the unacknowledged work of another person. Plagiarism (presenting other people’s work and ideas as your own) will risk severe penalty (e.g., the minimum penalty is being grant a ZERO mark to the assessment component). Due: Friday 12/09/2014 @5:00 PM Page 1 CSG2245 Computer Science Methods Semester 2, 2014 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)). Due: Friday 12/09/2014 @5:00 PM Page 3 CSG2245 Computer Science Methods Semester 2, 2014 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} (Hint: you may simply extend the above code within the while loop to count the number of iterations it executes for a given array size n.) End of the Assignment Description Due: Friday 12/09/2014 @5:00 PM Page 4 © NewOCR.com 2009 “ 2014