|
The sieve technique is a special case, where the number of sub problems is just
• 5
• Many
• 1
• few
Question No: 1 ( Marks: 1 ) - Please choose one
Random access machine or RAM is a/an
► Machine build by Al-Khwarizmi
► Mechanical machine
► Electronics machine
► Mathematical model
Question No: 2 ( Marks: 1 ) - Please choose one
_______________ is a graphical representation of an algorithm
► notation
► notation
► Flowchart
► Asymptotic notation
Question No: 3 ( Marks: 1 ) - Please choose one
A RAM is an idealized machine with ______________ random-access memory.
► 256MB
► 512MB
► an infinitely large
► 100GB
Question No: 4 ( Marks: 1 ) - Please choose one
What type of instructions Random Access Machine (RAM) can execute? Choose best answer
► Algebraic and logic
► Geometric and arithmetic
► Arithmetic and logic
► Parallel and recursive
Question No: 5 ( Marks: 1 ) - Please choose one
What will be the total number of max comparisons if we run brute-force maxima algorithm with n elements?
►
►
►
►
Question No: 6 ( Marks: 1 ) - Please choose one
What is the solution to the recurrence T(n) = T(n/2)+n .
► O(logn)
► O(n)
► O(nlogn)
► O(n2)
Question No: 7 ( Marks: 1 ) - Please choose one
Consider the following code:
For(j=1; j
For(l=5; l
Do_something_constant();
}
What is the order of execution for this code.
► O(n)
► O(n3)
► O(n2 log n)
► O(n2)
Question No: 8 ( Marks: 1 ) - Please choose one
Consider the following Algorithm:
Factorial (n){
if (n=1)
return 1
else
return (n * Factorial(n-1))
}
Recurrence for the following algorithm is:
► 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
Question No: 9 ( Marks: 1 ) - Please choose one
What is the total time to heapify?
► Ο(log n)
► Ο(n log n)
► Ο(n2 log n)
► Ο(log2 n)
Question No: 10 ( Marks: 1 ) - Please choose one
When we call heapify then at each level the comparison performed takes time
► It will take Θ (1)
► Time will vary according to the nature of input data
► It can not be predicted
► It will take Θ (log n)
Question No: 11 ( Marks: 1 ) - Please choose one
In Quick sort, we don’t have the control over the sizes of recursive calls
► True
► False
► Less information to decide
► Either true or false
Question No: 12 ( Marks: 1 ) - Please choose one
Is it possible to sort without making comparisons?
► Yes
► No
Question No: 13 ( Marks: 1 ) - Please choose one
If there are Θ (n2) entries in edit distance matrix then the total running time is
► Θ (1)
► Θ (n2)
► Θ (n)
► Θ (n log n)
Question No: 14 ( Marks: 1 ) - Please choose one
For Chain Matrix Multiplication we can not use divide and conquer approach because,
► We do not know the optimum k
► We use divide and conquer for sorting only
► We can easily perform it in linear time
► Size of data is not given
Question No: 15 ( Marks: 1 ) - Please choose one
The Knapsack problem belongs to the domain of _______________ problems.
► Optimization
► NP Complete
► Linear Solution
► Sorting
Question No: 16 ( Marks: 1 ) - Please choose one
Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50 i.e. W = 50.
Item Value Weight
1 60 10
2 100 20
3 120 30
The optimal solution is to pick
► Items 1 and 2
► Items 1 and 3
► Items 2 and 3
► None of these
3. ______________ graphical representation of algorithm.
> asymptotic
>. flowchart
4. who invented the quick sort
C.A.R. Hoare
5. function is given like 4n^4+ 5n^3+n what is the run time of this
• (n^4)
• (n^3)
• (4n^4+ 5n^3)
• (4n^4+ 5n^3)
6. main elements to a divide-and-conquer
Divide---->conquer---------->combine
7. T(n)={4 if n=1, otherwise T(n/5)+3n^2
what is the answer if n=5
answer is 79
8. Merge sort is a stable algorithm but not an in-place algorithm.
>True
>false
_______________ is a graphical representation of an algorithm
• notation
• Flowchart
• Asymptotic notation
• notation
Question No: 2 ( Marks: 1 ) - Please choose one
Which of the following is calculated with Big o notation?
• Lower bounds
• Upper bounds
• Both upper and lower bound
• Medium bounds
Question No: 3 ( Marks: 1 ) - Please choose one
Merge sort makes two recursive calls. Which statement is true after these recursive calls
finish, but before the merge step?
• The array elements form a heap
• Elements in each half of the array are sorted amongst themselves
• Elements in the first half of the array are less than or equal to elements in the
second half of the array
• None of the above
Question No: 4 ( Marks: 1 ) - Please choose one
Who invented Quick sort procedure?
• Hoare
• Sedgewick
• Mellroy
• Coreman
Question No: 5 ( Marks: 1 ) - Please choose one
What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1
• O(logn)
• O(n)
• O(nlogn)
• O(2n)
FINALTERM EXAMINATION
Fall 2008
CS502- Fundamentals of Algorithms (Session - 1)
Marks: 75
Question No: 1 ( Marks: 1 ) - Please choose one
_______________ is a graphical representation of an algorithm
notation
Flowchart
Asymptotic notation
notation
Question No: 2 ( Marks: 1 ) - Please choose one
Which of the following is calculated with Bigo notation?
Lower bounds
Upper bounds
Both upper and lower bound
Medium bounds
Question No: 3 ( Marks: 1 ) - Please choose one
Merge sort makes two recursive calls. Which statement is true after these recursive calls
finish, but before the merge step?
The array elements form a heap
Elements in each half of the array are sorted amongst themselves
Elements in the first half of the array are less than or equal to elements in the
second half of the array
None of the above
Question No: 4 ( Marks: 1 ) - Please choose one
Who invented Quick sort procedure?
Hoare
Sedgewick
Mellroy
Coreman
Question No: 5 ( Marks: 1 ) - Please choose one
What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1
O(logn)
O(n)
O(nlogn)
O(2n)
Question No: 6 ( Marks: 1 ) - Please choose one(Huffman tree is missing)
Consider the following Huffman Tree
The binary code for the string TEA is
10 00 010
011 00 010
10 00 110
11 10 110
Question No: 7 ( Marks: 1 ) - Please choose one
If a graph has v vertices and e edges then to obtain a spanning tree we have to delete
v edges.
v e + 5 edges
v + e edges.
None of these
Question No: 8 ( Marks: 1 ) - Please choose one
Can an adjacency matrix for a directed graph ever not be square in shape?
Yes
No
Question No: 9 ( Marks: 1 ) - Please choose one
One of the clever aspects of heaps is that they can be stored in arrays without using any
_______________.
Pointers
constants
variables
functions
Question No: 10 ( Marks: 1 ) - Please choose one
Merge sort requires extra array storage,
True
False
Question No: 11 ( Marks: 1 ) - Please choose one
Non-optimal or greedy algorithm for money change takes____________
O(k)
O(kN)
O(2k)
O(N)
http://ping.fm/2WhSM
• 5
• Many
• 1
• few
Question No: 1 ( Marks: 1 ) - Please choose one
Random access machine or RAM is a/an
► Machine build by Al-Khwarizmi
► Mechanical machine
► Electronics machine
► Mathematical model
Question No: 2 ( Marks: 1 ) - Please choose one
_______________ is a graphical representation of an algorithm
► notation
► notation
► Flowchart
► Asymptotic notation
Question No: 3 ( Marks: 1 ) - Please choose one
A RAM is an idealized machine with ______________ random-access memory.
► 256MB
► 512MB
► an infinitely large
► 100GB
Question No: 4 ( Marks: 1 ) - Please choose one
What type of instructions Random Access Machine (RAM) can execute? Choose best answer
► Algebraic and logic
► Geometric and arithmetic
► Arithmetic and logic
► Parallel and recursive
Question No: 5 ( Marks: 1 ) - Please choose one
What will be the total number of max comparisons if we run brute-force maxima algorithm with n elements?
►
►
►
►
Question No: 6 ( Marks: 1 ) - Please choose one
What is the solution to the recurrence T(n) = T(n/2)+n .
► O(logn)
► O(n)
► O(nlogn)
► O(n2)
Question No: 7 ( Marks: 1 ) - Please choose one
Consider the following code:
For(j=1; j
For(l=5; l
Do_something_constant();
}
What is the order of execution for this code.
► O(n)
► O(n3)
► O(n2 log n)
► O(n2)
Question No: 8 ( Marks: 1 ) - Please choose one
Consider the following Algorithm:
Factorial (n){
if (n=1)
return 1
else
return (n * Factorial(n-1))
}
Recurrence for the following algorithm is:
► 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
Question No: 9 ( Marks: 1 ) - Please choose one
What is the total time to heapify?
► Ο(log n)
► Ο(n log n)
► Ο(n2 log n)
► Ο(log2 n)
Question No: 10 ( Marks: 1 ) - Please choose one
When we call heapify then at each level the comparison performed takes time
► It will take Θ (1)
► Time will vary according to the nature of input data
► It can not be predicted
► It will take Θ (log n)
Question No: 11 ( Marks: 1 ) - Please choose one
In Quick sort, we don’t have the control over the sizes of recursive calls
► True
► False
► Less information to decide
► Either true or false
Question No: 12 ( Marks: 1 ) - Please choose one
Is it possible to sort without making comparisons?
► Yes
► No
Question No: 13 ( Marks: 1 ) - Please choose one
If there are Θ (n2) entries in edit distance matrix then the total running time is
► Θ (1)
► Θ (n2)
► Θ (n)
► Θ (n log n)
Question No: 14 ( Marks: 1 ) - Please choose one
For Chain Matrix Multiplication we can not use divide and conquer approach because,
► We do not know the optimum k
► We use divide and conquer for sorting only
► We can easily perform it in linear time
► Size of data is not given
Question No: 15 ( Marks: 1 ) - Please choose one
The Knapsack problem belongs to the domain of _______________ problems.
► Optimization
► NP Complete
► Linear Solution
► Sorting
Question No: 16 ( Marks: 1 ) - Please choose one
Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50 i.e. W = 50.
Item Value Weight
1 60 10
2 100 20
3 120 30
The optimal solution is to pick
► Items 1 and 2
► Items 1 and 3
► Items 2 and 3
► None of these
3. ______________ graphical representation of algorithm.
> asymptotic
>. flowchart
4. who invented the quick sort
C.A.R. Hoare
5. function is given like 4n^4+ 5n^3+n what is the run time of this
• (n^4)
• (n^3)
• (4n^4+ 5n^3)
• (4n^4+ 5n^3)
6. main elements to a divide-and-conquer
Divide---->conquer---------->combine
7. T(n)={4 if n=1, otherwise T(n/5)+3n^2
what is the answer if n=5
answer is 79
8. Merge sort is a stable algorithm but not an in-place algorithm.
>True
>false
_______________ is a graphical representation of an algorithm
• notation
• Flowchart
• Asymptotic notation
• notation
Question No: 2 ( Marks: 1 ) - Please choose one
Which of the following is calculated with Big o notation?
• Lower bounds
• Upper bounds
• Both upper and lower bound
• Medium bounds
Question No: 3 ( Marks: 1 ) - Please choose one
Merge sort makes two recursive calls. Which statement is true after these recursive calls
finish, but before the merge step?
• The array elements form a heap
• Elements in each half of the array are sorted amongst themselves
• Elements in the first half of the array are less than or equal to elements in the
second half of the array
• None of the above
Question No: 4 ( Marks: 1 ) - Please choose one
Who invented Quick sort procedure?
• Hoare
• Sedgewick
• Mellroy
• Coreman
Question No: 5 ( Marks: 1 ) - Please choose one
What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1
• O(logn)
• O(n)
• O(nlogn)
• O(2n)
FINALTERM EXAMINATION
Fall 2008
CS502- Fundamentals of Algorithms (Session - 1)
Marks: 75
Question No: 1 ( Marks: 1 ) - Please choose one
_______________ is a graphical representation of an algorithm
notation
Flowchart
Asymptotic notation
notation
Question No: 2 ( Marks: 1 ) - Please choose one
Which of the following is calculated with Bigo notation?
Lower bounds
Upper bounds
Both upper and lower bound
Medium bounds
Question No: 3 ( Marks: 1 ) - Please choose one
Merge sort makes two recursive calls. Which statement is true after these recursive calls
finish, but before the merge step?
The array elements form a heap
Elements in each half of the array are sorted amongst themselves
Elements in the first half of the array are less than or equal to elements in the
second half of the array
None of the above
Question No: 4 ( Marks: 1 ) - Please choose one
Who invented Quick sort procedure?
Hoare
Sedgewick
Mellroy
Coreman
Question No: 5 ( Marks: 1 ) - Please choose one
What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1
O(logn)
O(n)
O(nlogn)
O(2n)
Question No: 6 ( Marks: 1 ) - Please choose one(Huffman tree is missing)
Consider the following Huffman Tree
The binary code for the string TEA is
10 00 010
011 00 010
10 00 110
11 10 110
Question No: 7 ( Marks: 1 ) - Please choose one
If a graph has v vertices and e edges then to obtain a spanning tree we have to delete
v edges.
v e + 5 edges
v + e edges.
None of these
Question No: 8 ( Marks: 1 ) - Please choose one
Can an adjacency matrix for a directed graph ever not be square in shape?
Yes
No
Question No: 9 ( Marks: 1 ) - Please choose one
One of the clever aspects of heaps is that they can be stored in arrays without using any
_______________.
Pointers
constants
variables
functions
Question No: 10 ( Marks: 1 ) - Please choose one
Merge sort requires extra array storage,
True
False
Question No: 11 ( Marks: 1 ) - Please choose one
Non-optimal or greedy algorithm for money change takes____________
O(k)
O(kN)
O(2k)
O(N)
http://ping.fm/2WhSM