2023 105402

End Semester Examination - 2023

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (Any seven question only):

Q1.1

The fractional Knapsack problem can be solved by using

a)

Greedy method

b)

Divided and conquer method

c)

Dynamic programming

d)

None of these

Q1.2

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

a)

$O(|V|+|E|)$

b)

$O(|V|)$

c)

$O(|E|)$

d)

None of the above

Q1.3

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

a)

2

b)

3

c)

4

d)

1

Q1.4

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

a)

$O(n)$

b)

$O(n^2)$

c)

$O(\log_2 n)$

d)

$O(n^3)$

Q1.5

Travelling salesman problem belongs to

a)

P class

b)

NP class

c)

NP- hard

d)

NP- complete class

Q1.6

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

a)

Edges, vertex

b)

Vertex, edges

c)

Edges, edges

d)

Vertex, vertex

Q1.7

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

a)

Depth first search

b)

Breadth first search

c)

Pre-order traversal

d)

In-order traversal

Q1.8

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

a)

$f(n) \times g(n)$

b)

$\max(f(n), g(n))$

c)

$\min(f(n), g(n))$

d)

$f(n)+g(n)$

Q1.9

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

a)

Dijkstra's shortest path algorithm

b)

Kruskal algorithm

c)

Bellman ford shortest path algorithm

d)

Prim's algorithm

Q1.10

The node removal of which makes a graph disconnected is called

a)

Pendant vertex

b)

Bridge

c)

Articulation point

d)

Coloured vertex

Q.2 Solve both questions :

Q2.1

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

Q2.2

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

Q.3 Solve both questions :

Q3.1

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.

Q3.2

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

Q.4 Solve both questions :

Q4.1

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

Q4.2

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

Q.5 Solve both questions :

Q5.1

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) $

Q5.2

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

Q.6 Solve both questions :

Q6.1

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

Q6.2

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

Q.7 Solve both questions :

Q7.1

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

Q7.2

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

Q.8 Solve all questions :

Q8.1

Define the classes P and NP.

Q8.2

Discuss what you mean by polynomial reduction.

Q8.3

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

Q8.4

Describe Clique Decision Problem (CDP).

Q8.5

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

Q.9 Write short notes on any two of the following:

Q9.1

a)

Asymptotic notations

b)

Heap creation technique

c)

Strassen's matrix multiplication

d)

Divide-and-Conquer vs Dynamic programming

2023 V2 105402

End Semester Examination - 2023

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (Any seven question only):

Q1.1

The fractional Knapsack problem can be solved by using

a)

Greedy method

b)

Divided and conquer method

c)

Dynamic programming

d)

None of these

Q1.2

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

a)

$O(|V|+|E|)$

b)

$O(|V|)$

c)

$O(|E|)$

d)

None of the above

Q1.3

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

a)

2

b)

3

c)

4

d)

1

Q1.4

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

a)

$O(n)$

b)

$O(n^2)$

c)

$O(\log_2 n)$

d)

$O(n^3)$

Q1.5

Travelling salesman problem belongs to

a)

P class

b)

NP class

c)

NP- hard

d)

NP- complete class

Q1.6

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

a)

Edges, vertex

b)

Vertex, edges

c)

Edges, edges

d)

Vertex, vertex

Q1.7

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

a)

Depth first search

b)

Breadth first search

c)

Pre-order traversal

d)

In-order traversal

Q1.8

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

a)

$f(n) \times g(n)$

b)

$\max(f(n), g(n))$

c)

$\min(f(n), g(n))$

d)

$f(n)+g(n)$

Q1.9

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

a)

Dijkstra's shortest path algorithm

b)

Kruskal algorithm

c)

Bellman ford shortest path algorithm

d)

Prim's algorithm

Q1.10

The node removal of which makes a graph disconnected is called

a)

Pendant vertex

b)

Bridge

c)

Articulation point

d)

Coloured vertex

Q.2 Solve both questions :

Q2.1

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

Q2.2

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

Q.3 Solve both questions :

Q3.1

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.

Q3.2

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

Q.4 Solve both questions :

Q4.1

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

Q4.2

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

Q.5 Solve both questions :

Q5.1

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) $

Q5.2

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

Q.6 Solve both questions :

Q6.1

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

Q6.2

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

Q.7 Solve both questions :

Q7.1

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

Q7.2

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

Q.8 Solve all questions :

Q8.1

Define the classes P and NP.

Q8.2

Discuss what you mean by polynomial reduction.

Q8.3

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

Q8.4

Describe Clique Decision Problem (CDP).

Q8.5

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

Q.9 Write short notes on any two of the following:

Q9.1

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

a)

Asymptotic notations

b)

Heap creation technique

c)

Strassen's matrix multiplication

d)

Divide-and-Conquer vs Dynamic programming

2022 105402

B.Tech 4th Semester Exam., 2022

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven) :

Q1.1

Any decision trees that sorts elements has height

a)

$\Omega(\lg n)$

b)

$\Omega(n)$

c)

$\Omega(n \lg n)$

d)

$\Omega(n^2)$

Q1.2

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

a)

When a resource is shared among multiple consumers

b)

When data is transferred asynchronously between two processes

c)

Load balancing

d)

All of the above

Q1.3

The complexity of binary search algorithm is

a)

$O(n)$

b)

$O(\log n)$

c)

$O(n^2)$

d)

$O(n \log n)$

Q1.4

In linear search algorithm the worst case occurs when

a)

the item is somewhere in the middle of the array

b)

the item is not in the array at all

c)

the item is the last element in the array

d)

the item is the last element in the array or is not there at all

Q1.5

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?

a)

Insertion sort with time complexity $O(kn)$

b)

Heap sort with time complexity $O(n \log k)$

c)

Quick sort with time complexity $O(k \log k)$

d)

Merge sort with time complexity $O(k \log k)$

Q1.6

Approach of dynamic programming is similar to

a)

parsing

b)

hash table

c)

divide and conquer algorithm

d)

greedy algorithm

Q1.7

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

a)

divide/break

b)

sorting/divide

c)

conquer/solve

d)

merge/combine

Q1.8

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

a)

10, 8, 7, 5, 3, 2, 1

b)

10, 8, 7, 2, 3, 1, 5

c)

10, 8, 7, 1, 2, 3, 5

d)

10, 8, 7, 3, 2, 1, 5

Q1.9

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

a)

dynamic programming

b)

greedy

c)

divide and conquer

d)

recursion

Q1.10

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

a)

computational complexity

b)

time complexity

c)

problem complexity

d)

decision complexity

Q.2 Solve both questions :

Q2.1

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 $

Q2.2

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"); }
}

Q.3 Solve both questions :

Q3.1

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

Q3.2

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

Q.4 Solve both questions :

Q4.1

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

Q4.2

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

Q.5 Solve this question :

Q5.1

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.

Q.6 Solve this question :

Q6.1

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 $

Q.7 Solve this question :

Q7.1

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?

Q.8 Solve this question :

Q8.1

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.

Q.9 Write short notes on the following:

Q9.1

a)

Cook's theorem

b)

Approximation algorithms

2022 V4 105402

B.Tech 4th Semester Exam., 2022

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven) :

Q1.1

Any decision trees that sorts elements has height

a)

$\Omega(\lg n)$

b)

$\Omega(n)$

c)

$\Omega(n \lg n)$

d)

$\Omega(n^2)$

Q1.2

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

a)

When a resource is shared among multiple consumers

b)

When data is transferred asynchronously between two processes

c)

Load balancing

d)

All of the above

Q1.3

The complexity of binary search algorithm is

a)

$O(n)$

b)

$O(\log n)$

c)

$O(n^2)$

d)

$O(n \log n)$

Q1.4

In linear search algorithm the worst case occurs when

a)

the item is somewhere in the middle of the array

b)

the item is not in the array at all

c)

the item is the last element in the array

d)

the item is the last element in the array or is not there at all

Q1.5

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?

a)

Insertion sort with time complexity $O(kn)$

b)

Heap sort with time complexity $O(n \log k)$

c)

Quick sort with time complexity $O(k \log k)$

d)

Merge sort with time complexity $O(k \log k)$

Q1.6

Approach of dynamic programming is similar to

a)

parsing

b)

hash table

c)

divide and conquer algorithm

d)

greedy algorithm

Q1.7

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

a)

divide/break

b)

sorting/divide

c)

conquer/solve

d)

merge/combine

Q1.8

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

a)

10, 8, 7, 5, 3, 2, 1

b)

10, 8, 7, 2, 3, 1, 5

c)

10, 8, 7, 1, 2, 3, 5

d)

10, 8, 7, 3, 2, 1, 5

Q1.9

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

a)

dynamic programming

b)

greedy

c)

divide and conquer

d)

recursion

Q1.10

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

a)

computational complexity

b)

time complexity

c)

problem complexity

d)

decision complexity

Q.2 Solve both questions :

Q2.1

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 $

Q2.2

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"); }
}

Q.3 Solve both questions :

Q3.1

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

Q3.2

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

Q.4 Solve both questions :

Q4.1

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

Q4.2

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

Q.5 Solve this question :

Q5.1

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.

Q.6 Solve this question :

Q6.1

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 $

Q.7 Solve this question :

Q7.1

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?

Q.8 Solve this question :

Q8.1

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.

Q.9 Write short notes on the following:

2020 051506

B.Tech 5th Semester Special Exam., 2020

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are EIGHT questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

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

a)

$\Omega(n)$

b)

$O(\sqrt{n})$

c)

$\Theta(loglogn)$

d)

$\Theta(sqrt(n))$

Q1.2

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?

a)

$n(n-1)/2$

b)

$2^n$

c)

$n!$

d)

$2^{n(n-1)/2}$

Q1.3

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

a)

$T(n)=2T(n-2)+2$

b)

$T(n)=2T(n-1)+n$

c)

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

d)

$T(n)=2T(n-1)+1$

Q1.4

Dijkstra's algorithm is based on

a)

dynamic programming

b)

divide and conquer

c)

greedy programming

d)

None of the above

Q1.5

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?

a)

$O(n)$

b)

$O(n^2)$

c)

$O(n \log n)$

d)

$O(n!)$

Q1.6

Name three sorting algorithms which are stable by nature.

a)

Bubble sort, Insertion sort, Merge sort

b)

Bubble sort, Quick sort, Heap sort

c)

Insertion sort, Radix sort, Heap sort

d)

Count sort, Radix sort, Quick sort

Q1.7

What is the worst time complexity of insertion sort?

a)

$n \log n$

b)

$\log n$

c)

$n$

d)

$n^2$

Q1.8

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

a)

$O(n)$

b)

$O(m)$

c)

$O(m+n)$

d)

$O(mn)$

Q1.9

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

a)

BFS identifies all vertices reachable from v.

b)

Using an adjacency list instead of an adjacency matrix can improve the worst case complexity to $O(n+m)$ .

c)

BFS cannot be used to check for cycles in the graph.

d)

BFS can be used to identify the furthest vertex from v in any graph, in terms of number of nodes.

Q1.10

Finding the location of the element with a given value is

a)

traversal

b)

search

c)

sort

d)

None of the above

Q.2 Solve this question :

Q2.1

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.

Q.3 Solve both questions :

Q3.1

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

Q3.2

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

Q.4 Solve both questions :

Q4.1

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.

Q4.2

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

Q.5 Solve this question :

Q5.1

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

Q.6 Solve this question :

Q6.1

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.

Q.7 Solve this question :

Q7.1

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 $

Q.8 Write short notes on the following:

Q8.1

a)

Travelling salesman problem

b)

Activity selection problem

c)

Monte Carlo types

d)

Divide-and-Conquer vs. Dynamic programming

2020 SPECIAL 051506

B.Tech 5th Semester Special Exam., 2020

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are EIGHT questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

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

a)

$\Omega(n)$

b)

$O(\sqrt{n})$

c)

$\Theta(loglogn)$

d)

$\Theta(sqrt(n))$

Q1.2

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?

a)

$n(n-1)/2$

b)

$2^n$

c)

$n!$

d)

$2^{n(n-1)/2}$

Q1.3

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

a)

$T(n)=2T(n-2)+2$

b)

$T(n)=2T(n-1)+n$

c)

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

d)

$T(n)=2T(n-1)+1$

Q1.4

Dijkstra's algorithm is based on

a)

dynamic programming

b)

divide and conquer

c)

greedy programming

d)

None of the above

Q1.5

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?

a)

$O(n)$

b)

$O(n^2)$

c)

$O(n \log n)$

d)

$O(n!)$

Q1.6

Name three sorting algorithms which are stable by nature.

a)

Bubble sort, Insertion sort, Merge sort

b)

Bubble sort, Quick sort, Heap sort

c)

Insertion sort, Radix sort, Heap sort

d)

Count sort, Radix sort, Quick sort

Q1.7

What is the worst time complexity of insertion sort?

a)

$n \log n$

b)

$\log n$

c)

$n$

d)

$n^2$

Q1.8

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

a)

$O(n)$

b)

$O(m)$

c)

$O(m+n)$

d)

$O(mn)$

Q1.9

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

a)

BFS identifies all vertices reachable from v.

b)

Using an adjacency list instead of an adjacency matrix can improve the worst case complexity to $O(n+m)$ .

c)

BFS cannot be used to check for cycles in the graph.

d)

BFS can be used to identify the furthest vertex from v in any graph, in terms of number of nodes.

Q1.10

Finding the location of the element with a given value is

a)

traversal

b)

search

c)

sort

d)

None of the above

Q.2 Solve this question :

Q2.1

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.

Q.3 Solve both questions :

Q3.1

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

Q3.2

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

Q.4 Solve both questions :

Q4.1

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.

Q4.2

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

Q.5 Solve this question :

Q5.1

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

Q.6 Solve this question :

Q6.1

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.

Q.7 Solve this question :

Q7.1

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 $

Q.8 Write short notes on the following:

2019 051506

B.Tech 5th Semester Exam., 2019

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer from any seven of the following:

Q1.1

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; }

a)

$\Theta(\log n)$

b)

$\Omega(n)$

c)

$\Theta(loglogn)$

d)

$\Theta(sqrt(n))$

Q1.2

Time complexity of Kadane's Algorithm is

a)

$O(n)$

b)

$O(n^2)$

c)

$O(n \log n)$

d)

$O(n(\log n)^2)$

Q1.3

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?

a)

$1/8$

b)

$1$

c)

$7$

d)

$8$

Q1.4

Any decision tree that sorts 'n' elements has height

a)

$\Omega(\lg n)$

b)

$\Omega(n)$

c)

$\Omega(n \lg n)$

d)

$\Omega(n^2)$

Q1.5

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

a)

Dijkstra's algorithm

b)

Bellman-Ford algorithm

c)

Kruskal algorithm

d)

Floyd-Warshall algorithm

Q1.6

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

a)

In adjacency list representation, space is saved for sparse graphs.

b)

DFS and BFS can be done in $O(V+E)$ time for adjacency list representation.

c)

Adding a vertex in adjacency list representation is easier than adjacency matrix representation.

d)

All of the above

Q1.7

Which of the following is true about Huffman Coding?

a)

Huffman coding may become lossy in some cases.

b)

Huffman codes may not be optimal lossless codes in some cases.

c)

In Huffman coding, no code is prefix of any other code.

d)

All of the above

Q1.8

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

a)

When a resource is shared among multiple consumers

b)

When data is transferred asynchronously between two processes

c)

Load balancing

d)

All of the above

Q1.9

In linear search algorithm the worst case occurs when

a)

the item is somewhere in the middle of the array

b)

the item is not in the array at all

c)

the item is the last element in the array

d)

the item is the last element in the array or is not there at all

Q1.10

The complexity of binary search algorithm is

a)

$O(n)$

b)

$O(\log n)$

c)

$O(n^2)$

d)

$O(n \log n)$

Q.2 Solve both questions :

Q2.1

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

Q2.2

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

Q.3 Solve both questions :

Q3.1

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

Q3.2

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

Q.4 Solve both questions :

Q4.1

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)) $.

Q.5 Solve this question :

Q5.1

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

Q5.2

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

Q.6 Solve this question :

Q6.1

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.

Q.7 Solve this question :

Q7.1

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.

Q.8 Solve this question :

Q8.1

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.

Q.9 Write short notes on:

Q9.1

a)

Kruskal algorithms

b)

Branch and bound technique

c)

Amortized analysis

d)

Divide-N-Conquer VS Dynamic Programming

2019 V4 051506

B.Tech 5th Semester Exam., 2019

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer from any seven of the following:

Q1.1

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; }

a)

$\Theta(\log n)$

b)

$\Omega(n)$

c)

$\Theta(loglogn)$

d)

$\Theta(sqrt(n))$

Q1.2

Time complexity of Kadane's Algorithm is

a)

$O(n)$

b)

$O(n^2)$

c)

$O(n \log n)$

d)

$O(n(\log n)^2)$

Q1.3

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?

a)

$1/8$

b)

$1$

c)

$7$

d)

$8$

Q1.4

Any decision tree that sorts 'n' elements has height

a)

$\Omega(\lg n)$

b)

$\Omega(n)$

c)

$\Omega(n \lg n)$

d)

$\Omega(n^2)$

Q1.5

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

a)

Dijkstra's algorithm

b)

Bellman-Ford algorithm

c)

Kruskal algorithm

d)

Floyd-Warshall algorithm

Q1.6

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

a)

In adjacency list representation, space is saved for sparse graphs.

b)

DFS and BFS can be done in $O(V+E)$ time for adjacency list representation.

c)

Adding a vertex in adjacency list representation is easier than adjacency matrix representation.

d)

All of the above

Q1.7

Which of the following is true about Huffman Coding?

a)

Huffman coding may become lossy in some cases.

b)

Huffman codes may not be optimal lossless codes in some cases.

c)

In Huffman coding, no code is prefix of any other code.

d)

All of the above

Q1.8

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

a)

When a resource is shared among multiple consumers

b)

When data is transferred asynchronously between two processes

c)

Load balancing

d)

All of the above

Q1.9

In linear search algorithm the worst case occurs when

a)

the item is somewhere in the middle of the array

b)

the item is not in the array at all

c)

the item is the last element in the array

d)

the item is the last element in the array or is not there at all

Q1.10

The complexity of binary search algorithm is

a)

$O(n)$

b)

$O(\log n)$

c)

$O(n^2)$

d)

$O(n \log n)$

Q.2 Solve both questions :

Q2.1

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

Q2.2

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

Q.3 Solve both questions :

Q3.1

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

Q3.2

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

Q.4 Solve both questions :

Q4.1

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)) $.

Q.5 Solve this question :

Q5.1

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

Q5.2

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

Q.6 Solve this question :

Q6.1

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.

Q.7 Solve this question :

Q7.1

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.

Q.8 Solve this question :

Q8.1

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.

Q.9 Write short notes on:

2018 051506

B.Tech 5th Semester Exam., 2018

Time 03 Hours

Full Marks 70

Instructions:

All questions carry equal marks.
There are NINE questions in this paper.
Attempt any FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer (any seven):

Q1.1

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

a)

Bubble sort

b)

Quicksort

c)

Both are equally good

d)

These cannot be compared

Q1.2

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

a)

brute force

b)

divide and conquer

c)

dynamic programming algorithm

d)

None of the mentioned

Q1.3

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

a)

Input

b)

Finiteness

c)

Generality

d)

Constancy

Q1.4

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

a)

Dijkstra's shortest path algorithm

b)

Kruskal algorithm

c)

Bellmen Ford shortest path algorithm

d)

Prim's algorithm

Q1.5

What is the time complexity of Huffman coding?

a)

$O(N)$

b)

$O(N \log N)$

c)

$O(N(\log N)^2)$

d)

$O(N^2)$

Q1.6

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

a)

$(n^2+n+2)/2$

b)

$(n^3+n-2)/2$

c)

$(n^2+n-2)/2$

d)

$(n^2-n-2)/2$

Q1.7

Which of the following is true about Huffman coding?

a)

Huffman coding may become lossy in some cases

b)

Huffman codes may not be optimal lossless codes in some cases

c)

In Huffman coding, no code is prefix of any other code

d)

All of the above

Q1.8

A complexity of algorithm depends upon

a)

time only

b)

space only

c)

both time and space

d)

None of the mentioned

Q1.9

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

a)

2.40

b)

2.16

c)

2.26

d)

2.15

Q1.10

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

a)

$O(n \log n)$

b)

$O(n^2)$

c)

$O(\log n)$

d)

$O(n)$

Q.2 Solve this question :

Q2.1

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

Q.3 Solve this question :

Q3.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.

Q.4 Solve both questions :

Q4.1

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.

Q4.2

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

Q.5 Solve this question :

Q5.1

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.

Q.6 Solve both questions :

Q6.1

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

Q6.2

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

Q.7 Solve this question :

Q7.1

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

Q.8 Solve this question :

Q8.1

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

Q.9 Solve both questions :

Q9.1

Explain travelling salesman problem using Greedy method.

Q9.2

Explain travelling salesman problem using Dynamic programming method.

2018 V4 051506

B.Tech 5th Semester Exam., 2018

Time 03 Hours

Full Marks 70

Instructions:

All questions carry equal marks.
There are NINE questions in this paper.
Attempt any FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer (any seven):

Q1.1

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

a)

Bubble sort

b)

Quicksort

c)

Both are equally good

d)

These cannot be compared

Q1.2

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

a)

brute force

b)

divide and conquer

c)

dynamic programming algorithm

d)

None of the mentioned

Q1.3

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

a)

Input

b)

Finiteness

c)

Generality

d)

Constancy

Q1.4

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

a)

Dijkstra's shortest path algorithm

b)

Kruskal algorithm

c)

Bellmen Ford shortest path algorithm

d)

Prim's algorithm

Q1.5

What is the time complexity of Huffman coding?

a)

$O(N)$

b)

$O(N \log N)$

c)

$O(N(\log N)^2)$

d)

$O(N^2)$

Q1.6

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

a)

$(n^2+n+2)/2$

b)

$(n^3+n-2)/2$

c)

$(n^2+n-2)/2$

d)

$(n^2-n-2)/2$

Q1.7

Which of the following is true about Huffman coding?

a)

Huffman coding may become lossy in some cases

b)

Huffman codes may not be optimal lossless codes in some cases

c)

In Huffman coding, no code is prefix of any other code

d)

All of the above

Q1.8

A complexity of algorithm depends upon

a)

time only

b)

space only

c)

both time and space

d)

None of the mentioned

Q1.9

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

a)

2.40

b)

2.16

c)

2.26

d)

2.15

Q1.10

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

a)

$O(n \log n)$

b)

$O(n^2)$

c)

$O(\log n)$

d)

$O(n)$

Q.2 Solve this question :

Q2.1

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

Q.3 Solve this question :

Q3.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.

Q.4 Solve both questions :

Q4.1

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.

Q4.2

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

Q.5 Solve this question :

Q5.1

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.

Q.6 Solve both questions :

Q6.1

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

Q6.2

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

Q.7 Solve this question :

Q7.1

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

Q.8 Solve this question :

Q8.1

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

Q.9 Solve both questions :

Q9.1

Explain travelling salesman problem using Greedy method.

Q9.2

Explain travelling salesman problem using Dynamic programming method.