The number of edges that come out of a vertex is called the ________ of that vertex in a digraph.

• A) out-degree
• B) post-degree
• C) in-degree
• D) pre-degree

Brute-force is a simple strategy for computing ______________.

• A) Longest path
• B) Complete path
• C) Easiest path
• D) shortest path

The ancestor and descendent relation can be nicely inferred by the ______________ lemma.

• A) node
• B) addition
• C) parenthesis
• D) division

Fractional Knapsack is founded on ____________ method.

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

The Binary Tree constructed by Huffman Encoding is a:

• A) Full binary tree
• B) Incomplete binary tree
• C) None of the given options
• D) Partial binary tree

In context of activity selection algorithm, time is dominated by sorting of the activities by _________.

• A) Average Times
• B) Finish Times
• C) CPU Burst Times
• D) Start Times

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

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

If we implement the bag by using a queue, we have ________________________.

• A) Loop
• B) BFS
• C) DFS
• D) Graph

In general, the activity selection problem is to select a ___________.

• A) maximum-size set of mutually non-interfering activities
• B) maximum-size set of interfering activities
• C) minimum-size set of mutually non-interfering activities
• D) minimum-size set of interfering activities

Which of the following is true about graph?

• A) A graph may contain many edges and no vertices
• B) A graph may contain no edges and no vertices
• C) A graph may contain no edges and many vertices
• D) A graph may contain no vertices and many edges

Huffman algorithm uses a ___________________to generate a prefix code T that minimizes the expected length B(T) of the encoded string.

• A) Heuristic Approach
• B) Greedy Approach
• C) Dynamic Programming
• D) Null Approach

The running time of the traversal algorithm depends on ____________and __________ which is used for the bag.

• A) Edges, Vertices
• B) Parent Node, Child Node
• C) Graph representation, Data structure
• D) Root, Leaf

Using ASCII standard the string “greedy” will be encoded with

• A) 48 bits
• B) 44 bits
• C) 40 bits
• D) 120 bits

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

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

For a digraph G = (V, E), Sum of in-degree(v) ____________

• A) < Sum of out-degree(v)
• B) = Sum of out-degree(v)
• C) > Sum of out-degree(v)
• D) Not equal to Sum of out-degree(v)

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