Bt0080 - Fundamentals Of Algorithms

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

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

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

• Definiteness

• Finiteness

• Correctness

• Effectiveness

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

• Itself, recursive

• By other program, recursive

• Itself, non-recursive

• Some other function , recursive

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

Merge sort is an example of

• Divide and conquer

• Decrease and conquer

• Space and time tradeoff

• Greedy method

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

• FIFO

• LIFO

• LILO

• FILO

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

Knapsack Problem is an example of

• Divide and conquer technique

• Greedy technique

• Decrease and conquer technique

• Time and space tradeoff

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

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

• Undirected graph

• Directed graph

• Directed as well as undirected graph

• Type of tree

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%

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 closed walk running through every edge of the graph G exactly once is called an ………….

• Euler path

• Euler line

• Euler forest

• Euler tree

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

• Systematically

• Logically

• Periodically

• Non- systematically

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

• Comparison

• Differentiation

• Multiplication

• Division

If A[i] is less than A[j], then the algorithm proceeds down the …………... of the tree; otherwise, it proceeds down the …………….

• Depth, height

• Right branch., left branch

• Left branch, right branch.

• Right branch, depth

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

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

• FINITENESS , EFFECTIVENESS

• Definiteness, effectiveness

• Finiteness, definiteness

• Correctness, finiteness

The worst case efficiency for quick sort is

• O(n2).

• O(2n).

• O(log n2).

• Nlog n

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

• Vertices, edges

• Node , path

• Weight , direction

• Vertices , weight

 A process is a ………….. actually being carried out to solve a problem.

• Sequence of activities

• Step-by step procedure

• Flow of information

• Both b and c

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

• FIFO

• LIFO

• FILO

• LILO

A collection of trees is called a . …….

• A collection of trees is called a forest.

• Almost complete binary tree

• Binary tree

• Parser tree

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

• Circuits.

• Multiple path

• Multiple vertices

• Forest

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

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

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

• [1:n]

• [2n:n]

• [1:2n]

• [2:n]

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

• 1736

• 1730

• 1836

• 1730

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

• Isomorphic, identical

• Isomorphic, different

• Tree, identical

• Tree, different

A graph is also called a ………..

• Linear complex

• 1 – complex

• One-dimensional complex

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

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)

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)

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 cost c(.) is such that the solution node with least c(.) corresponds to a ………………….. in G.

• Shortest tour

• Longest tour

• Cost calculator

• Cost definition

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

• 1. True, 2. true, 3. true

• 1. true, 2. false, 3.true

• 1. false, 2. false, 3. false

• 1. true, 2. true, 3. false

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.

• 1. True, 2. true, 3. true

• 1. true, 2. false, 3.true

• 1. false, 2. false, 3. false

• 1. true, 2. true, 3. false

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

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

• A

• B

• C

• D

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

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

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

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

Digraphs that have at most ……………... edge between any pair of vertices, but are allowed to have self-loops are called the ……………….

• One directed, asymmetric (or) anti-symmetric digraphs.

• One directed, symmetric digraphs.

• Two directed, symmetric digraphs.

• Two directed, asymmetric

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

• Single cycle, once

• Single cycle, twice

• Double cycle, once

• Double cycle, twice

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

• 1. True, 2. true, 3. true

• 1. true, 2. false, 3.true

• 1. false, 2. false, 3. false

• 1. true, 2. true, 3. false