知识点
学习流水线化的 Y86-64 处理器的设计和实现，深刻理解流水线冒险。
学习循环展开，理解其对程序性能的影响。
题目Part A要求使用 Y86-64 指令集，编写关于 sum_list, rsum_list 和 copy_block 函数的 Y86-64 程序。
做法参考书本图 4-7 即可，实现也较为简单。
Part B要求使用硬件控制语言（HCL）修改 sim/seq/seq-full.hcl，使得处理器支持 iaddq 指令。
做法iaddq 指令将立即数和寄存器相加，并将结果写回寄存器。
具体参考 irmovq 指令的实现即可。
Part C要求在 ncopy.ys ...
知识点
在这个实验中，学习利用缓存溢出（buffer overflow）来改变程序的行为，即完成攻击者的目的效果。
需要掌握 x86-64 的栈和参数传递机制，其结构如下图所示。
其中函数 P 调用了函数 Q，返回地址为函数 P 调用位置的下一条指令。实验攻击均修改该返回地址来完成攻击目的。
题目实验中的程序 CTARGET 和 RTARGET 都调用了函数 test：
12345void test() { int val; val = getbuf(); printf("No exploit. Getbuf returned 0x%x\n", val...
安装 GDB问题一在 Ubuntu 18.04 LTS 中使用 apt-get install gdb 安装失败。替换使用国内 Ubuntu 的镜像源后安装成功。
首先更新 /etc/apt/sources.list，将该文件内容替换为阿里源：
12345678910deb http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiversedeb http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe mul...
自动测试
使用 dlc 检测代码是否符合题目要求
1unix> ./dlc bits.c
编译并调用自动测试程序
12unix> makeunix> ./btest
题目bitXor(x, y)要求：仅使用 ~ 和 & 完成异或运算。
运算：~ &
做法：画出 & 运算符的真值表，配合 ~ 运算符易得。
123int bitXor(int x, int y) { return ~(x&y)&~(~x&~y);}
tmin()要求：返回二进制补码表示的最小整数。
运算： ! ~ & ^ |...
内容基本是翻译自论文《A Subquadratic Algorithm for Minimum Palindromic Factorization》，主要对文章进行翻译，力图简化算法的证明过程并给出相应的结论。简化证明过程可能存在不严谨的地方，如有需要可自行查看参考资料中的论文原文。
太长不看版给定一字符串，对于每个右端点为 $r$ 的回文子串，将左端点记为 $l_1\lt l_2\lt \dots \lt l_k$，记间距 $Δ_i=l_i-l_{i-1}$，结论有：
间距 $Δ_i$ 构成单调递减序列（严格来说，是单调非增序列），即 $\forall i>1,Δ_i\ge Δ...
计划计划一年内（截止 2021 年 1 月 1 日）把 SGU 500 刷完，形式以所有题目给出翻译后的简要题意和解题思路概要。
AC 代码库
题目101 Domino
题意 多米诺牌两端标有 0 至 6 的数字，以 形式表示，每张牌均可翻转。要求将 100 个多米诺牌横向放置成一排，相邻的多米诺牌数字需要相同。如 。判断是否存在方案，存在的话给出一种排列。
分析 将数字 0 至 6 视为图上的点，多米诺牌视为无向边，则问题转化成找出一条欧拉路径，而欧拉路径使用搜索+剪枝解决。
102 Coprimes
题意 给定 $1\le N \le 10^4$，求 $[1, N)$ 范围...
题目Necklace of Beads来源 POJ 1286
题意 使用 RGB 三种颜色对长为 $0\le n\le 23$ 的项链染色，求本质不同的方案数。一种方案如果经过旋转或翻转得到另一种方案，两种方案视为同一种。
注意 $n=0$ 在本题中会出现，测试数据输出 0。
分析 使用 Polya 计数公式求解，即对于正 $n$ 边形的顶点对称群
\{ρ_n^0=\iota,ρ_n,\dots, ρ_n^{n-1}, τ_1, τ_2, \dots, τ_n \}的循环因子分解。
旋转置换 $ρ_n^i,i=0,1,\dots n-1$ 的循环个数为
\gcd(n, i)证明 ...
简介简单来说，B-Tree 是针对大数据存取的平衡树，考虑了磁盘读取对查找效率的影响。
B-Tree 的主要思想是通过减少磁盘读取次数来提高数据存取性能，而磁盘读取次数与树高相关。故B-Tree 允许每个节点拥有多于 2 个的子节点来减小树高。
与二叉平衡树类似，B-Tree 中的每个节点存储若干键值（keys）以及子节点地址。
图 1. B-Tree 结构图
定义和性质阶（order）：将子节点的允许最大数量定义为阶，如图 1 为 5 阶树。
$m$ 阶的 B-Tree 满足以下定义：
每个节点最多能有 $m$ 个子节点。
每个内部节点至少有 $\lceil \frac m2\r...
简介AhoCorasick 算法（简称 AC 自动机），解决多模式串的字符匹配问题，即给定若干个单词串 $W_i$，求在文本串 $T$ 中的出现位置。KMP 算法解决单模式串的字符匹配，所以 AC 自动机可认为是 KMP 算法的扩展。
预备知识
字典树（Trie）：树上任意节点到根的路径所构成的子串，记为 $S(u)$，都是某个插入串的前缀。
KMP 算法：利用最长前后缀完成线性匹配。
核心思想AhoCorasick 本质上与 KMP 算法是一样的，都是通过相同前后缀减少重复计算问题，只是数据结构不同。
对应于 KMP，AC 自动机需要构建最长公共前后缀（LCPS，Longese Co...
KMP 算法解决在文本串（text）快速找出单词（word）的所有出现位置。
暴力匹配的时间复杂度为 $O(|T||W|)$，而 KMP 算法通过引入最长前后缀，将检索的时间复杂度降至线性。
最长前后缀
lps indicates longest proper prefix which is also suffix.
最长前后缀（LPS, Longest proper Prefix and Suffix）表示既是原串 $S$ 的真前缀也是后缀的最长子串 $T$，其中 $|T|\lt |S|$。
LPS(aaa) = aa \\
LPS(abcdab)=ab检索过程假设已知单词串的每个...
