FINAL EXAM COSC 320/COSC 520
Duration: 3 Hours + additional time for file download and upload
Date: April 24, 2020
This examination consists of 15 questions and is out of 100 points.
Special Instructions:
• Write your name on top of the first page of your solutions.
• When preparing your submission, sort your answers based on the question numbers. It
means first question first, followed by the second question, etc.
• Save your solutions with a file name that includes
yourFirstName_YourLastName_StudentID. The type of the file should be PDF. For
example, I will submit my final exam as Fatemeh_Fard_1234567.pdf.
• Submit all answers as ONE pdf file.
• Once finished, submit the PDF file under the assignments section on Canvas. There is
a specific assignment titled “Final Exam”. Follow the instructions on the “Final exam
guidelines.pdf” under the “Final Exam Instructions” on the course home page on Canvas
if you need help.
• The submission link is only available until 12:50 PM. The 50 minutes extra time is
allowed to prepare your submission file. So, make sure you use it properly and have enough
time to prepare the PDF file and submit your exam.
• DRC accommodation: As the submission link is not available after 12:50 PM, Your time will be calculate based on the 3 HOUR exam time, and
you have 50 minutes extra to prepare your file. For example, if you are allowed for a 2X
extension, you must submit your exam by 3:50 PM.
• Remember to start by answering the first question. Failure to answer the question 1 result
in a 0 on the exam and a report to the Dean. Print your name and sign under the first
question, specifying the date.
• I have categorized the questions as Easy, Intermediate, and Semi-Advanced. The SemiAdvanced
questions are NOT hard. They require you to think a bit more and analyze the
algorithms.
• The instructor and two TAs are available during the exam time (9:00-12:00) via zoom to
answer your questions.
• If a question is frequently asked, or a hint is required, I will send a note on Canvas
Announcement to all.
Academic honesty
Question 0) (0 points)
Write your name on first page of your solutions.
Question 1) (0 points)
Academic honesty is an expectation of all members of UBCs community, from first-year
undergraduates to professors. All UBC students are expected to behave as honest and responsible
members of an academic community. This includes, but is not limited to, never taking credit for
work completed by another individual. All tests, assignments, and other forms of assessment must
be completed by the individual being assessed, and only by the individual being assessed.
a) Do you agree to abide by the UBC expectations of academic honesty? [yes/no]
b) On page 1 of your written notes write “I hereby declare that all work within this exam is
my own and only my own.” Then print your name, sign your name, and write the date
below the declaration.
• Failure to answer this question honestly will result in a 0 on the exam and a report to the
Dean
• Failure to write the note on page 1 will result in a 0 on the exam and a report to the Dean
• Answering “no” on this question will result in a report to the Dean3
True/False, Multiple-Choice, Short Answer Questions (10 points)
Question 2) (Easy) What is the runtime of �(�) = 8� '()+ 12- + �/? Use big-O notation. (2
points)
Question 3) (Easy) An advertising company is using the information of social media websites
(e.g. Twitter) to target specific audiences for its products by using community messages. This can
happen by finding the users following each other. Note that following a person on social media is
a directional relationship. For example, person A can follow person B, but B might not be A’s
follower. The company can find such communities (group of target audiences) in �(� + �) time.
(2 points)
a) True b) False
Question 4) (Easy) Consider the following graph. What is the vector d(2) in the Bellman-Ford
algorithm, where d(2) determines the cost of the shortest path from node A with at most 2 edges?
(2 points)
Question 5) (Intermediate) You are given a sorted array of n positive integers, and a positive
integer x. Design an algorithm that finds two integer pairs of the array whose sum is closest to x.
For example, given the array A={1, 4, 5, 8, 10, 11} and integer x=20, the output is (10, 11). Note
that the pair are not necessarily consecutive. For example, given the array A={1, 4, 5, 8, 10, 11}
and integer x=16, the output is (5,10). Your algorithm should run in O(n). Write the pseudocode.
(2 points)
4
Question 6) (Easy) We consider an � × � matrix a sorted matrix with distinct integers if every
row is increasingly sorted from left to right and every column is increasingly sorted from top to
bottom. For example, the following is a sorted matrix:
3
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15;
6.1) If matrix A is a 1 × � sorted matrix, we can define an algorithm that determines whether
integer x appears in A in time. (1 point)
a) True b) False
6.2) Given an integer x, what is the running time of determining whether x appears in � × � matrix
B? Determine the running time using big-O notation and the dimensions of B (m and n). In one
sentence explain why (without explanation it worth 0 point). (1 point)
5
Recurrences (10 points)
Question 7) (10 points) (Easy)
Consider the pseudocode for an algorithm called “unknown”. It calls a helper function HELPER
whose code is not written. When HELPER(X, Y ) is called on two lists X and Y of integers, it
computes and returns an integer in time O(|X||Y| log(|X||Y|)). Here |X| means the size of list X.
unknown takes a list of integers L.
Algorithm unknown(L)
Let T(n) be the runtime for calling unknown on a list of n distinct integers, which can be written
as the following recurrence relation.
What are the values of the constants below as they correspond to the recurrence relation for the
unknown function above. Express f(n) in terms of its big-O bound.
7.1) a = ? (The answer is an integer) (2 points)
7.2) b = ? (The answer is an integer) (2 points)
7.3) f(n) = O(fill_the_blank). Explain how you calculated the run time of the algorithm
(f(n)). (1 point fill in the blank, 5 points the explanation).
6
Randomized Algorithms (10 points)
Question 8) (10 points) (Easy-Intermediate)
The following algorithm is written using randomization to find the maximum of an array A:
1: def randomizedFindMax(A):
2: while true:
3: choose a uniformly random number k in {0, …., n-1}
4: candidate = A[k]
5: #check if the candidate is the maximum
6: isMax = True
7: for j in {0, …, n-1}:
8: if candidate < A[j]:
9: isMax = False
10: break
11: if isMax:
12: return candidate
8.1) What is the expected running time of randomizedFindMax on an array of size n?
Hint: Answer the following questions to find the answer.
i. What is the probability of choosing the candidate that is a true max? (1 point)
ii. Calculate the expected number of iterations of the while loop (line 2). (2 points)
iii. What is the work required to check the max in each iteration of the while loop, in
terms of big-O notation? (2 points)
8.2) What is the worst case running time of randomizedFindMax on an array of size n? Explain.
(5 points)
Hint: Think about what can happen in line 3.
7
Graph algorithms (20 points)
Question 9) (10 points) (Easy)
There are m students who have requested to rent a room in a residency. Each student is allowed to
select a number of rooms based on his/her preferences (such as lake view, furnished room, etc.).
Each room might be selected with more than one student, and each student can select multiple
rooms. There are n vacant rooms in the residency. The residency administrator wants to match the
students and the rooms such that maximum number of students receive their preferred rooms (in
other words, as many rooms as possible are assigned to the students who have preferred them).
There is no restriction on m or n, but, for simplicity, you can consider.
9.1) Reformulate the problem with graphs. (4 points)
9.2) Define an algorithmic solution to find the maximum matching. Hint: You require to use
other algorithm paradigms taught in the class to solve the problem. (6 points)
Question 10) (10 points) (Easy-Intermediate)
There are two processors P1 and P2 that execute a list of n tasks [t1, t2, .., tn] where each task
analyzes a separate dataset. The processors have a scheduling restriction based on the tasks’
features. Some tasks must be a scheduled to run on the same processor. However, some pair of
tasks cannot be scheduled on the same processor and they must be assigned in a way that they run
on different processors. For each task t, there is list of similar(t) and different(t). The similar(t)
contains the tasks that must be scheduled to execute on the same processor. The different(t)
contains the tasks that much be scheduled to execute on different processors.
10.1) You are given a list of n tasks and the similar(t) and different(t) lists for each of the tasks.
Design an algorithm that returns the allocation of the tasks on each processor, where all the
constraints are met. Your algorithm should return “no allocation is possible” if there is no
allocation that meets the constraints. Your algorithm should run in �(� + �) time, where m
is the number of edges and n is the number of nodes. (7 points)
Hint: Think about i) how you will reformulate the problem as a graph and ii) graph traversal
algorithms to solve the problem.
10.2) Briefly explain why your algorithm is correct. (3 points)
8
Greedy algorithms (20 points)
Question 11) (10 points) (Semi-Advanced)
There are n people who want to bake a cake on April 25th, 2020. The baking for person i is
scheduled to begin at time si and end at time ei. Each person requires full access to a kitchen for
his/her baking. Two peoples’ baking times cannot be administered to be accomplished using the
same kitchen if they overlap. Two baking times i and j have overlap if
(including if a = d, so one starts exactly at the time that the other baking ends). Your task is to
design an algorithm which solves the following problem. Write the pseudocode of your algorithm.
Pay attention to the indexes of the arrays. I should be able to follow your pseudocode and achieve
the correct result.
- Given arrays A and B of length n as input, so that A[i]= a and B[i] = a, the algorithm
returns the smallest number of kitchens necessary to schedule all of the baking times as
output, and this is an optimal assignment of peoples’ baking times to kitchens.
- Hint: The running time of the algorithm is O(nlog(n) + nk) where k is the minimum
number of kitchens needed.
- For example, suppose that there are 3 people with baking times start at 12PM, 4PM, and
2PM respectively. Their baking finishes at 3PM, 6PM and 5PM respectively. The optimal
number of required kitchens is 2 (person 1 and 2 are scheduled to bake in kitchen1, and the
third person will bake in kitchen2).
Question 12) (10 points) (Easy)
A workshop about applications of machine learning on software engineering will be organized
soon. The organizers have invited n leaders to give a tutorial to the audience. The durations of the
talks are defined as g, h, … , (. Based on the survey that has been done previously, a weight is
assigned to each talk. The weight of each talk identifies its importance from the perspective of the
audience.
12.1) Your job is to develop a Greedy Algorithm for the workshop organizers that identified the
sequence of the talks. Your algorithm receives a set of n talks with their durations
g, h, … , ( and their weights g, h, … , (. The output of your algorithm is a sequence of
talks in which the sum of weighted completion times is minimized. Write the pseudocode. (5
points)
12.2) Prove that your algorithm is correct. (5 points)
9
Dynamic programming (10 points)
Question 13) (10 points) (Semi-Advanced)
Suppose that in a factory the pathways to the storage rooms are laid out in an grid. Some of
the pathways are blocked. A robot has to calculate the number of ways to go from a storage at
position ( 0,0) to a storage at position. However, the robots are programmed in
way that they can only go up and to the right. Design an algorithm that solves this problem
(Dynamic Programming Algorithm).
For example, the storage rooms and the pathways can be represented as follows. The coordinates
of some of the storage rooms are shown (The only purpose of color coding is for better
visualization). In this example, the number of pathways to go from (0,0) to (2,2) are 2.
10
Flow Networks (10 points)
Question 14) (10 points) (Easy)
Consider the following flow on a given graph. The notation X:Y means that the edge has flow X
out of capacity Y.
14.1) Consider a cut that contains set S ={s, a} as one set and T={b, t} as another set. What is the
flow f(S,T) of this cut? (1 point)
14.2) What is the capacity of the cut c(S,T) defined in part 14.1? (1 point)
14.3) Find the residual network of the flow given in this graph. (1 point)
14.4) Is the current flow at maximum? Answer explicitly. Why? (1 point)
14.5) If the current flow is not at maximum, find the augmenting path and residual capacity to
find a flow which is at maximum (Ford Fulkerson algorithm). (2 points)
14.6) Draw the graph with the updated flow obtained from part 14.5, if any. (2 points)
14.7) Draw the residual network of the updated flow from 14.6 and explain why the flow cannot
be increased any more. What is the maximum flow of the network? (2 points)
11
Your project and presentation (10 points)
Question 15) (10 points) (Easy)
15.1) Describe the topic of your presentation and your role in preparing your presentation in
2-3 sentences. (4 points)
15.2) What was your role in algorithm design, analysis, and implementation for your project?
(3 points)
15.3) Describe one learned lesson while accomplishing your project. (3 points)