In a digraph, the number of edges coming out of a vertex is called the ________ of that vertex.

• A) Out-degree
• B) Complete degree
• C) In-degree
• D) Node

The _______________ given by DFS allow us to determine a number of things about a graph or digraph.

• A) time stamps
• B) line stamps
• C) color stamps
• D) node stamps

Which of the following algorithms solves the fractional knapsack problem most effectively?

• A) Greedy algorithm
• B) Backtracking
• C) Dynamic programming
• D) Divide and conquer

Which of the following problems is NOT solved using dynamic programming?

• A) Matrix chain multiplication problem
• B) 0/1 knapsack problem
• C) Edit distance problem
• D) Fractional knapsack problem

In Fractional Knapsack problem, one is allowed to take fraction of an item for __________

• A) None of the given options
• B) for fraction of the value
• C) for fraction of the weight
• D) Both, fraction of the weight and value

Breadth-first search is a traversal strategy for_________.

• A) Array
• B) Tree
• C) Link List
• D) Graph

If you find yourself in maze the better traversel approach will be :

• A) BFS and DFS both are valid
• B) BFS
• C) DFS
• D) Level order

Each time we traverse graph by Breadth-first search algorithm, we count the distance from _________

• A) starting node
• B) right most node
• C) neighbors of the starting node
• D) left most node

For traversing the graphs, _____________can be visualized as a wave front propagating inward towards root node.

• A) Depth-first Search
• B) Breadth-first search
• C) Binary search
• D) Linear search

Time complexity of activity selection algorithm is _________.

• A) O(NlogN)
• B) O(logN)
• C) O(N)
• D) O(logN2)

For ____________ graphs, there is no distinction between forward and back edges.

• A) large
• B) directed
• C) undirected
• D) small

If the graph is represented using an adjacency list, then Depth-first search takes __________ time.

• A) O(V^2)
• B) O(E + 1)
• C) O(V)
• D) O(V + E)

A _____________ w is adjacent to vertex v if there is an edge from v to w.

• A) cycle
• B) loop
• C) acyclic
• D) vertex

Which graph traversal algorithm uses a stack to keep track of vertices?

• A) Depth First Search
• B) Breadth First Search
• C) Greedy Algorithm
• D) Divide and Conquer

DFS or BFS yields a ___________ of the graph.

• A) Simple Tree
• B) Free Tree
• C) Spanning tree
• D) Traversed Tree

Graphs are important __________ model for many application problems.

• A) Haphazard
• B) Unpredictable
• C) Unsystematic
• D) Mathematical

__________________ data structure is used to perform the Breadth-first search.

• A) Stack
• B) Queue
• C) Tree
• D) Array

There are _____________ ways of representing graphs.

• A) 4
• B) 3
• C) 2
• D) 1

In Activity scheduling algorithm, the width of a rectangle ____________

• A) Is always ignored
• B) Indicates the duration of an activity
• C) Directs towards recursion
• D) Should be maximized

Which type of algorithm is harder to prove the correctness?

• A) Brute Force
• B) Greedy
• C) Dynamic Programming
• D) Divide and Conquer