CS502 Quiz 1 by Junaid

Which method is preferable for dealing with chain matrix multiplication?

i. Divide and conquer strategy ii.

Dynamic programming formulation

iii. Graph theory iv. Greedy Approach

i. Better ii.

Optimal

iii. Worst iv. Best

A….w is adjacent to vertex v if there is an edge from v to w. i. Acyclic ii.

Vertex

iii. Loop iv. Cycle

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

i. 44 bits ii. 120 bits iii. 40 bits iv.

48 bits

Find the maximum value of the items which can carry using knapsack weight capacity =50

Item weight Value

i. ii. iii. iv.

In activity scheduling algorithm, each activity is represented by a

i.

Rectangle

ii. Square iii. Circle iv. Triangle

Those problems in which greedy finds good, but not always best is called a greedy….. i.

Heuristic

ii. Solution iii. Result iv. Algorithm

The knapsack problem belongs to the domain of…..Problems

i. Searching ii. Sorting iii. Linear solution iv.

Optimization

The general coin change problem can be solved using

i. Recursion ii. Greedy algorithm iii. iv.

i.

Optimal

ii. Better iii. Best iv. Worst

Huffman algorithm generates an optimum …..code

i. Postfix ii. Infix iii. None of the given options iv.

Prefix

There are …..ways of representing graphics

i. ii. iii. iv.

Knapsack word originates from ……language

i.

German

ii. English iii. French iv. Norwegian

Graphs are important…….model for many application problems

i.

Mathematical

ii. Unpredictable iii. Haphazard iv. Unsystematic

Which type of algorithm is harder to prove the correctness?

i. Dynamic ii. Greedy iii. iv.

…..Items are not allowed in 0/1 knapsack problem

i. ii. iii. iv.

Matrix multiplication is a(n)……..operation

i. Nether commutative nor associative ii. Transitive iii. Commutative iv.

Associative

For a Diagraph G= (V.E), Sum of in-degree (v) -----------------. Not equal to sum of out-degree(v) = sum of out-degree(v) pg#115 < sum of out-degree(v) > sum of out-degree(v)

DFS or BFS yields a-------------of the graph. Traversed tree Spanning tree pg#125 Simple tree Free tree

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

8 pg#100

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 the Knapsack. Minimized Decreased Maximized pg#109 None of the above given