Computer Science

12:21 AM

Hmm. Yet another "how do I solve a recurrence with a square root?" question:

0

Q: Not sure if my recurrence is correct for T(n) = 2T(n^.5) + O(1)

I have T(n) = 2T(n^.5) + O(1) = 2(2T(n^.25) + O(1)) + O(1) = 2(2(2T(n^.125) + O(1)) + O(1)) + O(1) and so on To me this seems wrong, and I don't know where to go from here to reach a Big-O solution... Thanks in advance.

Interestingly, none of the questions actually have the words "square root" in the question body or title and so may be more difficult to search for as a result.

(Several of the answers use the phrase "square root").

Also interestingly: google searches for "recurrence sqrt" and "recurrence square root" return a ton of answers from math.stackexchange.com and stackoverflow.com, but not ours, on the first page of results. :-(

Raphael

9:50 AM

@WanderingLogic Hm. Can you divine the reason? It may be worth editing the questions we have so they are easier to find, once we know how.

(IIRC, SE search does go through the LaTeX source so sqrt should return hits on posts that contain a TeXed square root somewhere.)

Yes, it does.

Raphael

10:14 AM

@WanderingLogic I edited our "standard reference" (I don't think it quite qualifies as reference question, in particular because the actual reference question contains methods on dealing with such recurrences) so searching works better.

In particular, it's not listed on recurrence+square root and still for the sqrt query.

In my filter bubble, Google showed the question anyways? (2nd position)

But true enough, bubble-free DuckDuckGo looks worse. Startseite (which afaik uses Google, without a bubble) showed it.

So I think we are fine. :)

(And you broke your filter bubble. ;))

Oh, @WanderingLogic, thought you'd appreciate this quote by Stephen Wolfram:

2

> I’ve been doing language design now for 35 years—and it’s the hardest intellectual activity I know. It requires a curious mixture of clear thinking, aesthetics and pragmatic judgement. And it involves always seeking the deepest possible understanding, and trying to do the broadest unification—to come up in the end with the cleanest and “most obvious” primitives to represent things.

And from the same article, @Gilles, with some tongue-in-cheek on my part:

> But there’s actually only a quite small set of constructs and concepts that can be represented with any degree of standardization in mathematical notation

Wandering Logic

11:22 AM

@Raphael It seems to have improved on Google substantially since last night! Perhaps their spider already hit the changes? (You can, supposedly, turn off your filter bubble by clicking the little "planet earth" icon in the upper right corner of the screen.)

I also just checked Bing. There it is currently showing up near bottom of first page for search "solve recurrence square root" and on second page for "recurrence square root".

I guess I shouldn't worry so much that we're getting beat by stackoverflow.com and math.stackexchange.com on questions with similar content. It makes sense that PageRank-like algorithms would favor order-of-magnitude larger traffic sites.

@Raphael Thanks!

Programming languages really are a special kind of artifact. Works of art that reflect their creator's personalities and knowledge.

Raphael

1:03 PM

@WanderingLogic Some search results showed the old title, so I thought it had not been re-soidered yet.

38

Q: How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem instances, including a few simple "corner cases". This is a great heuristic: it's a great way to q...

algorithms algorithm-analysis education correctness-proof didactics

Should we delete all "answers" that state/list bugs instead of algorithmic errors? They explicitly don't answer the question.

FrankW

1:17 PM

@Raphael Are you talking about upvoted ones as well as downvoted ones?

FrankW

1:29 PM

By my count that would leave 5 answers: Rick Decker's, yours, and the 3 top voted ones.

FrankW

1:43 PM

I'd say put away with them. But given the vote patterns, I'm not sure this is shared by many in the community: Quite a few of these answers have only a single downvote.

Raphael

@FrankW That's part of the question. Should we care about upvotes on non-answers? The question was hot, and its plausible that a number of people did not get the question; the non-answers serve as evidence.

@FrankW I did not go and count; wanted to get a feel for the "room" first.

I'm for deleting, too; in particular because D.W. commented on them to that effect and the answers were not changed.

@d.w. What do you think? (see above) In case you can't/won't join chat feel free to make your opinion known via votes/flags.

In any case, I'd rather it happened by community votes than mod-hammers.

FrankW

@Raphael Be aware, that even with 10k-tools we can't vote to delete non-downvoted answers.

Raphael

@FrankW Ah, there's that. Flagging it is, then.

FrankW

I've voted to delete, where I'm allowed to. Should I flag other answers, given that you are already aware of my opinion?

Raphael

@FrankW Yes, please. It adds a paper trail to the platform and allows us to collect multiple flags before acting.

@FrankW Nikos M.'s answer is fine, isn't it?

Not sure about DanaJ's; haven't read in detail.

FrankW

1:59 PM

@Raphael Might depend on how you look at it. I took it as pointing out a common error in implementing a per se correct algorithm. But rereading, I notice it can be taken otherwise.

@Raphael From the comments it seems that 2 of the 5 examples fit the question.

So both could be labeled as being answers, but not good answers.

Raphael

@FrankW So we'd prefer a trimming edit; that justfies a downvote. click

@FrankW Defending the answer, I read it as "Shuffling is often done wrong. This is how it does work, but this is how people tend to attempt it, and this is how this is wrong." Sounds fair to me.

FrankW

I'd have retreated my flag, if that were possible.

Raphael

@FrankW That's easy to remedy, I'll dismiss it. :)

Wandering Logic

2:36 PM

@Raphael I'm happy to let StackExchange's voting mechanism do its work over time. Are not the best (real) answers rising to the top? If there are ways in which that social-engineering mechanism encourages wrong answers or non-answers to rise to the top then shouldn't we ask for fixes to the mechanism, rather than trying to second-guess it?

Raphael

@WanderingLogic The rising does not seem to happen, due to the high influx of ill-informed votes during the hot-question period.

The way I see it, lots of users unaccustomed to out site broke the game for this one question. The fact that D.W. clarified the question late and only in the comments probably didn't help. I think it's reasonable to fix this singular case "with force"; it does not indicate a problem with the mechanism of the site. (It does indicate the hot question business is a dirty one, but well.)

vzn

3:47 PM

re wolfram. am not very fond of his math language in Mathematica. found the notation hard to work with. precedence hard to decipher/ remember.

wolfram is a very controversial figure in TCS. really like his work in (cellular) automata theory as pioneering but many other TCS researchers are not fond of him.

some of that may be due to his more applied physics bkg.

(interesting blog entry by him thx for the ref)

wolfram mathematica code reminds me a bit of perl where there are too many rules & not easy to predict/ remember how they interact in the parser. clearly simplicity is an important part of language design.

Wandering Logic

6:00 PM

@vzn That's because he is one of those researchers who is very bad at sharing credit for things that he discovered simultaneously, or even a little after, someone else. If you read "a New Kind of Science" you might be led to believe that Wolfram almost invented the field of cellular automata all on his own, where in fact, AFAIK, he did very little to establish the field or move it forward.

Raphael

@WanderingLogic So he's a Steve Jobs of science? ;)

Wandering Logic

My impression is that he's a genius who really did independently re_invent large swaths of cellular automata theory and who is better at _explaining it than almost anyone else. But he's not particularly strong on the history of the field, so his excellent explanations tend not to talk about the history.

That leaves the people who did the work earlier than him feeling bitter and unappreciated.

Raphael

That's unfortunate then. :/

Wandering Logic

It may be a fine way to do science, and advance science even, but it's a poor way of winning friends and influencing people.

@Raphael Yes.

Wandering Logic

6:35 PM

But you shouldn't take my word for it. I'm just relating various scurilous 4th hand gossip related over coffee at faculty lunches. Surely someone active on tcs.se could give you a more accurate/fairer picture.

vzn

lol WL dont you know that tcs.se is also for "scurrilous 4th hand gossip related over coffee at faculty lunches"... at least in the comments :\

do not overly disagree with your characterization/ reputation of wolfram.

he does seem to be weak on crediting others. in his defense, NKS does have extensive endnotes citing others afaict.

cited wolfram a few times on tcs.se & learned the hard way that he's apparently got few fans in the TCS crowd.

seems NKS has not turned out to be all that influential as far as introducing any new techniques.

think it does accurately herald a new massive/ wondrous terra incognita but he has only pointed at it, which is quite different than illuminating it... the key challenge of science...

anyway he seems to be a polarizing figure...

maybe some in academia have some hard feelings about him getting quite rich off his expensive/ largely proprietary math software, sold to many universities.

NKS does anticipate/ nail a new angle in science more recently promoted by other theoreticians known as the algorithmic lens...

need to blog on the guy sometime...

he does seem to have an exaggerated grandiosity at times...

(listed in the TMachine mad genius profiles, wink)

god, stephen wolfram, and everything else forbes 2000

which reminds me of an old (silicon valley) joke about larry ellison (multibillionaire ceo Oracle)...

> "the difference between god & larry ellison is that god doesnt think he is larry ellison" lol

have noticed algorithmic lens pov very similar to his so-called principle of computational equivalence... aka Turing completeness...

Wandering Logic

7:40 PM

@vzn That's a fascinating Forbes article.

Something of a personal coincidence for me on Page 7. forbes.com/asap/2000/1127/162_7.html

I happen to be reading Stephen Jay Gould's Structure of Evolutionary Theory.

This was the last book Gould wrote before he died in 2002 (about the time that Wolfram finished NKS). Like NKS it is kind of a "magnum opus". (My term for a 1400 page book that makes it very easy for me to fall asleep every night.)

The Forbes article talks about a specific critique that Wolfram has of a result in Gould's dissertation.

Interestingly, Gould over the course of his career went from being a staunch Darwinist (like Dawkins or Dennett now-a-days) to having a much subtler view of natural selection.

From what I've read recently of Gould he would actually have been delighted by Wolfram's finding on possible sea-shell shapes.

Gould spends a relatively large chunk of his book talking about "channels", which is basically the modern version of a classic (early 20th century) critique of natural selection.

Natural Selection, in its basic form, requires changes from generation-to-generation to have no preferred direction. But there is (according to Gould) a lot of evidence from embryology that certain kinds of changes can only happen in a small and limited number of directions.

Much like Wolfram's proof that there can't be "thousands' of sea-shell shapes, but only six.

Also. Gould's claim to fame actually isn't his dissertation, but the theory of Punctuated Equilibrium, which is considered by most Darwinists to be a critique of the basic Darwinist principle that the important parts of natural selection occurs on organisms (rather than genes or species.)

Again: thank you for the article!

vzn

8:28 PM

:)

the article is ~1½ decade old now but a great & maybe even timeless read

re evolution, there is a lot of new thinking on that in a short amt of time in biology due to many advances across many areas.

maybe chat more on that here?

The Biosphere

General discussion for biology.stackexchange.com

1

evolutionary theory interests me a lot too. you might enjoy Red Queen by Ridley, a book that was very influential on my thinking on the subj...

there are also a few (encouraging) signs of increasing crosspollination between TCS & evolutionary theory...

NKS as "magnum opus", touche

re evolutionary theory, another major/ high profile figure on that is Dawkins.

re NKS/"techniques"... was thinking after writing that, the real major advances in TCS are often all about techniques...

even eminent mathematicians (eg Terence Tao) are known to occasionally refer to "theoretical machinery" as "technology"

24

Q: Ecology and evolution through the algorithmic lens

The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very discrete nature (see for example SLBS00) and could benefit from a computer science perspective. Yet, I a...

reference-request big-picture application-of-theory evolutionary-game-theory algorithmic-lens

The Biosphere

Transcript for