首页 >
> 详细

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)

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Tsp课程作业代写、代做algorithms留学生作业、代做java，C/C 2020-06-23
- Kit107留学生作业代做、C++编程语言作业调试、Data课程作业代写、代 2020-06-23
- Sta302h1f作业代做、代写r课程设计作业、代写r编程语言作业、代做da 2020-06-22
- 代写seng 474作业、代做data Mining作业、Python，Ja 2020-06-22
- Cmpsci 187 Binary Search Trees 2020-06-21
- Comp226 Assignment 2: Strategy 2020-06-21
- Math 504 Homework 12 2020-06-21
- Math4007 Assessed Coursework 2 2020-06-21
- Optimization In Machine Learning Assig... 2020-06-21
- Homework 1 – Math 104B 2020-06-20
- Comp1000 Unix And C Programming 2020-06-20
- General Specifications Use Python In T... 2020-06-20
- Comp-206 Mini Assignment 6 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Mech 203 – End-Of-Semester Project 2020-06-20
- Ms980 Business Analytics 2020-06-20
- Cs952 Database And Web Systems Develop... 2020-06-20
- Homework 4 Using Data From The China H... 2020-06-20
- Assignment 1 Build A Shopping Cart 2020-06-20