IS 554 “Computational Thinking” - HWS 2020
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.
2022-02-09