截止日期：9月30日，午夜
指南：（请完整阅读！）
- 你的作业解决方案必须以打字的PDF文档形式提交。扫描的手写解决方案、任何其他格式的解决方案或难以辨认的解决方案将不被接受或评分。我们鼓励你学习LATEX排版系统并使用它来输入你的解决方案。请参阅课程网站获取LATEX资源。
- 你的提交内容不应超过8页，采用单列美国信纸或A4页面格式，使用至少9点字体和1英寸页边距。
- 要提交此作业，请使用MarkUs系统，网址为https://markus.teach.cs.toronto.edu/
- 这是一个小组作业。这意味着你最多可以与另外一名学生一起完成此作业。我们强烈鼓励你与伙伴合作。小组中的两个成员应共同努力并得出解决方案。两个成员在本作业上将获得相同的分数。
- 一起解决所有问题。如果你们中的一人写下了某个（子）问题的解决方案，那么另一名学生应进行校对。小组的所有成员都应对提交的所有问题的所有解决方案负责。
- 除了你的伙伴、你的课堂笔记、你的教科书和指定的阅读材料外，你不得参考任何其他资源。参考任何其他资源或与小组伙伴以外的学生合作，均违反学术诚信政策！
- 你可以使用之前在课堂上或本课程的任何先修课程中学习过的数据结构、算法或定理，只需引用它们，而无需描述它们。这包括我们在讲座、教程或任何指定阅读材料中涵盖的任何算法或定理。请确保对你使用的数据结构/算法/结果给出精确的引用。
- 除非另有说明，否则你应使用严格的论证来证明你所有的答案。你的解决方案将根据其完整性和正确性，以及你解释的清晰度和精确度进行评分。
问题1.（11分）
在这个问题中，你将得到实线上的n个区间I1 = [a1, b1]，…，In = [an, bn]作为输入。每个区间$I_{j}$由两个数$a_{j}$和$b_{j}$指定。我们假设对于所有j，$a_{j} < b_{j}$。我们还假设没有两个区间共享它们的任何端点，即所有的数$a_{1}，…，a_{n}，b_{1}，…，b_{n}$都是不同的。这些区间在两个数组A[1…n]和B[1…n]中给出，其中$A[j] = a_{j}$，$B[j] = b_{j}$。
我们说区间$I_{j}$和$I_{k}$交叉，如果$I_{j} \cap I_{k} ≠ \emptyset$，但两个区间都不包含另一个。换句话说，如果$I_{k}$的恰好一个端点包含在$I_{j}$中，那么$I_{j}$和$I_{k}$交叉。
部分a.（3分）
假设存在某个数x，使得对于所有j，$a_{j} < x$，并且对于所有j，$b_{j} > x$。给出一个在最坏情况下时间复杂度为$O(n log n)$的算法来计算满足$j < k$且$I_{j}$和$I_{k}$交叉的对数。证明你的答案。
提示：使用课堂上的一种分治算法。
部分b.（8分）
给出一个分治算法来计算满足$j < k$且$I_{j}$和$I_{k}$交叉的对数，而不使用前一个子问题中的假设。你的算法应在最坏情况下的时间复杂度为$O(n log ^{2} n)$。证明你的答案。
部分c.（7分）
（加分问题 – 可选）。修改你的算法，使其在最坏情况下的时间复杂度为$O(n log n)$。证明你的答案。
提示：尝试仅调用一次时间复杂度为$O(n log n)$的任何子例程，而不是递归调用。
问题2.（19分）
在这个问题中，你需要为k家杂货店确定位置，以服务于街道上的n所房屋。假设我们将街道建模为从0到1的区间，并且房屋的位置由实数$x_{1}，…，x_{n} \in [0,1]$给出。你可以假设$x_{1} < x_{2}… < x_{n}$，即位置是从左到右排序的，并且它们以数组$x[1…n]$的形式提供给你，其中$x[i] = x_{i}$。每周，每个房屋中的一个人会前往最近的杂货店购买食品杂货。你的目标是计算$y_{1}，…，y_{k} \in [0,1]$这k家杂货店的位置，以使每个家庭每周旅行的总距离最小，给定x和k作为输入。
部分a.（4分）
证明如果$k = 1$，则单个杂货店的最佳位置是$x_{1}，…，x_{n}$的中位数。即，通过选择y为$x_{1}，…，x_{n}$的中位数，可以最小化每个家庭前往杂货店位置y的总距离$\left|x_{1} – y\right| +… + \left|x_{n} – y\right|$。在这里，我们定义中位数如下：回想一下，$x_{1} <… < x_{n}$是排序的，中位数是$x_{\lceil(n + 1) / 2\rceil}$。因此，$x_{1} < x_{2}$的中位数是$x_{2}$，$x_{1} < x_{2} < x_{3}$的中位数也是x2。（这可能不是你之前看到的对于n为偶数时中位数的定义；任何标准定义都可以，但请坚持使用上面的定义。）
提示：有很多方法可以证明这一点。一种可能性是证明，对于$x_{1} ≤… ≤ x_{n}$，$\left|x_{1} – y\right| +… + \left|x_{n} – y\right| \geq\left|x_{n} – x_{1}\right| + \left|x_{n – 1} – x_{2}\right| +… + \left|x_{\lceil(n + 1) / 2\rceil} – x_{\lfloor(n + 1) / 2\rfloor}\right|$，并且当y是中位数时，不等式的两边相等。
部分b.（5分）
对于$1 ≤ i ≤ j ≤ n$，令$M[i, j]$等于$|x_{i} – y| +… + |x_{j} – y|$，其中y是$x_{i}，…，x_{j}$的中位数。给出一个算法，在最坏情况下的时间复杂度为$O(n^{2})$（即每对i和j的常数时间）计算所有$M[i, j]$的值。证明你的答案。
部分c.（6分）
给出一个算法，计算使用k个商店位置可实现的最小总旅行距离。即，你需要输出在所有选择的$y_{1}，…，y_{k} \in [0,1]$上，$min {j = 1}^{k}\left|x{1} – y_{j}\right| +… + min {j = 1}^{k}\left|x{n} – y_{j}\right|$的最小值。你的算法应在最坏情况下的时间复杂度为$O(k n^{2})$。使用自底向上的动态规划，并明确你选择的子问题，以及你使用的最优子结构，即子问题满足的递归（贝尔曼方程）及其基本情况。给出你的算法的伪代码，并证明你的答案。
提示：你也可以等效地将目标（1）写为$min {X{1}，…，X_{k}}\left{min {y{1} \in [0,1]}\left(\sum_{i \in X_{1}}\left|x_{i} – y_{1}\right|\right) +… + min {y{k} \in [0,1]}\left(\sum_{i \in X_{k}}\left|x_{i} – y_{k}\right|\right)\right}$，其中第一个最小值是在所有将$x_{1}，…，x_{n}$划分为不相交子集$X_{1}，…，X_{k}$的方式上。换句话说，我们不是直接选择商店位置$y_{1}，…，y_{k}$，而是首先选择将前往商店j的家庭集合$x_{j}$，然后选择第j家商店的位置$y_{j}$，以最小化$x_{j}$中家庭需要旅行的总距离。
部分d.（4分）
修改你之前问题的算法，以输出最小化总旅行距离的商店位置$y_{1}，…，y_{k}$的选择。你的算法仍然应在最坏情况下的时间复杂度为$O(n^{2} k)$。证明你的答案。
问题3.（14分）
银河研究协会（GRS）决定组织一次星际探险。主席坚持要求正好k名成员，包括她自己，参加探险，并且所有选定的成员都必须参加。
有n名GRS成员，他们组织在一个严格的层次结构（即一棵树）中，主席在根节点。每个协会成员都表示为树中的一个节点。除主席外的每个成员都有一个主管（他们在树中的父节点），并且成员最多监督另外两个成员（他们在树中的子节点）。
协会的人力资源办公室确定了每个成员与其主管之间的“紧张系数”。这是一个实数，表示成员与主管之间紧张程度的程度：一个大的正数意味着他们的关系非常紧张，存在冲突的潜在可能性，而一个绝对值较大的负数意味着他们相处得非常好。
你的任务是使用动态规划算法选择正好k名成员参加探险，以使总紧张程度最小。你可以假设k（$1 ≤ k ≤ n$）已提供给你，并且GRS层次结构也已作为根二叉树$T = (V, E)$提供给你，树的每个边$e = (u, v) \in E$都由紧张系数$t_{e} = t_{u, v}$标记。k个GRS成员的集合$S \subseteq V$的总紧张程度等于所有$e = (u, v)$的$t_{e}$之和，其中u和v都在s中。即，我们将所有同时被选为探险的协会成员和他们的主管之间的紧张系数相加。
部分a.（7分）
定义你正在使用的子问题结构，并指定每个子问题满足的递归关系，以及递归的基本情况。假设“较小”子问题的值已经计算出来，递归关系应允许你快速（肯定在多项式时间内）计算子问题的值。证明递归关系。
部分b.（3分）
使用你在前一个问题中得到的递归关系，给出一个自底向上的动态规划算法，计算包括主席（树的根节点）在内的k个GRS成员的最小可能总紧张程度。你的算法应在总GRS成员数n的多项式时间内运行。给出你的算法的伪代码，并分析其最坏情况下的运行时间。
部分c.（4分）
修改你之前子问题的算法，以输出包括主席在内的最小化总紧张程度的k个GRS成员的集合S。分析修改后的算法的最坏情况下的运行时间。