texts:
General satisfiability (with a few exceptions such as Horn Clauses) is not believed to have an algorithmic solution. However, the following algorithm appears to be a solution for general satisfiability. What exactly is the flaw with the following algorithm?

Let $W$ be an empty set which will contain all variables that necessarily have to be true or false.
Let $L$ be the set of clauses.
Loop through $L$.
Every time a non-conditional variable† is found, remove it from $L$ and insert it into $W$.
If this leaves an empty AND implication‡, remove all variables in that empty implication from $L$ and insert into $W$.
If this leaves an empty OR implication‡, create new instances of the algorithm, where each instance deals with one variable in the implication (i.e. if the implication is: $x V \implies y$, create one instance where $x$ is inserted into $W$, one where $y$ is inserted into $W$ and one where $x$ and $y$ are inserted into $W$).
Set all variables in $W$ to the value they necessarily have to be.
Reinsert the variables in $W$ in $L$ with their changed values and check if all clauses  are satisfied.
If satisfiability is met, then return $L$, else return "Not Satisfiable".

† A non conditional variable is defined as a variable that is necessary true or false, e.g. $\implies x$ or $\implies \neg y$.

‡ An empty implication is defined as an implication where one side is empty (e.g. $\implies x \wedge y$) or the other side is necessarily true (e.g. $\mathrm{true} \vee a \implies b$.

To get a more intuitive understanding of the algorithm consider the following set of clauses $L$:

$$\begin{align}
  a \wedge b &\implies c & \text{(i)} \\
  &\implies f \wedge g & \text{(ii)} \\
  f &\implies \neg a & \text{(iii)} \\
  f \vee a &\implies b & \text{(iv)} \\
  &\implies c & \text{(v)} \\
\end{align}$$

The algorithm will do the following:

1) Since $c$, $f$, $g$ are non-conditional variables, the algorithm will insert them into $W$. $W = \{c, f, g\}$.

2) Removing $c$, $f$ and $g$ will leave the empty clauses: $\implies \neg a, a \wedge b, b$. These will be added to $W$. $W = \{c, f, g, b, \neg a\}$.

3) Reinserting the variables into $L$ will result in the first clauses being violated: $a \wedge b \implies c$. Since $a$ is false, $c$ is false, meaning clause (v) is violated. The algorithm will return "Not Satisfiable"

I am aware that the algorithm appears confusing. Please feel free to ask for clarification.

From comments I now realize that there is no known efficient general satisfiability algorithm. I'm still interested in feedback about my algorithm. Does it work? How does it compare with common algorithms?


texts: Difference between the Cartesian product in set theory and in relational algebra

texts:
What's the difference between the Cartesian product in set theory and in relational algebra?

The Cartesian product in set theory is defined as:

$$A \times B = \{(a, b) \mid (a \in A) \land (b \in B)\}$$

I think this is exactly how it works in relational databases, but Wikipedia tries to make a difference that I don't understand:

$$ R \times S := \{ (r_1,r_2,\dots,r_n,s_1,s_2,\dots,s_m) \mid (r_1,r_2,\dots,r_n) \in R, (s_1,s_2,\dots,s_m) \in S \} $$


texts: What is the meaning of undecidability in Rice Theorem?

texts:
Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable?

As an example the following language is R.E but it contains a non-trivial property

$A = \{x | \phi_x$ is defined for at least one input$ \}$

this language equals to $Empty$ $Complement$ and it is clearly r.e.(m-complete in fact) while non-emptiness property is non-trivial.


texts: per-record timeline consistency vs. monotonic writes

texts:
It seems to me that the per-record timeline consistency as defined by Cooper et al. in "PNUTS: Yahoo!’s Hosted Data Serving Platform" mimics the (older?) definition of monotonic writes. From the paper:

  per-record timeline consistency: all replicas of a given record apply
  all updates to the record in the same order.

This is quite similar to a definition for monotonic writes:

  A write operation by a process on data item x is completed before any
  successive write operation on x by the same process.

Can I conclude that those things are the same, or is there a difference that I misunderstand? Note that the link above also mentions possible copies of data item x, so monotonic write includes replicas.


texts: Why does Patience sorting find the longest increasing subsequence?

texts:
According to Wikipedia (link), patience sort finds the longest increasing subsequence of a given sequence. Lets say the longest increasing subsequence of seq has length correct(seq)

Patience sort works like this:

Parameters: A sequence of integers called seq
Output: A number between 0 and the length of seq. Lets call it patienceSort(seq)
Algorithm (in Python):

def patienceSort(seq):
    piles = []
    for el in seq:
        for i in range(len(piles)):
            # If there is a pile with a strictly greater element on top,
            # place current element on that pile
            if piles[i][-1] > el:
                piles[i].append(el)
                break
        # if there is no such pile, create a new one
        else:
            piles.append([el])
    return len(piles)

What I've understood:

(I) We can guarantee that at every time the top of piles (piles[i][-1]) is ordered in increasing order.

(II) For numbers in the same pile: Numbers are ordered...

(II.1) ... by time (first one in the pile came first)

(II.2) ... by value (first one in the pile has highest value)

(III) The numbers on top of the piles are not necessarily an increasing sequence
within seq

(IV) The right pile is always the latest one that was created

Example for (III):

      37
20    38
30    39
40    40
50    70
pile1 pile2
seq = [50,40,70,30,40, 39,38,37,20]
[20,37] is not an increasing sequence in seq

For each card (which is not on the first pile), you can store a pointer to the top of the pile before when you add it to the pile. This way, you can get an increasing sequence by following the pointers and inverting the list. So:

patienceSort(seq) <= correct(seq)

Question

Why is patienceSort(seq) >= correct(seq)


texts: In Theoretical Computer Science, which one is more important? Computability of a problem or Complexity of a problem?


texts: Natural candidates for the hierarchy inside NPI

texts:
Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems conjectured to be $\mathsf{NPI}$ here.

Ladner's theorem tells us that if $\mathsf{NP}\neq\mathsf{P}$ then there is an infinite hierarchy of $\mathsf{NPI}$ problems, i.e. there are $\mathsf{NPI}$ problems which are harder than other $\mathsf{NPI}$ problems.

  I am looking for candidates of such problems, i.e. I am interested in pairs of problems
  - $A,B \in \mathsf{NP}$,
  - $A$ and $B$ are conjectured to be $\mathsf{NPI}$,
  - $A$ is known to reduce to $B$,
  - but there are no known reductions from $B$ to $A$.

Even better if there are arguments for supporting these, e.g. there are results that $B$ does not reduce to $A$ assuming some conjectures in complexity theory or cryptography.

Are there any natural examples of such problems?

Example: Graph Isomorphism problem and Integer Factorization problem are conjectured to be in $\mathsf{NPI}$ and there are argument supporting these conjectures. Are there any decision problems harder than these two but not known to be $\mathsf{NP}$-hard?


texts: Implement data structure with efficient insert/findKthSmallest operations

texts: I was asked this question by an interviewer. I tried solving it using an array, such that I make sure the array in sorted when I insert. However I don't think this is the best solution. What would be a good solution for this problem?


texts: Best algorithm (Time Complexity) to find Minimum spanning tree of an complete, positive weighted, undirected, graph

texts:
Suppose that we have a complete undirected positive weighted graph $G = \langle V, E\rangle$. What is the most efficient algorithm, in terms of time complexity, to find an MST for $G$?
The best prime complexity I have found is $O(|V|^2)$, and the complexity of the Kruskal algorithm is $O(|E|\cdot \log(|E|))= O(|V|^2 \cdot \log(|V|))$.
Any ideas for how to improve the time complexity so that we get something more efficient than $|V|^2$?


texts: Is every language in PTime also context-sensitive?

texts:
Context-sensitive languages are exactly those that can be recognised using linearly bounded automata, i.e., those in NSPACE(O($n$)). This subsumes all languages that can be recognised in linear time, i.e., DTIME(O($n$)), since you can only use n memory cells in n steps.

However, this leaves open the possibility that some super-linear polynomial time problems are not context-sensitive. Is this likely or even known? Are there examples?

Here are some general facts that one should be aware of:

There are PSpace-complete problems in NSPACE(O($n$)), e.g., TrueQBF. One might think that this answers my question, since PTime is contained in PSpace.
However, not all PSpace-complete problems are in NSPACE(O($n$)). Indeed, we know that there are strictly more languages in NSPACE(O($n^2$)) than in NSPACE(O($n$)) (space-hierarchy theorem). In other words, PSpace is strictly larger than NSPACE(O($n$)), i.e., some PSpace languages are not context-sensitive.
PTime is subsumed by PSpace, but not necessarily by NSPACE(O(n)) (hence my question). Indeed, it seems unlikely that today's answer to my question is "All PTime languages are context-sensitive." If we would know this for sure, then (using 2.) we would know that PTime is strictly smaller than PSpace, which is an open conjecture today.

However, I don't see an immediate reason why there should not be a known example of a non-context-sensitive language in PTime.

Conclusion after reading the answer: We know very little. Mostly, we know $NL\subseteq NSPACE(O(n))\subseteq PSpace$ and $NL\subseteq P\subseteq NP\subseteq PSpace$. It is unclear how $NSPACE(O(n))$ (CSL) compares to $P$ and $NP$. If we could show that $P\subseteq NSPACE(O(n))$, this would show $P\subsetneq PSpace$ (open); if we could show $P\not\subseteq NSPACE(O(n))$, then this would show $NL\subsetneq P$ (open). Both of these open conjectures are expected to be true, which is not of any help for making a guess regarding the answer to my question.


texts: Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?

texts:
I am studying the algorithm of Sollin and we recently studied a lemma:
Let be G a graph which values are diffferent on the edges.

We sort the edges  $e_1,e_2,...e_m$ such as $v(e_i)<v(e_j)$
Every tree of minimal value has at least $e_1$ et $e_2$

Proof
let be A a spanning tree which doesn't have $e_1$
$A\bigcup\{e_1\}$ has a unique cycle
let be $e_i \in$ cycle, $e_i\ne e_1$ then $A\bigcup\{e_1\}-\{e_i\}$ is a tree which value is < $v(A)$ because $v(e_i)>v(e_1)$

I don't understand why would $A\bigcup\{e_1\}$ would have a unique cycle?
Do you have a justification? A graphical example?


texts: Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel

texts:
Given integers $n,m$, I want to find a $m \times n$ binary matrix $X$ such that there does not exist any non-zero vector $y \in \{-1,0,1\}^n$ with $Xy=0$ (all operations performed over $\mathbb{Z}$).  What algorithm could I use for this?

In more detail: We are given parameters $n$ and $m$.  The problem is to determine if there exists $x$ such that $x_{i,j} \in \{0,1\}$, and there does not exist $y\ne (0,0,\dots,0)$ where $y_j \in \{-1,0,1\}$ for all $j$ and for all $1 \leq i \leq m$,

$$\sum_{1 \leq j \leq n} x_{i,j} y_j = 0.$$

(Notice that we require that at least one of the  $y_j \ne 0$ to avoid the trivial solution.)

For example, consider $m=3,n=4$.  Then, expressing $x_{i,j}$ as a matrix $X$,

$$
X=\begin{pmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 \\
\end{pmatrix}
$$

is a valid solution for $m=3$ and $n=4$.

What algorithm can I use to solve this problem?  Can I formulate this as an integer linear programming problem or maybe as a constraint programming problem?


texts:
Given $n$ distinct values $(x_i)_{i=1}^{n}$ with mean $\mu$ and standard deviation $s$, for all $i$, we have $|x_i−\mu| ≤ s \sqrt{n − 1}$.
How does this inequality compare with Chebyshev inequality as $n$ increases?


texts: Statement of the Goldwasser-Sipser Set Low Bound Protocol

texts:
I'm trying to understand the statement of the Goldwasser-Sipser Set Low Bound Protocol as presented in "Computational Complexity: A Modern Approach" by Arora and Barak.
In particular, I'm trying to understand why the following claims yields what we would want:
$S \subseteq \{0,1\}^m$ is a set such that membership can be certified. Both parties know a number $K$. Let $k$ be an integer such that $2^{k-2} < K \le 2^{k-1}$.
Claim: Let $S \subseteq \{0,1\}^m$ satisfy $|S| \le 2^{k}/2.$ Then for $p=|S|/2^k$ we have $p \ge \mathbf{P}_{h \in_{_R} \mathcal{H}_{m,k}, y \in_{_R} \{0,1\}^k}\left[\exists x \in S: h(x)=y \right] \ge \frac{3p}{4}-\frac{p}{2^k}.$
My understanding is that we want:

If $|S| \ge K$ then the verifier should accept (corresponding to the prover finding such an $x$ in the claim) with "high" probability;
If  $|S| \le K/2$ then the verifier will accept with probability at most 1/2.

I'm getting thrown off by a few things here:

the claim assumes that $|S| \le 2^k/2 = 2^{k-1} = 2\times2^{k-2} < 2 K$, so how does this place us in one of the relevant cases?
How do we actually use those left ($p$) and right ($3p/4 - p/2^k$) bounds to conlude what we want?

Overall, I'm understand bits and pieces of this setup, but I'm having trouble seeing how it all fits together. Can someone walk through the logic/algebra here?


texts: Bob has to find Alices hidden gold by questioning yes/no questions

texts:
Suppose that Alice has $n$ places to hide the gold $v_1, ..., v_n$ and that
Bob knows the probability of each place.

Bob has to ask Alice a series of yes/no questions to find the gold.

I have done it this way:

We order the places by probability highest to lowest.
Repeat the following:

Divide them by two so we have two sets High and Low sets
Bob asks whether the gold is in High.
Repeat with the places in the correct set.

My professor told me that we have to get that he questions on average $H(V)$ questions, where $H(V)$ is the entropy.

But with this I have $2.576$, which is close to $H(V)=2.47$ but it's not $H(V)$.

Are there any better ways?


texts: Does this constraint satisfaction problem have a name

texts:
I've been struggling with a particular constraint satisfaction problem, that appears like it should have an easy solution. In fact, I need a very fast solution.

The problem is: I am making a card-playing AI, and at some point I need to guess a plausible solution to the other players hands. Given the history of the game, I can definitely say that some players don't have certain cards .

Put formally: I have a set of elements $S$ (the remaining cards in the game), and the goal is to partition $S$ into a fixed number of disjoint subsets $S_i$, for  $ i \in \{1...n\}$. For each subset, we have a set of elements $A_i$ that they may not have, and a number of elements $N_i$ that this subset must contain. Also, $|S| = \Sigma_i N_i$. Find a partition.

There are a number of extra conditions that could make this problem much easier:

The initial conditions guarantee that there will always be a solution.
All remaining cards are in other peoples hands. There is no deck, and so all other cards have either already been played, or are in my AI's hand.
The number of cards to be distributed is $<24$.
There is always exactly 3 opposing players, i.e. $n = 3$.
For any $i, j$, $abs(|N_i| - |N_j|) <= 1$.

I am convinced that this problem has already been studied and has a name. Does anybody know if it exists? If not, is the problem is simple enough that there is a solution that does not require exponential search?


texts:
I want to find the most optimal algorithm for finding closest ordered pairs and link them.

For example:
Go thru the vector, one by one

For each one set the next according to a set of various conditions

For example, something like:

A B X C Y Z D

First we will link A to B
Then when we have a look at B,
we will link B to C
Next when we consider X,
we will link X to Y
Next when we consider C,
we will link C to D   ... and so on

Currently someone has completed this task with some nested loops that are genuinely sub-par and it completes in O(n^2) time.  Not to mention it doesn't work.  What might be a better algorithm?

Here is what the current algorithm is:

for(i in list)
  while (i and j) is not linked
     increment j
  if j is not the end
     while ++j is not the end
       if link exists (i and j)
       break
     end while
     set link i to j
  end if
end for

I was going to write my own but I have a feeling I've seen this problem before at university and there was a simple solution to it..?  Can anyone point me in the right direction please?


texts:
I am trying to solve the following problem:

For each Turing machine $M_k$ and each string $x$ in $\{$0,1$\}$$^\ast$ let

$time_k(x)$ = $\{$the number of steps executed by $M_k(x)$ if $M_k(x)$$\downarrow$ (halts), and $\infty$ if $M_k(x)$$\uparrow$ (does not halt)$\}$

Prove that the function $T$: $\mathbb{N}$ $\rightarrow$ $\mathbb{N}$ defined by

$T(n)$ = max$\{$$time_k(x)$ | $0$ $\leq$ $k$ $\leq$ $n$, $x$ $\in$ $\{$0,1$\}$$^\ast$, and $M_k(x)$$\downarrow$ (halts)$\}$

is uncomputable.

So far, I have begun my proof by assuming that $T$ is computable. Thus, there exists a Turing machine $M$ such that for all $n$$\in$$\mathbb{N}$, $M$ produces $T(n)$ on its tape. Thus, we must show that we can decide the Halting Problem if $T$ is computable, which in turn lets us know that $T$ is uncomputable since the Halting Problem is uncomputable.

I do not know where to go from there however. Any help would be greatly appreciated. Thanks in advance.


texts: Solving recurrence with logarithm squared $T(n)=2T(n/2) + n \log^2n$

texts:
$T(n)=2T(n/2) + n\log^2(n)$.

If I try to substitute $m = \log(n)$ I end up with

$T(2^m)=2 T(2^{m-1}) + 2^m\log^{2}(2^m)$.

Which isn't helpful to me. Any clues?

PS. hope this isn't too localized. I specified that the problem was a squared logarithm which should make it possible to find for others wondering about the same thing.


texts:
I need help figuring out the runtime of the following pseudocode. I believe it is O(|E| + |V|), but I'm not totally sure...

graphFunction(graph):
     q = Queue()
     for vertex in graph:
         q.enqueue(vertex)
     while q is not empty():
         v = q.dequeue()
         for  every outgoing edge of v:
             edge.weight++
         for every incoming edge of v:
             edge.weight++


texts: Gantt chart for Round Robin Scheduling using only arrival and completion time

texts:
I had the following question in my Operating System 'CPU- Scheduling' assignment-
4 processes A,B,C,D have estimated time of completion of 5,7,9,11 ns each. They are scheduled in a round-robin fashion and the time slice is of 2ns. The processes A,B,C,D arrive at the 0,1,2,3 ns respectively. At what time will the process C  complete? Also what will be the completion time of process C, if Shortest Job First was used instead of Round Robin?
My doubt is- Can we design a Gantt Chart using just Arrival time and Completion time. I referred many books and websites but in all the places the chart was designed using arrival and burst time rather than completion time.
If I assume the question to be straightforward then I don't need a Gantt Chart and can easily get the completion time of C to be 9 in round-robin scheduling. However, calculating the completion time for SJF scheduling will become a mystery. I am guessing the question could be printed wrong yet I am not sure and would like some assurance if it's wrong, else some guidance on how to tackle the above question.


texts: Can Inverse of weights(1/weight,not negation) be used to find the longest path between two points by using dijkstra's algorithm?

texts:
Considering that there no cycles in the graph.

I have seen the posts where the negation of the weights is suggested and to use Bellman-ford. But I was wondering if the inverse is possible.


texts: Language containing all unambiguous grammars

texts:
Suppose $L$ is the language of the unambiguous grammars. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar.

Considering that deciding whether a context-free grammar is ambiguous is non-decidable, would it be correct to say that $L$ exists but is not recursively enumerable?


texts: What is the smallest time/space complexity class for which no sparse language is hard?

texts:
For example, whether there exists $\mathsf{PSPACE}$-hard sparse language an open problem, as it is not yet known whether polynomial hierarchy collapses.
But is it a solved problem for larger complexity classes like $\mathsf{EXP}$ or $\mathsf{PR}$? What is the smallest complexity class (that is larger than $\mathsf{PSPACE}$) for which it is a solved problem?


texts: Decoding a binary linear code given its generator matrix

texts:
Let $C$ be the binary linear code with the following generator matrix

$G= \begin{bmatrix}
    1 & 1 & 0 & 1 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 & 1 & 0 & 0  \\
    0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix}$

I need to decode the received word $r$, $\begin{pmatrix} 1 & 1 & 0 &0 & 0 &1 &1\end{pmatrix}$.

I am really strugggling with this. I know a message $m$ is encoded as $mG$.

So $mG$=$\begin{pmatrix} 1 & 1 & 0 &0 & 0 &1 &1\end{pmatrix}$.

I have tried doing this by eye but couldn't find a single $m$ that I could multiply $G$ by to give me $r.$ Is there another method? Also I know that there must be $2^4=16$ codewords and when I wrote them out this one wasn't in them? Not sure if that helps or maybe I did that wrong?


texts:
I've heard that the functions that are definable in simply-typed $\lambda$-calculus is the class of extended polynomials.

However, it is still not clear to me what exactly is extended polynomials. Could someone explain that to me? Some pointers would be good as well.

Thanks.


texts:
If $X \sim \mathcal{O}(\log n)$, then $e^{-X} \sim \mathcal{O} (?)$

Is this a valid question to ask?


texts: How to design context-free grammars generating the languages with twice as many a’s as b’s?

texts:
The problem is designing context-free grammars generating the following languages.

The set of strings over the alphabet Σ = {a, b} with twice as many a’s as b’s.
I found a solution but I don't know how to get this.

S → SS | aaSb | bSaa | aSbSa | $\epsilon$


texts: How approximable is time-bounded Kolmogorov Complexity?

texts:
Given a Turing Complete Language, the optimization problem would be: Given inputs x and S, where x is a finite binary string and S is a limit on steps, find the shortest program in that TC language that outputs the string x in less than or equal to S steps. (With S being in unary.)

My question is how approximable this definition of time-bounded KC is in terms of the NPO classes such as PTAS, APX, log APX, and so on.

I've been searching and have only been able to find info on KC itself and little info on resource-bounded KC as a decision or optimization problem.


texts: Voronoi Diagram Drawing Variations and Charateristics

texts:
I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays.

Similarly how can we draw the Voronoi diagram for the following:
(a) A set of lines and points?
(b) A set of disjoint line segments?
(c) A set of line segments forming a convex polygon?
(d) A set of circles (non intersecting and no circle contains another)?

For each of these sets of objects, how can we describe the shape of the boundary pieces that form the Voronoi diagram.

I believe that the distance between a point and another object is the smallest distance between the point and any point of the object.


texts: A version of the longest simple cycle problem - NP-completeness reduction proof

texts:
I've been learning about proving NP-completeness via reduction, and came across the following problem:

Prove via reduction the following: whether a graph $G = (V, E)$ contains a simple cycle using $\ge \frac{1}{2}$ of the vertices is a NP-Complete problem.

The first part is to show that the above problem is in NP. That's simple enough, since a solution is verifiable in linear time by just traversing through the vertices to ensure they form a cycle, and that the no. of vertices in the solution set are $\ge \frac{1}{2}$ of the total no. of vertices.

As far as polynomial-time reduction...my thoughts so far are that you can probably reduce Hamiltonian circuit problem to it, but I'm unsure how to proceed. I suppose that, given the original graph $G$, you could first check whether the entire graph is a Hamiltonian circuit. Then if not, you could delete a random vertex from $G$ (there are a total of $|V|$ ways of doing this), and check for Hamiltonian circuit again...then if not, delete two vertices from G (there are $\binom{|V|}{ 2}$ ways of doing this), and check again for Hamiltonian circuit...and so on, all the way down to deleting $\frac{|V|}{2}$ vertices from $G$.  But reducing it this way sounds cumbersome, and may even be an exponential-time reduction.

Any help would be appreciated.


texts: What the length of instructions on these processors will be?

texts: Let's say we have two computers with identical ISA, but different size of word in main memory. One is 32 bit and the other 64 bits. So will it be identical length of instruction, different, depends on memory or depends on cache memory and why ?


texts: How can an existential type be defined in terms of universal type?

texts:
In Types and Programming Languages by Pierce,  how does the following achieve the definition of an existential type  in terms of universal type, by polymorphic version of Church encoding of pairs?

  24.3 Encoding Existentials

  The encoding of pairs as a polymorphic type in §23.4 suggests a
  similar encoding for existential types in terms of universal types,
  using the intuition that an element of an existential type is a pair
  of a type and a value:

{∃X,T} := ∀Y. (∀X. T→Y) → Y.

  That is, an existential package is thought of as a data value that,
  given a result type and a continuation, calls the continuation to
  yield a ﬁnal result. The continuation takes two arguments—a type X and
  a value of type T—and uses them in computing the ﬁnal result.

To complete the quote, the polymorphic version of Church encoding of pairs of numbers is given in Exercise 23.4.8 (p349 p546):

pairNat = λn1:CNat. λn2:CNat.
λX. λf:CNat→CNat→X. f n1 n2;
fstNat = λp:PairNat. p [CNat] (λn1:CNat. λn2:CNat. n1);
sndNat = λp:PairNat. p [CNat] (λn1:CNat. λn2:CNat. n2);

which is further generalized to pairs of elements of any types, on p352

  we use the abbreviation Pair X Y (generalizing the PairNat type from
  Exercise 23.4.8) for the Church encoding of pairs with ﬁrst component
  of type X and second component of type Y:

Pair X Y = ∀R. (X→Y→R) → R;

  The operations on pairs are simple generalizations of the operations
  on the type PairNat above:

> pair : ∀X. ∀Y. X → Y → Pair X Y
fst : ∀X. ∀Y. Pair X Y → X
snd : ∀X. ∀Y. Pair X Y → Y

Thanks.


texts: closure property on Recursively enumerable language

texts:
How to prove that recursive and recursively enumerable language is closed under reversal?

Why recursively enumerable language is not closed under set difference? [But intersection of recursive and recursively enumerable language is recursively enumerable]


texts: Existence of NP problems with complexity intermediate between P and NP-hard

texts:
Assuming P!=NP, there is a result that there are decision problems intermediate between P and NP-complete. That is, the class NP cannot be a union of two disjoint subsets: P and NP-complete.

I could never quite understand the proof of the above result. The proof I saw in a textbook was starting with the assumption that one can enumerate all P and NP-hard problems, and then proceeding with a construction of a function that didn't fit in either. However, this construction seemed a bit fishy to me; in particular, the assumption that one can start with enumerated set of problems in a particular class, the NP.

Could you refer me to a clear self-contained proof of the statement in the 1st paragraph? More generally, what would be a good reference for proofs of such results?


texts: A question regarding definition of Deterministic Subexponential Time (SUBEXP)

texts:
First Look at the definition of SUBEXP from Complexity Zoo:

SUBEXP: (Deterministic Subexponential-Time)
The intersection of DTIME($2^{n^\epsilon}$) over all $\epsilon$>0. (Note that the algorithm used may vary with $\epsilon$.) or it can be written as: SUBEXP = $\bigcap_{\epsilon>0}$DTIME$(2^{n^\epsilon})$.

So, I bring the definition of EXP which is:

EXP = $\bigcup_{k\geq 1}$DTIME$(2^{n^k})$

The definition of EXP is clear, since it includes all polynomial of n to the power of 2. (e.g. $2^{n^{30}}$ or $100^{n^{99}}$ etc.)
First question: what is domain of $\epsilon$? I guess it is between 0 and 1 but it didn't specify in the definition. Is it usual that when we have $\epsilon$ then it means between 0 and 1.
Second question: Now, in case of SUBEXP, it is not clear how the definition is about the intersection? I mean, Shouldn't be written as following: $\bigcup_{1>\epsilon>0}$DTIME$(2^{n^\epsilon})$. For example by definition above what is the intersection of: $2^{n^{0.01}} \bigcap 2^{n^{0.02}} ?$
Third question: There are two definition of SUBEXP in wikipedia, Is there definition that take over all subexponential or we don't since this is why we have two definitions.
Thank you!


texts: What makes Bayesian Networks decomposable into joint trees?

texts:
Given a Bayesian Network $N$, one can build a junction/joint tree $JT$ over $N$ by applying series of steps (namely, moralisation,triangulation..etc). Then we can use $JT$ to answer queries over $N$.

My question is: what makes BN decomposable into $JT$? The structure (along with the CPTs) must exhibit certain conditions otherwise any graphical model is decomposable.


texts: Is Event Calculus applied for program verification?

texts:
Recently I've read wiki page about Robert Kowalski (Prolog author) and stumbled upon interesting concept of Event Calculus. The wiki article mentions only few applications of this logical language. I am wondering if any tools are using EC for program verification (similarly to Effect Systems).

Is there any technology (language, library) applying Event Calculus for program verification?


texts: In top-down parser how do you match a product $A \rightarrow a_1 | a_2 | ...$, $a_i$s terminals

texts:
One procedure for table-driven top-down parsing is given here:
https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html

This gives for matching the input the lines:

else if NextInputSymbol == top then
    /* Match terminal symbol in input */
    Pop(stack)
    /* Get next terminal symbol in input */
    scanner(NextInputSymbol)

Which seems to be assuming that every product leading to terminal symbols has only one terminal.

But what if the product leading to terminals is of the following form:
$$A \rightarrow a_1 | a_2 | ...$$
where $a_i$s terminals.

How do you match for such product?

Merely by trying out each terminal symbol?
But reading them all to the stack would cause some overhead for keeping account of how many terminals symbols were added?

In predict table form:


texts:
We know $P\subseteq PH\subseteq PSPACE\subseteq EXP\subseteq NEXP$.

Is it known or believed that $\Delta_2^{exp}=EXP^{NP}\subseteq NEXP=\Sigma_1^{exp}$ and/or $EXP^{PH}\subseteq NEXP$?
Does $NP=coNP\iff NEXP=coNEXP$ hold?

Note $NEXP=coNEXP\implies \Delta_2^{exp}=\Sigma_1^{exp}$?


texts: What algorithm could I use to find the largest set of disjoint members from a set of subsets of a set?

texts:
I've written a political quiz based on data from the public whip.  They group politicians' votes by policy; each vote can belong to many policies.  There are too many policies for me to ask a question for each one, and anyway some are duplicates and some policies' votes are subsets of other policies.  In the past, I've manually chosen a subset of policies to use in my quiz try to maximise the number of votes included without double-counting any, but I'm worried that that may introduce my biases into what is supposed to be as neutral as possible a quiz.  So I'd like to find the set of policies which maximises the number of votes included without counting any of them twice.

Is there a known algorithm I could use to do this?  I've seen similar questions elsewhere on this site but they generally seem to involve sets of intervals or geometric shapes.


texts: Path planning agent in a grid with compulsory states to visit with Reinforcement Learning

texts:
Is it possible to make a Reinforcement Learning agent for path planning in a 2D grid where visiting certain intermediate states is mandatory?

Please give an insight if it is indeed possible as to how I can proceed about it or give some reference.

I mean how to achieve it. I have tried giving more rewards to each of the intermediate states (grid locations in our case) that are mandatory to visit. But I want to visit certain states in a certain order. For example, Let's say S1 S4 and S5 are intermediate states that are mandatory to visit in a given order, S0 is the initial state and SG is the goal state. Then S0 -> SI -> S1 -> SI -> S4 -> SI -> S5 -> SI -> SG must be a sequence where SI = (zero or more intermediate states). The method mentioned above will make an agent visit given states but not necessarily in the order that I want.


texts: Proof that (x-y)(x+y) is more accurate than x²-y²

texts:
I was carrying on my reading of What Every Computer Scientist Should Know About Floating-Point Arithmetic but got stuck on the proof of Theorem 2 (page 34).

At some point it says:
\begin{align}
(x \otimes x) \ominus (y \otimes y) & = \left[x^2(1 + \delta_1) - y^2(1 + \delta_2)\right](1 + \delta_3) \\
& = \left[(x^2 - y^2)(1 + \delta_1) + (\delta_1 - \delta_2)y^2\right](1 + \delta_3) \\
\end{align}
I'm ok with the rewriting, but I don't understand the argument that:

  When $x$ and $y$ are nearby, the error term $(\delta_1 - \delta_2)y^2$ can
  be as large as the result $x^2 - y^2$.

This doesn't make much sens to me right now. I understand that if both quantities are close to each other, then the relative error is close to $1$. But not why they should be close to each other.


texts: How can I show a linear languages are closed against concatenating with regular ones?

texts:
This was given as a homework problem but I have already submitted the assignment.  I'd like to resolve it at this point for my own satisfaction.

Given that $L_1$ is a linear language and $L_2$ is a regular language, show that $L=L_1L_2$ is a linear language.

Recall that a linear grammar $G=(\Sigma, V, P, \sigma)$ has productions $A\to yBz$ for some $y,z \in \Sigma^*$ and $A,B \in V$.

I use the theorem that every regular language can be represented by a right linear grammar.

Then I use the theorem that every right linear grammar is the reverse of a left linear grammar (being a little careful about what I mean by reverse)... $L(rev(G))=rev(L(G))$...

Next each left linear grammar is the reverse of a regular language, but the reverse of a regular language is regular, so left linear grammars also represent regular languages.

So our productions in $L_2$ are of the form $x \to Ca \mid a$ for some $C \in V_{L_2}$ and $a \in \Sigma_{L_2}$.

Now on to the show...

What we are looking for is $L = L_1.L_2$, $L$ is linear (to show).

So this has the form $S \to yBzCa \mid yBzaa$

So far so good, the second production is linear and within our expectations for set inclusion.

I'm having a devil of a time reducing $yBzCa$ however ...

If I introduce $V\to BzC$ that linearizes $S$ but $V$ is not linear ...

If I give $T\to z$ to get $V\to BTC$ I'm not much better off

If I use $V_1\to Bz$ (ok linear!) but then $V\to V_1C$ (not linear)

What is the piece of the puzzle I'm missing?

I have a suspicion that my woes are because I failed to have a production that is $B\implies^*a$ for some terminal $a \in \Sigma_{L_1}$ but I haven't observed that in the definitions thus far... and further unless B only goes to a terminal I'm in the same mess (if $B\to t$ where $t \in \Sigma_{L_2} \bigcup {\epsilon} $ then I think I'm finished but how do I justify it?


texts: Merge Sort meaning of a bit part of code

texts:
I am studying this part for a merge sort implementation:

void mergeSort(int arr[], int l, int r) {
if (l < r)
{
    // Same as (l+r)/2, but avoids overflow for
    // large l and h
    int m = l+(r-l)/2;

    // Sort first and second halves
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);

    merge(arr, l, m, r);
}}

What is the meaning of:

    // Same as (l+r)/2, but avoids overflow for
    // large l and h
    int m = l+(r-l)/2;

in the code?
Why can't I use (l+r)/2? (I didn't understand the comment)


texts: PCP when upper and lower words have different length

texts:
The Post correspondence problem (PCP) asks, given two sets of words $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$ over the same alphabet, whether there are indices $i_1,\ldots,i_s \in \{1,\ldots,n\}$ and $j_1,\ldots,j_t \in \{1,\ldots,m\}$ such that
$$
a_{i_1} \ldots a_{i_s} = b_{j_1} \ldots b_{j_t}.
$$
It is well-known that PCP is undecidable.
What happens if we restrict $s \neq t$? Does the problem become any easier?


texts: Simplifying circuits using boolean algebra

texts:
I am having a lot of trouble simplifying my circuit using boolean algebra. I am very new to this and any explanation would be greatly appreciated.

I have y'+z+w'x+wx'
I feel like I could use DeMorgan's law and somehow omit the last 2 terms but when I run my circuit I cannot seem to get the same result.
Also for clarification, can you apply deMorgan's law to only one term, such as to wx' to get
y'+z+w'x+(w'+x)? Or am I going about this the wrong way?

Once again thank you so much.


texts:
I had read about the various functionalities of system calls recently in one of my coursebooks and about how they are used to allocate memory for new processes. The book didn't specify whether it was possible to combine multiple memory allocation requests within a single system call.
So I asked one of my teachers and they said that it was indeed possible.
I feel that this would probably decrease the system's performance in some way but I cannot seem to give a concrete reason for the same.

Could someone explain why the performance drops in this case?

Thank you for your time.


texts: Counting frequencies of Element in an array

texts:
Given an array of size $N$. I need to find the count of values in range $[L, R]$ which are repeated at least three times in successive positions (i.e., the value occurs contiguously three times).

For eg-
\begin{align*}
    A&= 1,1,1,2,2,1,5,1,1,2,2,2,5,5 \\
    L&=0,\ R=3\,,
\end{align*}
the answer would be 1 (1,1,1) and 2 (2,2,2).

I tried it by doing the following:

  answer = 0
  count[] = 0
  for i in {l..r}:
    count[array[i]]++
    if count[array[i]] == 3:
      answer++

But this will count frequencies all over the range and not just the contiguous ones. So the answer will include $5$ as well where as it shouldn't.

How do I treat any element that starts again after some other integers come in between to be different (like here I need to treat $5$'s count differently) and consider it again for it be $\geq 3$ ? Like can I hash them somehow?

Update :Logic being same, some modification in code. I shift the $L,R$ as the function is called multiple times and increase and decrease the count.

add(position):
  count[array[position]]++
  if count[array[position]] == 3:
    answer++

remove(position):
  count[array[position]]--
  if count[array[position]] == 2:
    answer--

currentL = 0
currentR = 0
answer = 0
count[] = 0
for given L,R
  // currentL should go to L, currentR should go to R
  while currentL < L:
    remove(currentL)
    currentL++
  while currentL > L:
    add(currentL)
    currentL--
  while currentR <= R:
    add(currentR)
    currentR++
  while currentR >R+1 :
    remove(currentR)
    currentR--
  output answer

I need to calculate for many pairs of L,R .So I need an efficient algorithm.
The above algorithm seems to do so.

But How do I differentiate the contiguous triplets here ?


texts: Is there a fpt reduction of a NP-hard problem towards a fpt parameterisation $K'-D' \in FPT$?

texts:
Question
While trying to search for a (example of a) NP-hard problem that fixed-parameter reduces to another NP-hard problem that is known to be fixed parameter tractable, such as k-Vertex Cover, my search results are "poluted" by papers establishing $W[1]$ hardness through parameterized reductions.
It is stated in numerous sources  that if one can complete a fpt reduction from NP-hard problem $K-D$ to the parameterization $K'-D'$ of another NP-hard problem, where $K'-D'$ is FPT, then $K-D$ is FPT as well.
But I am experiencing some difficulties finding a single example of such a parameterized reduction. Hence I would like to ask:
Does there exist a fixed-parameter tractable reduction of a parameterisation $K-D$ of a NP-hard problem towards a fixed-parameter tractable parameterisation $K'-D' \in FPT$? (Where $D\neq D'$)
Doubts

Most likely my search queries are not good enough, but I do not know how to verify this without evaluating all information, developing some increadibly difficult proof, or an authoritarian input. The first two options are currently considered unfeasible by me. This is my third option.
I am aware that it is generally more easy to show something is difficult~ something is not FPT (establishing non-trivial $W[1]$ hardness), than it is to show something is (relatively) easy (showing something is FPT). However since some problems are already shown to be FPT, such as $k-Vertex Cover$, $k-Max Cut$, $k-Subset Sum$ etc. I would expect at least some parameterized reductions from an NP-hard problem towards a parameterization that is shown to be FPT. So most likely, I need to search more effectively.


texts:
Let $\Sigma=\{0, 1, \#\}$.
Is the following language regular; context-free but not regular; or not context-free?
Justify your answer
$$L=\{x\#y :\ x, y \in\{0, 1\}^∗\text{ and }\operatorname{bin}(x) + 1 = \operatorname{bin}(\operatorname{rev}(y))\}$$


texts: Does programming language detection need more input than natural language detection?

texts:
I wonder which one of the two needs a larger input to achieve a decent accuracy:

programming language detection or natural language detection?

More details:

Definition of Language detection:

  In natural language processing, language identification or language
  guessing is the problem of determining which natural language given
  content is in. Computational approaches to this problem view it as a
  special case of text categorization, solved with various statistical
  methods.

The question I was asking can be written bit more formally as: let $x$ be a substring from some text $X$ written in natural language, and $y$ a substring from some source code $Y$ written a programming language. Assume a $X$ and $Y$ are each written in one language only (natural language or programming language).

Let $f(X)$ be the size of $x$ so that on average (i.e. trying on a bunch of different X) I correctly predict the language with accuracy $p$. Does $f(X) < f(Y)$ or $f(X) > f(Y)$ ?


texts:
Let $L$ be the language of all the words with the shape $<M_1,M_2,w>$ such that $M_1,M_2$ are turing machines that accepts $w$, show that $L$ isn't decidable.

I thought to use reduction from $L_{TM}=\{<M,w>\mid M \text{ accepts } w\}$

how can I defined the function $f$ ?


texts: Does all derivation trees generated by context free grammar in cnf form can be recognized by buttom up tree automata?

texts:
G is a context-free grammar in Chomsky normal form.
we define L(G) to the set of all derivation trees that formed by G.
Is it possible to create a non-deterministic bottom-up tree automaton that will accept L(G) exactly?
if so, how to construct such automaton?
I think it's true, so I'm trying to construct the automaton but having hard time to define specifically the transition function.
hope to get help.


texts: Problems that are Cook-reducible to a problem in NP $\cap$ co-NP

texts:
Let $\mathcal{A}$ be a problem in $\text{NP} \cap \text{co}$-$\text{NP}$.

Now assume we can reduce another problem $\mathcal{B}$ to it using Cook reduction.

What conclusions can we draw about $\mathcal{B}$? Does this question even make sense?

I'm asking because from what I understand Cook reductions differ from Karp reductions (for example, $\text{NP}$ cannot be distinguished from $\text{co}$-$\text{NP}$).
I'm pretty confused and can't seem to really understand the properties of Cook reductions. Any good reference about the topic would also be appreciated!

I hope this question is not too basic, but I was not able to find anything about it.


texts: Which sorting algorithm is most efficient to 'continuously' sort a vector again and again?

texts:
I have an uncommon use case

I have a vector, which contains a fixed number of taxi's real-time fees (the red/green number that keeps bumping up when you sit in the back).

This vector is continuously updated by message sent back from taxis. I need to find the top 10 taxis every time when there is an update.

if I only need to do this once, then std::sort() or std::partial_sort would easily solve the problem. However, since the vector is largely the same after only a few updates, the sorting result from step T should be largely the same as sorting result of step T+1

I am wondering if the std::partial_sort will be 'smart' enough to 'incrementally' sort the vector, rather than start-over again from scratch.

Can anyone share any ideas here?

Thanks!


texts: Can the turing machine accept these type of languages in O(n)? or better? $L = \{a^n b^n c^n ... d^n | n > 0\}$

texts:
$L = \{a^n b^n c^n ... d^n | n>0 \}$

so for example $L = \{a^n b^n | n>0 \}$ , $L = \{a^n b^n c^n| n>0 \}$ and such

can the turing machine accept these in O(n)? if yes then what about a better time complexity like O(logn) or O(1)?

my take on this is: yes because we can use n number of tapes and we go through all of them word by word altogether, but a book i was reading said the best time is $O(n^2)$ so i got confused, maybe it was referring to standard turing machine but idk

so my question is this :

can a turing machine do this in O(n) ?
if yes, then is there a better time complexity?


texts: i was trying to understand the difference between programmed I/O and interrupt driven I/O can anyone show me a good read or explain the above concept it is not given in layman words anywhere please help


texts: IP Programming - objective function ist not a function BUT a table

texts:
Here is a short description of my problem:
Part of my objective function is not a regular function. Instead it's a table.
You can see a short extract here:

So if the height is smaller or equal to 300 and the length is  between 301 and 345 (including 345) the price is p2.
My first idea was to create a boolean variable:

So i can add sth like this to my objective function:

Next step is to create two other boolean variables, one for, wenn the height is matching row r, and one for the length:

So when both of them are 1, y_r is also 1:

But how do i create constraints that can switch h_r and l_r to 1 if they are fitting the row r ?
I found a smiliar question here, but its not quite it. I´m not sure, if I have upper and lower bonds and what they are if so.
Thank you for your help!


texts: Can this Arrow-Ring puzzle be encoded as an integer programming problem?

texts:
I would like to write a solver for these kind of Arrow-Ring puzzles.  However, I can't encode all the constraints correctly.

I noticed that Sudoku can be solved using integer programming and I am hoping it can be done for this kind of puzzle as well.  Let's take a look at the rules:

  Draw a line to make a single loop.
  Lines pass through the centers of cells, horizontally, vertically, or turning.
  The loop never crosses itself, branches off, or goes through the same cell twice.
  The numbers show how many black cells there are in the direction of the arrow.
  The loop does not pass through the black cells or the cells with numbers, and black cells cannot touch horizontally or vertically.

The first constrant seem the most difficult, that we should require a single closed loop.  And I wonder if integer programming is even the best way to solve these, but it's a start.

The third constraint (with numerical hints) is the most clear and for simplicity, they could also be replaced by black squares.  However, if you already know how to encode these as integer programming problems, go for it.

Lastly, are there other algorithms that are efficient for finding loops in graphs with constrants?  Wikipedia suggests this could be a Hamiltonian Path or an SAT problem.


texts: Can CNF with an input string be evaluated in logarithmic space?

texts:
I have been trying to solve satisfiability of

{$<c, w>$ | $c$ is a CNF and $w$ is a binary string which satifies the $c$}.

As first looks to me, it is satisiable in linear time ($O(n)$) since $w$ has lenght $n$.

I tried thinking about whether the space complexity of this problem can be reduced to logarithmic order. But couldn’t end up with an acceptable reason so far. Well, my first thought is the following:

Considering that CNF $c$ is composed of conjuction of some clasuses, it’s possible to write every clauses’s result (0 or 1) to the working tape and after reading the entire string, evaluate those 0’s and 1’s (which correlates with the CNF’s clauses). But this won’t result in a logarithmic space complexity anyway and I think it would be of $O(n/k) = O(n)$ where $k$ is the number of clauses.

Is there an optimize way of solving this in logarithmic space?


texts: General structure of solutions to 3-SAT circuits

texts:
Certain special forms of the SAT problem have solution sets of a special form. For example, given any three solutions to a 2-SAT circuit, their bitwise median is also a solution. Likewise, given any three solutions to an XOR-SAT circuit, their bitwise XOR is also a solution. Lastly, given any two solutions to a HORN-SAT circuit, their bitwise AND is also a solution.

Does there exist a similar situation for 3-SAT, where given some subset of solutions, one can somehow generate additional solutions?

If not, does there exist a related SAT problem that 3-SAT can be reduced to, and hence which is also NP-complete, which have solutions of the form specified? For instance 1-in-3 SAT, or exactly-3-SAT, or NAE-3-SAT, or etc.


texts: Prove that any subtree in a red-black tree has at least $2^{bh(x)} -1$ internal nodes

texts:
I'm reading the book Introduction to Algorithms. In the book, in the initial step of proving that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$, they prove that any subtree rooted at any node $x$ in a red-black tree has at least $2^{bh(x)} -1$ internal nodes. However I couldn't wrap my head around this proof.
They do an induction where this holds for the base case when $x$ is a leaf by $2^{bh(x)}-1 = 2^0 - 1 = 0$. However, when they do the induction, they say that  a child of node $x$ has at least $2^{bh(x)-1}-1$ internal nodes (by the way isn't the correct way to put is to start with subtree rooted at a child of node $x$...?). This part confuses me a little bit, is it too trivial to say that it has $2^{bh(x)-1}-1$ nodes given that $bh(x)$ is the black-height (the number of black nodes on any simple path from a node not including itself), or is this related to the rules of the red-black tree which are:

Every node is either red or black.
The root is black.
Every leaf (NIL) is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.


texts: RGBD alignment without explicit transformation between RGB and depth

texts:
I have a set of RGB-D scans of the same scene, corresponding camera poses, intrinsics and extrinsics for both color and depth cameras. RGB's resolution is 1290x960, depth's is 640x480.

Depth is pretty accurate, but still noisy, the same with camera poses. However, both intrinsics and extrinsics are not very accurate: for example, intrinsics does not introduce any distortion terms, while images are definitely distorted. Extrinsics tell that both cameras take place exactly at the same point, since they are just identity matrices. It could be decent approximation though.

When I try to compute a point cloud from a frame by downsampling RGB, unprojecting depth, transforming it with RGB extrinsics and projecting with RGB's intrinsics, it looks like RGB frame is shifted by a few cm from depth - for example, an object's border could be colored as background.

One might assume that such artifacts could be eliminated by aligning depth to RGB with improved extrinsics. Is there a way to estimate more accurate transformation between RGB and depth in such scenario?

I'm familiar with pretty relevant question, but there you have required Rt matrix for both cameras.

In case of well-performing monocular depth estimation, one could align two point clouds (computed from depth and estimated from RGB) directly and determine required transformation.

Am I missing something and there is well-known approach for this problem?


texts:
I'm not sure which StackExchange community is the correct place to ask this so I'm trying this one.

I want to write a code that generates random brick wall type textures. Similarly to what, for example, this commercial software does: http://www.vizpark.com/shop/walls-and-tiles/ .

So far I've thought at least three types of brick wall textures I would like to generate:
1) Periodic and user-defined pattern with one or more predefined brick types (bricks can be different shape an size). This is the simplest case.
2) Completely random pattern with predefined brick types
3) Completely random pattern with random sized bricks.

This is pretty much a mathematical problem that could be rephrased as: what is the way to fill a predefined area with certain shapes (either random or predefined) without leaving gaps?

I would assume that people have thought about this type or problems before, but I don't know how to search for it. I'm not looking for a conclusive answer, but would appreciate links to articles, etc. discussing different variations of this or related problems.


texts:
In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task needs to be assigned to exactly $m$ or $m+1$ agents.

It is guaranteed this this is possible: the segment $\left[ |A|n, |A|(n+1) \right]$ intersects the segment $\left[ |B|m, |B|(m+1) \right]$.

Each agent-task combination yields a profit, and I want to maximize the profit.

Is this a special case of one of the known problems? How can this be solved? If not practical for n=100,000, what are good approximations and what is their complexity?

 Not a comp.scientist, but have done the basic research. Please excuse me if I've overlooked anything obvious.


texts:
This came from a picture of something that I'm supposed to make, and I can't find it in the program I'm supposed to use (LogicWorks). It looks like it 'not's only one of its inputs, but that doesn't make sense because that input comes from a not gate (not pictured here); it would make more sense for this part to be no gate at all, just two connected wires.

It would be helpful to say what this is called and/or what it does.


texts: List of all possible reasoning tasks - satisfiability and theorem proving only?

texts:
What is the exhaustive list of reasoning tasks? As far as I can understand, then any logical reasoning reduces to 2 tasks only: 1) satisfiability problem (finding the assignment of the variables) and 2) theorem proving (deducing general statement from the other statements).

https://en.wikipedia.org/wiki/Logical_reasoning lists 3 types of reasoning: 1) deductive; 2) inductive; 3) analogical. But, as far as I understand, then each of those types reduces to some methods/heuristics of forming some statements and again - in the final step one of two reasoning tasks is applied - SAT or theorem proving.

Logic programming in essence if SAT problem as well (at least for stable model semantics/fixed poing semantics): one compiles the list of implicational statements and then tries to find the assignment of variables under which no internal dynamics happen further.

So - are there only those 2 reasoning tasks - SAT and theorem proving? Of course, there are many logics in which those tasks can be completed, but that is other problem, see, e.g. https://kwarc.info/people/frabe/Research/rabe_howto_14.pdf and https://uniformal.github.io/

The question is important when one tries to implement cognitive architecture (https://en.wikipedia.org/wiki/Cognitive_architecture and http://bicasociety.org/cogarch/architectures.php) - one should be sure about the exhaustive list or reasoning tasks to certify that some implementation achieves some generality.

My question is of even more important when one considers neural networks. One can ask - what is the exhaustive list of reasoning tasks that neural networks should be able to do? Of course, generally there are evidence about Turing completeness of neural networks, but my question concerns the cognitive/reasoning subset of general computations.


texts: Are there existing extensions to behavior trees that fascilitate node communication?

texts:
I've been looking into behavior trees, but I cannot find a lot about them. The Wikipedia page pretty much only mentions sequence and selector nodes.

I have found implementations that also provide memory selector, memory sequence, and parallel sequence, as well as some decorators like inversion and repetition.

I found some papers that discuss some form of a "weighted" selector/sequence that queries its children for their utility/probability. This can also be used in machine learning to dynamically adjust those weights.

What I have not yet found much about is communication between nodes.
Some implementations use a shared "blackboard" where nodes can write values, but this seems rather clumsy, as it creates a huge lookup table that tightly couples different nodes.

I've been thinking more in terms of sending messages to the next node.
I think the bulk of the shared state is a condition/action providing a specific value to the next action (rather than just success).

Has there been any research in this area? I was not able to find anything.
I'm also curious to hear about other useful extensions.


texts: What is a regular expression that matches all strings over the alphabet except a particular substring?

texts:
I've come across this problem in my studies, and I've abstracted it to the more general case here.

Given a finite alphabet, what is a regular expression that matches all strings over the alphabet, except one particular finite substring?

As an example:

Given $\Sigma = \{a, b, c\}$

What is a regular expression that matches all of $\Sigma$ except the substring $
ba$?

What I really want is simply $\Sigma^* - ba$.


texts: How does machine learning relate to artificial intelligence?

texts:
For example, is it a subset?

Are they two separate fields in Computer Science?

I have hear conflicting information: one professor said they are synonyms. However, in the courses taught at Stanford CS they are two distinct classes:

CS221 (Artificial Intelligence)

and

CS229 (Machine Learning)


texts: Weighted Average of Multi-Output Neural Networks

texts:
[1] discusses how to construct an ensemble of neural networks by giving each network a certain weight $\alpha_i$:
\begin{equation}
f_\mathrm{GEM}(\boldsymbol{x}) = \sum_{i=1}^N \alpha_i f_i(\boldsymbol{x})
\end{equation}
where each $\alpha_i$ is obtained using a correlation matrix which is defined in the following way:
\begin{equation}
C_{ij} = E[m_i(\boldsymbol{x}) m_j(\boldsymbol{x})]
\end{equation}
where $m_i(\boldsymbol{x}) \equiv f(\boldsymbol{x}) - f_i(\boldsymbol{x})$, with $f(\boldsymbol{x})$ being the target function and $f_i(\boldsymbol{x})$ being the output.

I was wondering how should one compute $C_{ij}$ when the neural network has multiple outputs. Would one firstly calculate $\boldsymbol{m}_i(\boldsymbol{x}) \equiv \boldsymbol{f}(\boldsymbol{x}) - \boldsymbol{f}_i(\boldsymbol{x})$ for all examples and then compute $C_{ij} = E[\boldsymbol{m}^T_i(\boldsymbol{x}) \boldsymbol{m}_j(\boldsymbol{x})]$? I tried doing that (with MNIST data) but the accuracy was not better than when taking a simple average of all the networks in the ensemble. I would appreciate any help on this.

[1] M. P. Perrone and L. N. Cooper, "When networks disagree: Ensemble methods for hybrid neural networks," in Artificial
Neural Networks for Speech and Vision. Chapman and Hall, 1993, pp. 126-142.


texts: Has this generalization of Turing machines studied before?

texts:
Introduction

Hello, I'm designing a generalized model of Turing machines for a formalization in MIZAR. Mizar needs some concrete objects to work with, so I spent some time figuring out how the "tape" of a Turing machine could be defined since that part is usually left out when introducing Turing machines.
After some thinking I concluded it would be best to use graphs, so I define a "Turing Space" $T$ as a function from an cardinal $C$ to graphs. A position $p$ in the Turing Space is then defined as a function from the cardinal into the vertex sets of these graphs, so that for $c\in C$, $p.c$ is a vertex of $T.c$. From this basis one can built transition functions and so forth.

Examples

Given a double ray (a path graph that is infinite in both directions) $R$ and a positive integer $k$, the function $f_k:k\ni i\mapsto R$ (defined on $\{0,\ldots,k-1\}$) would be a Turing space describing the bands of a $k$-band TM.
Given a positive integer $d$, set $E_d:=\{\{a,b\}:a,b\in\mathbb{Z}^d,\sum|a_i-b_i|=1\}$ and graph $G_d=(\mathbb{Z}^d, E_d)$, this is the grid on $\mathbb{Z}^d$. Now the function $g_d:\{0\}\ni i\mapsto G_d$ describes the hyperspace of a $d$-dimensional TM.
These two examples are of course quite different, as the first has $k$ pointers, that can move in 3 directions (left, right, stay) each, and the second has one pointer that can move in $2d+1$ directions. That they are nevertheless computational equivalent (because they are Turing-complete) is well known. Also both reduce to a simple Turing tape in case of $k=d=1$.
It is easy to see that other well-known tape variants can be described by this definition just as well.

But it doesn't end there

However, the definition above allows much more complex examples for tapes, most notably when using infinite cardinals. And when I'm about defining Turing machines, I wonder why I would restrict the alphabet and set of states to be finite. Of course, these generalizations make it much more difficult to image any kind of realization in the real world. Nevertheless, I think it is kind of interesting if these generalizations of a TM would make it possible to archive something beyond Turing completeness. Other known generalizations such as non deterministic TMs and quantum TMs do not seem to have archived greater computability. Maybe I missed something?

The Question

Has my kind of generalization (the different "Turing Spaces") been studied before? Or any kind of allowing infinite states and/or alphabets besides the kind appearing in quantum TMs?


texts: The Church-Turing thesis and Hyper-computation

texts:
I am not a computer scientist and this is my first question.
This question is a question in layman terms and I also want the answer in layman terms.
When I searched hyper-computation. There was a list of models of hyper-computers.
Now, my question is that what are the problems with those models and if it is possible to  create models of computers which can compute non-Turing computable things then doesn't, that already proves the Church-Turing thesis wrong and if it does prove that Church-Turing thesis is wrong then why people still consider it to be a thing?


texts:
Given a set of intervals on the real line, compute the largest subset of pairwise
intersecting intervals (an interval in the subset must intersect with every other interval
in the subset). Design a greedy algorithm that computes an optimal solution.


texts:
Let's say we have given array $A$ consisting of $n$ integers, and integer $K$. Now we want to count number of indexes $i$ such that $A_i<K$. What is the easiest way to pre-process the array and answer queries for different $K$ fast. Note that the elements of the array will be small up to $10^5$, so it will be possible to count how many times each elements appears.

For example, let $A = \{1, 2, 3,0,0,2\}, K =3$ the answer is $5$, because all $\{1,2,0,0,2\}$ are less than $3$.

I know that we can implement this with segment tree and than answer queries in $O(\log N)$, but I was thinking that we can implement easier solution that is easier to code.


texts: Subexponential size of string to prove $\{xy : x,y \in \{0,1\}^\star, |x| = |y|, x \ne y\}$ is not regular?

texts:
In the standard proof of this language not being regular using the Pumping Lemma for Regular languages, one picks $0^p 1^p 0^{p+p!} 1^p$ where $p$ is the pumping constant and using that can derive the string $0^{p+p!}1^p0^{p+p!}1^p$ (since $p$ divides $p!$ for every $p$, thus proving the language is not regular.
Is there a string that has length subexponential in $p$ (or even polynomial) to show this language is not regular using the Pumping Lemma?


texts: Matching elements of two lists to identify the missing ones

texts:
Given two arrays of integers, A and B, with same size (or two bit vectors A and B with some bits enabled)

What would be the faster way to create a list C containing the elements from B not in A, (or the indexes of the bit vector B not enabled in A)?


texts:
Can a problem be both NP-Hard and CoNP?

Can a problem be both NP and CoNP-Hard?


texts: Relationship between algorithm size and compression power

texts:
Does the size of an algorithm restrict how many bitstrings it can compress, and how much it can compress the bitstrings?

Some definitions and an example to illustrate this is the case.

An elite program is the shortest program that outputs a particular bitstring.
Elite programs are generally incomputable (Kolmogorov complexity).
Due to the non-computability of elite programs, the most general compression algorithm is a lookup table, which maps bitstrings to their corresponding elite programs.
Compression power is the proportion of bitstrings with a specified length and Kolmogorov complexity that an algorithm can compress.

The following example illustrates how the algorithm size can impact its compression power.

To compress a set of bitstrings of length 10 that have Kolmogorov complexity of 5, we need a lookup table of size $10 * 2^5$ bits.  This table is signified by $T_1$.
If our bitstrings are now length 20 and still have KC of 5, we need $20 * 2^5$ bits for our table $T_2$.
If we have a table with the number of bits from #1, $T_1$, but need to compress the bitstrings from #2 to their KC length, we only have enough space to compress $\frac{T_1}{T_2}=\frac{10*2^5}{20*2^5}=\frac{10}{20}=\frac{1}{2}$ of the bitstrings.  This is because to compress all bitstrings from #2 we need all the bits in $T_2$.  However, we only have half that amount of bits we need in $T_1$.
Similarly, if the KC of the bitstrings increases to 6 and length remains 10, we can only compress $\frac{10*2^5}{10*2^6}=\frac{1}{2}$ of the bitstrings.

An argument from this example suggests it is generally true an algorithm's size restricts its compression power.

A. The example shows if we are restricted to a simple lookup table algorithm, then as the bitstring length or KC increases, the number of bitstrings the algorithm can compress to KC length decreases.

B. Since elite programs are incomputable, modern compression algorithms that can compress arbitrarily large bitstrings appear to be a special case, and the lookup table is a better characterization of compression algorithms in general.

C. By A and B, it is generally the case the size of a compression algorithm in bits restricts its compression power.


texts: What is meant by a preemptive algorithm?

texts:
The definition on Google says 'serving or intended to pre-empt or forestall something, especially to prevent attack by disabling the enemy.'
So, how does this relate to an algorithm, especially the Nearest Neighbour Algorithm?


texts: Decomposing the n-cube into vertex-disjoint paths

texts:
I am not sure if this question is better suited for cs.stackexchange or math.stackexchange - This is of interested to me in the context of a data structure problem, but the question itself may be better suited elsewhere. If so, please feel free to move my question.

Let $\mathcal{Q}_n$ denote the $n$-cube graph. Given a set of vertices $S = \{s_1, \ldots s_k \}$ and $T = \{t_1, \ldots t_k\}$, we would like to decompose $\mathcal{Q}_n$ into $k$ vertex disjoint paths $P_1, \ldots P_k$, such that each $P_i$ begins with $s_i$ and ends with $t_i$. Here, two paths are vertex-disjoint if they do not share any vertices. In addition, I require that every vertex in $\mathcal{Q}_n$ be part of some path $P_j$. I would like to know under what conditions (particularly on $S$ and $T$) can we guarantee that such a decomposition exists?

Also, I would like to know the name of this problem so that I can better search for references.


texts: Master theorem for $T(n) = 2T(n/2) + n^{2}\log n$

texts:
Would I use the third case of the Master Theorem for the recurrence equation $T(n) = 2T(n/2) + n^{2}\log n$?

The condition given for the third case by Wikipedia is $f(n) = \Theta(n^c)$ when $c > \log_{b}a$.


texts: Is it viable to use an HMM to evaluate how well a catalogue is used?

texts:
I was interested on evaluating a catalogue that students would be using to observe how is it being used probabilistically.

The catalogue works by choosing cells in a temporal sequence, so for example:

Student A has: ($t_1$,$Cell_3$),($t_2$,$Cell_4$)
Student B has: $(t_1,Cell_5),(t_2,Cell_3),(t_3,Cell_7)$.

Assume that the cells of the table are states of a Hidden Markov Model, so the transition between states would map in the real world to a student going from a given cell to another.

Assuming that the catalogue is nothing more than guidance, it is expected to have a certain kind of phenomenon to occur on a given artifact. Consider this artifact to be unique, say, for example a program.

What happens to this program is a finite list of observations, thus, for a given cell we have a finite list of observations for following the suggestion mentioned on that cell. On a HMM this would be then the probability associated to a state to generate a given observation in this artifact.

Finally, consider the catalogue to be structured in a way that initially it is expected that the probability to start in a given cell is equal. The catalogue does not suggest any starting point.

Question 1: Is the mapping between the catalogue and the HMM appropriate?
Question 2: Assuming question 1 holds true. Consider now that we train the HMM using as entries $(t_1,Cell_1), (t_2,Cell_3) , ... (t_n,Cell_n)$ for the students. Would the trained HMM, once asked to generate the transition between states that it is most likely yields as result what is the most used way by the people who used the catalogue for a given experiment $\epsilon$?


texts: What does the "big O complexity" of a function mean?

texts: What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?


texts: Designing less than and less than or equal operators for Map with value being a Set

texts:
I am trying to come up with less than and less than or equals operators for a Map where values are Sets. These are the hints I was able to get from the Professor.
{A -> {1,2}, B -> {3,4}} < {A -> {1,2}, B -> {3,4}, C -> {5,6}}

{A -> {1,2}, B -> {3,4}} < {A -> {1,2}, B -> {3,4,5}}

My solution was this:
val v_compare = (x, y) => (x.keySet intersect y.keySet).forall(key => x(key) subsetOf y(key))

val v_compare_equal = v_compare

I am wondering can I get some hints? I don't know what should the "<=" be


texts: Why do we need double-rotations to rebalance AVL trees?

texts:
I was reading about AVL tree rebalancing from Behrouz Forouzan's book. The book first defines Left High and Right High tree:

  Left High (LH) tree is a tree tree with the height of the left subtree more than that of right subtree.
  Right High (RH) tree is a tree with the height of the right subtree more than that of left subtree.

Then the book says:

  Insertion of a node may make an AVL tree height unbalanced. All height unbalanced trees fall in one of these four cases:

  LH of LH — A subtree of a tree that is left high has also become left high.
  RH of RH — A subtree of a tree that is right high has also become right high.
  RH of LH — A subtree of a tree that is left high has become right high.
  LH of RH — A subtree of a tree that is right high has become left high.

I went through the example of balancing RH of RH tree as below. As can be seen below it involves left rotating root of RH tree (not subtree) to replace left node of the root of RH subtree:

Now I am looking at the example in Schaum's, which inserts W in the AVL tree already containing M,E,D,G,T,P,V,U,Z as follows:

I dont understand if the rotateRight() in above is necessary. I guess above is also an example of RH of RH tree, if you apply Forouzan's analogy. In this case nodes T and V are Right High. So as per explanation in Forouzan's book, we can apply single left rotation to node T to make it left child of V and balance this AVL tree as follows:

                 M
               /   \
              /     \
             E       V
            / \     /  \
           D   G   T    Z
                  / \  /
                 P   U W

I dont find the need of first rightRotate() to make W right child of Z. Is it necessary? Or Schaum's example is wrong?


texts:
Will $L = \{a^* b^*\}$ be classified as a regular language?

I am confused because I know that $L = \{a^n b^n\}$ is not regular. What difference does the kleene star make?


texts:
Our professor asked us to think of a function in OCaml that has the type

'a -> 'b

i.e. a function of one argument that could be anything, and that can return a different anything.

I thought of using raise in a function that ignores its argument:

let f x = raise Exit

But the professor said there was a solution that doesn't require any function in the standard library. I'm confused: how can you make a 'b if you don't have one in the first place?

 I'm asking here rather than on Stack Overflow because I want to understand what's going on, I don't want to just see a program with no explanation.


texts: How polynomial interpolation of polynomial multiplication algorithm works?

texts:
I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following:

Algorithm [DPV, p. 60]
Input: Coefficients of two polynomials. A(x) and B(x), of degree d.
Output: Their product $C = A . B$

Selection: Pick some points $x_0, x_1, x_2, ..., x_{n-1}$ where $n\geq 2d+1$
Evaluation: Compute $A(x_0), A(x_1), ...., A(x_{n-1})$ and $B(x_0), B(x_1), ...., B(x_{n-1})$
Multiplication: Compute $C(x_k)=A(x_k) \times B(x_k)$ for all $k=0, 1, ..., n-1$
Interpolation: Recover $C(x) = c_0 + c_1 x + c_2 x^2 + .... + c_{2d} x^{2d}$

Now, I took an example $A(x) = 3x^2 -4x + 1$ and $B(x) = x-2$. The output should be $C(x) = 3x^3 - 10 x^2 + 9 x -2$. Now, the algorithm first choose an arbitrary points, so I will choose the following: $x_0 = 1, x_1 = 3, x_2=6,$ and $x_3 = 9$. Now, we evaluate the A(x_i) and B(x_i) for $i=0, 1, 2$ and $3$. Thus, $A(x_0) = 0, A(x_1) = 16, A(x_2) = 85, A(x_3)=208, B(x_0) = -1, B(x_1) = -2, B(x_2) = -5,$ and $B(x_3)=-8$. Thus, we compute $C(x_i)$ for $i=0, 1, 2,$ and $3$. So, we get $C(x_0) = 0, C(x_1) = -32, C(x_2)=-425,$ and $C(x_3) = -1664$.
Now, I have $x_0=1, x_1=3, x_2=6,$ and $x_3=9$ and the corresponding $C(x_0) = 0, C(x_1) = -32, C(x_2) = -425,$ and $C(x_3)=-1664$. This I will apply the polynomial interpolation to get the output. I used this page to compute the coefficients of C(x). So, I got the output as following: $-3x^3 + 7x^2 - 5x + 1$ but it should be this one: $C(x) = 3x^3 - 10 x^2 + 9 x -2$. So, where is the problem? Is it because finding interpolation cannot be in exact so the coefficient is an approximation to the exact one.


texts: Proving that the set of deciders is not Turing-recognizable

texts:
Let $A$ be the language consisting of descriptions of Turing machines $\{M_1, M_2, \dots \}$, where each $M_i$ is a decider. Prove that $A$ is not Turing-recognizable.

Then suppose $A$ is Turing-recognizable and suppose $s = \{s_1, s_2, \dots \}$ is a set of all possible binary strings. Then I construct decider $D$ as follows. On input $w$, if $w$ is not equal to binary string, then reject. Else, $w$ is a binary string that is equal to $s_i$ for some $i$. Use the enumerator $E$ to print the $i$-th output which is $M_i$. If $M_i$ accepts $s_i$, $D$ is going to reject $s_i$. Otherwise, accept $s_i$.

But in the last step, what happens when $M_i$ doesn't have defined transition over the alphabet $\{0,1\}$? Does $M_i$ immediately enter a reject state? What should I argue?


texts:
So, I was analyzing the Calibron 12 puzzle and to me it looks like a bin-packing problem. Is this puzzle actually a bin-packing problem and thus NP-hard for the perfect solution?

Basically, you can make your own calibron 12-ish puzzle by doing the following:

Take a rectangular piece of wood. Cut the wood into randomly sized rectangles. Jumble the pieces. Now put it back together into the exact same shape. (note there are technically 4 solutions, due to mirroring vertically or horizontally also fitting the exact shape)


texts: Showing a language is context free. Use PDA or CFG?

texts:
I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it.

Show language $L$ is context free, where $L = \{\text{all strings where middle two symbols are the same}\}$


texts: Huffman encoding: why is there no need for a separator?


texts:
Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$.

I need to find a vertex $v \in V$ such that $$\sum_{i=1}^n d(v_i, v)^2$$ is minimal. What is the most time-efficient algorithm to solve this problem? Could I do any better than computing shortest paths from all $v_i$ to all other vertices in the graph?

Real-world example: $n$ friends are looking for a place for a meeting.

This is similar to closeness centrality, but here I have a sum of squared distances rather than sum of distances.


texts: No common terms between polynomials: an efficient check?

texts:
The "common term" would be in standard form, but the two input multivariate  polynomials needn't be, e.g $x(1+y)+y$ and $y(x+a+b)$ have one common term, $xy$.

A brute force solution would be to expand both polynomials to standard form, then check for common terms. e.g. $x+xy+y$, $xy+ay+ab$.

Is there a better way?

EDIT if it makes it easier, we can loosen "same term" to allow different coefficients, so that e.g. $2xy$ and $3xy$ count as the "same term". (there must be a more mathy way to say that)...
so, perhaps it becomes like a single component in Fourier analysis?

Maybe, a specific term could be identified by differentiating its factors by their power number of times to eliminate it (e.g. $x^2y^3$, differentiate by $x$ twice and by $y$ three times). Though, seems inefficient, and unclear how to extend that to checking all terms apart from brute force.

BTW "no common terms" is the opposite of "all terms in common" (in a sense), i.e checking for identical polynomials. This does have an efficient algorithm, using the Schwartz-Zippel lemma (see Is there an efficient algorithm for expression equivalence?).


texts: Can you pop 2 elements at a time in a PDA

texts: My question is N(a)=2N(b) ; No of a's = 2 * No of b's . So for every symbol b can I pop 2 a's simultaneously


texts: 1's complement addition of outer carry to the result

texts:
Let's take for example this addition: 3 + (-1).

1 in binary is 001, and to obtain it's 1's complement counterpart we
flip the bits. So it is: 110.

3 in binary is 011.

011 + 110 = 1001
That first 1 which is in bold has to be added to the number formed by the last 3 bits as follows:
001 + 1 = 010 (2 in decimal).

Why do we do the last step, adding that outer carry? Which is the logic behind?


texts: Runtime and space usage of a snippet of code

texts:
I've been trying to understand time complexity and space complexity by writing my own snippets of code and solving them. Can you see if I'm correct?

for(int i=1; i<=n; i*=2) c = i+8;
for(int j=n; j>0 ; j/=2) a[j] = 8;

I think the time complexity is $O(log_2n)$ and the space complexity is $O(n)$.

for(int i = 1; i<=n;i*=2)
    for(int j=n ; j>0 ; j/=2)
        a[j] = 8;

In this case, the time complexity is $O((log_2n)^2)$ and the space complexity is $O(n)$.

What do you think?


texts: How this expression leads to the given sequence

texts:
Here given is a sequence from OEIS.

The sequence is triangle of coefficients from fractional iteration of e^x - 1. Few terms are:
1, 1, 3, 1, 13, 18, 1, 50, 205, 180, 1, 201, 1865, 4245, 2700, 1, 875, 16674

The expression of finding the sequence is also given as:
A(n;x) for n-th row satisfies
 A(n;x) = Sum_{k=0..n-1} Stirling_2(n, k)*A(k;x)*x, A(1;x) = 1.

The tabular  view shows the entries row wise. Stirling_2(n,k) is most probably stirling numbers of the second type

I am not able to get how above expression is resulting in the given sequence.
In summation, k begins from 0, but nothing is mentioned about A(0;x). I assumed it to be 0, but still can't get the above values.
Please explain how the first few terms are resulting from the expression.


texts: How does the Y combinator exemplify "Lambda calculus inconsistency"?

texts:
On the Wikipedia page for Fixed Point Combinators is written the rather mysterious text

  The Y combinator is an example of what makes the Lambda calculus inconsistent. So it should be regarded with suspicion. However it is safe to consider the Y combinator when defined in mathematic logic only.

Have I entered into some sort of spy novel?  What in the world is meant by the statements that $\lambda$-calculus is "inconsistent" and that it should be "regarded with suspicion"?


texts: Shortest Path in a Graph with Interacting Edge Weights

texts:
Suppose we have a graph $G = (V,E)$.

Every edge $e \in E$ has a unary cost $f(e) > 0$.

Also, for every two edges $e_1,e_2 \in E$ we have a binary reward function $g(e_1,e_2) \geq 0$.

Given two vertices $s$ and $t$, is it possible to find the path that minimizes the following objective function efficiently?

$
\sum_{e \in \text{Path}} f(e)
- \sum_{e_1 \in \text{Path}} \sum_{e_2 \in \text{Path}} g(e_1,e_2)
$

Update:

According to @xavierm02's answer this problem seems to be NP-hard. But is there any heuristic that can at least partially deal with this? If it helps, this is the context for which I want to use this problem.

This shortest path simply represents a sequence of curves for a piecewise curve fitting as in the paper: http://www.mit.edu/~ibaran/curves/ .

The final goal is to fit a sequence of curves to a bunch of points. As we cannot fit just one curve, we also have to decide where the transitions occur. In this approach, we basically fit every possible curve. Then, we construct a graph, where each curve is associated with an edge, and the points to be fitted are the vertices (not exactly the same as the paper). The weight of each edge is basically its error in the least square fit. We then find the shortest path from the first point, to the last, which in turn tells us the best sequence of curves.

What I am trying to do is to use this reward function to encourage certain curve pairs to be inside the final selected sequence of curves. For example, the ones that are symmetric.

Further updates:

$g$ has very few non-zero values, and we can safely assume $g(e_1,e_2)<f(e_1)$ and $g(e_1,e_2)<f(e_2)$. The graph has cycles, and we might have $s=t$.


texts: Why interaction net languages use interaction rules to represent their syntaxes?

texts:
What I have looked up into:
here, here and here

What I have learnt:

What is an interaction net, its deduction & interaction rules,
How deduction rules can be changed into interaction rules -- you "link" the two sides of one deduction rule, "magically" turn their arrows up and rearrange the bubbles, and then split them according to the rearrangement, and
You can use interaction rules to simply represent a interaction programming language's syntax.

What I am confused of:

Why interaction rules can be used as syntaxes: they haven't told me how to translate interaction rules back into deduction rules, they are only giving one direction of the translation.
Why interaction rules are chosen for syntaxes: since there've been already deduction rules for describing the net's behavior, why even use harder-to-read interaction rules to describe it? Otherwise you can just use deduction rules and translate it into interaction rules when using any interaction PLs. Is it easier to be applied in some technical details? How does interaction rules work on one sentence like (Cons Nil Nil)?


texts: Is string matching and replacement considered in formal languages?

texts:
Is string matching and replacement, as an operation on strings or on formal languages, considered in  formal languages?

For example, the family of regular languages, or the family of
context free languages, ..., are closed under certain string
operations.

I would wonder if these families or some others may be closed under
string matching and replacement?
Are string matching and replacement equivalent to some combination
of other string operations?
Or is matching and replacement considered in formal languages in
some other ways?

Thanks and regards!


texts: Use of sorting in counterexamples for equations

texts:
I came across a question which asked how sorting would help in searching for counterexamples to the conjecture that $$u^6 + v^6 + w^6 + x^6 + y^6 = z^6$$ has no non trivial solutions in integers.

The answer said to make two files containing values of $u^6 + v^6 + w^6 \pmod W$ and $z^6 - y^6 - x^6 \pmod W$. $W$ is the word size of the computer. Sort these, search for duplicates and go for further steps.

Can someone explain what these further steps would be in detail ?


texts: How do I write a proof using induction on the length of the input string?

texts:
In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata.  I understand mathematical induction, however when strings come into play I get real tripped up.  I'd really appreciate it if someone would go through the process of making such a proof step by step.

Here's an example problem (Exercise 2.2.10 from Hopcroft and Ullman 3rd Edition):

  Consider the DFA with the following transition table:

        0    1
       ________
-> A |  A    B
  *B |  B    A

  Informally describe the language accepted by this DFA, and prove by induction on the length of an input string that your description is correct.

This is an answered problem in the book, so I'm not looking for someone to do my homework.  I just need someone to explain it to me straight.

Book's Answer:
(taken from here)

  The automaton tells whether the number of 1's seen is even (state A) or odd (state B), accepting in the latter case. It is an easy induction on |w| to show that dh(A,w) = A if and only if w has an even number of 1's.
  Basis: |w| = 0. Then w, the empty string surely has an even number of 1's, namely zero 1's, and δ-hat(A,w) = A.

  Induction: Assume the statement for strings shorter than w. Then w = za, where a is either 0 or 1.

  Case 1: a = 0. If w has an even number of 1's, so does z. By the inductive hypothesis, δ-hat(A,z) = A. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then so does z. By the inductive hypothesis, δ-hat(A,z) = B, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case, δ-hat(A,w) = A if and only if w has an even number of 1's.
  Case 2: a = 1. If w has an even number of 1's, then z has an odd number of 1's. By the inductive hypothesis, δ-hat(A,z) = B. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then z has an even number of 1's. By the inductive hypothesis, δ-hat(A,z) = A, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case as well, δ-hat(A,w) = A if and only if w has an even number of 1's.

I understand how to prove things like $\sum_{i=0}^{n}i = \frac{n(n+1)}{2}$ using induction.  I'm just confused by how this works with building strings.  I'm confused by the bolded parts.  I don't understand how they are come up with/how it actually proves what is accepted/how it is inductive.

δ-hat is the extended transition function, by the way.


texts: How to determine convergence when using Q-learning?

texts:
I'm using Q-Learning to find the values of states in on a gameboard. For example, something like:

-----------------
|   |   |   | 1 |
-----------------
|   | W |   | -1|
-----------------
|   | W |   |   |
-----------------
| S |   |   | 1 |
-----------------

I have the transition, and I can calculate the values of the states, but I can't tell when to stop computing. Normally I would just compute until a terminal state, for x-episodes; but this particular board has no terminal states. So I'm stuck to just calculating the values over say 1000 iterations (the more the more accurate obviously). I would like a way to stop though when I'm within an acceptable range.

How is this normally done for a non-terminal state space?


texts: Is the FSA for that language right? Comparison between two solutions

texts:
Given the alphabet $ Λ = \{a, b\}$ construct a FSA for the following language:

$$ L=\{α∈Λ^* ∧ |α|a =even ∧ |α|b =odd\}$$

where $|α|x $ is the number of occurrences of $x$ in $α$.
Basically, only strings where the number of $a$'s is even and the one of $b$'s is odd.

My attempt was the following:

whereas that's the solution of my teacher:

I wonder if mine is correct, too. I tried to follow the paths and I think that mine is working.


texts:
According to the definition of ADT on wikipedia , it is given that ADT is a mathematical model for data types , And as per wikipedia, definition of mathematical model says that it is composed of variables and relationships.
Relationships can be described by operators, such as algebraic operators, functions, differential operators, etc. Variables are abstractions of system parameters of interest, that can be quantified.

Now I can get the intution that variables we can although define operations like addition , subtraction over integers but then how come they can be quantified ?

It's hard for me to get the basic understanding of this terminology used

Now this is the definition of quantification ,Approximation of a subjective aspect (attribute, characteristic, property) of a thing or phenomenon into numbers through an arbitrary scale (such as the Likert scale). Every aspect of nature can be quantified although it may not be measurable.

so how can integers be approximated when they don't have decimal parts


texts:
I am studying for my exam and I wanted to do some extra excercises, but I have some problems with solving :) Can anyone please help or give me some advice where to start? Thank you!

We can represent every list of lambda expressions $x_0, x_1, ..., x_k$ with lambda expression $[x_0, x_1, ..., x_k]$ , defined as:
$[x_0, x_1, ... , x_k] = \lambda c n. c \, x_0 \, (c \, x_1 \, (... (c \, x_k \, n) ...))$

Define lambda expression s, satisfying the equation  $s([\underline{n_0}, ..., \underline{n_k}]) = \underline{n_0 + ... + n_k}$ , where  $\underline{n}$ is a Church numeral, representing natural number $n$.

Define lambda expression $r$ , satisfying the equation  $r([x_0, ..., x_k]) = [x_k,  ..., x_0]$ .

Define lambda expression $h$ and $t$ , satisfying the equation  $h([x_0, ..., x_k]) = x_0 in t([x_0, x_1, ..., x_k]) = [x_1, ..., x_k]$ .


texts: Table-driven lexers in Engineering a Compiler 2nd Edition

texts:
Recently, I am reading Engineering a Compiler 2nd Edition.

But I am struggling to understand the following pseudocode.

Can anyone help me to explain the pseudocode in a simple and plain English?

Why NextChar does take a char input?
Why lexeme is the result 0f lexeme + char?
What is the result of Delta[state, cat];?


texts:
This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them!

In the analysis of Ford-Fulkerson I understand why the while loop runs no more than $val(f^*)$ times but I don't see why it only takes $O(E)$ time to find an augmenting path. Using a BFS or DFS would give $O(V+E)$ no? The running time I see everywhere says $O(E\cdot val(f^*))$

Also, given $C$, the maximum capacity of any edge in the network, I see a lot of people stating the bound $val(f^*)\leq nC$ where $n$ seems to be $|V|$. However it isn't clear why this relation holds. $val(f^*)\leq C|E|$ makes more sense to me but never seems to be used...


texts: number of connected induced subgraph in a tree

texts:
Let G be a tree-structured graph. A connected induced subgraph is an induced subgraph from G that is connected. (Since the original graph is a tree, any connected induced subgraph is also a tree)

My question: Given a tree G of n vertices, how many connected induced subgraph can be obtained from G?

An example: n = 4, G looks like 1---2---3---4 (I name those four vertices by 1, 2, 3, 4). Then we have 10 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,2,3}, {2,3,4}, {1,2,3,4} where I represent a connected induced subgraph by a set of their vertices.

Another example: n = 4, G looks like 1---2---3, 1---2---4 (node 2 directly connects 3 and 4. forgive my poor way of drawing it in text)
In this case, we have 11 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,2,4}, {2,3,4}, {1,2,3,4}.

From those two little examples we can see that the actual number depends on the exact structure of the tree, so, I am hoping you can help me further determine what is the factor that influences the result (I guess the maximal degree?).

Thank you!


texts: General algorithm to find a minimal branching program

texts:
Given a general branching program, is there an algorithm which can find an equivalent branching program $P$ of minimal length. That is $|P| \leq |P'|$ for all equivalent branching program $P'$.

If not, are their some specific cases where this algorithm exists?


texts:
I have a method Func() that has two inner methods Func1() and Func2().

Func1() has a running time of $O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert))$ and Func2() has a running time of $O(k \lvert K \rvert \lvert V\rvert)$.

What is the running time of Func()?

Is it $\max \{ O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert)),O(k \lvert K \rvert \lvert V\rvert)\} $? or $O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert))+O(k \lvert K \rvert \lvert V\rvert)$?

If it is the latter one, how can it be simplified?


texts: CFG for all strings of a’s and b’s that contain a different number of a’s and b’s

texts:
I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this:

S→A|B
A→aE|aA|EA
B→bE|bB|EB
E→aEbE|bEaE|Λ

I tried running few strings on this, it worked, But then I run string "abbab" and it failed.
 Kindly someone point out at my mistake or tell me the correct CFG for this as I don't know how to correct this.


texts: Disprove unrealistic speed-up of total Turing machines

texts:
Let $T_1$ be a total Turing machine deciding language $L_1$, and let $I_1$ and $I_2$ be two separate inputs to $T_1$. Further, let $I_{c}$ be $I_2$ concatenated to $I_1$ with some separation symbol in between, and let $S_{T}(I)$ be the number of steps total TM $T$ needs to run until it accepts/rejects input $I$. I am wondering about the following two statements:

For every $T_1$ there exists another total Turing machine $T_2$ such that for all valid inputs $I_1 \neq I_2$ for $T_1$, $T_2$ accepts $I_c$ if $T_1$ accepts $I_1$ or if $T_1$ accepts $I_2$.

For every $T_1$, there exists a $T_2$ with the above property such that for all valid inputs $I_1 \neq I_2$, it holds that $S_{T_2}(I_c) < S_{T_1}(I_1) + S_{T_1}(I_2)$

To me, it seems as if the second statement would imply an impossible speed-up and should have an obvious counterexample, but I haven't been able to come up with one.