CS502 Midterm Solved MCQs

CS502- Fundamentals of Algorithms · Solved MCQS From Midterm Papers · Dec 09,2012

( Marks: 1 ) - Please choose one

1.Random access machine or RAM is a/an

Machines build by Al-Khwarizmi

Mathematical model (lec#2 pg#10)

2._______________ is a graphical representation of an algorithm

Σ notation Θ notation

Flowchart( refrence cls10 chapter no1)

3. A RAM is an idealized machine with ______________ random-access memory.

256MB 512MB

an infinitely large (page#10)

100GB

4.What type of instructions Random Access Machine (RAM) can execute? Choose best

Arithmetic and logic(page#10)

5.What will be the total number of max comparisons if we run brute-force maxima

n n

n n n

Answe is option 3

6. What is the solution to the recurrence T(n) = T(n/2)+n. O(logn) (not sure)

O(n)

O(nlogn)

O( n )

7. Consider the following code: · For(j=1; j<n;j++) · For(k=1; k<15;k++) · For(l=5; l<n; l++) · Do_something_constant();

What is the order of execution for this code.

O(n)

O(

n )

O( · n log n) · O(

n )

8. Consider the following Algorithm: · if (n=1) · return 1 · else

T(n) = T(n-1) +1 T(n) = nT(n-1) +1 T(n)= T(n-1) +n

T(n)=T(n(n-1)) +1 (lec#9)

Q9. What is the total time to heapify?

(Olog n) (page#43)

(n log n) n log n) log n)

10. When we call heapify then at each level the comparison performed takes time It will take (1)

It will take (log n)

11. In Quick sort, we don’t have the control over the sizes of recursive calls True(page#49)

False Less information to decide Either true or false

Q12. Is it possible to sort without making comparisons?

Yes (pge#57)

No

Q13. If there are 𝛉 (1 marks)

n entries in edit distance matrix then the total running

(1)

n ) (pg#84)

(n) (n log n)

14. For Chain Matrix Multiplication we can not use divide and conquer approach because, We do not know the optimum k (pg#86)

We use divide and conquer for sorting only We can easily perform it in linear time Size of data is not given

15. The Knapsack problem belongs to the domain of _______________ problems. Optimization (pg#91)

NP Complete Linear Solution Sorting

16. Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50 i.e. W = 50.

The optimal solution is to pick · item · value · weight

Items 1 and 2 Items 1 and 3 Items 2 and 3 None of these

answer

1. Algebraic and logic
2. Geometric and arithmetic

3. Arithmetic and logic (rep)

4. Parallel and recursive
5. Machine build by Al-Khwarizmi
6. Mechanical machine
7. Electronics machine