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

#1 · 2023-09-13

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

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

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

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

mod #2 · 2023-09-13

加油🤗👍🏻

年月擦身过，暂且问，会更好吗？

#3 · 2023-09-13

加油加油，等一个打卡

#4 · 2023-09-13

加油加油 😀

#5 · 2023-09-13

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

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

当前位置：

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

#6 · 2023-09-16

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

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

当前位置：

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

#7 · 2023-10-16

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

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

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

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

#8 · 2023-10-17

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

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

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

#9 · 2023-10-18

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

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

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

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

mod #10 · 2023-10-18

uika_winwing

加油喵加油喵

#11 · 2023-10-23

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 去做。

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

#12 · 2023-10-23

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

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

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

mod #13 · 2023-10-23

uika_winwing

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

#14 · 2023-10-23

TsuinoSora

草，好。

#15 · 2023-10-23

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，但不会。

mod #16 · 2023-10-23

uika_winwing

一开始想到判断是不是 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

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

#17 · 2023-10-24

TsuinoSora

写了个位操作 [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;
}

#18 · 2023-10-24

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

Fundamentals
Sorting

1. Elementary sorts <-
2. Mergesort
3. Quicksort
4. Priority queues
5. Applications
Searching
Graphs
Strings
Context

#19 · 2023-10-24

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

#20 · 2023-10-27

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

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

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

#21 · 2023-10-27

JAV 是吧

#22 · 2023-10-27

Anonymous Coward Old

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

mod #23 · 2023-10-27

uika_winwing

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

mod #24 · 2023-10-27

uika_winwing

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

年月擦身过，暂且问，会更好吗？

#25 · 2023-10-27

玉米🌽

数学领域大神 🙀。

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

mod #26 · 2023-10-27

uika_winwing

好好好

mod #27 · 2023-10-27

uika_winwing

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

年月擦身过，暂且问，会更好吗？

#28 · 2023-10-27

玉米🌽

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

#29 · 2023-10-31

这是 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.

#30 · 2023-10-31

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。

#31 · 2023-10-31

Autograder score: 50.0 / 50.0

ASAG: Because your code deserves the best

好 😋。

mod #32 · 2023-10-31

uika_winwing

好耶

#33 · 2023-11-01

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

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

#34 · 2023-11-06

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 的时候再去优化它。

Fundamentals
Sorting
1. Elementary sorts
2. Mergesort
3. Quicksort <-
4. Priority queues
5. Applications
Searching
Graphs
Strings
Context

#35 · 2023-11-06

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

#36 · 2023-11-06

uika_winwing

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

#37 · 2023-11-06

小王在上海

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

#38 · 2023-11-07

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

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

Fundamentals
Sorting
1. Elementary sorts
2. Mergesort
3. Quicksort
4. Priority queues <-
5. Applications
Searching
Graphs
Strings
Context

#39 · 2023-11-07

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

#40 · 2023-11-07

uika_winwing

uika_winwing:

精细调整后的 quicksort 还可以将复杂度由 \sim N\log N∼NlogN\sim N\log N 降低到 \sim NH - N∼NH−N\sim NH - N，其中 HHH 为 Shannon 熵。

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

uika_winwing:

对于存在大量重复 key 的数组，复杂度甚至可以达到 linear。

这个书上写的是前面那个结论的直接推论吗？

#41 · 2023-11-07

Anonymous Coward Old

二叉树和 Huffman 编码有了解，然后后面那个是 quicksort with 3-way partitioning 的性质。它使用 $\sim (2 ln 2) NH$ 次比较，当没有重复键时， $H = lg N$ 此时复杂度为 $\sim N lg N$ 当重复键非常多时， $H$ 接近常数值。

#42 · 2023-11-09

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

非常好 heap 数据结构和 heapsort 算法，使我的时间复杂度 $\sim N log N$ ，空间复杂度 $1$ 。Priority queue 用处多多，非常好。

知道了这么多种排序方法，综合来说最好用的是 quicksort，但是当 stability 比较重要而 extra space 不太重要的时候最好用的还是 mergesort。

在 Java 中有非常好库方法 java.util.Arrays.sort()，但是在 Java 中要注意维护 immutability。

Fundamentals
Sorting
Searching
1. Symbol tables <-
2. Binary search trees
3. Balanced search trees
4. Hash tables
5. Applications
Graphs
Strings
Context

#44 · 2023-11-09

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

已完成 cs61b hw1: Packages, Interfaces, Generics, Exceptions, Iteration。

mod #45 · 2023-11-09

我也能在这里打卡吗，我懒得开贴了（x

#46 · 2023-11-09

TsuinoSora

好哇好哇 🥳

#52 · 2023-11-09

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

你已经掌握了排序算法的奥秘了，那么就来一场试炼罢。

LeetCode 148. Sort List

1 Selection sort

创建一个 sentinel node，每次选出最大的 node，append 到 sentinel 后面。

class Solution {

    public ListNode sortList(ListNode head) {
        return selectionSort(head);
    }

    private static ListNode selectionSort(ListNode head) {
        ListNode sentinel = new ListNode(0, null);
        while (head != null) {
            ListNode largestPrev = findLargestPrev(head);
            ListNode largest = largestPrev.next;

            if (largest == head) {
                head = head.next;
            }
            largestPrev.next = largest.next;
            largest.next = sentinel.next;
            sentinel.next = largest;
        }
        return sentinel.next;
    }

    /** return the previous node of the largest node */
    private static ListNode findLargestPrev(ListNode head) {
        ListNode largestPrev = new ListNode(0, head);
        ListNode currentPrev = largestPrev;
        while (currentPrev.next != null) {
            if (currentPrev.next.val > largestPrev.next.val) {
                largestPrev = currentPrev;
            }
            currentPrev = currentPrev.next;
        }
        return largestPrev;
    }
}

时间复杂度 $O(N^{2})$ ，空间复杂度 $O(1)$ ，不出意外的 TLE。

2 Insertion sort

数组的 insertion sort 是从头开始遍历，如果比左边小就向左交换位置。对于 SLList，依然是创建一个 sentinel node，从 head 节点开始一个一个插入 sentinel 之后，若比后面节点大则向右交换。

class Solution {

    public ListNode sortList(ListNode head) {
        return insertionSort(head);
    }

    private static ListNode insertionSort(ListNode head) {
        ListNode sentinel = new ListNode(0, null);
        while (head != null) {
            ListNode temp = head;
            head = head.next;
            temp.next = sentinel.next;
            sentinel.next = temp;
            swapHelper(sentinel);
        }
        return sentinel.next;
    }

    /** swap first node of sorted list rightwards while larger than right */
    private static void swapHelper(ListNode sentinel) {
        ListNode prev = sentinel;
        ListNode newly = sentinel.next;

        while (newly.next != null && newly.val > newly.next.val) {
            prev.next = newly.next;
            newly.next = newly.next.next;
            prev.next.next = newly;

            prev = prev.next;
        }
    }
}

时间复杂度 $O(N^{2})$ ，空间复杂度 $O(1)$ ，又是令人欣慰的 TLE。但是这个指针操作比上一个要优雅多了。

3 Mergesort

Divide and conquer. Use top-down mergesort.

class Solution {

    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        return mergesort(head);
    }

    /** recursively split and merge */
    private static ListNode mergesort(ListNode head) {
        if (head.next == null) return head;
        ListNode mid = split(head);
        ListNode leftSorted = mergesort(head);
        ListNode rightSorted = mergesort(mid);
        return merge(leftSorted, rightSorted);
    }

    /** split the given list into two and return the pointer to the second half */
    private static ListNode split(ListNode head) {
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode mid = slow.next;
        slow.next = null;
        return mid;
    }

    /** merge left list and right list */
    private static ListNode merge(ListNode left, ListNode right) {
        ListNode sentinel = new ListNode(0, null);
        ListNode rear = sentinel;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                ListNode temp = left;
                left = left.next;
                temp.next = null;
                rear.next = temp;
            } else {
                ListNode temp = right;
                right = right.next;
                temp.next = null;
                rear.next = temp;
            }
            rear = rear.next;
        }

        if (left == null) {
            while (right != null) {
                ListNode temp = right;
                right = right.next;
                temp.next = null;
                rear.next = temp;
                rear = rear.next;
            }
        } else { // right == null
            while (left != null) {
                ListNode temp = left;
                left = left.next;
                temp.next = null;
                rear.next = temp;
                rear = rear.next;
            }
        }

        return sentinel.next;
    }
}

时间复杂度 $O(NlogN)$ ，空间复杂度 $O(1)$ ，顺利 AC。

对 SLList 进行 quicksort 用 Java 太难实现了，遂放弃。（因为 Java 方法只能返回一个值，并且不能像 C/C++ 一样传递指针的指针来实现多返回值。）

SLList 的节点只有一个指针空间，故也不能实现 Heapsort。所以 mergesort 事坠吼的。

但是有一点小问题：为了避免 mergesort 的 worst case，在数组版本中首先对待排序数组进行 shuffle，链表好像不是很好进行 shuffle。第二个就是为了方便在 SLList 中进行节点插入删除，我使用了 currentPrev.next == current。但感觉这样很不优雅，不知道有没有什么修改方法。

Insertion sort 中我函数抽象的层次不对，应该把可复用的 swap() 抽象出来，而不是依赖于调用函数的 swapHelper()。

mod #53 · 2023-11-13

今天刷了 2 节 c s61b，复习了下 BST 和 AVL 树，学到了 B 树和红黑树

学 B 树使我水元素充盈，太牛逼了

但是像 AVL 树，B 树，红黑树这些都是平衡二叉搜索树的实现方法，结果都是一样的？都是为了 $O(\log N)$ 的搜索时间复杂度

mod #54 · 2023-11-13

TsuinoSora

哦，b 树可以做操作系统的文件索引和数据库索引，酷

mod #55 · 2023-11-13

TsuinoSora

渐进时间复杂度一样，但实际应用的时候并不是只看大 O 复杂度的。比如说

红黑树不是严格平衡，这会导致它每次操作的时间不完全稳定（虽然这个影响比较小），极少数情况下会被人挑毛病
AVL 实现起来一般比较麻烦，导致大多数 AVL 实现的时间常数都比较大。以至于虽然理论上它是严格平衡（稳定）的，但实际上大家经常嫌麻烦（不想写）或者嫌常数太大（慢好多）

更不严格的平衡二叉搜索树 Splay 甚至是均摊 O(log N) 复杂度的，也就是可能出现有的操作非常慢而有的非常快这种现象。感觉公司里搞开发的时候就不喜欢用 Splay，只是竞赛选手刷题的时候还比较常见。

#56 · 2023-11-13

TsuinoSora

主流 linux FS btrfs，XFS，ext4 都是

mod #57 · 2023-11-13

Anonymous Coward Old

谢谢！

另外你叫 success，可以和本站 @3ee28fe1a60c95b89d29317f122c70 组成 cp 😽 😻

mod #58 · 2023-11-13

greyishsong

😽 😺

mod #59 · 2023-11-16

21sp 的 lab2 有几个 hidden test 过不了，如果我写的测试用例都能通过，我要怎么找 bug 呢🥲

#61 · 2023-11-17

主治医师李大华

hidden test 就是考验你自己找问题的时候了（
test case 可能不够全面，可能有些 marginal case 没有照顾到

mod #62 · 2023-11-17

uika_winwing

找到几个 bug 了，现在正在被 Velocity Limiting 折磨 🥲

#63 · 2023-11-21

两月之期已到，然而才学到二叉树和搜索，后面还有图与字符串。这几天光看人类简史和微软 semantic kernel 的文档了。

mod #64 · 2023-11-26

把 B 树的视频投了，做这个太麻烦了，我在思考自动化生产视频

mod #65 · 2023-11-27

TsuinoSora

今天在 ISO C++ 群看到 B 树视频了

#66 · 2023-11-27

TsuinoSora

恭喜，本站第一个用户网红

mod #67 · 2023-11-27

TsuinoSora

我就是因为 CS61abc 的群里有个位置陕西西安 19 岁的二次元头像用户转发了你的新 B 站视频，所以导致我开盒失败😤

年月擦身过，暂且问，会更好吗？

#68 · 2023-11-27

TsuinoSora

写脚本用 ffmpeg 合成

mod #69 · 2023-11-27

rotartsinimdA

受宠若惊，我还以为新视频要没人看了。现在看来还行，而且评论区讨论视频内容的评论比例明显上升了🥰

mod #70 · 2023-11-27

Anonymous Coward Old

网红不至于，视频有人看我都很满足了

#71 · 2023-11-27

有人一起玩 Codeforces 吗，刚注册了，速加好友喵

mod #72 · 2023-11-27

uika_winwing

我们一起来做 leetcode 吧（）

#73 · 2023-11-27

TsuinoSora

好（）

mod #74 · 2023-11-27

TsuinoSora

可以把做 leetcode 当成期末周复习的放松，换换脑子。
但是我觉得很可能会做急了摆一天

mod #75 · 2023-11-27

TsuinoSora

好高雅的放松 😽

年月擦身过，暂且问，会更好吗？

mod #76 · 2023-11-27

TsuinoSora

我看着你这么卷我已经红温了

mod #77 · 2023-11-27

rotartsinimdA

😨 😱

#78 · 2023-11-27

Nov 28, 2023, 12:15:00 AM (Asia/Shanghai)

2-3 Tree 十分可爱，生长成为 Red-Black Tree 让我的红色节点旋转。

Fundamentals
Sorting
Searching
1. Symbol tables
2. Binary search trees
3. Balanced search trees
4. Hash tables <-
5. Applications
Graphs
Strings
Context

#79 · 2023-11-28

Nov 29, 2023, 3:15:00 AM (Asia/Shanghai)

Hash table 感觉看懂了，但又好像还隔着一层雾，搞得我不懂了。总之一般来说是用 Linear probing with resizing arrays 罢。

Fundamentals
Sorting
Searching
Graphs
1. Undirected graphs <-
2. Directed graphs
3. Minimum spanning trees
4. Shortest paths
Strings
Context

#80 · 2023-12-02

Dec 2, 2023, 8:10:00 PM (Asia/Shanghai)

学了 Huffman encoding。

#81 · 2023-12-05

Dec 5, 2023, 5:00:00 PM (Asia/Shanghai)

无向图。临接表表示、symbol graph、dfs、bfs 及应用。

实现红黑树的时候还是遇到了很多问题，然后 sorting 算法的一些细节也记不清了。还是得练，菜就多练。

Fundamentals
Sorting
Searching
Graphs
1. Undirected graphs
2. Directed graphs <-
3. Minimum spanning trees
4. Shortest paths
Strings
1. String sorts <-
2. Tries
3. Substring search
4. Regular expressions
5. Data compression [complete]
Context

#82 · 2023-12-18

Dec 19, 2023, 3:00:00 AM (Asia/Shanghai)

有向图。接口，实现，应用。环检测，拓扑排序。强联通支。传递闭包。

拓扑排序的算法：Reverse postorder DFS in a DAG
环检测：用栈
强联通支算法：KosarajuSCC，实现非常简单，但数学证明很复杂也很巧妙。
传递闭包：用来查找 all-pairs reachability，复杂度为平方级。

Fundamentals
Sorting
Searching
Graphs
1. Undirected graphs
2. Directed graphs
3. Minimum spanning trees <-
4. Shortest paths
Strings
1. String sorts <-
2. Tries
3. Substring search
4. Regular expressions
5. Data compression [complete]
Context

#83 · 2023-12-20

Dec 21, 2023, 2:00:00 AM (Asia/Shanghai)

最小生成树。为什么我说他讲的好：

先给出并证明了 cut theory，即连接两个 partition 的最小 weight crossing edge 一定在这个图的最小生成树中。由此诞生了 greedy algorithm，找出连接所有 paritition 的 minimum crossing edge。而 Prim's MST 与 Kruskal's MST 都是基于此的变种。

The eager version of Prim's MST algorithm is the relatively most efficient (amongst them). However, all of them are not that efficient for huge and sparse graphs, where it comes the Boruvka's algorithm.

Fundamentals
Sorting
Searching
Graphs
1. Undirected graphs
2. Directed graphs
3. Minimum spanning trees
4. Shortest paths <-
Strings
1. String sorts <-
2. Tries
3. Substring search
4. Regular expressions
5. Data compression [complete]
Context