CS570
Analysis of Algorithms
Fall 2011
Exam I
Name: _____________________
Student ID: _________________
____Monday ____Friday ____DEN
Maximum Received
Problem 1 20
Problem 2 16
Problem 3 14
Problem 4 20
Problem 5 10
Problem 6 20
Total 100
2 hr exam
Close book and notes
If a description to an algorithm is required please limit your description to within 150
words, anything beyond 150 words will not be considered.
https://www.coursehero.com/file/8199462/CS70MidtermExam1Fall2011/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/8199462/CS70MidtermExam1Fall2011/
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any
justification.
[ TRUE/FALSE ]
If T is a spanning tree of G and e an edge in G which is not in T, then the graph T+e
has a unique cycle.
[ TRUE/FALSE ]
Any BFS tree corresponding to a graph G=(V,E) will have exactly |V| edges.
[ TRUE/FALSE ]
A constant n0 1 exists such that for any n n0 , there exists an array of n elements
such that insertion sort runs faster than merge sort on that input.
[ TRUE/FALSE ]
If f, g, and h are positive increasing functions with f in O(h) and g in Ω(h), then the
function f+g must be in Θ(h).
[ TRUE/FALSE ]
Delete operation takes O(logn) time in the worst case in any of the 3 heaps discussed
in class.
[ TRUE/FALSE ]
By running BFS at most n times (n is the number of vertexes in G) one can find all-
pairs shortest path in an un-weighted graph G.
[ TRUE/FALSE ]
DFS Tree can never be the same as a BFS tree for a given graph.
[ TRUE/FALSE ]
The order of is O(n2 Log(n)).
[ TRUE/FALSE ]
A greedy algorithm always makes the choice that looks best at the moment.
[ TRUE/FALSE ]
Dijkstra’s algorithm will always fail in the presence of negative cost edges in the
graph.
2) 16 pts
Rank the following functions in order from smallest asymptotic complexity to largest.
Additionally, identify all pairs i, j where fi (n) = (fj (n)).
(a) fa(n) = 42n
(b) fb(n) = 1 +
(c) fc(n) = log(nn)
https://www.coursehero.com/file/8199462/CS70MidtermExam1Fall2011/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/8199462/CS70MidtermExam1Fall2011/
(d) fd(n) = nn
(e) fe(n) = log n4
(f) ff (n) =
(g) fg(n) = 37
(h) fh(n) = log 2n
3) 14 pts
Given an undirected graph G, the Line Graph GL is a graph where all edges in G
are vertices in GL. Two vertices in GL (which were edges in G) have an edge between
them if and only if their edges in G have a common endpoint.
Prove or disprove: The line graph of a bipartite graph is a bipartite graph.
4) 20 pts
Hardy decides to start running to work in San Francisco city to get in shape. He
prefers a route that goes entirely uphill and then entirely downhill so that he could
work up a sweat uphill and get a nice, cool breeze at the end of his run as he runs
faster downhill. He starts running from his home and ends at his workplace. To guide
his run, he prints out a detailed map of the roads between home and work with k
intersections and m road segments (any existing road between two intersections).
Each road segment has unit length, and each intersection has a distinct elevation.
Assuming that every road segment is either fully uphill or fully downhill, give an
efficient algorithm to find the shortest path (route) that meets Hardy’s specifications.
If no such path meets Hardy’s specifications, your algorithm should determine this.
Justify your answer.
5) 10 pts
How many times does “USC” get printed when the function Func() is called with
input m, a power of 2. Your answer is required to be in Θ( ) notation as a function of
m.
Func(n) {
if (n > 1) {
Print(USC) n times
Func(n/2)
Func(n/2)
}
return}
6) 20 pts
The citizens of Hollywood vote for their favorite film of the year. Assume there are
n = 2m citizens voting. The vote of the ith citizen is for the film V(i). A film is said to
win with majority if more than half the citizens vote for it. Assume you can answer if
V (i) and V (j) are the same film in constant time. Describe an O(n log n) algorithm to
find if a film wins with majority and if so to find that film.
https://www.coursehero.com/file/8199462/CS70MidtermExam1Fall2011/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
Powered by TCPDF (www.tcpdf.org)
https://www.coursehero.com/file/8199462/CS70MidtermExam1Fall2011/
http://www.tcpdf.org