首页 >
> 详细

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
- 微信：codinghelp

- 代写cmpt 214编程、代做programming语言、代写c/C++程序 2020-11-08
- 代写csci 2122课程、代做program编程实验、C++程序语言代写代 2020-11-08
- Fit5032语言编程代做、代写web程序实验、Web、Html程序语言代做 2020-11-08
- Com3503程序编程代做、Java，C++，Python留学生编程代写代写 2020-11-08
- 代写program程序课程、代写c++编程实验、C/C++编程语言代做 代做 2020-11-08
- Data留学生编程代做、代写python程序、Java，C++程序语言代写 2020-11-08
- 代写secj 1023实验编程、Programming程序代做、代写c++语 2020-11-08
- 代写cmpsc 465编程、代做java程序语言、Python，C++编程设 2020-11-07
- 代做mf 703语言编程、代写programming程序、Sql编程语言调试 2020-11-07
- 954246编程设计调试、代做programming程序、C++编程语言代写 2020-11-07
- Pstat 115程序实验代写、R编程语言调试、Data留学生程序代做 代写 2020-11-07
- Com1005课程编程代做、代写python程序、Java，C++程序语言调 2020-11-07
- Tcp留学生程序代写、Java程序设计调试、Java编程语言代写 帮做r语言 2020-11-07
- 代写program语言编程、代做data留学生程序、Python，Java编 2020-11-07
- 代做cosc2666编程、代写programming程序、C/C++程序语言 2020-11-07
- Digital编程设计代写、代做r程序实验、代写r留学生程序 调试matla 2020-11-07
- 代写programming程序实验、R程序语言调试、Data课程编程代做 代 2020-11-07
- Comp104-17B程序代写、代做c++编程实验、C++程序语言调试 帮做 2020-11-07
- Csc8501课程程序代做、C++编程语言调试、代写program编程课程 2020-11-07
- 代写css3留学生程序、代做html、Css编程语言、Data课程程序代做 2020-11-07