George Mason University, Fall 2020 CS483 Algorithms Final Exam
Name: G#:
Some notes:
• This exam takes 3 hours (December 9, 2020, 7:30pm to 10:30pm)
• There are 8 problems. The total score is 100.
• Unless specified clearly, you do not have to describe in details the known algorithms that we have
learned in class, such as Ford-Fulkerson Max Flow algorithm.
• If you cheat in this exam, then you violate the academic honesty and honor code at Mason.
1
1. (12pts)
Indicate, for each pair of running time functions f(n) and g(n), show whether f(n) = O(g(n)), or
f(n) = Ω(g(n)), or f(n) = Θ(g(n)). Assume that k ≥ 1, > 0, and c > 1 are constants.
(a) f(n) = lgk n and g(n) = n
(b) f(n) = nk and g(n) = cn
(c) f(n) = 2n and g(n) = 2n/2
(d) f(n) = lg(n!) and g(n) = lg(nn)
2
2. (12pts)
Suppose that if you want to graduate from Mason, you need to take n courses and all of them are
mandatory. The prerequisite graph G has a node for each course, and an edge from a course v to a
course w if and only if v is a prerequisite for w. (A course may have more than one prerequisites.)
Find a linear time algorithm to minimize the number of semesters necessary for you to complete the
degree requirements. (Assume you can take any number of courses in one semester.)
3
3. (12pts)
During Covid-19, you stay at home and want to repair some holes on the drywalls. The problem is
formulated as below: You have n points on the real line. These n points (imagine they are small dots
with infinitely small size) have their distances to the origin as {x1, x2, . . . , xn}. You are using some
coins (or pads) to cover these points. The coins are with the same radius 1. Design an algorithm which
minimizes the number of coins used to cover all points. Prove that your algorithm is correct.
4
4. (12pts)
Covid-19 is gone and all states are reopening. You and your friend are eager to meet each other in
person. However, You two live in two different cities that are far from each other (say, Fairfax and New
York) and so you two decide to drive to meet at an intermediate city. Suppose you two simultaneously
hop in the cars and start driving toward each other.
Assume there are no red traffic lights along the routes. You two drive at the same speed. Design an
algorithm to find the city to meet so that you both meet there at the earliest time.
5
5. (13pts)
Given a sorted array of distinct integers A[1, . . . , n], you want to find out whether there is an index i
for which A[i] = i. Given an algorithm that runs in time O(log n).
6
6. (13pts)
During the shutdown period due to covid-19, you take a job to deliver foods in two cities, Fairfax and
Richmond. In each city, you know how much you can earn by delivering food in each day (yes, I know
that this assumption is not very realistic). You can drive from one city to another at night but you
have to take some time to rest so that you cannot work on the next day. For example, if you deliver
food in Fairfax on Monday and if you drive to Richmond at Monday night, then you have to rest at
home on Tuesday but you can start to work on Wednesday.
Example: The following is an example.
Monday Tuesday Wednesday Thursday Friday
Fairfax $100 $90 $30 $30 $30
Richmond $20 $20 $90 $40 $90
A good strategy is to work at Fairfax on Monday, drive to Richomond at Monday night, rest at
Richmond on Tuesday, and work at Richmod from Wednesday to Friday, with a total income of
$100 + $90 + $40 + $90 = $320.
Given a one-month table of earns on each day in each city, design an algorithm to maximize your
income with running time O(n).
7
7. (13pts)
Given two strings x = x1x2 · · ·xn and y = y1y2 · · · ym, we wish to find the length of their longest
common sub-sequence, that is, the largest value k for which there are indices i1 < i2 < · · · < ik and
j1 < j2 < · · · < jk with xi1xi2 . . . xik = yj1yj2 . . . yjk. Your algorithm should run in time O(nm).
(NOTE that a sub-sequence does not need to be continuous.)
8
8. (13pts)
Consider a n× n grid, which is is an undirected graph consisting of n rows and n columns of vertices.
We denote the vertex in the i-th row and the j-th column by (i, j). All vertices in a grid have exactly
four neighbors, except for the boundary vertices.
Given m (< n2) starting points (x1, y1), (x2, y2), . . . , (xm, ym) in the grid, the escape problem is to
determine whether or not there are m vertex-disjoint paths from the starting points to escape to any
m different points on the boundary. For example, the grid on the left has an escape, but the grid on
the right does not.
Design an algorithm to tell whether a grid has escape paths for all the starting points or not.
9

欢迎咨询51作业君