type
status
date
slug
summary
tags
category
icon
password
2 的整体难度比 1 低了很多，是拿高分的好机会！
那么大家跟着我的思路，Go,Go,Go 出发咯！
❗❗请不要在 Applied 课上拿出笔记❗❗
更新日志
（上次更新2025年5月18日）
重点新增
2025年5月12日 - 发布了题目
1,2,3,4 的笔记。2025年5月13日 - 发布了题目
5 的笔记。2025年5月15日 - 发布了题目
6,7,8 的笔记。 - 修复了超链接显示问题。
2025年5月18日 - 发布了题目
9 的笔记。内容分析
想要做出题目，首先先要了解这个题在讲什么？
最少把题读懂了吧…
做每道题之前，先把题目之前的阅读内容读了。不然看得懂问题就怪了。
主要覆盖内容
Modules 3,4,6 and 7
- 逻辑门
- 时间复杂度
- 布尔运算
- 归纳法()
- 数论( 类)
题目分析
第一题
通过题目上方的内容我们知道了 和 的定义。
想要做出这道题，我们需要考虑的是 与 和 的关系，
我们可以排列出的所有可能(i.e. 1 或者 0) 来建立它们之间的关系。
考虑情况
默认式子 | 当 | 当 |
通过列出所有的可能性，我们可以看出它们之间的关系，列出式子 + 画图 第一题的a,b俩问就都好了。
第二题
读完第二题上方的内容，我们知道了两位数进一的式子可以被理解成
在理解了表达式以后，我们回忆一下FIT 1047中逻辑门的画法，理解parallelism的含义，第二题就送分了。
第三题
又是一段阅读，其中我们需要理解的是这个one-bit selector - 这个东西非常重要，在后续的题目中会反复的用到它。
理解关键式子表达的隐藏含义。
(再往后写就直接给答案了)
然后同样的再画上逻辑门，这题就解决了。
第四题
读完题目上的阅读，我们理解了第三题中 one-bit selector是服务于N-bits selector的，
其中N-bits selector 可以被拆分成若干个小型的 one-bit selector。
尝试将一个1-bit selector画出来后思考如何将它变成2-bit版本的就可以找到答案了。
1-bit 版本
2-bits 版本
思考版本分别需要的时间，以及如何拓展成3-bits，以及时间。
第五题
解题思路
第五题是前几题学到的 2-bit incrementor 以及 n-bit selector 的杂交版。思考这一题我们需要考虑的是 如何将一个大问题分解成小问题，小问题分解成更小的问题，直到我们可以解决（即.递归思路）。
这里以 8-bit 举例如何将大问题拆解成我们可以解决的问题。 表示根据右边是否进位选择是否+1
8-bit的时候
我们现在还没有能力处理4-bit的情况，所以继续拆解。
4-bit的时候
我们直到如何单独处理一个2-bit - 同第二题
开始回溯
现在我们可以理解成位数的进1可以被拆解成若干个小型的2-bit 进一，通过selector相连（）。
可视化（帮助理解）
我们以直单个的时间消耗为1单位（第二体），单个的时间小单为3单位(第四题）。所以找到 bits的时间消耗递增的规律就可以找到的表达式。
4-bits 进一
8-bits 进一
16-bits 进一
注意事项
- 需要注意的是- 当k=1的时候，是2位进一; 当k=0的时候，才是1位进一。
表达式
所以通过上述的思路我们可以列出表达式。
多多观察可视化进位里面每次新增加的内容，找到表达式也就不难了。
第六题
Prove By Induction 已经出现过很多次了。写出来以后，多注意一下格式 就可以拿满分了。
格式推荐
这里推荐 ED 示例上的格式，超链接
得分点
在上图中，几个比较重要的得分点如下。
- Base Case 的证明
- Inductive step
- 必须先声明 再假设
- 推断步骤 - Deduce 的情况
- 通过 从而推到
- By the I.H 这一步写出来
- 结论
Induction 只要不偷懒，是最好拿分的了。得分点查漏补缺，最好写的时候明显一些（写个小标题告诉老师你在做什么这类的）
第七题
第七题算我们接触最少的Big-O。Big-O 快速了解见，超链接
第一部分
这个部分没什么好讲的，跟着老师的例子带一个能用的进去就好了。
注意好格式的一些内容不要忘了
然后再证明
第二部分
思考
此部分为第一部分的进阶版。唯一难点是考虑 所有 和 的关系。
其中我们可以通过 的方法来获的关系。
剩余的 Big-O 同第一部分一样，得到的式子常数项可以通过Big-O 舍去。
难点在于如何化简掉ceiling(i.e. )。
第二部分属于Prove that 问题，这类题是不可以直接用答案去反推过程的，也就是过程中不可以使用题目中给的答案。
化简提示
如果你学过一些数论或者接触过一些Big-O什么的，
或者你有着惊人注意力，你就可以注意到 ↓
当 的时候：
第八题
这题为了防止大家做着做着偏离航道，有给答案。
但是只写答案是没有分的！！
第一部分
题目要求我们找到
我们可以直接参考 Applied Session 7 中的第13题，超链接
我们这题的解题方法可以参考Problem 13的答案步骤，超链接
参考解题步骤，将 带入上述的公式，找到output，其中就是答案了(不同版本可能字母不一样)。
答案
最终答案也是：
第二部分
第一步
同上述第一部分的方法一样，我们先需要找到，
将 代数公式得到答案:
第二步
然后我们是式子就变成了如何化简，
这一步需要我们掌握的方法，
标准答案里给了,参考[Solution to Question 14:]，超链接
直接套公式
第三步
在通过化简以后的式子就非常简单了，这里也就不多过多解释了…
答案
最终答案还是：
第九题 [附加题]
第九题看起来比较复杂，实则不然。只需要我们对Diffie-Hellman有着一定的理解，就可以轻易的拿到不错的附加分为我们的成绩保驾护航。
这里直接给大家思路以及答案，但是需要确保的是面试的时候万一老师问道你可以回答出来。
否则面试分数低，甚至是会影响到之前的成绩。
以及还是那句话，不要直接抄-不然大家全一样就炸了。
第一部分
在我们了解了Diffie-Hallman以后，直接套用公式就可以获得我们的和。
已知信息
计算得出
第二部分
已知信息
New
New
推理
我们分别考虑当为单数和偶数的情况。
当X为单数
let
当X为双数
let
结论
自己通过“推理”的过程来思考一下能推理出什么结果，获得什么信息。
