Design and Analysis of Algorithms - B.C.A 17-20 Sem 4
SAINTGITS
COLLEGE OF APPLIED SCIENCES
First Internal Assessment Examination, Feb 2019
Department of B.C.A, Semester IV
DESIGN
AND ANALYSIS OF ALGORITHM
Time : 2 hours Total: 50 Marks
Section
A
Answer
any 5 questions. Each question carries 2 marks.
1. Define an Algorithm.
An algorithm (pronounced
AL-go-rith-um) is a procedure or formula for solving a problem, based on
conductiong a sequence of specified actions. A computer program can be viewed
as an elaborate algorithm
2. What is divide and conquer approach?
Divide-and-conquer algorithm. ...
A divide-and-conquer algorithm works by recursively breaking
down a problem into two or more sub-problems of the same or related type, until
these become simple enough to be solved directly. The solutions to the
sub-problems are then combined to give a solution to the original problem.
3. What is performance analysis of an algorithm?
Performance analysis of an algorithm depends upon two factors
i.e. amount of memory used and amount of compute time consumed on any CPU.
Formally they are notified as complexities in terms of:
§ Space
Complexity.
§ Time
Complexity.
4. Define Ω-notation
The notation Ω(n)
is the formal way to express the lower bound of an algorithm's running time. It
measures the best case time complexity or the best amount of time an algorithm
can possibly take to complete.
5. What is an algorithm design technique?
Algorithm
design is identified and incorporated into many solution
theories of operation research, such as dynamic programming and
divide-and-conquer.
6. if F(n) = 5n2+6n+4, then prove that f(n) is O(n2).
(5 X 2 = 10 marks)
Section B
Short
essay questions
Answer any 5
questions. Each question carries 5 marks.
7. Write the algorithm of merge sort.
Only write algorithm of merge sort - 5 marks
8. What is
the best case, average case and worst case of a linear search algorithm?
In
computer science, best, worst, and average cases of a given algorithm express
what the resource usage is at least, at most and on average, respectively.
Usually the resource being considered is running time, i.e. time complexity,
but it could also be memory or other resource. Best case is the function which
performs the minimum number of steps on input data of n elements. Worst case is
the function which performs the maximum number of steps on input data of size
n. Average case is the function which performs an average number of steps on
input data of n elements.
9. Write
the differences between linear search and binary search.
Linear
search does the sequential access whereas Binary
search access data randomly. Input data needs to be sorted in
Binary Search and not in Linear Search. ... The best case
time in linear search is for the first element that is O(1).
And the other side O(1) is the middle element in binary search.
10. Explain in detail with an example Strassen’s
matrix multiplication method.
Write the equations and explanation of Strassen’s
matrix multiplication method - 3 marks
Example - 2 marks
11. Illustrate Big oh, Theta and Omega notations
graphically and explain.
Definitions - 2 marks
Graphical explanation - 3marks
12. Write an algorithm for quick sort and write its
time complexity.
Algorithm - 5 marks.
(5 X 5 = 25 marks)
Section C
Long essay
questions
Answer any 1question.
It carries 15marks.
13. Apply binary
search to the list {4, 6, 10, 17, 23, 32, 42, 48} and find the location of item
6.
Apply binary
search to trace the given list.
Item found in location
2.
Only tracing is
required.
14. Write the
algorithm of quick sort and apply it on the list {5, 3, 1, 9, 8, 2, 4, 7}
Definition 3 marks
Algorithm 7 marks
Tracing 5
marks
Comments
Post a Comment