CS502 Quiz 1 by MCS

CS502 – Fundamental of Algorithms Quiz # 1 January 2021

If found any error please correct it accordingly

Q1. DFS or BFS yields a ________ of the graph.

1. Traversed Tree
2. Spanning tree page 125
3. Simple Tree
4. Free Tree

Correct answer: Spanning tree page 125

Q2. In Knapsack Problem, the goal is to put items in the knapsack such that the value of the items is _________ subject to weight limit of knapsack.

1. Minimized
2. Decreased
3. Maximized
4. None of the given options

Correct answer: Maximized

Q3. Using ASCII code, each character is represented by a fixed-length code of _________ bits per character.

1. 4
2. 6
3. 8 page 99
4. 10

Correct answer: 8 page 99

Q4. Which type of algorithm is harder to prove the correctness?

1. Greedy

google

b. Brute Force c. Dynamic Programming d. Divide and Conquer

Q5. Consider the string "abcdaacac". if the string is coded with ASCII codes, the message length would be ____________________.

1. 70 bits
2. 60 bits
3. 90 bits
4. 75 bits

Correct answer: 75 bits

8*9=72 bits is the right answer

Q6. In _________ algorithm, you hope that by choosing a local optimum at each step, you will end up at a global optimum.

1. Simple
2. Divide and conquer
3. Greedy page 97
4. Brute force

Correct answer: Greedy page 97

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

1. Not equal to Sum of out-degree(V)
2. = Sum of out-degree(v) page 115
3. < Sum of out-degree(v)
4. > Sum of out-degree(v)

Correct answer: = Sum of out-degree(v) page 115

Q8. In inductive approach of knapsack problem, we consider 2 cases, _______ Or _______.

1. Median, Mode
2. Recursive, Iterative
3. Leave object, Take object page 93
4. Sequentially, Parallel

Correct answer: Leave object, Take object page 93

Q9. A/an _________ is one in which you want to find, not just a solution, but the best solution.

1. Optimization Problem page 97
2. Divide and Conquer
3. NP Complete problem
4. Best Problem

Correct answer: Optimization Problem page 97

Q10. If the graph is represented using an adjacency matrix, then Breadth-first search takes ________ time.

1. O(E+1)
2. O(V^2) page 125
3. O(V)
4. O(E)

Correct answer: O(V^2) page 125

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

1. O(V^2)
2. O(V)
3. O(V + E)

Correct answer: O(V + E)

google

d. O(E + 1)

Q12. A graph is ________ if every vertex can reach every other vertex

1. Connected page 116
2. Cycle
3. Acyclic
4. Loop

Correct answer: Connected page 116

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

1. post-degree
2. in-degree
3. out-degree page 114
4. pre-degree

Correct answer: out-degree page 114

Q14. Huffman algorithm produces the _________ prefix code tree

1. Optimal page 105
2. Best
3. Worst
4. Better

Correct answer: Optimal page 105

Q15. A graph is said to be acyclic if it contains _____________

1. at least one cycle
2. exactly one cycle
3. always more than one cycle
4. no cycles page 116

Correct answer: no cycles page 116

Q16. Fractional Knapsack is founded on __________ method.

1. Greedy
2. Recursive
3. Dynamic Programming

Correct answer: Dynamic Programming

google and page 93

d. Divide and Conquer

Q17. If Matrix-A has dimensions "3x2" and Matrix-B has dimensions "2x3", then multiplication of Matrix-A and Matrix-B will result a new Matrix-C having dimensions

1. 3x2
2. 2x3
3. 2x2
4. 3x3

Correct answer: 3x3

Q18. Some places a person wants to visit Starting from a vertex, he wants to visit every place linked to this vertex, and so on. What algorithm does he need to use?

1. Depth First Search
2. Breadth First Search
3. Greedy Algorithm
4. Divide and Conquer

Correct answer: Breadth First Search

Q19. A Greedy algorithm can NOT be used to solve all the _______ problems.

1. Dynamic programming

google

b. Memorization programming c. Edit distance programming d. Storing value programing

Q20. In Huffman encoding, the _____ is the number of occurrences of a character divided by the total characters in the message.

1. Counting
2. Parsing
3. Relative Probability page 100
4. Weight

Correct answer: Relative Probability page 100