Avoid this book at all costs. [Data structures and algorithms in C++) David Mount

[adam2016]

Data structures and algorithms by Robert Tamassia, David Mount and Michael T Goodrich

so I'm quite the novice and that statement is well established on here, I have read a couple of books on CS, two to be precise on C++, the first one being Jumping into C++ by Alex Allain and practices and principles by Bjarne.

I will say that jumping into C++ is very basic and is only intended for beginners but I did learn some nice concepts such as binary search trees, recursion , linked lists , pointers to pointers etc , in my opinion the majority of the book is very well explained, there is no doubt a couple of flaws exist with this book so by no means is it perfect but in my opinion it's a pretty decent book to start with I would give it a 7/10.

Practices and principles is highly regarded and well praised by most of the C++ community, is Bjarne the greatest teacher out there? of course not but the book is quite well written and the source code does make sense I picked up some interesting techniques in this book also. In short you can't go wrong with a book from the creator of the language.

Of course when reading a book on programming there will be some chapters that you may need to do extra research on until it clicks but not with every chapter.

I'm only on the 4th chapter of this book and almost every section of each chapter I have to do extra research on, the author gives half baked examples and does not elaborate on much of what he writes, in order to understand sub topics of discrete maths such as proof by induction, contrapositives , contradictions and big oh notation I had to do extra research, he tries to squeeze quite long topics into very few lines and fails to get his points across.

I've finally comes to chapter 4 and it's awful, his code is wrong for example on page 151 he gives an example of binary recursion, the example is a linear summation and I will post the code itself below.

Below is the code he uses in the book with the only difference being the function name.

in the example I'm assuming he uses an array = {1,2,3,4,5,6,7,8}

emphasis on assuming as he doesn't even give you this information. He does however say that the end variable will be 8.

so I indeed the code does work for when end is 8, it will give us the correct summation of 36!

but when you remove 2 numbers from the array and assign 6 to end instead of 8 it will give an incorrect summation,

so in short the only way this code works is if you have end = 8.

An incompetent programmer like myself does not go hand in hand with an incompetent and poorly written book, if you have read this book before please tell me your thoughts on it, at this point I'm considering not finishing the rest of it.

int summation_binaryRec(int* arr,int start,int end){

   if(end == 1)
    return arr[start];

    return summation_binaryRec(arr,start,end/2) + 
    summation_binaryRec(arr,start + (end/2),end/2);

}

int main()


    int arr[] = {1,2,3,4,5,6,7,8};
    cout << "summation binary recursion :: " << summation_binaryRec(arr,0,8) 
}

[jonnin]

never heard of it, but be aware that the topic here (d/s & alg) is for intermediate level and you are expected to know some of those things. Typically big-O is introduced in this topic/class, so if that was expected going into it, a poor book indeed. Most comp-sci courses expect you to have had discrete math by now. Proofs, maybe, maybe not... I got to that in my senior year and only because I wanted a math minor, it wasn't required, but the 'harder' / better known schools required a proofs course back when (not sure about now) and you would have that by now as well, usually.

point being, the book may or may not be terrible: it could just be that you lack the background that the authors expected, meaning your professor picked the wrong book if your school didn't have the right background before this class.... hard to say on that front. But if the examples are unclear or don't work etc, that is another story.

does the book have a 'before you read this, you need' section up front?!

[adam2016]

The only pre requisite the book expects you to have as far as programming is some prior knowledge or the basics of C++,

the author actually lists the prerequisites

- variables and expressions
- functions and procedures
- conditional statements
- iteration structures ( for and while loops )

now to the math part it expects you to have high school level math,

now I'm not from the US but in high school we barely touched on much discrete math, mainly geometry , probability and statistics and some calculus ( differentiation and integration )

[lastchance]

Adam2016 wrote:

Below is the code he uses in the book with the only difference being the function name.

in the example I'm assuming he uses an array = {1,2,3,4,5,6,7,8}

emphasis on assuming as he doesn't even give you this information. He does however say that the end variable will be 8.

so I indeed the code does work for when end is 8, it will give us the correct summation of 36!

I don't have the book but I think you do this example an injustice.

It is looking at the particular recursive routine
int summation_binaryRec(int* arr,int start,int end)
NOT at the other part of the code, which is just a test driver routine.

You may have miscopied the example (because I had to add a few characters to make it compile). However, it's a reasonably good example of a divide-and-conquer recursion.

The book is apparently online as a PDF. I don't know whether that is a legal copy or not. However, a brief scan of it suggests that it "does what it says on the can". The only quibble I would have with it is that it doesn't seem to deal with the modern computing paradigm of parallelisation.

[adam2016]

It is looking at the particular recursive routine
int summation_binaryRec(int* arr,int start,int end)
NOT at the other part of the code, which is just a test driver routine.

but how is it that the function will only seem to work for an array with 8 Integers?

I've tried a few tests on it and sometimes there is a literal off by one numeric problem if I tweak the numbers in the array around a little.

[ne555]

> chapter 4 his code on page 151 he gives an example of binary recursion,
> the example is a linear summation
> Below is the code he uses in the book with the only difference being
> the function name.
¿what edition?
the page number is useless, the chapter number may also be (not so much the chapter name)
and you changed the function name, ¿how do you expect for us to search for the actual code?

this is what I found on the 2nd edition
chapter "arrays, linked lists, and recursion"
section "binary recursion"

Algorithm BinarySum(A,i,n):
	Input: An array A and integers i and n
	Output: The sum of the n integers in A starting at index i

	if n = 1 then
		return A[i]
	return BinarySum(A,i,⌈n/2⌉) + BinarySum(A,i+⌈n/2⌉,⌊n/2⌋)

Code Fragment 3.41: Summing the elements in an array using binary recursion.

two things:
1. the parameters are clear: n integers, starting at index i, so the base condition is if(n==1)
you have start, end instead which is commonly used on ranges [start, end), I expected a if(end-start == 1) base condition

2. ⌈x⌉ means ceil(x)
⌊x⌋ means floor(x)
and with those it'll work with any array size (well, except 0)

> in the example I'm assuming he uses an array = {1,2,3,4,5,6,7,8}
> emphasis on assuming as he doesn't even give you this information. He does however say that the end variable will be 8.

To analyze Algorithm BinarySum, we consider, for simplicity, the case where
n is a power of two. The general case of arbitrary n is considered in Exercise R-4.5.
Figure 3.20 shows the recursion trace of an execution of function BinarySum(0,8).

It doesn't care about the result or the operations, just about the time/space analysis and the recursive functions
(altough BinarySum(0,8) is kind of missing an argument)

[againtry]

8 is a power of 2, and 6 isn't. The rest follows.

[adam2016]

two things:
1. the parameters are clear: n integers, starting at index i, so the base condition is if(n==1)
you have start, end instead which is commonly used on ranges [start, end), I expected a if(end-start == 1) base condition

yes i being the starting index and n being the number of integers in the array, obviously we split this in two for each case.

2. ⌈x⌉ means ceil(x)
⌊x⌋ means floor(x)
and with those it'll work with any array size (well, except 0)

what effect would the ceil and floor functions have ? obviously floor rounds down and ceil rounds up to the nearest integer, could you give an example with the code

to analyze Algorithm BinarySum, we consider, for simplicity, the case where
n is a power of two. The general case of arbitrary n is considered in Exercise R-4.5.
Figure 3.20 shows the recursion trace of an execution of function BinarySum(0,8).

Oh ok I didn't see this, maybe I glossed over it or maybe it's not included in my edition, I know the pdf you can find online is the newer rewritten version of the book, but that brings me to the question why does n have to be a power of 2 for this algorithm to work?

*edit to confirm, the edition I'm using does not specify that " we consider, for simplicity, the case where n is a power of two", alluding to the fact this edition is poorly written and maybe these mistakes were addressed with the newer edition of the book.

thanks

[lastchance]

adam2016 wrote:

that brings me to the question why does n have to be a power of 2 for this algorithm to work?

So that there is no integer-truncation error in doing end / 2.

For general n you have a number of choices, including:
- amend the code to run for arbitrary n (clue - you aren't obliged to split it in half);
- or pad it with zeroes to the next power of two; the sum won't change.


The online version of the book looks considerably better than the title of your thread would suggest.


Here's a version with 6 elements.

#include <iostream>
using namespace std;

int summation_binaryRec(int* arr,int start,int end)
{
   if ( end == 1 ) return arr[start];
   int length = end / 2;
   return summation_binaryRec(arr, start, length ) + summation_binaryRec( arr, start + length , end - length);
}

int main()
{
    int arr[] = {1,2,3,4,5,6};
    int size = sizeof arr / sizeof arr[0];
    cout << "summation binary recursion :: " << summation_binaryRec(arr,0,size) << '\n';
}

It can also be simplified - you don't need the start parameter because the array decays to a pointer pointing to the right position.

#include <iostream>
using namespace std;

int summation_binaryRec(int* arr,int end)
{
   if ( end == 1 ) return arr[0];
   int length = end / 2;
   return summation_binaryRec(arr, length ) + summation_binaryRec( arr + length , end - length);
}

int main()
{
    int arr[] = {1,2,3,4,5,6};
    int size = sizeof arr / sizeof arr[0];
    cout << "summation binary recursion :: " << summation_binaryRec(arr,size) << '\n';
}

[adam2016]

yeah agreed, from what I have seen from the online version it is a big improvement on the edition I'm using, which is horrible. the pdf online seems to be the 2nd edition, I'm reading the original edition.

perhaps the first edition was a little rushed and the second edition corrects these glaring mistakes.

thanks lastchance , awesome examples :) the first snippet of code which you posted, I actually got that far by myself but gave up before I even tested it.

[jonnin]

now I'm not from the US but in high school

I was speaking of college. Most high schools have only the basic intro to programming (before this book) level material in the US.

If you are doing this pre-college, you are ahead of the game from a US perspective.

Looks like you have your answer on the book... start working the 2nd ed.

[adam2016]

I am actually a CS student, albeit not a very good one lmao

interestingly we have two math modules, one in first year and one in second year, but none really cover any of the topics in that book :/

the first math class contained conversion,addition,subtraction,multiplication and division of binary,octal and hex numbers, it also widely covered set theory, coordinate geometry and advanced linear algebra.

the second math class covered integration and differentiation, probability and statistics , graph theory and matrices

[jonnin]

interesting way to do it.
trying to think.. I had it all one class at a time, old style USA degree (each is 1/3 of a year)

differentiation (calc 1)
integration (calc 2)
multivariable calc(optional, and actually easier than most)
differential eqtns (calc 3 harder than it should be, too much pattern memorize, not enough mathing)
prob/stats (side-class powerful, but simple and boring)
numerical methods (comp-sci /eng math very useful)
proofs (optional, useless)
linear algebra 1 & 2 very useful
discrete (waste of time, for comp-sci degree only ) I think we did sets in here. Or somewhere. I forget when.
graph theory was in algorithms, not math.

all the algebra and geom and such were in high school.
we never did binary/hex/etc ... its the same technique as base 10, isnt it? We did conversion in an early comp sci class. Only thing I recall is that binary and hex and octal are all related in a couple of handy ways, and that base 10 to anything else is annoying to do by hand. I drove my peers nuts at my first job because I would only do constants in base 10 and they were all hex snobs. A number is what it is, who cares how you print it?