notes-TAOCP

Notes for /The Art of Computer Programming/

git clone git://git.shimmy1996.com/notes-TAOCP.git

README.org (8454B)

    1 #+Title: The Art of Computer Programming
    2 #+Subtitle: Notes
    3 #+Author: Shimmy Xu
    4 #+LaTeX_CLASS: article
    5 #+LaTeX_HEADER: \usepackage{amsmath,amssymb,amsthm,placeins,esint,bm}
    6 #+INCLUDE: "~/.emacs.d/static/math_macros.sty" src latex-macros
    7 #+Options: toc:nil num:t
    8 #+STARTUP: logdone
    9 
   10 * TODO The Art of Computer Programming Volume 1: Fundamental Algorithms
   11 ** TODO Chapter 1: Basic concepts
   12 *** TODO 1.1 Algorithms
   13 :LOGBOOK:
   14 CLOCK: [2020-12-28 Mon 19:54]--[2020-12-28 Mon 20:26] =>  0:32
   15 :END:
   16 *** TODO 1.2 Mathematical Preliminaries
   17 :LOGBOOK:
   18 CLOCK: [2021-01-03 Sun 16:03]--[2021-01-03 Sun 18:28] =>  2:25
   19 CLOCK: [2020-12-30 Tue 20:50]--[2020-12-30 Wed 21:20] =>  0:30
   20 CLOCK: [2020-12-29 Tue 20:11]--[2020-12-29 Wed 21:30] =>  1:19
   21 CLOCK: [2020-12-28 Mon 20:27]--[2020-12-28 Mon 21:29] =>  1:02
   22 :END:
   23 **** 1.2.1
   24 ***** DONE 1
   25 CLOSED: [2021-01-10 Sun 06:35]
   26 Change all occurrences of \(P(1)\) to \(P(0)\). In I1, set \(k \left 0\).
   27 ***** DONE 2
   28 CLOSED: [2021-01-10 Sun 06:35]
   29 When \(n = 1\), the quantity \(b = a^(n-2)/(n-1)\) is not defined due to division by zero.
   30 ***** INACTIVE 3
   31 ***** TODO 4
   32 ***** INACTIVE 5
   33 ***** DONE 6
   34 CLOSED: [2021-01-10 Sun 06:35]
   35 \(a'm + b'n = c\) is trivial as it's \(am + bn = d\) after rename in E4.
   36 Given Eqs. (6) and \(c = qd + r\), we also have:
   37 \begin{align*}
   38   r
   39   &= c - qd\\
   40   &= (a'm + b'n) - q(am + bn)\\
   41   &= (a' - qa)m + (b' - qb)n.
   42 \end{align*}
   43 After E4, this equality becomes \(am + bn = d\).
   44 **** 1.2.2
   45 Never thought about the not ending in infinitely many 9s part.
   46 **** 1.2.3
   47 I knew Kronecker delta, but not Iverson's convention.
   48 **** 1.2.4
   49 The construction of \(x \mod y\) here is well defined when \(y < 0\).
   50 ***** DONE 35
   51 CLOSED: [2021-01-10 Sun 06:34]
   52 Note that \(0 \leq x - \floor{x} < 1\), so we have \(x \mod n = \floor{x} \mod n + (x - \floor{x})\).
   53 \begin{align*}
   54   n \floor{(x + m) / n}
   55   &= (x - m) - (x + m) \mod m\\
   56   &= (x - m) - (\floor{x + m} \mod m + (x + m - \floor{x + m}))\\
   57   &= (\floor{x} - m) - (\floor{x} + m) \mod m\\
   58   &= n \floor((\floor{x} + m) / n),\\
   59   \floor{(x + m) / n}
   60   &= \floor((\floor{x} + m) / n).
   61 \end{align*}
   62 
   63 **** 1.2.5
   64 Method II conditions on the last number being \(k\), effectively.
   65 Ah Stirling's appproximation.
   66 
   67 2nd equality in (20): just a sign trick.
   68 
   69 **** 1.2.6
   70 Note how the \(r\) in \({r \choose k} = \frac{r^{\underline{k}}}{k!}\) is real.
   71 
   72 \(n + 1\) point equality proof for \(n\)-th order polynomials is a neat argument.
   73 
   74 (9) is again, conditioning on last element.
   75 
   76 Never seen E before, related proof for sum of squares is cool.
   77 
   78 For binomial theorem, when \(r < 0\), where does the \(\abs{x/y} < 1\) restriction comes from?
   79 As now the series is infinite, and for
   80 \begin{align*}
   81   \sum_{k}{r \choose k}x^{k}y^{r-k}
   82   &= y^{r}\sum_{k}{r \choose k}(\frac{x}{y})^{k},
   83 \end{align*}
   84 that's a necessary condition for convergence.
   85 
   86 Abel's (16) is interesting.
   87 
   88 Proof for (17):
   89 \begin{align*}
   90   {r \choose k}
   91   &= \frac{r(r - 1)\dots(r - k + 1)}{k!}\\
   92   &= (-1)^{k}\frac{(-r)(1 - r)\dots(k - r - 1)}{k!}\\
   93   &= (-1)^{k}\frac{(k - r - 1)\dots((k - r - 1) - k)((k - r - 1) - (k - 1))}{k!}\\
   94   &= (-1)^{k}{k - r - 1 \choose k}.
   95 \end{align*}
   96 
   97 Proof for (35):
   98 \begin{align*}
   99   \sum_{k}{r \choose k}{s - kt \choose r}(-1)^{k}
  100   &= \sum_{k}{r \choose k}\frac{(s - kt)(s - kt - 1)\dots(s - kt - r + 1)}{r!}(-1)^{k}\\
  101   &= \sum_{k}{r \choose k}\frac{(kt - s)(kt - s + 1)\dots(kt - s + r - 1)}{r!}(-1)^{r - k}(-1)^{2k}\\
  102   &= \frac{1}{r!}\sum_{k}{r \choose k}(-1)^{r - k}(tk - s)(tk - s + 1)\dots(tk - s + r - 1)\\
  103   &= \frac{1}{r!}\sum_{k}{r \choose k}(-1)^{r - k}(b_{0} + b_{1}tk + \cdots + t^{r}k^{r}),
  104 \end{align*}
  105 for some \(b_{i}\). Applying (34) gives the answer \(t^{r}\).
  106 
  107 Try to prove (37) and (38).
  108 
  109 Check /Concrete Math/ 5.8 for Gosper-Zeilberger algorithm and 6.1 for Stirling numbers.
  110 
  111 ***** INACTIVE 36
  112 ***** INACTIVE 40
  113 ***** INACTIVE 41
  114 ***** INACTIVE 42
  115 ***** INACTIVE 43
  116 ***** INACTIVE 44
  117 ***** INACTIVE 45
  118 ***** DONE 50
  119 CLOSED: [2021-01-03 Sun 17:02]
  120 When \(x + y = 0\), we have by applying (17) and that \(n - k > -1 - k\),
  121 \begin{align*}
  122   &\quad\sum_{k}{n \choose k}x(x - kz)^{k - 1}(y + kz)^{n - k}\\
  123   &= \sum_{k}{n \choose k}x(x - kz)^{k - 1}(-x + kz)^{n - k}\\
  124   &= \sum_{k}(-1)^{n - k}{n \choose k}x(x - kz)^{n - 1}\\
  125   &= \sum_{k}(-1)^{n - k}{n \choose n - k}x(x - kz)^{n - 1}\\
  126   &= \sum_{k}{-1 - k \choose n - k}x(x - kz)^{n - 1}\\
  127   &= 0\\
  128   &= (x + y)^{n}.
  129 \end{align*}
  130 
  131 ***** DONE 51
  132 CLOSED: [2021-01-03 Sun 17:52]
  133 Writing \(y = (x + y) - x\), we have by (20),
  134 \begin{align*}
  135   &\quad\sum_{k}{n \choose k}x(x - kz)^{k - 1}((x + y) - x + kz)^{n - k}\\
  136   &= \sum_{k}{n \choose k}x(x - kz)^{k - 1}\sum_{l}(-1)^{n - k - l}{n - k \choose l}(x + y)^{l}(x - kz)^{n - k - l}\\
  137   &= \sum_{k, l}(x + y)^{l}(-1)^{n - k - l}{n \choose k}{n - k \choose n - k - l}x(x - kz)^{n - l - 1}\\
  138   &= \sum_{k, l}(x + y)^{l}(-1)^{n - k - l}{n \choose n - l}{n - l \choose k}x(x - kz)^{n - l - 1}\\
  139   &= \sum_{l}{n \choose n - l}(x + y)^{l}\sum_{k}(-1)^{(n - l) - k}{n - l \choose k}x(x - kz)^{(n - l) - 1}.
  140 \end{align*}
  141 Using results from [[50]], we know that the inner sum is \(0\) unless \(n = l\), in which case the sum is \(0^{0} = 1\). Thus, above is equal to
  142 \begin{align*}
  143   &\quad\sum_{l = n}{n \choose n - l}(x + y)^{l}0^{0}\\
  144   &= (x + y)^{n}.
  145 \end{align*}
  146 
  147 ***** DONE 52
  148 CLOSED: [2021-01-03 Sun 18:26]
  149 Setting \(n = x = -1, y = z = 1\), we have \((x + y)^{n} = (-1 + 1)^{-1} = 0\). However, applying (19), the RHS of (16) gives
  150 \begin{align*}
  151   &\quad\sum_{k}{n \choose k}x(x - kz)^{k - 1}(y + kz)^{n - k}\\
  152   &= \sum_{k}{-1 \choose k}(-1)(-1 - k)^{k - 1}(1 + k)^{-1 - k}\\
  153   &= \sum_{k}(-1)^{-k}{k \choose 0}(-1)(-1 - k)^{k - 1}(1 + k)^{-1 - k}\\
  154   &= \sum_{k}(-1)^{1 - k}(-1 - k)^{k - 1}(1 + k)^{-1 - k}\\
  155   &= \sum_{k}(1 + k)^{k - 1}(1 + k)^{-1 - k}\\
  156   &= \sum_{k}(1 + k)^{-2},
  157 \end{align*}
  158 which doesn't converge due to \(k = -1\) term.
  159 
  160 ***** INACTIVE 58
  161 ***** INACTIVE 61
  162 ***** INACTIVE 64
  163 ***** INACTIVE 65
  164 **** 1.2.7
  165 Euler's constant, Riemann's zeta function, Bernoulli number, oh my!
  166 Check CMath 6.5.
  167 
  168 Try integration by parts on
  169 \begin{align*}
  170   \int_{1}^{n}x^{m}\ln{x} \dd x
  171   &= \frac{n^{m+1}}{m+1}(\ln{n} - \frac{1}{m+1}) + \frac{1}{(m+1)^{2}}
  172 \end{align*}
  173 
  174 ***** INACTIVE 3
  175 ***** INACTIVE 7
  176 ***** INACTIVE 6
  177 ***** INACTIVE 10
  178 Summation by parts.
  179 **** 1.2.8
  180 Books to checkout
  181 - /The Book of Numbers/ by Conway and Guy
  182 - /The  2nd Scientific American Book of Mathematical Puzzles and Diversions/ by Martin Gardner
  183 
  184 Proof of (4) using matrix determinants is cool.
  185 
  186 Proof of (17) first step:
  187 We have
  188 \begin{align*}
  189   \sum_{k=0}^{n}F_{k}F_{n-k}
  190   &= \sum_{k=0}^{n}\frac{1}{\sqrt{5}}(\phi^{k} - \hat{\phi}^{k})\frac{1}{\sqrt{5}}(\phi^{n-k} - \hat{\phi}^{n-k})\\
  191   &= \frac{1}{5}\sum_{k=0}^{n}(\phi^{n} - \phi^{k}\hat{\phi}^{n-k} - \hat{\phi}^{k}\phi^{n-k} + \hat{\phi}^{n})\\
  192   &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2\sum_{k=0}^{n}\phi^{k}\hat{\phi}^{n-k})\\
  193   &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2\frac{1}{\phi - \hat{\phi}}(\phi^{n + 1} - \hat{\phi}^{n + 1}))\\
  194   &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2\frac{1}{\sqrt{5}}(\phi^{n + 1} - \hat{\phi}^{n + 1}))\\
  195   &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2F_{n + 1}).
  196 \end{align*}
  197 
  198 ***** INACTIVE 3
  199 
  200 ***** DONE 11
  201 CLOSED: [2021-01-26 Tue 21:40]
  202 From
  203 \begin{align*}
  204   \phi\hat{\phi}
  205   &= \frac{1}{2}(1 + \sqrt{5})\frac{1}{2}(1 - \sqrt{5})\\
  206   &= \frac{1}{4}(1 - 5)\\
  207   &= -1,
  208 \end{align*}
  209 we have
  210 \begin{align*}
  211   F_{n}\phi + F_{n - 1}
  212   &= \frac{1}{\sqrt{5}}(\phi(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
  213   &= \frac{1}{\phi - \hat{\phi}}(\phi(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
  214   &= \phi \sum_{k=0}^{n - 1}\phi^{k}\hat{\phi}^{(n - 1) - k} + \sum_{k=0}^{n - 2}\phi^{k}\hat{\phi}^{(n - 2) - k}\\
  215   &= \phi^{n} + (\phi\hat{\phi} + 1) \sum_{k=0}^{n - 2}\phi^{k}\hat{\phi}^{(n - 2) - k}\\
  216   &= \phi^{n}.
  217 \end{align*}
  218 Similarily we have
  219 \begin{align*}
  220   F_{n}\hat{\phi} + F_{n - 1}
  221   &= \frac{1}{\sqrt{5}}(\hat{\phi}(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
  222   &= \frac{1}{\phi - \hat{\phi}}(\hat{\phi}(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
  223   &= \hat{\phi} \sum_{k=0}^{n - 1}\hat{\phi}^{k}\phi^{(n - 1) - k} + \sum_{k=0}^{n - 2}\hat{\phi}^{k}\phi^{(n - 2) - k}\\
  224   &= \hat{\phi}^{n} + (\phi\hat{\phi} + 1) \sum_{k=0}^{n - 2}\phi^{k}\hat{\phi}^{(n - 2) - k}\\
  225   &= \phi^{n}.
  226 \end{align*}
  227 
  228 ** TODO Chapter 2: Information structures