Question 1A)
The time factor when determining the efficiency of algorithm is measured by
a) Counting microseconds
b) Counting the number of key operations
c) Counting the number of statements
d) Counting the kilobytes of algorithm
Answer: b
Justification: It is hardware and language independent , rest are dependent on hardware or on software
1B) The concept of order Big O is important because
a) It can be used to decide the best algorithm that solves a given problem
b) It determines the maximum size of a problem that can be solved in a given amount of time
c) It is the lower bound of the growth rate of algorithm
d) Both A and B
Answer: a
Justification: We know that Big Oh notation is used in time complexity . the reason why we called Big Oh because it says "at any condition this is worst time that an algorithm could take " where as Big Omega says its is "best time that you can get , You cant get better than this.
1C) In worst case Quick Sort has order
A) O (n log n) B. O (n^{2} /2) C. O (log n) D. O (n^{2} /4)
Answer: A
Justification: In the worst case of quick sort has order O(n2). Quick sort is the quickest comparisonbased sorting algorithm. It is very fast and requires less additional space, only O(n log n) space is required.
1D) Consider the following program segment. What is the Space complexity?
Begin
i=0;
S=0;
S=s+1;
Return s;
End
Answer: [If i,S considered as integers] => Space Complexity = 4 +(4*2) = 12 bytes, where additional 4 bytes is for return value
To calculate the Space complexity of an algorithm, we need to follow the below instruction first:
It is the amount of memory used by the algorithm (including the input values to the algorithm) to execute and produce the result.
Space Complexity = Auxiliary Space + Input space
Calculating the Space Complexity:
For calculating the space complexity, we need to know the value of memory used by different type of datatype variables, which generally varies for different operating systems, but the method for calculating the space complexity remains the same.
Type  Size 

bool, char, unsigned char, signed char  1 byte 
short, unsigned short,  2 bytes 
float, int, unsigned int, long, unsigned long  4 bytes 
double, long double, long long  8 bytes 
(1) a)O(n) b) O(1) c)O(2^{n/2}) d) O(n^{2})
Answer: d
Justification:
An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum.
For Reference:
The complexity of linear search algorithm is
a) O(n)
b) O(log n)
c) O(n^{2})
d) O(n log n)
Answer: a
Justification: It refers to n values complexity in the algorithm which can be reduced by choosing the other algorithms.
The complexity of Bubble sort algorithm is
a) O(n)
b) O(log n)
c) O(n^{2})
d) O(n log n)
Answer: c
Justification: Bubble sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.
Question
Randomised algorithms are also called as __________________ and whose behavior is dependent on _______________ in decision making as part of its logic
Answer: probabilistic algorithm and randomness
Question:
Match the following
Answer:
Question:
Match the following
Problem

Recurrence Equation


1

Binary Search

A

tn – t_{n1} = 1

2

Merge Sort

B

T(n)=2T(n/2)+n1

3

Sequential Search

C

tn = t_{n1}
+ n

4

Factorial

D

T(n)=7T(n/2)+18(n/2)^{2}

5

Strassen Matrix Multiplication

E

T(n)=T(n/2)+1

6

Selection Sort

F

T(n)=T(n/2)+n1

Answer:
T(n) = Time Complexity
Problem

Recurrence
Equation


1

Binary
Search

E

T(n)=T(n/2)+1

2

Merge
Sort

B

T(n)=2T(n/2)+n1

3

Sequential
Search

A

tn
– t_{n1} = 1

4

Factorial

F

T(n)=T(n/2)+n1

5

Strassen
Matrix Multiplication

D

T(n)=7T(n/2)+18(n/2)^{2}

6

Selection
Sort

C

tn
= t_{n1} + n

Additional
Reference:


7

Insertion
sort



T(N)
= T(N1) + N1

8

Tree
traversal



T(n)
= 2T(n/2) + 1

9

Quicksort



(n)
= 2T(n/2) + n

10

Master
Theorm



T(n)=aT(n/b)+f(n)

Tip:
Merge Sort: The merge sort algorithm deals with the problem of sorting a list of n elements. It is able to sort a list of n elements in O(n log n) runtime, which is considerably faster than insertion sort, which takes O(n^{2}).
Merge sort uses a divide and conquer method:
1. If the length of the list is 1, the list is sorted. Return the list.
2. Otherwise, split the list in two (roughly) equal halves and then recursively merge sort the two halves
3. Merge the two sorted halves into one sorted list.
Master Theorem:
Generic equation: T(n) = aT(n/b) + f(n) where a >= 1 and b > 1
There are following three cases:
1. If f(n) < Logba then T(n) = Θ(nLogba)
2. If f(n) = Logba then T(n) = Θ(nLogba Log n)
3.If f(n) > Logba then T(n) = Θ(f(n))
Question:S = {A, B, C, B} , T = {B, D, C, A} Find the Longest Common Subsequence of S and T with detailed procedure.
Solutions:
Before jumping to any solutions, we need to understand the
logic first (Recurrence). Try to understand 3 key points below for further
moving:
So we define Si, Tj to be the prefixes of S and T of
length i and j respectively.
Let, C[i,j]=LCS(Si, Tj)
Recurrence Tip:
1 If i=0 and j=0 then value would be 0
2 If Si=Tj then value would be as C [i1, j1] + 1 [Meaning, Character
matched > apply formula]
3 If Si
≠ Tj then
value would be as max{C [i, j1], C [i1, j] } [Meaning, Not matched > take the max out of both]
Given:  String as S and T with the length of 4 and 4
respectively. m=4 and n=4
1^{st} Operation:
C (1, 1) = max { C (0,1) , C(1,0) } = 0 [Character, not matched  >
Apply 3rd formula]
C (1, 2) = max { C (0,2) , C(1,1) } = 0
C (1, 3) = max { C (0,3) , C(1,2) } = 0
C (1, 4) = C (0, 3) + 1 = 0+1 = 1 [Character matched > apply 2nd formula]
2^{nd} Operation:
C (2, 1) = C (1, 0) + 1 = 0 + 1 = 1
C (2, 2) = max { C (1,2) , C(2,1) } = 1
C (2, 3) = max { C (1,3) , C(2,2) } = 1
C (2, 4) = max { C (1,4) , C(2,2) } = 1
3^{rd} Operation:
C (3, 1) = max { C (2,1) , C(3,0) } = 1
C (3, 2) = max { C (2,2) , C(3,1) } = 1
C (3, 3) = C(2,2) + 1 = 2
C (3, 4) = max { C (2,4) , C(3,3) } =2
C (4, 1) = C (3, 0) + 1 = 0 + 1 = 1
C (4, 2) = max { C (3,2) , C(4,1) } = 1
C (4, 3) = max { C (3,3) , C(4,2) } = 2
C (4, 4) = max { C (3,4) , C(4,3) } = 2
Finally we get the table as given below:
Finding the LCS:
* The last digit defines the length of our LCS.
* Follow the below table to get the LCS.
*The LCS is : B C
Question:
Apply merge sort for the following list of elements: 6, 3, 7, 8, 2, 4, 5, 1 . Analyze the time complexity of Merge Sort.
Solution:
Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition. If the list has more than one item, we split the list and recursively invoke a merge sort on both halves.
Apply merge sort for the following list of elements: 6, 3, 7, 8, 2, 4, 5, 1 . Analyze the time complexity of Merge Sort.
Solution:
Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition. If the list has more than one item, we split the list and recursively invoke a merge sort on both halves.
Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted.
Time Complexity : O(n1 + n2)
No comments:
Post a Comment