Scribd
Upload
21 views

Algorithm 2016 Fall Quiz

1. The document is a quiz on algorithms consisting of 9 questions covering topics like: - Breadth-first search time complexity - Finding strongly connected components in a directed graph - Matrix chain multiplication dynamic programming algorithm - Knapsack problem solutions 2. Questions involve algorithms like DFS, BFS, dynamic programming, greedy algorithms and analyzing their properties, running times and solving problems using the algorithms. 3. The quiz tests understanding of fundamental graph algorithms and optimization problems like knapsack and their algorithmic solutions.

Uploaded by

woogie boogie
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views

Algorithm 2016 Fall Quiz

1. The document is a quiz on algorithms consisting of 9 questions covering topics like: - Breadth-first search time complexity - Finding strongly connected components in a directed graph - Matrix chain multiplication dynamic programming algorithm - Knapsack problem solutions 2. Questions involve algorithms like DFS, BFS, dynamic programming, greedy algorithms and analyzing their properties, running times and solving problems using the algorithms. 3. The quiz tests understanding of fundamental graph algorithms and optimization problems like knapsack and their algorithmic solutions.

Uploaded by

woogie boogie
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Algorithm 2016 fall

Quiz
1. (10%) Illustrate the BREATH-FIRST SEARCH algorithm and analysis its time
complexity.

2. (10%) Find the strongly connected components on a directed graph in Figure 1.

Fig 1
Figure
Figure 2

3. (20%) (1) (10%) The matrix-chain multiplication problem can be stated as follows:
Given a chain <A1, A2,…, An> of n matrices, where for i=1,2,…,n, matrix Ai has
dimension pi-1 pi, fully parenthesize the product A1A2......An in a way that
minimizes the number of scalar multiplications. Give a dynamic-programming
algorithm to solve the problem and analyze its time complexity. (write pseudo
code)

(2) (10%) Suppose that you have 6 matrices: A1 has dimension 30 x 35, A2 has
dimension 35 x 15, A3 has dimension 15 x 5, A4 has dimension 5 x 10, A5 has
dimension 10 x 20, A6 has dimension 20 x 25. Please use your algorithm to
calculate the minimum number of scalar multiplications.(write table and answer)

4. In the algorithm SELECT, the input elements are divided into groups of 5. Will
the algorithm work in linear time if they are divided into groups of 7? Argue that
SELECT does not run in linear time if groups of 3 are used.

5. (10%) Using the depth-first-search algorithm DFS on an undirected graph in


Figure 2. Vertices are timestamped by discovery time/finishing time. (draw your
answer)
6. Consider the knapsack problem consists of 3 items, and the capacity of the
knapsack is equal to 8. The profits and weights of the three items are (p1, p2, p3)
= (8, 6, 3) and (w1, w2, w3) = (6, 5, 3), respectively.
Assume that you are allowed to put in a fraction of an item. Use the greedy
method to solve for the maximum profit and show the items to be included in the
knapsack.

7. Consider the following sentence:


In a dynamic programming solution, the space requirement is always at least as
big as the number of unique sub-problems.
Is it correct? Please give a short answer briefly (you can give an example to
explain your answer)

8. True or false
(I) 0-1 knapsack problem can be solved by greedy strategy
(II) In undirected graph, we apply DFS algorithm and we can get tree edges and
cross edges
(III) In top-down approach, memorization is a way to reduce some time cost in
exchange for space cost
(IV) Unweighted longest simple path problem does not satisfy the optimal
sub-structure
(V) If we apply topology sort for a directed graph, then using DFS on this graph
will produce no back edges

9. Consider the following table.


𝐢𝐭𝐞𝐦 𝐢 1 2 3 4 5 6 7
𝒗𝒂𝒍𝒖𝒆𝒊 8 6 15 3 2 5 9
𝒘𝒆𝒊𝒈𝒉𝒕𝒊 2 3 5 4 3 2 6
Imaging that you have a travel and the maximum weight of your knapsack is 16.
Now, you cannot take any fraction of an item. It means that you cannot take any
item partially. What is the optimal value of items that you can choose into your
knapsack?

You might also like