Bt0080 - Fundamentals Of Algorithms

An algorithm must terminate after a finite number of steps is known as

• Definiteness

• Finiteness

• Correctness

• Effectiveness

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

• Direct sequencing

• Indirect sequencing

• Direct selection

• Indirect selection

Each of the floor function and ceiling function is a monotonically increasing function but not ……………..

• Strictly monotonically increasing function

• Monotonically decreasing function

• Strictly monotonically decreasing function

• Mod function

………………….maps each real number x to the integer, which is the greatest of all integers less than or equal to

• Ceiling function

• Floor Function

• Monotonically increasing function

• Exponentiation Function

 The concept of logarithm is defined indirectly by the definition of ……………

• Exponential

• Floor Function

• Ceiling function

• Monotonically increasing function

• A

• B

• C

• D

Merge sort is an example of

• Divide and conquer

• Decrease and conquer

• Space and time tradeoff

• Greedy method

Before executing Merge Sort, the n elements should be placed in a [1:n].

• [1:n]

• [2n:n]

• [1:2n]

• [2:n]

A feasible solution that either maximizes or minimizes a given objective function is called an …………..

• Optimal solution

• Local solution

• Exact solution

• Correct solution correct solution correct solution

Knapsack Problem is an example of

• Divide and conquer technique

• Greedy technique

• Decrease and conquer technique

• Time and space tradeoff

In a graph, when does Dijkstra's algorithm stop?

• When the shortest path to the destination vertex is found

• When all the vertices in the graph are included to the path

• When the vertices together form a cycle

• When the minimum spanning tree is constructed

The multistage graph problem can also be solved using the ……………….

• Backward approach

• Forward approach

• Top down approach

• Bottoms up approach

A multistage graph G = (V,E) is a ……………….

• Undirected graph

• Directed graph

• Directed as well as undirected graph

• Type of tree

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.

• Matrix A

• Array A

• Graph A

• Tree A

All solutions to the 8-queens problem can be represented as ………………. where xi is the column on which queen i is placed.

• 8-tuples (x1…… x8),

• 12-tuples (x1…… x12),

• 16-tuples (x1…… x16),

• 4-tuples (x1…… x4),

The estimated no. of unbounded nodes is only ………... of the total no of nodes in the 8 queen state space tree.

• 3.34%

• 2.34%

• 1%

• 4.34%

Backtracking algorithms determine problem's solutions by …………………... searching the solution space for the given problem instance

• Systematically

• Logically

• Periodically

• Non- systematically

In branch-and-bound terminology, a BFS-like state space search will be called ……….

• FIFO

• LIFO

• LILO

• FILO

A D-search-like state space search will be called ………….

• FIFO

• LIFO

• FILO

• LILO

To use the branch-and-bound technique to solve any problem, first, it is necessary to conceive of a …………... for the problem

• State space tree

• Binary search tree

• Syntax tree

• Flowchart

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).

• Lower bound

• Upper bound

• Space complexity

• Average bound

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

• Descendent

• Identical

• Differ

• Local

Each internal node in binary tree represents a …………

• Comparison

• Differentiation

• Multiplication

• Division

An edge having the same vertex as both its end vertices called a ……………

• Self-loop

• Open loop

• Closed vertex

• Open vertex Open vertex Open vertex

A graph is also called a ………..

• Linear complex

• 1 – complex

• One-dimensional complex

• Linear complex, or a 1 – complex, or a one-dimensional complex

A circuit is a closed, ………….. walk

• Nonintersecting

• Intersecting

• Crossed

• Easy

A collection of trees is called a . …….

• A collection of trees is called a forest.

• Almost complete binary tree

• Binary tree

• Parser tree

A tree in which one vertex (called the root) is distinguished from all the other vertices, is called a …………....

• Null tree

• Rooted tree

• Graph

• Forest

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.

• Complete binary tree

• Almost complete binary three

• Forest

Graph theory was born in ………….. with Euler’s famous paper

• 1736

• 1730

• 1836

• 1730

A closed walk running through every edge of the graph G exactly once is called an ………….

• Euler path

• Euler line

• Euler forest

• Euler tree

A connected graph G is a Euler graph if and only if it can be decomposed into ……………

• Circuits.

• Multiple path

• Multiple vertices

• Forest

Any graph can be represented with the help of……………..

• Adjacency matrix

• Adjacency linked list matrix

• Both a and b

• Stack

The ____ namespace is based on a hierarchical and logical tree structure

• (0, 1)-matrix

• Binary matrix

• Both a and b

• Weight matrix

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)

• Sub matrix

• Linked matrix

• Simple matrix

• Both b and c

A directed graph is also referred to as ……………

• An oriented graph.

• Tree

• Forest

• Connected graph

A vertex v is said to be an ……………. vertex if the out degree of v and the indegree of v are equal to zero.

• Connected

• Isolated

• Directed

• Pendent

A functions differing from each other by constant factors, should be treated as ……………..

• Complexity-wise equivalent

• Complexity-wise different

• Space wise equivalent

• Space wise different

The problems which require so large amount of computational resources and can not be solved by computational means. These problems are called …………………

• Non-intractable problems

• Intractable problems.

• Difficult problem

• Classical problem

It may be noted that the …………..condition is a special case of……………………

• FINITENESS , EFFECTIVENESS

• Definiteness, effectiveness

• Finiteness, definiteness

• Correctness, finiteness

A procedure, which can call …………., is said to be ………….. procedure/ algorithm

• Itself, recursive

• By other program, recursive

• Itself, non-recursive

• Some other function , recursive

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

• X ≤ y, f(x) ≤ f(y)

• X ≤ y, f(x) > f(y)

• X > y, f(x) > f(y)

• X >y, f(x) ≤ f(y)

The worst case efficiency for quick sort is

• O(n2).

• O(2n).

• O(log n2).

• Nlog n

To formulate a greedy-based algorithm to generate the shortest paths, we must conceive of a ………. solution to the problem and also ……….. measure.

• Multistage, an optimization

• Single stage, an optimization

• Single stage , simple

• Multistage, simple

The travelling salesperson problem is to find a tour of ……………... and principle of …………….. holds.

• Maximum cost, optimality

• Maximum cost, generality

• Minimum cost, generality

• Minimum cost ,optimality

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.

• Eight queens, same row

• Four queens, same column

• Four queens, same row

• 8-quenes, same column

Backtracking algorithms for the knapsack problem can be arrived at using either of these two state space trees. What are they?

• Tuple size, input size

• Fixed tuple size formulation, variable tuple size formulation

• Input size, output size

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

• Cost function c (.), (r) ≤ c(r) ≤ u(r)

• Copy function, (r) ≤ c(r) ≤ u(r)

• Cost function c (.), (r) > c(r) > u(r)

• Copy function, (r) > c(r) > u(r)