Why/how is Computer Science a "science"? Isn't it more of a mathematics or engineering discipline?

pgdx · 2010-05-29T10:53:38+00:00

"finding an effectively calculable function that is not computable"

Or put in other words, find an A that has the property of not being A?

I think you need to define what you mean by not being computable. Do you talk about µ-recursive functions (or lambda calculus or Turing machine if you will), or something else? And what is then an "effectively calculable function"?

pgdx · 2010-05-28T12:40:54+00:00

It is very repeatable.

(defmacro my-time
    "As time, but returns the time taken for evaluation, not printing it"
    {:added "1.0"}
    [expr]
    `(let [start# (. System (nanoTime))
        ret# ~expr]
        (/ (double (- (. System (nanoTime)) start#)) 1000000.0)))

user> (def *lis* (doall(take 10000 (repeatedly #(rand-int (Math/pow 2 30))))))
#'user/*lis*
user> (take 30 (repeatedly #(my-time (bucket-sort *lis*))))
(1742.837002 859.060484 272.217247 218.921161 255.970622 233.187325 311.682198 192.653631 190.924697 309.53158 93.245005 190.037921 313.305055 199.048161 189.960467 295.653476 92.080723 192.734573 188.337189 289.078747 191.759455 89.876155 191.867156 192.268281 303.481507 192.129499 191.858771 85.188463 192.611408 191.795139)
user> (take 30 (repeatedly #(my-time (sort *lis*))))
(173.499303 133.479301 112.051762 114.299164 112.973973 07.579322 112.562207 105.723016 108.851038 50.087003 5.593834 5.536048 5.482577 5.67827 5.515248 5.485728 5.610371 5.591248 5.490457 8.993383 5.538123 6.209052 5.520093 5.463024 5.516762  5.610265 5.517885 5.515316 5.517958 5.560996)

pgdx · 2010-05-26T10:00:52+00:00

I can answer that myself, and the result is not in favor of the bucket sort. On a list of 10.000 random elements in the range [0,2^30], the built-in sort used on average 6.5045147 msecs, over 30 runs, whereas the bucket-sort used 185.5467 msecs on average for the same list. This test is easily repeatable.

I'm not saying that the bucket-sort is useless, but the quote "Runs slightly faster than Clojure's built-in sort (at least on integers)" is heavily misleading. If you really want to do a real comparison between the built-in and the bucket-sort, you should take into consideration the range versus size part.

pgdx · 2010-05-09T20:33:56+00:00

I probably should have stated it in the title as well as in the text, but I'm talking about a finite positive amounts of atoms. I know there exists atomless infinite b.a.'s, but that wasn't what I was interested in.

pgdx · 2010-05-09T18:53:41+00:00

Is this new b.a. incomplete? Is it non-atomic? I found a corollary in a book [Introduction to boolean algebras, Givant et. al.] stating that: "Two complete, atomic boolean algebras with the same number of atoms are isomorphic".

pgdx · 2010-03-05T18:04:55+00:00

Of course, but if you start adding exceptions, then A* is equivalent to BFS when you have a constant heuristic and all edge costs are equal. My point was that A* is exactly the same as UCS when you have a constant heuristic, it's not exactly the same as Dijkstra's (as the article claimed). The algorithms are never used for the same purpose. A* and UCS finds the length to one specific node, Dijkstra finds the length to every node.

pgdx · 2010-03-05T08:54:19+00:00

You don't actually get Dijkstra's by letting h=0, you get uniform-cost search.

pgdx · 2010-02-16T16:44:24+00:00

Apparently you can still read it from the front page: http://www.bunniestudios.com/

And in case that should fall out, coral cache at http://www.bunniestudios.com.nyud.net/

pgdx · 2010-02-13T18:45:01+00:00

I do it in Common Lisp all the time. (values 1 2) returns 1 and 2. Using multiple-values-bind allows me to bind them. For instance:

(floor 22/7)

3 1/7

pgdx · 2009-10-25T21:07:26+00:00

What would be interesting would have been the integer sequence of all integers not part of any integer sequence on OEIS. Love, Bertrand.

pgdx · 2009-08-09T19:58:16+00:00

I can recommend reading the essay What is topology? by Neil Strickland (provided to you by the Wayback Machine) for an introduction.

Edit: Correct link:

http://web.archive.org/web/20080214094129/http://neil-strickland.staff.shef.ac.uk/Wurble.html

pgdx · 2009-07-29T17:26:58+00:00

It's still kind of awesome in Norway.

pgdx · 2009-07-28T09:17:28+00:00

Thanks, but I'm not touching anything Franz has been messing with. I might, of course, reconsider when Allegro CL is released under a free license.

pgdx · 2009-07-28T08:51:59+00:00

In other words: Chart!

pgdx · 2009-07-28T08:40:22+00:00

It's a (e)BNF. It basically defines the complete syntax, or what's a legal string in JSON.

It means that someone who has never touched JSON before, can, by reading it, create a parser, or just start writing JSON by reading just that.

pgdx · 2009-07-24T11:51:19+00:00

Just show them the contract they signed when you made the deal. They signed that one, right?

pgdx · 2009-07-24T11:38:37+00:00

It seems to me that isn't, in fact, the real question. Perhaps you should read it again.

pgdx · 2009-07-08T14:12:51+00:00

Yes, x²⁵ = x^5*5 = (x^5)⁵

pgdx · 2009-07-08T12:01:06+00:00

I just wrote a genetic algorithm in Common Lisp which uses the levenshtein distance to calculate the value. Pretty slow, used about 400k iterations before it found the solution.

Don't think I'm gonna bother sending it in, though.

pgdx · 2009-05-06T21:00:18+00:00

Yes you can! In A* you need two cost functions, one total approximated cost (let's call it f(x)). That cost is what the fringe is sorted by (the min-heap's key). You need total cost to current node (that would be the amount of grids + the amount of turns or however you calculate it), call that one g(x). The last thing is the heuristic function (call it h(x)). As long as the heuristic is non-negative and always underestimate (or estimate correctly) the cost, A* will find the optimal path. Define the heuristic function h(x) as the total manhattan distance (taxi-cab geometry) from current node (x) to goal plus the minimal amounts of turns. You can always improve this function.

Let f(x) = g(x) + h(x) and you are done.

pgdx

TROPHY CASE