【记录】这是什么？算法（第 4 版）？速通一下

小红书刚刚到货，虽然一打开就看到了 Java 代码有点呃呃，但用的都是基本语法能看懂 ✌️😓。作业习题什么的就用 C/C++ 写一下好了。

看介绍说这是一本给低年级学生的一学期课程教材，那就是标准的学习时间为 4 个月。但是既然是自己啃，没有规定的课程节奏，那还是希望早一点结束为好。所以我定的目标是 Nov 21, 2023, 11:59:00 PM (Asia/Shanghai)，也就是我的生日前夜。

虽然不一定能做到，可能中途还会有很多意想不到的意外，但是走一步是一步了 ✌️😥。

[calendar defaultView="month"]
[/calendar]

加油🤗👍🏻

加油加油，等一个打卡

加油加油 😀

Sep 14, 2023, 12:52:00 AM (Asia/Shanghai)

结果 1.1 节一上来就是 Java 基础教学。不过也好，不需要太动脑子，光看书就行。之后的练习题也可以用 Java 做了。

当前位置：

1. Fundamentals

   1. Basic Programming Model <-
   2. Data Abstraction
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms
   5. Case Study: Union-Find

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

Sep 16, 2023, 8:12:00 PM (Asia/Shanghai)

做了一下第一节的课后题，但发现官网只给出了 answers for selected problems。所以决定之后学一个算法就在 leetcode 上做相应的题来练习。

当前位置：

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction <-
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms
   5. Case Study: Union-Find

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

Oct 16, 2023, 1:30:00 PM (Asia/Shanghai)

因为作业需求，先学了下后面的 Strings 部分内容。然后看完了抽象数据类型这节，了解到了很多 Java 特性，对面向对象编程思想理解更深入了。还学会了用 assertion 进行防御式编程，判断 preconditions 是否成立。

后面两节基本数据结构、算法分析我就比较熟悉了，但是 Bags 还是要看看。最期待 case study。

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction
   3. Bags, Queues, and Stacks <-
   4. Analysis of Algorithms
   5. Case Study: Union-Find

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

Oct 17, 2023, 7:30:00 PM (Asia/Shanghai)

再熟悉不过的链表和基本数据结构。也学到了 how data structure interplays with algorithms。

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms <-
   5. Case Study: Union-Find

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

Oct 18, 2023, 8:38:00 PM (Asia/Shanghai)

你妈，看书太枯燥了，看不下去一点了。但基础部分就这样，还好已经快到头了。期中之前把第一章看完，其实这本书 1/4 就过去了。之后稍微放一放罢，再钻研理论就 hbxql，先学点好玩的。

之前还对理论有点兴趣，太好笑了，真学起来学不进去一点。疯狂！彻底疯狂！

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms
   5. Case Study: Union-Find <-

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

加油喵加油喵

Oct 23, 2023, 6:20:00 PM (Asia/Shanghai)

Doubling ratio experiment 可以用来测试算法复杂度 [order of growth]（除了指数型）。其原理是 if $T(N) \sim aN^{b}\lg N$ then $T(2N)/T(N) \sim 2^{b}$. 每次增加一倍的数据量，最终时间增加的倍数将会稳定在某一 2 的幂。

Big-Oh notation 一般用来表示 the upper bound of worst case，然而平均来说算法的表现要好得多。比如 brute-force pattern matching 最坏情况下的时间复杂度为 n * m，但实际情况一般约为 n。还有一种情况是在某些边界值上算法复杂度很高，而平摊 [amortized] 来看其实表现不错。比如 resizing-array implementation of stack。

编写程序时，算法的简单、高效是十分重要的，但将大量精力投入算法优化中其实费力不讨好。只需注意选择正确的数据结构与算法，并在编写程序时注意防止冗余，就可以了。至于极致的算法优化，交给 theoretical computer scientists 去做。

1. Fundamentals

   1. Basic Programming Model
   2. Data Abstraction
   3. Bags, Queues, and Stacks
   4. Analysis of Algorithms
   5. Case Study: Union-Find <-

2. Sorting

3. Searching

4. Graphs

5. Strings

6. Context

此贴打算转型，不再局限于算法第四版这本书，而是记录我的算法学习历程 🤔。

书上第一章的内容特别长，占了整本书的 1/4。读完之后准备开始做 LeetCode 每日一题（？）

稍微学一下 Java 之后做一下 CS61b 的大作业罢，不写大项目实在是枯燥。

好好好，我困在 proj2 好一段时间

草，好。

Oct 24, 2023 (Asia/Shanghai)

10 月 23 日 LeetCode 每日一题：342. Power of Four

bool isPowerOfFour(int n) {
    if (n < 1) return false;
    while (n % 4 == 0) n /= 4;
    return n == 1 ? true : false;
}

草？

其实一开始想到 bit fiddling，但不会。

一开始想到判断是不是 2 的偶数次方就行，然后想到可能要位运算，我不太会。。
然后又不想就用普通的循环 / 递归
于是用了个这个：

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        ans = [1]
        i = 0
        cnt = 0
        while i <= 31:
            ans.append(ans[cnt] * 2 * 2)
            i += 2
            cnt += 1

        return n in ans

（反正给了范围，一共也就十几项（

写了个位操作 [bit fiddling] 版的：

bool isPowerOfFour(int n){
    if (n < 1) return false;
    for (unsigned i = (unsigned)(sizeof(int) * 8); i > 0; i -= 2, n >>= 2) {
        switch (n & 0x3) {
            case 0x0:
                continue;
            case 0x1:
                return n == 1 ? true : false;
            default:
                return false;
        }
    }
    return true;
}

Oct 24, 2023, 10:40:00 PM (Asia/Shanghai)

见证了 Union-Find 算法一步一步建构、优化的过程，真是乐趣无穷。

本章从 Java 基础编程模型开始，先介绍了抽象数据类型，然后是一些基本数据结构，最后是算法的分析方法。Now I am armed with the fundamentals of data structure and algorithms.

主要学到的算法有：

• Pushdown stack (resizing array)
• Pushdown stack (linked-list)
• FIFO queue
• Bag
• Union-find

1. Fundamentals

2. Sorting

   1. Elementary sorts <-
   2. Mergesort
   3. Quicksort
   4. Priority queues
   5. Applications

3. Searching

4. Graphs

5. Strings

6. Context

今天的 LeetCode 每日一题用到了二叉树。虽然学了二叉树，但还不会实现和使用。看今天能不能突击一下。

Oct 27, 2023, 8:28:00 PM (Asia/Shanghai)

练习时长两天半 😎，我要成为 Jvav 大师 😾。

学了下 Java，做了 CS61b proj0，真是极致爽滑。

JAV 是吧

你怎么知道今晚准备打交 😾。

jav 很好，cs61b proj0 也很好，赞美啊！😺😺

唉，之前我还计划着学 java 来着，这几天都看小说 + 学数学😭，下周我们数据结构就开始了 😭 现在 🐁 🐁Java 还没入门

数学领域大神 🙀。

好好，我宣布成立胶带门数据结构学习小组，狠狠学习 😾。

好好好

狠狠加入大神的学习小组 😋 🤗

学习小组有了，大神在哪 🙀

这是 Autograder 的 Halloween 彩蛋吗 😨，刚看到还被吓到了。

ASAG: If you are looking for ransom, I can tell you I don't have money. But what
I do have are a very particular set of skills; skills I have acquired over a
very long career. Skills that make me a nightmare for people like you. If you
let my daughter go now, that'll be the end of it. I will not look for you, I
will not pursue you. But if you don't, I will look for you, I will find you and
I will give you a zero.

Oct 31, 2023, 6:24:00 PM (Asia/Shanghai)

做完了 cs61b proj1a。第一次用 Java 写双向队列，过程中还是遇到了些问题的。使用了 resizing-array 和 DLList 两种数据结构实现，还使用 jUnit 写了 unit test。（虽然还是没搞懂 vscode 怎么检测 Java project 的，不能直接在 vscode 中启动测试）

修完 bug 提交后，用完了三次提交资格，但还有 style 的 2.5 分没拿到。是 hidden field error，其实是命名的问题。我在 class 中调用成员变量和函数都 explicitly 使用了 this，所以其实没大碍。

顺便，还看到了今天 Autograder 的一个彩蛋，还稍稍被吓到了点 😗。

明天就 11 月了啊，天气也是越来越冷了，我也该加快速度了。Searching 部分的树和二叉树学过了，但还没有实现过，快速过一遍就开始上手。Sorting 部分的书还得看。还要做一下 proj1b。

Autograder score: 50.0 / 50.0

ASAG: Because your code deserves the best

好 😋。

好耶

Nov 2, 2023, 3:10:00 AM (Asia/Shanghai)

cs61b proj1b 堂堂完成！这节主要是应用之前 proj1a 中编写的 deque 数据结构，简单的。

Nov 6, 2023, 8:40:00 PM (Asia/Shanghai)

讲得太好了！ Sedgewick 为什么是神：

排序算法部分先给出了最简单、符合直觉的 Selection sort 和 Insertion sort。这两种算法复杂度都是 $O(N^{2})$ ，但是 Insertion 要略快一些。

在 Insertion 的基础上进行优化，先把每隔 h 个元素的子数列排序好（h-sorted），再减小 h 的值直到 1。这样使得每个元素首先抵达自己目的地附近的位置，减少交换的次数。如此得到了 Shellsort，虽然不能证明其复杂度，但是 it's complexity is not necessarily $\sim N^{2}$ 。

Mergesort 是将数列切分成两个字数列，分别排序好后再进行合并。可以使用递归的 Top-down mergesort，也可以使用非递归的 Bottom-up mergesort。

递归的 divide and conquer 思想与数学归纳法相对应，于是可以用 Induction 来证明其复杂度为 $\sim N \log N$ 。作者也使用二叉树证明了任何基于比较的排序方法，其复杂度都不可能比 $N \log N$ 更优。（这段证明看得本 🍠 是浑身喜悦，接近高潮）

虽然 Mergesort 已经是 asymptotically optimal，但是其使用了辅助数列，所以空间复杂度不是最优。书中也给出了几个小优化点，可以在常数层面上进行优化。

在工程中应该永远首先使用最简单直观的方式，只有在这个算法成为 bottleneck 的时候再去优化它。

1. Fundamentals

2. Sorting

   1. Elementary sorts
   2. Mergesort
   3. Quicksort <-
   4. Priority queues
   5. Applications

3. Searching

4. Graphs

5. Strings

6. Context

我一定要把这段 post 出来，写得太好了 😾。

老哥买的英文原版啊，应该很贵吧......

不是进口的，是人民邮电出版社和中国工信出版集团在大陆出版的。定价是 129，当时买的应该能稍微便宜一点。

Nov 7, 2023, 9:50:00 PM (Asia/Shanghai)

Quicksort 与 mergesort 相比，不用创建辅助数组，因此空间占用更少。精细调整后的 quicksort 还可以将复杂度由 $\sim N\log N$ 降低到 $\sim NH - N$ ，其中 $H$ 为 Shannon 熵。对于存在大量重复 key 的数组，复杂度甚至可以达到 linear。

1. Fundamentals

2. Sorting

   1. Elementary sorts
   2. Mergesort
   3. Quicksort
   4. Priority queues <-
   5. Applications

3. Searching

4. Graphs

5. Strings

6. Context

书好像开胶了 🙀，有点心疼 😿

这个可以和哈夫曼编码一块看