1.
The next question applies to the following
code fragment:
1. for i in 1..N loop
2. for j in 1..i loop
3. for k in i..j loop
4. Sum := Sum + 1;
5. end loop;
6. end loop;
7. end loop;
8. for p in 1..N*N loop
9. for q in 1..p loop
10. Sum := Sum - 1;
11. end loop;
12. end loop
How many times is statement 4 executed?
Correct Answer
C. O(N^{3})
Explanation
The code fragment contains three nested loops: i, j, and k. The outermost loop, i, iterates N times. The second loop, j, iterates i times for each value of i. The innermost loop, k, iterates from i to j. Therefore, the number of times statement 4 is executed is equal to the sum of the number of iterations of the innermost loop for each iteration of the second loop, for each iteration of the outermost loop. This can be represented as the sum of the cubes of the numbers from 1 to N, which is O(N^3).
2.
The next question applies to the following
code fragment:
1. for i in 1..N loop
2. for j in 1..i loop
3. for k in i..j loop
4. Sum := Sum + 1;
5. end loop;
6. end loop;
7. end loop;
8. for p in 1..N*N loop
9. for q in 1..p loop
10. Sum := Sum - 1;
11. end loop;
12. end loop
How many times is statement 10 executed?
Correct Answer
D. O(N^{4})
Explanation
The given code fragment consists of nested loops. The outermost loop iterates N times, and the second loop iterates i times, where i ranges from 1 to N. The innermost loop iterates from i to j, where j ranges from 1 to i.
Therefore, the number of times statement 10 is executed can be calculated as the sum of the product of the iterations of each loop. The outer loop iterates N times, the second loop iterates i times, and the innermost loop iterates (i-j+1) times.
Hence, the total number of times statement 10 is executed is the sum of (N * i * (i-j+1)) for all values of i and j. This simplifies to O(N^4) as the number of iterations.
3.
The next question applies to the following
code fragment:
1. for i in 1..N loop
2. for j in 1..i loop
3. for k in i..j loop
4. Sum := Sum + 1;
5. end loop;
6. end loop;
7. end loop;
8. for p in 1..N*N loop
9. for q in 1..p loop
10. Sum := Sum - 1;
11. end loop;
12. end loop
What is the running time of this fragment?
Correct Answer
A. O(N^{4})
Explanation
The running time of this code fragment is O(N4). This is because there are three nested loops in lines 1-7, with the outer loop running N times, the middle loop running i times, and the innermost loop running j-i+1 times. The loop in lines 8-12 also runs N2 times. Therefore, the total number of iterations is approximately N * (N * (N+1) * (N+2)) / 6, which simplifies to O(N4).
4.
Suppose T_{1}(n) = O(f(n)) and T_{2}(n) = O(g(n)). Which of the following are true?
Correct Answer(s)
A. T_{1}(n) + T_{2}(n) = O(max(f(n), g(n)))
B. T_{1}(n) * T_{2}(n) = O(f(n) * g(n))
Explanation
The given answer is correct.
When we add the time complexities T1(n) and T2(n), the worst-case time complexity will be the maximum of f(n) and g(n). Hence, T1(n) + T2(n) = O(max(f(n), g(n))).
Similarly, when we multiply the time complexities T1(n) and T2(n), the worst-case time complexity will be the product of f(n) and g(n). Hence, T1(n) * T2(n) = O(f(n) * g(n)).
However, T1(n) / T2(n) is not equal to O(f(1)). The division of time complexities does not follow the same rules as addition and multiplication.
Lastly, we cannot conclude that T1(n) = O(T2(n)) without knowing the specific functions f(n) and g(n). Therefore, the correct answers are T1(n) + T2(n) = O(max(f(n), g(n))) and T1(n) * T2(n) = O(f(n) * g(n)).
5.
Suppose that you have the following algorithm to sort
a list of N integer numbers:
1. Build an AVL-tree with the input list of N integer
numbers.
2. Incorporate in-order traversal for the N nodes of
the AVL-tree. This step allows to print the value of
the nodes of the AVL-tree in sorted order.
What is the total running time complexity of this
algorithm?
Correct Answer
C. O(NlogN)
Explanation
The algorithm first builds an AVL-tree, which has a time complexity of O(NlogN) since each insertion or deletion operation takes O(logN) time. Then, it performs an in-order traversal of the AVL-tree to print the values in sorted order, which also takes O(N) time. Therefore, the total running time complexity of the algorithm is O(NlogN).
6.
Which of the following can be done in O(N)?
Correct Answer
A. Find an element in an unsorted array
Explanation
Finding an element in an unsorted array can be done in O(N) time complexity, where N is the number of elements in the array. This is because in the worst case scenario, we may have to iterate through all the elements of the array to find the desired element. Therefore, the time taken to find an element in an unsorted array is directly proportional to the size of the array, making it O(N).
7.
The next question relates to the following
binary tree with root A:
The root has left child B and right child C.
B has left child D and right child E.
C has right child F.
There are no other nodes in the tree.
Which of the following traversals yields DEBFCA
Correct Answer
B. Postorder
Explanation
Postorder traversal visits the nodes in the following order: left subtree, right subtree, and then the root. In this case, the postorder traversal would be DEBFCA.
8.
The next question relates to the following
binary tree with root A:
The root has left child B and right child C.
B has left child D and right child E.
C has right child F.
There are no other nodes in the tree.
Which of the following traversals yields DBEACF?
Correct Answer
A. Inorder
Explanation
Inorder traversal visits the left subtree first, then the root, and finally the right subtree. In this case, the inorder traversal DBEACF would visit the nodes in the following order: D, B, E, A, C, F. Therefore, the correct answer is Inorder.
9.
For minimum spanning tree (MST) construction, Kruskal’s algorithm selects an edge:
Correct Answer
B. With minimum weight so that cost of MST is always minimum
Explanation
Kruskal's algorithm for constructing a minimum spanning tree (MST) selects an edge with the minimum weight so that the cost of the MST is always minimum. This is because the algorithm aims to connect all the vertices in the graph with the minimum total weight possible. By selecting edges with the minimum weight, the algorithm ensures that it is adding the least expensive connections to the tree, resulting in the overall minimum cost for the MST.
10.
Which of the following algorithms is non stable? (select all that apply)
Correct Answer(s)
A. Heap sort
B. Selection sort
C. Shell sort
F. Quick sort
Explanation
The stability of an algorithm refers to whether it maintains the relative order of elements with equal keys. In a stable sorting algorithm, elements with equal keys appear in the same order in the sorted output as they do in the input. Heap sort, selection sort, shell sort, and quick sort are all non-stable sorting algorithms. They do not guarantee the preservation of the relative order of elements with equal keys. Merge sort and insertion sort, on the other hand, are stable sorting algorithms as they maintain the relative order of equal elements.
11.
The following items are inserted in the given order into an AVL-tree: 6, 3, 5, 2, 4, 1, 7.
Which node is in the deepest node?
Correct Answer
D. 7
Explanation
The given AVL-tree is built by inserting the nodes in the following order: 6, 3, 5, 2, 4, 1, 7. The deepest node in this tree is the node with the value 7. The AVL-tree is a self-balancing binary search tree, and the depth of a node is the length of the longest path from that node to a leaf node. In this case, the node with the value 7 is at the deepest level of the tree, meaning it has the longest path to a leaf node compared to the other nodes in the tree.
12.
Which of a) to d) is true: The size of a hash table with n keys:
Correct Answer
B. Should be a prime number greater than n for linear probing
Explanation
For linear probing, the size of the hash table should be a prime number greater than n. This is because linear probing uses a simple linear function to resolve collisions, which means that if two keys hash to the same index, the second key will be placed in the next available slot in the table. Using a prime number as the size of the table helps to minimize clustering and distribute the keys more evenly, reducing the number of collisions and improving the performance of the hash table. Therefore, the correct answer is that the size of the hash table should be a prime number greater than n for linear probing.
13.
Which of the following algorithms requires the most extra space memory (not in place algorithm)?
Correct Answer
C. Merge sort
Explanation
Merge sort requires the most extra space memory compared to the other algorithms listed. This is because merge sort uses a temporary array to merge the sorted subarrays, resulting in additional space usage. In contrast, insertion sort, selection sort, and shell sort do not require additional space for merging or creating temporary arrays.
14.
N elements are inserted from a min-heap with N elements. The total running time is:
Correct Answer
D. O(log n) worst case and O(1) average case
Explanation
When inserting N elements into a min-heap with N elements, the worst-case running time is O(log n) because each insertion requires traversing the height of the heap, which is log n. The average case running time is O(1) because on average, each insertion only requires a constant amount of operations regardless of the size of the heap. Therefore, the correct answer is O(log n) worst case and O(1) average case.
15.
Which of the following algorithms runs in O(n log n) average time but O(n^{2}) worst-case time?
Correct Answer
D. Quicksort
Explanation
Quicksort is the correct answer because it has an average time complexity of O(n log n), which means that on average it will take a time proportional to n multiplied by log n to sort the elements. However, in the worst-case scenario, where the pivot chosen is always the smallest or largest element, the time complexity can degrade to O(n2), which means it will take a time proportional to n squared to sort the elements. Therefore, quicksort runs in O(n log n) average time but O(n2) worst-case time.