CS502 Solved Quiz 1 by VUBuddy

WMIg3Q

CS502 QUIZ 1 SOLVED

1. DFS or BFS yields a _ _ of the graph.

Traversed Tree

b) Spanning tree

c. Simple Tree d. Free Tree

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

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

1. 4
2. 6

WMIg3Q

c) 8

d) 10

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

1. Greedy
2. Brute Force
3. Dynamic Programming
4. Divide and Conquer

Correct answer: Greedy

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 are 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

Correct answer: Greedy

WMIg3Q

d) Brute force

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)
3. < Sum of out-degree(v)
4. > Sum of out-degree(v)

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

8. In inductive approach of knapsack problem, we consider 2 cases,

Or a) Median, Mode b) Recursive, Iterative

c) Leave object, Take object

d. Sequentially, Parallel

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

a) Optimization Problem

b) Divide and Conquer c) NP Complete problem d) Best Problem