Program Analysis - Computer Science

Card 0 of 20

Question

Which of the following code excerpts would output "10"?

Answer

Each bit of code has something similar to this:

num = (boolean statement) ? X : Y;

The bit at the end with the ? and : is called a ternary operator. A ternary operator is a way of condensing an if-else statement. A ternary operator works like this:

<boolean statement> ? <do this if true> : <do this if false>

The correct answer is

int num = 5;

num = (num > 0) ? 10: 11;

System.out.println(num);

Therefore, the ternary operator portion of code, when converted to an if-else, looks like this:

if (num > 0) {

num = 10;

else {

num = 11;

}

Because num is 5, which is greater than 0, it would go into the if, so num would then get 10. Then, num gets printed, which means 10 gets printed (the correct answer).

Compare your answer with the correct one above

Question

True or False.

The assertion in this code snippet is to prevent users from inputting bad data.

public class UserInput {

int userInput;

public static void main(String[] args) {

assertTrue(isInteger(args[0]));

userInput = args[0];

userInput = 25 - userInput;

}

}

Answer

The assertion is used to validate user input. The user is able to input anything into the value at args\[0\]. Since this is the case, we must validate and make sure that the user is inputting what we want. To make this code snippet better, add error checking to do something if the user did not input an integer.

Compare your answer with the correct one above

Question

Consider the following code:

O_n_

What is the expected runtime of the code (in Big-O notation?)

Answer

The run-time can best be analyzed by breaking the code down by line. The line iterating the value of sum is performed in constant time, or O(1). This constant time operation is performed n times in the for loop, leading to a run time that is proportional to n, or O(n).

Compare your answer with the correct one above

Question

Consider the following code:

O_n2_

What is the expected run time of the code (in Big-O notation?)

Answer

The run time can best be analyzed by breaking the code down by line. The line iterating the value of sum is performed in constant time, or O(1). This constant time operation is performed n times in the inner "for" loop, and n times in the outer "for" loop. Thus, the run time is .

Compare your answer with the correct one above

Question

Consider the following code:

O_n3_

What is the run time of the code (in Big-O notation)?

Answer

The run time can best be analyzed by breaking the code down by line. The line iterating the value of sum is performed in constant time, or O(1). This constant time operation is performed times in the inner "for" loop, and times in the outer "for" loop. Thus, the overall run time is .

Compare your answer with the correct one above

Question

Consider the following code:

O_log_n__

What is the run-time of the code (in Big-O notation?)

Answer

The run-time can best be analyzed by breaking the code down by line. The line iterating the value of sum is performed in constant time, or O(1). The "for" loop that controls this constant-time operation is initialized at i = 1, and i is iterated by multiplying by 2 until it is equal to or greater than n. Thus, this loop will run times, and the run-time will be O(log(n))

Compare your answer with the correct one above

Question

Consider the following code:

O_2n_

What is the run time of the code (in Big-O notation?)

Answer

The run time of this code is best analyzed by plugging in numbers. Take the value of bar(2) for example. bar(2) leads to two calls to bar(1), which lead to four calls to bar(0). A call to bar(4) leads to two calls to bar(3), four calls to bar(2), eight calls to bar(1), and sixteen calls to bar(0). Thus, it can be shown that the number of calls is proportional to 2^n, and that that run time is O(2^n).

Compare your answer with the correct one above

Question

What is the BigO of the following function?

public void bigO(int[][] m)

{

if (m.length > 2)

{

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

{

for (int j = 0; j < m[i].length; j++)

{

System.out.println(m[i][j]);

}

}

}

else

{

for (int j = 0; j < m[0].length; j++)

{

System.out.println(m[0][j]);

}

}

}

Answer

The function is O(n2) because it has a nested loop of size 2, with no extras thrown in that could possibly add on a log(n). A good rule of thumb is this: if there are nested loops, then the BigO is usually O(nm), with m being the levels of loops in the longest part.

Compare your answer with the correct one above

Question

for( int i = 0; i < n; ++i){

for( int j = 1; j < n; j *= 2){

someFunction();

}

}

For the code above, what is the run time in Big O notation?

Answer

At first glance we might be tempted to pick O( ) because there are 2 for loops. But, upon closer inspection we can see that the first loop will yield a O( n ) running time but the second loop does not. The second loop has only an O( log(n) ) running time because "j" doubles each iteration and does not increase linearly. That will yield O( log(n) ) since O( log(n) ) is a much faster running time. So the final result is O( n log(n) ).

Compare your answer with the correct one above

Question

Which is more efficient (i.e. Lower Big O)?

arr = \[1, 2, 3, 4, 5, 6, 7, 8\]

arr2 = \[\[1,2\],\[3,4\],\[5,6\], \[7,8\], \[9,10\], \[10, 11\]\]

for (int i = 0; i < arr.length; i++) {

for (int j = i; j < arr2.length; j++) {

arr\[i\]\[j\] = 0;

}

}

arr = \[1, 2, 3, 4, 5, 6, 7, 8\]

arr2 = \[\[1,2\],\[3,4\],\[5,6\], \[7,8\], \[9,10\], \[10, 11\]\]

for (int i = 0; i < arr.length; i++) {

for (int j = 0; j < arr2.length; j++) {

arr\[j\] = 0;

}

}

Answer

Code sample #1 relies on i in the second loop where int j = i. Since the code relies on i in the second loop, the order goes from O(N) to O(N2)

Code sample #2 has two separate loops that do not rely on each other. The first for loop loops through the array arr and the second for loop loops through the array arr2. Since the two loops are exclusive, the order is O(N)

Compare your answer with the correct one above

Question

Which has faster compile time, O(N), O(N2), O(N3), or O(NlogN)?

Answer

O(NlogN) is O(N) * O(logN) which is greater than O(N) alone.

O(N2) is O(N*N) which is greater than O(N).

O(N3) is O(N*N*N) which is greater than O(N).

O(N) is the smallest and therefore is the quickest to compile. Therefore, O(N) is the correct answer.

Compare your answer with the correct one above

Question

Which is more efficient?

a)

arr = [0, 1, 2, 3]

for (int i = 0; i < arr.length; i++) {

int j = 0;

if (j == arr[i]) {

j++;

}

}

b)

ArrayList<Integer> arL = new ArrayList<Integer>();

arL.add(0);

arL.add(1);

arL.add(2);

arL.add(3);

for (int i = 0; i < arL.size(); i++) {

int k = 0;

if (k == arL.get(i)) {

k++;

}

}

Answer

The two code snippets have the same efficiency. Both operate in O(N) time. ArrayLists use arrays as their underlying data structure so access to the data is also the same.

Compare your answer with the correct one above

Question

True or False.

The code snippet A has a more efficient running time than code snippet B.

(A)

for (int i = 0; i < 25; i++) {

for (int j = i; j < 25; j++) {

}

}

(B)

for (int i = 0; i < 25; i++ {

for (int j = 0; j < 25; j++) {

}

}

Answer

Code snippet A has a running time of O(N2). Code snippet B has a running time of O(N). While the two code snippets may look the same, the second for loop in code snippet A sets j=i. Since j is relying on i, it's multiplying the first for loop's running time by the second for loop's running time. This gives us O(N*N) or just O(N2).

Compare your answer with the correct one above

Question

What is the error in the following code?

int val1 = -14,val2 = 4;

final int val3 = 9;

double val4 = 4.1;

double val5 = 3.1;

val1 = val2 * val3;

val3 = val1 * 12;

val5 = val1 - val3;

val4 = val2 + val5;

Answer

The only error among the options given is the fact that this code assigns a new value to the variable val3, which is defined as a constant. (This is indicated by the keyword final before the rest of its declaration.) You cannot alter constants once they have been declared. Thus, the following line will cause a compile-time error:

val3 = val1 * 12;

Compare your answer with the correct one above

Question

Consider the following code:

public static class Rectangle {

private double width, height;

public Rectangle(double w,double h) {

width = w;

height = h;

}

``

public double getArea() {

return width * height;

}

``

public double getPerimeter() {

return 2 * width + 2 * height;

}

}

``

public static class Square extends Rectangle {

public Square(double s) {

super(s,s);

}

}

public static void main(String[] args) {

Rectangle[] rects = new Rectangle[6];

for(int i = 0; i < 6; i++) {

if(i % 2 == 0) {

rects[i] = new Rectangle(i+10,i + 20);

} else {

rects[i] = new Square(i+20);

}

}

Square s = rects[1];

}

What is the error in the code above?

Answer

This code fills up the 6 member array with alternating Rectangle and Square objects. You can do this because the Square class is a subclass of Rectangle. That is, since Squares are Rectangles, you can store Square objects in Rectangle variables. However, even though rects[1] is a square, you CANNOT immediately reassign that to a Square object. The code has now come to consider all of the objects in the array as being Rectangle objects. You would need to explicitly type cast this to get the line to work:

Square s = (Square)(rects[1]);

Compare your answer with the correct one above

Question

public static void main(String[] args) {

int[] x = {3,4,4,5,17,4,3,1};

int[] y = remove(x,4);

for(int i = 0; i < y.length; i++) {

System.out.print(y[i] + " ");

}

}

``

public static boolean remove(int[] arr, int val) {

boolean found = false;

int i;

for(i = 0; i < arr.length && !found; i++) {

if(arr[i] == val) {

found = true;

}

}

if(found) {

for(int j = i; j < arr.length;j++) {

arr[j - 1] = arr[j];

}

arr[arr.length - 1] = 0;

}

return found;

}

What is the error in the code above?

Answer

The problematic line is this one:

int[] y = remove(x,4);

Notice that the variable y is defined as an array. Now, it is tempting to think (without looking too closely) that the remove method returns the array after the removal has been accomplished; however, this is not how the logic works in the remove method. Instead, it returns a boolean indicating whether or not this removal was successful or not (i.e. it tells you whether or not it actually found the value). Therefore, you cannot make an assignment like the one above, for the two types are not the same. That is, y is an integer array, while remove returns a boolean value!

Compare your answer with the correct one above

Question

public interface ServerInstance {

byte[] readBytes();

boolean writeBytes(byte[]b);

boolean wake();

boolean status();

void sleep();

}

``

public class MyHost implements ServerInstance {

boolean running = false;

public boolean wake() {

// Other logic code here...

return running;

}

public boolean status() {

// Other logic code here...

return running;

}

public byte[] readBytes() {

byte[] buffer = null;

// Other logic code here...

return buffer;

}

public void sleep() {

// Other logic code here...

running = false;

}

public byte[] writeBytes(byte[] b) {

// Other logic code here...

return b;

}

// Other methods...

}

What is the error in the code above?

Answer

When you implement an interface, all of the methods defined in that interface must be written in the class that is proposing to be such an implementation. (Or, if they are not implemented there, you need to involve abstract classes—but that is not our concern here.) The methods must match the prototypes proposed in the interface. In the example code, ServerInstance has a method writeBytes that returns a boolean value. However, the MyHost class has implemented this method as returning a byte[] value. Since you cannot have different types of return values for methods with the same parameter set, Java interprets this as being the proposed implementation for writeBytes(byte[] b), and this method must return a boolean if MyHost is to implement ServerInstance.

Compare your answer with the correct one above

Question

public static void foo() {

int x = 10; y = 21, z = 30;

int[] arr = null;

for(int i = 0; i < y; i+= 4) {

arr = new int[i / 5];

}

for(int i = 0; i < x; i++) {

arr[i] = z / i;

}

for(int i = 0; i < z; i++) {

arr[i] = z * i;

}

}

Which of the following lines of code will cause a compile-time error?

Answer

An error in compilation occurs before any code even attempts to execute. Thus, it is primarily a syntactical error in the code. In the selection above, the line

int x = 10; y = 21, z = 30;

has a semicolon right after 10_._ This causes an error in the code directly following on this, for the code

y = 21, z = 30;

is not valid Java code.

There are other errors in this code. arr[i] = z / i; will cause a divide by 0 error when iis 0. Also, arr[i] = z * i; will overrun the bounds of the array arr. However, these are not compile-time errors—i.e. errors that occur before the code is even able to run!

Compare your answer with the correct one above

Question

class Base{};

class Derived : public Base{

public:

void method(){ cout<< "method1
"; }

};

class Derived2 : public Base{

public:

void method() { cout<< "method2
"; }

};

int main(){

Base* bp = new Derived();

Derived2* d2p = bp;

d2p -> method();

}

What is the result of compiling and running the program in C++?

Answer

In this problem, Derived1 and Derived2 are children of the Base class. If we take a look at this line:

Base* bp = new Derived();

We are assigning a new Derived class to a base pointer. This will compile. Think of the Base as a larger object because it is the parent, so copying a smaller object into a larger one is acceptable.

Now let's look at this one:

Derived2* d2p = bp;

This line will cause the program to not compile. Since the Base class is considered the "bigger" object, copying a bigger object into a "smaller" one will result in a failure to copy everything over, this is known as a Slicing Problem.

We don't even have to look at the next line because we know that the program wil crash.

Compare your answer with the correct one above

Question

Given:

const int x = 10;

Which of the following will compile?

Answer

First we take a look at the given statement:

const int x = 10;

the const in front of "int" means that x will always hold the value of 10 and it will not change.

Let's observe all the choices.

int *p =&x

This line says to assign the address of x (in memory) to the pointer p. This however, will not compile because int * p is not marked as const. x is marked as a const so this forces int * p to be a const as well.

int * const q = &x

There is a const in this case but it is in the wrong place

const int * r = &x

The const is in the correct place and this is the correct answer

Compare your answer with the correct one above

Tap the card to reveal the answer