咨询 Alpha 小助手，获取更多课业帮助

Guidelines

Your assignment solution must be submitted as a typed PDF document. Scanned handwritten

solutions, solutions in any other format, or unreadable solutions will not be accepted or marked.

You are encouraged to learn the LATEX typesetting system and use it to type your solution. See

the course website for LATEX resources.

Your submission should be no more than 8 pages long, in a single - column US Letter or A4 page

format, using at least 9 pt font and 1 inch margins.

To submit this assignment, use the MarkUs system, at URL https://markus.teach.cs.toronto.edu/

This is a group assignment. This means that you can work on this assignment with at most one

other student. You are strongly encouraged to work with a partner. Both partners in the group

should work on and arrive at the solution together. Both partners receive the same mark on this

assignment.

Work on all problems together. If one of you writes the solution to a (sub -)problem, then the

other student should proof read it. Both members of a group are responsible for understanding

all solutions to all problems in their submission.

You may not consult any other resources except: your partner; your class notes; your textbook and assigned readings. Consulting any other resource, or collaborating with students other than

your group partner, is a violation of the academic integrity policy!

You may use any data structure, algorithm, or theorem previously studied in class, or in one of

the prerequisites of this course, by just referring to it, and without describing it. This includes any algorithm, or theorem we covered in lecture, in a tutorial, or in any of the assigned readings. Be sure to give a precise reference for the data structure/algorithm/result you are using.

Unless stated otherwise, you should justify all your answers using rigorous arguments. Your

solution will be marked based both on its completeness and correctness, and also on the clarity

and precision of your explanation.

Question 1. (11 marks)

In this question you are given as input n intervals I1 = [a1, b1],..., In = [an, bn] on the real line. Each intervals is specified by the two numbers nd . We assume that for all j. We also assume that no two intervals share any of their endpoints, i.e., all the numbers distinct. The intervals are given in two arrays.

We will say that intervals and cross if but neither interval contains the other one. In other words, and cross if exactly one of the endpoints of is contained in .

Part a. (3 marks)

Suppose that there exists some number x so that for all j, and for all j. Give an algorithm running in worst case time complexity to compute the number of pairs such that and cross. Justify your answer.

Hint: use one of the divide and conquer algorithms from class.

Part b. (8 marks)

Give a divide and conquer algorithm that computes the number of pairs such that and

cross, without making the assumption from the previous subquestion. Your algorithm should run in worst case time complexity . Justify your answer.

Part c. (7 marks)

(Bonus question - Optional). Modify your algorithm so that it runs in worst case time complexity

. Justify your answer.

Hint: Try to call any subroutine that takes time only once, rather than recursively.

Question 2. (19 marks)

In this question, you are tasked with deciding the locations for k grocery stores, to serve n houses on a street. Suppose we model the street as the interval from 0 to 1, and the locations of the houses are given as real numbers . You can assume that , i.e., the locations are sorted from left to right, and that they are given to you as an array where Each week, one of the people living in each house travels once to their closest grocery store to buy their groceries. Your goal is to compute the locations k grocery stores that minimize the total distance each household travels every week, given x and k as input.

Part a. (4 marks)

Prove that if , then the optimal location of the single grocery store is the median of .I.e., the total distance each household travels to the grocery store at location y is minimized by choosing y to be the median of . Here we define the median as follows: recalling that are sorted, the median is . So, the median of , and the median of is x2 as well. (This may not be how you have seen medians defined for n even; any of the standard definitions would work, but please stick to the one above.)

Hint: There are many ways to prove this. One possibility is to show that, for , and that the two sides of the inequality are equal when y is the median.

Part b. (5 marks)

For , let equal where y is the median of . Give an algorithm that computes all values of for all worst case time complexity (i.e., constant time per pair of i and j). Justify your answer.

Part c. (6 marks)

Give an algorithm that computes the minimum total travel distance achievable with k store locations. I.e., you need to output the minimum of over all choices of . Your algorithm should run in worst case time complexity . Use bottom - up dynamic programming, and be precise about your choice of subproblems, and the optimal substructure you are using, i.e., the recurrence (Bellman equation) satisfied by the subproblems, and its base cases. Give pseudocode for your algorithm, and justify your answers.

Hint: You can also equivalently write the objective (1) as, where the first minimum is over all ways to partition into disjoint subsets . In other words, rather than directly choosing the store locations we first choose the set of households which will go to store j, and then we choose the location of the j - th store to minimize the total distance the households in need to travel.

Part d. (4 marks)

Modify your algorithm from the previous problem to also output the choice of store locations

that minimizes the total distance travelled. Your algorithm should still run in worst case time

complexity . Justify your answer.

Question 3. (14 marks)

The Galactic Research Society (GRS) has decided to organize an interstellar expedition. The

president insists that exactly k members, including herself, join the expedition, and all selected

members are required to participate.

There are n GRS members, and they are organized in a strict hierarchical structure (i.e., a tree), 

except the president has a supervisor (their parent in the tree), and members supervise at most two other members (their children in the tree).

The society’s HR office has determined a “tension coefficient” between each member and their

supervisor. This is a real number, and represents the degree to which there is tension between the member and their supervisor: a large positive number means their relationship is quite tense and there is potential for conflict, and a negative number with large absolute value means they get along very well.

Your task is to use a dynamic programming algorithm to choose exactly k members to join the expedition such that the total tension is minimized. You can assume that k is given to you, and also that the GRS hierarchy is given to you as a rooted binary tree , and each edge of the tree is labeled by the tension coefficient . The total tension of a set of k GRS members equals the sum of the for all where u and v are both in s. I.e., we add up the tension coefficients over all pairs of a society member and their supervisor who are both selected for the expedition.