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,…..,vn 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 |
