Computer Science

« first day (1116 days earlier) ← previous day next day → last day (3312 days later) »

vzn

12:44 AM

@thomas ?!? "writing a widely acclaimed comprehensive ref of a field" is indeed "playing a special role" in the field

elsewhere, via reddit

Turing Machines and the Busy Beaver Game / Faustini

overexchange

1:01 AM

@WanderingLogic Do you know any good resource on exception handling design strategy for distributed products where java packages run on multi layer design on multiple machines?

10 hours later…

Thomas Klimpel

10:33 AM

@vzn The question was whether the definitions of $M$-automata can be traced back to volume B from 1976 of S.Eilenberg's "comprehensive reference". Eilenberg himself seems to blame Schützenberger, but Mathematical Foundations of Automata Theory by Jean-Eric Pin indeed seems to blame the volume B from 1976. This is also the volume referenced in my German book...

2 hours later…

evinda

12:03 PM

Hello!!! :)

I want to find a counterexample in order to show that the following proposition does not hold.

For a Dynamic Programming algorithm, the calculation of all the values with bottom-up is asymptotically faster than the use of recursion and memoization.

Could yu give me a hint?

evinda

1:01 PM

@Telastyn @Juho Do you maybe have an idea?

Telastyn

1:12 PM

this is not my strong suit, but I'm not sure I see why you might think that was the case.

I would expect a calculation to take the same amount of operations, regardless of the order you perform them in.

1 hour later…

overexchange

2:24 PM

@WanderingLogic In insertItem() can I avoid this code, because the code does not look more elegant.

if(this.rest() == null){
				return new Sequence<T>(this.first(), new Sequence<T>(item, null));
			}

5 hours later…

evinda

7:39 PM

@Telastyn You mean that they require asymptotically the same time?

Telastyn

@evinda - that would be my expectation. Though I would also expect that not all memoizable problems be memoizable bottom up.

but again, this is not my strength.

evinda

@Telastyn I thought that with bottom-up we start from the computation of the smallest subproblem, which we will need for the computation of the greater ones... At recursion, we start from the greater problems and in order to calculate them, we find the smaller ones..
Does it hold that each subproblem builds on already computed subproblems, and so doesn't need to solve them again each time in both cases?

Telastyn

not sure. seems likely when you explain it that way.

evinda

@Telastyn Ok

@Telastyn Could I also ask you something about the time complesity of an algorithm?

Telastyn

sure, though others may be more helpful.

evinda

7:51 PM

@Telastyn I have to use a Divide-and-Conquer procedure for the computation of the i-th greatest element at a row of integers and analyze the asymptotic time complexity of the algorithm. I tried the following: http://pastebin.com/rPnc74gd
Then the time complexity will be T(n)=Θ(n)+T(q-1)+T(n-q), right? How can we compute tha latter without knowing the value of q?

Telastyn

I am not certain, though I would expect a log of some sort if the partitioning is doing anything.

evinda

@Telastyn What do you mean with a log of some sort?

Telastyn

I mean, usually algorithms with partitioning (quicksort, searching a RB tree) have log in their complexity.

« first day (1116 days earlier) ← previous day next day → last day (3312 days later) »

all rooms