知乎被邀请回答了一个问题，和之前探索过的类似。问题如下：
10个不同的盒子，每个盒子里装有10块饼干。每次随机选择一个盒子，然后吃掉其中的一块饼干。直到第一次出现了任何一个空盒子就结束。求吃的饼干数目的期望。
这种问题是求第一次遇见的步长问题。我们可以转换为下面两步来求：
书接上回，我们考虑如何构造这个游戏。这里就是研究如何构造一个7阶的Finite Projective Plane。这篇的内容，大量参考 The what, how and why of Finite projective planes。然后我又找到了一个更好的视频资料：Module 4: Projective and Affine Planes。
前文从群开始讨论了抽象代数的一些基本概念，这篇文章我们完成讨论到有限域的构造。
Continue reading为了后面要讨论的Finite Projective Plane的构造算法中用到的Finite Prime Field，我们需要做一些抽象代数的回归。完整的抽象代数教材和课程固然好，但不适合突击。我找到了一份不错的小件一点儿的资料Introduction to finite fields (是Stanford CS250/EE387的补充阅读)。基于这份资料，我们列出所有需要弄清楚的问题，然后一一整理明白。
慕慕的玩具和游戏背后有很多有趣的算法话题。之前已经写三篇（如下）：
第四篇的游戏是一组卡牌，称为疯狂对对碰，网上很容易买到，如下图：
这个游戏是由一组卡牌，每个卡牌上有一些图标（这里是不同国家的国旗），任何两张卡牌的国旗组合里，有且只有一个共同点（这是我们的游戏经验）。家人陪慕慕玩这个游戏的办法是，洗牌，然后每个人分同样多的牌，每次各出一张，最快发现唯一相同国旗的人，赢走两张牌。最后计赢取的牌的数目决定胜负。
Continue reading我时不时会浏览一些大佬的个人主页(如Knuth和Sedgewick)，好久好久之前我就看到了Sedgewick关于HyperBitBit的研究了，一直就等他论文发表了。后来才想，不会这大爷忘了更新主页吧，去搜其他合作者，果然，论文刚刚都发布了。本文先罗列资料，然后再贴我的分析笔记。
华容道之水，不下赤壁。—— 孔明(火凤燎原)
慕慕妈妈给慕慕外卖凑单，多买了一个华容道游戏。
看到这种面板，脑子里自然而然的涌现几个问题：
针对这些问题，一个一个的解决。所有代码和数据文件在 https://github.com/kainwen/misc/tree/main/dancing_links
Continue readingKnuth教授的第28届圣诞讲座的视频：Stanford Lecture: Dr. Don Knuth – Strong Components and Weak Components (2024)，这引导我们继续去读一读这个Knuth教授这辈子最喜欢的算法，来自他的学生TARJAN(图灵奖得主)。
其中Knuth教授在上面的手稿里引用了一个别人对Tarjan这个算法的评论：
这更加让人想深刻理解这些科学家们的思路了。
Continue readingKnuth教授近期在自己的个人主页上强烈呼吁大家要更正对弱连通分量的定义，不要用大部分教材里三心二意的定义，而是要用上个世纪70年代一篇关于离散数学的论文里的定义。Knuth教授的呼吁在此：https://www-cs-faculty.stanford.edu/~knuth/news22.html#weakcomps，部分引用如下：
Let’s all agree as soon as possible to use the easily understood term undirected components, or (as suggested by Doug West) underlying components, for what many people have unfortunately been calling weak components, and to celebrate the properties of directed graphs whose weak components are defined in a truly useful way.
本文研究学习上个世纪70年代一篇离散数学的话题，它有一个很好的关于图(Graph)的弱连通分量的定义。论文信息如下：
多键值排序是把快速排序(Quick Sort)和基数排序(Radix Sort)结合起来的算法。论文为 Fast Algorithms for Sorting and Searching Strings (J. Bentley, R. Sedgewick) 。Greenplum 6里面有实现，本文是我自己按论文搜索资料，一步一步复习、学习、整理的记录。
教授的讲座资料：