Scribd
Upload
9 views2 pages

Question Bank M1

The document is a question bank for a Computer Science and Engineering course, specifically for the BCS401 module. It includes a variety of questions related to algorithms, algorithm design and analysis, efficiency classes, and specific algorithm implementations such as GCD, factorial, Fibonacci, and sorting methods. Additionally, it covers theoretical concepts such as asymptotic notations and efficiency analysis for both recursive and non-recursive algorithms.

Uploaded by

pranay.3818
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

Question Bank M1

The document is a question bank for a Computer Science and Engineering course, specifically for the BCS401 module. It includes a variety of questions related to algorithms, algorithm design and analysis, efficiency classes, and specific algorithm implementations such as GCD, factorial, Fibonacci, and sorting methods. Additionally, it covers theoretical concepts such as asymptotic notations and efficiency analysis for both recursive and non-recursive algorithms.

Uploaded by

pranay.3818
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Department of Computer Science and Engineering

BCS401-Question Bank
Module -1
1) What is an algorithm. Write algorithms using any 2 methods for obtaining GCD of 2
numbers also explain the same……………………………………………………………6M
2) Explain the algorithm design and analysis process……………………………………….8M
3) Algorithm enigma (A[0----n-1,0------n-1]
for i 0 to n-2 do
for j i+1 to n-1 do
if A[ i,j] ≠ A[j, i]
return FALSE
END for
return TRUE
END Algorithm
i. What does the Algorithm compute ………………………………….…………10M
ii. What is its input size
iii. What is its basic operation
iv. How many times is the basic operation executed
v. What is the efficiency class of this algorithm
4) What are the various basic efficiency classes? Explain Big O, Big Omega and Big Theta
asymptotic notations………………………………………………………………………10M
5) Prove the following theorem if t1(n) ϵO((g1(n)) and t2(n) ϵ O(g2(n)) then
t1(n)+ t2(n) ϵ O(max{g1(n),g2(n}). ………………………………………….………..4M
6) What are the basic efficiency classes. List the following function according to their order of
growth from lowest to highest. State proper reasons.
(n-2)! ,5 log (n+100)10, 22n , 0.001n4 +3n3+1,ln2 n, 3√n,3n…………………....………….4M

7) The factorial function n! has value 1when n<=1 and value n *(n-1)! When n is >1.
Write both a recursive and iterative algorithm to compute n!.……………………….….…..6M
Department of Computer Science and Engineering

8) Write both a recursive and iterative algorithm to compute nth Fibonacci number, analyze its
efficiency.
9) Write an algorithm to find uniqueness of elements in an array and give the mathematical
analysis of this non-recursive algorithm with all steps……………………………………..8M
10) Explain the general plan for analyzing the efficiency of non recursive algorithm. Write an
algorithm to find max element in the array of n elements. Give mathematical analysis of this
algorithm…………………………………………………………………………….…8M
11) Explain the general plan for analyzing the efficiency of recursive algorithm. Write a
recursive algorithm for Tower of Hanoi problem and analyze the
same…………………………………….……………..………………………..…………7M
12) Design an algorithm for performing sequential search, discuss the best case, worst case, and
average case efficiency of this algorithm..………………………………………………….10M
13) Write an algorithm to compute the product of 2 matrices and analyze the same ………….6M
14) Write a non recursive algorithm for finding the number of digits required to in a binary
representation of a decimal number………………………………………………………5M
15) Write an algorithm for Selection sort, trace its working for the given elements and also
analyze its efficiency.
89 45 68 90 29 34 17
16) Write an algorithm for Bubble sort, trace its working for the given elements and also analyze
its efficiency.
89 45 68 90 29 34 17
17) Explain Brute Force String Matching problem with an example. Write an algorithm for the
same and analyze its efficiency………………………………………………………..8M
18) Define the following and give an example:
(i) Time Efficiency
(ii) Space Efficiency
(iii) Order of Growth

You might also like