colinaaa/algorithm-course-notes

何老师算法课笔记

algorithm-course-notes's Issues

排版错误

algorithm-course-notes/src/Image-segmentation.tex

Line 4 in 29f6e0c

\centering 本章简单介绍网络流在图像分割上的应用。

本行使用\centering，使得之后章节正文全部居中显示了，建议删除。

References for beginners

这里给出了一些新手指引，帮助大家上手LaTeX

安装与环境配置

• Install-LaTeX by OsbertWang
• LaTeX 编译环境配置：Visual Studio Code 配置简介 by EthanDeng

LaTeX教程

• lshort-cn by CTeX-org（这个应该是目前最好的中文LaTeX教程了）

模版文档

• ElegantBook by ElegantLaTeX

发现了几处错误

几处错误：

1. algorithm-course-notes/src/stable-matching.tex

   Line 10 in 99741ef

   现在有n个男性的一个集合$M=\{m_1,\dots,m_n\}$和n个女人性一个集合$W=\{w_1,\dots,w_n\}$。

   女人性--女性（女权警告）

2. algorithm-course-notes/src/stable-matching.tex

   Line 127 in 99741ef

   约定的对最后会形成匹配。我们袈裟算法会在还有一个未匹配的$m$的时候终止。在终止的时候，$m$一定向所有的女性发出过请求，否则算法不会终止。

   袈裟算法--G-S算法

3. algorithm-course-notes/src/dynamic-programming-1.tex

   Line 46 in 99741ef

   \item $OPT(k)$：表示区间集合$\{ I_1, I_2, \ldots , I_i \}$上的最优解权值。

   最后一个下标错误$\{ I_1, I_2, \ldots , I_k \}$

4. algorithm-course-notes/src/dynamic-programming-1.tex

   Line 93 in 99741ef

   \item 以最大权重排序，反例如\autoref{fig:wis-counterexample2}

   该贪心算法的反例有误，应该是99而不是999

5. algorithm-course-notes/src/Network-flows.tex

   Line 61 in 99741ef

   如\autoref{fig3}所示，给定二分图中，点被分为了\(V_l\)和\(V_r\)两个部分，构造网络流算法，设置一个起点S，且令S到所有的Vl中的点均有路径，容量为1；设置一个终点T，且从\(V_r\)中的点到T均有路径，容量为1。同时，所有\(V_l\)与\(V_r\)之间的路径容量均设为无穷大，由此可以找到该网络流的最大流和最小割。

   下标没打上，应该是且令S到所有的$V_l$中的点均有路径

离谱的错误

一些离谱的错误：

1. algorithm-course-notes/src/Ln1-AsymptoticOrderGrowth.tex

   Line 62 in 99741ef

   继续使用 $f(n)=pn^2+qn+r$ 的例子，其中q 、p、 r 均为正常数，我们可以说具有任何这种形式的函数都是$\Omega(n)$。

   
   具体内容如下：

继续使用 $f(n)=pn^2+qn+r$ 的例子，其中q 、p、 r 均为正常数，我们可以说具有任何这种形式的函数都是$\Omega(n)$。
证明如下：
\begin{proof}
	\begin{align*}
		\forall n \geq 1,t     & hen\ qn\leq 0,r\geq 0 \\
		\Longrightarrow   f(n) & =pn^2+qn+r            \\
		                       & \geq pn^2+pn^2+rn^2   \\
		                       & =(p+q+r)n^2
	\end{align*}
\end{proof}

显然证明错误，上面说$q, p, r$都是正常数，下面又来个$qn<0$，然后$n > n^2$？咋放缩的？应当是将低阶项舍去，建议修改：

继续使用 $f(n)=pn^2+qn+r$ 的例子，其中q 、p、 r 均为正常数，我们可以说具有任何这种形式的函数都是$\Omega(n)$。
证明如下：
\begin{proof}
	\begin{align*}
		\forall n \geq 1\\
		\Longrightarrow   f(n) & =pn^2+qn+r \\
		                       & \geq pn^2\\
		                       & =pn^2
	\end{align*}
\end{proof}

2. algorithm-course-notes/src/Ln1-AsymptoticOrderGrowth.tex

   Line 98 in 99741ef

   \section{渐进增长的一些性质}

   
   这个定理的条件错误，修改如下：

\section{渐进增长的一些性质}
下面将给出渐进增长的一些性质，对于性质的证明，可以自己证明，然后与\cite{textbook1}的P38-P40的证明进行对照
\begin{theorem}{Transitivity}{}
   (a)\ If\ $f=O(g)$\ and\ $g=O(h)$, then $f=O(h)$\\
   (b)\ If\ $f=\Omega(g)$\ and\ $g=\Omega(h)$, then $f=\Omega(h)$\\
   (c)\ If\ $f=\Theta(g)$\ and\ $g=\Theta(h)$, then $f=\Theta(h)$
\end{theorem}

3. algorithm-course-notes/src/Ln1-AsymptoticOrderGrowth.tex

   Line 106 in 99741ef

   \begin{theorem}{Sum\ of\ Functions}{}

   
   i的范围错误，应该是闭区间。

一些想法

您好，我是来自西电计算机的一名学生，我最近也有做类似『算法笔记』的想法。

• 第一章想写简单数据结构的的技巧与题目，如不定长数组，map，字符串的使用等，这种代码比较简单，我考虑放实际代码，这会比伪代码更加直接。见这里。每章结尾放几个练习题。
• 后面就是难度较大但很基本的数据结构，如树的遍历、图的连通分量等，这里侧重讲解，但还是想放实际的题目与代码。毕竟 Talk is cheap。
• 后面就是比较复杂的应用，如网络最大流、树状数组和动态规划等算法，这类算法需要很好的讲解和大量题目的阅读。（我看你们直接从复杂度过度到算法，emmm，可能是你们在上『算法分析与设计』等类似的课程吧）

以上都是我这种脑子不太好使的人学习算法的态度，恩，所以所有的内容和讲解都想给出实际练习题和代码，不然理解纯概念确实有些累。

等我期末月过完且您方便的时间，可否讨论下？

一些图片的label错误

algorithm-course-notes/src/Network-flows.tex

Line 35 in 99741ef

\caption{极大匹配举例}\label{fig1}

与

algorithm-course-notes/src/Image-segmentation.tex

Line 37 in 99741ef

\caption{图片前景背景识别}\label{fig2}

中均使用fig1, fig2 这样的label来标识图片，导致了build的过程中引用混乱。

计划：

• 修复问题，增加图片label的作用域（如：\label{fig:network-flow1}）
• 增加文档，规范化label名称（最好不使用1，2，3，而是使用有意义的名称）
• code review时注意类似问题⚠️

slight error to be corrected

algorithm-course-notes/src/Ln11-LargeIntegerMultiplication.tex

Line 76 in 99741ef

\KwRet{$C_3 \ll n + (C_2 + C_1) \ll (n - 1) + C_0$}\;

In line 76, the (C2 + C1) \ll (n - 1) should be corrected as:
(C2 + C1) \ll (n / 2)

algorithm-course-notes/src/Ln11-LargeIntegerMultiplication.tex

Line 141 in 99741ef

\KwRet{$C_2 \ll n + (C_0 - C_2 - C_1) \ll (n - 1) + C_1$}\;

Also in line 141, the (C_0 - C_2 - C_1) \ll (n - 1) should be corrected as:
(C_0 - C_2 - C_1) \ll (n / 2)

图片过大 & example定理

example中的定理cp过来没删掉

algorithm-course-notes/src/Proof-of-Statute.tex

Lines 12 to 14 in dc249cf

	\begin{theorem}{xxx定理}{label-for-this-theorem}
	这是一个定理。
	\end{theorem}

图片太大了，scale一下（下面一个图也是）

algorithm-course-notes/src/Proof-of-Statute.tex

Line 53 in dc249cf

\includegraphics{image/Proof-of-Statute2.png}

辛苦 @qzylalala 改一下吧，当时没认真review（

编译出错: ! LaTeX Error: File `pgfornament.sty' not found.

副标题

求一位同学贡献一个副标题