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 <your Student ID>_<your full name>_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