Design and Analysis of Algorithms

The fractional Knapsack problem can be solved by using

BFS on a graph $ G=(V,E) $ has running time

The minimum number of colors needed to color a graph having $ n>3 $ vertices and 2 edges is

Complexity the recurrence relation $ T(n)=8T(\frac{n}{2})+n^2 $ is

Travelling salesman problem belongs to

Kruskal's algorithm uses ___ and Prism' algorithm uses ___ in determining the MST

Level order traversal of a rooted tree can be done by starting from root and performing

An algorithm is made up of two independent time complexities $ f(n) $ and $ g(n) $. Then the complexities of the algorithm is in order of

Which of the following standard algorithms is not a greedy algorithm?

The node removal of which makes a graph disconnected is called

Write the algorithm for quick-sort and find its complexity.

Discuss the average, worst, best time complexity of the algorithm. Give suitable examples.

Construct the Huffman coding tree for the text of characters with given frequencies: T:43, I:38, V:16, K:8, L:56, E:12, O:41, Z:13, P:22, R:6.

State the general Knapsack problem. Write a greedy algorithm for this problem and derive its time complexity.

State master's theorem and find the time complexity for the following recurrence: $ T(n) = 2T(n^{1/2}) + \log n $

What is negative weight-cycle? Write Bellman-Ford algorithm to find single source shortest distance of a directed graph.

Find the minimum number of operations required for the following matrix chain multiplication using dynamic programming: $ A(10 \times 20) * B(20 \times 50) * C(50 \times 1) * D(1 \times 100) $

Write Knuth-Morris-Pratt algorithm for string matching problem.

Write an algorithm to find a minimum spanning tree (MST) for an undirected graph. Estimate the time complexity of your algorithm.

Using greedy strategy. Schedule the following jobs within deadline so as to maximize the profit. Deadline and profits are mentioned as follow:
Job i: 1, 2, 3, 4
Deadline d: 3, 2, 3, 1
Profit g: 9, 7, 7, 2

Write an algorithm for n-queen's problem find its time-complexity and explain the algorithm using an example.

Solve the single source shortest path problem for the following graph considering '1' as the source vertex using Dijkstra's algorithm.

Define the classes P and NP.

Discuss what you mean by polynomial reduction.

Discuss diagrammatically the relation among P class, NP class, NP hard and NP complete.

Describe Clique Decision Problem (CDP).

Explain the max-flow min-cut theorem with an example.

The fractional Knapsack problem can be solved by using

BFS on a graph $G=(V,E)$ has running time

The minimum number of colors needed to color a graph having n>3 vertices and 2 edges is

Complexity the recurrence relation $T(n)=8T(\frac{n}{2})+n^2$ is

Travelling salesman problem belongs to

Kruskal's algorithm uses ___ and Prism' algorithm uses ___ in determining the MST

Level order traversal of a rooted tree can be done by starting from root and performing

An algorithm is made up of two independent time complexities $f(n)$ and $g(n)$. Then the complexities of the algorithm is in order of

Which of the following standard algorithms is not a greedy algorithm?

The node removal of which makes a graph disconnected is called

Write the algorithm for quick-sort and find its complexity.

Discuss the average, worst, best time complexity of the algorithm. Give suitable examples.

Construct the Huffman coding tree for the text of characters with given frequencies: T:43, I:38, V:16, K:8, L:56, E:12, O:41, Z:13, P:22, R:6.

State the general Knapsack problem. Write a greedy algorithm for this problem and derive its time complexity.

State master's theorem and find the time complexity for the following recurrence: $ T(n) = 2T(n^{1/2}) + \log n $

What is negative weight-cycle? Write Bellman-Ford algorithm to find single source shortest distance of a directed graph.

Find the minimum number of operations required for the following matrix chain multiplication using dynamic programming: $ A(10 \times 20) * B(20 \times 50) * C(50 \times 1) * D(1 \times 100) $

Write Knuth-Morris-Pratt algorithm for string matching problem.

Write an algorithm to find a minimum spanning tree (MST) for an undirected graph. Estimate the time complexity of your algorithm.

Using greedy strategy. Schedule the following jobs within deadline so as to maximize the profit. Deadline and profits are mentioned as follow:
Job i: 1, 2, 3, 4
Deadline d: 3, 2, 3, 1
Profit g: 9, 7, 7, 2

Write an algorithm for n-queen's problem find its time-complexity and explain the algorithm using an example.

Solve the single source shortest path problem for the following graph considering '1' as the source vertex using Dijkstra's algorithm.

Define the classes P and NP.

Discuss what you mean by polynomial reduction.

Discuss diagrammatically the relation among P class, NP class, NP hard and NP complete.

Describe Clique Decision Problem (CDP).

Explain the max-flow min-cut theorem with an example.

• Asymptotic notations
• Heap creation technique
• Strassen's matrix multiplication
• Divide-and-Conquer vs Dynamic programming

Any decision trees that sorts elements has height

Which one of the following is an application of Queue Data Structure?

The complexity of binary search algorithm is

In linear search algorithm the worst case occurs when

Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

Approach of dynamic programming is similar to

In the divide and conquer process, breaking the problem into smaller sub-problems is the responsibility of

A priority queue is implemented as a Max-heap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements '1' and '7' are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called

The choice of polynomial class has led to the development of an extensive theory called

Calculate the time complexity of the following problem using divide and conquer strategies:
(i) $ T(n) = \sqrt{n} T(\sqrt{n}) + n $, $ n > 2 $
$ = a $, $ n \le 2 $
(ii) $ T(n) = T(n-1) + 1/n $, $ n > 1 $
$ = 1 $, $ n = 1 $

Write time function and calculate the time complexity, space complexity and number of function calls of the following pseudocode using substitution method:
rec (n) {
if ($ n \le 1 $) return(1);
else { rec (n/2); for ($ i=1; i \le n; i++ $) printf("algorithm"); }
}

Explain the working of merge sort algorithm with an example. Give the complexity calculation of merge sort.

What are the rules of manipulate Big-Oh expression and about the typical growth rates of algorithms.

What is heap sort? What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?

Explain how radix sort works, to what inputs it can be applied and what is its asymptotic complexity?

What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider the given graph $ G=(V,E) $ and find the minimum spanning tree by Prim's algorithms.

Find the optimal way to multiply the following matrices to perform the fewest multiplications:
A1: $ 5 \times 11 $, A2: $ 11 \times 4 $, A3: $ 4 \times 15 $, A4: $ 15 \times 23 $

You are given a graph containing n vertices and m edges and given that the graph doesn't contain cycle of odd length. What is the time complexity of the best known algorithm to find out whether the graph is bipartite or not?

What is activity selection problem? Suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

Any decision trees that sorts elements has height

Which one of the following is an application of Queue Data Structure?

The complexity of binary search algorithm is

In linear search algorithm the worst case occurs when

Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

Approach of dynamic programming is similar to

In the divide and conquer process, breaking the problem into smaller sub-problems is the responsibility of

A priority queue is implemented as a Max-heap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements '1' and '7' are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called

The choice of polynomial class has led to the development of an extensive theory called

Calculate the time complexity of the following problem using divide and conquer strategies:
(i) $ T(n) = \sqrt{n} T(\sqrt{n}) + n $, $ n > 2 $
$ = a $, $ n \le 2 $
(ii) $ T(n) = T(n-1) + 1/n $, $ n > 1 $
$ = 1 $, $ n = 1 $

Write time function and calculate the time complexity, space complexity and number of function calls of the following pseudocode using substitution method:
rec (n) {
if ($ n \le 1 $) return(1);
else { rec (n/2); for ($ i=1; i \le n; i++ $) printf("algorithm"); }
}

Explain the working of merge sort algorithm with an example. Give the complexity calculation of merge sort.

What are the rules of manipulate Big-Oh expression and about the typical growth rates of algorithms.

What is heap sort? What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?

Explain how radix sort works, to what inputs it can be applied and what is its asymptotic complexity?

What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider the given graph $ G=(V,E) $ and find the minimum spanning tree by Prim's algorithms.

Find the optimal way to multiply the following matrices to perform the fewest multiplications:
A1: $ 5 \times 11 $, A2: $ 11 \times 4 $, A3: $ 4 \times 15 $, A4: $ 15 \times 23 $

You are given a graph containing n vertices and m edges and given that the graph doesn't contain cycle of odd length. What is the time complexity of the best known algorithm to find out whether the graph is bipartite or not?

What is activity selection problem? Suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

Find the complexity of the below program:
void function(int n) { int i=1, s=1; while(s<=n) { i++; s+=i; printf("*"); } }

How many undirected graphs (not necessarily connected) can be constructed out of a given set $ V = \{V_1, V_2, \dots, V_n\} $ of n vertices?

The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is

Dijkstra's algorithm is based on

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

Name three sorting algorithms which are stable by nature.

What is the worst time complexity of insertion sort?

The most efficient algorithm for finding the number of connected components in an undirected graph of n vertices and m edges has the time complexity

Which of the following statement is not true about breadth-first search (BFS) in an undirected graph starting at a vertex v?

Finding the location of the element with a given value is

Write the asymptomatic notation used for best case, average case and worst case analysis of algorithm. Write an algorithm for finding maximum element in an array. Give best, worst and average case complexities.

Explain the brute force method to find the two closet points in a set of n points in k-dimensional space.

Explain the working of merge sort algorithm with an example. Give the complexity calculation of merge sort.

Write an algorithm based on divide-and-conquer strategy to search an element in a given list. Assume that the elements of list are in sorted order.

What is the relationship among P, NP and NP-complete problems? Show with the help of a diagram.

Give the complete solution (step-by-step using state space tree) for N-Queen problem using back-tracking with pseudocode. Give the complexity analysis.

Construct the Huffman coding tree for the text of characters with given frequencies: T:43, I:38, V:16, K:8, L:56, E:12, O:41, Z:13, P:22, R:6. Also find the variable length Huffman codes and frequency path length for corresponding above characters.

Find the optimal way to multiply the following matrices to perform the fewest multiplications:
$ A_1: 5 \times 11 $, $ A_2: 11 \times 4 $, $ A_3: 4 \times 15 $, $ A_4: 15 \times 23 $

Find the complexity of the below program:
void function(int n) { int i=1, s=1; while(s<=n) { i++; s+=i; printf("*"); } }

How many undirected graphs (not necessarily connected) can be constructed out of a given set $ V = \\{V_1, V_2, \dots, V_n\\} $ of n vertices?

The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is

Dijkstra's algorithm is based on

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

Name three sorting algorithms which are stable by nature.

What is the worst time complexity of insertion sort?

The most efficient algorithm for finding the number of connected components in an undirected graph of n vertices and m edges has the time complexity

Which of the following statement is not true about breadth-first search (BFS) in an undirected graph starting at a vertex v?

Finding the location of the element with a given value is

Write the asymptomatic notation used for best case, average case and worst case analysis of algorithm. Write an algorithm for finding maximum element in an array. Give best, worst and average case complexities.

Explain the brute force method to find the two closet points in a set of n points in k-dimensional space.

Explain the working of merge sort algorithm with an example. Give the complexity calculation of merge sort.

Write an algorithm based on divide-and-conquer strategy to search an element in a given list. Assume that the elements of list are in sorted order.

What is the relationship among P, NP and NP-complete problems? Show with the help of a diagram.

Give the complete solution (step-by-step using state space tree) for N-Queen problem using back-tracking with pseudocode. Give the complexity analysis.

Construct the Huffman coding tree for the text of characters with given frequencies: T:43, I:38, V:16, K:8, L:56, E:12, O:41, Z:13, P:22, R:6. Also find the variable length Huffman codes and frequency path length for corresponding above characters.

Find the optimal way to multiply the following matrices to perform the fewest multiplications:
$ A_1: 5 \times 11 $, $ A_2: 11 \times 4 $, $ A_3: 4 \times 15 $, $ A_4: 15 \times 23 $

In the following C++ function, let $ n \ge m $. What is the time complexity of the above function assuming $ n > m $?
int gcd(int n, int m) { if(n%m==0) return m; if(n < m) swap(n, m); while(m>0) { n=n%m; swap(n, m); } return n; }

Time complexity of Kadane's Algorithm is

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?

Any decision tree that sorts 'n' elements has height

An all-pairs shortest-paths problem is efficiently solved using

Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

Which of the following is true about Huffman Coding?

Which one of the following is an application of Queue Data Structure?

In linear search algorithm the worst case occurs when

The complexity of binary search algorithm is

Discuss the steps in mathematical analysis for recursive algorithm. Do the same for finding the factorial of a number?

What are the rules of manipulate Big-Oh expression? Write about the typical growth rates of algorithms.

What are the advantages of merge-sort over the quick-sort algorithm?

What is the time complexity of the matrix multiplication and Strassen's algorithm?

Prove that if $ f_1(n) = O(g_1(n)) $ and $ f_2(n) = O(g_2(n)) $, then $ f_1(n)+f_2(n) = O(g_1(n)+g_2(n)) $.

What is the relationship among P, NP and NP complete problems? Show with the help of a diagram.

Compare the various programming paradigms such as divide-and-conquer, dynamic programming and greedy approach.

Consider the array A = {26, 17, 41, 14, 21, 30, 47, 10, 16, 19, 21, 28, 38, 7, 12, 14, 20, 35, 39, 3}. Create binary search tree with one more attributes its size of node. Retrieve 17th smallest element in the tree and rank the 12th element.

What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider a graph $ G=(V,E) $ and find the minimum spanning tree by Prim's algorithms.

Explain back-tracking, DFS and BFS with help of small example. Differentiate in between backtracking and dynamic programming. Apply the backtracking algorithm to solve the three-colouring problem for the graph using state space tree. Assume three colours red, green and blue.

In the following C++ function, let $ n \ge m $. What is the time complexity of the above function assuming $ n > m $?
int gcd(int n, int m) { if(n%m==0) return m; if(n < m) swap(n, m); while(m>0) { n=n%m; swap(n, m); } return n; }

Time complexity of Kadane's Algorithm is

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?

Any decision tree that sorts 'n' elements has height

An all-pairs shortest-paths problem is efficiently solved using

Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

Which of the following is true about Huffman Coding?

Which one of the following is an application of Queue Data Structure?

In linear search algorithm the worst case occurs when

The complexity of binary search algorithm is

Discuss the steps in mathematical analysis for recursive algorithm. Do the same for finding the factorial of a number?

What are the rules of manipulate Big-Oh expression? Write about the typical growth rates of algorithms.

What are the advantages of merge-sort over the quick-sort algorithm?

What is the time complexity of the matrix multiplication and Strassen's algorithm?

Prove that if $ f_1(n) = O(g_1(n)) $ and $ f_2(n) = O(g_2(n)) $, then $ f_1(n)+f_2(n) = O(g_1(n)+g_2(n)) $.

What is the relationship among P, NP and NP complete problems? Show with the help of a diagram.

Compare the various programming paradigms such as divide-and-conquer, dynamic programming and greedy approach.

Consider the array A = {26, 17, 41, 14, 21, 30, 47, 10, 16, 19, 21, 28, 38, 7, 12, 14, 20, 35, 39, 3}. Create binary search tree with one more attributes its size of node. Retrieve 17th smallest element in the tree and rank the 12th element.

What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider a graph $ G=(V,E) $ and find the minimum spanning tree by Prim's algorithms.

Explain back-tracking, DFS and BFS with help of small example. Differentiate in between backtracking and dynamic programming. Apply the backtracking algorithm to solve the three-colouring problem for the graph using state space tree. Assume three colours red, green and blue.

Which algorithm is better for sorting between bubble sort and quicksort?

An algorithm which uses the past results and uses them to find the new results is

Out of the following which property of algorithm does not share?

Which of the following standard algorithms is not a greedy algorithm?

What is the time complexity of Huffman coding?

How many comparisons are required to sort the list 1, 2, 3... n using insertion sort?

Which of the following is true about Huffman coding?

A complexity of algorithm depends upon

A text is made up of the characters a, b, c, d, e each occurring with the probability 0.11, 0.40, 0.16, 0.09 and 0.24 respectively. The optimal Huffman coding technique will have the average length of

Build heap is used in heap sort as a first step for sorting. What is the time complexity of build heap operation?

Solve the following recurrence by successive substitution method:
$ f(1) = 1 $, if $ n=1 $
$ f(n) = 3f(n/2) + 6 $, if $ n>1 $

COUNTING SORT algorithm assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When $ k=O(n) $, the sort runs in $ \Theta(n) $ time. Change COUNTING SORT algorithm for the numbers lying in the range p to q where $ (q-p) $ is still $ O(n) $. Also analyze the new complexity.

Consider a directed acyclic graph with non-negative edge costs and with a given start vertex s. Write an algorithm to compute distances from source s in $ O(E+V) $ time. Justify why your algorithm is correct.

Explain, with an example, why Dijkstra's algorithm might take $ \Omega(V \log V) $ time.

Consider the two standard representations of directed graphs: the adjacency-list representation and the adjacency-matrix representation. Find a problem that can be solved more efficiently in the adjacency-list representation than in the adjacency-matrix representation, and another problem that can be solved more efficiently in the adjacency-matrix representation than in the adjacency-list representation.

Differentiate between the following: Fractional Knapsack vs. 0/1 Knapsack.

Differentiate between the following: Kruskal's vs. Prim's Algorithm.

What are NP-complete problems? Write some problems which are P, NP and NP-hard. Explain any NP-hard problem in detail.

Explain quicksort and its asymptotic complexities. Take some distinct numbers and perform quicksort over it.

Explain travelling salesman problem using Greedy method.

Explain travelling salesman problem using Dynamic programming method.

Which algorithm is better for sorting between bubble sort and quicksort?

An algorithm which uses the past results and uses them to find the new results is

Out of the following which property of algorithm does not share?

Which of the following standard algorithms is not a greedy algorithm?

What is the time complexity of Huffman coding?

How many comparisons are required to sort the list 1, 2, 3... n using insertion sort?

Which of the following is true about Huffman coding?

A complexity of algorithm depends upon

A text is made up of the characters a, b, c, d, e each occurring with the probability 0.11, 0.40, 0.16, 0.09 and 0.24 respectively. The optimal Huffman coding technique will have the average length of

Build heap is used in heap sort as a first step for sorting. What is the time complexity of build heap operation?

Solve the following recurrence by successive substitution method:
$ f(1) = 1 $, if $ n=1 $
$ f(n) = 3f(n/2) + 6 $, if $ n>1 $

COUNTING SORT algorithm assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When $ k=O(n) $, the sort runs in $ \Theta(n) $ time. Change COUNTING SORT algorithm for the numbers lying in the range p to q where $ (q-p) $ is still $ O(n) $. Also analyze the new complexity.

Consider a directed acyclic graph with non-negative edge costs and with a given start vertex s. Write an algorithm to compute distances from source s in $ O(E+V) $ time. Justify why your algorithm is correct.

Explain, with an example, why Dijkstra's algorithm might take $ \Omega(V \log V) $ time.

Consider the two standard representations of directed graphs: the adjacency-list representation and the adjacency-matrix representation. Find a problem that can be solved more efficiently in the adjacency-list representation than in the adjacency-matrix representation, and another problem that can be solved more efficiently in the adjacency-matrix representation than in the adjacency-list representation.

Differentiate between the following: Fractional Knapsack vs. 0/1 Knapsack.

Differentiate between the following: Kruskal's vs. Prim's Algorithm.

What are NP-complete problems? Write some problems which are P, NP and NP-hard. Explain any NP-hard problem in detail.

Explain quicksort and its asymptotic complexities. Take some distinct numbers and perform quicksort over it.

Explain travelling salesman problem using Greedy method.

Explain travelling salesman problem using Dynamic programming method.