Bt0080 - Fundamentals Of Algorithms
A set of rules to be followed during calculations or other problem solving operations is what defines algorithm. Computational complexity for instance defines clearly the major concern of algorithm, which is efficiency, which involves how much time and memory required to solve problem. Bt0080 - Fundamentals of algorithms will help you understand what algorithm is all about.
- 1.
A process is a ………….. actually being carried out to solve a problem.
- A.
Sequence of activities
- B.
Step-by step procedure
- C.
Flow of information
- D.
Both b and c
Correct Answer
A. Sequence of activitiesExplanation
A process refers to a series of activities that are being carried out to solve a problem. It involves a step-by-step procedure and a flow of information. Therefore, the correct answer is "both b and c" as a sequence of activities encompasses both a step-by-step procedure and a flow of information.Rate this question:
-
- 2.
An algorithm must terminate after a finite number of steps is known as
- A.
Definiteness
- B.
Finiteness
- C.
Correctness
- D.
Effectiveness
Correct Answer
B. FinitenessExplanation
Finiteness refers to the property of an algorithm that ensures it will terminate after a finite number of steps. This means that the algorithm will eventually reach an end point and produce a result, rather than running indefinitely or getting stuck in an infinite loop. Finiteness is an essential characteristic of algorithms as it guarantees that they can be executed within a reasonable amount of time and resources.Rate this question:
-
- 3.
When the sequence of execution of instructions is to be the same as the sequence in which instruction are written in program text is known as ………..
- A.
Direct sequencing
- B.
Indirect sequencing
- C.
Direct selection
- D.
Indirect selection
Correct Answer
A. Direct sequencingExplanation
Direct sequencing refers to the execution of instructions in the same order as they are written in the program text. This means that the computer will execute each instruction one after the other, following the exact sequence specified by the programmer. This ensures that the program behaves as intended and produces the desired output. In contrast, indirect sequencing or indirect selection allows for conditional branching or jumping to different parts of the program based on certain conditions.Rate this question:
-
- 4.
Each of the floor function and ceiling function is a monotonically increasing function but not ……………..
- A.
Strictly monotonically increasing function
- B.
Monotonically decreasing function
- C.
Strictly monotonically decreasing function
- D.
Mod function
Correct Answer
A. Strictly monotonically increasing functionExplanation
The floor function and ceiling function are both monotonically increasing functions because as the input increases, the output either stays the same or increases. However, they are not strictly monotonically increasing functions because there are cases where the output remains the same even if the input increases. For example, the floor function of 2.5 is 2, and the floor function of 3.5 is also 2. Therefore, the correct answer is "strictly monotonically increasing function".Rate this question:
-
- 5.
………………….maps each real number x to the integer, which is the greatest of all integers less than or equal to
- A.
Ceiling function
- B.
Floor Function
- C.
Monotonically increasing function
- D.
Exponentiation Function
Correct Answer
B. Floor FunctionExplanation
The given correct answer is "Floor Function." The floor function maps each real number x to the integer, which is the greatest of all integers less than or equal to x. It rounds down the value of x to the nearest integer. For example, the floor of 3.7 is 3, the floor of -2.3 is -3, and the floor of 5 is 5. The floor function is a commonly used mathematical function that is often used in various fields including mathematics, computer science, and engineering.Rate this question:
-
- 6.
The concept of logarithm is defined indirectly by the definition of ……………
- A.
Exponential
- B.
Floor Function
- C.
Ceiling function
- D.
Monotonically increasing function
Correct Answer
A. ExponentialExplanation
The concept of logarithm is defined indirectly by the definition of exponential. Logarithm is the inverse operation of exponentiation. It represents the power to which a base must be raised to obtain a given number. Exponential functions have the form y = a^x, where a is a constant and x is the exponent. Logarithmic functions have the form y = log_a(x), where a is the base and x is the argument. The relationship between exponential and logarithmic functions is fundamental in mathematics and allows for solving equations involving exponents and finding the unknown exponent.Rate this question:
-
- 7.
- A.
A
- B.
B
- C.
C
- D.
D
Correct Answer
A. A -
- 8.
Merge sort is an example of
- A.
Divide and conquer
- B.
Decrease and conquer
- C.
Space and time tradeoff
- D.
Greedy method
Correct Answer
A. Divide and conquerExplanation
Merge sort is an example of the divide and conquer algorithmic technique. This technique involves breaking down a problem into smaller subproblems, solving them independently, and then combining the solutions to obtain the final result. In the case of merge sort, the algorithm divides the input array into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted output. This approach of dividing the problem into smaller subproblems and solving them individually before combining the results is the essence of the divide and conquer strategy.Rate this question:
-
- 9.
Before executing Merge Sort, the n elements should be placed in a [1:n].
- A.
[1:n]
- B.
[2n:n]
- C.
[1:2n]
- D.
[2:n]
Correct Answer
A. [1:n]Explanation
The given answer [1:n] is correct because in Merge Sort, the array is divided into smaller subarrays until each subarray contains only one element. Then, the subarrays are merged back together in a sorted manner. So, [1:n] represents the initial state of the array before any division or merging has occurred, indicating that all the elements are in their original order.Rate this question:
-
- 10.
A feasible solution that either maximizes or minimizes a given objective function is called an …………..
- A.
Optimal solution
- B.
Local solution
- C.
Exact solution
- D.
Correct solution correct solution correct solution
Correct Answer
A. Optimal solutionExplanation
An optimal solution refers to a feasible solution that either maximizes or minimizes a given objective function. It is the best possible solution among all feasible solutions and provides the highest or lowest value for the objective function, depending on whether it is a maximization or minimization problem. Therefore, the correct answer is "optimal solution."Rate this question:
-
- 11.
Knapsack Problem is an example of
- A.
Divide and conquer technique
- B.
Greedy technique
- C.
Decrease and conquer technique
- D.
Time and space tradeoff
Correct Answer
B. Greedy techniqueExplanation
The Knapsack Problem is an example of the greedy technique because it involves making locally optimal choices at each step in order to find the overall optimal solution. In this problem, we are given a set of items with different weights and values, and we need to determine the most valuable combination of items that can fit into a knapsack with a limited weight capacity. The greedy approach involves selecting the items with the highest value-to-weight ratio first, without considering the future consequences. This technique may not always provide the globally optimal solution, but it often yields good results in practice.Rate this question:
-
- 12.
In a graph, when does Dijkstra's algorithm stop?
- A.
When the shortest path to the destination vertex is found
- B.
When all the vertices in the graph are included to the path
- C.
When the vertices together form a cycle
- D.
When the minimum spanning tree is constructed
Correct Answer
A. When the shortest path to the destination vertex is foundExplanation
Dijkstra's algorithm stops when the shortest path to the destination vertex is found because the algorithm works by continuously updating the distances from the source vertex to all other vertices in the graph. It explores the neighboring vertices and chooses the one with the smallest distance as the next vertex to visit. This process continues until the algorithm reaches the destination vertex. Once the shortest path to the destination vertex is determined, there is no need to continue exploring other vertices, so the algorithm stops.Rate this question:
-
- 13.
The multistage graph problem can also be solved using the ……………….
- A.
Backward approach
- B.
Forward approach
- C.
Top down approach
- D.
Bottoms up approach
Correct Answer
A. Backward approachExplanation
The multistage graph problem can be solved using the backward approach. In this approach, we start from the last stage and move towards the first stage. At each stage, we calculate the optimal solution based on the solutions obtained from the next stage. This approach is useful when the optimal solution depends on future stages and allows us to efficiently solve problems with multiple stages.Rate this question:
-
- 14.
A multistage graph G = (V,E) is a ……………….
- A.
Undirected graph
- B.
Directed graph
- C.
Directed as well as undirected graph
- D.
Type of tree
Correct Answer
B. Directed grapHExplanation
A multistage graph is a directed graph where the vertices are divided into multiple stages and there are directed edges between the stages. In this type of graph, the edges only go from one stage to the next, indicating a specific direction of flow. Therefore, the correct answer is a directed graph.Rate this question:
-
- 15.
The all pairs shortest path problem is to determine a …………….such that A (i,j) is the length of a shortest path from i to j.
- A.
Matrix A
- B.
Array A
- C.
Graph A
- D.
Tree A
Correct Answer
A. Matrix AExplanation
The correct answer is matrix A. In the all pairs shortest path problem, the goal is to determine a matrix A where A(i,j) represents the length of the shortest path from vertex i to vertex j. This matrix allows us to easily access and compare the shortest path lengths for all pairs of vertices in the graph.Rate this question:
-
- 16.
All solutions to the 8-queens problem can be represented as ………………. where xi is the column on which queen i is placed.
- A.
8-tuples (x1…… x8),
- B.
12-tuples (x1…… x12),
- C.
16-tuples (x1…… x16),
- D.
4-tuples (x1…… x4),
Correct Answer
A. 8-tuples (x1…… x8),Explanation
The 8-queens problem involves placing 8 queens on an 8x8 chessboard such that no two queens threaten each other. Each solution to the problem can be represented as an 8-tuple (x1......x8), where xi represents the column on which queen i is placed. This means that each element in the tuple represents the column number of the corresponding queen. Therefore, the correct answer is 8-tuples (x1......x8).Rate this question:
-
- 17.
The estimated no. of unbounded nodes is only ………... of the total no of nodes in the 8 queen state space tree.
- A.
3.34%
- B.
2.34%
- C.
1%
- D.
4.34%
Correct Answer
B. 2.34%Explanation
The estimated number of unbounded nodes is only 2.34% of the total number of nodes in the 8 queen state space tree. This means that the majority of nodes in the state space tree are bounded, meaning they have a limited number of possible moves or solutions. The small percentage of unbounded nodes suggests that there are only a few nodes in the state space tree that have an infinite number of possible moves or solutions.Rate this question:
-
- 18.
Backtracking algorithms determine problem's solutions by …………………... searching the solution space for the given problem instance
- A.
Systematically
- B.
Logically
- C.
Periodically
- D.
Non- systematically
Correct Answer
A. SystematicallyExplanation
Backtracking algorithms determine problem's solutions by systematically searching the solution space for the given problem instance. This means that the algorithm explores all possible solutions in a structured and organized manner, considering each option and backtracking when necessary. The algorithm follows a systematic approach to find the solution, ensuring that all possible paths are explored and evaluated before reaching the final solution.Rate this question:
-
- 19.
In branch-and-bound terminology, a BFS-like state space search will be called ……….
- A.
FIFO
- B.
LIFO
- C.
LILO
- D.
FILO
Correct Answer
A. FIFOExplanation
In branch-and-bound terminology, a BFS-like state space search will be called FIFO. This is because BFS (breadth-first search) explores all the neighboring nodes of the current node before moving on to the next level of nodes. Similarly, in a FIFO (first-in, first-out) queue, the elements that are added first are the first ones to be removed. Therefore, a BFS-like state space search can be referred to as FIFO.Rate this question:
-
- 20.
A D-search-like state space search will be called ………….
- A.
FIFO
- B.
LIFO
- C.
FILO
- D.
LILO
Correct Answer
B. LIFOExplanation
A D-search-like state space search refers to a depth-first search algorithm, where the search explores a path as far as possible before backtracking. In this type of search, the last node that is discovered is the first one to be expanded. This follows the Last In, First Out (LIFO) principle, where the most recently added item is the first one to be removed. Therefore, LIFO is the correct answer for this question.Rate this question:
-
- 21.
To use the branch-and-bound technique to solve any problem, first, it is necessary to conceive of a …………... for the problem
- A.
State space tree
- B.
Binary search tree
- C.
Syntax tree
- D.
Flowchart
Correct Answer
A. State space treeExplanation
The branch-and-bound technique involves breaking down a problem into a state space tree, where each node represents a possible solution. By exploring different branches of the tree and bounding the search based on certain criteria, the technique efficiently narrows down the search space and finds an optimal solution. Therefore, the correct answer is "state space tree".Rate this question:
-
- 22.
If f(n) is the time for some algorithm, then we write f(n)=Ω(g(n)) to mean that g(n) is a …………. for f(n).
- A.
Lower bound
- B.
Upper bound
- C.
Space complexity
- D.
Average bound
Correct Answer
A. Lower boundExplanation
The notation f(n) = Ω(g(n)) means that g(n) is a lower bound for the time complexity of the algorithm represented by f(n). This means that the algorithm will take at least as much time as g(n) for any input size n. In other words, g(n) provides a lower limit on the time complexity of the algorithm.Rate this question:
-
- 23.
For many problems it is possible to easily observe that a lower bound ………………..to n exists where n is the number of input to the problem
- A.
Descendent
- B.
Identical
- C.
Differ
- D.
Local
Correct Answer
B. IdenticalExplanation
The word "identical" is the correct answer because it means "exactly the same" or "not different." In the given statement, it is mentioned that a lower bound exists for many problems, which implies that the lower bound is the same as the number of inputs to the problem (n). Therefore, the lower bound and n are identical or the same.Rate this question:
-
- 24.
Each internal node in binary tree represents a …………
- A.
Comparison
- B.
Differentiation
- C.
Multiplication
- D.
Division
Correct Answer
A. ComparisonExplanation
Each internal node in a binary tree represents a comparison. In a binary tree, each node has at most two children, a left child and a right child. The internal nodes are the nodes that have at least one child. These nodes are used to compare values and determine the direction in which the tree is traversed. The comparison can be based on various criteria such as the value of the node or any other attribute associated with it. Hence, the internal nodes in a binary tree represent a comparison.Rate this question:
-
- 25.
An edge having the same vertex as both its end vertices called a ……………
- A.
Self-loop
- B.
Open loop
- C.
Closed vertex
- D.
Open vertex Open vertex Open vertex
Correct Answer
A. Self-loopExplanation
A self-loop is an edge in a graph that connects a vertex to itself. In this case, the edge has the same vertex as both of its end vertices, making it a self-loop.Rate this question:
-
- 26.
A graph is also called a ………..
- A.
Linear complex
- B.
1 – complex
- C.
One-dimensional complex
- D.
Linear complex, or a 1 – complex, or a one-dimensional complex
Correct Answer
D. Linear complex, or a 1 – complex, or a one-dimensional complexExplanation
A graph is referred to as a linear complex, a 1 – complex, or a one-dimensional complex. These terms all describe the same concept, which is a graph that consists of a set of vertices and edges connecting the vertices in a linear or one-dimensional manner. This means that the graph can be represented as a straight line or a sequence of connected points.Rate this question:
-
- 27.
A circuit is a closed, ………….. walk
- A.
Nonintersecting
- B.
Intersecting
- C.
Crossed
- D.
Easy
Correct Answer
A. NonintersectingExplanation
A circuit is a closed path that starts and ends at the same point. In this context, "nonintersecting" means that the path of the circuit does not cross or intersect with itself at any point. This is the correct answer because a circuit must be nonintersecting in order to be considered a valid closed path.Rate this question:
-
- 28.
A collection of trees is called a . …….
- A.
A collection of trees is called a forest.
- B.
Almost complete binary tree
- C.
Binary tree
- D.
Parser tree
Correct Answer
A. A collection of trees is called a forest.Explanation
The correct answer is "A collection of trees is called a forest." This is because a forest is a term used to describe a grouping or collection of trees. It is commonly used in ecology and forestry to refer to a large area of land covered with trees.Rate this question:
-
- 29.
A tree in which one vertex (called the root) is distinguished from all the other vertices, is called a …………....
- A.
Null tree
- B.
Rooted tree
- C.
Graph
- D.
Forest
Correct Answer
B. Rooted treeExplanation
A tree in which one vertex is distinguished as the root is called a rooted tree. In a rooted tree, all other vertices are connected to the root by edges, and there is a unique path from the root to any other vertex in the tree. This distinction of the root vertex allows for a hierarchical structure in the tree, making it easier to navigate and analyze.Rate this question:
-
- 30.
A tree in which there is exactly one vertex of degree 2, and all other remaining vertices are of degree one or three, is called a ………….
- A.
Binary tree.
- B.
Complete binary tree
- C.
Almost complete binary three
- D.
Forest
Correct Answer
A. Binary tree.Explanation
A tree in which there is exactly one vertex of degree 2, and all other remaining vertices are of degree one or three, is called a binary tree. This is because in a binary tree, each vertex can have at most two children, which aligns with the condition stated in the question. The other options, complete binary tree, almost complete binary tree, and forest, do not specify the requirement of exactly one vertex of degree 2.Rate this question:
-
- 31.
Graph theory was born in ………….. with Euler’s famous paper
- A.
1736
- B.
1730
- C.
1836
- D.
1730
Correct Answer
A. 1736Explanation
Graph theory was born in 1736 with Euler's famous paper.Rate this question:
-
- 32.
A closed walk running through every edge of the graph G exactly once is called an ………….
- A.
Euler path
- B.
Euler line
- C.
Euler forest
- D.
Euler tree
Correct Answer
B. Euler lineExplanation
A closed walk running through every edge of the graph G exactly once is called an Euler path. An Euler line is not a term used in graph theory. Euler forest and Euler tree are also not the correct terms to describe a closed walk running through every edge of the graph exactly once.Rate this question:
-
- 33.
A connected graph G is a Euler graph if and only if it can be decomposed into ……………
- A.
Circuits.
- B.
Multiple path
- C.
Multiple vertices
- D.
Forest
Correct Answer
A. Circuits.Explanation
A connected graph G is a Euler graph if and only if it can be decomposed into circuits. This means that there exists a path that starts and ends at the same vertex, and visits every edge exactly once. If a graph can be decomposed into circuits, it satisfies the necessary condition for being an Euler graph. Therefore, the correct answer is circuits.Rate this question:
-
- 34.
Any graph can be represented with the help of……………..
- A.
Adjacency matrix
- B.
Adjacency linked list matrix
- C.
Both a and b
- D.
Stack
Correct Answer
C. Both a and bExplanation
Both an adjacency matrix and an adjacency linked list can be used to represent a graph.
An adjacency matrix is a 2D array where each cell represents an edge between two vertices. If there is an edge between vertex i and vertex j, then the cell at (i, j) will have a value indicating the weight or presence of the edge.
On the other hand, an adjacency linked list uses an array of linked lists to represent the edges. Each vertex has a linked list associated with it, containing the vertices it is connected to.
Both representations have their advantages and disadvantages. The adjacency matrix allows for efficient edge lookups and is useful when the graph is dense. The adjacency linked list is more memory-efficient and is suitable for sparse graphs.Rate this question:
-
- 35.
The ____ namespace is based on a hierarchical and logical tree structure
- A.
(0, 1)-matrix
- B.
Binary matrix
- C.
Both a and b
- D.
Weight matrix
Correct Answer
C. Both a and bExplanation
The correct answer is "both a and b". This is because both (0, 1)-matrix and binary matrix are based on a hierarchical and logical tree structure. A (0, 1)-matrix is a matrix where each element can only have the values 0 or 1, and it can represent a hierarchical structure where 0 represents absence and 1 represents presence. Similarly, a binary matrix is a matrix where each element can only have the values 0 or 1, and it can also represent a hierarchical and logical tree structure. Therefore, both options a and b are correct.Rate this question:
-
- 36.
Let g be a sub graph of a graph G. Suppose I(g) and I(G) are the incidence matrices of g and G respectively. Then I(g) is called a ……………... of I(G)
- A.
Sub matrix
- B.
Linked matrix
- C.
Simple matrix
- D.
Both b and c
Correct Answer
A. Sub matrixExplanation
In graph theory, an incidence matrix represents the relationships between vertices and edges in a graph. In this question, we are given a subgraph g of a graph G, and we need to determine the term used to describe the incidence matrix of g (denoted as I(g)) in relation to the incidence matrix of G (denoted as I(G)). The correct term is "sub matrix" because I(g) is a matrix that is obtained by selecting a subset of rows and columns from I(G), representing the vertices and edges of the subgraph g. Therefore, I(g) is a sub matrix of I(G).Rate this question:
-
- 37.
A directed graph is also referred to as ……………
- A.
An oriented graph.
- B.
Tree
- C.
Forest
- D.
Connected graph
Correct Answer
A. An oriented grapH.Explanation
A directed graph is also referred to as an oriented graph because it is a graph where the edges have a specific direction. In a directed graph, each edge has an associated direction, indicating the flow or relationship between the nodes. This term "oriented" emphasizes the directional aspect of the graph, distinguishing it from an undirected graph where the edges do not have a specific direction. Therefore, the correct answer is "an oriented graph."Rate this question:
-
- 38.
A vertex v is said to be an ……………. vertex if the out degree of v and the indegree of v are equal to zero.
- A.
Connected
- B.
Isolated
- C.
Directed
- D.
Pendent
Correct Answer
B. IsolatedExplanation
An isolated vertex is a vertex that has no edges connecting it to any other vertex in a graph. In this context, a vertex v is considered an isolated vertex if both its out degree (the number of edges leaving v) and its indegree (the number of edges entering v) are zero. This means that the vertex v is completely disconnected from the rest of the graph, making it an isolated vertex.Rate this question:
-
- 39.
A functions differing from each other by constant factors, should be treated as ……………..
- A.
Complexity-wise equivalent
- B.
Complexity-wise different
- C.
Space wise equivalent
- D.
Space wise different
Correct Answer
A. Complexity-wise equivalentExplanation
Functions that differ from each other by constant factors should be treated as complexity-wise equivalent. This means that the time complexity of these functions is essentially the same, as the constant factors do not significantly impact the overall complexity. In terms of analyzing the efficiency of algorithms, it is common to ignore constant factors and focus on the dominant terms or growth rates. Therefore, these functions can be considered equivalent in terms of their overall complexity.Rate this question:
-
- 40.
The problems which require so large amount of computational resources and can not be solved by computational means. These problems are called …………………
- A.
Non-intractable problems
- B.
Intractable problems.
- C.
Difficult problem
- D.
Classical problem
Correct Answer
B. Intractable problems.Explanation
The given statement describes problems that cannot be solved using computational means due to their large computational requirements. These types of problems are commonly referred to as intractable problems. "Intractable" means that these problems are difficult or impossible to solve using current computational resources and techniques. Therefore, the correct answer is intractable problems.Rate this question:
-
- 41.
It may be noted that the …………..condition is a special case of……………………
- A.
FINITENESS , EFFECTIVENESS
- B.
Definiteness, effectiveness
- C.
Finiteness, definiteness
- D.
Correctness, finiteness
Correct Answer
A. FINITENESS , EFFECTIVENESSExplanation
The given correct answer is "FINITENESS, EFFECTIVENESS". This answer suggests that the condition being referred to is both finite and effective. The term "finiteness" implies that the condition has a definite and limited scope or duration. The term "effectiveness" suggests that the condition is capable of producing the desired or intended result. Therefore, the condition being discussed in this question is both finite in its scope and effective in achieving its purpose.Rate this question:
-
- 42.
A procedure, which can call …………., is said to be ………….. procedure/ algorithm
- A.
Itself, recursive
- B.
By other program, recursive
- C.
Itself, non-recursive
- D.
Some other function , recursive
Correct Answer
A. Itself, recursiveExplanation
A procedure that can call itself is referred to as a recursive procedure or algorithm. This means that the procedure includes a statement that calls itself during its execution. By doing so, it allows for repetitive execution of a specific task until a certain condition is met. This recursive approach is often used to solve problems that can be broken down into smaller, similar subproblems.Rate this question:
-
- 43.
F: R -> R where, R is the set of real numbers. A function f: R -> R is said to be monotonically increasing if for x, y є R and …………. we have ………...
- A.
X ≤ y, f(x) ≤ f(y)
- B.
X ≤ y, f(x) > f(y)
- C.
X > y, f(x) > f(y)
- D.
X >y, f(x) ≤ f(y)
Correct Answer
A. X ≤ y, f(x) ≤ f(y)Explanation
A function f: R -> R is said to be monotonically increasing if for any two real numbers x and y, if x is less than or equal to y, then f(x) is less than or equal to f(y). This means that as the input values increase, the output values also increase or stay the same.Rate this question:
-
- 44.
The worst case efficiency for quick sort is
- A.
O(n2).
- B.
O(2n).
- C.
O(log n2).
- D.
Nlog n
Correct Answer
A. O(n2).Explanation
The worst case efficiency for quicksort is O(n^2) because in the worst case scenario, the pivot chosen for partitioning the array is either the smallest or largest element. This results in one partition having n-1 elements and the other partition having 0 elements. This unbalanced partitioning leads to a time complexity of O(n^2) as each partition needs to be recursively sorted.Rate this question:
-
- 45.
To formulate a greedy-based algorithm to generate the shortest paths, we must conceive of a ………. solution to the problem and also ……….. measure.
- A.
Multistage, an optimization
- B.
Single stage, an optimization
- C.
Single stage , simple
- D.
Multistage, simple
Correct Answer
A. Multistage, an optimizationExplanation
To formulate a greedy-based algorithm to generate the shortest paths, we must conceive of a multistage solution to the problem and also an optimization measure. A multistage solution means that the problem is divided into multiple stages or steps, where each step contributes to finding the shortest path. This approach allows for a more systematic and efficient way of solving the problem. Additionally, an optimization measure is necessary to determine the best path among the available options at each stage, ensuring that the algorithm consistently selects the shortest path. Therefore, the combination of a multistage solution and an optimization measure is crucial for generating the shortest paths using a greedy-based algorithm.Rate this question:
-
- 46.
The travelling salesperson problem is to find a tour of ……………... and principle of …………….. holds.
- A.
Maximum cost, optimality
- B.
Maximum cost, generality
- C.
Minimum cost, generality
- D.
Minimum cost ,optimality
Correct Answer
D. Minimum cost ,optimalityExplanation
The travelling salesperson problem is a well-known optimization problem in computer science. It involves finding the shortest possible route that a salesperson can take to visit a given set of cities and return to the starting city. The "minimum cost" refers to finding the tour with the lowest total distance or cost. The "optimality" principle suggests that the solution obtained is the best possible solution, meaning it cannot be further improved upon. Therefore, the correct answer is "minimum cost, optimality."Rate this question:
-
- 47.
A classic combinational problem is to place …………. on 8x8 chessboard so that no two “attack” that is, so that no two of them are on the …………….., colors or diagonal.
- A.
Eight queens, same row
- B.
Four queens, same column
- C.
Four queens, same row
- D.
8-quenes, same column
Correct Answer
A. Eight queens, same rowExplanation
The correct answer is "eight queens, same row". This means that the problem is to place eight queens on an 8x8 chessboard in such a way that no two queens are in the same row. This condition ensures that no two queens can attack each other horizontally. The other options mentioned in the question (four queens, same column; four queens, same row; 8-queens, same column) are incorrect because they do not satisfy the condition of placing eight queens on the board.Rate this question:
-
- 48.
Backtracking algorithms for the knapsack problem can be arrived at using either of these two state space trees. What are they?
- A.
Tuple size, input size
- B.
Fixed tuple size formulation, variable tuple size formulation
- C.
Input size, output size
Correct Answer
B. Fixed tuple size formulation, variable tuple size formulationExplanation
Backtracking algorithms for the knapsack problem can be arrived at using either fixed tuple size formulation or variable tuple size formulation. The fixed tuple size formulation refers to a scenario where the number of items in the knapsack is fixed, and the algorithm tries to find the optimal combination of items. On the other hand, the variable tuple size formulation allows for flexibility in the number of items in the knapsack, and the algorithm adjusts the combination accordingly. Both formulations provide different approaches to solving the knapsack problem using backtracking.Rate this question:
-
- 49.
To search the travelling salesperson state space tree, we need to define a …………... and two other functions č(.) and u(.) such that (r) ≤ c(r) ≤ u(r) for all nodes r
- A.
Cost function c (.), (r) ≤ c(r) ≤ u(r)
- B.
Copy function, (r) ≤ c(r) ≤ u(r)
- C.
Cost function c (.), (r) > c(r) > u(r)
- D.
Copy function, (r) > c(r) > u(r)
Correct Answer
A. Cost function c (.), (r) ≤ c(r) ≤ u(r)Explanation
In order to search the travelling salesperson state space tree, it is necessary to define a cost function c(.) and two other functions č(.) and u(.) such that (r) ≤ c(r) ≤ u(r) for all nodes r. This means that the cost function c(.) should have a lower bound (r) and an upper bound u(r), ensuring that the cost of reaching a node falls within this range. By defining the cost function in this way, it allows for an effective search of the state space tree to find the optimal solution.Rate this question:
-
- 50.
The cost c(.) is such that the solution node with least c(.) corresponds to a ………………….. in G.
- A.
Shortest tour
- B.
Longest tour
- C.
Cost calculator
- D.
Cost definition
Correct Answer
A. Shortest tourExplanation
The cost function c(.) is designed in such a way that the solution node with the least cost corresponds to the shortest tour in graph G. This means that the cost assigned to each possible tour in G is calculated in a manner that the tour with the lowest cost is identified as the shortest tour.Rate this question:
-
.jpg)
Quiz Review Timeline +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Mar 21, 2023Quiz Edited by
ProProfs Editorial Team -
Jul 11, 2012Quiz Created by
Dsouzaanil
Back to top