@Raphael yeah, and it's the deadlines season, which leaves me even less time (:
@Gilles Actually, I do believe it deals with randomized algorithm, maybe not the way it was asked, but to my knowledge, the field in CS that deals with random-number-generators is randomized-algorithm
OK, so here is a question from a past test in my Theory of Computation class:
A useless state in a TM is one that is never entered on any input string. Let $USLESS_{TM}$ = {$$ | $M$ is a TM that contains useless state $q$}. Prove that $USELESS_{TM}$ is undecidable.
I think I have an answ...
I have a grid of some width and height, where each cell can be of three possible values (presented as white, green and red in this illustration):
You may select any number of green cells (marked blue on the following illustration), which covers all red cells (marked yellow) in a pre-determined...
In mathematics, a rational function is any function which can be written as the ratio of two polynomial functions. Neither the coefficients of the polynomials nor the values taken by the function are necessarily rational numbers.
Definitions
In the case of one variable, x\,, a function is called a rational function if and only if it can be written in the form
: f(x) = \frac{P(x)}{Q(x)}
where P\, and Q\, are polynomial functions in x\, and Q\, is not the zero polynomial. The domain of f\, is the set of all points x\, for which the denominator Q(x)\, is not zero, where one assumes that t...
and another family of examples is the finite fields
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of multiples of $a$ plus a constant:
$$M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \}$$
Is $M$ regular? context-free?
(Contrast with Language of the graph o...
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ be integers, with $a > 0$. Consider the language of solutions of the Diophantine equation $y=ax+b$:
$$L = \{ \bar{x} \mathtt: \bar{y} \mid y = a\,x + b \}$$
Is $L$ ...
I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer. How do you formally define a sub-problem for a problem that you would solve using dynamic progr...
@Gilles Maybe I don't understand the question resp. their solutions well. For me, they talk about formal languages. That they are defined using equations over integers seem tangential (at least to the question).
I am currently learning the lambda calculus and was wondering about the following two different kinds of writing a lambda term.
$\lambda xy.xy$
$\lambda x.\lambda y.xy$
Is there any difference in meaning or the way you apply beta reduction, or are those just two ways to express the same th...
In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ?
This is the case when one use for instance van Emde Boas trees instead of more conventional binary search tree implementations.
But for example, if we tak...
By optimal substructure, I mean that an optimal solution to a problem contains necessarily optimal solutions to subproblems that combined give rise to the problem
This principle of optimality was stated by Belmann in its work on dynamic programming
I am not sure if there are alternative characterizations
what you really need is this: 1) Every problem can be partitioned into subproblems of the same kind 2) Any combination of optimal solutions of these subproblems can be comined to an optimal solution of the original problem
2) is different than what you say; it argues bottom-up instead of top-down, and this is as should be because we combine solutions bottom-up
yes, I know, it's everywhere, but it's wrong. the truth is that Bellman wrote about stuff very different from the things we apply DP to today, and his wording was terrible. There have been several, conflicting interpretations of the so-called "Bellman criterion for optimality"
suppose there is an optimal solution S=f(S1, S2) where S1 and S2 are optimal solutions of subproblems. Now assume we solve the subproblems (independently) and obtain optimal partial solutions S1' and S2'. f(S1', S2') is not necessarily optimal if we only use "your" definition! That would be terrible as we would have to check all possible combinations of all possible optimal solutions.
By the way, the fact alone that we can combine solutions of subproblems to solutions of the original problem is noteworthy. This is not trivial, but often left out resp only said implicitly.
We all know that Markov Chains can be used for generating real-looking text (or real-sounding music). I've also heard that Markov Chains has some applications in the image processing, is that true? What are some other uses of MCs in CS?
take for example syntax trees (CYK parsing). We have to be able to combine arbitrary syntax trees for partial words provided there is a fitting rule. Of course this works, but requiring "A syntax tree for the whole word consists of two syntax trees for a prefix resp a suffix"
yes I fully agree that the actual solution may be different
this is an assumption
given that we said that there can be more than one optimim
but the value will be identical
here we are not interested in recovering a solution
only in what its optimal value is
recovering the actual solution is indeed quite a different story
to recap: my focus is on the optimal value of a solution
so I do not see any difference: all optimal solutions to subproblems are in the same equivalence class; therefore, their combinations can not give raise to different values. They will always give an optimal solution for the initial problem
this is why I say "if and only if", and to me your definition is logically equivalent
Anyway, this discussion was both stimulating and interesting
I never though before to subproblems in terms of equivalence classes with respect to their value
in fact, during the recursion the actual solution may be of utmost importance! Take again CYK: we need to know which non-terminal is the root of the partial syntax tree, otherwise we can not continue. The value ("YES") is of no use.
I think you are wrong, but discussion this via chat is less than ideal :)
really there is no difference (apart from a slightly more efficient implementation) in implementing a DP solution top-down via a memorized, recursive algorithm or bottom-up, in an iterative fashion
again, I do not stress too much the top-down versus bottom-up approach choice
well, actually that one achieves the optimum is implicit: if you characterize correctly a solution to a problem in terms of its subproblems, then optimal substructure on one hand, and taking advantage of overlapping subproblems on the other, will lead you to the optimum
this is not true only if your initial recurrence which is the solution for the problem is based on incorrect subproblems
mmhh, but you know when you are on the wrong track: your definition of a subproblem is wrong only if it does not contain within itself optimal solutions to sub-subproblems!
bold statement. I'd rather have a reliable characterisation, so I don't have to try and find a recursion. In particular, if there is none I can probable never tell.
I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing the set of strings $S$.
Add-Prefix-Set on $\mathcal{D}(S)$: given some set $T$ of (possibly empty...
I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave like a stack, it'd seem that we can actually claim that TMs are more powerful.
Is this true?
This question here: Intuition for logarithmic complexity where the question, and almost all the answers are using BigOh when they really mean Theta and as written, the answers are answering the wrong question (or if you look at it differently, they are incomplete) as they are only explaining Thet...
@Raphael I've taken a look at your bounty on that min-heap question, and I think the suggestion made by Ran G. combined with my idea in the initial question prove that HAL and DHAL are not closed under reversal. However, I'm not sure how much of my proofs you believe - if not, I'll try to give it another shot at writing them down rigorously
@Raphael I'm also quite interested in your idea regarding my question :)
Many intractable problems can be modeled as deciding whether a set of triples satisfy some no-trivial property. For example, 3-edge coloring of cubic graphs can be modeled as the problem of deciding whether a set of triples satisfy that the elements in each triple must have different color.
I'm...
@Gilles Not all (partial) solutions do. Besides, I feel tags should reflect the questions, not solutions. I honestly don't know how to take into account that the language definition uses arithmetics; maybe just not?
@AlextenBrink yes, I have a half-written answer about this, it's not difficult
Then I wrote up the part where I proved |E| <= 2(|V|-1) and realized my proof was wrong
you can partition a graph into subgraph by partitioning the nodes, but that only works if you have no edge between different partitions... I'd forgotten a case
I also thought of coloring edges red or blue, and showing that I can make a red tree and a blue tree. But I can't find a way to split the edges.
As in, if you hit the worst case on a structure, then you must still get the amortized bound even if we keep doing that same operation on the same structure
You can, you can just make 'merge nodes' that, when extracted, get merged into normal tries
Basically you make 'I stopped here' nodes, that you take care of before you expose them via extraction
@AlextenBrink It did, although its an unusual requeset. Basically, every operation adds to the set of structures we have to keep track of. That might render rigorous analysis next to impossible
one of these days we will have to go to my teamspeak server and use on of those online whiteboard thingies... chat is awful for discussions like this :/
Anyway, I think that you might be able to amortize the merges over the extracts, but I'll have to take a good look at the application I have in mind whether I really do about as many extracts as merges...
Basically, I perform O(n) steps that go as follows: I have a constant number of these structures; I do an add-prefix on these structures, merge them together (not all into the same structure, but into several), then do a get prefix and an extract prefix, and then take these structures to the next step, discarding some from both the original as the constructed structures, and sometimes I backtrack to structures I worked with in an earlier step
by the way, do you think it would be worthwhile to make sources/scripts used to create images for questions/answers available so people can access/reuse them?
OK, so here is a question from a past test in my Theory of Computation class:
A useless state in a TM is one that is never entered on any input string. Let $USLESS_{TM}$ = {$$ | $M$ is a TM that contains useless state $q$}. Prove that $USELESS_{TM}$ is undecidable.
I think I have an answ...
I have a grid of some width and height, where each cell can be of three possible values (presented as white, green and red in this illustration):
You may select any number of green cells (marked blue on the following illustration), which covers all red cells (marked yellow) in a pre-determined...
I am currently learning the lambda calculus and was wondering about the following two different kinds of writing a lambda term.
$\lambda xy.xy$
$\lambda x.\lambda y.xy$
Is there any difference in meaning or the way you apply beta reduction, or are those just two ways to express the same th...
In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ?
This is the case when one use for instance van Emde Boas trees instead of more conventional binary search tree implementations.
But for example, if we tak...
We all know that Markov Chains can be used for generating real-looking text (or real-sounding music). I've also heard that Markov Chains has some applications in the image processing, is that true? What are some other uses of MCs in CS?
I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing the set of strings $S$.
Add-Prefix-Set on $\mathcal{D}(S)$: given some set $T$ of (possibly empty...
I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave like a stack, it'd seem that we can actually claim that TMs are more powerful.
Is this true?
Many intractable problems can be modeled as deciding whether a set of triples satisfy some no-trivial property. For example, 3-edge coloring of cubic graphs can be modeled as the problem of deciding whether a set of triples satisfy that the elements in each triple must have different color.
I'm...
