8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 1 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…=104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 1 (2 points)
Ques!on 2 (2 points)
Ques!on 3 (2 points)
Ques!on 4 (2 points)
Problem 1. True/False (20 pts)
If P = NP, then all problems in NP are NP hard.
True
False
.
True
False
If a polynomial-!me algorithm is found for the special case of the traveling salesman
problem where triangle inequali!es hold, then we have proven that P=NP.
True
False
Bellman-ford will always fail to find the shortest path between two nodes if the
graph contains a nega!ve cycle.
True
False
n ! O( log n)n2 log3 n2
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 2 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…=104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 5 (2 points)
Ques!on 6 (2 points)
Ques!on 7 (2 points)
Ques!on 8 (2 points)
Ques!on 9 (2 points)
Prim algorithm can always get the correct Minimum Spanning Tree even if there are
nega!ve-weight edges in the connected graph.
True
False
The number of itera!ons in the Ford-Fulkerson algorithm could change based on
whether we use BFS or DFS to find an augmenta!on path at each itera!on.
True
False
Max flow problem in a flow network with integer capaci!es can be solved exactly
using linear programming in polynomial !me.
True
False
There is a polynomial !me algorithm for the subset sum problem if all items have size
of 1 regardless of the number of bits required to represent W (the size of the
knapsack).
True
False
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 3 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…=104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 10 (2 points)
Ques!on 11 (5 points)
If a data structure adds new items in in worst case, then the worst-case
!me for adding a single item can be as large as in this data structure.
True
False
If all capaci!es of edges in a network are unique, there is a unique min-cut for this
network.
True
False
Problem 2. Mul!-Choice (25 pts)
What’s the value of the maximal flow?
n !(n log n)
!(n log n)
For the following network, with edge capaci!es as shown,
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 4 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…=104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 12 (5 points)
Ques!on 13 (5 points)
Which of the following is a min-cut?
Assuming that , which of the following statements is true?
10
13
14
16
None of the above.
{S, A, B, C, D, E, G}, {F, T}.
{S, A, C, F}, {B, D, E, G, T}.
{S, C, F}, {A, B, D, E, G, T}.
{S, A, C, D, F}, {B, E, G, T}.
More than one above.
P ” NP
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 5 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…=104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 14 (5 points)
Ques!on 15 (5 points)
Assuming that , for the complexity classes P, NP, NP-Complete, and NP-
Hard, which of the following statements are correct? Select all correct statements.
if , which of the following decision problems are in the class P? Select all
correct statements.
If , and is NP-complete, then is NP-complete.X # p Y X Y
3-SAT cannot be solved in polynomial !me.
Although the general Travelling Salesman Problem is NP-complete, in class, we
presented a 2-approxima!on algorithm for it that runs in polynomial !me.
None of the above.
P ” NP
P belongs to NP.
P belongs to NP-Complete.
NP belongs to NP-Hard.
NP-Hard belongs to NP.
P ” NP
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 6 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…=104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 16 (15 points)
Problem 3
Prove or disprove that the following problem is NPC.
Given an undirected graph G = (V, E) with posi!ve edge weights, find a simple
cycle (a cycle that has no duplicate nodes) and has a total edge cost of at least D.
Add a File Record Audio
In a weighted undirected graph with posi!ve and nega!ve edge costs, is there a
simple path between to with cost at most ?S T C
In a weighted directed graph with posi!ve and nega!ve edge costs, and no
nega!ve cycle, is there a simple path between to with cost at most ?S T C
Given a flow network, is there a flow of value at least from to ?X S T
In a weighted directed graph with posi!ve edge costs, is there a simple path
between to with cost at least ?S T C
Format
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 7 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…=104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 17 (5 points)
Ques!on 18 (10 points)
Problem 4
Consider the following algorithm to choose those cameras that need to stay on:
At each stage, select the camera that covers the greatest number of uncovered
cells.
Show a counter example to prove that this algorithm does not always give the
op!mal solu!on.
Add a File Record Audio
Prove that if we used the above algorithm as an approxima!on algorithm, this
approxima!on algorithm has no constant approxima!on ra!o > 1. In other words, if
In a prison, each cell is being protected and monitored by a set of security cameras. A
cell might be monitored by more than one security camera and a security camera can
be also monitoring more than one cell. This year they are !ght on budget and they
want to reduce the electricity usage and maintenance cost by turning off some of the
cameras but they also want to make sure that each cell is being monitored by at least
one camera.
Format
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 8 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…=104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
the minimum number of cameras needed is , prove that there is no constant
, where we can guarantee our greedy algorithm to achieve an
approximate solu!on with total number of cameras .
Add a File Record Audio
Problem 5
C$
” (” > 1)
# “C$
Format
Remember Jus!n and Randall who work at a restaurant near USC? Here is a
reminder about how they split their !ps:
Customers who come to the restaurant usually leave !ps (in a form of a currency
note) for both of them in a !p jar. Given that there are n notes and every note have a
posi!ve value (not necessary the same value for each note) wri#en on it. At the end
of their workday, they arrange the notes arbitrarily from le$ to right on a table (this
row of notes is not necessarily sorted). They play the following game to split the !p
money: they take turns to play and at each turn, the player chooses either the
le$most note or the rightmost note and takes it. Jus!n is greedy and always plays
using the following strategy: “If the le$most note has value larger than the rightmost
note, then take the le$most note. Otherwise, take the rightmost note.” Construct a
dynamic programming algorithm that determines the plays for Randall such that the
!p money he gets is maximized. Assume n is even and Randall plays the first turn.
We also assume that the values for the notes are given to us—in order—from le$ to
right in an input array , i.e. is the value of the le$most note and is
the value of the rightmost note.
v[1. . n] v[1] v[n]
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 9 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…=104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 19 (5 points)
Ques!on 20 (3 points)
Assuming that is the maximum amount of money that Randall can get
from the remaining note sequence write the recurrence rela!on for
subproblems.
Add a File Record Audio
How will you ini!alize the array? You do not need to write the complete
pseudocode.
The restaurant has now hired a busboy to help set and clear tables and Jus!n and
Randall have decided that they want to change their game the following ways:
– Jus!n Plays the first turn
– The last two notes le$ on the table will go to the busboy.
OPT(i, j)
i, . . . , j
Format
OPT
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 10 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 21 (2 points)
Ques!on 22 (15 points)
Add a File Record Audio
To find the value of the op!mal solu!on for this problem a minimum of
memory is required.
True
False
Problem 6
Suppose that you are managing a car dealership, and your job is to connect sales
agents with the right sellers and buyers. There are sales agents, sellers each
selling a car, and buyers each buying a car. Each buyer has either a low, medium or
high credit history. Let us assume that the only factor which ma#ers is the credit
history of buyers and the credit history requirement of sellers for a deal to be
successful according to the following rules:
(a) High credit buyers can buy from sellers with low, medium, or high credit
requirements.
(b) Medium credit buyers can only buy from sellers with low and medium credit
Format
!( )n2
k n
m
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 11 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
requirements.
(b) Low credit buyers can only buy from sellers with low credit requirements.
To make things fair for sales agents, you want to spread buyers with different credit
ra!ngs across different sales agents the following way: Each sales agent can do at
most
deals with high credit buyers
deals with medium credit buyers
deals with low credit buyers
Where are posi!ve integers. Give a network flow algorithm to find
the assignment of buyers to sales agents such that it results in the maximal number
of possible deals.
Add a File Record Audio
Submit Quiz 0 of 22 ques!ons saved
i
H(i)
M(i)
L(i)
H(i), M(i), L(i)
Paragraph
8/10/21, 3:00 PMQuiz – CSCI570(Shamsian) – 20212 – Analysis of Algorithms – USC Viterbi School of Engineering
Page 12 of 12https://courses.uscden.net/d2l/lms/quizzing/user/attempt/quiz_att…104996&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1