By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,234 Members | 2,010 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,234 IT Pros & Developers. It's quick & easy.

Concrete Mathematics

P: n/a
I want to learn algorithms & data-structures. search told me nothing
beats KNUTH, the DON. since my Maths is weak, i purchased prerequisite
to his AoCP i.e. "Concrete Mathematics" . it's very complicated &
confusing for the time being i am unable to make any sense out of it
but i am persisting because i think sooner or later it will make sense
( i am reading this book from last 5-6 days). if i leave this book then
i will not be able to to Knuth's AoCP, RIGHT?

what do you think? is there any prerequisite to "Concrete Mathematics"
like say "Higher Algebra by Hall & Knight" .i am just a normal B.Sc.
graduate :-(

i am thinking of doing CORMEN/SEDGWICK but If i do not do KNUTH, then i
will never become an *excellent* programmer, am i right?

i will really appreciate if you can provide some help or views/comments

-- arnuld

Jun 14 '06 #1
Share this Question
Share on Google+
21 Replies


P: n/a
arnuld wrote:
I want to learn algorithms & data-structures. search told me nothing
beats KNUTH, the DON. since my Maths is weak, i purchased prerequisite
to his AoCP i.e. "Concrete Mathematics" . it's very complicated &
confusing for the time being i am unable to make any sense out of it
but i am persisting because i think sooner or later it will make sense
( i am reading this book from last 5-6 days). if i leave this book then
i will not be able to to Knuth's AoCP, RIGHT?

what do you think? is there any prerequisite to "Concrete Mathematics"
like say "Higher Algebra by Hall & Knight" .i am just a normal B.Sc.
graduate :-(

i am thinking of doing CORMEN/SEDGWICK but If i do not do KNUTH, then i
will never become an *excellent* programmer, am i right?

i will really appreciate if you can provide some help or views/comments

-- arnuld


This is not a C++ question. You should ask on comp.programming or some
other newsgroup. See this FAQ for what is on-topic here:

http://www.parashift.com/c++-faq-lit...t.html#faq-5.9

Cheers! --M

Jun 14 '06 #2

P: n/a
"arnuld" wrote:
i am thinking of doing CORMEN/SEDGWICK but If i do not do KNUTH, then i
will never become an *excellent* programmer, am i right?


No, you are not right.

Excellent programmers are born, not made. And for that matter,there are
many very good programmers who have never heard of Knuth. Or Cormen either.
I think Knuth is good for a lot of things, but I also think he spends way
too much time on corner cases and *proving* things. There are only so many
neurons and I think there are much better ways to allocate them.

I think a serious programmer should have Knuth on his shelves, but not try
to comprehend every little nuance of everything he says. That's what
indexes are for.
Jun 14 '06 #3

P: n/a
mlimber wrote:
This is not a C++ question.
i agree
You should ask on comp.programming or some
other newsgroup. See this FAQ for what is on-topic here:

http://www.parashift.com/c++-faq-lit...t.html#faq-5.9


i tried but did not find any newsgroup specific to algorithms, since i
knew that quite talented folks exist at comp.lang.c++, so i thought i
should post it here.
anyway, i will not post such question again on comp.lang.c++

Jun 14 '06 #4

P: n/a

arnuld wrote:
i tried but did not find any newsgroup specific to algorithms, since i
knew that quite talented folks exist at comp.lang.c++, so i thought i
should post it here.


comp.programming

Knuth is for when you want a Master's or Docterate in CS. I own a set,
I've read some of it and actually comprehended a little. It's hardly
ever practical; in fact I don't know that I have ever found a practical
use for anything in the Knuth books. Most of the stuff he talks about
is spoken of in simpler terms elsewhere.

To get through the math part you need lots of algebra. That's pretty
much all he uses. You need to know summations and whatever you call
the multiplication equivelant. You'll need logs and powers. That's
about it. Some practice creating formulas for real world problems
would be very helpful.

In TAOCP itself he says it is not necissary to read CH1 to understand
most of the rest of the books. It will help to understand the proofs
though.

Even if you know the math he uses it in very advanced ways. He IS a
mathmetician. Have fun.

Jun 14 '06 #5

P: n/a
> No, you are not right.

Excellent programmers are born, not made.
I just don't agrre with this. I know at least 2 more guys who will not
agree with you. they are Albert Einstein & Isaac Newton. Newton once
said: "if other people could think as hard as i thought, they would
have gotten similiar results".

"I spent all of my life and i say, *kings* are not born but made,
through suffering and hardness. these women are dangerous, you can
never know them. "

-- father of ALEXANDER

and i am not intelligent but a poor fellow who has 54% marks in his
graduation. It took me 1 year from beginner to programmer. I never
understood Python, people recommend this language to a beginner. i
never understood SCHEME, people also recommend this to a beginner. I
understood some LISP, (read "Practical Common LISP" straight form being
a beginner), then i did "Programming Ruby" easily.

I have my classmate who is a B.Sc graduate with me but he doesn't know
what is the "differential of Sin x" but presently he is the TSM
(Territory Sales Manager) with Bank of Punjab, earning 28,000 INR per
month, great part is that nobody, inlcuding you, knows him. unlike
Newton, & Einstein, he is just another guy.

my learning curve & experience of life force me to think that Newton &
what father of Alexander said was right but how can i apply this to
learning from Knuth?

And for that matter,there are
many very good programmers who have never heard of Knuth. Or Cormen either.
now that is truly unexpected & strange for me, but my experience says,
it is *true*.
I think Knuth is good for a lot of things, but I also think he spends way
too much time on corner cases and *proving* things.
did not get what you intend to say, technically.
There are only so many neurons and I think there are much better ways to allocate
them.
I am not from an native English-man , so can you explain the meaning of
that.
I think a serious programmer should have Knuth on his shelves, but not try
to comprehend every little nuance of everything he says. That's what indexes are for.


thanks
-- arnuld

Jun 14 '06 #6

P: n/a
Noah Roberts wrote:
comp.programming
ok, got it.

Knuth is for when you want a Master's or Docterate in CS.

ha, ha, ha ;-). never knew this one. on the contrary i thought he
writes for average programmers. I am happy to see someone just broke my
belief.
I own a set, I've read some of it and actually comprehended a little. It's hardly
ever practical; in fact I don't know that I have ever found a practical
use for anything in the Knuth books.
i thought he created TEX and METAFONT only by using his AoCP books. Am
I pretty wrong?

so what exactly is real stuff?, in context of algorithms, & where can i
get that real-suff?
Most of the stuff he talks about is spoken of in simpler terms elsewhere.
in CORMEN or SEDGWICK? or somewhere else
To get through the math part you need lots of algebra. That's pretty
much all he uses. You need to know summations and whatever you call
the multiplication equivelant. You'll need logs and powers. That's
about it. Some practice creating formulas for real world problems
would be very helpful.
ok, i got it, my trouble is algebra.
In TAOCP itself he says it is not necissary to read CH1 to understand
most of the rest of the books. It will help to understand the proofs
though.
I will try this style.
Even if you know the math he uses it in very advanced ways. He IS a
mathmetician. Have fun.


thanks a lot, Noah, my friend.

-- arnuld

Jun 14 '06 #7

P: n/a
arnuld wrote:
No, you are not right.

Excellent programmers are born, not made.
I just don't agrre with this. I know at least 2 more guys who will not
agree with you. they are Albert Einstein & Isaac Newton. Newton once
said: "if other people could think as hard as i thought, they would
have gotten similiar results".


Huh? Do you not see the 'if' and 'could' in the Newton's statement?
*If* I *could* run as fast as a cheetah, I'd be the world champion in
sprint.

"I spent all of my life and i say, *kings* are not born but made,
through suffering and hardness. these women are dangerous, you can
never know them. "

-- father of ALEXANDER

[...]

my learning curve & experience of life force me to think that Newton &
what father of Alexander said was right but how can i apply this to
learning from Knuth?
Ability to learn is genetic. And it's not binary (either there or not
there), it's analog (you have as much as you inherited). If you can
learn from Knuth, you'll be able to, after you read it some number of
times. Some people can learn from Knuth on the first reading, some have
to read several times before they grasp the ideas. Also, different folks
learn different things from Knuth. It all depends on two main things:
your desire/intent and your ability. The former you develop, the latter
you mostly inherit.
[..]
I think Knuth is good for a lot of things, but I also think he
spends way
too much time on corner cases and *proving* things.


did not get what you intend to say, technically.


TAOCP is mostly a theoretical book, not an instruction manual.
There are only so many neurons and I think there are much better
ways to allocate them.


I am not from an native English-man , so can you explain the meaning
of that.


Your brain has a limited capacity for learning (just like everybody
else's). Learning is based on memory. Memory is formed in neurons.
With the limited number of neurons in your brain, you have to choose
what to use the for.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jun 14 '06 #8

P: n/a

arnuld wrote:
Noah Roberts wrote:
comp.programming
ok, got it.

Knuth is for when you want a Master's or Docterate in CS.

ha, ha, ha ;-). never knew this one. on the contrary i thought he
writes for average programmers. I am happy to see someone just broke my
belief.


Definately NOT for /average/ programmers. No, he is for people
interested in the theory behind what they do. There is need for such
people but practical knowledge for the average programmer it is not.
I own a set, I've read some of it and actually comprehended a little. It's hardly
ever practical; in fact I don't know that I have ever found a practical
use for anything in the Knuth books.
i thought he created TEX and METAFONT only by using his AoCP books. Am
I pretty wrong?


The language most often used to describe algorithms in his books
doesn't actually exist as a real programming language. There are
emulators of the machine in question and assemblers that will assemble
the assembler code for his made up machine but it doesn't actually
exist.

Besides, he wrote his books in TEX. Chicken/egg. I dunno.

He could have made TEX using algorithms he designed or proved in his
books and papers. In fact, the algorithms and data structures
discussed in his books are so fundamental to what we do that it would
be odd if he didn't use them, and likely nothing BUT them, in his own
work. His books are nothing if not complete ;)

Actually I take back what I said about practicality if you include his
papers. His paper on the AlphaBeta algorithm, though I didn't read it,
was very important to the world of chess AI programming and I have used
that algorithm and read papers that cited and expanded his to improve
my own engine.

But again, these things are described much simpler in other places.
His books and papers are very detailed and exact and can be very
difficult to digest. If you just want to use the algorithm or data
structure in question then you don't need all that. Knuth is
theoretical, if you want 'practical' you can get your information more
easily elsewhere. This doesn't mean Knuth is not important...it just
means he has a totally different goal in discussing things.
so what exactly is real stuff?, in context of algorithms, & where can i
get that real-suff?


bookpool.com and look up algorithm. Since you are in the C++ newsgroup
I assume that is the language you want to use...try something specific
to that language. Hell, it might even make the discussion topical.

Jun 14 '06 #9

P: n/a

Victor Bazarov wrote:
Your brain has a limited capacity for learning (just like everybody
else's). Learning is based on memory. Memory is formed in neurons.
With the limited number of neurons in your brain, you have to choose
what to use the for.


Worse, we only use 10% of those nurons as far as science can tell.
Certainly for most things we think of as "thought" and "memory". In
fact, they are only represented by some fraction of the 10%....the rest
of that 10% are feelings, instincts, and body control. So really, our
storage capacity is quite limited unless you find a way to access that
other 90%.

Jun 14 '06 #10

P: n/a
Noah Roberts wrote:
Victor Bazarov wrote:
Your brain has a limited capacity for learning (just like everybody
else's). Learning is based on memory. Memory is formed in neurons.
With the limited number of neurons in your brain, you have to choose
what to use the
... should be "them" ..
for.
Worse, we only use 10% of those nurons as far as science can tell.


Doesn't necessarily mean it's true. Science just can't tell what the
rest of them are used for.
Certainly for most things we think of as "thought" and "memory". In
fact, they are only represented by some fraction of the 10%....the
rest of that 10% are feelings, instincts, and body control. So
really, our storage capacity is quite limited unless you find a way
to access that other 90%.


Again, the knowledge about *how* we use our brains or how *much* or them
is at this point severely limited by today's methods of measurement.
Please do not confuse it with what's going on in reality. Science is
just as much a reflection of reality as anybody's opinion, and as such
can (and most likely does) present a distorted picture.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jun 14 '06 #11

P: n/a
> Huh? Do you not see the 'if' and 'could' in the Newton's statement?
*If* I *could* run as fast as a cheetah, I'd be the world champion in
sprint.
no, you and i can not run like a cheetah but if you can run like
"Milkha Singh" (a.k.a. "Flying Sikh"), then you can create a world
record. Flying Sikh did.

("Sikh" is the name of a religion originated in punjab state, INDIA)
Ability to learn is genetic. And it's not binary (either there or not
there), it's analog (you have as much as you inherited). If you can
learn from Knuth, you'll be able to, after you read it some number of
times. Some people can learn from Knuth on the first reading, some have
to read several times before they grasp the ideas. Also, different folks
learn different things from Knuth. It all depends on two main things:
your desire/intent and your ability. The former you develop, the latter
you mostly inherit.
you are right.
TAOCP is mostly a theoretical book, not an instruction manual.
got it. it realy hurt my feelings as from my experience as a salesman,
never trust theory,
just go to the door-to-door selling and sell water-purifiers &
cigarettes & whatever, but sell. you can not learn selling from a book.
you have to go out. i did and i am proud of myself that i worked as a
salesman and a waiter. it was *real* & *practical* experience, totally
opposite from what motivational speakers like Zig Zigler or Shiv Khera
in USA tell.

Your brain has a limited capacity for learning (just like everybody
else's). Learning is based on memory. Memory is formed in neurons.
With the limited number of neurons in your brain, you have to choose
what to use the for.
ok. OP was taliking about neurons biologically, i know about them. i
thought it was a cliche.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask


thanks victor, you are good at 2 things:

1.) at technical things

2.) at communicating your ideas clearly.

are you a businessman?

--arnuld

Jun 14 '06 #12

P: n/a
Victor Bazarov wrote:
Noah Roberts wrote:
Victor Bazarov wrote:
Your brain has a limited capacity for learning (just like everybody
else's). Learning is based on memory. Memory is formed in neurons.
With the limited number of neurons in your brain, you have to choose
what to use the
.. should be "them" ..
for.
Worse, we only use 10% of those nurons as far as science can tell.


Doesn't necessarily mean it's true. Science just can't tell what the
rest of them are used for.

he, he, i like this guy named Victor 8-)
Science is just as much a reflection of reality as anybody's opinion, and as such
can (and most likely does) present a distorted picture.


you are right, Victor. this is what exactly Newton & Einstein said &
even nearly all Mathematicians said exactly the same things after they
put their theorms & formulae in front of us.

thanks for your time.

-- arnuld

Jun 14 '06 #13

P: n/a
Noah Roberts wrote:
arnuld wrote:
Noah Roberts wrote:
But again, these things are described much simpler in other places.
His books and papers are very detailed and exact and can be very
difficult to digest.
this is what exactly he said in the Preface of "Concrete Mathematics".
He saays:

"after you will complete this book, you will never settle for nearly
correct answers because then you will be able to produce *exact*
results.
If you just want to use the algorithm or data
structure in question then you don't need all that.
well, truth is quite *surprising*.
Knuth is theoretical, if you want 'practical' you can get your information more
easily elsewhere. This doesn't mean Knuth is not important...it just
means he has a totally different goal in discussing things.
do you want to say that:

ther are 2 different style of presentation--

*in theortical type*

Knuth presents his ideas better than all other authors.

*in Practical type*

here comes authors like Sedgwick, Cormen, Aho etc ( i dont
know any other except Niklaus Wirth) where each has different pattern
for his writings.

bookpool.com and look up algorithm. Since you are in the C++ newsgroup
I assume that is the language you want to use...try something specific
to that language. Hell, it might even make the discussion topical.


you are right. I am trying to learn C++. untill now, from searching the
archives, i have come down to 3 choices :

(from comp.lang.c++, comp.lang.c++.moderated & ACCU.org)

Robert Sedgwick, Cormen et al, & Aho et al.
what do you say about Niklaus Wirth's algorithms+dat
structures=programmes

nobody recommended that but i am curious.

(all of these are available in INDIA ;-), pretty good thing)

thanks for your precius time.

-- arnuld

Jun 14 '06 #14

P: n/a
arnuld wrote:
[..]
thanks victor, you are good at 2 things:

1.) at technical things

2.) at communicating your ideas clearly.

are you a businessman?


Not sure what you mean. I work for living. It is my business.
So, I am a businessman. Everybody who works for living is one.
I am not a salesman, I have no training (either self- or formal)
in sales. Currently my field is software engineering and it's
been for the last couple of decades. I am not a manager. Does
that answer your question?

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jun 14 '06 #15

P: n/a
> Not sure what you mean. I work for living. It is my business.
So, I am a businessman.
again, playing with words :-)
Everybody who works for living is one.
I am not a salesman, I have no training (either self- or formal)
in sales. Currently my field is software engineering and it's
been for the last couple of decades. I am not a manager. Does
that answer your question?


well, you always provide a puzzle tothe person who asks a question and
in that puzzle
the person finds what he wants. different persons find different things
according to their thinking and desires. you did this to me when i saw
you 1st time.
thanks a lot

--arnuld

Jun 14 '06 #16

P: n/a
Noah Roberts wrote:
Victor Bazarov wrote:
Your brain has a limited capacity for learning (just like everybody
else's). Learning is based on memory. Memory is formed in neurons.
With the limited number of neurons in your brain, you have to choose
what to use the for.

Off course there's some limit to our memory, but according to the
memory research I've read, it appears almost boundless practically
speaking. The limiting issue is not storage space so much as recall
ability.
Worse, we only use 10% of those nurons as far as science can tell.
Certainly for most things we think of as "thought" and "memory". In
fact, they are only represented by some fraction of the 10%....the rest
of that 10% are feelings, instincts, and body control. So really, our
storage capacity is quite limited unless you find a way to access that
other 90%.


The 10% thing is a myth. See, e.g.,

http://www.snopes.com/science/stats/10percnt.htm

Cheers! --M

Jun 14 '06 #17

P: n/a
On 14 Jun 2006 12:41:18 -0700, "mlimber" <ml*****@gmail.com> wrote:
Off course there's some limit to our memory, but according to the
memory research I've read, it appears almost boundless practically
speaking. The limiting issue is not storage space so much as recall
ability.


Discovery Channel (I think ) ran a program recently where they
followed this British chap around who could recall PI to eleven
thousand digits. Took him almost 6 hours. He recited it without a
single mistake.

Turns out that was just the tip of the iceberg. He was an "idiot
savant" without the idiot. He could communicate very well which makes
him extra special. It was interesting when the producers flew him to
America to meet "Rain man." Rain man seemed to be much more the
typical savant.

From what I saw and have studied (neural nets lead me to real human
brain studies) it's not just capacity and recall, it is also the way
our brains are "wired." An average person has very small "pathways"
from the left and right brain. Apparently genius / savants have
enormous pathways to each side of their brains that average people
don't have. Also they seem to "sense" numbers more than just calculate
them.

Kind of like a "full asynchronous duplex 1-gig" connection as apposed
to a measly 115k baud com port. :-) Fascinating stuff.

"I think perhaps the most important problem is that we are trying to
understand the fundamental workings of the universe via a language
devised for telling one another when the best fruit is."
- Terry Pratchett :-)
Jun 14 '06 #18

P: n/a
Victor Bazarov wrote:
arnuld wrote:
[..]
thanks victor, you are good at 2 things:

1.) at technical things

2.) at communicating your ideas clearly.

are you a businessman?


Not sure what you mean. I work for living. It is my business.
So, I am a businessman. Everybody who works for living is one.
I am not a salesman, I have no training (either self- or formal)
in sales. Currently my field is software engineering and it's
been for the last couple of decades. I am not a manager. Does
that answer your question?


You should have reordered that paragraph.

"I'm not a manager, I work for a living."

Brian
Jun 14 '06 #19

P: n/a
mlimber wrote:
Noah Roberts wrote:
Victor Bazarov wrote:
Your brain has a limited capacity for learning (just like everybody
else's). Learning is based on memory. Memory is formed in neurons.
With the limited number of neurons in your brain, you have to choose
what to use the for.


Off course there's some limit to our memory, but according to the
memory research I've read, it appears almost boundless practically
speaking. The limiting issue is not storage space so much as recall
ability.


Unlike the computer we use to post to c.l.c++, our brain is not a clearly
delineated CPU/RAM combo. Neurons play the roles of both memory and
processing unit[s]. I would probably likened it more to the enormous
cluster of [partially] interconnected computers with very little RAM and
processing power each. While individual performance doesn't matter much,
what is important is the connections between the nodes. What exactly is
"recall ability", or can we pull some other analogy to a computer here, I
don't know. My explanation to which you decided to comment was merely to
clear the understanding (or the lack thereof) of osmium's reference to
neurons and their allocation. Perhaps I oversimplified.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jun 14 '06 #20

P: n/a
Default User wrote:
"I'm not a manager, I work for a living."


What's the line from the movie? "You don't call me 'Sir'! I'm a
sergeant! I work for a living!!!!"
Jun 14 '06 #21

P: n/a
hey folks,

It's really amazing. I just solved the exercise-13 in
chapter-1 of "Concrete Mathematics". i thought i will never be able to
do that but i did, & yes straight through the "homework execise"
skipping warmups completely. WOW!. Paul Graham's principle really
works. Paul Graham said:

"if you asked random people on the street if they'd like to be able to
draw like Leonardo, you'd find most would say something like "Oh, I
can't draw." This is more a statement of intention than fact; it means,
I'm not going to try. Because the fact is, if you took a random person
off the street and somehow got them to work as hard as they possibly
could at drawing for the next twenty years, they'd get surprisingly
far. But it would require a great moral effort; it would mean staring
failure in the eye every day for years. And so to protect themselves
people say "I can't." (1)

well, now i came to know one thing:

"there are no miracles in ordinary lives & Isaac Newton, Alexander,
Albert Einstein, Leonardo Da Vinci were ordinary men.".

if something feels too complicated at first sight, then remember your
brain will take some time to immerse into that special type of
thinking. work *hard* & take your time for that. when i tried Concrete
Mathematics for the 1st time, it was just WOO-HOO! & this WOO-HOO!
existed for 5th time too. now i am understanding Knuth's theories,
slowly.

but i am not going to do CM becuase that is *not* my need. today i
picked it up with the intention of understanding it & solving a
problem, not to mention only for the pure enjoyment of it. i have other
needs, for now. i need to learn C++, LISP, Algorithms, Data-Structures,
learning about OSs, so that i can settle for a god job/business after
contributing some time to FSF. All of this was feasible because of you
*folks*, you gave me clarity on the role of CM in becoome a good
programmer & removed the fog of confusion from the front of my eyes. I
owe many thanks to you.
special thanks to "Noah Roberts".

-- arnuld
(1) see www.paulgraham.com

Jun 16 '06 #22

This discussion thread is closed

Replies have been disabled for this discussion.