Doraemonzzz

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Section 2。 1. Cubed Fourier(a) \begin{array}{l} \omega_{3}^{0}: \omega_{9}^{0}, \omega_9^3 ,\omega_9^6\\ \omega_{3}^{1}: \omega_{9}^{1}, \omega_9^4 ,\omega_9^7\\ \omega_{3}^{2}:\omega_{9}^{2}, \omega_9^5 ,\omega_9^8 \end{array}(b) \begin{aligned} P(x) &=a_{0}+a_{1} x+a_{2} x^{2}+\ldots+a_{8} x^{8}\\ &= (a_0 +a_3 x^3+a_6 x^6) + (a_1x +a_4 x^4+a_7 x^7) + (a_2x^2 +a_5 x^5+a_8 ...

这次回顾第二章第五部分习题。 学习资料： https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm https://github.com/DeathKing/Learning-SICP https://mitpress.mit.edu/sites/default/files/sicp/index.html https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454 参考资料： https://sicp.readthedocs.io/en/latest 2.59(p104)(load "unordered-set.scm") (define (union-set set1 set2) (cond ((null? set1) se ...

这次回顾第二章第四部分习题。 学习资料： https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm https://github.com/DeathKing/Learning-SICP https://mitpress.mit.edu/sites/default/files/sicp/index.html https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454 参考资料： https://sicp.readthedocs.io/en/latest 2.44(p90)形式： up-splict n - 1 | up-splict n - 1 up-splict n 代码如下： (define (up-split painter n) ...

这里给出摩尔投票法正确性的证明，之前在网上看的资料都是以实现或者解释为主，这里给出一般情形下的证明。 参考资料： https://leetcode-cn.com/problems/majority-element-ii/solution/duo-shu-tou-piao-de-sheng-ji-ban-hao-li-jie-java-b/ 摩尔投票法证明描述问题： 给定一个大小为$n$的整数数组，找出其中所有出现超过$\lfloor n/k \rfloor$次的元素。 可以用摩尔投票法在$O(k n)$时间复杂度，$O(k)$空间复杂度解法上述问题，算法接口： 算法名称：majorityKElement 输入：数组$a$，数组长度$n$，参数$k \ge 2$ 输出：所有出现超过$\lfloor n/k \rfloor$次的元素 代码如下： class Solution { public: vector<int> majorityElement(vector<int>& nums) { return majori ...

书籍介绍： https://book.douban.com/subject/3155710/ 配套课程： CS170（伯克利），CS161（斯坦福） github仓库： https://github.com/Doraemonzzz/Algorithm-DPV 参考资料： https://www.cnblogs.com/atyuwen/archive/2009/11/10/algorithmsexercisessolution.html https://stackoverflow.com/questions/36316109/what-is-the-complexity-of-long-division https://stackoverflow.com/questions/2884172/algorithm-for-dividing-very-large-numbers https://zhuanlan.zhihu.com/p/62088196 https://stackoverflow.com/questions/10213929/linear-3sat-a-version-of-3 ...

书籍介绍： https://book.douban.com/subject/3155710/ 配套课程： CS170（伯克利），CS161（斯坦福） github仓库： https://github.com/Doraemonzzz/Algorithm-DPV 参考资料： https://www.cnblogs.com/atyuwen/archive/2009/11/10/algorithmsexercisessolution.html 很久以前就买了这本书，一直没怎么翻，今天争取完成重点部分的习题解答，部分习题还是挺难的。 这次回顾第0章，序言。 第0章4(a)记 \begin{aligned} A& = \left[ \begin{matrix} a_{11} & a_{12}\\ a_{21}& a_{22} \end{matrix} \right]\\ B& = \left[ \begin{matrix} b_{11} & b_{12}\\ b_{21}& b_{22} \end{matrix} \right] \en ...

概要： 工作后时间确实紧张不少，之前看的编译原理公开课没有看完，project也一直没写，今年的一个目标就是完成编译原理的课程以及对应project，实现一些对应的算法。 这一次先从正则表达式的实现开始，这部分完成了正则表达式到NFA的转换。 参考资料： 正则表达式： https://cyberzhg.github.io/toolbox/ 中缀转后缀： https://blog.csdn.net/weixin_42034217/article/details/84679679 https://www.cnblogs.com/tech-bird/p/3971555.html 代码实现参考： https://github.com/bonkyzhu/Regex2NFA2DFA 辅助函数class Stack(object): def __init__(self): self.stack = [] def empty(self): return len(self.stack) == 0 def pop(self): ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Hw2。 2.Counting inversions 算法：Counting inversions 输入：数组$A$，起点$\text{start}$，终点$\text{end}$ 输出：逆序数 算法流程： 如果$\text{end}- \text{start}\le 0$，返回$0$ $l=\text{Counting inversions}(A, \text{start}, [n/2] -1)$ $r=\text{Counting inversions}(A, [n/2],\text{end})$ $B=[],i=0,j=0, c = 0$ while $(i \le [n/2] -1- \text{start})$ and $(j \le \text{end}- [n/2])$: if $A[\text{start}+i] < ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Section 1。 1.Squaring vs multiplying: matrices(a) \begin{aligned} A& = \left[ \begin{matrix} a & b\\ c & d \end{matrix} \right]\\ A^2 &=\left[ \begin{matrix} a & b\\ c & d \end{matrix} \right]\left[ \begin{matrix} a & b\\ c & d \end{matrix} \right]\\ &= \left[ \begin{matrix} a^2 + bc & ab + bd\\ ca+dc & cb + d^2 \end{matrix} \ ...

这次回顾第二章第三部分习题。 学习资料： https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm https://github.com/DeathKing/Learning-SICP https://mitpress.mit.edu/sites/default/files/sicp/index.html https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454 参考资料： https://sicp.readthedocs.io/en/latest 2.33(p80)(define (map p sequence) (accumulate (lambda (x y) (cons (p x) y)) '() sequence)) ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Hw1。 2.Analyze the running time(a) T(n) \in \Theta(n^2)(b)总时间复杂度为 \begin{aligned} T(n) &= \sum_{i=0}^{ \log n} 2^i\\ &=2^{\log n + 1} - 1\\ &=2n - 1 \\ &\in \Theta(n) \end{aligned}(c)第$k$轮的$i$为 i = 2^{2^{k}}令 2^{2^{k}} = n得 k = \log \log n所以 T(n) \in \Theta(\log \log n)(d) \begin{aligned} T(n) & =\sum_{i=1}^n \sum_{j=i^2} ^ n 1\\ &= \sum_{i=1}^{[\sqrt n]} \sum_{j=i^2 ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 最近规划复习算法分析的内容，主要材料是UCB的CS170，斯坦福的算法课程以及《算法概论》，这部分总结CS170相关内容，视频选择是fa20，作业选择的是fa18。 这次回顾Section 0。 1.Asymptotic Bound Practice证明： $\forall \epsilon > 0$，我们有 \begin{aligned} \lim_{x\to \infty} \frac{\log x}{x^{\epsilon}} &= \lim_{x\to \infty} \frac{(\log x)'}{(x^{\epsilon})'}\\ &= \lim_{x\to \infty} \frac{1/x}{\epsilon x^{\epsilon -1}}\\ &=\frac 1 {\epsilon} \lim_{x\to \in ...