CS502 Midterm Preparation

CS502 MIDTERM PREPARATION · LEC WISE MCQS from lec 1 to 10 · Solved by Anie

Q1. The term "Algorithm" is derived from:

1. Euclid
2. Turing
3. Al-Khwarizmi ✅
4. Fibonacci

Q2. An algorithm is:

1. A software
2. A hardware component
3. A set of programming instructions
4. A well-defined computational procedure ✅

Q3. What distinguishes an algorithm from a program?

1. Syntax
2. Efficiency
3. Independence from language/hardware ✅
4. Memory usage

Q4. Macro programming issues relate to:

1. Performance
2. Coordination of multiple programmers ✅
3. Loop optimization
4. Variable names

Q5. Micro issues are focused on:

1. Team management
2. High-level architecture
3. Critical code sections that consume most execution time ✅
4. Hardware design

Q6. Worst-case time complexity is:

1. Best possible performance
2. Maximum time taken for input size n ✅
3. Minimum time required
4. Random average

Q7. Which of the following is NOT a resource considered in algorithm analysis?

1. Time
2. Space
3. Battery life ✅
4. Bandwidth

Q8. Average-case analysis depends on:

1. Sorting
2. Probability distribution of inputs ✅
3. Execution environment
4. Code length

Q9. The primary mathematical model used is:

1. CPU architecture
2. RAM model ✅
3. Neural network
4. Turing machine

Q10. Which algorithm was used to solve 2D Maxima problem in brute force?

1. Merge sort
2. Plane sweep
3. Nested loops
4. Double for loop comparing all points ✅

Q11. Worst-case time for brute-force maxima algorithm is:

1. Θ(n log n)
2. Θ(n²) ✅
3. Θ(n)
4. Θ(log n)

Q12. What does Θ notation represent?

1. Upper bound
2. Lower bound
3. Exact growth rate ✅
4. None of the above

Q13. What is the sum of first n natural numbers?

1. n
2. n(n+1)/2 ✅
3. n²
4. log n

Q14. Which of the following is a geometric series?

1. 1 + 2 + 3 + ...
2. 1 + x + x² + ... + xⁿ ✅
3. 1 + 1/2 + 1/3 + ...
4. 1 + 2² + 3²

Q15. The harmonic series grows as:

1. Constant
2. Linear
3. Logarithmic ✅
4. Quadratic

Q16. Running time of NESTED-LOOPS example was:

1. Θ(n²)
2. Θ(n log n)
3. Θ(n³) ✅
4. Θ(n⁴)

Q17. Summation of i² from i=1 to n is:

1. n(n+1)/2
2. (n(n+1)(2n+1))/6 ✅
3. 2n
4. n!

Q18. Which function grows fastest asymptotically?

1. log n
2. n
3. n log n
4. 2ⁿ ✅

Q19. In asymptotic notation, O(g(n)) represents:

1. Lower bound
2. Exact value
3. Upper bound ✅
4. Average

Q20. Which of the following is a valid example of Θ(n²)?

1. 5n
2. 8n² + 2n - 3 ✅
3. log n
4. 2ⁿ

Q21. Plane-sweep algorithm improves brute-force by:

1. Recursion
2. Stack usage ✅
3. Matrix multiplication
4. Sorting edges

Q22. Plane-sweep first sorts the points based on:

1. y-coordinate
2. Weight
3. x-coordinate ✅
4. Value

Q23. Which data structure is used in plane-sweep for storing maximal points?

1. Queue
2. List
3. Tree
4. Stack ✅

Q24. Plane-sweep algorithm time complexity:

1. Θ(n²)
2. Θ(n log n) ✅
3. Θ(log n)
4. Θ(n³)

Q25. In plane-sweep, why does while-loop execute at most n times?

1. Due to nested loops