Kaveh

So you are not pointing an error just in this textbook, but trying to argue that all proofs of a famous result that has been checked by tens of thousands of experts and even has computer verified formal proofs is wrong. I will not comment any further. You might want to read this.

You can continue to believe whatever you want. :) I have no reason to argue with someone who doesn't want to learn. (Even if there was an error in the presentation in the book, the overall proof is well known and even checked by computer, this is really not a research level question).

1. This is definitely not research level, this is more like a typical undergraduate student misunderstanding textbook (I shall know since I have been an instructor for such courses). 2. You are not going to win any favors with reposting. 3. If you genuinely want to understand where your misunderstanding is I would suggest posting on cs.stackexchange.com and asking more humbly, something like "I think I have a misunderstanding, can you help me identify where?", and then people would be more willing to help you figure out where your misunderstanding lies.

@VijayD, yes, it is annoying that good questions and answers automatically turn into CW when they get more than some fixed number of answers or edits. It seems that SE is planning a major reviewing of CW, hopefully this issue will also get solved when they do.

@Emanuele, the reason for adding it was that I thought it would help people understand what you are looking for. ps: the roll-back links are on revisions page which are accessible by clicking on the "edited ..." links below the posts.

@Emanuele, I edited your question to make it more readable (hopefully). Feel free to roll-back or edit further.

Voting to close as off-topic: Can I ask about this cool paper that I just saw on the arxiv?

Re different size boards, I think it would do quite well, it is really understanding the game and positions. You might find this talk helpful: youtube.com/watch?v=Bm7zah_LrmE

Keep in mind that generalized Go is ExpSpace-complete. Re Nim, interesting question, I think it is not difficult for say DeepMind's Atari algorithm to win against most humans who don't know the optimal winning strategy.

[cont.] It is easy to teach someone to run Dijkstra, it is a totally different story to teach someone to invent algorithms. I know people are trying it but hasn't happen yet afaik.

[cont.] You can probably do something similar for finding shortest paths in graphs. But I think the real issue is what you are trying to do. Maybe look at this way: playing chess at human level is not the same as playing optimal strategy in chess. DNNs are helpful for problems that are hard to solve by direct programming like object recognition, playing chess, ... So if you want to think about it this way what you want is not just learning some particular graph algorithm but to learn to solve a large class of algorithmic problems.

I am neither an expert. The ability to play games at human level is a very recent advance. They combined reinforcement learning with DNNs. Intuitively, they do a back track, they use DNNs to compute the value of each position and to compute which branches to explore. These DNNs are trained by playing a very large number of games and the result of the game is feedback through the play to update the weights of the DNNs.

Re multiplication, I asked Ilya and he pointed me to this paper:arxiv.org/abs/1511.08228

maybe, but this does't help the fact that shiism is a very uncommon term.

I just did a simple Google site search

I will add links.

And I have never heard anyone refer to shia islam as shiism before this discussion and I can assure you I read and listen to a lot of English material.

the OP also mentioned shia. As I said, if shiism was a commonly used term it would show up considerably more often than what we see on these major news websites.

Me too. :)

That was my point: the N-gram is misleading.

and Shia do not refer to it as shiism.

If it was it would show up on CNN, BBC, and CBC more than a few times.

I think the N-gram is misleading because it makes people who are not familiar with the usage of these terms that Shiism is a commonly used term. It is not as I exaplained in my answer.

I think the N-gram is misleading

if you edit the N-gram and add Shia as well.

I understand that. I was the down-voter. I will reverse it.

@goldPseudo I removed the previous ones and replace them with a comment that is better conveys my point.

I understand that. Let me rewrite my comments so the issue is resolved.

The OP proposed "shia" as well, and based on evidence I think that is more appropriate than "shiism". If you disagree with this let me know why, otherwise I feel we are starting to talk past each other.

I have read your post. I understand that you don't have a strong position on this, but you did claim that the N-gram contradict the OP's claim and that is what I was criticizing. I think it is pretty clear that the shia is the better term to use, I don't see shiism as a term that is common in any way unless you want to think that BBC has only referred to shia Islam only 6 times ever.

@goldPseudo, I disagree with your claim that the N-gram proves it. The way people refer to it is "Shia". News organization are generally good at devising policies for what term to use and I think we should follow that. In addition your N-gram should have been "shia" vs. "shiism" and the result would be quite different from your graph, see here

ppps: I should really really at least watch their Sedgewick's Coursera lectures so I can make more informed statements. :)

pps: I am all for stating the limitation of models and I completely agree that we often do not do a good job in doing it when teaching.

ps: the example of quicksort does not work because the asymptotic analysis (even + landau notation) doesn't say that quicksort is worst than other ones.

The whole point of asymptotic analysis is that the behavior of the algorithm on large inputs is not different from the limit.

Now I still think the O notation is a good first approximation for simple functions and tasks like sorting and search and basic graph algorithms. If you think that is not true you have to come up with examples where it goes drastically wrong. If we are only interested in special small cases then of course we should not use asymptotic analysis.

First, notation is not just for communication. Language has more functions than communication. One prime use of language is computation as we do in arithmetic.

I read the post.

@Raphael,

Sure, I will be pleased to read. (But I don't know if I would have much to say.)

@Raphael, I have them on my list. But there are always to many book to read and too many lectures too watch. :) I should say I didn't like their intro algorithms book that much.

pps: I don't know much about analytic combinatorics. Sedgewick coursera course is on my list but I don't know when I will have time for it or their book. :)

ps: I removed my comments under the post now that we have them here.

If you know a good alternative to asymptotic analysis and performance tests then I would be very interested to learn about it.

Often tasks are repetitive in practice so you can actually get good estimates.

e.g. 90% under 1m, 99% under 10m, 99.99 under 30m, and don't care about the remaining .01%.

More often we care about the time for different percentiles of running time

Other times we care about average.

Other times we care about the worst case running time.

Sometimes we have strict limits on time for an operations (e.g. UI interacting with user).