CS 170 2023 年秋季作业 1

学生根据自身情况填写即可。

(a) Midterm 1: Tuesday 10/3, 7:00pm - 9:00pm PST；Midterm 2: Tuesday 11/7, 7:00pm - 9:00pm PST；Final: Friday 12/15, 8:00am - 11:00am PST。我们不计划提供备用考试。

(b) 10:00 pm。

(c) 这 2 次 homework drops 正是为了应对你在最后一刻出现问题并错过 Gradescope 截止时间的情况。由于截止时间后不久答案就会发布，因此不会批准作业延期（homework extensions），你什么都不用做。不过，我们会对 DSP 相关原因及同时影响多周的严重情况给予例外；如果你认为自己符合条件，请联系 cs170@。

(d) 首要沟通渠道是 Edstem。

(e) 抄写并签名："I have read and understood the course syllabus and policies."（官方样例签名用了 Alan Turing。）

(a) Not OK.

(b) Not OK.

(c) Not OK。一般经验法则是：你绝不应该持有除自己解答之外的任何确切作业解答。

(d) OK。鉴于你是无意间在网上发现了该资源，请明确引用它，并确保从零写出你的解答。

(a) (i) \(\log_y x\)。 (ii) \(\ln (xy)\)。 (iii) \(\ln (x/y)\)。 (iv) \(\ln (x^{170})\)。

(b) (i) 由换底公式 \(\log_{1/x} y = \frac{\ln y}{\ln(1/x)} = \frac{\ln y}{-\ln x}\), \[x^{\log_{1/x} y} = x^{\frac{\ln y}{-\ln x}} = \bigl(x^{\frac{\ln y}{\ln x}}\bigr)^{-1}.\] 而 \(x^{\frac{\ln y}{\ln x}} = x^{\log_x y} = y\), 故整体等于 \(y^{-1} = \frac{1}{y}\)。

(ii) 设 \(S = \sum_{i=1}^{n} i = 1 + 2 + \cdots + (n-1) + n\)。将其正序与倒序相加配对： \[S = [1+n] + [2+(n-1)] + [3+(n-2)] + \cdots = \frac{n(n+1)}{2}.\]

(iii) 设 \(S_n = \sum_{k=0}^{n} a r^{k}\)。当 \(r \neq 1\) 时， \[S_n = a + ar + \cdots + ar^{n},\] \[rSn = ar + ar^{2} + \cdots + ar^{n+1}.\] 两式相减得 \((1-r) S_n = a - ar^{n+1}\), 因此 \[S_n = \frac{a - ar^{n+1}}{1-r} = a \cdot \frac{1-r^{n+1}}{1-r}.\] 当 \(r = 1\) 时，\(S_n = a + a + \cdots + a\)（共 \(n+1\) 项），故 \(S_n = a(n+1)\)。

(a) 将 \(T(n)\) 按递归树展开： \[T(n) = 10n + 3\bigl(10n/4 + 3T(n/16)\bigr) = 10n + 10\cdot\frac{3n}{4} + 10\cdot\frac{9n}{16} + 10\cdot\frac{27n}{64} + \cdots\] 该求和式为 \[T(n) = \sum_{k=0}^{\lfloor \log_{4} n \rfloor} \Bigl(\frac{3}{4}\Bigr)^{k}\cdot 10n \le \sum_{k=0}^{\infty} \Bigl(\frac{3}{4}\Bigr)^{k}\cdot 10n = \frac{1}{1-3/4}\cdot 10n = \Theta(n).\] 直观解释：每一层都有 3 个规模为 \(n/4\) 的递归调用，所以下一层输入总规模为 \(3n/4\)，即每层会"丢掉" \(1/4\) 的输入，形成收敛的等比级数，总工作量与第一层同阶，为 \(\Theta(n)\)。

(b) 答案为 \(\Theta(n)\)。与 (a) 同理：递归调用数（97）小于子问题规模的分母（100），问题规模每次减少一个常数比例（\(3/100\)），运行时间由第一层的工作量 \(\Theta(n)\) 主导，无需主定理。

(c) 递推关系为 \(T(n) = 3T(n/5) + \Theta(n^{2})\)。与 (a)(b) 思路相同，每层都会丢掉输入规模/工作量中的一个常数比例，因此答案为 \(\Theta(n^{2})\)。

(d) 画出递归树，每一层的工作量之和都是 \(\Theta(n)\)，而层数最多为 \(\log n\)，因此整体运行时间为 \(\Theta(n \log n)\)。

(e) 主定理不能直接套用。采用如下两步： 首先给出上下界：由 \(T(n) \ge 2T(n/2)\) 得到 \(T(n) \ge \Omega(n)\)；由 \(T(n) \le 2T(4n/5)\) 得到 \(T(n) \le O\bigl(n^{\log_{5/4} 2}\bigr)\)。由此猜测 \(T(n)\) 形如 \(a n^{b}\)。 由初值 \(T(1) = 1 = a\), 得 \(a = 1\), 即 \(T(n) = n^{b}\)。把它代回递推式： \[n^{b} = T(3n/5) + T(4n/5) = \Bigl(\frac{3}{5}\Bigr)^{b} n^{b} + \Bigl(\frac{4}{5}\Bigr)^{b} n^{b}.\] 两边除以 \(n^{b}\) 得到 \(\bigl(\frac{3}{5}\bigr)^{b} + \bigl(\frac{4}{5}\bigr)^{b} = 1\)。函数 \(f(b) = (3/5)^{b} + (4/5)^{b}\) 对 \(b > 0\) 单调递减，且 \(f(2) = 9/25 + 16/25 = 1\)，故唯一正解为 \(b = 2\)。因此 \(T(n) = n^{2}\)，答案是 \(\Theta(n^{2})\)。

(a) 当 \(k > d\) 时 \(f\) 不满足 (1)，因为 \(n^{d}\) 的增长严格慢于 \(n^{k}\)。

(b) 当 \(c < \lg a\) 时 \(f\) 不满足 (2)。改写 \(a^{n} = 2^{n \lg a}\) 后可见，只要 \(c\) 小于 \(\lg a\)，\(2^{cn}\) 的增长就会慢于 \(a^{n}\)。

(c) 取 \(D(n) = \lg n\)。则对任意常数 \(k\), \[f(n) = n^{\lg n} = \Omega(n^{k}),\] 因为 \((\lg n)^{2}\) 最终会超过任意常数 \(k \cdot \lg n\)。同时，对任意常数 \(c\), \[n^{\lg n} = 2^{(\lg n)^{2}} = O(2^{cn}),\] 因为 \((\lg n)^{2} = o(n)\)。 更一般地，凡满足 \(D(n) = o(n / \lg n)\) 的函数均可，因为此时 \(n^{D(n)} = 2^{\lg n \cdot D(n)} = 2^{o(n)}\)。

(a) 与 Karatsuba 算法类似，把 \(x\) 写成 \(10^{n/2}\cdot a + b\)，其中 \(a, b\) 为两个 \(n/2\) 位的十进制数。算法递归地计算 \(10^{n/2}, a, b\) 的二进制表示，然后用一次乘法和一次加法得到 \(x\) 的二进制表示。

(b) 在每一步递归上，我们把问题分成 3 个规模为一半的子问题。合并时，乘法耗时 \(O(n^{\log_{2}3})\)，加法耗时 \(O(n)\)。于是得到递推式 \[T(n) = 3T(n/2) + \bigl[O(n^{\log_{2}3}) + O(n)\bigr] = 3T(n/2) + O(n^{\log_{2}3}).\] 用主定理或画出递归树均可得到解 \(O(n^{\log_{2}3} \log n)\)。 （事实上存在 \(O(n^{\log_{2}3})\) 的算法：我们可以通过依次计算 \(10 \cdot 10,\ 10^{2} \cdot 10^{2},\ 10^{4} \cdot 10^{4}, \ldots\) 来得到 \(10^{n}\) 的二进制表示——其中 \(10^{n/2} \cdot 10^{n/2}\) 的乘法主导这段计算的总时间。这给出递推式 \(T(n) = 2T(n/2) + O(n^{\log_{2}3})\)，解为 \(T(n) = O(n^{\log_{2}3})\)。）

(c) 提供的编码实现如下：

def decimal_to_binary(decimal):
    """
    args:
        decimal: string = decimal representation of a number, passed as a string
    returns:
        A string representing the binary representation of the number
    """
    # BEGIN SOLUTION
    # base case
    if not decimal:
        return '0'
    if len(decimal) == 1 or decimal == '10':
        return digit_to_binary(decimal)

    # split the decimal into halves and recursively
    # generate the binary representation
    lhs = decimal[:(len(decimal)+1)//2]
    rhs = decimal[(len(decimal)+1)//2:]
    power_of_10 = '1' + '0'*len(rhs)

    lhs_bin = decimal_to_binary(lhs)
    rhs_bin = decimal_to_binary(rhs)
    power_of_10_bin = decimal_to_binary(power_of_10)

    # reconstruct the original number by multiplying and adding
    return add_binary(mul_binary(lhs_bin, power_of_10_bin), rhs_bin)
    # END SOLUTION

该实现将十进制串平分为两半 lhs 与 rhs，构造 \(10^{\text{len(rhs)}}\) 的字符串 power_of_10，把三者分别递归转成二进制后，用 mul_binary 与 add_binary 合并得到原数的二进制表示。