From 4445dde0536a9ed26b682be8aca68220b9261b75 Mon Sep 17 00:00:00 2001 From: pin Date: Sat, 1 Jul 2017 17:20:04 +0900 Subject: [PATCH 1/3] Set theme jekyll-theme-cayman --- _config.yml | 1 + 1 file changed, 1 insertion(+) create mode 100644 _config.yml diff --git a/_config.yml b/_config.yml new file mode 100644 index 00000000..c4192631 --- /dev/null +++ b/_config.yml @@ -0,0 +1 @@ +theme: jekyll-theme-cayman \ No newline at end of file From 7c518846752569559e4f551486da6f63bb4f5f51 Mon Sep 17 00:00:00 2001 From: spinute Date: Sat, 15 Jul 2017 14:56:57 +0900 Subject: [PATCH 2/3] undo accidental gh-pages setting --- _config.yml | 1 - 1 file changed, 1 deletion(-) delete mode 100644 _config.yml diff --git a/_config.yml b/_config.yml deleted file mode 100644 index c4192631..00000000 --- a/_config.yml +++ /dev/null @@ -1 +0,0 @@ -theme: jekyll-theme-cayman \ No newline at end of file From e953f54730660514b3ad04d2bc96899aec9262b9 Mon Sep 17 00:00:00 2001 From: spinute Date: Sat, 15 Jul 2017 14:57:57 +0900 Subject: [PATCH 3/3] point out some errors found during ja-translation --- latex/arrays.tex | 1 + latex/btree.tex | 6 ++++-- latex/integers.tex | 1 - latex/intro.tex | 12 ++++++------ latex/linkedlists.tex | 4 ++-- latex/redblack.tex | 4 ++-- 6 files changed, 15 insertions(+), 13 deletions(-) diff --git a/latex/arrays.tex b/latex/arrays.tex index f9fc5729..9f7eda48 100644 --- a/latex/arrays.tex +++ b/latex/arrays.tex @@ -802,6 +802,7 @@ \subsection{Space Usage} #r#, used by a #RootishArrayStack# that stores #n# elements therefore satisfies \[ + % XXX: (#r#-2)(#r#-1)/2 ? (#r#-2)(#r#-1) \le #n# \enspace . \] Again, using the quadratic equation on this gives diff --git a/latex/btree.tex b/latex/btree.tex index b33bd3c0..f261d68f 100644 --- 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 index e7651b5f..8859417b 100644 --- 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 index ba8630d6..baf0323b 100644 --- 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 index c32b148a..b6c7ac0d 100644 --- 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 index e04f63eb..48d96cfe 100644 --- 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,