7/22/21, 2:59 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…=102272&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 (20 pts)
There is a path from any point to any other point in a connected undirected graph.
True
False
In the Bellman-Ford algorithm, if every node keeps a pointer to the neighbor that
gives it a shortest distance to the des!na!on, a top down pass will not be required
to find shortest paths from all nodes to .
True
False
The recurrence can be solved using
Master Theorem
True
False
If , then for large values of beyond some constant , we
always have
t
T(n) = 16T(n/4) ! log nn2
f (n) = O(g(n)) n n0
f (n) ” g(n)
7/22/21, 2:59 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…=102272&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)
True
False
The merge opera!on in a binomial heap takes .
True
False
Dijkstra’s algorithm is able to find the Shortest Path in directed and undirected
graphs with posi!ve edge weights.
True
False
There are at most two stable matching solu!ons in a stable matching problem.
True
False
A correctly constructed dynamic programming algorithm maybe have an exponen!al
running !me.
True
False
!(log n)
7/22/21, 2:59 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…=102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 9 (2 points)
Ques!on 10 (2 points)
Ques!on 11 (5 points)
In a graph with posi!ve edge weights, if we add the same posi!ve weight on every
edge, Dijkstra’s algorithm will s!ll find the nodes in the same order, when star!ng
from the same source node.
True
False
In an undirected connected graph, if the cost of all edges is the same, we can use
DFS to find a minimum spanning tree.
True
False
Problem 2 (25 pts)
Which of the following has the highest !me complexity?
!( )n3
!(1. )01n
!( (log n )n2.5 )4
!( )3log n
7/22/21, 2:59 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…=102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 12 (5 points)
Ques!on 13 (5 points)
Ques!on 14 (5 points)
Assume we have the following opera!ons available on a data structure
Put, Get, Reorder. We know that Put takes constant !me in the worst case and
there is a worst-case sequence of Put, Get and Reorder opera!ons that takes
exactly !me. Which of the following statements is correct? Select all
correct statements.
Which of the following algorithms has a worst case run time complexity that is .
Consider an instance of a stable matching problem where there are three men,
and three women, . Their preference lists are
n
5n log n
Amor!zed cost of Get is .O(log n)
Amor!zed cost of Put is .O(log n)
Amor!zed cost of Reorder is .O(log n)
None of the above.
O( )n1.5
Gale-Shapley— representing the number of men and women.n
Merge sort – representing the size of the array.n
Prim algorithm on a dense graph – representing the number of nodes.n
None of the above.
, , M1 M2 M3 , , W1 W2 W3
7/22/21, 2:59 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…=102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 15 (5 points)
given below – in descending order of preference:
which one of the following is a stable matching
The total edge cost for the minimum spanning tree shown below is:
: , , M1 W1 W2 W3
: , , M2 W1 W3 W2
: , , M3 W2 W3 W1
: , , W1 M2 M1 M3
: , , W2 M3 M1 M2
: , , W3 M1 M2 M3
( , ), ( , ), ( , )M1 W3 M2 W2 M3 W1
( , ), ( , ), ( , )M1 W3 M2 W1 M3 W2
( , ), ( , ), ( , )M1 W1 M2 W2 M3 W3
( , ), ( , ), ( , )M1 W1 M2 W3 M3 W2
7/22/21, 2:59 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…=102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Problem 3 (10 pts)
26
27
28
29
7/22/21, 2:59 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…=102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 16 (5 points)
Ques!on 17 (5 points)
Describe your algorithm.
Add a File Record Audio
Analyze the complexity of your algorithm.
Add a File Record Audio
Let be an matrix of integers. Given an integer , show that the biggest
elements of the matrix can be found in .
M m # n k ” m # n
k O(k log(m # n) + m # n)
Format
Format
7/22/21, 2:59 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…=102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 18 (15 points)
Ques!on 19 (6 points)
Problem 4 (15 pts)
A circle is centered at the origin of 2-dimensional space ( and axis), and points are selected
randomly on the perimeter of the circle. Selected points are stored as an array , where each
element of the array is a point represented by its and coordinates. You may assume that points have
distinct coordinates in both dimensions. Let represent the point with the minimum coordinate
and that the vertices are ordered counter clockwise on the perimeter of the circle.
Propose an efficient algorithm with the complexity of to find the vertex with the maximum
coordinate. Describe your algorithm using pseudocode and show your complexity analysis. You do not
need to provide any proof of correctness for your algorithm.
Add a File Record Audio
Problem 5 (15 pts)
Propose an algorithm to help Mrs. T to maximize her team score. In other words, assign questions to
team students in the team such that she maximizes the number of problems that can be solved by her
x y n
V[1 … n]
x y
V[1] x
V[1 … n]
O(log n)
x
Format
Mrs. T attends a mathematics competition with a team of students. In the contest, each team is
given a set of questions, where the question has a difficulty of . Each student can
handle a certain level of question difficulty , i.e. student can only solve the question iff
. Mrs T can assign at most one question to each student to solve.
n
n ith d[i] j
s[j] j ith
d[i] ” s[j]
7/22/21, 2:59 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…=102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 20 (3 points)
team.
Add a File Record Audio
What is the worst case run time complexity of your solution?
Format
!(log n)
!(n)
!( log n)n2
!( )n3
!( )n2
!(n log n)
7/22/21, 2:59 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…102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 21 (6 points)
Ques!on 22 (5 points)
Prove the correctness of your algorithm.
Add a File Record Audio
Problem 6 (15 pts)
Define (in plain English) subproblems to be solve.
Format
Justin and Randall work at a restaurant near USC. Customers who come to the restaurant usually leave
tips (in a form of a currency note) for both of them in a tip jar. Given that there are n notes and every note
have a positive value (not necessary the same value for each note) written on it. At the end of their
workday, they arrange the notes arbitrarily from left to right on a table (this row of notes is not necessarily
sorted). They play the following game to split the tip money: they take turns to play and at each turn, the
player chooses either the leftmost note or the rightmost note and takes it. Justin is greedy and always
plays using the following strategy: “If the leftmost note has value larger than the rightmost note, then take
the leftmost note. Otherwise, take the rightmost note.” Construct a dynamic programming algorithm that
determines the plays for Randall such that the tip 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—form
left to right in an input array , i.e. is the value of the leftmost note and is the value
of the rightmost note.
v[1. . n] v[1] v[n]
7/22/21, 2:59 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…=102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Ques!on 23 (5 points)
Ques!on 24 (5 points)
Add a File Record Audio
Write the recurrence relation for subproblems.
Add a File Record Audio
Using the recurrence formula in part b, write pseudocode to compute the maximum amount of tip for
Randall. Do not forget the initialization step.
Format
Format
7/22/21, 2:59 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…102272&dnb=0&cfql=0&fromQB=0&showIncorrectOnly=1&d2l_body_type=1
Add a File Record Audio
Submit Quiz 0 of 24 ques!ons saved
Paragraph