What do you mean by time and space complexity? Explain Big Oh, Big Omega and Big Theta. (2076)
Explain Worst case, best case and average case of algorithm analysis with an example.
(2067, 2075)
Why do you need the algorithm analysis? (2071)
What do you mean by complexity of an algorithm?
Explain RAM model for the analysis of an algorithm with example. (2075)
Write down the formal definition of big-oh, big-omega and big-theta notation with examples.(2068, 2070, 2073)
Show that a function f = 3n²+ 4n + 7 is big theta of n².
What is the recurrence tree method? Determine a good asymptotic upper bound of following recurrence relation using recurrence tree method
T(n) = 3T (n/2) +n
Recurrence tree method is a pictorial representation of an iteration method which is in the form of a tree where at each level nodes are expanded.
In general we consider the second term in recurrence as root.
It is useful when the divide and conquer algorithm is used.
In the recurrence tree, each root and child represents the cost of a single subproblem.
We sum the cost of each levels of the tree to obtain a set of pre-levels costs and then sum all pre-levels cost to determine total cost of all levels of the recursion.
What is recurrence relation?(2067, 2068, 2069, 2070)
A recurrence relation is an inequality that describes a problem in terms of itself. Recurrence relations are used to describe recursive algorithms.
For e.g, Finding Factorial of a number n:
Fact (A, n)
{
If (n == 0)
return 1;
Else
return (n*Fact(n-1));
}
The recurrence relation is
T(n) = 1 if n = 0;
T(n) = T (n - 1) + O(1) if n > 0;
Find big-O of the following recurrence using recurrence tree method.
T(n) = T(n/2) + 1 n > 1
T(n) = 1 n = 1
(2067)
T(n) = 2T(n/2) + nn > 1= 1 n = 1
Explain the big Oh of the following recurrence relations using the iterative expansion method
T(n) = 2T(n/2)+ k, n>1
T(n) = 1, n=1
T(n) = 2T(n/2) + kn, n>1
T(n) = 1, n=1
Make a tight big-O analysis of the following code.
(2067, 2068)
What is order statistics?
The ith order statistics of a set of n elements is the ith smallest element.
For e.g, The minimum of a set of elements is the first order statistics (i = 1), and the maximum is the nth order statistics (i = n).
A median, informally, is the “halfway point” of the set.
When n is odd, the median is unique occurring at i = (n+1)/2.
When n is even, there are two medians occurring at i = n/2 and i = n/2 + 1.
This type of problem is called order statistics. Sometimes it is also called a selection problem.
How can you devise an algorithm that guarantees the section of ith order statistics in linear time? Write the algorithm of it and analyze it.
(2067, 2069)
How can you solve the selection problem in linear time? Write the algorithm and analyze for its time complexity.
We can solve the selection problem in linear time by using divide and conquer approach. The main idea for this problem solving is to partition of the element set as in Quicksort where partition is randomized one.
Note: Linear time selection algorithm is also called median finding algorithm.
Algorithm for Randomized Quicksort:
Rand Quicksort (A, l, r)
{
If (l < r)
{
P = RandPartition (A, l, r);
Rand Quicksort (A, l, p-1);
Rand Quicksort (A, p+1, r);
}
}
RandPartition (A, l, r)
{
I = Random (l, r);
swap (A[l], A[i]);
return partition (A, l, r);
}
Partition (A, l, r)
{
P = A[r];
PIndex = l;
For i = l to r-1
{
If (A[i] < = P)
{
swap (A[i], A[PIndex]);
PIndex++;
}
}
swap (A[PIndex], A[r]);
Return PIndex;
}
Analysis:
Since our algorithm is randomized algorithm, no particular input is responsible for worst case. However, the worst case running time of algorithm is O(n²). This happens if everytime unfortunately the pivot even chosen randomly came out to be largest one (while finding min element) and smallest one (while finding max element).
Since, we are in randomized version of quick sort, we analyze the expected running time and not a worst case running time because it represents the more typical time cost.
What is the main idea of randomized algorithm? (2067, 2068)
The main idea of randomized algorithm is to partition of the element set as in Quick sort where partition is randomized one.
Write an algorithm quick sort and analyze it. (2067, 2068, 2069, 2072)
Algorithm for Randomized Quicksort:
Rand Quicksort (A, l, r)
{
If (l < r)
{
P = Partition (A, l, r);
Quicksort (A, l, p-1);
Quicksort (A, p+1, r);
}
}
Partition (A, l, r)
{
P = A[r];
PIndex = l;
For i = l to r-1
{
If (A[i] < = P)
{
swap (A[i], A[PIndex]);
PIndex++;
}
}
swap (A[PIndex], A[r]);
Return PIndex;
}
Complexity Analysis:
For Time Complexity:
=> Worst Case Complexity: O (n²)
It occurs when pivot element picked is always either greatest or the smallest element.
=> Best Case Complexity: O(n log n)
When pivot element is always middle element or near to middle element
=> Average Case Complexity:
It occurs when the above condition do not occur.
Space Complexity: O(log n)
trace out the algorithm for the following array
A [] = {16, 7, 15, 14, 18, 25, 55, 32}. (2070, 2073)
Define greedy paradigm. How can you define Huffman algorithm is greedy algorithm?Explain.
What is the Greedy paradigm? Write down the Greedy job sequencing algorithm.
What do you mean by a prefix code? How Huffman algorithm generates prefix codes? Explain with an example. (2071, 2072)
What is Huffman code? Write down Huffman algorithm and find out it’s complexity. (2075)
What is prefix code? You have given a message text having seven distinct characters {p,q,r,s,t,u,v} with frequency {40,20,15,12,8,3,2}. Trace the Huffman algorithm to build the free and obtain the optimum prefix codes for each character.
What is the minimum spanning tree? Write the execution trace of the following graph to construct minimum spanning tree by prim’s algorithm
(2067, 2069)
Explain Prim’s algorithm for computing the MST of a given graph and analyze it. Also verify the correctness of this algorithm. (2067, 2069, 2070, 2072)
Describe the Prim's algorithm for finding the spanning tree of a graph. Also trace the algorithm for a weighted connected graph with at least 7 vertices. (2074, 2076)
Define convex hull in 2D. Explain Graham's Scan algorithm to compute convex hull. (2069, 2073, 2074)
Analyze it.(2070, 2071)
Explain the Gram’s scan algorithm with example to compute the convex hull of the set of points in 2D.
Define convex hull in 2D. Write the Graham's Scan algorithm and discuss its correctness and analyze its time complexity. (2076)
Define the terms ''Class P'', ''Class NP'' and ''NP -Completeness'' with suitable examples.
(2067, 2068, 2069, 2070, 2073, 2075)
What is the concept of dynamic programming? Find the longest common subsequence (LCS)between ''XMJYAUZ'' and ''MZJAWXU''.
Find the longest common subsequence between two sequences <A, B, C, B, D, A, B> and <B, D, C, A, B, A>. (2070)
Find the LCS between "XYYXXY" and "XXYXXYY". (2075)
Write an algorithm to compute the LCS of given two sequences. Trace the running of the algorithm to find the LCS of the sequences “XMJYAUZ” and be “MZJAWXU”. (2072, 2073)
What is the concept of dynamic programming? Explain the algorithm to solve the LCS and analyze it’s complexity. (2074)
What are the advantages of dynamic programming? Find Longest Common Subsequence(LCS) between''abbaab'' and ''aabaabb''.
What is linear data structure? Write down the algorithm of heap sort and find its complexity analysis.
Trace the heap-sort algorithm for the following data: {16, 41, 18, 99, 74, 20, 17, 25, 10}.
(2072, 2075)
What is divide and conquer technique
What is the shortest path problem? Explain Dijkstra's algorithm for shortest path problem.
Explain Dijkstra’s algorithm for computing the single source shortest path in a graph with a suitable example.
Write the Dijkstra’s algorithm for single source shortest path in a weighted connectedgraph. Find the shortest path form the nodesto other nodes in the following graph.
Write an algorithm for the single source shortest path in DAG. Trace the algorithm for finding the shortest path from a source vertex in the following graph. (2074)
What is left turn and right turn? Give an algorithm for finding two lines segments intersect or not by using left turn and right turn.Does this algorithm work for all cases? Justify with example. (2068, 2075)
What do you mean by left turn and right turn for given three points in 2D? Explain the method for computing the intersection of two line segments efficiently. (2069, 2076)
Define the term diagonal, ear and mouth of a simple polygon. How can you determine the intersection of two line segments efficiently? Explain in detail.
Write an algorithm of approx.-vertex-cover problem and analyze it.
What do you mean by approximation algorithm? Write the algorithm for approximate the vertex cover of a connected graph with example. (2071, 2074, 2076)
Discuss NP completeness. What is the role of approximation algorithms? Explain the algorithm for vertex cover of a graph with a running example.
What is directed acyclic graph? How to find the shortest path from a vertex of directed acyclic graph?
Use RAM model to estimate the big-oh of the running time for following code segment
Explain the master method for solving the recurrence relations. Solve the following recurrence relations using this method.
a.T(n) = 3T(n/2) + n
b.T(n) = 2T(n/4) + √n
c. T(n) = 4T(n/2) + n2 n>1
d. T(n) = 9T(n/3) +n n>1
Estimate the running time of the algorithm given by following recurrence relations using master method.
T(n) = 4T(n/2) + n³
T(n) = 2T (n/2) + n
T(n) = 3T (n/4) + n log n
How randomized quicksort works efficiently even for the worst case.
how can you solve the selection problem in linear time in worst case? Explain the algorithm.
Give the job sequencing algorithm with deadlines. You have given 5 jobs with profit pi and deadline di as
job i = { 1, 2, 3, 4, 5 }
pi = { 20, 10, 5, 15, 1 }
di = { 2, 1, 3, 2, 3 }
Find the optimal job lists that can be executed in sequence within their deadlines so as to maximize the profits.
Explain and analyze Floyd's warshall algorithm for all pairs shortest path problem. Trace the algorithm for the following graph.
What is Floyd’s algorithm? Write the details of Floyd’s algorithm to find shortest path in a graph.
Explain the algorithm to find the all pair shortest path of a weighted connected graph. Trace the algorithm for the following graph.
design the binary search algorithm and analyze it’s time complexity. (2071, 2076)
What is BST? Write the algorithm of insertion and deletion operation of BST.
Discuss the 0/1 knapsack problem and how this problem can be solved? Explain the algorithm. (2071, 2074, 2076)
Write an algorithm for depth first search. Use depth first search to find a spanning tree of the following graph.
Write an algorithm for insertion sort and estimate the best and worst case complexity.
(2072)
Write the algorithm for matrix chain multiplication and estimate its time complexity.
Trace the algorithm for matrix chain multiplication for the given chain ABCD with size array {5, 2, 3, 5, 4}
Explain Kruskal's algorithm for computing spanning trees of weighted connected graphs with an example of seven nodes graph.
Compare the algorithm for quick sort, merge sort and heap sort in terms of time and space complexity (2076)
Explain the merge-sort algorithm with example and analyze its time complexity.
(2071, 2074)
No comments:
Post a Comment