Bt0080 - Fundamentals Of Algorithms
Settings
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
- 2.An algorithm must terminate after a finite number of steps is known as
- A.
Definiteness
- B.
Finiteness
- C.
Correctness
- D.
Effectiveness
- 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
- 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
- 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
- 6.The concept of logarithm is defined indirectly by the definition of ……………
- A.
Exponential
- B.
Floor Function
- C.
Ceiling function
- D.
Monotonically increasing function
- 7.
![- ProProfs]()
- A.
A
- B.
B
- C.
C
- D.
D
- 8.Merge sort is an example of
- A.
Divide and conquer
- B.
Decrease and conquer
- C.
Space and time tradeoff
- D.
Greedy method
- 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]
- 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
- 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
- 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
- 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
- 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
- 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
- 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),
- 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%
- 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
- 19.In branch-and-bound terminology, a BFS-like state space search will be called ……….
- A.
FIFO
- B.
LIFO
- C.
LILO
- D.
FILO
- 20.A D-search-like state space search will be called ………….
- A.
FIFO
- B.
LIFO
- C.
FILO
- D.
LILO
- 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
- 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
- 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
- 24.Each internal node in binary tree represents a …………
- A.
Comparison
- B.
Differentiation
- C.
Multiplication
- D.
Division
- 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
- 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
- 27.A circuit is a closed, ………….. walk
- A.
Nonintersecting
- B.
Intersecting
- C.
Crossed
- D.
Easy
- 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
- 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
- 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
- 31.Graph theory was born in ………….. with Euler’s famous paper
- A.
1736
- B.
1730
- C.
1836
- D.
1730
- 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
- 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
- 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
- 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
- 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
- 37.A directed graph is also referred to as ……………
- A.
An oriented graph.
- B.
Tree
- C.
Forest
- D.
Connected 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.
- A.
Connected
- B.
Isolated
- C.
Directed
- D.
Pendent
- 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
- 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
- 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
- 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
- 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)
- 44.The worst case efficiency for quick sort is
- A.
O(n2).
- B.
O(2n).
- C.
O(log n2).
- D.
Nlog n
- 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
- 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
- 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
- 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
- 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)
- 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
- 51.If the algorithm ………., following a left or right branch, then no i has been such that x=A[i] and the algorithm must declare the search …………..
- A.
Terminates, unsuccessful
- B.
Starts, successful
- C.
Starts , unsuccessful
- D.
Terminates, successful
- 52.If A[i] is less than A[j], then the algorithm proceeds down the …………... of the tree; otherwise, it proceeds down the …………….
- A.
Depth, height
- B.
Right branch., left branch
- C.
Left branch, right branch.
- D.
Right branch, depth
- 53.A linear graph (or simply a graph) G = (V,E) consists of a set of objects V = {v1,v2…..} called …………..., and another set E = {e1,e2…}, whose elements are called ………..
- A.
Vertices, edges
- B.
Node , path
- C.
Weight , direction
- D.
Vertices , weight
- 54.The sum of path lengths from the root to all pendent vertices is called the…………. (or) ………….. of a tree.
- A.
Path length, external path length
- B.
Path length, internal path length
- C.
Depth of a tree, internal path length
- D.
Depth of a tree, external path length
- 55.A Hamiltonian circuit in a connected graph is defined as a ……………... that traverses every vertex of G exactly once, except ……………..
- A.
Closed walk , starting vertex
- B.
Open walk , starting vertex
- C.
Closed walk , end vertex
- D.
Open walk, end vertex
- 56.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
- 57.A digraph that has neither ……………. nor …………….. is called a simple digraph
- A.
Self-loops, parallel edges
- B.
Isolated vertex, parallel edges
- C.
Isolated vertex, vertical edges
- D.
Self-loops, vertical edges
- 58.Digraphs that have at most ……………... edge between any pair of vertices, but are allowed to have self-loops are called the ……………….
- A.
One directed, asymmetric (or) anti-symmetric digraphs.
- B.
One directed, symmetric digraphs.
- C.
Two directed, symmetric digraphs.
- D.
Two directed, asymmetric
- 59.A Hamiltonian circuit of a graph G = (V, E) is a set of edges that connects the nodes into a …………..., with each node appearing exactly ………...
- A.
Single cycle, once
- B.
Single cycle, twice
- C.
Double cycle, once
- D.
Double cycle, twice
- 60.Two graphs H1 = (V1, E1) and H2 = (V2, E2) are said to be …………….. if we can rename the vertices in V2 in such a manner that after renaming, the graph H1 and H2 look ………….
- A.
Isomorphic, identical
- B.
Isomorphic, different
- C.
Tree, identical
- D.
Tree, different
- 61.State weather the following statement is true or false for NP-Complete and NP-Hard Problems 1).a problem is called NP-Complete if P has at least one Non-Deterministic Polynomial-time solution. 2).The process of transformation of the instances of the problem already known to the decidable to instances of the problem, is called reduction 3). A Polynomial-time reduction is a polynomial-time algorithm
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 62.
![- ProProfs]()
- A.
A
- B.
B
- C.
C
- D.
D
- 63.State weather the following statement is true or false 1).Shell sort is also called diminishing-increment sort 2).A tree is called a binary tree, if it is either empty, or it consists of a node called the root 3). The concept of mathematical expectation is needed in best case analysis of algorithms.
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 64.State weather the statement is true or false for Understanding the problem we should know the following things . 1).The type of problem 2). The type of inputs and the type of expected/ desired outputs 3). Special cases of the problem, which may need different treatment for solving the problem
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 65.State weather the following statement is true or false for Single Source Shortlist Paths 1).The problem is to determine the shortest paths from v̥0 to all the remaining vertices of G.. 2).It is assumed that all the weights are positive. 3). The greedy way to generate the shortest paths from v0 to the remaining vertices is to generate these paths in non-decreasing order of path len
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 66.
![- ProProfs]()
- A.
A
- B.
B
- C.
C
- D.
D
- 67.State weather the following statement is true or false for Sum of Subsets 1).Given positive numbers wi, 1≤ i ≤n, and m, this problem calls for finding all subsets of the wi whose sums are m. 2). In general, all solutions are k-tuples (x1, x2…….. xk), 1 ≤ k ≤ n, and different solutions may have different sized tuples 3). implicit constraints that is imposed is xi<xi+1, I ≤ i < k.
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 68.
![- ProProfs]()
- A.
A
- B.
B
- C.
C
- D.
D
- 69.State weather the following statement is true or false for NP Hard and NP Complete Problems 1).The theory of NP-completeness, which we present here, does not provide a method of obtaining polynomial time algorithms for problems in the second group.. 2). Nor does it say that algorithms of this complexity do not exist. 3). , we establish two classes of problems. These are given names, NP-hard and NP-Complete.
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 70.State weather the following statement is true or false for Trees 1).A tree is a connected graph with circuits. 2). A graph must have at least one vertex, and therefore so must a tree. 3). a tree without any vertices called null tree
- A.
1. false , 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 71.State weather the following statement is true or false for Spanning Trees 1).A tree T is said to be a spanning tree of a connected graph G if T is a sub graph of G and T contains all the vertices of G 2). Spanning trees are the largest (with the maximum number of edges) trees among all trees in G. 3). Spanning is defined only for a connected graph
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 72.State weather the following statement is true or false for Hamiltonian Circuit and Path 1).every connected graph has a Hamiltonian circuit. 2). every graph that has a Hamiltonian circuit also has a Hamiltonian path. 3). A given graph may contain more than one Hamiltonian circuit
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 73.State weather the following statement is true or false for Circuit Matrix. 1).i) If a column of B(G) contains all zeros, then the related edge does not belong to any circuit. 2). iii) If a row contains only one "1", then the related edge is a self-loop 3). ii) Each row of B(G) corresponds to a circuit. So each row may be called as a circuit vector
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 74.State weather the following statement is true or false for Binary Euler’s Digraphs 1) D is said to be a Euler digraph if it contains a directed Euler line 2). A closed directed walk which traverses every edge of D exactly once, is called a directed Euler line 3). A directed walk that starts and ends at the different vertex is called a closed directed walk.
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
- 75.State weather the following statement is true or false for Recursion 1) A procedure, which can call itself. 2). There must be conditions within the definition of a recursive procedure 3). The arguments in successive calls should not be simpler.
- A.
1. True, 2. true, 3. true
- B.
1. true, 2. false, 3.true
- C.
1. false, 2. false, 3. false
- D.
1. true, 2. true, 3. false
.jpg)
.jpg)
.jpg)
.jpg)
Back to top