patmorin · spinute · Jul 1, 2017 · Jul 15, 2017 · Jul 15, 2017 · Jul 15, 2017
diff --git a/latex/btree.tex b/latex/btree.tex
@@ -656,6 +656,7 @@ \subsection{Amortized Analysis of $B$-Trees}
   borrows and merges that occur. This completes the proof of the lemma.
 \end{proof}
 
+XXX: joins? borrows?
 The purpose of \lemref{btree-split} is to show that, in the word-RAM
 model the cost of splits, merges and joins during a sequence of $m$
 #add(x)# and #remove(x)# operations is only $O(Bm)$.  That is, the
@@ -699,7 +700,7 @@ \section{Discussion and Exercises}
 $B^*$-trees,
 \index{B*-tree@$B^*$-tree}%
 and counted $B$-trees.
-\index{conted $B$-tree}%
+\index{conuted $B$-tree}%
 $B$-trees are indeed
 ubiquitous and are the primary data structure in many file systems,
 including Apple's HFS+,
@@ -795,7 +796,8 @@ \section{Discussion and Exercises}
     operation, each of the (at most 3) affected nodes has at least
     $B+\alpha B$ keys and at most $2B-\alpha B$ keys, for some constant
     $\alpha > 0$.
-    \item Let #u# be an underfull node and let #v# and #w# be siblings of #u#
+	%XXX: underfull -> underflow?
+    \item Let #u# be an underfull node and let #v# and #w# be siblings of #u#.
     There are two ways to fix the underflow at #u#:
     \begin{enumerate}
        \item keys can be redistributed among #u#, #v#, and #w#; or

diff --git a/latex/integers.tex b/latex/integers.tex
@@ -482,7 +482,6 @@ \section{Discussion and Exercises}
 \begin{exc}
   Design and implement a simplified version of a #BinaryTrie# that
   does not have a linked list or jump pointers, but for which #find(x)#
-
   still runs in $O(#w#)$ time.
 \end{exc}
 

diff --git a/latex/intro.tex b/latex/intro.tex
@@ -272,7 +272,7 @@ \subsection{The #List# Interface: Linear Sequences}
     $#x#_{#i#},\ldots,#x#_{#n#-1}$; \\ 
     Set $#x#_{j+1}=#x#_j$, for all
     $j\in\{#n#-1,\ldots,#i#\}$, increment #n#, and set $#x#_i=#x#$
-  \item #remove(i)# remove the value $#x#_{#i#}$, displacing
+  \item #remove(i)#: remove the value $#x#_{#i#}$, displacing
     $#x#_{#i+1#},\ldots,#x#_{#n#-1}$; \\ 
     Set $#x#_{j}=#x#_{j+1}$, for all
     $j\in\{#i#,\ldots,#n#-2\}$ and decrement #n#
@@ -631,11 +631,11 @@ \subsection{Asymptotic Notation}
 
 An example of how big-Oh notation allows us to compare two different
 functions is shown in \figref{intro-asymptotics}, which compares the rate
-of growth of $f_1(#n#)=15#n#$ versus $f_2(n)=2#n#\log#n#$.  It might be
-that $f_1(n)$  is the running time of a complicated linear time algorithm
-while $f_2(n)$ is the running time of a considerably simpler algorithm
+of growth of $f_1(#n#)=15#n#$ versus $f_2(#n#)=2#n#\log#n#$.  It might be
+that $f_1(#n#)$  is the running time of a complicated linear time algorithm
+while $f_2(#n#)$ is the running time of a considerably simpler algorithm
 based on the divide-and-conquer paradigm.  This illustrates that,
-although $f_1(#n#)$ is greater than $f_2(n)$ for small values of #n#,
+although $f_1(#n#)$ is greater than $f_2(#n#)$ for small values of #n#,
 the opposite is true for large values of #n#.  Eventually $f_1(#n#)$
 wins out, by an increasingly wide margin.  Analysis using big-Oh notation
 told us that this would happen, since $O(#n#)\subset O(#n#\log #n#)$.
@@ -1118,7 +1118,7 @@ \section{Discussion and Exercises}
   parts of this exercise should be done by making use of an implementation
   of the relevant interface (#Stack#, #Queue#, #Deque#, #USet#, or #SSet#)
   provided by the \javaonly{Java Collections Framework}\cpponly{C++
-  Standard Template Library}.
+  Standard Template Library}. % looks weird in pseudo-code version
 
   Solve the following problems by reading a text file one line at a
   time and performing operations on each line in the appropriate data

diff --git a/latex/linkedlists.tex b/latex/linkedlists.tex
@@ -51,9 +51,9 @@ \section{#SLList#: A Singly-Linked List}
 \end{figure}
 
 
-An #SLList# can efficiently implement the #Stack# operations #push()#
+An #SLList# can efficiently implement the #Stack# operations #push(x)#
 and #pop()# by adding and removing elements at the head of the sequence.
-The #push()# operation simply creates a new node #u# with data value #x#,
+The #push(x)# operation simply creates a new node #u# with data value #x#,
 sets #u.next# to the old head of the list and makes #u# the new head
 of the list. Finally, it increments #n# since the size of the #SLList#
 has increased by one:

diff --git a/latex/redblack.tex b/latex/redblack.tex
@@ -23,7 +23,7 @@ \chapter{Red-Black Trees}
 running times are only expected. Scapegoat trees have a guaranteed
 bound on their height, but #add(x)# and #remove(x)# only run in $O(\log
 #n#)$ amortized time.  The third property is just icing on the cake. It
-tells us that  that the time needed to add or remove an element #x# is
+tells us that the time needed to add or remove an element #x# is
 dwarfed by the time it takes to find #x#.\footnote{Note that skiplists and
 treaps also have this property in the expected sense. See
 Exercises~\ref{exc:skiplist-changes} and \ref{exc:treap-rotates}.}
@@ -747,7 +747,7 @@ \section{Discussion and Exercises}
 
 \begin{exc}
   Design and implement a series of experiments that compare the relative
-  performance of #find(x)#, #add(x)#, and #remove(x)# for the #SSet# implemeentations #SkiplistSSet#,
+  performance of #find(x)#, #add(x)#, and #remove(x)# for the #SSet# implementations #SkiplistSSet#,
   #ScapegoatTree#, #Treap#, and #RedBlackTree#.  Be sure to include
   multiple test scenarios, including cases where the data is random,
   already sorted, is removed in random order, is removed in sorted order,