patmorin / ods Goto Github PK

In section 1.3.1 (pseudocode edition):

The expression b^x denotes the number b raised to the power of x. If x is a positive integer, then this is just the value of b multiplied by itself x-1 times:

Shouldn't it be x times instead of x-1? It even shows so in the accompanying picture:

cd images ; make
make[1]: Entering directory '/home/aveyond/Downloads/ods/latex/images'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/aveyond/Downloads/ods/latex/images'
cd figs ; make
make[1]: Entering directory '/home/aveyond/Downloads/ods/latex/figs'
ipetoipe -pdf selist-remove-b.ipe
Document selist-remove-b.ipe has 1 pages (1 views)
There were Latex errors.
Makefile:15: recipe for target 'selist-remove-b.pdf' failed
make[1]: *** [selist-remove-b.pdf] Error 1
make[1]: Leaving directory '/home/aveyond/Downloads/ods/latex/figs'
Makefile:24: recipe for target 'figs' failed
make: *** [figs] Error 2

All required packages are installed.

In page 10 there is the following mention
'When x is a negative integer, b^-x = 1/b^-x'

Shouldn't this be
When x is a negative integer, b^-x = 1/b^x

?

lines 14/15

def new_boolean_matrix(n, m):
    return numpy.zeros([n, n], numpy.bool_)

shouldn't this be

def new_boolean_matrix(n, m):
    return numpy.zeros([n, m], numpy.bool_)

?

The first sentence of §12.3.1 Breadth-First-Search calls it the bread-first-search.

It appears the URL in the bibliography for L, L, and M's Mathematics for Computer Science is broken: http://courses.csail.mit.edu/6.042/spring12/mcsfull.pdf returns with a 404 "resource not found" response.

A bit of exploration of the 6.042 course page lead me to this URL—http://courses.csail.mit.edu/6.042/spring12/mcs.pdf—which does resolve to a PDF text. I am uncertain if it is equivalent to the intended resource, so I'll leave the actual correction of the bibliography to someone who can confirm this is the same.

Note: thanks for the helpful (and fabulously licensed) text! :-)

When I try to use \usepackage[portuguese]{babel} to translate headers to portuguese (for example Chapter to Capítulo),
there is a error in the LaTeX compilation: "Argument of @ "rightmarksection" has an extra }"

If I comment the following lines in ods.tex the error disappear but the fancy style is lost.

\fancyhead[CO]{\small\rightmarktitle} % section title, right center
\fancyhead[RO,LE]{{\small\rightmarksection}}

How to fix the error without losing the style?

The last audio clip for the skiplist-i video needs to be rerecorded at home.

inkscape changed how to identify export file.

Now it is
%.pdf : %.svg
inkscape --export-pdf=$@ $<

%.eps : %.svg
inkscape --export-eps=$@ $<

It should be now:

%.pdf : %.svg
inkscape --export-type=pdf --export-filename=$@ $<

%.eps : %.svg
inkscape --export-type=eps --export-filename=$@ $<

The screen pdf format file doesn't fit screen well, because most e-readers
such as iPad, kindle, etc. holds a screen of 4:3, which makes the "screen pdf" hard to fit the screen. Could you please provide 4:3 version screen pdf file or a compilation option in makefile? Thank You!

Since the edges of skiplists are stored in arrays, the lengths can be stored in the same way:
[pseudocode goes here]?
The useful property of this definition...

Firstly, thank you for publishing your work as gratis and libre!

As a curious developer I explore collections on GitHub using their topics.
I noticed a topic textbook exists. https://github.com/jeffgerickson/algorithms is another project like this that uses the textbook tag for discoverability.

Can you add the tag at your convenience?

There is a question about ods-cpp 2.6.2 Space Usage " The number of blocks r, used by a RootishArrayStack that stores n elements therefore satisfies (r − 2)(r − 1) ≤ n " . I think n should satisfies (r-2)(r-1)/2 ≤ n. And the following proof process should be changed correspondingly.

Hi. I think there is an error on function height(u), section 6.11, for binary trees. The right function must be

height(u)
  if u = nil then return -1
  return 1 + max(height(u.left), height(u.right))

in order to give the right answer. Thank you for your great work. I'm preparing a translation to brazilian portuguese from your book.

It does not response. And http://isup.me/opendatastructures.org confirms that

The remove method of DLList of the Python version does not return values. The following is the snippet of the code.

   def remove(self, i):
        if i < 0 or i >= self.n: raise IndexError()
        self._remove(self.get_node(i))

The "remove" operation should return the removed values in this textbook. The same problem exists in the remove method of SEList of the Python version.

I started the book and the first datastructure feels strange and it gave a strange view on the rest of the book.
See
https://github.com/Ducasse/Containers-XP/blob/master/Containers-XP/CTArrayStack.class.st

and copied here.

Started to implement ArrayStack from this book https://opendatastructures.org/
But the first datastructure feels strange and it gave a strange view on the rest of the book.
The book defines the state of ArrayStack as an array and a number representing the number of elements.

T[] a;
int n; 

int size() {
   return n; }

For example add is defined as follows:

void add(int i, T x) {
   if (n + 1 > a.length) resize();
   for (int j = n; j > i; j--)
     a[j] = a[j-1];
   a[i] = x;
   n++;
}

Set is defined as follows:

 T set(int i, T x) {
   T y = a[i];
   a[i] = x;
   return y;
}

To me these definition are bogus.
Indeed

• first set does not update the number of elements, so using set break the invariant that n is the number of elements stored.
• second set should not return the previous value because it propagates null value
• third why set and get are needed (I renamed them as at: at:put:) but they are not needed in a Stack API.

The book text, as well as the Java and Python implementations, all use Queues to accumulate nodes to visit, but in the C++ code, the supporting data structure is ArrayDeque<Node*>. Elements are added at q.size() but instead of being removed at the other end, they're removed at q.size()-1. (See full implementation pasted in below.)

This strikes me as odd; I'm happy to submit a PR to fix this, but I wanted to check that I'm not overlooking something.

void BinaryTree<Node>::bfTraverse() {
	ArrayDeque<Node*> q;
	if (r != nil) q.add(q.size(),r);
	while (q.size() > 0) {
		Node *u = q.remove(q.size()-1);
		if (u->left != nil) q.add(q.size(),u->left);
		if (u->right != nil) q.add(q.size(),u->right);
	}
}

In section 12.3.1, the algorithm for BFS & DFS is given as below:

void bfs(Graph g, int r) {
   boolean[] seen = new boolean[g.nVertices()];
   Queue<Integer> q = new SLList<Integer>();
   q.add(r);
   seen[r] = true;
   while (!q.isEmpty()) {
     int i = q.remove();
     for (Integer j : g.outEdges(i)) {
      if (!seen[j]) {
         q.add(j);
         seen[j] = true;
} }
} }

There is mistake in the below highlighted line. It iterates over the value of the edges rather than index.
for (Integer j : g.outEdges(i)) {

If graph doesn't have sequenced number as value, the following line will throw ArrayIndexOutOfBoundsException.

if (!seen[j]) {

For example, graph like this: 0->1, 0->5, 3 -> 5, 0 -> 3 where size of the graph is 4.
while i = 0 and j = 5, It'll try access the seen array with index value 5. which won't exist and throw exception. Because, seen array won't have 5th index.

It also applies to section 12.3.2 (DFS).

Hello,

There is a function called allocTable declared inside ChainedHashTable but it is not used anywhere in the class itself, nor is there any implementation for it.
I thus believe that the implementation of ChainedHashTable will not work because items inside t will not be initialized properly.
I may have missed something as it's been years since I did serious C++, and if that's the case I would greatly appreciate an explanation.

Regards

The pdf files contain no table of contents. I mean, well, there IS table of contents as just a lot of hyperreferences in the beginning of the document, but there's no table of contents that pdf viewer is aware of.

It is a pain to navigate especially if I use pocket book device.

And thank you very much for this project, it is really incredible. Thanks.

The URLs on this page are relative to the site they are hosted:

http://opendatastructures.org/ods-cpp/Why_This_Book.html

The problem is that the LaTeX sources use plain URLs like:

\url{opendatastructures.org}

Correction is to add http:// or https:// at the beginning

\url{http://opendatastructures.org}
\url{https://github.com/patmorin/ods}

There seems to be something wrong with figure 1.5, which is about half-way down the page on chapter 1.3. I see this on both Chrome and Firefox:

There is only 1 occurrence of the word "null" in this edition, I believe the rest are "nil."
reference page 176, talking about scapegoat trees.

I assumed you didn't mean null, but this may be correct.

In Section 1.2.3 of the book. The dictionary/map was compared to the USet interface. One subtle issue here that we won't be able to update the dictionary/map using the add(x) method of USet, since 1) according to the text, two pairs are treated as equal if their keys are equal and 2) the USet add(x) interface states that the element x will be added to the set if not already present.

To create a dictionary/map, one forms compound objects called Pairs, each of which contains a key and a value. Two Pairs are treated as equal if their keys are equal. If we store some pair (k,v) in a USet and then later call the find(x) method using the pair x = (k, null) the result will be y = (k, v). In other words, it is possible to recover the value, v, given only the key, k.

Line 120

protected void addAfter(Node u, Node v) {
		v = u.next.next;
		u.next = v;
		if (u == tail) 
			tail = v;
}

the v=u.next.next; seems wrong, this function will only delete the node after u

I suspect the line

long p = (1L<<32)-5; // prime: 2ˆ32 - 5

causes overflow. long on my machine is 32-bit (printf("%ld\n", LONG_MAX); prints 2147483647), and compiler would give a warning -Wshift-count-overflow on that line. Indeed long type cannot hold that prime number.

I suspect it could be corrected as

unsigned long p = (1L<<32) - 5;

with printf("%lu\n", p); prints 4294967291, which is desired.

However the -Wshift-count-overflow warning: left shift count >= width of type still persists.

With

unsigned long p = (~0L) - 4;

(*)
the warning vanishes.

In summary, I think that line should be (*).

In section 5.2.3,w=32 and r=4 as the case which been used in hash method.But as described above ,the size of arrays used by tabulation hashing is w/r = 8 and each array's length is 2^r=8,meanwhile,under the code,the text says:

In this case, tab is a two-dimensional array with four columns and 2^(32/4) = 256 rows

Would this is wrong or something?Maybe r is 8?By the way ,at the begin of the LinearHashTable code(java version),r is inited by 8.

// https://github.com/patmorin/ods/blob/master/cpp/array.h
array& operator=(array &b) {
if (a != NULL) delete[] a;
a = b.a;
b.a = NULL;
length = b.length;
return *this;
}
a = b.a; // This is not deep copy.

In this line of the intro, the pseudocode version of the book shows the following truncated text:

[...] use of an implementation of the relevant interface (Stack, Queue, Deque, USet, or SSet) provided by the .

At the last paragraph of proo(in page 125),the text says 'By theorem 5.3'，but this proof just proves this theorem.Accoding to this section says above,maybe would this be Lemma5.1 which proofs Pr{hash(x) = hash(y)}<=2/2^d?

First line after the BTNode class declaration code: ".. we set it to nill."
Should be NULL.

I am having a problem making the odds document. I am on OS X 10.10. The make fails to make the figures. When I try to use ipetoipe -pdf on a single figure, for example 24rb.ipe, it returns

bash-3.2$ ipetoipe -pdf 24rb.ipe
Document 24rb.ipe has 1 pages (3 views)
There were Latex errors.

If I load the figure into ..ipe.. and run latex from inside ..ipe..I get:

(/Users/emisshula/Library/texmf/tex/latex/ods/ods-colors.sty

! LaTeX Error: Option clash for package xcolor.

See the LaTeX manual or LaTeX Companion for explanation.
Type H for immediate help.
...

l.3 \definecolor
{keyword}{named}{RoyalPurple}
The package xcolor has already been loaded with options:
[]
There has now been an attempt to load it with options
[usenames,dvipsnames]
Adding the global options:
,usenames,dvipsnames
to your \documentclass declaration may fix this.
Try typing to proceed.

! Package xcolor Error: Undefined color `RoyalPurple'.

If I try to run a minimal document using dos-colors:

\documentclass{article}
\usepackage{ods-colors}
\begin{document}
Hello, World!
\end{document}

It writes without error. Any guidance would be appreciated. Thank you.

I was trying to refer the book to a friend, but the website has been down for quite some time now. Tried through several different connections without any luck.

Python 2 reached its end of life on January 1st of 2020.
Scripts ./figs-python/snarf-fig.py and ./snarf-python.py in latex/ should use explicitly python2 path:

#!/usr/bin/python2

Possible error in figure 2.3
Text says elements will be moved left if i < n/2, but for example when i=4 and n=9 that means diagram should show moving elements right since 4 >= 9/2

Those nil's are considered as nodes when calculation, but not included in data_nodes(T)=n.

So given a red-black tree T with n data nodes, the two highlighted parts should be: log(n+1)+1, log(n+1).

Then height(T)= ((log(n+1)+1)+log(n+1)) - 1= 2log(n+1). (when calculating height, nil's are included; both CLRS, GeeksForGeeks gives the same result.)

This error has to be fixed immediately.

In §1.2.1 it is written "The remove(x) operation on a priority Queue is usually called deleteMin() in other texts." I believe that this should say "The remove() operation ...": remove takes no parameter.

The length of a path is never defined (it's the number of edges not the number of vertices in the path).

There is a typo in the introduction, section 1.2, page 5, latex line 209 :)
remove(x) should be remove() -- no argument

In the paragraph

Big-Oh notation is not new or unique to computer science. It was used by the number theorist Paul Bachmann as early as 1894, and is immensely useful for describing the running times of computer algorithms. Consider the following piece of code: One execution of this method involves

in 1.3.3 Asymptotic Notation (pseudocode version), there's a reference to a piece of code that's missing. This refers to the function

void snippet() {
    for (int i = 0; i < n; i++)
        a[i] = i;
    }
}

in the Java version.