1.
A process is a ………….. actually being carried out to solve a problem.
Correct Answer
A. Sequence of activities
Explanation
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.
2.
An algorithm must terminate after a finite number of steps is known as
Correct Answer
B. Finiteness
Explanation
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.
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 ………..
Correct Answer
A. Direct sequencing
Explanation
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.
4.
Each of the floor function and ceiling function is a monotonically increasing function but not ……………..
Correct Answer
A. Strictly monotonically increasing function
Explanation
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".
5.
………………….maps each real number x to the integer, which is the greatest of all integers less than or equal to
Correct Answer
B. Floor Function
Explanation
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.
6.
The concept of logarithm is defined indirectly by the definition of ……………
Correct Answer
A. Exponential
Explanation
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.
7.
Correct Answer
A. A
8.
Merge sort is an example of
Correct Answer
A. Divide and conquer
Explanation
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.
9.
Before executing Merge Sort, the n elements should be placed in a [1: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.
10.
A feasible solution that either maximizes or minimizes a given objective function is called an
…………..
Correct Answer
A. Optimal solution
Explanation
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."
11.
Knapsack Problem is an example of
Correct Answer
B. Greedy technique
Explanation
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.
12.
In a graph, when does Dijkstra's algorithm stop?
Correct Answer
A. When the shortest path to the destination vertex is found
Explanation
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.
13.
The multistage graph problem can also be solved using the ……………….
Correct Answer
A. Backward approach
Explanation
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.
14.
A multistage graph G = (V,E) is a ……………….
Correct Answer
B. Directed graph
Explanation
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.
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.
Correct Answer
A. Matrix A
Explanation
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.
16.
All solutions to the 8-queens problem can be represented as ………………. where xi is the column on which queen i is placed.
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).
17.
The estimated no. of unbounded nodes is only ………... of the total no of nodes in the 8 queen state space tree.
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.
18.
Backtracking algorithms determine problem's solutions by …………………... searching the solution space for the given problem instance
Correct Answer
A. Systematically
Explanation
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.
19.
In branch-and-bound terminology, a BFS-like state space search will be called ……….
Correct Answer
A. FIFO
Explanation
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.
20.
A D-search-like state space search will be called ………….
Correct Answer
B. LIFO
Explanation
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.
21.
To use the branch-and-bound technique to solve any problem, first, it is necessary to conceive of a …………... for the problem
Correct Answer
A. State space tree
Explanation
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".
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).
Correct Answer
A. Lower bound
Explanation
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.
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
Correct Answer
B. Identical
Explanation
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.
24.
Each internal node in binary tree represents a …………
Correct Answer
A. Comparison
Explanation
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.
25.
An edge having the same vertex as both its end vertices called a ……………
Correct Answer
A. Self-loop
Explanation
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.
26.
A graph is also called a ………..
Correct Answer
D. Linear complex, or a 1 – complex, or a one-dimensional complex
Explanation
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.
27.
A circuit is a closed, ………….. walk
Correct Answer
A. Nonintersecting
Explanation
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.
28.
A collection of trees is called a . …….
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.
29.
A tree in which one vertex (called the root) is distinguished from all the other vertices, is called a …………....
Correct Answer
B. Rooted tree
Explanation
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.
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 ………….
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.
31.
Graph theory was born in ………….. with Euler’s famous paper
Correct Answer
A. 1736
Explanation
Graph theory was born in 1736 with Euler's famous paper.
32.
A closed walk running through every edge of the graph G exactly once is called an ………….
Correct Answer
B. Euler line
Explanation
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.
33.
A connected graph G is a Euler graph if and only if it can be decomposed into ……………
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.
34.
Any graph can be represented with the help of……………..
Correct Answer
C. Both a and b
Explanation
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.
35.
The ____ namespace is based on a hierarchical and logical tree structure
Correct Answer
C. Both a and b
Explanation
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.
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)
Correct Answer
A. Sub matrix
Explanation
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).
37.
A directed graph is also referred to as ……………
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."
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.
Correct Answer
B. Isolated
Explanation
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.
39.
A functions differing from each other by constant factors, should be treated as ……………..
Correct Answer
A. Complexity-wise equivalent
Explanation
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.
40.
The problems which require so large amount of computational resources and can not be solved by computational means. These problems are called …………………
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.
41.
It may be noted that the …………..condition is a special case of……………………
Correct Answer
A. FINITENESS , EFFECTIVENESS
Explanation
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.
42.
A procedure, which can call …………., is said to be ………….. procedure/ algorithm
Correct Answer
A. Itself, recursive
Explanation
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.
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 ………...
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.
44.
The worst case efficiency for quick sort is
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.
45.
To formulate a greedy-based algorithm to generate the shortest paths, we must conceive of a ………. solution to the problem and also ……….. measure.
Correct Answer
A. Multistage, an optimization
Explanation
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.
46.
The travelling salesperson problem is to find a tour of ……………... and principle of …………….. holds.
Correct Answer
D. Minimum cost ,optimality
Explanation
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."
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.
Correct Answer
A. Eight queens, same row
Explanation
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.
48.
Backtracking algorithms for the knapsack problem can be arrived at using either of these two state space trees. What are they?
Correct Answer
B. Fixed tuple size formulation, variable tuple size formulation
Explanation
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.
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
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.
50.
The cost c(.) is such that the solution node with least c(.) corresponds to a ………………….. in G.
Correct Answer
A. Shortest tour
Explanation
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.