这是用户在 2024-12-2 11:16 为 https://app.immersivetranslate.com/pdf-pro/bf5673ee-ac90-405a-93dd-0c592ff09153 保存的双语快照页面,由 沉浸式翻译 提供双语支持。了解如何保存?

 CS 170 作业 1

 到期的 1 / 2 6 / 2 0 2 1 , at 10:00 pm (grace period until 11:59pm) 1 / 2 6 / 2 0 2 1  , at 10:00 pm (grace period until 11:59pm)  1//26//2021" , at 10:00 pm (grace period until 11:59pm) "\mathbf{1 / 2 6 / 2 0 2 1 \text { , at 10:00 pm (grace period until 11:59pm) }}

 1个研究小组


列出您的学习组中成员的姓名和 SID。如果您没有合作者,请写“无”。

 2 课程政策


(a) 本学期 CS170 考试的日期和时间是什么?有替代考试吗?注意:我们将为遥远时区的学生提供住宿。


(b) 家庭作业的截止时间为每周二晚上 10:00,最晚截止时间为晚上 11:59。我们建议您什么时候完成作业?


© 我们提供 2 次作业投放,以应对因作业提交而可能出现的紧急情况或技术问题。如果你错过了 Gradescope 的截止日期(即使是几分钟)并且需要提交作业,你应该怎么做?


(d) CS170 接触学生的主要沟通来源是什么?我们将通过此媒介通过电子邮件发送所有重要的截止日期,您有责任检查您的电子邮件并完整阅读每条公告。


(e) 请阅读以下所有内容:


(i) 教学大纲和政策: https://cs170.org/syllabus/


(ii) 家庭作业指南:https: //cs170.org/resources/homework-guidelines/


(iii) 降级礼仪:https: //cs170.org/resources/regrade-etiquette/


(iv) 广场礼仪:https: //cs170.org/resources/piazza-etiquette/

阅读完后,将以下句子复制并在您提交的作业上签名。


“我已阅读并理解课程大纲和政策。”


3 理解学术不诚实


在回答以下任何问题之前,请确保您已仔细阅读教学大纲和课程政策 ( https://cs170.org/syllabus/ )。对于下面的每条语句,请写下 O K O K OKO K 如果课程政策允许并且不允许 O K O K OKO K 否则。


(a) 你向一位之前学过 CS 170 的朋友询问了他们的作业答案,其中一些作业与本学期的习题集重叠。您查看他们的解决方案,然后用自己的话写下来。


(b) 您同一天有 5 次期中考试,并且作业落后。你决定向已经完成作业的同学寻求帮助。他们告诉你如何做前三个问题。


© 您在线查找作业问题并找到准确的解决方案。然后你用自己的话写下来并引用来源。


(d) 你在互联网上查找 Dijkstra 的问题,并遇到了一个与你作业中的问题非常相似的网站。你阅读它,包括解决方案,然后关闭网站,写下你的解决方案,并在作业中引用网站 URL。


4 渐近复杂度比较


(a) 对以下函数进行排序,以便对于所有 i , j i , j i,ji, j , 如果 f i f i f_(i)f_{i} 出现在之前 f j f j f_(j)f_{j} 然后按顺序 f i = O ( f j ) f i = O f j f_(i)=O(f_(j))f_{i}=O\left(f_{j}\right) 。不要证明你的答案合理。
  • f 1 ( n ) = 3 n f 1 ( n ) = 3 n f_(1)(n)=3^(n)f_{1}(n)=3^{n}
  • f 2 ( n ) = n 1 3 f 2 ( n ) = n 1 3 f_(2)(n)=n^((1)/(3))f_{2}(n)=n^{\frac{1}{3}}
  • f 3 ( n ) = 12 f 3 ( n ) = 12 f_(3)(n)=12f_{3}(n)=12
  • f 4 ( n ) = 2 log 2 n f 4 ( n ) = 2 log 2 n f_(4)(n)=2^(log_(2)n)f_{4}(n)=2^{\log _{2} n}
  • f 5 ( n ) = n f 5 ( n ) = n f_(5)(n)=sqrtnf_{5}(n)=\sqrt{n}
  • f 6 ( n ) = 2 n f 6 ( n ) = 2 n f_(6)(n)=2^(n)f_{6}(n)=2^{n}
  • f 7 ( n ) = log 2 n f 7 ( n ) = log 2 n f_(7)(n)=log_(2)nf_{7}(n)=\log _{2} n
  • f 8 ( n ) = 2 n f 8 ( n ) = 2 n f_(8)(n)=2^(sqrtn)f_{8}(n)=2^{\sqrt{n}}
  • f 9 ( n ) = n 3 f 9 ( n ) = n 3 f_(9)(n)=n^(3)f_{9}(n)=n^{3}

作为答案,您可以将函数写为列表,例如 f 8 , f 9 , f 1 , f 8 , f 9 , f 1 , f_(8),f_(9),f_(1),dotsf_{8}, f_{9}, f_{1}, \ldots


(b) 在下列每一项中,请指出是否 f = O ( g ) , f = Ω ( g ) f = O ( g ) , f = Ω ( g ) f=O(g),f=Omega(g)f=O(g), f=\Omega(g) ,或两者(在这种情况下 f = Θ ( g ) f = Θ ( g ) f=Theta(g)f=\Theta(g) )。简要证明你的每个答案的合理性。回想一下,就渐近增长率而言,对数 < 多项式 < 指数。
f ( n ) f ( n ) f(n)f(n) g ( n ) g ( n ) g(n)g(n)
 (我) log 3 n log 3 n log_(3)n\log _{3} n log 4 ( n ) log 4 ( n ) log_(4)(n)\log _{4}(n)
 (二) n log ( n 4 ) n log n 4 n log(n^(4))n \log \left(n^{4}\right) n 2 log ( n 3 ) n 2 log n 3 n^(2)log(n^(3))n^{2} \log \left(n^{3}\right)
 (三) n n sqrtn\sqrt{n} ( log n ) 3 ( log n ) 3 (log n)^(3)(\log n)^{3}
 (四) n + log n n + log n n+log nn+\log n n + ( log n ) 2 n + ( log n ) 2 n+(log n)^(2)n+(\log n)^{2}
f(n) g(n) (i) log_(3)n log_(4)(n) (ii) n log(n^(4)) n^(2)log(n^(3)) (iii) sqrtn (log n)^(3) (iv) n+log n n+(log n)^(2)| | $f(n)$ | $g(n)$ | | :--- | :---: | :---: | | (i) | $\log _{3} n$ | $\log _{4}(n)$ | | (ii) | $n \log \left(n^{4}\right)$ | $n^{2} \log \left(n^{3}\right)$ | | (iii) | $\sqrt{n}$ | $(\log n)^{3}$ | | (iv) | $n+\log n$ | $n+(\log n)^{2}$ |

 5 计算阶乘


考虑计算问题 N ! = 1 × 2 × × N N ! = 1 × 2 × × N N!=1xx2xx cdots xx NN!=1 \times 2 \times \cdots \times N


(一个) N N NN log N log N log N\log N 位长(这是需要多少位来存储大小为 N ) N ) N)N) 。找到一个 f ( N ) f ( N ) f(N)f(N) 以便 N ! N ! N!N! Θ ( f ( N ) ) Θ ( f ( N ) ) Theta(f(N))\Theta(f(N)) ) 位长。尽可能简化你的答案,并论证为什么它是正确的。

注意:您不能使用斯特林公式。


(b) 给出一个简单(朴素)的算法来计算 N N NN !.您可以假设将两个位相乘(例如 0 × 0 , 0 × 1 0 × 0 , 0 × 1 0xx0,0xx10 \times 0,0 \times 1 ) 需要 1 个时间单位。

请给出算法描述和运行时分析。

 6 多项式计算


给定系数 a 0 , , a n N a 0 , , a n N a_(0),dots,a_(n)inNa_{0}, \ldots, a_{n} \in \mathbb{N} ,考虑多项式:
p ( x ) = k = 0 n a k x k p ( x ) = k = 0 n a k x k p(x)=sum_(k=0)^(n)a_(k)x^(k)p(x)=\sum_{k=0}^{n} a_{k} x^{k}

对于这个问题,假设两个自然数的加法和乘法只需要 O ( 1 ) O ( 1 ) O(1)\mathcal{O}(1) 时间(无论它们有多大)。


(a) 描述一个简单的算法,给定 [ a 0 , , a n ] a 0 , , a n [a_(0),dots,a_(n)]\left[a_{0}, \ldots, a_{n}\right] x x xx ,计算 p ( x ) p ( x ) p(x)p(x) 。分析其运行时间与多项式次数的关系 n n nn


(b) 作为替代方案,我们可以计算以下表达式:
p ( x ) = a 0 + x ( a 1 + x ( a 2 + + x ( a n 1 + x a n ) ) ) p ( x ) = a 0 + x a 1 + x a 2 + + x a n 1 + x a n p(x)=a_(0)+x(a_(1)+x(a_(2)+dots+x(a_(n-1)+x*a_(n))dots))p(x)=a_{0}+x\left(a_{1}+x\left(a_{2}+\ldots+x\left(a_{n-1}+x \cdot a_{n}\right) \ldots\right)\right)

描述并分析使用上述表达式计算多项式的算法。运行时间应该是一个函数 n n nn 以及。


按照作业指南中的描述给出由 3 部分组成的解决方案。