CS502 Quiz 1 Set 3

Q1. For 2D Maxima problem, Plane Sweep algorithm first of all _________.

1. Sorts all points
2. Output the elements
3. Pushes all points on stack
4. Delete some points

Correct answer: Sorts all points

Q2. For small values of n, _______________ algorithm is fast enough.

1. Any
2. quick sort
3. heap sort
4. merge sort

Correct answer: Any

Q3.

1. that it is used for large n
2. that if used for small n
3. constant amount of time
4. time can not be calculated

Correct answer: constant amount of time

Q4. The asymptotic growth of n(n+1)/2 is:

1. O(n+2)
2. O(n log n)
3. O(n²)
4. O(n)

Correct answer: O(n²)

Q5. In Running Time Analysis, we are also concerned about the _______________ required by the algorithm.

1. Memory
2. Both space and memory
3. code
4. Space

Correct answer: Space

Q6. In 2-D maxima problem, A point p is said to be dominated by point q if ________________.

1. p.x = q.x and p.y = q.y
2. p.x ≠ q.x and p.y ≠ q.y
3. p.x ≤ q.x and p.y ≤ q.y
4. p.x ≥ q.x and p.y ≥ q.y

Correct answer: p.x ≤ q.x and p.y ≤ q.y

Q7. Rank of an element can be defined as ____________

1. Two minus the number of elements that are smaller
2. One minus the number of elements that are smaller
3. One plus the number of elements that are smaller
4. Two plus the number of elements that are greater

Correct answer: One plus the number of elements that are smaller

Q8. For n > 1, _______ divides into two halves, sorts the two and then combine them together.

1. Heap Sort
2. Insertion Sort
3. MergeSort
4. Quick Sort

Correct answer: MergeSort

Q9. Random Access Machine (RAM) can execute ________________ instructions.

1. Only arithmetic
2. Logical and arithmetic
3. Only logical
4. Parallel

Correct answer: Logical and arithmetic

Q10. The main purpose of mathematical analysis is measuring the ____________required by the algorithm.

1. Execution time
2. Execution time and memory
3. Inputs & outputs
4. Space

Correct answer: Execution time