texts: Proof of an Optimal substructure in Dynammic Programming?

texts:
Could someone please explain how exactly the proof of optimal substructure property in dynamic programming problems works?

They usually say:

  Let's say the global optimal solution is A, and B is part of the solution. So B must the optimal solution of the subproblem, because if it weren't, then A wouldn't be the global optimal.

It makes some  sense to me, but I think this would work with any non-dynamic problem (the property), or maybe it is because I still don't get how it works.

Can someone please help? How does the contradiction work?


texts: Pick matrices such that each partial sum is positive

texts:
There is a sequence of $n$ sets, each set contains a constant number of constant-size vectors, e.g:

$\{M_{1,1},M_{1,2},M_{1,3},M_{1,4}\}$
$\{M_{2,1},M_{2,2},M_{2,3},M_{2,4}\}$
...
$\{M_{n,1},M_{n,2},M_{n,3},M_{n,4}\}$

The task is to pick, from each set, a single vector, such that the sum of vectors and all the partial sums have no negative elements, i.e, select $i1,i2,...,in$ such that the following vectors:

$M_{1,i1}$,
$M_{1,i1} + M_{2,i2}$,
$M_{1,i1} + M_{2,i2} + M_{3,i3}$,
...

have only non-negative elements.

Is anything known about this problem?


texts: Why doesn't Godel's Second Incompleteness Theorem rule out a formalizable proof of P!=NP?

texts:
I'm sure there must be something wrong with the following reasoning because otherwise a lot of P vs. NP research would be curtailed but I cannot determine my error:

For any fixed integer $k>0$ define $$B_k := \{ \langle \varphi \rangle | \; \varphi \; \text{is a wff of ZF and has a proof of length} \; \leq k{|\varphi|}^k \; \}$$

Now for all $k$, the language $B_k$ is in NP since a valid proof for $\varphi$ of length $\leq k{|\varphi|}^k$ can be a NP-witness verified by an automated proof-checker in polynomial time.  Furthermore, for sufficiently large enough $k$, $B_k$ is NP-complete since SAT reduces to it: that is, for an instance $\phi$ of SAT make a corresponding wff of ZF $\varphi$ using existential quantifiers. Then a satisfying truth assignment of $\phi$ can be made into a formal proof of $\varphi$ of length polynomial in $|\varphi|$ since a truth assignment of $\phi$ is linear in $|\phi|$.

Now, if ZF is inconsistent, this means that there is a formal statement $\sigma$ such that both $\sigma$ and $\neg \sigma$ have proofs in ZF.  As is well known, any other statement $\tau$ can then be derived from the contradictory conjunction $\langle \sigma \wedge \neg \sigma \rangle$ (that is by following the path: $$\langle \sigma \wedge \neg \sigma \rangle \implies \text{both} \; \sigma \; \text{and} \; \neg \sigma \; \text{are true} \implies \langle \neg \tau \rightarrow \sigma \rangle \; \text{is true (since regardless of} \; \tau
\; \text{the implication is valid since} \; \sigma \; \text{is true)} \implies \langle \neg \sigma \rightarrow \tau \rangle \; \text{(by contraposition and double negation)} \implies \tau \; \text{ is true (by modus ponens with} \; \neg \sigma \, )$$

). Thus if ZF is inconsistent, then every statement $\varphi$ has a proof polynomial (it seems to me even just linear) in $|\varphi|$.

Let $B:=B_k$ for a sufficiently large $k$ a referred to above to allow for $B$ to be NP-complete.  Then if ZF is inconsistent, there are only finitely many $\varphi$ such that $\langle \varphi \rangle \notin B$ because the high-degree polynomial proof length allowance of $B$ is enough to cover the guaranteed short proofs of wffs of sufficient length.  This implies that $B$ is decidable in polynomial time which by its NP-completeness implies that P=NP. If we rephrase this chain of reasoning in terms of contrapositives, if P!=NP then ZF is not inconsistent (that is it is consistent).

Therefore If we have a formal proof of P!=NP then we have a formal proof of the consistency of ZF.  But by Godel's Second Incompleteness theorem, this implies that ZF is inconsistent which in turn get P=NP as outlined above (as well as the theoremhood of any negated theorem).

This is not exactly a proof that P vs. NP is independent of ZF.  It could be that ZF is consistent and that P=NP or that P!=NP can be proven through techniques not formalizable within ZF.  However, it does present another formidable barrier to resolving P vs. NP.


texts: Search on Conformant Problem: solution for subset of a belief state

texts:
I am having trouble understanding the following statement.

I have understood why in a sensorless/conformant problem, if there exists a solution (a sequence of actions) for a belief state $b$, then it is also a solution for any $b'$ that is a subset $b$.

Next claim is what is confusing me.

Then in a standard graph search, we can save time by pruning some branches from the search tree.

Example from the Sensorless Vacuum World problem in Russel Norvig.

When we have a successor $\{1,3,5,7\}$ generated during graph search, we do not add it to the frontier if we have already expanded the belief state $\{5, 7\}$ which is a subset.

I thought those cases are totally unrelated since each belief state may encode a different path from the start state. If $\{5, 7\}$ does give us a solution, we have no guarantee it will work for $\{1, 3, 5, 7\}$. It's also possible $\{1, 3, 5, 7\}$ can lead to a solution through a different path.

I must be missing something.. can someone please explain?


texts: Is k-means parallelizable (other than the data parallelism of the distance function computation)

texts:
The k-means algorithm is known to be NP-hard.

While the distance function computation in the algorithm loop is data parallel, the algorithm is iterative and may become exponential in the number of iterations.

Is there a way to parallelize in practice k-means so as to alleviate (even in a small way) the hardness of k-means?


texts: Space complexity analysis of binary recursive sum algorithm

texts:
I was reading page 147 of Goodrich and Tamassia, Data Structures and Algorithms in Java, 3rd Ed. (Google books).
It gives example of linear sum algorithm which uses linear recursion to calculate sum of all elements of the array:

Algorithm linearSum (arr , n)
    if (n == 1)
        return arr[0]
    else
        return linearSum (arr , n-1) + arr[n-1]
end linearSum

And the binary sum algorithm which uses binary recursion to calculate sum of all elements of the array:

Algorithm binarySum (arr, i, n)
    if (n == 1)
        return arr[i]
    return binarySum (arr, i, ⌈n/2⌉) + binarySum (arr, i+⌈n/2⌉, ⌊n/2⌋)
end binarySum

It further says:

  The value of parameter $n$ is halved at each recursive call binarySum(). Thus, the
  depth of the recursion, that is, the maximum number of method
  instances that are active at the same time, is $1 + \log_2 n$. Thus the
  algorithm binarySum() uses $O(\log n)$ additional space. This is big
  improvement over $O(n)$ needed by the linearSum() algorithm.

I did not understood how the maximum number of method instances that are active at the same time, is $1 + \log_2n$.

For example consider the below calls to method with method parameters given in rounded box:

Then in two recursive calls of second row from top, $n = 8$. So, $1 + \log_2 8 = 4$. Now I dont get what maximum limit this 4 represent?


texts: Proving that a language satisfies the pumping lemma condition

texts:
I have to proof that $L = \{ a^{2i} b^{2j} \mid i,j \in \mathbb{N} \}$ is a regular language, and how it meets the Pumping Lemma condition.

For the PL, there is a string $xyz \in L$ such that $y \neq \epsilon$ and any string $xy^nz$, for any $n \ge 0$, is in $L$.

From what I understand, I cannot use the pumping lemma to prove that a language is regular.

I am a bit puzzled how I have to show that this $L$ meets this condition.
Do I have to divide a string into $xyz$ again?


texts:
Let the function cane and its auxiliary helping function down be the smallest functions satisfying the following requirement. For every x∈ℕ, for every y∈ℕ, and for p=(x,y), all of the following statements hold:

down(x+1,y)=(x,y+1)

down(0,y+1)=(y,0)

cane(p)= 0 if down(p) is undefined

cane(p)=1+cane(down(p)) if both down(p) and cane(down(p)) are defined.

(NOTE: p above is a pair.)

For every x ∈ ℕ and y ∈ ℕ such that x+y ≤ 2 (there are six such pairs), calculate the value, if there is one, of down(x,y) and also of cane(x,y). Put your answers in two tables, one for down and one for cane, of this form:

Hint: It might help you for the later parts of this question if you he k these two functions with more values for x and y.

Describe in words how the function cane and its auxiliary helping function down work, and what they accomplish. Explain any wider significance ane these functions might have. My question is how am I supposed to fill in this table;

for example, if I take in x to be 0 and y to be 0 then my down function would be as follows;

down(0+1,0)=(0,0+1)==(1,0)=(0,1) and down(0,0+1)=(0,0)==(0,1)=(0,0) I believe then that when x=0 and y=0 then the position in the table is "undefined" and true for all other coordinates of the table because they form a trail back to (0,0).

Could someone please help me understand this?


texts: Reduction of graph chromatic number to hypergraph 2-colorability

texts:
I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this paper, the author tries to reduce graph chromatic number to hypergraph 2-colorability (same as set splitting).

You can find the paper here: http://web.cs.elte.hu/~lovasz/old-papers.html

I'm reproducing the reduction below.

Let $G$ be a graph, $V(G) = \{x_1,\dots,x_n\}$. Let $G_i$ be an isomorphic copy of $G$, $(i=1,\dots,k)$, $V(G_i) = \{x_{i,1},\dots,x_{i,n}\}$ ($x_{i,v}$ is a point corresponding to $x_v$). Take a new point $y$ and let $f_v = \{x_{1,v},\dots,x_{k,v},y\}$. Define hypergraph $H$ by
$$
  H = E(G_1) \cup \dots \cup E(G_k) \cup \{f_1,\dots,f_n\}.
$$
Then $H$ is 2-colorable if and only if $G$ is $k$-colorable. I don't understand this conclusion and the only example I've been able to come up with where this is true is $k = 1$.


texts:
Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the vertices of $P$ visible from point $p$. A point $q$ is visible from point $p$, if the line segment $\overline{qp}$ is completely in the polygon $P$.

One can use the accepted answer here to compute visible vertices in $P$ from a point $p$ in $\mathcal{O}(n\log{}n)$.

My question is, does an algorithm exist to do it in $\mathcal{O}(n)$ time?


texts: Confusion with "every path from a given node to any of the leaves goes through the same number of black nodes" property of RB trees

texts:
One of the properties of Red Black trees is: "every path from a given node/vertex to any of the leaves goes through the same number of black nodes"

Two related questions about this property:

1) is the vertex we start at counted in this black vertex count?

2) is the leaf we end at counted in the black vertex count?

I have a secret theory about both of these questions, but am hoping for confirmation and so shalt not yet reveal it.


texts:
Are all pseudo-random number generators ultimately periodic? Or are they periodic at all in the end?

By periodic I mean that, like rational numbers, they in the end generate a periodic subsequence...

And pseudo-random means algorithmic/mathematical generation of random numbers...


texts:
Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ and then perform the modular reduction mod $q$.

For example, with $p = 5$ and $q=3$, we have:

$$0 \mapsto 0$$
$$1 \mapsto 1$$
$$2 \mapsto 2$$
$$3 \mapsto 0$$
$$4 \mapsto 1$$

NB. that this is not modular inversion or division.

Is there an efficient algorithm to compute $r_q (x)$ for $p, q$ fixed? Here $p, q$ are very big, like $\log_2 p\approx 128$ and $\log_2 q \approx 48$. I am particularly interested in the arithmetic circuit model, where we have the usual gates $+ : \mathbb{F}_p \times \mathbb{F}_p  \to \mathbb{F}_p$ and $\times : \mathbb{F}_p \times \mathbb{F}_p  \to \mathbb{F}_p$. But answers in other models are interesting.


texts:
I am seeking a fast algorithm to compute the following function, a quantile of the Poisson distribution:
$$f(n, \lambda) = e^{-\lambda} \sum_{k=0}^{n} \frac{\lambda^k}{k!} $$

I can think of an algorithm in $O(n)$, but considering the structure of the series, there is probably a $O(1)$ solution (or at least a good $O(1)$ approximation). Any take?


texts: How do proof assistants nowadays avoid floatpoint error?

texts:
I heard that Coq is using "Dedekind cut", but how's that related to floatpoint errors?

Can we just use something like

data Q : Type where
  div : N -> N -> Bool -> Q

To replace all usages of floatpoint numbers?


texts:
I read in the introduction of this paper

http://www.scottaaronson.com/papers/uncompute.pdf

that there is a problem $B$ such that $BQP^B \not\subset P^{NP^B}$, and that $B$ is in $BPP$. But, using the fact that $BPP$ is in $BQP$ and that $BQP$ is low for itself (i.e. $BQP^{BQP}=BQP$), as proved in

http://arxiv.org/pdf/quant-ph/9701001v1.pdf

can we state that $BQP^B \subseteq BQP^{BPP} \subseteq BQP^{BQP} = BQP$ and thus $BQP \not\subset P^{NP^B}$ and finally $BQP \not\subset P^{NP}$?


texts: How fast can all nth roots of an integer be computed?

texts: I mean that for every $i$ from 2 to $\lceil \log_2n\rceil$ I want to know $\lfloor \sqrt[i]{n}\rfloor$. Could this be done faster than computing the roots one by one?


texts: Possible error in Computer Networks, V Edition by Tanenbaum & Wetherall

texts:
Under section 5.4 Quality of Service on page 404:

Multimedia applications in particular, often need a minimum throughput and maximum latency to work.

Isn't this statement incorrect? Shouldn't it be :
Multimedia applications in particular, often need a maximum throughput and minimum latency to work.


texts: Closure of regular languages to shuffle using closure operations

texts:
Given a language:
$L = \{\; a_1b_1a_2b_2a_3b_3\dots a_nb_n \mid \forall i: a_i,b_i \in \Sigma,  a_1\dots a_n \in L_1\ ,  b_1\dots b_n \in L_2 \;\}$

Also $L_1, L_2$ are regular languages.

Using closure only (homomorphism) prove that L is also regular language.

I think there can be a mapping $h\colon (L_1 \cup L_2) \to \Sigma$, then use $h^{-1}(\Sigma)$  in order to show regularity. I'm a bit stuck over here.


texts: Length of longest arithmetic progression in an array

texts:
I was reading an article on Longest Arithmetic Progression. The solution given has S(n)=$O(n^2)$. Can't I solve it in $O(1)$ space? To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). When we found them we still keep on decreasing left and right to find llap (length of longest arithmetic progression). The other cases left are those where llap is even.. for them I will select i and (i+1)$^{th}$ element as my center two elements of AP and find elements on their right and left satisfying ap. T(n) will still be $O(n^2)$.

Is my approach correct?


texts:
In trying to design an algorithm, I needed a datastructure to implement a restricted kind of set partition refinement, where the sets $X$ to split on are subtrees. Specifically, given an arbitrary tree $T$ (computed earlier in the algorithm), and an initial partition where everything is in the same set, I need to do two things efficiently:

Refine the partition by splitting nodes in some subtree $T'$ of $T$ from the rest of the nodes.
Given a node $n$ in the tree, figure out the farthest (closest to the root) ancestor in its subset $S_n$.

The algorithm may have to do both up on (close to) every node on the tree, in any order. There's an obvious algorithm, similar to the one described on Wikipedia, where each node stores a pointer to the farthest ancestor in its set, and then when given a subtree $T'$ to split, we walk through every node in $T'$, and update the pointer to the root $r$ of $T'$ if it's an ancestor of $r$. The problem with this implementation is that since splitting can take up to $O(n)$ time (where $n$ is the size of the tree) to update all the pointers, the whole thing would be $O(n^2)$. Another implementation would be store, for each node, whether it's been split with its parent node. This makes splitting $O(1)$, since we just have to set the flag for the root node, but now finding the ancestor is $O(n)$ (we have to walk up the tree) so the whole thing is still $O(n^2)$. Is there a way to make this faster than $O(n^2)$ by taking advantage of the structure of the problem?


texts: Does a DFA on {0,1} accept any string whose length is composite/prime?

texts:
My attempt is this:
 This is similar to proving whether a language {w^p|p is prime} is regular or not.(For the prime case)
Suppose on the contrary that this language L is regular. Let p be its pumping length and t be a prime greater than p. (Note that t exists since the number of primes is inﬁnite.) Then, wt ∈ L, and by the pumping lemma, we can write wt as wt = xyz for some x,y,z, such that |y|> 0, |xy|≤p, and for each i≥0, xy^iz ∈L. By setting i = t + 1, the pumping lemma implies that xy^(t+1)z is in L. On the other hand, xy^(t+1)z = w^(t+t|y|), which implies that xy^(t+1)z does not belong to  L, as t + t|y| = t(1 +|y|) is not a prime.Thus, a contradiction occurs, so that L is not regular. Hence we can say that the DFA may not accept any string of length prime.      Please tell me where i am wrong.


texts: Tree structure that is like a quadtree/octree but splits a different number of times in each dimension?

texts: I'm looking for a data structure that is like a quadtree where each level is a subdivision of the previous. However, unlike a quadtree I need the subdivision to occur a different number of times in the horizontal direction to the vertical direction. In a quadtree the space is subdivided once in each dimension (resulting in four children per node). In the tree I'm looking for the space may be divided a given number of times in one dimension and a different number of times in the other. Say for example, twice in the X and once in the Y (resulting in six children per node). Has such a space partitioning tree been given a name? Can anyone point me to an existing data structure that fulfills this requirement? Thanks!


texts: Why is the processes address space a continuous block in RAM?

texts:
I need some clarification regarding how the process address space is organized in memory. I went through basic concepts of virtual memory and adress translation and according to the size of the page, it seems that a virtual adress can have its equivalent physical address located anywhere in RAM, it that right ?

I saw the following representation of RAM :

It seems that processes address space is continuous in RAM, how come ? I though that we could have, for example, the stack of a process(or some part of it) located at a totally different region of RAM than, for example, the heap.


texts: Mathematical limits on lossless data compression

texts:
Let's say Bob wants to send a particular binary sequence to Alice. Imagine that Bob and Alice both have powerful machines but slow Internet connections. Bob could just send the sequence directly but the upload and the download would take a lot of time. Instead Bob could send a program that outputs the sequence. Assume Bob and Alice have agreed on the programming language they will use beforehand (be it C++ or Iota).
Two natural questions are what is the smallest possible size of the source file and how to find a program attaining the lower bound for a given sequence (e.g. can it be done algorithmically for any sequence or at least for some sequences). Have these questions been studied?


texts: Show that every infinite language has a non-regular subset

texts:
I'm trying to solve this problem:

  Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular

But can this be correct? If I have the language $\{a\}^*$ for example, that's infinite but you can make a DFA for any sub-language of it, right?

There's a hint that this can be proved using diagonalization, but I think I must be misunderstanding the question.


texts: When can one use a $O(n)$ time sorting algorithm?

texts:
Some sorting algorithms like counting sort/insertion sort can work in $O(n)$ time while other algorithms such as quicksort require $O(n \log n)$ time.

As I understand it, it's not always possible to use the $O(n)$ sorting algorithms. What are those cases when they can not be used?


texts: How many bits to represent a quantity $\omega$ bounded in a particular way?

texts:
I'm working out some details to implement a division algorithm, I'm following the explanation given in this book (chapter 5) for who is interested.

Anyway I need to work out how many bits are necessary to represent a value $\omega$ bounded by

$$
| \omega | \leq \rho r^{k+1} y
$$

where

$$
\begin{array}{l}
\frac{1}{2} < \rho \leq 1 \\
r = 2^l, \text{where $l\geq 1$ is some integer} \\
0 \leq y \leq 2^{k} - 1, \text{ $k$ positive integer}
\end{array}
$$

My approach is finding the number of bits to represent $| \omega |$ and then adding one bit to represent the sign of $\omega$, in two complement.

There fore

$$
\left\lceil \log_2(|\omega|) \right\rceil \leq \left\lceil \log_2(\rho r^{k+1} y) \right\rceil = \left\lceil \log_2(\rho) + (k+1)\log_2 r + \log_2(y) \right\rceil \leq \left\lceil (k+1)l  + \log_2(2^k-1))\right\rceil \leq \left\lceil (k+1)l  + k \right\rceil = \left\lceil (k+1)(l+1) - 1 \right\rceil = (k+1)(l+1) - 1
$$

Therefore in two complement I would need a total of $(k+1)(l+1)$ bits to represent my value $\omega$.

Is this correct?


texts:
The given description of language is:

  $\Sigma=\{a,b\}$ and $L=\{a^nwa^n:n\geq 1,w\in\Sigma^*\}$

I felt its regular as we can always interpret $aabaa$ in string $aaabaaa$ as $w$. That is we can always interpret $a^n(a+b)^*a^n$ as $a(a+b)^*a$. So isnt it correct to call this language regular. The book calls it not regular without any explanation. So I was just confused, what is correct.


texts: How to get all tree-like refutations of a formula

texts:
I need to extract all tree-like refutations of this formula

$$(a+b)(a+ b')(a'+c)(a'+c')\,.$$

I get understand this one

but how do I get the other ones?


texts: Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?

texts:
I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up).

Why does this algorithm have a time complexity of $\Omega(2^{\frac{n}{2}})$? Where does the exponent come from?


texts: Compact representation of paths in a graph

texts:
I've a subset of the simple paths in a graph. The length of the paths is bounded by $d$.

What's the most compact way (memory-wise) I can represent the paths such that no other paths apart from the selected ones are represented?

Note that I want to use this representation in an algorithm that will iterate through this subset of paths over and over again and that I want to be fairly fast, so for instance, I can't use any standard compression algorithms.

One representation that came to my mind was representing them as a set of trees. I'm guessing though that getting it down to an optimal number of trees is NP-hard? What other representations would be good?


texts: How to show all possible implied parenthesis?

texts:
Can I use recursion to find out the possible parenthesis we can add to this expression: 2*3-4*5 ?

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

I am not able to find out the right states for the recursion to proceed. As at any point we wouldn't know if it would have two open parenthesis or two closed parenthesis. I am just looking for ideas.


texts: How to prove that a language is context-free?

texts:
There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?

What techniques are there to prove this?  Obviously, one way is to exhibit a context-free grammar for the language.  Are there any systematic techniques to find a context-free grammar for a given language?

For regular languages, there are systematic ways to derive a regular grammar / finite-state automaton: for instance, the Myhill-Nerode theorem provides one way.  Is there any corresponding technique for context-free languages?

My motivation here is to (hopefully) build up a reference question that contains a list of techniques that are often helpful, when trying to prove that a given language is context-free.  Since we have many questions here that are special cases of this, it would be nice if we could document the general approach or general techniques that one can use when facing this sort of problem.


texts:
I was reading Data Communication book by Forouzan in which there is a one restriction put on CIDR subnetting by Internet authorities:

  First IP address in the block should be evenly divisible by the number of addresses. For example, below, the first address, when converted to a decimal number, is 3440387360, which when divided by 16 (block size) results in 215024210.

Since this did not clear the practical significance behind this restriction I went on exploring and came across the video where it is explained as follows:

  Whenever we divide any number by $k^{th}$ power of 2 (another restriction being that the block size should be $2^k$), the reminder is least significant k bits. So evenly divisible by $2^k$ means that least significant $k$ bits should all be 0. This way the first address of the allocated address block can be used as a block ID since it has all 0s in the host ID part.

Now that seems more logical despite the fact that I dont understand how

evenly divisible by the number of addresses $2^k$

translates to

least significant $k$ bits should all be 0

Can't it be just that the decimal equivalent of least significant $k$ bits should be divisible by 2. I mean if least significant 4 bits (for a block of $2^4$ addresses) is $(1010)_2$, then it translates to $(10)_{10}$ which is divisible by 2.

So in short why is evenly divisible translates to all 0 LSBs?


texts:
I'm trying to come up with an algorithm for optimizing cutting a rod. Most of the examples I see online are for a stock of rod of a single length and optimizing the way to cut it up for max price.

I need something where the user enters length cuts they want (e.g. 2 of 1" length, 5 of 6" length, 10 of 8" length) and then they can choose to have this optimized for multiple stock rod lengths where they can choose which stock lengths they want to use, either 1 or multiple lengths, (e.g 8' stock, 10' stock, 12' stock).

I don't have a computer science background, so am not as familiar with algorithms and whatnot. From looking around I've seen Greedy Algorithm recommended, but was a little confused, because most examples were more simple.

I can logically come up with some really poor optimization starategy like 1.) see if any stock lengths are completely divisible by any of the desired cut lengths and do those first 2.) see if any stock lengths are completely divisible by any combination of desired cut lengths and do those next 3.) from there just kind of pick a pattern and stick to it like use up the smallest cuts first and largest last.

Possibly after doing a problem like this, I may need to move on to optimizing rectangular cut areas from a piece of plywood, but I can't even figure this out yet. Any help to point me in the right direction would be appreciated. I am a mobile app developer, so I'm trying to code this for a carpentry app.

Thanks!


texts: Design the regular expression and DFA that accepts a language in which "110" is no less than "011"

texts:
The question is to design a DFA that accepts a language in which the count of  substring "$110$" is no less than the count of substring "$011$". For example, $110$, "0101", "0111101110" is good but "011011" is bad.

The restriction of the language equivalently means whenever a "011" is encountered, only this pattern "$0111^*0$" is allowed, so that a "$011$" is matched with a "$110$". There is no other restriction.

I tried to give a regular expression as $(1^*0111^*0)^* + 1^*0^*$, but I tried very hard but failed to convert this to a DFA. Is there a systematic way to convert such a regular expression to a DFA?


texts: How not to prove that P ≠ NP implies NP ≠ PSPACE

texts:
Let's define the two variants of the Travelling salesman problem:

$TSP_{opt}$ : Give me the shortest tour

$TSP_{dec}$ : Is there a tour of $l$ or shorter (Yes/No)

Now assume $P \neq NP$:

Since $TSP_{dec}$ is NP-complete, there is no polynomial time algorithm to solve it. Now given a solution to
$TSP_{opt}$ with optimal objective $l_{opt}$.

Any algorithm that can verify that this optimal solution is indeed optimal, would also answer the question is there a tour of length $l_{opt}-1$ ($#1$) or shorter. But this question is basically $TSP_{dec}$ and from the assumption $P \neq NP$ cannot be solved in polynomial time. So $TSP_{opt}$ is not in $NP$.

$#1$: for the sake of simplicity assume that the TSP only contains integer values as arc length, so the objective can only take integer values.

It was pointed out to me, that this proof has a flaw, which is not obvious to me. Where is it and from what false assumption it is coming from, so it might help people who have the same false assumption.


texts: The purpose of grey node in graph depth-first search

texts: In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (discovered and all its neighbours was visited). What is the purpose of this distinction? It seems that DFS algorithm will never visit a visited vertex regardless of whether it's grey or black.


texts: Categorizing sport events and competitors

texts:
Let's say we have a sport, where many competitions are organized throughout the year. In these events, a set of people compete, although not every person competes in every event.

I would like to categorize these people, and the events, in such a way that people in category $A$ performed well in the events of category $A$ etc. This also means that people in category $A$ usually perform well at the same events. There would then be a one-to-one correspondence between event categories and people categories.

It would also be OK for me if every event and every person is not uniquely put into one category, but is given a weight $w_A$ representing how much it fits into category $A$

The data I have are the results from all the events.

What do you think would be a good algorithm to categorize both events and people at the same time (since they are related)? I have been reading up on different machine learning algorithms, but would love some input on what to focus on.


texts: How can we solve halting problem efficiently?

texts:
I was doing exercises regarding the halting problem and there is this question where I am stuck
Ques: it goes like suppose if you can decide the halting problem with a query "Is <tm,s> belongs to HALT?" (tm = turning machine and s = string) so it can solve i number of instances <tm1,s1> <tm2,s2> <tm(i),s3(i)> now it says show how can we solve 3 instances with 2 queries only?
I am not sure how to start thinking about this one.. like should we have to simulate one instance with another one? Can anyone provide a proof?


texts: How do cycles of non-consuming transitions in NFAs influence their halting properties?

texts:
I am in a class that is going over NFAs. The way they are described is a set of states, one of which is the start state, zero or more are accept states, and one or more transitions between them, which consume a symbol of the language or a lambda transition which does not consume a symbol from the string.

One thing that was mentioned is that languages defined by NFAs are regular, and thus can be parsed in constant time (since strings are finite). We then went through the basic pathfinding sort of algorithm where we try paths until we find one that consumes the entire string and if one path completely consumes the string and ends in an accept state - hurray.

Now, if there is a non-consuming transition from one state to itself, or another non-consuming loop in the NFA, that algorithm wouldn't halt.

Are those sorts of loops explicitly forbidden? Is halting not a required property of NFAs? Where is the disconnect in my understanding?


texts: Best data structure for a queue with random reads?

texts:
Well, it's not exactly a queue if it allows for random reads. This question is about a data structure which behaves like a queue for insertions and a sorted dictionary for reads.

Imagine an algorithm that maintains a list of elements so that:

It reads an element from the list based on its key.
It then inserts that element as the last element in the list.
On demand it returns all entities in the order in which they were inserted.

And I am looking for a solution that is faster than a naive implementation based on a linked list, which would have complexity O(n) for all three parameters - search, insert as the last element, and return all elements in the inserted order.

Such a data structure should probably:

Allow for a quick lookup of the key (e.g. a tree, a hashmap)
Maintain the order in which elements were inserted (e.g. a list, a queue)

A practical example is a list of agents receiving calls. When an agent is called, it's fetched from the list, and when it finishes the call, it's put at the back of the list. Therefore the agent that is first in that list is the most idle agent (waiting for a call the longest). In other words, the list would be sorted according to agent's idleness.

Another example implementation could be based on two structures, one dictionary and one array, referencing each other. The dictionary would keep the index in the array as the value and the array would keep the key as the value. Then the element would be removed from the array by looking up the value/index in the dictionary and the dictionary would be updated with the new index once the element was put as the last element in the array.


texts: How should I choose the neighborhood structure for simulated annealing for my problem?

texts:
There are $n$ students and $m$ courses. Each student $i$ wants to attend a subset $C_i \subseteq \{1,\ldots,m\}$ of the courses. There are $k$ time slots on a weekly schedule. The goal is to select a time slot for each course such that the students can attend as many courses as possible, that is, find a mapping $f: \{1,\ldots,m\} \rightarrow \{1,\ldots,k\}$ such that the following objective function is maximized:

$$\sum_{i = 1}^n \big| \bigcup_{j \in C_i} \{f(j)\} \big| $$

For my (artificial) instance $n = 10^5, m = 5000, k = 25$, and any student wants to attend at most 16 courses. I have tried a hill climbing algorithm which moves in the search space by changing one course at a time in the mapping $f$ if it improves the objective function, until it can improve no more. This gives a local maximum, but I'd like to do better. I've tried to implement a simulated annealing approach with the same neighbourhood structure, but I haven't been able to tune the parameters to beat the hill climbing algorithm.

I've read that the number of moves from any part of the search space to another part should be small. In my solution I need at most $5000$ moves, is this too much? If make bigger changes into the mapping, the evaluation of the cost function becomes expensive, as I have to recompute the objective function for every student affected by the change. What kind of a neighbourhood structure would suit this problem the best?


texts: Problems conjectured but not proven to be easy

texts: We have many problems, like factorization, that are strongly conjectured, but not proven, to be outside P. Are there any questions with the opposite property, namely, that they are strongly conjectured but not proven to be inside P?


texts:
I need to find the fastest route passing in all vertices

Each vertex is a class.
I can choose the number of classes for semester.
Some classes have prerequisites (A and B need to be done one semester before C), so I can't do A, B and C at the same time.
Some classes (C in this case) have only in the second semester of the year (a year has only 2 semester).

So let's say that I study 2 classes each semester

Worst case possible:

First semester of year 1:

Study A and D

Second semester of year 1:

Study B (C can't be done because A and B is a prerequisite)

First semester of year 2:

nothing (C can only be done in the second semester)

Second semester of year 2:

Study C

The optimal answer would be:

First semester of year 1:

Study A and B

Second semester of year 1:

Study C and D

I know the basics of the most common graph algorithm like Kruskall, Prim, DFS... but I just don't know how I could apply them to my problem, the first think that I thought was use Dijkstra algorithm to pass in all vertices but how I would take in count that C can only be done at certain semesters? maybe I should use different algorithms at the same time?

This is not an exercise, it's a real problem that exists at my college, and I would like to solve using a smarter solution using an algorithm rather than a hard coded implementation. Anything that helps me to guide to the right direction will be well appreciated.


texts:
I posted this question on mathoverflow two years ago but got no answer:

Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$

Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-i} } $ be the corresponding binary number constructed
from the word.
Let $k=  \left \lfloor \frac{n!}{2^n} \right \rfloor \cdot (m+1)$ , then $ 1 \le k \le n! $.

Compute the Lehmer-Permutation $\pi_k$ from $k$ on $n$ numbers.
(
https://en.wikipedia.org/wiki/Lehmer_code
)

Set $ x := \pi_k \cdot w = a_{\pi_k(0)} \cdot a_{\pi_k(1)} \cdots a_{\pi_k(n-1)} $

Then $f(w) := x$.

So the function permutes the digits in the word $w$ and the permutation is determined by $w$.

Suppose you randomly choose uniformly a word from $\{0,1\}^{1000}$ and then you apply the function. Is it practically possible to invert the constructed word?
That is, does somebody have an idea on how to invert the word?

More details may be found on:

http://orgesleka.blogspot.de/2015/09/candidate-one-way-function.html

This picture shows all words of length 7 when f is applied on those words:


texts: Why is this language a regular language?

texts:
Came across this in a book, and I'm wondering why the following language is regular?

$$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$

Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a regular language because it can be expressed by a regular expression $$a*$$, and $$ \{ww^R: w \in \{a,b\}^3\} $$ is a regular language because it is finite; therefore the union of the two regular languages makes a regular language?


texts: Is there a data-structure for semilattices similar to a tree data-structure?

texts:
If we regard a tree as a partial ordered set, it becomes a special case of a join-semilattice. For a join-semilattice, we want to be able to compute the (unique) least upper bound of two elements (more or less) efficiently. In the case of a tree, a data structure which would enable this would be to store for each element in the corresponding node a pointer to the parent and a distance measure to the root. (Actually, a labeling based on topological sort usually used for "a distance measure to the root", effectively all that is needed is a compatible partial order which can be evaluated efficiently).

Each finite join-semilattice can be represented as a set of subsets of a finite set with containment as order such that the least upper bound is given by the union of the sets. Hence, representing each element by a finite number of tags, and computing the least upper bound by the union of the corresponding tags would be one possible data structure. (By looking at the complement, one sees that defining the least upper bound as the intersection of the corresponding tags would also be possible.) A much more common data-structure is to simply use a matrix to store all results of "a <= b" or even all results of "join(a,b)".

However, using such a data-structure to represent a tree would be sort of strange. Are there more tree-like data-structures for join-semilattices, which still allow (more or less) efficient computation of the (unique) least upper bound of two elements? (Perhaps some sort of directed acyclic graph with additional information in the nodes similar to the distance measure to the root for the tree?)


texts:
I know that P is a subset of NP, but I'm not sure what this tells me about P as it relates to coNP?
I feel like this is how I should go about proving it, but I'm not sure how. Otherwise, I could find a language that is in both NP and coNP, but I'm not sure how to prove any examples of that.

I know that I can prove L and L complement both exists in P and therefore NP, but I don't know how to relate this to coNP.


texts: Is (a+b)* and (ab)* same in finite automata?

texts:
Regular language of (a+b)* and (ab)* are:
(a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...}
(ab)* =   { ε, a, b, aa, ab, ba, bb, aaa, ... }

I am new to Finite automata and this simple notion is confusing me!
I didn't find (a+b)* = (ab)* in rules of regular expressions.


texts: Turing machine with a finite tape after the input word ends

texts: How can I prove that for a natural number K, a language that accepted by a Turing machine with K cells after the input word ends, belongs to R (which R is the set of languages that there is Turing machine that accept them while for each input the run is finite)?


texts: Algorithm / data structure to filter documents by number of missing words

texts:
Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)?

Problem Definition

We have a list of documents $D = \{d_1, d_2, \dots, d_n\}$. Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\text{words}(d_1) = \{w_1, w_5, w_{7}\}$.

Each person $p_j$ also has a set of words $\text{words}(p_j)$.

The goal is to find all documents where the length of the set difference between both is smaller than a threshold $t$:

$$
|\text{words}(d_i) \setminus \text{words}(p_j)| < t
$$

$\text{words}(p_j)$ will in most of the cases be much larger than $\text{words}(d_i)$ (i.e. there will be a lot of words in the person's set that are not in the document's set).

Complexity

The sizes will probably be around these numbers:

documents: millions or tens of millions of documents
words: around 100k different words (per independent set)
person: between 1 and 1000 people

Use Cases

My actual use case for this is to retrieve foreign language texts where I do not know all the vocabulary, yet. I have a list of words that I know for each language and I want to find documents from a collection of texts that contain between 1 and 10 words that I do not know, yet. That way, I expect to be able to find texts that I can understand while also improving my vocabulary skills.

Another use case might be finding recipes that match a user's stock at home. In this case, you might want to find documents (recipes) that contain between 0 and 2 missing items, so that the user either has to buy nothing or can replace the few missing items with something similar.

My current approach

While it is easy to find documents that have an overlap of at least $t$ words, I found the opposite (find documents that have a difference of at most $t$ words) quite complex. At the moment I fell back to a two stage approach:

I first filter documents by the length of the text and the length of the sentences and compare them to an average value I store for myself
In the filtered list I then loop in my code and calculate the set difference for each document and delete all that have more than $t$ unknown words.


texts: How to make an anytime version of alpha beta pruning?

texts:
I wish to use alpha beta pruning in a problem with following constraints:

Terminal nodes are likely too distant to be found in most searches
Instead I want to maximize an evaluation function
There is a fixed time limit per search (say 1 second)
Moves are made on a "WeGo" basis ie. we both move simultaneously (I still model this as a tree of my move then their move, but the game state is only updated every second level)

Hence I need an anytime version for alpha beta pruning which relies solely on an evaluation function.

I thought one way would be to iteratively deepen the alpha beta pruning search while keeping track of the frontier eg something like:

while (within time limit):

   frontier = alpha_beta_search(max_ply_depth, frontier)
   increment max_ply_depth

return (best node on frontier)

The frontier contains nodes in the last depth level which have not been pruned by alpha-beta. It's likely the time limit would be reached before an entire depth level is explored in which case the frontier would still contain some nodes from the earlier level.

Would this work or is there another way of implementing anytime alpha-beta pruning with an evaluation function?


texts: Is computing a square root of a number and having more than 2 roots a reliable way to decide primality?

texts:
I was reading CLRS and it mentions that if $p$ is a prime of the form $4k+3$ and $a$ is a quadratic residue, then $a^{k+1}$ is a square root of $a$.  One can also easily show that $a^{-k}$ is a square root of $a$ as well.

Can we use this to get a primality test, for numbers $N$ of the form $N=4k+3$?

After reviewing Miller-Rabin (and after asking the related question Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function? ) and thinking about it a little more I thought of an algorithm that seems promising.  The intuition is that if $N=pq$ (or some other composite) there will be more than 2 square roots. Therefore, if we can find more than 2 square roots, we have evidence that $N$ is a composite.  With that idea, here is the algorithm:

PrimalityTest$(N)$: (where $N = 4k + 3$)

Choose $x \in \mathbb{Z}_N$ and compute $a = x^2 \pmod N$.
Compute $y = a^{(N+1)/4} \pmod N$.  (Notice that if $N$ is prime, this is just computing a square root of $a$.)
If $y^2 \equiv a \pmod N$ but $y \not \equiv \pm x \pmod N$ then there are more than 2 distinct square roots of $a$. Therefore, return "composite".
If $y^2 \not \equiv a \pmod N$ then return "composite".  (If $N$ were prime, then step 2 would have computed a valid square root of $a$, so by the contrapositive, if $y$ is not a valid square root, then $N$ is not prime.)
If $y^2 \equiv a \pmod N$ and $y \equiv \pm x \pmod N$ we have no idea what $N$ is. Therefore, go back to step 1 and choose a different $x$.  If this step happens too often, simply return "prime".

I believe this will succeed with probability 1/2, since it has half chance of choosing a "bad" square root that gives us no information. The only step I am not sure how to analyze probabilistically is step 4, but it seems that step 2 might do nonsense when $N$ is composite, it seems the probability that 4 catches is is quite high. I'd guess around $\frac{N-2}{N}$.


texts: Why we don't care about minimizing Push Down Automata & Turing Machines?

texts:
I never heard or read about the concepts of "Minimizing Push Down Automata or Turing Machines"?
why we are not concerned about minimizing them, in general?


texts: I'm ordering functions by their asymptotic growth for an assignment and I have verified I have the correct order by using limits, but I'm trying to understand why $n^{log\ log\ n}$ is between $n^3$ and $2^n$. It seems like it should be closer to the order of $n^n$. Can anyone provide some insight on this.


texts:
I am reading from "Discrete Mathematics and Its applications" by Kenneth H. Rosen, 7th edition. Consider the highlighted part in the following example taken from the same book:

  Question Use predicates and quantifiers to express the system specifications “Every mail message larger
  than one megabyte will be compressed” and “If a user is active, at least one network link will
  be available.”

  Solution: Let S(m, y) be “Mail message m is larger than y megabytes,” where the variable x has
  the domain of all mail messages and the variable y is a positive real number, and let C(m) denote
  “Mail message m will be compressed.” Then the specification “Every mail message larger than
  one megabyte will be compressed” can be represented as ∀m(S(m, 1) → C(m)).
  Remember the rules of
  precedence for quantifiers
  and logical connectives!
  Let A(u) represent “User u is active,” where the variable u has the domain of all users,
  let S(n, x) denote “Network link n is in state x,” where n has the domain of all network
  links and x has the domain of all possible states for a network link. Then the specification
  “If a user is active, at least one network link will be available” can be represented by

  ∃uA(u) → ∃nS(n, available).

"Existential quantifier" ∃u is used here, So I think, it should be ∃uA(u)∧ ∃nS(n, available) in place of ∃uA(u) → ∃nS(n, available).

Generally, we use 'implication' with 'universal quantifier' as shown in ∀m(S(m, 1) → C(m)).

Please correct me, if I am wrong.


texts:
[previously appearing in cstheory, it was closed there and introduced here instead]

Given an edge-weighted graph $G=(V,E)$ the problem of finding the shortest path is known to be in P ---and indeed a simple approach would be Dijkstra's algorithm which can solve this problem in $O(V^2)$. A similar problem is to find the maximum path in $G$ from a source node to a target node and this can be solved with Integer Programming so that, as far as I know, this is not known to be in P.

Now, the problem of finding a path in $G$ such that it deviates the minimum from a given target value (typically larger than the optimal distance but less than the maximum distance that separates the source and target nodes) has been conjectured to be in EXPTIME (see section "Conventions" of A depth-first approach to target-value search in the proceedings of SoCS 2009). In particular, this paper addresses this particular problem for  directed acyclic graphs (DAGs). A previous work is Heuristic Search for Target-Value Path Problem. There is event a US Patent of this algorithm US 2011/0004625.

I've been searching for related problems in other fields of Computer Science and Mathematics and strikingly, I have found none though this problem is clearly relevant in practice ---there are tons of opportunities to look for a specific target value instead of the minimum or the maximum path.

Do you know related problems to this or additional bibliographical references to this problem? Any information on this problem including studies of their complexity would be very welcome

Note: as already pointed out by Jeffe in cstheory, proving this problem to be in EXPTIME is trivial and the authors probably meant EXPTIME-complete.


texts: Is EXPTIME "solvable" or "checkable" in exponential time?

texts:
According to this video, EXP has problems that are exponentially difficult to check.

But according to this video, EXP are problems that are exponentially difficult to solve.

It would make sense to me, that if EXP contains problems that are exponentially difficult to check, that they would contain problems that are harder than NP-complete ones.

However, if it's true that EXP is problems that are just solvable in exponential time, why wouldn't they be equal? Wouldn't EXP therefore be a subset of NP (and so would R), as problems that are harder (like R) are still solvable in "non-deterministic" time? Because the term "non-deterministic" extends to any finite amount of time, correct?

Thank you in advance for resolving my confusion. If you could explain it as simply as possible, I would appreciate it, as I get easily bogged down by the set theory.


texts: Research on Tree Automata/Tree Transducers for implementing Tree Generators

texts:
I would like to write from scratch a tree pattern matching algorithm. Well actually, not just a matching algorithm, and not even a tree transducer, but a sort of tree constructor that takes basically a tree grammar ("tree pattern"), and an input tree instance like an XML tree, and constructs objects out of the instance tree (like constructing a JSON tree that differs significantly in structure from an original XML tree).
In the tree grammar/automaton, tree nodes are basically as described in that post: they can match sequences of zero/one or more (like regular expressions, but on trees), handle wildcards, and arbitrarily nested sequences/wildcards.
The question is, how can you apply the theory of tree automata (tree pattern recognizers) to constructing new trees from trees matching patterns? Can you work off of or build off of the idea of tree automata in this situation? If so, what must be added to allow for constructing trees that match the pattern, and where must it be added? If not, why not, must you write a hand-crafted algorithm for traversing the pattern tree and instance tree to construct the output tree in that case?
Basically wondering what research direction I should be looking into for inspiration, and if this is a solved problem. (Though, I would like to reinvent the wheel here, to learn how to implement it from scratch). In practice, I would like to handle errors gracefully (with helpful user messages) if trees are malformatted, for example. So the research shouldn't be too simplistic.


texts: What are Predictive Clustering Trees in machine learning?

texts:
Anybody could let me know what exactly the PDT is and where does it come from? it comes from predictive modeling or decision tress?

I read some articles and websites like: this and this
but both of them are about predictive modeling. I think PDT comes from decision tree rather than predictive modeling.


texts: Sort an array with a constant number of unsorted elements

texts:
I am trying to sort an array that I know to have a constant number of unsorted elements (elements that are not in their right place).
In the solution I looked at they say you can do this in $O(n)$ time:
you can find any unsorted element in $O(n)$ and then move it to the right place in $O(n)$ also. I am not seeing how you can do these things in $O(n)$.
I mean, I thought of an algorithm that iterates from 1 to $n$ ($n$ is length of the array), checks if the element at the index is in it's sorted place and if the answer is no then you can use partition for bringing it to the right place (partition works in $O(n)$).
Because I have a constant number of elements that are not in their right place I will use partition constant $\times n$ times which means the algorithm is $O(n)$ as asked. Problem is that checking for every index if the element in the index is in his right place is $O(n)$ and doing it for every index is $O(n)$ so it sums up to $O(n^2)$ so maybe the solution is not right. (Every other solution I wrote also has this problem)
I will be glad for any help.


texts: Building probability distribution functions from observation

texts:
There are N players and M objects, each of the objects has a value. Each player has a strategy in choosing an object. Each round a player will choose an object, many players can choose the same object. However the value of each object is divided evenly among every player that has chosen it. There will be 9000 rounds(choices) per game. Our goal is to maximize the values that we accumulate at the end of the game.

Question: how can I build a probability distribution function for each playing assuming that their decisions are random variables?

Current Approach: My current approach is to count the frequency of a player choosing a specific object and dividing by the total number of rounds, that would give a probability a player is likely to choose that specific object.

Problem: With each player playing aggressively trying to be unpredictable as possible(noise), with my current approach the probability distribution functions are not accurate(9000 rounds doesn't seem to be enough data). Is there a better way to build these distribution functions?

Note: I've read somewhere that (Bayes model and HMM) are more superior than frequency counts, but I am not sure how to adapt it to this situation.


texts: Is L2 = {a^n| n is a product of one or more primes} regular?

texts:
I am having a hard time proving the following with pumping lemma:
Is $L_2 = \{a^n \mid \text{$n$ is a product of one or more primes}\}$ regular?

Here's what I have so far:

Suppose $L$ is regular, and let $m$ be the constant pumping lemma.
Let then $w = a^m$ where $m$ is a product of at least one prime number, therefore $w$ is in the language $L_2$ and $|w| \geq m$.
Then $w = xyz$, where $|xy| \leq m$ and $|y| \geq 1$.
Then $y = a^j$ where $j \geq 1$.

This is where I'm not sure what to do:
Pumping down we get $w_2 = a^{m-j}$

I don't know where to keep going from here since I don't even know if pumping down is the right thing to do.


texts: Example of execution fragment of multi-process transition system

texts:
Here is a simple transition system of beverage vending machine:

The exemplary execution fragments can look like this:

Now, imagine we have multi-process TS where processes are identical and communicate over channels. I don't understand the semantics of how to present an execution fragment that runs across multiple processes. Should I specify the whole execution in one line? If yes how do I denote that the state belongs to some certain process? Or maybe I present execution fragment on each process in the separate line? I'd love to see a "meta-example" of how that could look like.

I am referring to this specific exercise sheet, task 3.) b). The figures are from the book "Principles of Model Checking" by Christel Baier and Joost-Pieter Katoen p. 22 and p. 25.


texts:
In Corman, Introduction To Algorithms, 3rd edition, question 2-4 it asks to count the number of inversions in a list of numbers in $\theta( n \lg n )$ time.  He uses a modified Merge Sort to accomplish this.  However, there is something in his algorithm which seems redundant / unnecessary to me:

MERGE-INVERSIONS(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1 ... n1 + 1] and R[1 ... n2 + 1] be new arrays
for i = 1 to n1
    L[i] = A[p + i - 1]
for j = 1 to n2
    R[j] = A[q + j]
L[n1 + 1] = infinity
R[n2 + 1] = infinity
i = 1
j = 1
inversions = 0
counted = FALSE
for k = p to r
    if counted == FALSE and R[j]  < L[i]
        inversions = inversions + n1 - i + 1
        counted = TRUE
    if L[i] <= R[j]
        A[k] = L[i]
        i++
    else A[k] = R[j]
        j++
        counted = FALSE
return inversions

The counted variable seems redundant to me and I would have written the last for loop as follows:

inversions = 0
for k = p to r
    if L[i] <= R[j]
        A[k] = L[i]
        i++
    else A[k] = R[j]
        inversions = inversions + n1 - i + 1
        j++
return inversions

What am I missing, or is counted really unnecessary?


texts: How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?

texts:
The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion:
$$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{h - 1}^2 $$
How to compute the general term formula with this recursion formula?


texts:
I needed to sort vertices into buckets as an optimization for collision detection later. I came up with this:

Go over all the vertices and count the size that each bucket needs to be to contain them into an array.
Shift the size array index by -1 unit and use it as offset array instead.
Create a single array for all the indices, go over all the vertices again and place their indices according to the offsets while bumping the offset each time.
Use the index list to translate vertices to their new positions (or optionally move the vertices on step 3 if you don't need a map but I did for transforming other primitives).

Surprisingly enough, it's much faster than std::sort (by 10x) or a gpu bitonic sort (by 13x) that I implemented earlier. It can't be a new idea since it's so simplistic in its concept.  So what is it called? I want to see what other people have done with it to perhaps make it even faster.


texts: Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?

texts:
I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half of the proof. Namely, the proof of the statement that the intersection of a CFL and a regular language is again CFL.

The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunately, Sipser does not handle it in his book Introduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.


texts:
Everybody says that Valuation is a truth value assignment to all variables in the formula.

How do you call the valuation when some (neither single yet nor all) variables are
assigned a value?
Truth value implies that variables are binary. How do you call the multivalued
case?
I know that Haskel uses the term "partial application". If "partial application" is supplied with optimization, they call it "partial evaluation". I am not sure whether boolean valuation falls into the application or evaluation or second category?

ps, Dec 2013

Is it right that single variable assignment is called Restrict operation? I read Restrict(Function F, variable v, constant k) is defined as "Shannon cofactor of $F$ w.r.t. $v=k$" in Berkly lectures.


texts: "Learning occupancy grid maps with forward sensor models, S.Thurn,2008" a formula that is difficult to overcome

texts:
I am reviewing the document" Learning occupancy grid maps with forward sensor models, S.Thrun, 2008" (http://faculty.iiit.ac.in/~mkrishna/ThrunOccGrid.pdf)

i am really confused about formula (26), which is merged by formula (22), (24), (25) in an "intersection of probabilities" computed in (22),(24),(25). So, it should be a product of factors in (22),(24),(25). If it is correct, the first factor of (26), 1/sqrt(2*π*σ), should be powered.

any one can tell me why 1/sqrt(2*π*σ) isn't powered?


texts: "Subpaths" of Dijkstra's shortest path also shortest?

texts: I have trouble putting this into formal mathematical terms, so let's suppose that I found the shortest path from A to E as A > C > D > B > F > E with Dijkstra's algorithm. Am I correct in assuming that the shortest path from C to B would be C > D > B, and that the shortest path from D to F would be D > B > F?


texts: Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut?

texts:
I'm currently watching a video on the analysis of Krager's Algorithm, and I am confused about something.

The analysis goes as follows:

Fix a min cut $(A,B)$.

Let $k$ = # of edges crossing $(A,B)$ , these edges will be called $F$

Let $S_{i}$ be the event that an edge of $F$ is contracted in iteration $i$.

For the first iteration,
$\Pr [S_i] = \frac{\text{# of crossing edges}}{\text{# of edges}}=\frac{k}{m}$,

where $k$ is the number of crossing edges, and $m$ is the total number of edges.

Here's where I get confused:

Observation: The degree of each vertex is at least k

Reason: Each vertex v defines a cut $\left( \{v\}, V - \{v\} \right)$

I don't really understand. The reason given for his observation doesn't make much sense to me. Why would the degree of each vertex be at least the number of edges crossing our min cut (A,B)?


texts:
I have a matrix of n lines and T columns, containing only 0's or 1's.

I would like to make permutations of lines (and lines only) to make the largest submatrix of 1's possible (i.e. i want to find sqaures of 1's in my matrix).

I thought of it as matrix clustering, but google remains silent; Does this problem have a name in computer science ?

I am also interested in the similar problem where one can apply permutations on both lines and columns.

Thanks,

Edit : Found out about Biclustering (https://en.wikipedia.org/wiki/Biclustering), which is exactly it. Thanks again !


texts: pictorial representation of pre and post ordering for edge types

texts:
I am reading chapter 3 Decomposition of Graphs of Algorithms by Dasgupta, Papadimitriou & Vazirani and they show a pictorial representation of pre and post numbers with brackets for tree, forward, back and cross edges. I have pasted the image of the area I am unclear on.
I am assuming that u is the node/vertex we see first and then we see v later. Comparing to the 2nd image showing the definitions on a graph, I am taking u as node A.
What I don't get is the order for the other 2 back and cross edges. What I have is

u v u v for back edge.
u u v v for cross edge.

Essentially the order is flipped with u and v in what the textbook has. Could someone clarify why this is the case with the image below.

I read this answer but I came out more confused with the explanation.
Surprisingly I was able to correctly identify the pre and post numbers in this figure in the textbook. It is the letters u and v that have me confused.


texts: Adding constraints in grammar for Grammatical Evolution

texts:
I'm trying to use Grammatical Evolution for creating trading strategies. Each sentence in the grammar when evaluated gives a weight matrix of size n x p . (n is the length of backtesting period and p is the total number of stocks in portfolio)

BNF form of Grammar

<expr>  ::= (<foptr>(<expr>,<expr>,<day>))|
        (<fopbi>(<expr>,<day>))|
        (<fopun>(<expr>))|
        (<expr><matbi><expr>)  |
        <var>
<foptr> ::= corr | covariance
<fopbi> ::= mean |
            sma|
            ema
<fopun> ::= rank| -1* | 1/
<matbi> ::= + | - | * | /
<var> ::= Open|High|Low|Close|Volume
<day> ::=  5 | 10 | 15 | 20

The problem is some expressions in this grammar do not make sense. For example, we cannot have a strategy like $Volume/Volume$ or $Low-Low$, etc. And some of the strategies do not have any physical significance, for example, the strategy $Volume+Close$ is not valid as the units of volume and close are different. Any suggestions/references on how to add these constraints to the grammar or circumventing this issue in genetic algorithms will be helpful.


texts: What is the difference between "definition" and "inductive" in Coq?

texts:
In Coq, you can use two different kinds of keywords to do definitions--Inductive and Definition.  I do not understand the difference between an inductive and a definition, or when it is appropriate to use one instead of the other.

Could someone with experience in Coq please shed some light on this, or provide a reference that is more succinct/informative on this point than the standard Coq tutorial?

Update:

Here are some additional, generally quite basic questions I have about Coq:

How do you force a set to be finite?  Is there a "finite set" data type?
What exactly do ":" and ":=" mean?


texts: If P=NP, does this imply that all problems are NP-hard?

texts:
A problem is said to be NP-hard if every problem in NP is reducible to that problem in polynomial time.
Hence, if P=NP, wouldn't that imply that every problem in NP is reducible to every possible problem, in polynomial time?
However the diagram above seems to imply that if P=NP, there exist problems outside of NP-hard.
Is there anything I am missing?


texts: validation of a pumping lemma proof for regular languages

texts:
I have the following regular expression:

Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT
I was just wondering, because $L$ is made up of a union of two expressions, is it valid to split $L$ into
$ L_1=\{a^ib^jc^{2j-1} | i<=j \land i,j>0\}$
$L_2=\{a^ib^jc^{2j-1}| i>=2j-1 \land i,j>0\}$
and show for  each $L_1$ and $L_2$ that the pumping lemma does not work on them (so for $L_1$ I just show that for each $k$, $i$ is not smaller or equal to $j$, and similarly for $L_2$.
By that I show that $L_1$ and $L_2$ are not regular which means that the union of the two will also be not regular. Is this correct?
thank you.


texts:
I am trying to understand how PCA works, and think I got most of it except...

By calculating eigenvalues/vectors of the covariance matrix of the original dataset allows to find those dimensions where data is least correlated (lowest covariance). Sorting them based on eigenvalues is the method which allows the sorting of dimensions.

Hence, multiplying the original dataset by the 'feature matrix' allows to discard those dimensions which are least significant.

What I don't understand is the relation between the covariance matrix and eigenvectors. Why is it that eigenvectors of the covariance matrix automatically allow us to find the directions where data is least correlated?

Hope this makes sense :)


texts:
I often hear phrases like 'true concurrency semantics' and 'true concurrency equivalences' without any references. What does those terms mean and why are they important?

What are some examples of true concurrency equivalences and what is the need for them? E.g. in which cases they are more applicable than more standard equivalences (bisimulation, trace equivalence, etc)?


texts: What is growth of $\psi_q(m) = \min \{ p: m ∣ (q^p−1) \}$ for fixed $q$?

texts:
I have to estimate the computational complexity of some algorithm that does $\psi_q(m)$ iterations. Assume that all inputs $m$ are coprime to $q$.

So I need to know what growth the $\psi(m)$ has.


texts: Is there an implicit condition OPT<P(|input|) in approximation schemes?

texts: Sorry if my question is banal. Consider an approximation scheme such as FPTAS that guarantees to find a soln>(1-eps)OPT for maximization. Now consider if OPT=exp(|input|) so It easily can be seen that soln is exp(|input|) So its run-time will be exponential too(just a print of result is exponential). So can we say the condition OPT<P(|input|) is a necessary condition for any problem that we want to find an approximation scheme algorithm for that?


texts: Partitioning a Number on the basis of an equation

texts:
I have an equation $x = 3a+4b+2c+4d$, where $a$, $b$, $c$ and $d$ are nonnegative integers such that $a+b+c+d=5$.
What algorithm can I use to calculate maximum value of $x$?


texts:
I'm reading about Quicksort algorithm, specifically using the Hoare partitioning scheme.

Wikipedia page says, that when choosing a pivot element one can use both hi and lo indexes. However, when implementing the same code in Python, my code fails in a very specific circumstances. My python code is a translation of the pseudo-code from Wikipedia.

def swap(A, i, j):
   A[i], A[j] = A[j], A[i]

def quick_sort_hoare(A, lo, hi):
    if lo < hi:
        p = hoare_part(A, lo, hi)
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)

def hoare_part(A, lo, hi):
    i = lo - 1
    j = hi + 1

    pivot = A[lo]

    while True:
        while True:
            i += 1
            if A[i] >= pivot:
                break

        while True:
            j -= 1
            if A[j] <= pivot:
                break

        if i >= j:
            return j

        swap(A, i, j)

This particular code works for many-many test-cases generated at random. However if I put  pivot = A[hi] in partitioning, sometimes it fails. Specifically, when the last element(i.e. pviot) appears to be the largest in the array at hand. In that case i appears to be equal the length of the array and everything goes to the infinite recursion.

Furthermore, in Introduction to Algorithms by Cormen et al., we see the following pseudo-code for the same partitioning:

This piece of code seems to be identical to the one from Wikipedia. Moreover, seems like the code would fail on their example. Because I understand this very unlikely to be the case for them to make this mistake, I'm wrong somewhere.

So my questions are:

What am I getting wrong?
Can hi be used for pivoting or there is a very specific fundamental reason to pick A[lo]?


texts: Undecidability of a restricted version of the acceptance problem

texts:
It's known that the following language, the so-called acceptance problem is undecidable:

$A_{TM} = \{\langle M,w\rangle\,\vert\,M\text{ is a TM which accepts }w\}$

The proof is by contradiction: Assume there is a TM $H$ which decides $A_{TM}$. Let $D$ be another TM. Given the code of a TM $M$, $\langle M\rangle$ as input, $D$ simulates $H$ on $\langle M,\langle M\rangle\rangle$, and accepts, if $H$ rejects this input and rejects, if $H$ accepts it. That is, $D$ accepts $\langle M\rangle$ if $M$ rejects its own code, and vice versa. Running $D$ on its own code, $\langle D\rangle$, leads to contradiction.

Let's restrict $A_{TM}$ by excluding all input strings which encode a TM:

$E = \{w\,\vert\,w\text{ is a structurally valid encoding of a TM}\}$
 $A'_{TM} = \{\langle M,w\rangle\,\vert\,M\text{ is a TM which accepts }w\text{ and }w\not\in E\}$

I'd like to know whether $A'_{TM}$ is also undecidable.

I tried to prove it the above way: Assume there is a TM $H'$ which decides $A'_{TM}$. Let $D'$ be another TM. Given the code of a TM $M$, $\langle M\rangle$ as input, $D'$ simulates $H'$ on $\langle M,\langle M\rangle\rangle$, and accepts, if $H'$ rejects this input and rejects, if $H'$ accepts it. The problem is that running $D'$ on its own code, $\langle D'\rangle$, doesn't necessarily lead to contradiction. I mean since $\langle D',\langle D'\rangle\rangle$ is not a member of $A'_{TM}$, we don't know what $H'$ will do with it.

Note: An encoding of TMs, and TMs along with an input string

Let $M = (Q, \Sigma, \Gamma, \delta, q_{i}, q_{a}, q_{r})$ be a TM, where

$Q$ is the set of states,
$\Sigma = \{0, 1\}$ is the input alphabet,
$\Gamma$ is the tape alphabet ($\Sigma\subset\Gamma$),
$\delta: (Q-\{q_a, q_r\})\times\Gamma\rightarrow Q\times\Gamma\times\{L,R,S\}$ is the transition function,
$L$, $R$ and $S$ denote the respective head movements, "left", "right" and "stay", and
$q_i$, $q_a$ and $q_r$ are the initial, accepting and rejecting state, respectively.

Let's assign a unique positive integer to each element of $Q$, and do the same in case of $\Sigma$, $\Gamma$ and $\{L,R,S\}$. Now every transition rule $\delta(p, a) = (q, b, m)$ can be encoded as $\langle p\rangle 1\langle a\rangle 1\langle q\rangle 1\langle b\rangle 1 \langle m\rangle$, where $\langle x\rangle$ denotes a sequence of $0$'s, with length being equal to the positive integer assigned to $x$. The encoding of $M$, denoted by $\langle M\rangle$, can be created by concatenating its transition rules, separated by $11$'s. The combined encoding of $M$, and an input string, $w\in\Sigma^*$, denoted by $\langle M,w\rangle$ is $\langle M\rangle111w$.


texts: Is the language $\{a^n b^m \mid 2n + 3m \le 1000 \}$ regular?

texts:
We have a language  $$ L = \{a^n b^m \mid 2n + 3m \le 1000 \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say x = $x=a^{h}$ and $y=a^{t}$ and $z =a^{n-t-h}b^m$
if I say i = 0 everything is okay because $L =a^{n-t}b^m$ and 2(n-t) + 3m <= 1000
if I say i = 2  $L =a^{n+t}b^m$ and 2(n+t) + 3m <= 1000 because I'm not sure about t value.
I think it didn't work. Is this language regular? How can I prove that?


texts: What precisely/concisely is the "head" of a singly linked list? I ask bc of ambiguity online

texts:
So I have a pic which I think illustrates my confusion:

the read surrounds what I wonder is the head? Does head refer to a node with both a data and next, or only a node with next? In other words, which marked box does it refer to in my pic?


texts: Doubt regarding strong component in a graph

texts:
I know that strong component in a graph means between any 2 vertices there should be bi-directional path.

My doubt is cycle is always a strong component. can there be any other subgraph with some property P so that it is strong component ie., P implies strong component.


texts: Reducing 3SAT to a Set Splitting Problem

texts:
I want to be able to reduce the 3SAT problem to a flavor of set-splitting problem. Basically, given $n$ items and $m$ subsets $S_1, S_2,...,S_m$ of these items I want a yes or no answer based upon the fact if it is possible to color the items red and blue so that each set $S_i$ contains at least one red item and at least one blue item.

I know this this problem is in NP and it is fairly simple to prove (at least that is what I think).

I actually want to prove that the problem is NP hard by reduction from 3SAT. I want to be able to convert an instance of 3SAT into an instance of the aforementioned set-splitting such that a yes instance of 3SAT get mapped to a yes instance of set-splitting and vice versa.

I have a basic intuition about how I can do this: given a 3SAT formula $f$ on $n$ variables I will create $2n+1$ items. One to denote each $x_i$ one for each $\overline{x_i}$ and an extra item.
I am not quite sure how to proceed beyond this basic intuition. This might be a gap in my understanding of the problem. Is this the right way to approach this? If so, how can I use this intuition to actually prove that this is NP hard by way of reduction from 3SAT?

Thank you!


texts: When we do register renaming to avoid WAR and WAW hazards while executing instructions, how can we know that there is no need for a physical register anymore and we can put it back in the free list?


texts: Propagating node labels upwards in a tree

texts:
I am trying to think of an efficient way to synchronize a tree's nodes with the following rules.

Consider for instance this tree:

so the top of the heap is always B which can have many leaf-type nodes called G, or children which are node themselves called S, which can have leaves as well (G)

it is possible in the future that each G will have many leaves, but I assume the algorithm will be the same

So each G has a list of categories, that I want to syncronize (add and remove) with their parents.

so if g1 has categories [a,b,c] then B will have [a,b,c], but if g2 has categories [a,g,w] B will have [a,b,c,g,w] (all the categories of its children)

if the S nodes' leaves have categories it goes the same, each G of an S node will have categories that will propagate to their parent (which will get all the categories of its children) and in return will propagate the categories up to B, and B will have a union of all categories below it.

if any of the G leaves changes categories, or if the a G is added or an S is added the entire tree/heap need to syncronize according the new categories added.

I need the categories to be syncronized when added or removed. So every time a category is added I need the parent to get the categories of its children, which sort of scan the whole tree again

Is there an efficient way to do this?


texts: Is recomnder systems part of computer science?

texts:
I want to work on a paper with one of my friends in Recommender systems. My field is programming, and I favourite part is to be more technical.
I want to know that, is field of Recommender systems a part of Computer science or field in Information technology?


texts: How does the equation for min heap array indexing work?

texts:
I've been reading about min heaps, currently looking at this article, and I am very confused by something.

The article makes the following statement:

  If a given node is located at index 'x' in the array, its left child
  exists at index = 2x, and its right child exists at index = 2x + 1.
  Each node's parent exists at index = x / 2 (rounded down).

It gives this example:

This min heap is represented in the array [100, 19, 36, 17, 3, 25, 1, 2, 7].

But this doesn't jive with the preceding statement about indexing. 36 can be found at index 2, and 2 * 2 is 4. But index 4 is 3-- the right child of the 19 node, not the left child of the 36 node.

What am I missing here?


texts: What is a proper way of solving a multibody nonlinear problem?

texts:
I encountered some system of ~5000 random nodes connected by ~8000 non-hookean springs, with ~1300 nodes at the boundary fixed as the "wall", the potential of the springs are of the form $dx*e^{(dx/a)}$ where $a$ is a constant and $dx$ the strain (displacement/original length) of the spring, I am using Monte Carlo method to find the energy-minimized configuration after I performed some "perturbation", say, a simple shear or a isotropic expansion of the whole system.

It seems that the conventional energy minimization schemes such as "steepest Descent", or "simulated annealing" is not working as efficiently here as the case of linear situations, it always fail to converge to a  satisfactorily balanced state.

Could someone share your experiences in dealing with such non-linear situations?

Thank you so much!


texts: How to use an old SAT solver to discover a new one, as is done in The Golden Ticket?

texts:
In Lance Fortnow's book The Golden Ticket, he mentions that once you have a polynomial-time algorithm for an NP-complete problem, you can use it to find a faster algorithm. Can you tell me how that is done? And once that is done, you can use the new algorithm to discover an even faster one ad infinitum, till a fixed point. Below is the exact quote from the book:

  "So what do you ask a genie who will grant you only one wish?" said
  the adviser.

  "I have no idea," replied Steve.

  "You ask for a genie who will grant all your wishes."

  The proverbial light bulb went off in Steve's head. He knew there must
  be some better algorithm for solving clique problems out there
  somewhere, but he couldn't figure it out on his own. But he had the
  genie, the Tsinghua code, which could search an exponential number of
  possibilities quickly. So he wrote up a program that used the
  Tsinghua routines to search for a better algorithm for NP problems.
  He got permission to use the computing resources of the National
  Center for Supercomputing Applications (NCSA), based at the University
  of Illinois. After weeks of processing time his work paid off a little
  bit, finding a new algorithm that had a 5 percent improvement over the
  Tsinghua code--good enough for a research paper but not enough to make
  a real impact.

  His adviser simply said, "Try again using the new code."

  So Steve used his new code to find an even faster algorithm for NP
  problems. A few weeks later he had a 20 percent improvement.

  But his adviser was not impressed. "Try it again."

  Steve replied, "Why don't I just set up the computer to automatically
  keep trying with the new code it finds?"

  The adviser gave that look, the look that told a student he had
  achieved enlightenment, or at least had realized the obvious.

  Steve went back to his office and started the tricky process of
  writing code that searches for faster code, and then used this faster
  code to find even faster code and continue this process until it could
  find no further improvement.

Now focus on SAT. MiniSAT is a fast SAT solver, though not to the point of being polynomial-time.

  How to use MiniSAT to mechanically discover a new SAT solver?


texts: Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities

texts:
Prove that if a CFL $L$ is inherently ambiguous, then for any grammar $G$ with $L(G) = L$, there are infinitely many strings in $L$ that have (at least) 2 different derivations in $G$.

Here's a sketch of a proof I have in mind:

  Suppose $G = (V, \Sigma, P, S)$ is a grammar satisfying $L(G) = L$.  Then, since $L$ is inherently ambiguous, it must be that $G$ is ambiguous.  Hence, there exists a string, call it $z$, with two different derivations in $G$.  Now, if the right-hand side of every production in G is of length $\leq d$, and if $|z| \geq d^{|V| + 1}$, then by Ogden's Lemma, if
  $d^{|V| + 1}$ or more symbols of $z$ are marked arbitrarily, there exists a decomposition $z = uvwxy$ such that there exists a variable $A$ in G such that

  $S \Longrightarrow^* uAy $

  $ A \Longrightarrow^* vAx$

  $A \Longrightarrow^* w$

  Hence, every derivation of $z$ must at least contain the sentential forms $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uvwxy = z$

  In particular, we may indefinitely "pump" the sentential form $uvAxy$ in both derivations via repeated application of $ A \Longrightarrow^* vAx$.  Hence, the resulting two derivations must at least contain the sentential forms

  $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uv^iAx^iy \Longrightarrow^* uv^iwx^iy \in L$

  Both derivations; however, are still different, and thus we have that strings of the form $uv^iwx^iy \in L$, with $i \geq 2$ have 2 distinct derivations.  Hence, there are infinitely many strings in $L$ with 2 different derivations.

Now, I do see some problems with this sketch.  For one, we cannot guarantee that $|z| \geq d^{|V| + 1}$.  Second, even if $|z| \geq d^{|V| + 1}$, I'm not sure that we can guarantee that both derivations of z must contain the sentential forms $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uvwxy = z$.

  Given $k = |V|$, suppose that every string of length $\geq d^{k+1}$ is unambiguous in G.  Let $z$ be an arbitrary string in $L$, with $|z| \geq d^{k+1}$.  Then by Ogden's lemma, there exists a decomposition $z = uvwxy$ and a derivation of $uv^2wx^2y$, namely:

  $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uv^2Ax^2y \Longrightarrow^* uv^2wx^2y$.  Clearly, $|uv^2wx^2y| \geq d^{|V| + 1}$, and thus the provided derivation for the string is unique.  But now, mark only the characters in $uv^2wx^2y$ which appear in $u, w, \text{ or } y$. The resulting derivation for $uv^2wx^2y$, obtained using Ogden's Lemma, must differ from the previous derivation for $uv^2wx^2y$, contradiction.  Hence, there exists an ambiguous string of length $\geq d^{|V| + 1}$, and we may apply the argument above.


texts: Alternative proof for the undecidability of $A_{TM}$

texts:
The proof of the undecidability of $A_{TM}$ in Michael Sipser's textbook* contains the definition of a Turing Machine, which accepts the encoding of a TM, if this TM doesn't accept its own encoding, and rejects it, if it does. If this TM is run on its own encoding, there is problem: it should accept if it doesn't accept and vice versa.

My problem with this proof is that it strongly resembles Russel's paradox. This paradox arises if we define a set, which contains all sets that are not members of themselves. If we ask whether this set contains itself, there is problem: it should contain itself if it doesn't contain itself and vice versa.

Russels's paradox has been eliminated from axiomatic set theory: in ZFC, it follows from the axioms that such a property doesn't define a valid set. Interestingly enough, in the theory of computation, a similar property defines a valid TM.

That's why I don't like the proof in Sipser's book. I'd like to emphasize that I know that this proof is perfectly valid, but I'd like to know if there is another proof which follows a different chain of thought, and doesn't define such a TM.

*Sipser, M.: Introduction to the Theory of Computation (2nd ed.), 2006, page 179. On this page, Sipser uses the term halting problem for the language $A_{TM}$. The proper name for this language is acceptance problem, see the footnote on page 188.


texts: Logical characterization of P versus NP problem (and references for least fixed point logic)

texts:
Wikipedia says the following (and more) about the logical characterization of the P versus NP problem here:

  Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?"

My question is, has there been any work done to tackle the P versus NP problem from this logical angle, by reasoning about existential second-order logic and first-order logic with least fixed point?

And more generally, what are some good references for learning about least fixed point logic?


texts: If it's Possible to Create the If-Statement from Simpler Primitives

texts:
This question is about how to create an if statement (one of the control-flow statements) from scratch.

An if-statement is typically a built-in construct in languages. However, I am wondering if there is a way to construct an if-statement from some other non-control-flow primitives. I am also wondering how to do this with Boolean algebra, and there is a link there to how to represent if/else statements with circuits.

I started off trying like this:

var x = true
var run = {
    true: [],
    false: []
}
var state = []
while (true) {
    x = !x
    var arr = run[x == true]
    for (var i = 0, n = arr.length; i < n; i++) {

    }
}

That x toggle seemed like it could be used to somehow shift the evaluation path. Then in the state array there would be states of the application listed, and so the application would go into that state if the x was 0 vs. 1. But there pops up the if right there, so it's hard to make it work without resorting to if somewhere. The for loop is also a form of control-flow, so would hope to avoid that.

Was going to try to test it out to simulate a program such as this:

if (a == 1) {
    if (b == 1) {
        console.log('1.1')
    }

    if (b == 2) {
        console.log('1.2')
    }
}

if (a == 2) {
    if (b == 1) {
        console.log('2.1')
    }

    if (b == 2) {
        console.log('2.2')
    }
}

if (a == 3) {
    if (b == 1) {
        console.log('3.1')
    }

    if (b == 2) {
        console.log('3.2')
    }
}

The program would then run:

myiftest(1, 1) // a == 1, b == 1
myiftest(1, 2)
...

There are ways to sort of cheat, such as using && to hack the conditional. For example:

a == 1 && b == 1 && console.log('1.1')

You could also do it with a while loop:

while (a == 1 && b == 1) {
  console.log('1.1')
  break
}

I would like to see if there's any way to do this using only non-control-flow statements in JavaScript (or in C, Ruby, or Python, any modern iterative language, or even Assembly which might make it easier), i.e. not cheating like the above. I don't even know if it's possible, so any form that shows it is possible (or not possible!) would be great to know.

It's okay to use the while(true) loop to start it out, so the program actually runs (if necessary).

Even in assembly the "if" statement is built into the jmp or jump-/branch-related statements.


texts: How are metric TSP and Eulerian cycle equivalent?

texts:
In paper : https://arxiv.org/pdf/1908.00227.pdf it is stated that

  In the metric TSP problem, which we study here, the distances satisfy the triangle inequality. Therefore the problem is equivalent to finding a closed Eulerian connected walk of minimum cost.

They don't seem to be equivalent at all, since for a complete graph of size 5, with all edge costs 1, a metric TSP solution would be of cost (and length) 5, whereas an Eulerian cycle would be of cost (and length) 10. Am I misunderstanding?


texts: Set of DAG vertices disconnecting a vertex from forbidden vertices

texts:
Let $v$ be a vertex with in-degree 0 in an (acyclic) DAG $G$, and let $F$ be a subset of $G$'s vertices (the "forbidden") vertices. Now suppose $U$ is a set of vertices such that every path from $v$ to $F$ intersects $U$.

Is there a commonly-used term for such sets? I was thinking about using the term "Front", but a (cursory and lazy) search tells me that's not a popular term. I can't use "cut", because that's reserved for sets of edges with the similar property (cutting off $v$ from $F$; usually $F$ is the subgraph of all vertices reachable from $A$ but not in $A$).

Also, suppose that $U$ is minimal, in the sense that for every $u$ in $U$, there's a path from $v$ to $F$ which intersects no other vertex of $U$. Is there a commony-used term for this kind of sets?

If it helps, I'm willing to refer to $v$ as a "source" and to $F$ as the set of "sinks".


texts: Spanning tree in a graph of intersecting sets

texts:
Consider $n$ sets, $X_i$, each having $n$ elements or fewer, drawn among a set of at most $m \gt n$ elements. In other words
$$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\right| \le m$$
Consider the complete graph $G$ formed by taking every $X_i$ as a node, and weighing every edge $(i,j)$ by the cardinal of the symmetric difference $X_i \triangle X_j$.
An immediate bound on the weight of the minimal spanning tree is $\mathcal{O}(n^2)$, since each edge is at most $2 n$, but can we refine this to $\mathcal{O}(m)$?
For illustration, consider $2 p$ sets, $p$ of which contain the integers between $1$ and $p$ and $p$ of which contain the integers of between $p+1$ and $2p$. A minimal spanning tree has weight $p$ but a poorly chose tree on this graph would have weight $(p-1)p$. Intuitively, if there are only $m$ values to chose from, the sets can't all be that different from one another.
EDIT:
Contributor Dmitry gives a nice counterexample below in which $m$ is nearly but not quite $n^2$.
A counterexample or proof would still be of interest in the case where $m = \mathcal{O}(k n)$. Can the weight of spanning-tree be bound by $\mathcal{O}(f(k) n)$? By $\mathcal{O}(f(k) n \log^c n)$?


texts: How to justify that if i=j=0 i will have a 0 in the Needleman-Wunsch or Levenchtein distance algorithm?

texts: I can't understand why we are setting the D(0,0) to 0 in the alignment matrix when we are running the algorithms for minimum distance like the Levencthein algorithm?


texts:
I have just began with my course of complexity and computability and I need your experience to help me progress !!

Something is not clear for me:

It is asked to determine if L1 is decidable or not, below the language is an answer given by a student. And I'm not agree with it...

The Rice theorem is given as follow :

I don't get why L1 is decidable since, for me, it looks like the Rice theorem could be immediately applied.

Did I understood very badly or am I right ? In the first case, why ?

Thanks in advance for your help !

Elia


texts: Point in Polygon Problem: Has anybody invoked the line integral?

texts:
Some twenty years prior I was given the task to solve the Point in Polygon problem for a piece of commercial software. I solved it invoking the ray casting algorithm. After a variety of enhancements the function worked well enough, but I felt there was a better way. I found inspiration in Gauss's Law. Charges and the electric field aside, it boils down to, in 2D, a (contour) line integral. In a plane, the integral $\int_C d\theta = 2\pi$ if the point lies within the contour, and is zero if the point lies outside. With this in mind I reformulated the algorithm for arbitrary polygons:

double sum_theta = 0`
for( int i = 0 ; i < n_vtx ; i++ )
{
    int    j         = (i + 1) % n_vtx;
    XYPT   p_i       = ngon[i];
    XYPT   p_j       = ngon[j];
    XYPT   vector_i  = p_i - p_o;                 // vector from point o to vertex i
    XYPT   vector_j  = p_j - p_o;                 // vector from point o to vertex j
    double cp        = vector_i.cross( vector_j ) // cross product
    double dp        = vector_i.dot  ( vector_j ) // dot   product
           sum_theta+= Atan2( cp, dp );

}
if( sum > pi ) return INSIDE;
else           return OUTSIDE;

I'm not asking if this works. It does, rather well. (And I see no reason to replace it; I like its simplicity and elegance.) My question to this forum is largely of curiosity: Indeed, how much slower is this method than doing it by ray-casting (which can present gotchas) and intersection count; or by counting winding number (WN)? The application this services never has self-intersecting polygons (so, it seems, WN has no particular advantage) and the vertex count is never excessive (n_max ~ 25).

Any thoughts?


texts: Keywords/terminology for using "extra" information in search problems?

texts:
I am trying to find references on a particular idea, but I don't know which keywords to use in a google search.

the idea is: as an example, consider graph search. maybe the problem is: find a path from node $X$ to node $Y$. We can consider two versions of this problem:

For any node $n$, we can query only the information: which other nodes are connected to it?
For any node $n$, we can additionally query the information: what is the "airplane distance" between $n$ and $Y$.

Clearly, if we have the additional information from (2), we can construct a larger set of possible search algorithms, in particular, ones that are faster.

My question is: What terminology/keywords do I need to search to read about this phenomenon that some search algorithms have more "heuristic" information at their disposal than others, and can therefore employ better search heuristics?


texts: Pairwise hash functions that are independent from each other

texts:
Is there there a way to build a collection of universal hash functions $H=\{h| h:U\to D \}$ where the values of two hash functions are independent one from another? i.e., $\Pr_{h_1,h_2\in H}(h_1(x)=y  \land h_2(z)=w )=|D|^{-2}$ for each $x,y,z,w\in U$.

Also, is there a term for such collection?


texts:
My data structures exam contains the following question:

Which of the statements below about red-black trees is true? (select one or more)

Every path from the root to a leaf has the same amount of red links.
A node never has two red links to his childs.
Using a red-black tree, you can always draw the associated 2-3 tree.
All leafs of a red-black tree are at the same height.

The correct answer is: 2 and 3.
I don't understand why a node can never have two red links to his child. On the image below (from Wikipedia), I can see two red childs at node 25.
Could someone explain this to me?


texts: Forming red-black tree from binary tree conserving in-order traversal

texts:
What is the optimal algorithm (in terms of time complexity) that can transform any binary tree to a red-black tree, with the requirement that in-order traversal must yield the same values for the new tree?

Is iterative insertion of the original nodes sufficient, or can it be done with better complexity?