**Question No: 1 (Marks: 01) – Please choose the correct option**

Matrix chain multiplication is a/an___________ type of problem.

- Search Problem
- Computational Problem
- Optimization Problem
- Parallel Computation Problem

Question No: 2 (Marks: 01) – Please choose the correct option

Dynamic Programming Algorithms involves solving the problem by________.

- Breaking up into sub-problems
- Only One Individual problem
- One Part of problem
- Starting from the first part of problem

**Question No: 3 (Marks: 01) – Please choose the correct option**

Matrix chain multiplication is a/an___________ type of problem.

- Search Problem
- Computational Problem
- Optimization Problem
- Parallel Computation Problem

__Question No: 4 (Marks: 01) – Please choose the correct option__

The Knapsack problem is an example of ____________.

a) Greedy algorithm

b) 2 D dynamic programming

c) 1 D dynamic programming

d) Divide and conquer

**Similar Posts:**

__Question No: 5 (Marks: 01) – Please choose the correct option__

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

a) 160

b) 200

c) 170

d) 90

__Question No: 6 (Marks: 01) – Please choose the correct option__

Which of the following algorithms is the best approach for solving Huffman codes?

a) exhaustive search

b) greedy algorithm

c) brute force algorithm

d) divide and conquer algorithm

__Question No: 7 (Marks: 01) – Please choose the correct option__

From the following given tree, what is the computed codeword for ‘c’?

a) 111

b) 101

c) 110

d) 011

__Question No: 8 (Marks: 01) – Please choose the correct option__

Fractional knapsack problem is solved most efficiently by which of the following algorithm?

a) Divide and conquer

b) Dynamic programming

c) Greedy algorithm

d) Backtracking

__Question No: 9 (Marks: 01) – Please choose the correct option__

The main time taking step in fractional knapsack problem is ___________.

a) Breaking items into fraction

b) Adding items into knapsack

c) Sorting

d) Looping through sorted items

__Question No: 10 (Marks: 01) – Please choose the correct option__

Which bit is reserved as a parity bit in an ASCII set?

a) first

b) seventh

c) eighth

d) tenth

__Question No: 11 (Marks: 01) – Please choose the correct option__

What does the Activity Selection Problem mean__________?

- Scheduling Problem
- Search Problem
- Computational Problem
- Non Computational Problem

__Question No: 12 (Marks: 01) – Please choose the correct option__

You are given infinite coins of denominations v1, v2, v3,…..,v_{n} and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________.

a) Greedy algorithm

b) Dynamic programming

c) Divide and conquer

d) Backtracking

__Question No: 13 (Marks: 01) – Please choose the correct option__

You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?

a) O(N)

b) O(S)

c) O(N2)

d) O(S*N)

__Question No: 14 (Marks: 01) – Please choose the correct option__

What is the fractional knapsack problem?

- A problem in computer science that deals with sorting algorithms
- A problem in mathematics that deals with dividing a line segment into a given number of equal parts
- A problem in optimization that deals with selecting items to include in a knapsack so as to maximize the total value of items in the knapsack
- A problem in physics that deals with calculating the force exerted by a gas on a container

__Question No: 15 (Marks: 01) – Please choose the correct option__

What is the objective of the fractional knapsack problem?

- To find the minimum weight of items that can be selected to fill the knapsack
- To find the maximum weight of items that can be selected to fill the knapsack
- To find the minimum value of items that can be selected to fill the knapsack
- To find the maximum value of items that can be selected to fill the knapsack

__Question No: 16 (Marks: 01) – Please choose the correct option__

What is the key difference between the 0/1 knapsack problem and the fractional knapsack problem?

- The 0/1 knapsack problem allows items to be broken into parts, while the fractional knapsack problem does not
- The 0/1 knapsack problem requires items to be taken in their entirety, while the fractional knapsack problem allows items to be taken in fractional amounts
- The 0/1 knapsack problem only allows items to be taken in whole numbers, while the fractional knapsack problem allows items to be taken in any amount
- The 0/1 knapsack problem is much easier to solve than the fractional knapsack problem

__Question No: 17 (Marks: 01) – Please choose the correct option__

A free tree does not have _______________ node/vertex.

- Root
- Left child
- Right child
- Leaf

__Question No: 18 (Marks: 01) – Please choose the correct option__

The number of edges in a Minimum Spanning Tree (MST) is _____________ the number of edges in the original graph.

- Greater than
- Less than or greater than
- Subset of
- Equal to

__Question No: 19 (Marks: 01) – Please choose the correct option__

The number of vertices in a Minimum Spanning Tree (MST) is _____________ the number of vertices in the original graph.

- Less than
- Greater than
- Subset of
- Equal to

__Question No: 20 (Marks: 01) – Please choose the correct option__

Kruskal’s algorithm is used for computing Minimum Spanning Tree (MST) and is based on ____________ strategy.

- Dynamic Programming
- Greedy
- Divide and Conquer
- Backtracking

__Question No: 21 (Marks: 01) – Please choose the correct option__

The Time complexity of Prim’s algorithm is ________________.

- Θ (logE + logV)
- Θ (log E V)
- Θ (E log V)
- Θ (log E+V)

__Question No: 22 (Marks: 01) – Please choose the correct option__

Dijkstra’s algorithm is used to compute ___________________ in a directed graph.

- Single-source shortest paths
- Single destination shortest paths
- Single-pair shortest paths
- All-pairs shortest paths

__Question No: 23 (Marks: 01) – Please choose the correct option__

The Dijkstra algorithm maintains estimate of the shortest path from source vertex to ____________

- Destination vertex
- Neighbor vertex
- Neighbor of the neighbor vertex
- All vertices in the graph

__ Question No: 24 (Marks: 01) – Please choose the correct option__

In Dijkstra algorithm the estimate of source vertex (i.e. s) is represented by d[s] and its value is ____________

- Equal to zero
- Greater than zero
- Less than zero
- Equal to one

__Question No: 25 (Marks: 01) – Please choose the correct option__

If a shortest paths algorithm allow negative cost cycle, then the algorithm will compute

- Multiple paths between pair of vertices
- Only one Path between pair of vertices
- Incorrect path between pair of vertices
- No Path between pair of vertices

__Question No: 26 (Marks: 01) – Please choose the correct option__

Which algorithm does not allow negative weights while computing the shortest paths in a directed graph?

- Dijkstra’s algorithm
- Floyd-Warshall Algorithm
- Bellman Ford
- Johnson

__Question No: 27 (Marks: 01) – Please choose the correct option__

The Time complexity of Bellman-Ford’ algorithm is ________________.

- Θ (logE + logV)
- Θ (log E V)
- Θ (E V)
- Θ (E+V)

__Question No: 28 (Marks: 01) – Please choose the correct option__

Floyd Warshall algorithm is used to compute _________________________ in a graph.

- Single-source shortest paths
- Single destination shortest paths
- Single-pair shortest paths
- All-pairs shortest paths

__Question No: 29 (Marks: 01) – Please choose the correct option__

Which one among the following is the slowest algorithm for computing shortest paths?

- Dijkstra’s algorithm
- Floyd-Warshall Algorithm
- Bellman Ford
- Prims

__Question No: 30 (Marks: 01) – Please choose the correct option__

Floyd Warshall’s algorithm is used for computing shortest paths and is based on ____________ strategy.

- Dynamic Programming
- Greedy
- Divide and Conquer
- Backtracking

__Question No: 31 (Marks: 01) – Please choose the correct option__

Which bit is reserved as a parity bit in an ASCII set?

a) first

b) seventh

c) eighth

d) tenth

__Question No: 32 (Marks: 01) – Please choose the correct option__

What is an adjacency list?

- A list of nodes and their edges in a graph
- A list of nodes in a graph, without any edges
- A list of edges in a graph, without any nodes
- A list of nodes in a graph, with their edges represented as a matrix

__Question No: 33 (Marks: 01) – Please choose the correct option__

What is an adjacency matrix used for in graph theory?

- To represent the distances between nodes
- To represent the edges between nodes
- To represent the weights of nodes
- To represent the orientation of nodes

__Question No: 34 (Marks: 01) – Please choose the correct option__

Which of the following best describes Breadth First Search (BFS)?

- BFS is a search algorithm that starts at the root node and visits all the nodes along the shortest path first, before visiting the more distant nodes.
- BFS is a search algorithm that visits all the nodes at the same depth before moving on to the next level.
- BFS is a search algorithm that visits nodes in a random order.
- BFS is a search algorithm that visits all the nodes in the order they were added to the tree.

__Question No: 35 (Marks: 01) – Please choose the correct option__

Which of the following best describes Depth First Search (DFS)?

- DFS is a search algorithm that starts at the root node and visits all the nodes along the shortest path first, before visiting the more distant nodes.
- DFS is a search algorithm that visits all the nodes at the same depth before moving on to the next level.
- DFS is a search algorithm that visits nodes in a random order.
- DFS is a search algorithm that visits all the nodes by exploring as far as possible along each branch before backtracking.

__Question No: 36 (Marks: 01) – Please choose the correct option__

What is the characteristic feature of Breadth First Search (BFS)?

- Visits all nodes along the shortest path first
- Visits all nodes at the same depth before moving to the next level
- Visits nodes in a random order
- Visits all the nodes in the order they were added to the tree

__Question No: 37 (Marks: 01) – Please choose the correct option__

What is a Directed Acyclic Graph (DAG)?

- A graph with directed edges and cycles
- A graph with directed edges and no cycles
- A graph with undirected edges and cycles
- A graph with undirected edges and no cycles

__Question No: 38 (Marks: 01) – Please choose the correct option__

What is the time stamp structure used in Depth First Search (DFS)?

- Inorder traversal time stamp
- Preorder traversal time stamp
- Postorder traversal time stamp
- Level-order traversal time stamp

__Question No: 39 (Marks: 01) – Please choose the correct option__

What is the characteristic feature of Depth First Search (DFS)?

- Visits all nodes along the shortest path first
- Visits all nodes at the same depth before moving to the next level
- Visits nodes in a random order
- Visits all the nodes by exploring as far as possible along each branch before backtracking

__Question No: 40 (Marks: 01) – Please choose the correct option__

What is the main property of a Directed Acyclic Graph (DAG)?

- The edges are undirected
- There are cycles present in the graph
- The edges are directed and there are no cycles present in the graph
- There is a unique path between any two vertices in the graph

**Question No: 41 (Marks: 03)**

Consider the case of 3 matrices: A1 is 5 × 4, A2 is 4 × 6 and A3 is 6 × 2 The multiplication can be carried out either as ((A1A2)A3) or (A1(A2A3)). Calculate the cost of these two matrices.

**Answer**

**Question No: 42 (Marks: 03)**

Write down at least three real life applications of Minimum Spanning Tree (MST).

**___________________________________________________________**

**Answer**

**Question No: 43 (Marks: 03)**

**__________________________________________________________**

Identify algorithms from the following list which compute the Minimum Spanning Tree (MST) in an undirected Graph.

Dijkstra

Prim

Bellman Ford

Kruskal

Floyd Warshall

**Answer**

**Question No: 44 (Marks: 03)**

**___________________________________________________________**

What makes Directed Acyclic Graphs (DAGs) a useful data structure for representing hierarchical relationships and relationships between events?

**Answer**

**Question No: 45 (Marks: 03)**

**___________________________________________________________**

How does the fractional Knapsack algorithm differ from the 0/1 Knapsack algorithm, and how can it be used to solve problems with continuous or fractional values.

**Answer**

**Question No: 46 (Marks: 03)**

**___________________________________________________________**

What is an adjacency matrix and how is it used to represent the connections between vertices in a graph?

**Answer**

**Question No: 47 (Marks: 05)**

**___________________________________________________________**

Consider the following graph and construct its Minimum Spanning Tree (MST) using Kruskal’s algorithm.

**Answer**

**Question No: 48 (Marks: 05)**

**___________________________________________________________**

Suppose you are given a map of a city with different locations and roads connecting them. How would you use the Breadth-First Search (BFS) algorithm to find the shortest route between two specific locations in the city?

**Answer**

**Question No: 49 (Marks: 05)**

**___________________________________________________________**

What is the time stamp structure used in Depth-First Search (DFS) algorithm, and how does it help in identifying different types of edges in a graph, such as tree edges, back edges, forward edges, and cross edges?

**Answer**

**Question No: 50 (Marks: 05)**

**___________________________________________________________**

Generate the Huffman binary tree for the string baadebbc based on the following frequency table.

Character | a | b | c | d | e |

Frequency | 2 | 3 | 1 | 1 | 1 |