Feedback on Quiz # 3 (Summative)
The Quiz # 3 was composed of 10 questions, which were randomly selected from a Question Bank of 20 questions. Answers and feedback comments for all of the questions are given below:
Q01
What is the purpose of an Assembler?
(a)
An assembler is a program that converts assembly code into machine code.
(b)
An assembler is a program that converts high level code into machine code
(c)
An assembler is a program that converts high level code into assembly code
(d)
An assembler is a program that converts assembly code into lower-level intermediate language
Feedback:
An assembler is a program that converts assembly code into machine code. The input to assembler is not the high-level code, rather it takes assembly code as input. The output of an assembler is the machine code (not the intermediate code).
Q02
(a)
(c)
(d)
What is the main purpose of a Linker?
The job of the linker is to link together a set of object files into a single binary executable
(b)
file.
The job of the linker is to convert different assembled parts into binary parts
The job of the linker is to link object codes of programs into a single assembly code file.
The job of the linker is to take source code files and link them into a single source code file
Feedback:
The job of the linker is to link together a set of object files into a single binary executable file.
Q03
(a)
(c)
(d)
Which of the following statements is correct for cross-compilation?
Compiled code runs on one computer system (host), and the compiling process runs on another computer system (target).
(b)
An example of Cross-compilation is when a compiler runs on a Windows 10 PC but
generates code that runs on iOS smartphone.
A cross compiler can only compile for one platform from another platform.
Cross-compilation generates code for the same platform on which it runs.
Feedback:
A cross-compiler runs on a host machine, such as a Windows 10 PC, and generates code for a different target machine, such as a mobile device like iOS smartphone. A cross-compiler usually supports multiple target platforms.
Q04
Which of the following statements is correct for Compilers?
(a)
A compiler can generate code for the same platform on which it runs.
(b)
An example of native compilation is when a compiler runs on a Windows 10 PC but generates code that runs on iOS smartphone.
(c)
A compiler can only compile for one platform from another platform.
(d)
Compiled code runs on one computer system (host), and the compiling process runs on another computer system (target).
Feedback:
A compiler can generate code for the same platform on which it runs. This process is also known as native compilation.
Q05
Which of the following statements is correct for Interpreters?
(a)
Program is translated line by line as the program is running
(b)
Program is translated line by line before the program runs
(c)
Program is translated line by line rather than the whole program in one step
(d)
Program is translated in program in one step rather than line by line
Feedback:
Program is translated line by line as the program is running. This translation process happens during program execution, and it is not a single step process.
Q06
Which of the following statements is false for Interpreters?
(a)
Interpreted program runs faster than compiled program
(b)
For interpreted programs, the source code is required every time the program gets executed
(c)
An Interpreter doesn’t need to convert the source code of a program to an object code or machine code.
(d)
Interpreted program runs slower than compiled program
Feedback:
“Interpreted program runs faster than compiled program” – this statement is incorrect. In fact, the interpreted programs run slower than the compiled programs, as the translation also happens during the execution of interpreted programs.
Q07
For the algorithm:
for i=1..n{
for j=1..n {
sum = sum + i*j
}
}
for i= 1..n {
for j=1..n {
diff = diff + i-j
} }
Using Big-O notation, what is the complexity of this algorithm?
(a)
O(n
2)
(b)
O(2n2)
(c)
O(2n)
(d)
O(2(2n))
(e)
O(n)
Feedback:
If we look at the first loop (which is 1..n), there is a nested loop that is also 1..n. So this loop is O(n2). [So, if n were to double, then it would take 4 times as long to execute.]
The second loop is the same. So it is also O(n2)
Because the two loops are independent, we take the maximum of the complexity of them: O(n2). [O(n2) + O(n2) –> O(n2)]
Remember, we are only concerned with how it changes with the size of the data, so we ignore that there are two consecutive loops.
Q08
Consider the following algorithm:
for i=1..n{
for j=1..n {
sum = sum + i*j
}
}
for i=1..n {
diff = diff +i-j
}
Using Big-O notation, what is the complexity of this algorithm?
(a)
O(n
2)
(b)
O(n)
(c)
O(n2+n)
(d)
O(n2) + O(n)
(e)
O(2n)
Feedback:
The first loop (i=1..n) has a nested loop (also 1..n) and so its complexity is O(n2). For instance, if n were to increase by 2 then the time required would grow n2 = 4
The second loop is simpler and has complexity O(n)
When we combine the analysis of the loops:
O(n2) + O(n) –> O(n2)
This is because the O(n2) loop will dominate the O(n) loop as n gets larger
Q09
You are working on a desktop machine and writing code in a high-level programming language. Your company has provided you with a ‘special’ software that takes the high-level source code and generates a binary executable than runs on the latest version of iPhone. What would you call such a source to binary translation process?
(a)
Cross-Compilation
(b)
Native Compilation
(c)
Interpretation
(d)
Just-in-Time Compilation
Feedback:
As we are working on a Desktop which is different from the system (iPhone in this case), on which the generated binary executable will be run, this will be known as Cross-Compilation.
Q10
You are working on a desktop machine and have written a program in a high-level language. Your company has provided you with a ‘special’ software that executes the program using interpretation. However, this software keeps track of code execution and if certain parts of the source code (such as a for loop) are executed many times, it converts this source code to native binary format so that it does not have to interpret it again when executing it. What would you call such a run time source code to binary code translation process?
(a)
Just-in-Time Compilation
(b)
Compilation
(c)
Interpretation
(d)
Cross-Compilation
Feedback:
We are working on a desktop machine and running the program using interpretation. The interpreter reads a line of source code and translates it into binary code, which is then executed on the same machine. The interpreter also keeps track of the code execution and if certain parts of the code are executed many times; it converts those parts of the source code into binary format. Once the code has been translated to native binary format, it can then be directly executed without requiring interpretation / translation again. This run-time source code to binary code translation process is known as Just-in-Time Compilation.
Q11
Consider the following Java bytecode instruction:
iload_2
What will be the effect of its execution?
(a)
JVM will push an integer local variable from slot #2 onto the stack
(b)
JVM will load an integer local variable from stack into the slot #2
(c)
JVM will push the integer value 2 onto the stack
(d)
JVM will load the integer value 2 and save it in memory
(e)
JVM will pop the integer constant 2 from stack and place it in memory
Feedback:
The iload_2 instruction in Java bytecode will push an integer local variable from slot #2 onto the stack. The ‘i’ specifies that it will operate on an integer, the load instruction in general is for pushing values on the stack and the 2 specifies the slot number.
Q12
Consider the following Java bytecode instruction:
dload_3
What will be the effect of its execution?
(a)
JVM will push a double local variable from slots 3 and 4 onto the stack
(b)
JVM will load a double local variable from stack into the slots 3 and 4
(c)
JVM will push the double value 3 onto the stack
(d)
JVM will load the double value 3 and save it in memory
(e)
JVM will pop the double constant 3 from stack and place it in memory
Feedback:
The dload_3 instruction in Java bytecode will push a double local variable from slots 3 and 4 onto the stack. The ‘d’ specifies that it will operate on a double, the load instruction in general is for pushing values on the stack and the 3 specifies the slot number.
Q13
Consider the following RPN expression:
8254*9-*+
Evaluate this expression using a stack and select the correct answer from the given choices.
(a)
30
(b)
18
(c)
-24
(d)
38
(e)
-32
Feedback:
Let’s evaluate the following expression with the help of a stack. 8254*9-*+
We can evaluate the RPN using the following steps:
Step#
INPUT
STACK
1
8
8
2
2
82
3
5
825
4
4
8254
5
*
8220
6
9
82209
7
–
8211
8
*
822
9
+
30
So, the correct answer is 30, as shown in step#9 above.
Q14
Consider the following RPN expression:
82549*-*+
Evaluate this expression using a stack and select the correct answer from the given choices.
(a)
-54
(b)
62
(c)
28
(d)
32
(e)
-24
Feedback:
Let’s evaluate the following expression with the help of a stack. 82549*-*+
We can evaluate the RPN using the following steps:
Step#
INPUT
STACK
1
8
8
2
2
82
3
5
825
4
4
8254
5
9
82549
6
*
82536
7
–
82-31
8
*
8 -62
9
+
-54
So, the correct answer is -54, as shown in step#9 above.
Q15
You have a program which implements an algorithm, which you have been told is O(n2). When you execute it with 1 data item, it takes 5 seconds to run. Therefore, you can assume that the 5 seconds is a constant setup time. When you repeat its execution with 1000 data items it takes 10 seconds to run. Estimate how long it will take with 2000 data items.
(a)
25 seconds
(b)
40 seconds
(c)
20 seconds
(d)
15 seconds
(e)
100 seconds
Feedback:
If we assume that the 5 seconds is constant (e.g., for program set up), then the actual execution time of the algorithm (on 1000 items) is 5 seconds (constant 5secs + 5 secs to execute the algorithm) Because it is O(n2) then we would expect that if we double the amount of data then the execution time (of the core algorithm) will increase by 4 (22).
So, the actual execution time would be 5+(5*4) = 25 seconds
Q16
You have a program where the core algorithm has O(n2) complexity. When you execute the program on some test data set, the following execution times are obtained:
Therefore, we can assume that the 10 seconds is a constant setup time. Estimate how long it will take to run if there are 40,000 data items.
Number of data items
Execution time
1
10 seconds
10,000
20 seconds
(a)
170 seconds
(b)
50 seconds
(c)
150 seconds
(d)
80 seconds
(e)
40 seconds
Feedback:
If we assume there is a fixed start-up time of 10 seconds, then it takes 10 seconds to execute the algorithm with 10,000 data items. So, we would expect the time for 20,000 items (twice as many) to be: 10+40 seconds.
[That is 10 seconds fixed time + 10secs*22]
For 40,000 items we would then expect it to be 10+160 seconds = 170 seconds [That is 10 seconds fixed time + 10 seconds * 42]
Q17
Consider the following infix expression:
8+(5*3^2)
Suppose that we are using the Shunting-Yard algorithm to convert the expression from infix to RPN (postfix notation). What will be the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
Note: The parenthesis () are also considered as symbols.
(a)
4
symbols
(b)
1 symbol
(c)
2 symbols
(d)
3 symbols
(e)
5 symbols
Feedback:
Theexpression:8+(5*3^2)
Will be converted to RPN using the following steps:
Step#
OUTPUT
STACK
INPUT
1
Empty
Empty
8+(5*3^2)
2
8
Empty
+(5*3^2)
3
8
+
(5*3^2)
4
8
+(
5*3^2)
5
85
+(
*3^2)
6
85
+(*
3^2)
7
853
+(*
^2)
8
853
+(*^
2)
9
8532
+(*^
)
10
8532^*
+
Empty
11
8532^*+
Empty
Empty
We can see that the maximum number of symbols on the stack is 4 (during steps 8 & 9), as highlighted above.
Q18
Consider the following infix expression:
2^(18–4*3)
Suppose that we are using the Shunting-Yard algorithm to convert the expression from infix to RPN (postfix notation). What will be the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
Note: The parenthesis () are also considered as symbols.
(a)
4 symbols
(b)
1 symbol
(c)
2 symbols
(d)
3 symbols
(e)
5 symbols
Feedback:
Theexpression:2^(18–4*3)
Will be converted to RPN using the following steps:
Step#
OUTPUT
STACK
INPUT
1
Empty
Empty
2^(18–4*3)
2
2
Empty
^(18–4*3)
3
2
^
(18–4*3)
4
2
^(
18–4*3)
5
218
^(
–4*3)
6
218
^(–
4*3)
7
2184
^(–
*3)
8
2184
^(–*
3)
9
21843
^(–*
)
10
21843*–
^
Empty
11
21843*–^
Empty
Empty
We can see that the maximum number of symbols on the stack is 4 (during steps 8 & 9), as highlighted above.
Q19
Consider the following Java function:
public static void exoticFun(long n){
float x = 0.0f / 0;
double d = 744.93;
float f = 328.7f;
}
Select the option which indicates the correct slots allocation for this function in the Java bytecode.
(a)
n = slots 0,1; x = slot 2; d = slots 3,4; f = slot 5
(b)
this = slot 0; n = slots 1,2; x = slot 3; d = slots 4,5; f = slot 6
(c)
this = slot 0; n = slot 1; x = slot 2; d = slots 3,4; f = slot 5
(d)
n = slots 0,1; x = slots 2,3; d = slots 4,5; f = slots 6,7
(e)
n = slot 0; x = slot 1; d = slots 2,3; f = slot 4
Feedback:
The slots will be allocated to local variables according to the following scheme num = slots 0,1 [num is long, therefore needs two slots]
x = slot 2 [x is float, therefore needs one slot]
d = slots 3,4 [d is double, therefore needs two slots]
f = slots 5 [f is float, therefore needs one slot]
Note: The function is static, therefore this reference will not exist.
Q20
Consider the following Java function:
public void fancyFun(float f){
double d = 744.93;
float x = 0.0f / 0;
long n = 328000;
}
Select the option which indicates the correct slots allocation for this function in the Java bytecode.
(a)
this = slot 0; f = slot 1; d = slots 2,3; x = slot 4; n = slots 5,6
(b)
f = slot 0; d = slots 1,2; x = slot 3; n = slots 4,5
(c)
this = slot 0; f = slot 1,2; d = slots 3,4; x = slot 5,6; n = slots 7,8
(d)
f = slot 0,1; d = slots 2,3; x = slot 4,5; n = slots 6,7
(e)
f = slot 0; d = slots 1,2; x = slot 3; n = slots 4
Feedback:
The slots will be allocated to local variables according to the following scheme this = slot 0 [this reference will exist as the function is non-static]
f = slot 1 [f is float, therefore needs one slot]
d = slots 2,3 [d is double, therefore needs two slots]
x = slot 4 [x is float, therefore needs one slot]
n = slots 5,6 [n is long, therefore needs two slots]