# Analysis of Algorithms (Original) - Original var ActionUrl = '/exam_action_public.asp?CrsID=734&AsnID=784&QInTest=99&ER_ID=0&from=preview';

Instructions:

This exam is meant to enhance your understanding of the subject matter, and contains roughly the same amount of multiple choice, fill-in-the-blank and true or false questions. For each question, select or fill in the choice that is most appropriate.

Exam-takers should read through each question carefully and take notes on difficult concepts.

The Bellman-Ford algorithm is suitable for distributed processing than Dijkstra’s algorithm.

Heapsort is not a stable sorting algorithm.

a)
True
b)
False

The in-order traversal of tree will yield a sorted listing of elements of tree in which of the following ?

a)
Binary trees
b)
Binary search trees
c)
Merging
d)
AVL trees

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)
submatrix
b)
c)
simple matrix
d)
both b and c

When the sequence of the execution of instructions is to be the same as the sequence in which instructions are written in program text, it is known as .

Which of the following technique is associated with the fractional knapsack problem ?

a)
Divide and Conquer Technique
b)
Greedy Technique
c)
Dynamic Programming
d)
Linear Programming

A 0/1 knapsack problem is NP-complete.

a)
True
b)
False

What is the termination condition in the case of Dijkstra's algorithm ?

a)
When the vertices form a cycle
b)
When all the vertices in the graph are included in the path
c)
When the shortest path to the destination vertex is found
d)
When the path with n-1 edges is found

Which of the following appropriately describes an edge with same vertex as a start and destination vertex ?

a)
Open Loop
b)
Backstage Loop
c)
Self Loop
d)
Backtrack Edge

Two functions differing from each-other by factors are considered a complexity-wise equivalent.

The maximum value of an s-t flow could be less than the capacity of a given s-t cut in a flow network.

a)
True
b)
False

In a dynamic programming solution, the space requirement is always at least as big as the number of unique sub problems.

a)
True
b)
False

Any problem that can be solved using dynamic programming has a polynomial worst case time complexity with respect to its input size.

a)
True
b)
False

Master theorem can always be used to find the complexity of T(n) if it can be written as the recurrence relation T(n) = aT(n/2) + f(n).

a)
True
b)
False

The travelling salesperson problem illustrates a tour of A and the principle that B holds. Which of the following correctly describes A and B ?

a)
Maximum Cost, optimality
b)
Minimum Cost, generality
c)
Minimum Cost, optimality
d)
Maximum Cost, generality

What is the time complexity of the recurrence relation ? a)
Theta(2^n)
b)
Theta(n)
c)
BigO(n^2)
d)
BigO(n)

What is the Time Complexity of the following recurrence relation? a)
Theta(Log(n)*Log(Log(n)))
b)
Theta(Log(n))
c)
Theta(n*Log(Log(n)))
d)
Theta(Log(Log(n)))

What is the time complexity of the following recurrence relation? a)
Theta(n*Log(Log(n)))
b)
Theta(n*Log(n^2))
c)
Theta(n^2*Log(n^2))
d)
Theta(n^2*(Log(n))^2)

What does it mean when we say that algorithm A is asymptotically more efficient than B ?

a)
B will be a better choice for small inputs.
b)
A will be a better choice for all inputs.
c)
A will be a better choice for all inputs except small inputs
d)
A will be a better choice for all inputs except large inputs

In graph G= (V,E), a Hamiltonian circuit is a set of edges that connects the nodes into A, with each node appearing as exactly B.

Which of the following appropriately describes A and B ?

a)
Single Cycle, Twice
b)
Single Cyle, Once
c)
Double Cycle, Once
d)
Double Cycle, Twice

If  a tree T is a sub graph of G, and T contains all the vertices of G, then T is said to be a spanning tree of a connected graph G.

a)
True
b)
False

A dynamic programming algorithm tames the complexity by making sure that no subproblem is solved more than once.

a)
True
b)
False

A greedy algorithm finds an optimal solution by making a sequence of choices and at each decision point in the algorithm, the choice that seems best at the moment is chosen.

a)
True
b)
False

Given a connected, undirected graph G with distinct edge weights, then the edge e with the second smallest weight is included in the minimum spanning tree.

a)
True
b)
False

For a graph G and a node v in that graph, the DFS and BFS trees of G rooted at v contain the number of edges

The complexity of the “Decrease_Key” operation is always O(lgn) for a priority queue.

a)
True
b)
False

Which of the following is true about MST, for a graph with distinct edge weight

a)
There can be multiple minimum spanning trees
b)
There will be a unique minimum spanning tree
c)
Minimum spanning tree might not exist
d)
None of these

Consider an undirected graph G=(V, E) and its minimum spanning tree T. Suppose we add one 1 to the cost of each edge in G. Which of the following is true ?

a)
An MST of the graph will change
b)
T and MST will complement each other
c)
Both A and B
d)
T will still remain as an MST.

Problems solved using dynamic programming can be solved through algorithms

While there are different algorithms to find a minimum spanning tree of undirected connected weighted graph G, all of these algorithms produce the same result for a given G.

a)
True
b)
False

What would be the time complexity of the following recurrence relation: a)
O(n*n*n*2^n)
b)
O(n*n*3^n)
c)
O(n*Log(n))
d)
Theta(n*n*n)

Which of the following is associated with Kruskal’s algorithm for finding an MST of a weighted, undirected graph?

a)
Dynamic Programming Technique
b)
Greedy Technique
c)
Divide and Conquer
d)
None of these

If all of the weights from a connected and weighted graph are distinct, then which of the following is true about the spanning trees of the graph ?

a)
Distinct spanning trees of the graph must have distinct weights.
b)
Graph must have only one spanning tree
c)
Distinct spanning trees of the graph can have same weights.
d)
None of these

A breadth-first-search (BFS) can be used to test whether a graph is bipartite.

a)
True
b)
False

There exists a perfect matching and a corresponding preference list showing that every man is part of an instability, and every woman is part of an instability.

a)
True
b)
False

You are given n elements to insert into an empty heap. You could directly call heap insert n times. Or you could first sort the elements and then call heap insert n times. The asymptotic time complexity in these scenarios would be the .

The Depth First Search algorithm can not be used to test whether a directed graph is strongly-connected.

a)
True
b)
False

An array that is sorted in descending order is a max-heap.

a)
True
b)
False

Let G be an undirected, connected, bipartite, weighted graph. If the weight of each edge in G is +1, and for every pair of vertices (u,v) in G there is exactly one shortest path, then G is a tree.

a)
True
b)
False

If DFS and BFS returns different trees, then which of the following is true ?

a)
Original graph is bipartite
b)
Original graph can be reduced to 3 SAT
c)
Original graph is not a tree
d)
None of these

If you are using Kruskal's algorithm to find the MST, which of the following is true about the edge costs?

a)
Only positive edges are allowed
b)
Only negative edges are allowed
c)
Both positive and negative edges are allowed
d)
None of these

Prim’s algorithm can fail in the presence of negative cost edges.

a)
True
b)
False

In every instance of the stable marriage problem, there is a stable matching containing a pair (m, w) such that m is ranked first on the preference list of w, and w is ranked first on the preference list of m.

a)
True
b)
False

Which of the following is true about Merge sort ?

a)
Merge sort is an in-place sorting algorithm
b)
Merge sort is a stable sort
c)
Both
d)
None of these

Which of the following statements is true ?

a)
Mergesort does not need any additional memory space other than that held by the array being sorted.
b)
There are at least 2 distinct solutions to the stable matching problem--one that is preferred by men and one that is preferred by women.
c)
A divide and conquer algorithm has a minimum complexity of O(n log n) since the height of the recursion tree is always O(log n).
d)
Gale Shapley algorithm for s`table marriage problem is based on the greedy technique.

Which of the following is true about delete operation w.r.t. binary heap and binomial heap?

a)
Binary heap is more efficient than binomial heap
b)
Binomial heap is more efficient than binary heap
c)
Both are equally efficient as they have the same complexity
d)
None of these

In priority queue implementation using heaps, for the meld operation, a is more efficient than a binary heap.

The Ford-Fulkerson algorithm is based on which on the following techniques ?

a)
Divide and Conquer
b)
Greedy Technique
c)
Dynamic Programming
d)
None of these

Assuming P != NP, which of the following is true?

a)
NP-complete = NP
b)
NP-hard = NP
c)
P = NP-complete
d)
NP-complete UNION P = NULL

Which of the following is not an in-place algorithm?

a)
Heap sort
b)
Insertion sort
c)
Merge sort
d)
Selection sort

Which of the following algorithms can be used most efficiently to determine the presence of a cycle in a given graph ?

a)
b)
Depth First Search
c)
Prim
d)
Kruskal

The Bellman-Ford algorithm solves the shortest path problem in graphs with negative cost edges in time.

Which of the following is true for the Ford-Fulkerson algorithm ?

a)
It is possible that in the final residual graph constructed during the execution of the Ford-Fulkerson algorithm, there can be a path from source to sink
b)
In the final residual graph constructed during the execution of the Ford-Fulkerson Algorithm, there is no path from source to sink.
c)
Availability of path from source to sink in the residual graph varies with the graphs
d)
None of these

Given a directed graph, if deleting edge e reduces the original maximum flow more than deleting any other edge does, then edge e must be part of a minimum s-t cut in the original graph.

a)
True
b)
False

The value of maximum flow for the given graph would be . Source: Tajinder Singh

Which of the following statement is true ?

a)
Complexity of a dynamic programming algorithm is equal to the number of unique sub-problems in the solution space.
b)
Dynamic programming and divide and conquer are similar, in that in each approach the sub-problems at each step are completely independent of one another.
c)
For every node in a network, the total flow into a node equals the total flow out of a node.
d)
In the Ford-Fulkerson algorithm

When finding the value of the optimal solution in a algorithmic technique, one must find values of optimal solutions for all of its sub-problems.

Which of the following statement is true ?

a)
If all edge capacities of a flow network are increased by k, then the maximum flow will be increased by at least k.
b)
The Ford-Fulkerson algorithm has a polynomial time complexity with respect to the input size.
c)
The main difference between divide and conquer and dynamic programming is that divide and conquer solves problems in a top-down manner, whereas dynamic-programming does this in a bottom-up manner.
d)
In the Ford-Fulkerson algorithm, the choice of augmenting paths can affect the number of iterations.

What is the maximum flow from O to T in the network ? Source: Tajinder Singh

a)
7
b)
8
c)
9
d)
10

A binary search could be called a divide and conquer technique.

a)
True
b)
False

Which of the following is definitely true ?

a)
If a problem is in NP, it must also be in P.
b)
If a problem is NP-complete, it must also be in NP.
c)
If a problem is NP-complete, it must not be in P.
d)
If a problem is in NP, it must also be NP-hard.

Which of the following statement is true about vertex cover?

a)
If we find an efficient algorithm to solve the vertex cover problem with an approximation factor of p>=1 (a single constant) then we have proven that P=NP
b)
If we find an efficient algorithm that takes as input an approximation factor p>=1 and solves the vertex cover problem with that approximation factor, we have proven that P=NP
c)
If we find an efficient algorithm to solve the vertex cover problem, we have proven that P=NP
d)
None of these

In case of an undirected graph, the sum of the degrees of all the vertices of the graph is .

In the case of undirected graphs, the number of odd-degree vertices of the graph is always

The following numbers are inserted into an empty binary search tree in the given order: 8,3,10,1,6,4,7,14,13. The height of the binary search tree would be (the height is the maximum distance of a leaf node from the root).

The pre-order traversal sequence of a binary search tree is 8,3,1,6,4,7,10,14,13. The following is the post-order traversal sequence of the same tree: 1,4,7,3,13,6,14,10,8.

a)
True
b)
False

In the case of graph and traversal techniques, an traversal technique is not sufficient to construct a BST from the given ordering of elements.

An AVL tree is a self-adjusting or self-balancing binary search tree.

a)
True
b)
False

In the case of a red-black tree, the path from the root to the furthest leaf is no more than as long as the path from the root to the nearest leaf.

In an AVL tree insertion operation, we first traverse from the root node to the newly inserted node and then after from this newly inserted node to the root node. However, in case of Red Black tree insertion operation, we traverse only once from root node to the newly inserted node.

a)
True
b)
False

The time complexity of the search operation in B/B+ tree is better than red-black trees in general.

a)
True
b)
False

In the case of a B/B+ tree, the number of child pointers in a node always the number of keys in it, plus one.

The in-order and pre-order traversals of a binary tree are 1,13,27,37,44,54,64,71,89,92  and 54,27,13,1,44,37,89,71,64,92, respectively. The postorder traversal of the binary tree is . (Please write nodes separated with comma in the answer space.)

The level-order traversal technique uses a data structure.

For arithmetic expression evaluation, generally the data structure is used.

When a resource is shared among multiple consumers, generally the data structure is used.

A priority queue can efficiently be implemented using a linked list data structure, more so than an array or heap data structure. Note: Assume that the number of insert, peek and extraction operations are almost the same.

a)
True
b)
False

If in a graph G, every node is adjacent to every other node of the graph, then the graph is said to be a graph.

In the case of a linked list data structure, the situation when the start pointer start = null is called .

In a social network, choosing a set of people so that every possible friendship has a representative, is a classic application of an independent set problem.

a)
True
b)
False

"On what nodes should you place sensors in an electric network to make sure you monitor every edge?"
Which of the following problem sets does this problem belongs to?

a)
Independent set problem
b)
Vertex cover problem
c)
3 SAT problem
d)
Traveling salesman problem

In the memory efficient implementation of the Bellman-Ford algorithm, the number of iterations it takes to converge can vary, depending on the order of nodes updated within an iteration.

a)
True
b)
False

In a dynamic programming formulation, the sub problems must be mutually independent.

a)
True
b)
False

If X is polynomial time reducible to Y, and Y can be solved in polynomial-time,  then X can be solved in .

The famous "Tower of Hanoi" problem is an application of data structure.

Subset sum problem: Given a set of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −1, 4, 8}, the answer is yes, because the subset {−3, −1, 4} sums to zero. In computer science, the subset sum problem is an important problem, and it belongs to the class of problems in computational compexity theory .

Optimal substructure property is exploited by which of the following ?

a)
Greedy approach
b)
Dynamic programming
c)
Both
d)
None of these

Greedy is a top down strategy in which each greedy choice in the sequence iteratively reduces each problem to a similar, but problem.

A problem exhibits if an optimal solution to the problem contains within it optimal solutions to subproblems.

When new data are to be inserted into a data structure, but there is no available space. This situation is usually called .

The diagonal of the adjacency matrix of a graph with a contains both 0 and 1.

Arrays are the best data structures for the size of the structure, and the data in the structure are constantly changing.

a)
True
b)
False

A stack does not keep track of the address of every element in the list.

a)
True
b)
False

A directed graph is if there is a path from each vertex to every other vertex in the digraph.

A bubble sort is an internal sort.

a)
True
b)
False

A ternary tree is a directed tree in which the out-degree of each node is less than or equal to .

Data elements in a linked list need not be stored in adjacent space in memory.

a)
True
b)
False

The term 'dequeue' is the contraction of the name .

A binary tree whose every node has either zero or two children is called an   .