Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


IS 554 “Computational Thinking” - HWS 2020


Assignment 1: Foundations of Computer Programs . . . 10 points

(a) In which number system(s) are the following equations valid? Justify your an-

swers.

i.  (1 point) 33025 + 64410 = 107435

ii.  (1 point)  1010101 + 101010 = 1111111

(b)  (1 point) Comment on the following statement:

”A variable of the type int in Java is stored in 32 bits. A variable of the type long is stored in 64 bits.   Thus, a long can store twice as many numbers as an int.”

(c)  (2 points) Unicode is a standard for the consistent encoding of text. Similar to ASCII it assigns one number to each character of multiple writing systems of the world.  When in 1991 the first Unicode version was established, there were

7161 different characters in the encoding table. How many bits are necessary to store one character? Justify your answer.

(d)  (5 points)  Consider the following assembler instructions:


LOAD S, R

Load the value of the operand S into register R

STORE R, S

Store the value of register R at memory address S

ADD S, R1, R2

Add the value of the operand S to the value of R1, and store the result in register R2

SUB S, R1, R2

Subtract the value of the operand S from the value of R1, and store the result in the register R2

DIV S, R1, R2

Divide the value of the operand S by the value of R1, and store the result in register R2

MUL S, R1, R2

Multiply the value of the operand S with R1, and store the result in R2

HALT

Stop execution


Using the instruction set above, write the assembler code for the following high- level language construct:

y  =  17;

x  =  x  *  y  +  2;

y  =  x;

Hints:

● If the number bit is set to 1, the operand is taken as a value (e.g., LOAD #12 loads 12 into the accumulator).  If the number bit is 0, the address is taken (e.g., LOAD 12 loads the value of address 12 into the accumulator).

● The variable x is stored at memory address 4.

● The variable y is stored at memory address 5.


Assignment 2: Programming in Java . . . . . . . . . . . . . . . . . 10 points

(a)  (2 points) Write a Java statement that calls the method below. Use parameter

values for which the method returns true.

boolean algA(int

if(c == d){ return

}

if(a > b &&

return } else {

return }

}

a, int b, boolean c, boolean d){

false;

c){

true;

false;

(b)  (1 point)  Consider the following scenario: After the exam, we want to store the

names of all students who took the exam and their grade in order to calculate statistical measures such as mean and standard deviation.  Is it a good idea to use a two-dimensional array? Justify your answer.

(c)  (3 points) Translate the following sequence diagram into Java code.

true

“write exam”


(d)  (2 points) A method is called recursive when it calls itself. Does this mean that all recursive methods are infinite? Justify your answer.


(e) The concept of inheritance is used in Java to express ’is-a’ relationships.  For

the following combinations, briefly discuss whether the specified inheritance re- lationship makes sense.

i.  (1 point) Car inherits from Vehicle

ii.  (1 point) Helicopter inherits from Airplane


Assignment 3: Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 points

(a)  (2 points)  Consider an array of integers that stores the last six digits of your

student ID number (Example:  if your student id is ”1756878” 二 consider the array [7,5,6,8,7,8]).

Perform a bubble sort on the array. Write down the array after each swap.

(b) Have a look at the following algorithm.

static boolean algB(int[] input) {

for (int i = 0; i < input.length - 1; i++) {

if (input[i] > input[i + 1]) {

return false;

}

}

return true;

}

i.  (2 points) What does the algorithm compute?

ii.  (1 point) What is the complexity of the algorithm in Big-O notation? Justify your answer.

(c)  (3 points) What does the following algorithm compute?

static String algC(int input) {

if(input <= 0) {

return "";

}

return algC(input/2) + input%2;

}

Hint: The + operator concatenates two Strings (e.g.  ”3”+ ”4”二 ”34”)


(d) Have a look at the following algorithm.


public static int[] algD(int[] numbers){

int index = 0;

while(index < numbers.length){

if(numbers[index] < 0){ numbers[index] = -numbers[index];

} index = index + 1;

}  return numbers;

}


i.  (2 points)

ii.  (1 point)


What does the algorithm compute?



your answer.

iii.  (2 points) Rewrite the method so that is uses a for-loop instead of a while-

loop.


(e)  Consider an algorithm that checks whether an array of integers contains dupli-

cates.

i.  (5 points) Write a Java method that implements the algorithm.

ii.  (1 point) What is the complexity of the algorithm in Big-O notation? Justify your answer.


(f)  Consider an algorithm that computes the average in a sorted array of integers. i.  (5 points) Write a Java method that implements the algorithm.

ii.  (1 point) What is the complexity of the algorithm in Big-O notation? Justify your answer.