texts: Common subgraph isomorphism with K vertex

texts:
I'm looking for subgraph isomorphism of at least K vertex between Graph A and B.
I only can come up with the dumbest algorithm, which is:

Compute all combination of vertices with length K of Graph A.
Run subgraph isomorphism test for every combination vertices against Graph B, probably using VF2 algorithm.

Upon researching I found Maximum Common Subgraph. On one paragraph, there is

  The associated decision problem, i.e., given G1, G2 and an integer k, deciding whether G1 contains a subgraph of at least k vertices isomorphic to a subgraph of G2 is NP-complete.

This "associated decision problem" is exactly what I'm looking for. But I can't look further than this Wikipedia article to learn about it. Can anybody point me to related paper or text about this problem? Or even better, slightly explain to me how solution of the problem might works compared to my dumb algorithm.

My sincerest thank to you all.


texts:
Suppose I have an alphabet of n symbols. I can efficiently encode them with $\lceil \log_2n\rceil$-bits strings. For instance if n=8:
A: 0 0 0
B: 0 0 1
C: 0 1 0
D: 0 1 1
E: 1 0 0
F: 1 0 1
G: 1 1 0
H: 1 1 1

Now I have the additional constraint that each column must contain at most p bits set to 1. For instance for p=2 (and n=8), a possible solution is:
A: 0 0 0 0 0
B: 0 0 0 0 1
C: 0 0 1 0 0
D: 0 0 1 1 0
E: 0 1 0 0 0
F: 0 1 0 1 0
G: 1 0 0 0 0
H: 1 0 0 0 1

Given n and p, does an algorithm exist to find an optimal encoding (shortest length) ? (and can it be proved that it computes an optimal solution?)

EDIT

Two approaches have been proposed so far to estimate a lower bound on the number of bits $m$. The goal of this section is to provide an analysis and a comparaison of the two answers, in order to explain the choice for the best answer.

Yuval's approach is based on entropy and provides a very nice lower bound: $\frac{logn}{h(p/n)}$ where $h(x) = xlogx + (1-x)log(x)$.

Alex's approach is based on combinatorics. If we develop his reasonning a bit more, it is also possible to compute a very good lower bound:

Given $m$ the number of bits $\geq\lceil log_2(n)\rceil$, there exists a unique $k$ such that
$$ 1+\binom{m}{1} + ... +\binom{m}{k} \lt n \leq 1+\binom{m}{1} + ... + \binom{m}{k}+\binom{m}{k+1}$$
One can convince himself that an optimal solution will use the codeword with all bits low, then the codewords with 1 bit high, 2 bits high, ..., k bits high. For the $n-1-\binom{m}{1}-...-\binom{m}{k}$ remaining symbols to encode, it is not clear at all which codewords it is optimal to use but, for sure the weights $w_i$ of each column will be bigger than they would be if we could use only codewords with $k+1$ bits high and have $|w_i - w_j| \leq 1$ for all $i, j$.
Therefore one can lower bound $p=max(w_i)$ with $$p_m = 0 + 1 + \binom{m-1}{2} +... + \binom{m-1}{k-1} + \lceil \frac{(n-1-\binom{m}{1}-...-\binom{m}{k}) (k+1)}{m} \rceil$$

Now, given $n$ and $p$, try to estimate $m$. We know that $p_m \leq p$ so if $p \lt p_{m'}$, then $m' \lt m$. This gives the lower bound for $m$. First compute the $p_m$ then find the biggest $m'$ such that $p \lt p_{m'}$

This is what we obtain if we plot, for $n=1000$, the two lower bounds together, the lower bound based on entropy in green, the one based on the combinatorics reasonning above in blue, we get:

Both look very similar. However if we plot the difference between the two lower bounds, it is clear that the lower bound based on combinatorics reasonning is better overall, especially for small values of $p$.

I believe that the problem comes from the fact that the inequality $H(X) \leq \sum H(X_i)$ is weaker when $p$ gets smaller, because the individual coordinates become correlated with small $p$. However this is still a very good lower bound when $p=\Omega(n)$.

Here is the script (python3) that was used to compute the lower bounds:

from scipy.misc import comb
from math import log, ceil, floor
from matplotlib.pyplot import plot, show, legend, xlabel, ylabel

# compute p_m
def lowerp(n, m):
  acc = 1
  k = 0
  while acc + comb(m, k+1) < n:
    acc+=comb(m, k+1)
    k+=1

  pm = 0
  for i in range(k):
    pm += comb(m-1, i)

  return pm + ceil((n-acc)*(k+1)/m)

if __name__ == '__main__':
  n = 100

  # compute lower bound based on combinatorics
  pm = [lowerp(n, m) for m in range(ceil(log(n)/log(2)), n)]
  mp  = []
  p = 1
  i = len(pm) - 1
  while i>= 0:
    while i>=0 and pm[i] <= p: i-=1
    mp.append(i+ceil(log(n)/log(2)))
    p+=1
  plot(range(1, p), mp)

  # compute lower bound based on entropy
  lb = [ceil(log(n)/(p/n*log(n/p)+(n-p)/n*log(n/(n-p)))) for p in range(1,p)]
  plot(range(1, p), lb)

  xlabel('p')
  ylabel('m')
  show()

  # plot diff
  plot(range(1, p), [a-b for a, b in zip(mp, lb)])
  xlabel('p')
  ylabel('m')
  show()


texts: Where did the terms memory pool and memory leak come from?

texts:
I wonder where those terms came from.

Is it computer science related?

Or are they related to civil engineering, or swimming sports?

Is it some analogy with filling water in a pool, or something like that?


texts: Bubble Sort with "while" loop - why is average case n^2?

texts:
If Bubble Sort is written as:

    while True:
        False
        for i in (0 to n - 2):
            if list[i] > list[i + 1]:
                swap.(list[i], list[i + 1])
                True
    return list

(where n is len(list))

Seems to me that in the worst case (a list in descending order):

the while loop runs $n$ times
the for loop runs $n - 1$ times per while loop $∴$ there will be $n^2 - n$ comparisons
the list is in decreasing order so there will ultimately be $(n^2 - n)/2$ swaps
$∴$ worst case is $O(n^2)$

In the best case (a list already sorted):

the while loop runs $1$ time
there will be $n - 1$ comparisons
the list is already sorted so there will ultimately be $0$ swaps
$∴$ best case is $\Omega(n)$

So for the average case...

the while loop will run more than $1$ time but less than $n$ times
there will be more than $n - 1$ but less than $n^2 - n$ comparisons
there will be more than $0$ but less than $(n^2 - n)/2$ swaps, depending on the state of the list
$∴$ how can we show that the average case is also $n^2$ and $\Theta(n^2)$?

I don't understand where $n^2$ can be observed?

Is it because the number of swaps will always be equal to $(n^2 - n)/x$, where $x$ is determined by the state of the list?

And, as stated here (and in other places), on average, with uniform distribution, the number of swaps would be  $(n^2 - n)/4$, which is half the worst case?

I'm confused :( Any help would be appreciated! Thank you.


texts: AVL tree with fixed height and as few elements as possible

texts:
I have been reading about AVL trees, at the moment I'm trying to figure out how to determine the height of a tree and how to draw an AVL tree of some height with minimum number of elements.

In a tutorial I found that this: would be a AVL tree of height 7

And this AVL tree with the height 4

This is really confusing by the look I would guess that both of them are of height 4. I'm fairly new to data structures, I could not find a simple documentation/tutorial regarding this most of what i found was about Insertion/Deletion with AVL trees.

So is the top tree of height 7 if not how would I draw it with the minimal number of elements. I understand the each sub tree would have to be balanced.


texts:
Consider a group of five processors implementing three-phase commit protocol. During the execution of the protocol, the coordinator and one other process crash. Two of the remaining processes are waiting in "READY" state for the coordinator while the third process is in "PREPARE COMMIT" state. Can they continue and complete the protocol without waiting for recovery of the crashed processes? Do they COMMIT or ABORT? Which state can the crashed process be in?

In my opinion, the crashed processor maybe was in the "ABORT" state, so how can the other processors know the "global decision"?


texts: Confusion related to time complexity of fast fourier transform

texts:
I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT.

It says that lets say I have a polynomial of degree n-1. I want to evaluate the polynomial at $2n^{th}$ roots of unity. For that I can use divide and conquer rule

I will divide my polynomial into evens and odds i.e,

$A(x) = A_{even}(x^2) + xA_{odd}(x^2)$

Now if I want to evaluate A at one of the  $2n^{th}$ roots of unity. I can break it into evaluating the $n^{th}$ root of unity at two polynomials $A_{even}$ and $A_{odd}$ and then add the results with complexity O(n).

They have shown the results to be O(nlogn). However, I think this is for evaluating the value of the polynomial at one of the roots not all the $2n^{th}$.  But the book seems to say it is the total complexity. I am a bit confused.

Can anyone please explain this to me? I am confused


texts: What does it mean that a set of intervals is sorted by the right and left endpoints?

texts:
While reading a paper (On the k-coloring of intervals), I came upon the following description:
"Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are indexed in order of increasing right endpoint, and it is assumed that all endpoints are positive integers."
What does it mean that they are sorted by "right and left endpoints"? Does it mean that each interval is on the form (left endpoint, right endpoint)?


texts: Do "compiler" and "assembler" correspond to frontend and backend phases of a compiler?

texts:
In Compilers: Principles, Techniques, and Tools (2nd Edition) 2nd Edition
by Alfred V. Aho (Author), Monica S. Lam (Author), Ravi Sethi (Author), Jeffrey D. Ullman (Author) , Figure 1.5 gives a language processing system, and Figure 1.6 shows the phases of a compiler. In Figure 1.6, if I am correct, a compiler has a front end (the first four phasesin Figure 1.6) and a backend (the last three phases "machine independent code optimizer", "code generator" and "machine dependent code optimizer" in Figure 1.6).

Literally by the names, the "compiler" in Figure 1.5 should correspond to the all 7 phases of a compiler in Figure 1.6.

But when I try to understand the individual phases of a compiler in Figure 1.6, I found that the book says:

  In App endix A, we put the techniques in this chapter together to build a
  compiler front end in Java. The front end translates statements into assembly-
  level instructions.

I was wondering:

Does the "backend" of the compiler in Figure 1.6 correspond to the "assembler" in Figure 1.5, and does the "frontend" of a compiler in Figure 1.6 correspond to the "compiler" in Figure 1.5?

Is the "intermediate repesentation" in Figure 1.6 the "assembly program" in Figure 1.5?

I guess the answers are all yes, but Yuval's reply mentions that an assembler does its job in only one way, while the books seems to say that each of the three steps in the backend can be done in more than one ways.

For Figure 1.5 in the book, let's take GCC as an example. In the following figure  from https://medium.com/@andrewlindburg/gcc-main-c-explained-1287d91b12a7, what phases does the compiler perform, and what does the assembler perform? Does "compiler CC1" perform the first four phases in Figure 1.6, and does the "assembler AS" perform the "assembler" in Figure 1.5 and to the backend (i.e. the last three phases) in Figure 1.6 in the book above?

Thanks.


texts: Superposition calculus: greater vs greater-or-equal

texts:
Bachmair and Ganzinger 1991, 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', specifies the criterion for using an equation as, by some appropriate ordering, u>v (after substitution, and assuming the terms can be ordered). Equivalently, !(u<=v), after substitution.

However, Schulz 2006, 'Algorithms and Data Structures for First-Order Equational Deduction', specifies the criterion as u>=v (after substitution, and assuming the terms can be ordered). Equivalently, !(u<v), after substitution.

As far as I can tell so far, the latter is correct. For example, TPTP problem SET836-2 seems to be only solvable by allowing applications of superposition that generate clauses ... | true!=true (where true!=true then of course disappears, but disallowing it seems to break completeness for that problem). So it seems it is actually necessary to allow the two terms to be equal.

Is this a case of the older paper simply containing an error which was later discovered? Or am I misinterpreting it, or are they correct given some other condition?


texts: Why Don't We Use Non-ML Artificial Evolution?

texts: I remember reading about Tom Ray's Tierra and how amazing the results it obtained were. However as far as I know, the only "evolution" based computer technology we use now is ML, which is very limited in its abilities. Why haven't we used artificial evolution perhaps similar to Tierra for practical purposes? Is it too hard? Do we lack the technology to make it practical so far or have we decided we don't need to do it, even if we had the technology?


texts: Why is $A \lor (A \land \neg B) \equiv A$?

texts: I would like to know if there is a rule to prove this. For example, if I use the distributive law I will get only $(A \lor A) \land (A \lor \neg B)$.


texts: Problem understanding DFA & NFA equivalence in Theory of Computation

texts:
Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction

but my question is a bit different from that. I was reading Michael Sipser's Introduction to Theory of Computation and I came to a problem. I couldn't understand as to how he is taking his act on equivalence between NFA and DFA.

I have problem understanding this para :-

  Next, we determine the start and accept states of D. The start state
  is E({1}), the set of states that are reachable from 1 by traveling
  along ε arrows, plus 1 itself. An ε arrow goes from 1 to 3, so E({1})
  = {1, 3}. The new accept states are those containing N4’s accept state; thus {1}, {1,2}, {1,3}, {1,2,3}.

My assumption---> As {2} is not in the list of accepted states,so {1,2} should not be considered as new accept state in equivalent DFA.Also,{1} and {1,2,3} and {1,3} stand out as new accept states as per me because traversing from 1 to reasonable nodes lets the final accept state be reached---here,{1},accept state--->{1,3}---accept state as on inputting a from node 3 makes arrive at {1} which is an accept state,hence accpeted,and similarly for {1,2,3}.

So,point at my wrong thinking PLEASE. I have understood that while making transitions only those states are considered final states which are accept states in NFA.Am I wrong???So,how come {1,2} be the new accept state in the equivalent DFA?

Secondly, why he has mentioned that

  The start state is E({1}), the set of states that are reachable from 1 by traveling
  along ε arrows, plus 1 itself`.

I couldn't derive a meaning out of this statement,the reason might be my poor understanding of English language(I am non-native English speaker).Means start state is E({1})---fine upto here. Now, the set of states that are reachable from 1 by travelling along ε arrows,plus 1 itself---It doesn't make any meaning standing as an independent sentence. Someone make me understand the meaning of this line,PLEASE!

Someone please make me understand and elaborate a bit. I feel that author might be wrong there,pardon my noobiness or for any mistake!


texts: Assumption on weights in threshold circuits

texts:
A threshold gate implementing a linear threshold function on $n$ boolean inputs $x_1, x_2 \ldots, x_n$ is given by the equation:
$w_1 x_1 + w_2 x_2 + \ldots, w_n x_n \ge t$
where $w_1, \ldots, w_n, t \in \mathbb{R}$. The $w_i$'s are called the weights of the threshold function and $t$ is called the threshold, and naturally, the gate fires a $1$ on an input $x$ if the weighted sum given by the equation above exceeds $t$.

Now, almost everywhere in the literature on threshold circuits, I encounter this fact (which I am guessing, is folklore since I couldn't find a proof anywhere): The $w_i$'s in the linear equation above can be made integers (on $n \log{n}$ bits), and a threshold circuit made up of these gates will still compute whatever was possible with real weights. I have given this some thought, and I think it must be a simple trick, but I have failed to obtain a proof of this fact. Can somebody help or provide me with a reference? (the only reference I could find was a text by Muroga, which I couldn't procure)


texts: Is the NP-hardness Proof with One Way Implication Correct and Why?

texts:
A problem $\Pi$ is NP-hard if I can prove this:

a known NP-hard problem $\Pi'$ reduces to $\Pi$ in polynomial time; and
$f(x) \in \Pi\iff$  $x \in \Pi'$.

If I can show only one way implication, that is  $f(x) \in \Pi\Rightarrow$  $x \in \Pi'$. Is this reduction known, correct and why?

For me it is correct because, if I had an algorithm for $\Pi$ then I would use it to solve $\Pi'$. Therefore, $\Pi$ is at least as hard as $\Pi'$ then $\Pi$ is NP-hard.


texts:
In order to find the recurrence function of The Height in Heap, the following figure is drawn.

Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have the height of Left subtree as log in base 3/2?

Question 2: it is stated that:
 "for a complete binary tree to have the maximum height the last level should be half full."
i don't grasp the logic behind this line.why?


texts:
Suppose we have following 2-QCNF problem:

$$\forall x_1...\forall x_m\exists y_1...\exists y_k:\varphi(x_1,...,y_k)$$

where $\varphi$ is 2-CNF.

When the formula is false?

Rules that I found:

$\exists y_i:(y_i\rightarrow \overline{y_i})\land(\overline{y_i}\rightarrow y_i).$ Existentially quantified variable and it's negation are strongly connected.
$\exists\{x_i,x_j\}:(x_i\rightarrow x_j)\lor(\overline{x_i}\rightarrow x_j)\lor(x_i\rightarrow \overline{x_j})\lor(\overline{x_i}\rightarrow \overline{x_j}).$ Two (or one and it's negation) totally quantified variables are connected.
$\exists\{x_i,y_j\}:((y_j\rightarrow x_i)\land(\overline{y_j}\rightarrow x_i))\lor((y_j\rightarrow \overline{x_i})\land(\overline{y_j}\rightarrow \overline{x_i})).$ Totally quantified variable is reachable from existentially quantified variable and it's negation.

Is there any other rule to solve 2-QCNF or, maybe, there is better way to solve it?


texts: State of the art in multi-modal command recognition

texts:
I'm currently researching various fusion methods in a multi-modal (video, audio, identity, user position and gesture) human-computer interaction environment (think in terms of a smart-home system). What is the current state of the art in this field and what fusion methods do they use?

The most recent publication I found was a PhD thesis that relied on lip reading, but I don't think this methodology is reasonable in the type of wide environment I'm considering.

Additionally, I found this publication which fuses various channels into "acts", but this seems to focus semantic-level fusion, which is seems simplistic.


texts: Regular expression to show that all strings contain each symbol atleast once

texts:
I'm studying for my exam and I came across the following exam question from last year, the only way I know how to solve this is build a regex that accounts for all six different series of letters so for example to recognize a string that has the letters a,b and c occur in that order:

$(a+b+c)^*a(a+b+c)^*b(a+b+c)^*c$

The question:
Give a regular expression r over the alphabet A = {a, b, c} such that the
language determined by r consists of all strings that contain at least one occurrence of each symbol in A. Brieﬂy explain your answer.


texts: Find amount of elements greater then number k in a BST

texts:
I am trying to find an Algorithm to find the amount of elements in a BST which are greater than a certain number K.
I found it problematic as there are elements which might be greater then K but wont be found by traveling constantly to the right child, as there might be elements that are greater then K in the left sub-tree.
The Algorithm must be executed in a run-time complexity of O(h), while h is the height of the tree.


texts: Show that it is undecidable if two Turing Machines accept the same language

texts: I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown' that two Turing machines which accept the same language is undecidable. This is not a homework question!


texts: Safe programming languages (PL) are gaining popularity. I wonder what is the formal definition of safe PL. For example, C is not safe, but Java is safe. I suspect that the property “safe” should be applied to a PL implementation rather than to the PL itself. If so, let’s discuss a definition of safe PL implementation. My own attempts to formalize this notion led to a strange outcome, so I would like to hear other opinions. Please, do not say that every PL has unsafe commands. We can always take a safe subset.


texts: Randomly construct linear combination that is within bounds over two basis

texts:
Given rank deficient matrix $A$, I want to randomly construct vectors $\vec{x}$ such that:

$0 \le x_{j} \le 1$
$0 \le b_{j} \le 1$ where $\vec{b} = A\vec{x}$

Matrix $A$ is about 10 x 15. I want to generate $10^{5}$ $\vec{x}$ as an initial guess in each iteration of a solver.

Below is my attempts.

Least square and rejection

Generate $\vec{y}$ with entries between 0 and 1.
Generate $\vec{b}$ with entries between 0 and 1.
Minimize $(\vec{y} - \vec{x})^{2}$ subjected to constraint $A\vec{x} = \vec{b}$.
Reject $\vec{x}$ that are out of bounds.

Problem: the rejection rate is very high. Very impractical even for a 10 x 15 matrix $A$.

Step 2 is equivalent to solving

$\begin{bmatrix}
A & 0\\
I & A^{T}
\end{bmatrix}
\begin{bmatrix}
\vec{x}\\
\vec{\lambda}\\
\end{bmatrix}
=
\begin{bmatrix}
\vec{b}\\
\vec{y}\\
\end{bmatrix}
$

Constrained Optimization

Generate random $\vec{y}$ within bounds.
Objective: $(\vec{x} - \vec{y})^2$.
Constraint: $A\vec{x} = b$
Bounds: between 0 and 1.

Problem: Optimization is too slow and often gives result out of bounds. Impractical.

Other ideas

Null space
Simplex, random planes, and projection
Hit and run sampling


texts: What is the difference between turing reductions and many-one reductions?

texts:
To show that a particular language $A \in C$ is $C$-complete, where $C$ is some complexity class, we might construct a reduction from some known $C$-complete language $B$ to $A$, where $B$ is $C$-complete and the complexity of the reduction is asymptotically less than the upper bound of the complexity class (I just made this up, but it seems to be the case for the reduction to be at all useful; can someone verify?). Restrictions with respect to resource usage make sense to me: Why would anyone need to reduce a problem $B$ to some other problem $A$ if the computation of the reduction is greater than or equal to the computation of $B$?

However, I am taught that such reductions (showing that something is $C$-complete) must be of the many-one kind. Assume we are only talking about decision problems. Why does it matter how the reduction is done, as long as it proves whatever we are trying to prove (i.e. $A$ is $C$-Complete)?

Below are some statements I've established from my studies. Some are incomplete (I have not proven all of them), but my intuition tells me that all of these statements ought to be true. Can someone please confirm/correct my statements below?

Show A is decidable

Construct a decider $M'$ of $A$ using a machine $M$ for decidable language $B$. This reduction does not turn instances of $A$ into instances of $B$, but it still decides $A$, so we say this is a Turing reduction from $A$ to $B$.
Give a many-one reduction from $A$ to $B$. This will show that $A$ is decidable, albeit overkill.

Show A is undecidable

For some known undecidable language $B$, Give a Turing reduction from $A$ to $B$.
For some known undecidable language $B$, Give a many-one reduction from $A$ to $B$ (is this impossible?).

Show A is recognizable

For some recongizable language $B$, give a reduction from $A$ to $B$.
Give a T.M. $M$ that accepts strings in the language of $A$; $M$ is not required to reject strings not in $A$ (it may never halt).
Show its complement $\overline{A}$ is decidable.
Show that $A$ is decidable.

Show $A$ is unrecognizable

Show that $A$ and $\overline{A}$ are both undecidable.
Are there any other ways to show a language is unrecognizable?.

Show $A$ is $C$-complete

Show $A \in C$, and for some known $C$-complete language $B$, give a reduction $B \leq_m A$.

The reduction $R$ must meet the following restriction: If the complexity class $C$ has upper bound $f(x)$ on resource $S$ for some positive quantity $x$ of abstract machines that decide languages in $C$, then $g(x)$ measures the $S$-complexity of $R$ such that $g(x) \in o(f(x))$.
I'm not entirely comfortable with this definition, because, well, $PSPACE$-complete reductions are only required to have polynomial running time. In this case, I think any polynomial-time algorithm has space-complexity asymptotically less than $PSPACE$.
This line of reasoning doesn't add up either, because it is not known that $P \subset PSPACE$ (help?).

In general, it seems anywhere a many-one reductions is used, a Turing reduction may be used, but I'm not sure if the opposite is true. This is where my question about undecidability comes in: Can a many-one reduction be used to show that a language is undecidable? If this were possible, what would it imply?


texts:
If I have two kinds of LinkedList $A$ and $B$.

$A$ is a move to front one which means:
>>> lst1 = 1, 2, 3, 4, 5, 6, 7, 8, 9
>>> lst1.contain(7)
True
>>> lst1.to_list
7, 1, 2, 3, 4, 5, 6, 8, 9
$B$ is a swap list, which means:
>>> lst2 = 1, 2, 3, 4, 5, 6, 7, 8, 9
>>> lst2.contain(7)
True
>>> lst2.to_list
1, 2, 3, 4, 5, 7, 6, 8, 9

I want to find a searching sequence such that the running time of $B$ is faster than $A$. I mean the Theta of them would be different. The length of lst1 and lst2 are both $n$. We search $m$ times and can search different elements for different times.


texts: Partial recursive function and Turing machine

texts:
The wikipedia article about primitive recursion states that

  An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine.

My question is how one can write down formally this definition?


texts:
I am working on finding a PDA that accepts the following language:

L = {0^i 1^j 0^k 1^l | i < j and k < l}

I am having trouble figuring out how to break this down/ where to start. I am able to form simpler PDA's such as when there are twice as many 0's as 1's but am drawing a blank on what approach to take to begin to solve.

Are there any methods or algorithmic approaches to forming a PDA for a given language?

edit: this is NOT a duplicate of the question that was flagged, that question asks how to determine if a grammar is context-free, this is completely different.

So far I have developed this PDA but for some reason it accepts 0101 which should fail, I haven't figured out how it manages to pass through the first portion from the first accepting state:


texts: How to prove a language isn't necessarily regular?

texts:
Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular.
So far I can't come up with much for how to solve this. I was thinking we could solve this by either generating an example where $L'$ isn't regular or we could use the pumping-lemma, but I'm unsure how to get started. This was the hardest one in my set of practice problems.


texts: P vs NP and Angle Trisection (serious question)

texts:
I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level.

My understanding from many popular-level sources (like Scott Aaronson's P vs NP for dummies blog post, or this New Yorker article) is that the P vs NP question asks whether a problem that can be checked "quickly” can also be solved "quickly". But to my knowledge there are well-known problems that can be checked quickly but are impossible to solve regardless of time or number of operations.

Take, for example, the (in)famous angle trisection with straightedge and compass. If asked to check that a provided angle really does trisect 60 degrees, you can very quickly verify that fact using a straightedge and compass. But if someone asks you to solve the problem of trisecting that 60 degree angle using the same straightedge and compass, you can’t do it. So the solution here really only goes "one way" (i.e. using classical tools, the 20 degree angle can be checked really quickly, but no finite amount of operations/time will ever solve the problem of constructing it).

How does this relate to P vs NP? My thought is that this would show that NOT every problem that can be checked quickly can be solved quickly. The specific case of the 60 degree angle trisection appears to be checked in P time and not solved in P time (or any time for that matter, because by using classical tools the problem of the 60 degree trisection cannot be solved at all).

I know I’m missing something, and I tried looking up the formal definition of P vs NP on the Clay Math website, and that was way over my level of understanding (I’m betting that the categories of P and NP don’t apply to my example for reasons I am just not aware of). I just went through the exercise and tried to intuit the question using some well-known math, and I’m having a tough time figuring out where my mistake is.

Any thoughtful feedback is very much appreciated :)

PS: This was moved from CS Theory StackExchange b/c it is not a research q.


texts:
Consider below two Languages

$L1=\{<M>|$M takes atleast 2000 steps on some input $\}$

$L2=\{<M>|$M takes atleast 2000 steps on all inputs$\}$

Where for each Turing machine M, $<M>$ denotes specific encoding of M.

Here I think both are recursive, because let's say I bound the number of steps the Turing machine runs to 2000, then Turing machine will only be able to process inputs of length atmost 2000.

Now, there are finite number of inputs of length 2000, I can check whether for all such inputs, my Turing machine is making 2000 steps or not.This answer L2.

And when L2 is answered, I have an answer to L1, making L1 and L2 both recursive.

Am I correct in my reasoning?


texts: Triple nested loop where outer and inner loop are dependent on n

texts:
I am trying to count the exact/total number of iterations these nested for-loops are executed:

procedure P (integer n);
 for (i: 1 to n)
  for (j: 1 to 10)
   for (k: n to n+5)
    x := x + 1;

I know that the first for loop runs (n-1) times, the second loop runs 10-1 (9) times, thus making the time complexity so far 9(n-1). I know that the the third loop will run n+5-n (5) times, but I am not completely sure because of the n involved. I believe with this calculation added, the total runtime will be 5(9(n-1)) which will translate to O(n). In general, I am wondering if this approach of multiplying the iterations of each loop is a good approach to solving worst case running time and big-Theta estimates. Thanks in advance.


texts: Making groups out of a list of things based on some similarity

texts:
Let's say I have a list of n items - i1, i2, ..., in.

These items are similar to one another based on some similarity function, say similar_func(item_x,item_y) where item_x,item_y belong to list i1, i2, ... in. This function returns a number that ranges from 0 to 1, where 0 means not similar at all and 1 means exactly similar.

Now I would like a create a number of groups, each of which may contain items from the above list. Each group having items that are similar to each other items of the group by let's say 0.5.

I could run a double loop on the list, comparing each item to one another and creating a group whenever I find two items with similarity more than 0.5. Of course I would need to check if the item already exists in a group already created and with all the other items in that group.

This brute force method is possible and will give the right answer.

But I would like to do this more efficiently. Is there a efficient method for solving this problem?

Edit:
There can be any number of groups and an item can be in multiple groups.

If similarity(x,y) = 0.6 and similarity(x,z) = 0.6, but similarity(y,z) = 0.4, then there will be two groups -> [x,y] and [x,z]

Also if x is similar to y AND x is similar to z, then it doesnt mean that y is similar to z. The similarity between two items solely depends on the the return value of similarity function when those items are passed as arguments to it.


texts: Is Differential Evolution a genetic algorithm?

texts:
I am trying to classify the Differential Evolution algorithm according to the framework in the book:

  Introduction to Evolutionary Computing

The authors classify the field of evolutionary computation into 4 paradigms:

Evolutionary programming
Genetic programming
Evolutionary strategies
Genetic algorithms

I have ruled out 1. and 2., since they deal with programs as opposed to abstract optimization problems. I also ruled out 3. since evolutionary strategies maintain an explicit random distribution during the optimization process. That leaves only genetic algorithms. But when you say "genetic algorithm", the firs thing that comes to most peoples' minds is the traditional flipping of 0s and 1s. I have personally never heard anybody refer to differential evolution as a genetic algorithm.


texts: How to convert a non-embedding context free grammar to regular grammar?

texts: Please note that I am aware the undecidability of the conversion of context-free grammar to regular grammar. But given the non-embedding property of the input context-free grammar, is there any algorithm to convert it to regular grammar, or DFA directly?


texts: Why linear transformation can improve classification accuracy when the dimensionality of data is high?

texts: Let $X$ be an $m\times n$ ($m$: number of records, and $n$: number of attributes) dataset.  When the number of attributes $n$ is large and the dataset $X$ is noisy, classification gets more complicated and the classification accuracy decreases. One way to over come this problem is to use linear transformation, i.e., perform classification on $Y=XR$, where $R$ is an $n\times p$ matrix, and $p\leq n$. I was wondering how linear transformation simplifies classification? and why classification accuracy increases if we do classification on the transformed data $Y$ when $X$ is noisy?


texts:
I understand the relation between max flow and min cut, however I made this (simplified) graph, and I cant figure out why max flow seems to be different from my min cut. Im probably overlooking something simple, but I've been staring at this for 10 minutes now...
Can anyone explain what Im missing?


texts: Distribution of Ones in a Psuedorandom Sequence

texts: Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table of the AND gate that you will end up with a string consisting of (approximately) 75% zeroes and 25% ones with the ones being psuedorandomly distributed , so to speak, in a string of zeroes. My question is given any number of observed output bits in the sequence , is it possible to predict WHEN the AND gate will output a one ?


texts: How to construct a random error-correcting code (its generator matrix) according to the code parameters?

texts:
I need to construct a random code which corrects T errors, has R check bits and has N maximum bits in the transmitting word.

I have researched the topic and found a few theorems about the bounds (The Varshamov-Gilbert bound, for instance). Neither of them suggests an algorithm of how to construct the code.

How do I build the random code with the specified parameters? I assume the algorithm should be probabilistic, but I'm not certain.


texts: Turn one string into another with single letter substitions

texts:
I want to turn one string into another with only single letter substitions.  What is a good way to do this, passing through only valid words in between (this website has some examples)?

Valid here means "a word in English" as this is the domain I consider.

My current idea is that I could use a shortest path algorithm with the Hamming distance for edge weights. The problem is that it will take a long time to build the graph, and even then the weight is not so precise in terms of distance (though it will never underestimate it) unless the weight is one, so I would probably have to find a to build a graph that only had weights of one.

What would be the easiest way to build the graph? Am I taking entirely the wrong approach?


texts:
I'm trying to understand the Bloom filter, and how it works, In particular, the subject that I use the bloom filter is the networking world store a large number of URLs.
I understand that the Bloom filter is a boolean array, like the figure below, and it uses a k different random hash function.

I have difficulties to understand how a URL like "https://cs.stackexchange.com/" can be mapped inside this array. In other work, I apply a hash function to this string that represents the url and after I will check if the result is inside the bool filter data structure.
I can not imagine how this can happens.


texts: Scheduling to minimize the truncated gaps

texts:
I have a single job of unit length, a set of $n$ slots, and a budget of $B$ units. If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled for a period of $x$ consecutive slots, then a penalty of $\lfloor x/2\rfloor$ occurs. The objective is to schedule the job in order to minimize the sum of penalties.

For example, for $n=12$, if the job is scheduled at slot 1, at slot 3, at slot 6, and at slot $12$, then the sum of penalties is $\lfloor 1/2\rfloor + \lfloor 2/2\rfloor + \lfloor 5/2\rfloor = 0+1+2=3$.

Is this problem NP-hard?

I am trying to reduce the knapsack problem to it. Transforming the values in the knapsack problem to the penalties is somehow difficult, because once the job is scheduled at $t$, the penalty is initialized.


texts: Why does this triple loop code have a running time of 1.5lnN * N^2

texts: Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $\frac{1}{2} N^2$ term comes from, but I am completley lost on the $3 \ln N$ term. Unfortunatley this is the only solution.


texts: Why is it meaningless to say the runtime of an algorithm is at least in the order of n squared?

texts:
I would like to know why the following statement

  The running time of algorithm $A$ is at least $O(n^2)$

which means the best-case running time of $A$ is $O(n^2)$ is meaningless (CLRS page 53).

But the following is not

  The worst-case running time of algorithm $A$ is $\Omega(n^2)$

(used in CLRS page 160).


texts:
Suppose A∪B is NP-hard, does it follow that A is NP-hard or B is NP-hard?

Equivalently, is the property "not NP-hard" closed under union?

A related question was already asked:

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

but it seems no consensus was formed.


texts: How do we place $8n$ objects in a grid of size $n \times n$?

texts:
How do we place $8n$ objects on a square of size $n\times n$ in a form of grid such that no 4 of them form a rectangle with sides parallel to those of square? Each object occupies exactly one cell in the grid and two objects cannot occupy the same cell. We are given $n\geq 100$.

Example. The following can be a $7\times7$ portion of some large grid (say $200\times200$), where 0 and 1 denote empty and filled cells respectively):

0000111
0101001
0011100
0110010
1010001
1001010
1100100

What approach one should follow to solve the problem?

Source: codechef.com MAY Long challenge "Ada Rooks 2"


texts: any hope for a universal automatic parser?

texts:
Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and you want to make some guesses on the corresponding syntactic tree.

How would you try to achieve this, and would you have any hope to make it working on some toy problems ?

To be clear, the goal isn't to make a parser for 4 or 5 different (but similar) programming languages, but really to detect -from some examples- the regularity in how the data is structured, and build from it a syntactic tree, with the hope to generate a grammar, a syntactic parser and -let's dream- a semantic parser and an interpreter.

My thoughts : a major problem is that in general the grammar needed for parsing a given source code isn't LR(1), but only locally LR(1), and globally recursive. For example HTML contains some Javascript, itself containing some HTML+Javascript hidden in a string :

 ");
</scritp>

For parsing this, you need to generate a grammar for HTML and another one for Javascript, and generate a recursive grammar saying that sometimes in the syntactic tree (from one node to its child) it can jump from one language to the other.

Do you have any reference/idea on this problem?


texts: Concise way to say "increases with n or some term of n"

texts:
I'm writing a thesis proposal and one of the systems involved has unknown complexity. It's not a focus of the proposal, but I wanted to include a line like this, as speculation:

  Presumably the complexity of each new connection scales with the number of rules.

Unfortunately I don't know if asymptotic complexity (space and time) will be O($\log{n}$), O($n$), O($n\log{n}$) or even O($n^{99}$). But I do doubt that it will be constant, so increasing $n$ will have some effect on it.

What is a good, accurate way to write this concisely? I'm asking here and not at English Language and Usage because the CS accuracy is essential.


texts: What is the adjunct of the evaluation morphism in a closed monodical category?

texts:
According to the nlab article about evaluation map if $X, Y \in C$, a closed monodical category then the adjunct to evaluation morphism $[X, Y]\otimes X \rightarrow Y$ is the identity morphism $[X, Y] \rightarrow [X, Y]$.

Is that correct and if yes why?
Because it seems to me that the adjunct of such has to be $X \rightarrow [Y, (X \otimes Y)]$


texts: Why should we study all the three forms of representation of finite automata?

texts: DFA, NFA and epsilon NFA all the three allow us to represent a particular regular language. With any of those representations we can arrive to the same regular expression, then why do we need to study all the three form of representation of finite automata? There can some explanation on what NFA can do which DFA cannot , that is NFA might help us in designing uncertainties. For example in designing a game (chess), we have many options to move a particular piece from a particular location which can be easily represented using NFA. But what is the use of epsilon NFA when the same can done using NFA or DFA?


texts: Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

texts: Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. I wonder, why has there not been an encryption algorithm which is based on an known NP-hard problem. It sounds (at least in theory) like it would make a better encryption algorithm than a one which is not proven to be NP-hard.


texts: How do I compress data vectors in broadcast messages?

texts:
Let us model a wireless broadcast network as an undirected graph $G(V,E)$ where there is an edge between every pair of nodes ${i,j}\in V$ if they are in transmission range of each other. $w_{i\to j}$ is the weight of the link $i\to j$ which can be calculated only by transmitter $i$ and is unique to receiver $j$. All nodes periodically broadcast messages.
Each receiver needs to know all link weights associated to it to calculate $f(w)$. Expecting every node to broadcast a vector of weights associated to its neighbors would be infeasible as the vector size increases with number of nodes and does the size of data.
Question: What strategy/encoding can I adopt to reduce the size of broadcast data and at the same time each receiver can receive its own weight from the received broadcast messages?
Assumptions: weights are float/double values with unknown precision and nodes know ID and location $(x,y)$ of each other. Number of transmission per second is fixed.
Update: A system model picture is added for clarification.


texts:
(I originally posted this on stackoverflow but thought it would be a better fit here)

I'm trying to understand the Ketama hash code used in consistent hashing.

link and snippet below:

public static Long md5HashingAlg(String key) {
    MessageDigest md5 = null;
    try {
        md5 = MessageDigest.getInstance("MD5");
    } catch (NoSuchAlgorithmException e) {
        log.error("++++ no md5 algorythm found");
        throw new IllegalStateException("++++ no md5 algorythm found");
    }
    md5.reset();
    md5.update(key.getBytes());
    byte[] bKey = md5.digest();
    long res = ((long) (bKey[3] & 0xFF) << 24)
        | ((long) (bKey[2] & 0xFF) << 16)
        | ((long) (bKey[1] & 0xFF) << 8) | (long) (bKey[0] & 0xFF);

    return res;
}

I think I understand what the code is doing, but I don't get why they're doing it. Particularly, I'm wondering why:

the code discards the least significant 8 bytes of the 16-byte MD5 and uses only the first four (bKey[0] through bKey[3]).
the code "flips" the significant bytes meaning that, of the 4 bytes from 1., the least significant now become the most significant (at least that's what I understand happens from the & 0xffs and left shifts).

I also came across another piece of code that uses the same logic as above, but in addition performs an & 0xffffffffL on the result to "truncate to 32-bits".

link and snippet:

case KETAMA_HASH:
    byte[] bKey = computeMd5(k);
    rv = ((long) (bKey[3] & 0xFF) << 24)
        | ((long) (bKey[2] & 0xFF) << 16)
        | ((long) (bKey[1] & 0xFF) << 8)
        | (bKey[0] & 0xFF);
    break;
    default:
    assert false;
}

return rv & 0xffffffffL; /* Truncate to 32-bits */

Could someone help me understand the rationale behind picking these particular bytes and re-arranging them in this particular fashion?


texts: Beta reduction of S combinator in pure lambda calculus

texts:
S is defined as S x y z = x z (y z)
This suggest that (y z) should be evaluated just after x z and the the results of x z is applied to the results of (y z).
I'm implementing call by value in lambda calculus, I would need to support parenthesis when evaluating this expression right? Does this affect the results? I thought that the order would not matter, so why the parenthesis in (y z)?
Regards


texts: String to small integer mapping without collision

texts:
Is there any good approach to devise a mapping of limited number of strings $N_1 << 2^{15}$ to integers less than $2^{15}$ without conflicts?

Strings are quite often of the form of prefix + postfix, where both prefix and postfix may repeat.

The mapping should be stable in a sense that if the mapping needs to be extended by a new set of strings, then the new mapping works identically to the old one for "old strings". New prefixes and postfixes can be introduced in the extension. Postfixes and prefixes can be empty, but the string can't be. Two different strings can't point to the same integer, so the mapping is an injection.

Example:

  mapping("prefix1postfix1") -> 1021
  mapping("prefix1postfix2") -> 1031
  mapping("prefix2postfix1") -> 1121

One obvious approach is to just store the mapping, and assign sequential numbers to the new strings, but I wonder if there is some guaranteed way to go without "hash collisions" up to some fraction of the limited integer space without the need to memorize assignments? How it may depend on the numbers of prefixes/postfixes or their ratio?

I suspect there may be some very old research on this topic as well as the result may be negative, but still curious if there is some pleasant surprise.


texts: When should you use the existential and universal quantifiers for Relational Calculus?

texts:
Could someone explain to me WHEN do you use existential and universal quantifiers for Relational Calculus?

Given this schema:

Hotel(hotelNo, hotelName, city)

The expression below gets all hotel names based in London (expressed in Domain Relational Calculus)

$$\mathrm{HotelName|(\exists hNo,cty)(Hotel(hNo,hotelName,cty)\wedge cty=\,\,"\!\!London\!")}$$

Why does the existential quantifier required for this example? Wouldn't this be the equivalent {hotelName | (Hotel(hNo, hotelName, cty) AND cty='London')}

And why is only hNoand cty selected for the existential quantifier? What about the hotelName?

Source: Herts University - Advanced Database Course


texts: Problems that become far easier when restricted to only integer values

texts:
I know that there are some problems that are very hard to solve in general, but become much easier and asymptotically faster if restricted to only integer values.

One such example would be sorting which can be done in O(n+M) if only integer values are allowed.

Another example (I think) is the undirected single source shortest path problem which seems to be solvable in linear time if all weights are positive integers.

My question now is which problems are significantly easier to solve if restricted to integer values (and why?)

Note: I obviously don't expect a complete listing, I just want to understand the general principle behind the speed up by restricting the problem space to integers.


texts:
I have this example code, which is an undefined language.  We want to know what will be printed if we use static versus dynamic scope.

def fun1(a):
  var z = 1
  def sub1(c,e):
    def sub2(d):
      print(z)
    sub2(z)
    print(z)
  def sub3(b):
    var z = 2
    var s = 1
    sub1(z,2)
  sub3(z)
var z = 0
fun1(3)
print(z)

The solution says that under static scoping it will print 1 1 0 and under dynamic scoping it will print 2 2 0.

However, I thought in static scoping the variable bindings are always determined by the most global definition first.  Since z is bound to 0 in the global environment, I would think this always overrides any local bindings, and it should print 0 0 0.

If we use dynamic scoping my understanding is that there are two versions of dynamic scope: deep and shallow binding.  Deep binding refers to the binding at definition of the function, and shallow refers to the definition that exists at the call of the function.

If we use deep binding, then I would think: We first call fun1(3) and here z=1 for both sub1 and sub3.  We call sub3 and that calls sub1, and that defines sub2, then calls sub2(z).  At this point z should be bound to 1 so it prints 1, then prints z which is still bound to 1.  At the end of the program we print z which in the more global scope is bound to 0 so we get 1 1 0.

If we use shallow binding then since sub2 is called in sub1 we use the binding for z there.  Since that binding is defined in the call environment for sub1, and that was sub3's environment, then we find that z=2.  This is the binding both inside of sub1 and inside of sub2 so we get 2 printed twice.  Then in the global environment, 0.  All together, we get 2 2 0.

It seems to me like the person who wrote these solutions is confusing static scope with deep binding dynamic scope, and confusing dynamic scope with shallow binding dynamic scope.  Or am I the one misunderstanding terms?


texts: Proving that the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(2) = 1$ is asymptotically $O(n)$

texts:
I've already solved the recurrence exactly and found that $T(n) = n - 1$. Therefore, I know that $T(n) = O(n)$.
However, I'm having trouble showing that $T(n) = O(n)$ without solving the recurrence exactly.
My strategy so far has been to prove that $T(n) \leq cn$ ($c$ is a constant) $\forall n \geq 2$ via induction on $n$.
Clearly, the base case holds $T(2) = 1 \leq 2c$ as long as $c \geq \frac{1}{2}$.
For the inductive hypothesis (IH), I assume $\forall k < n$, $T(k) \leq ck$.
Finally, for the inductive step, I have
$$
\begin{alignat*}{2}
T(n) &= 2T\left(\frac{n}{2}\right) + 1 &&\text{ (by definition)}\\
&\leq 2c\left(\frac{n}{2}\right) + 1 &&\text{ (by IH)}\\
&= cn + 1
\end{alignat*}
$$
However, I can't conclude that $T(n) \leq cn$ from this. Where am I going wrong?


texts: Can a Turing machine or Push Down Automaton construct languages of type 3?

texts: I am not quite sure, whether automata can construct languages over their types. For example, a Push down automaton can construct a language of type 2 - does that mean that a PDA also can construct a language of type 3? The same for turing machine?


texts: Leverege sorting by two fields from known sorting index(gather or scatter) of each field

texts:
A little context. First of all gather index in my case contains position to sorted an array. For example for an array

array = [3, 2, 0, 1]

gather index will be

gather_index = [2, 3, 1, 0]

the following operation will produce sorted array

sorted_array[i] = array[gather_index[i]]

I need to do a sort by all pairs of fields in a cartesian product and apply some logic then.
More precisely if the first set contains fields

[a, b]

and the second

[c, d, e]

Data should be sorted 6 times by

[(a, c), (a, d), (a, e), (b, c), (b, d), (b, e)]

that operation has O(N*M) complexity(N,M sizes of sets not a sorted array).

I'm curious can we somehow reduce it to O(N+M) or anything less than O(N*M) by using gather(or scatter) sorting index?
First sort data by each fields to get indexes. Then use it to get data sorted by two fields.

Let's say array is a matrix with a few columns(a, b, c, etc). My question can be rephrase like Can I sort it by a_and_b in a cheaper way than just sort by two columns directly if I already know gather index(sorting index) that sort by 'a' and 'b' separately.


texts:
How can I encode an ascii string in base 15?

In other words, I have the following characters available:

0123456789abcde

I have no idea how to do this. What do you suggest I do?

(If this is not on-topic, please migrate.)


texts:
I've seen a numerous interesting abstract machines (i.e. CESK) and evaluators (diverse meta-circular S-expression evaluators, i.e. vau, COLA) and other models (concatenative, SK/Lambda calculus) which implement some novel(?) computational ideas, but almost every time each model boils down to:

Executing a stream of primitives (from a fixed set) and giving means to combine/compose them.

And the only method of composing/reusing that I've ever seen is a function CALL (aka basic form of application, i.e. without talking about environments and other complex stuff).

Are there any alternative methods/theories? Unfortunately, I couldn't find anything on scholar google.


texts: Why Kosaraju's algorithm cannot use original graph by increasing finish time?

texts:
I saw this post, and it explains about why kosaraju's algorithm includes transpose graph $G^T$.

But, I totally didn't understand why cannot use increasing order of original graph. Kosaraju's algorithm uses decreasing order of transpose graph.

Is there an any counter example about this? I'm really confusing.


texts: The maximum & minimum number of sources that can be multiplexed so that no data loss occurs on TOKEN BUCKET?

texts:
A link of capacity 100 Mbps is carrying traffic from a number of sources. Each source generates an on-off traffic stream; when the source is on, the rate of traffic is 10 Mbps, and when the source is off, the rate of traffic is zero. The duty cycle, which is the ratio of on-time to off-time, is 1 : 2. When there is no buffer at the link, the minimum number of sources that can be multiplexed on the link so that link capacity is not wasted and no data loss occurs is S1. Assuming that all sources are synchronized and that the link is provided with a large buffer, the maximum number of sources that can be multiplexed so that no data loss occurs is S2. The values of S1 and S2 are, respectively,

A)  10 and 30

B)  12 and 25

C)   5 and 33

D)  15 and 22

I have solved the part (i) of the problem to find the minimum no. of stations & got 10 as there is no bucket,so for no data loss I equated the incoming traffic rate by S1 stations = Maximum capacity of the channel.In 2nd part I'm having trouble what will happen when a buffer is placed.Please help.Make me correct if 1st part is not correct.


texts: Is logical to physical address conversion inclusive?

texts:
If I am trying to translate a logical address of page N and offset O, and my translation unit tells me the translation has a base address of B and a length of L, is the length L inclusive or will it trap the OS?
Basically is the address valid if 0 <= O <= L or if 0<=O<L


texts: Is my proof for a context free language correct? Same number of a's as b's

texts:
I have the following grammar G:
$$
\begin{align*}
&S \to aB|bA \\
&A \to a|aS|bAA \\
&B \to b|bS|aBB
\end{align*}
$$

I am going to prove that this language L(G) consists of words with the same number of a's and b's by strong induction.

Inductive hypothesis: $S$ produces $m$ $a$'s and $m$ $b$'s, $A$ produces $m+1$ $a$'s and $m$ $b$'s, $B$ produces $m$ $a$'s and $m+1$ $b$'s for some integer $m$.

Base: The smallest string produced by $S$ is $ab$ or $ba$. The smallest string produced by $A$ and $B$ is $a$ and $b$ respectively. All three satisfy the IH.

Induction: Assume the inductive hypothesis is satisfied for all strings of length $k$ or less.

For strings of length $k+1$:

(1). $A\to aS$; then $S$ inductively derived a string of length $k-1$ with same number of $a$'s as $b$'s. Since $A$ is initiated by $S\to bA$, we concatenate that $b$ plus the $a$ in $aS$ and we get a string of length $k+1$ with same number of $a$'s as $b$'s.

(2). $A\to bAA$; then each $A$ on the right hand side has one more $a$ than $b$. Since $A$ is initiated by $S\to bA$, we concatenate that $b$ plus the $b$ in $bAA$ and we get a string of length $k+1$ with the same number of $a$'s as $b$'s.

Can I continue for $B\to bS$ and $B\to aBB$? Am I totally wrong here?


texts: Algorithm to determine if a number is perfect on a Turing Machine

texts:
I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it works, this particular algorithm is being really hard for me to develop.

The algorithm I'm trying to implement on the TM is basically this (on C, returns true iff n is a perfect number):

int main(int n) {
  int i=1, sum=0;

  while ( n > i ) {
    if ( n % i == 0 ) {
      sum = sum + i;
    }
    i++;
  }

  return sum == n
}

The tough part for me right now is the while(n>i) loop and the n%i inside it.

Since I already have a program that does a%b, I was trying to build the TM graph around it, but I'm not sure it's the best idea, specially since the b on this case changes on every iteration. The software I'm using to simulate the TM is called JFlap.

The algorithm on table or graph form would be perfect.


texts: Algorithm for optimal rule-based arrangements?

texts:
I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as defined in this table(I have one of each):

Num Vegetable     Friends      Foes
1   Watermelon    7,4,3        8,6
2   Tomatoes      9,8,6,5,1    7
3   Sunflowers    7,6,11
4   Zucchini      9,7,3
5   Eggplant      9,6,2        7,10
6   Cucumbers     9,7,3        8,1
7   Corn          8,6,4,3,1    5,2
8   Cantaloup     7,4,3        6,1
9   Bell peppers  6,5,11,10,2
10  Swiss chard   2            5
11  Rhubarb       9,3

How do I find the arrangement? Sort them using an algorithm? The title was my best guess at the answer. I am trying to understand the thought process and the implementation.


texts: What is the best algorithm for multiple matches?

texts:
What is an algorithm that can find the best possible matches given a set of data. I have read up on stable roommates problem and or stable marriage problems. However, from my understanding, these type of algorithms only output a specific match (pairings) and not a set of possible matches. For example, say we have a group of users each with a desire to trade one particular fruit for another.

[] - Has/Have
() - Wants

User 1:
[Apples, Bananas]
(Grapes)

User 2:
[Bananas, Grapes, Peaches]
(Apples)

User 3:
[Grapes, Oranges]
(Bananas)

User 4:
[Mango, Pineapple]
(Strawberry)

User 5:
[Raspberry]
(Pineapple)

User 6:
[Pineapple]
(Raspberry)

In this scenario, matches should be (->)

     User 1 -> (User 2 and User 3)
     User 2 -> (User 1)
     User 3 -> (User 1)
     User 4 -> None
     User 5 -> (User 6)
     User 6 -> (User 5)

Irving's algorithm requires that a solution have a unique pairing. What is an algorithm that could give me a solution set like above?


texts: What is the order of magnitude of bitwise operations involved in a SHA-256 hash?

texts:
Specifically, how many bitwise operations (approximately, could be just order of magnitude) occur each time a Bitcoin ASIC miner performs a SHA-256 hash in typical mining computation, i.e. as it guesses the nonce and computes the hash of the 1 MB block to be added to the blockchain?
By bitwise operation, I mean the most simple state changes that occur on each bit.


texts:
For a given sufficiently strong formal axiomatic system $\mathsf{F}$ (like $\mathsf{PA}$ or $\mathsf{ZFC}$) and any given function $p^*(x)$ that can be specified within the formal system $\mathsf{F}$, Hutter's algorithm $M_{\mathsf{F},p^*}$ computes the function $p^*(x)$ nearly as quickly as any (provably quick) algorithm $p$ provably computing $p^*(x)$. More precisely

  Let $p$ be any algorithm, computing provably the same function as $p^∗$ with computation time provably bounded by the function $t_p(\xi)$ for all $\xi$. $time_{t_p}(x)$ is the time needed to compute the time bound $t_p(x)$. Then Hutter's algorithm $M_{\mathsf{F},p^∗}$ computes $p^∗(x)$ in time
  $$time_{M_{\mathsf{F},p^∗}}(x) ≤ 5·t_p(x)+d_p·time_{t_p}(x)+c_p$$
  with constants $c_p$ and $d_p$ depending on $p$ but not on $x$.

Here "provably" means that a proof can be found in $\mathsf{F}$. The algorithm could be interpreted as a generalization and improvement of Levin search, but I wonder whether it is always an improvement.

Can we use the formal system $F$ to construct a function $p^*$ for which Hutter's algorithm $M_{\mathsf{F},p^*}$ performs badly? How about asking whether a short proof of $\bot$ (i.e. a contradiction) can be found in $\mathsf{F}$? A short proof would be a proof with fewer than $n$ symbols, and we would use $x$ to encode $n$ in binary form. The function $p^*$ would just be a brute force search for the contradiction.

I think this should give a problem in $NEXP$, but the optimal algorithm to compute $p^*$ would have complexity $O(1)$, because the answer is always "no". But $M_{\mathsf{F},p^*}$ will take double exponential time in the length of $x$ to arrive at that conclusion, if I'm not mistaken. Now I wonder whether there are more interesting ways to make $M_{\mathsf{F},p^*}$ look bad, perhaps similar in spirit to Rice's theorem?


texts: Pointers to schema evolution and semi-automated instance migration

texts:
QUESTION EDITED

Since this question wasn't clear, I'll rephrase. See question-history for original.

I'm looking for academic papers that describe schema evolution on documents (1) in a generic way. More specifically some questions I'm hoping to see answered in part: given a schema A and documents adhering to schema A:

what type of atomic 'change-operations' may occur on schema A for instances of schema A to be compatible with the newly created schema A+.
in general terms, does an exhaustive list of these 'change-operations' (A) even exist (theoretically) or (B) would this be db-dependent? Intuitively I think the answer is (A)
Assuming (A) any pointers to such a list? (2)
Given a schema A and a schema B, is it possible to deconstruct the delta  between these two schemas to their atomic 'change-operations'?
Given the above, theoretically, it seems possible to either:

do automatic migration of all instances of schema A to adhere to A+
list where manual intervention is needed because of incompatibilities.

1) with documents I mean objects generally stored in nosql document-databases. I.e.: objects with complex types / nesting. The misplaced term nosql I used in the original question was an attempt to point this out.

2) Although pretty old Recent advances in schema and ontology
evolution is an example of what I'm looking for. It illustrates a couple of 'change operations' as follows (through Moto et. al 2007 specifically mentioning Xml schema changes, copied verbatim) :

  Add a new optional or required element to a type
  Delete an element from a type
  Add new top-level constructs like complex types
  Remove top-level constructs
  Change the semantics of an element without changing its syntax – for instance, if the new version of an application treats the implicit
  units of a column to be in metric where previous versions did not
  Refactor a schema in a way that does not affect instance validation – for instance, factoring out common local type definitions into a
  single global type definition
  Nest a collection of elements inside another element
  Flatten an element by replacing it by its children
  Rename an element or change its namespace
  Change an element’s maximum or minimum multiplicity
  Modify an element’s type, either by changing it from one named type to another or adding or changing a restriction or extension
  Change an element’s default value
  Reorder elements in a type

Clearly this doesn't cover all change operations possible on a document schema. Missing for example are change-operations related to object-references.

Any pointers appreciated.


texts: How do I calculate the Nth result of a context-free grammar?

texts:
Given a context-free grammar and a maximum depth, how do I directly compute the Nth sentence without calculating or caching intermediary sentences?

Take as an example the following grammar:

(from http://www.nltk.org/howto/generate.html)

S -> NP VP
NP -> Det N
PP -> P NP
VP -> 'slept'
VP -> 'saw' NP
VP -> 'walked' PP
Det -> 'the'
Det -> 'a'
N -> 'man'
N -> 'park'
N -> 'dog'
P -> 'in'
P -> 'with'

Given a maximum depth of 4, it will deterministically generate the following 6 sentences:

0 the man slept
1 the park slept
2 the dog slept
3 a man slept
4 a park slept
5 a dog slept

So the brute force way of finding the Nth sentence is to compute sentences 0..N, discard them, then return the Nth. But with a more complex grammar it's wasteful to recompute it every time and it's not possible to hold the current state in memory.

But my question is, is there a way to directly compute the Nth sentence?

Also, is it possible to do the reverse: given a the grammar, depth, and sentence, determent what's the sentences index of all possible sentences.
Something like:

>>> find_index_in_grammar("a man slept", grammar, depth=4)
3

Update

To clarify: traversal order, lexicographical order, or ordering by length is not important as long as it's deterministic. The example above is just one possible ordering that is deterministic and would work.

What I've tried so far is to consider the grammar as a different numeric "base", with its sentences as specific numbers in that base. With the key difference being the "base" varies with the number of possible replacements at each branch in the grammar.

def grammar_index(grammar, index):
    sentence = [grammar.start()]
    while set(sentence) & set(grammar._lhs_index):  # any non-terminals?
        for i, symbol in enumerate(sentence):  # loop for the non terminal
            possible_replacements = grammar._lhs_index.get(symbol)
            if possible_replacements:  # if there is a replacement
                base = len(possible_replacements)  # the len of replacements is the "base"
                rem = index % base
                index = index // base
                replacement = possible_replacements[rem]
                del sentence[i]
                sentence[i:i] = replacement.rhs()
            if index <= 0:
                break
        if index <= 0:
            break
    return ' '.join(str(s) for s in sentence)

So this returns partially generated sentences with some duplicates as well.

Pros: it is deterministic, fast

Cons: has non terminals in the results...

>>> for i in range(20):
...:     s = grammar_index(grammar, i)
...:     print(i, s)
...:
0 NP VP
1 NP saw NP
2 NP walked PP
3 Det park slept
4 NP saw Det park
5 NP walked P Det park
6 Det dog slept
7 NP saw Det dog
8 NP walked P Det dog
9 a man slept
10 Det park saw Det man


texts: Replacement of a substring with another substring in a string

texts: I apologize if this is not the right stackexchange for this question. I was playing around with the Python programming language, when I discovered something strange. It concerns replacing a substring of a string with another substring. For example, in "spammy", replacing "mm" with "xx" results in "spaxxy". However, in "spammmy", replacing "mm" with "xx" results in "spaxxmy", not "spaxxxxy" or even "spaxxxy". My question is, what is the proper, rigorous definition of replacing in a string $S$ a substring $T$ with a substring $T'$?


texts: Comparing the sizes of two search spaces by comparing their numbers of possibilities

texts:
I am trying to solve an optimisation problem and come up with two Integer Linear Programming models. For each model, I am able to find a function that calculate the number of possibilities based on different variables, e.g. problem sizes.

I cannot directly conclude that one model has a smaller search space than the other. Instead, I develop an application that compares the actual numbers of possibilities between 2 models based on different values of the variables.

My application tries millions of different variables and shows that the number of possibilities of one model is less than the other 99% of the time. Is it enough to conclude that it is likely for one model to have the smaller search space, and to be solved faster than the other?


texts:
I want to create a matrix where each entry itself is a random matrix.
What would be a good way to represent this?

It is not necessary but some hints on how to implement your proposed solution in Python would be useful.


texts: Is the Rice Theorem applicable for these problems?

texts:
I have 1 problem :-->

L = { < M > | TM halts on no inputs }

I have solved the above problems by reductions given in the book and even there are many links in stackexchange site. I have no problems in the reduction method.

But, just trying to be more curious, I tried to solved these problems by using rice theorem. I know that rice theorem is applied on the property of languages and here it is property of TM's but i tried some conversion here .

Though, I am getting the right answer but i want to confirm is what i have tried is legal or Can It be solved like this ?

As the TM halts on no inputs, which means it is not halting on the inputs in the language as well as inputs not in the language.

So, I wrote it as

L = { < M > | L(M) = PHI }

which is surely a non trivial property and as well as non monotonic property, hence the language is Undecidable and as well as Non RE.

Well, I am new to this topic. So, i don't know whether I am right in the conversions or Can I assume something like this. Please correct me if i am being stupid .


texts: Number of instances of SAT (boolean satisfiability) problems of size N?

texts:
I assume the size of an instance of the SAT problem is measured by its number of (Boolean) variables.  What is total number of instances of SAT problems of size N?

I guess that amounts to counting the number of "distinct" formulas that can be formed by N boolean variables, using a normal form such as CNF or DNF.

Update:  this question is partly answered for the 3SAT case:
https://cstheory.stackexchange.com/q/2168/15553

and the number of distinct clauses is:
$$ C = 2N \times 2(N-1) \times 2(N -2) / 3! = 4 N(N-1)(N-2)/3 $$


texts:
A inference system is a set of rules that can be used to prove something in some formal model. I understand that.

But what does it mean to a inference system to be local?

For instance, in the page 36 of these MPRI notes there is the following definition:

Definition 4.2 (locality) Let $I$ be an inference system. The system $I$ is local if whenever $T ⊢ u$ in $I$, there exists a proof $\Pi$ of $T ⊢ u$  such that $Steps(\Pi) \subset st(T \cup \{u\})$.

But I am not able to understand this definition because even if I know that  $st(T\cup\{u\})$ is the set of subterms of $T \cup \{u\}$, I don't know what is $Steps(\Pi)$.


texts: Generative Machine Learning algorithms on tree structure

texts:
I'm looking into PCFG sentence grammar dependency structure parsing using StanfordNLP PCFG parser. It generates tree structures represented as a string like this:

 Happy new year => (ROOT (VP (VBN Happy) (NP (JJ new) (NN year))))

Or in a more visual way, the tree structure looks like this:

(ROOT
  (VBN (JJ Happy)
    (NP (JJ new) (NN year))))

Since some machine learning algorithms are generative, and I'm wondering if I group tree structures into two sets: one set contains sentences with negative emotions, one set on positive emotions. Can I use the machine learning algorithm to get the most commonly occurred subtree structure within each set?

I'm very sorry if I caused any confusion. First of all, I want to know if this problem is solvable in the realm of machine learning.

Remember topic modeling? Where the algorithm reads large chunks of text and generate similar topics and return keyword strings grouped together as a topic? One topic could be: Gun, ship, sailer, ocean, fish, war, Gulf, oil

It provides an insight into what computer understands what this document might be talking about, so we can compare it with what humans think.

However, what I want to do, is ask the question if I can find common syntactical subtree structures in a sentence that might indicate the attribute of this sentence: negative or positive.

No, I am not asking for a sentiment analysis classifier, and that is not my interest at all.

For example, (this is an unpublished study right now), as us humans, we can say certain things about the future, and it will appear in a special structure, like "I will go to the mall" or "I'm going to jogging." You can see that "will" or "going to" might appear in many sentences, and serve as a common grammatical/syntactical structure. Those structures can be spotted by us human beings (namely linguists), however, is it possible to let machine find such common pattern?

I know in data science, or in realm of machine learning, people use algorithms to find/generate common patterns. I can group my parsed sentences (as tree structures represented above) into two groups: negative group and positive group (NOT emotions, just names for two groups), and then I want to use this algorithm to see if one or multiple subtree structures are very common among the group so I can extract them out.

As I stated before, I only need two things:

Is this solvable in Machine Learning realm?
If it is, which algorithm should I use?


texts: What is the procedure for converting this finite automaton into a regular expression?

texts:
Could someone provide an explanation of how to convert this DFA into a regular expression? I have found three methods online, ie: How to convert finite automata to regular expressions?

but they are all very confusing to me.

The automaton is:

$$M = ((1,2,3), 1, \{a,b\}, \delta, \{1,3\})$$
where

$$\delta(1,a) = 2\\
\delta(1,b) = 2\\
\delta(2,a) = 2\\
\delta(2,b) = 3\\
\delta(3,b) = 2\\
\delta(3,a) = 1$$


texts: What problem is this application of simulated annealing trying to solve?

texts:
I was reading about simulated annealing on its Wikipedia page, and was drawn to a particular example illustrating the annealing schedule. Below is the picture and its description:

Example illustrating the effect of cooling schedule on the performance of simulated annealing. The problem is to rearrange the pixels of an image so as to minimize a certain potential energy function, which causes similar colours to attract at short range and repel at a slightly larger distance. The elementary moves swap two adjacent pixels. These images were obtained with a fast cooling schedule (left) and a slow cooling schedule (right), producing results similar to amorphous and crystalline solids, respectively.

I am drawn to this particular problem – that of rearranging pixels using this algorithm – for its connections to crystal formation, but I am finding it impossible to find a starting point to learn more about it on the internet. I know this is an unconventional question but I would like to know what this particular problem is called or the greater context it belongs in.


texts: Is there a described algorithm converting _from_ Continuation Passing Style?

texts:
Continuation Passing Style (CPS) is a form of code where the control is passed explicitly, by passing the continuation of the code at each call point, unlike direct style.

There are many descriptions in the literature for how to convert from direct style to CPS. The following pseudo-JavaScript:

function direct() {
    var a = foo(1);
    return bar(a);
}

becomes:

function cps(cont) {
    foo(1, function(a) {
        bar(a, cont);
    }
}

But are there any descriptions of the reverse transformation, where the CPS representation is taken back to a direct style?


texts:
So in a recent algorithm contest I was given a task to create an algorithm that could construct a rectangle out of n triangles.

The information that is available to me is:

Width and height of the rectangle
Coordinates of all three corner points of each triangle
All triangles have to be used that are given
Triangles cannot be rotated
Triangles cannot overlap
It is always possible to construct a rectangle from the given triangles

I've spent some time googling for algorithms that could help me get started but I found nothing. So my question is, how do I go about solving such problem?


texts: Turing machine that accepts language with more a's than b's

texts: I am doing an assignment for my 1st year langauges and automata class. I have been having trouble with the last question which is this: Create a Turing machine that acccepts more a's than b's. I think I am supposed to pair the a's and b's together and then do some more but I can't wrap my head around it. Would help greatly if someone can post the algorithm and explain a little.


texts: Identical register input operands in assembly

texts:
The question is not specific to any processor.
Can I have an assembly instruction, like:
 ADD R1 R0 R0

R1 is the destination.
My understanding is that, if the register file in a processor supports 2 simultaneous reads in a clock cycle (i.e. 2 read ports), two different registers can be read. But for 2 same input registers, this case has to be handled explicitly wherein the input can be duplicated after reading the first operand, and if that is not supported, the register file MUST have 2 read ports in one clock cycle, if not it might lead to a structural hazard.
I would like to know if my understanding is right.
EDIT:
And also do, any processors (current/old) handle this case, explicitly.
Thanks in advance.


texts: Optimization problem in a social network

texts:
I would appreciate anybody's help with a problem I am trying to solve.

A little background:

given is a social network consisting of people represented as a directed graph, with edge from person A to person B if person A is a follower of pers B on that network. For any set S of people, we say that S reaches all people who are followers of at least one person in S. Everyone is a follower of themselves so any set of people S reaches at least itself

Problem:

The optimization version of this problem is as follows: given a social network and
a parameter k, compute the maximum possible number of people that can be directly reached
by up to k (observers).

The search version of the problem is to compute a set of up to k observers, which reaches the
maximum number of people.

Show that given a hypothetical algorithm for the decision version of the problem, both the
optimization and search versions of the problems can be solved with at most a polynomial
overhead (i.e., if the algorithm for the decision version takes O(T(n)) time on instances of size n then the optimization and search versions can be solved in O(T(n)c) time for some constant c).


texts: Example of reduction in communication complexity

texts:
Let us assume the standard situation in communication complexity with two players $P_1,P_2.$

We have a function $f:[n] \times [n] \mapsto \{0,1\}$ that both players known in advance. They wish to compute  $f(x,y)$ given that the first player only knows $y$ and the second player only knows $x.$ The communication complexity of $f$ is the smallest number $k$ such that $P_1,P_2$ can always compute $f(x,y)$ communicating at most $k$ bits of information to each other.

If $f$ is the equality function (that is $f(x,y) = 1$ if and only if $x = y$) then I know that $P_1,P_2$ need to exchange at least $\log_2{n}$ bits in order to be able to always compute $f.$

Consider now the function $h_n:[n]\times[n] \mapsto \{0,1\}$ such that $h_n(x,y) = 1$ if and only if $x+y = n.$ I would like to show that $P_1,P_2$ cannot compute $h$ using fewer than $\Omega(\log{n})$ bits and the idea is to use the fact about the communication complexity of computing  $f.$

Hence I am wondering how to make a reduction in this case?

Suppose we can compute $h_n(x,y)$ with fewer than $\Omega( \log{n})$ bits. Can we somehow simulate such a protocol in order to be able compute $f$ using less than $\Omega(\log{n})$ communication bits?

Player $P_1$ receives the string $y$ and $P_2$ the string $x.$ Now $x = y$ if and only if $x+y = 2x = 2y.$ Hence they could simulate the algorithm for computing $h_{2x}(x,y).$ The problem that I see here is that in this reduction $h_n$ is not fixed in advance and may not even define the same function for $P_1,P_2$  (if $x,y$ actually differ).

Hence I am wondering

  How can one show that $h_n(x,y)$ cannot be computed communicating fewer than $\log_2{n}$ bits ?


texts:
Recently I am reading a document [1]. In this document, Prof. Cook provides a brief proof of $\mathbf{P} \subseteq \mathbf{NP}$, which is only one sentence:

  It is trivial to show that $\mathbf{P} \subseteq \mathbf{NP}$, since for each language $L$ over $\Sigma$, if $L \in \mathbf{P}$ then we can define the polynomial-time checking relation $R \subseteq \Sigma^* \cup \Sigma^*$ by
  $$R(w, y) \Longleftrightarrow  w \in L$$
  for all $w, y \in \Sigma^*$.

I know the definitions of $\mathbf{P}$ and $\mathbf{NP}$, as in [1], but I still can't understand this proof. Could any one explain the proof to me? Even one sentence is good.

By the way, I think $\Sigma^* \cup \Sigma^*$ should be $\Sigma^* \times \Sigma^*$. Am I right?

Reference

[1] S. Cook, The P versus NP problem, [Online] http://www.claymath.org/sites/default/files/pvsnp.pdf.


texts: Would switching the accept and reject states of an LBA A create a new LBA we'll say A' in which the language of A' is the complement of the language of A? I believe the answer is yes just by working out an example...but I'm not sure on a solid proof...nor am I sure if the fact that I am working with an LBA vs a regular turing machine makes a difference in this case.


texts:
I wonder how or why Avalanche Effect got its name.

Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (for example, flipping a single bit), the output changes significantly (e.g., half the output bits flip).
(source: Wikipedia)

But I feel like this definition has nothing to do with its name. If I asked what is avalanche/snowball effect, I would probably think of something which starts small but exponentially grow out of control.


texts: How to best model multidimensional, continuous, non-convex "shape" as neural network?

texts:
I have:

set of n-dimensional points that I know are inside of the shape
n >= 18, range on all dimensions has upper bound and lower bound (no axis goes to infinity).
shape is pretty large in this n-dimensional space, occupies roughly 10-50% of the whole space volume
knowledge that the shape is continuous, but it's definitely non-covex - has dents, has sealed bubbles inside it.

I wan't to have a model that can tell me fairly quickly if given point is inside of the shape or outside of it. Better yet a model that when a point is inside shape, can tell me, how close the point is to a shape contour.

I'm guessing neural networks would be good tool for this. What specific parameters of the network and the methods of learning would you recommend?

I'm fairly new to machine learning and neural networks.

Additional remarks:

Points that I have to determine the shape are not random, they lie on some lines in n-dimensional space and I can decide how to shape these lines when I gather data.
I'd like to avoid, false negatives, points that are guessed to be inside the shape but they actually aren't. False positives are way less troublesome for me. If some point that's inside of shape is guessed to be outside of it, then almost nothing bad happens if it's random or close to the shape boundary.
I probably could get additional information for my data points. Additional number that is likely to be higher if the point is on or near the boundary.

Additional information that might provide a clue about the shape:

if n would be 1 then the shape would always be line segment
if n would be 2 then the shape would never have holes
you can always get from one point of the shape to any other by some continuous trajectory, shape never consists of more than one part
the practical problem I'm trying to solve is that I have a hexapod robot with 3 motors on each leg and I wan't it to model allowed positions of motors so that the body of heaxapod robot won't collide with itself - that's the inside of my shape, boundary is when I try to move the legs to position where they collide with the body (or themselves), the outside of the shape is all positions where I can't go because body of robot is rigid and by trying to go there persistently would damage robot.
that's the concrete robot: http://www.theoldrobots.com/images20/bioloid3.JPG but I'd like to have general enough modelling and learning setup so I can use it for other robots with different number of motors and legs.


texts: Dynamic length of union of segments (1d Klee's measure problem)

texts:
Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of their union. There is a simple $O(n \log n)$ solution involving sorting endpoints of all intervals and then iterating over them while keeping track of some counters.

Now let's look at a dynamic variant of this problem: we are receiving $n$ segments one after another and the task is to find the length of the current union of segments after each new segment arrives. It seems like a natural generalization, however, I cannot find much information about this version of the problem. I wonder if it is still possible to solve this problem in $O(n \log n)$ time in an offline setting, i.e. when we are given all segments beforehand and can preprocess them in some way before giving an answer for each segment.

I feel like a modification of a segment tree might be useful here. In every node we need to keep track of both the total sum of lengths of segments (or their parts) corresponding to this node and the length of their union. However, I cannot figure out how to implement this modification without performance of one update degrading to linear time in some cases. Maybe using a segment tree is not the right approach and a better way exists.

Update:

What if we make the problem even more difficult by also allowing to delete previously added segments? Can it still be solved offline in $O(n \log n)$ time where $n$ is the total number of add/delete segment queries?


texts: How to define a TM which writes all the tape alphabet, when the number of states is independent of the tape alphabet size?

texts:
Given tape alphabet $\Gamma = \{\gamma_1  ,...,\gamma_n\}$ I wish to define a single-taped TM which given the input $\varepsilon$ writes the string $\gamma_1 \gamma_2...\gamma_n$ on the tape, and the number of states it (the TM) is using is independent of $n$.
My problem is that each time the head takes a right step and encounter a blank, It seems like the problem is just starting all over again, i.e  in order to continue I need to define a new state which acts differently on blanks in order to write a new letter which wasn't written by the previous states.


texts: Binary Equivalent vs. Computer code(Ascii or UTF)

texts:
Does computer convert every stuff using Ascii or UTF?
Meaning if there is a mathematical calculation including 65 (as a number) will it convert it into binary (00100001)?
And then how it differentiate it with 'A', whose code point is also 65 with code 00100001?


texts: What makes a nested function in gcc so complicated?

texts:
Disclaimer: I'm not a compiler expert, but some of my best friends are!  :)

I do a lot of embedded systems programming where stack (and other memory) is limited.  Most of my code is written in gcc, so I thought nested functions could be useful for reducing stack usage.  Here's an example of what I had in mind:

(Though the algorithm isn't important for this question, assume that list_traverse takes a pointer to a list head and a function.  The contains_aux() function gets called with each element in turn.)

bool list_contains(list_t *head, list_t *item) {
  bool found = false;
  void contains_aux(list_t *list) {
    if (list == item) {
      found = true;
    }
  }
  list_traverse(head, contains_aux);
  return found;
}

I assumed that the nested contains_aux() function would be able to directly reference its lexically closed variables (found and item).  But I was wrong.

Instead, looking at the generated code, I see that it installs some sort of trampoline function on the stack and calls that before getting to the contains_aux() function.

I know that contains_aux() can't share the same stack frame as list_contains() because there's an intervening function on the stack (list_traverse()), but -- geez -- it seems like the compiler could pass the frame pointer from list_contains() so contains_aux() could access its locals.

Is there a reason it doesn't work this way?  Is there a way I could torture the compiler into doing that?  Or should I just resign myself using un-nested functions and passing a "context" object to contains_aux()?


texts: Subgraph Isomophism Problem - Color Coding Technique - Proof Sketch

texts:
I am reading the paper Color Coding by Alon, Yuster, and Zwick. They state a theorem (6.3) that says if $H$ is a graph on $k$ vertices with treewidth $t$ and $G = (V, E)$, then a subgraph of $G$ isomorphic to $H$ can be found in $2^{O(k)}V^{t+1}$ expected time. They do not include a proof, but do state that the proof is similar to the case where $H$ is a forest (namely theorem 6.1, which they do provide a proof of).

As I am trying to understand how they algorithm would work for graphs of bounded treewidth, I was wondering if anyone could provide a proof sketch of the algorithm, as I don't see how it would be similar to the proof of 6.1 - Any help would really be appreciated, as this is for a course project, and I am having difficulties figuring out the algorithm.

A copy of the paper can be found here: http://www.tau.ac.il/~nogaa/PDFS/col5.pdf


texts: Is the Java 8 Grammar still a LALR(1) grammar?

texts: As I found out here: http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html , the Java Version of 2005 (might be Java 6, I'm not sure) is a LALR(1) grammar. However, I couldn't find out if the Java 8 grammar still is a LALR one. I found some Java 8 grammar on GitHub (https://github.com/antlr/grammars-v4/blob/master/java8/Java8.g4 ), however, I couldn't parse this file with jikespg like they did on the eclipse site I linked above. Is there another tool which I can try out?


texts: Does a language stay regular if you re-encode the input?

texts:
$\tau$ be a transformation that, applied to a word of $\Sigma_a^\star$, replaces each character with a word from a possibly different $\Sigma_b^\star$ and concatenates the resulting words. For instance, given a $\tau$ with the following translation table:

A -> AA
B -> AB
C -> BA
D -> BB

$\tau(ABC)=AAABBA$ and $\tau(DACB)=BBAABAAB$. Note that the words may not all have the same length. A translation table such as

A -> FOO
B -> BAR
C -> BAZ
D -> QUUX

is also valid.

Now, is $\{w'|w\in L\land w'=\tau(w)\}$ regular iff $L$ is a regular language as well?


texts: Recurrence formula for a known sequence?

texts:
Problem: How do we can generate some mathematical close form of the following sequence, which has following 256 entries:

1   7   7   7   7   9   9   9   7   9   9   9   7   9   9   9   7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15

Origin/background of Problem:
                              These number are generated from a divide and conquer algorithm. For example if we have a 8 bit binary-string and we are asked to find the location of 1's in minimal number of questions then, the above sequence is the # of questions asked for each possible binary 8-bit word i.e from 00000000, 00000001 ....11111111 the corresponding # of questions are elements of above sequence i.e 1,7,..15, respectively.

Algorithm:

Lets take 0000 0001, for instance:

1) First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.

2) Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?

3) Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide  this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.

4) This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.

So, I asked a total of 7 questions to find the location of 1 in a binary word of 0000 0001. Similarly, we will go through other binary words.


texts: Finding the Shortest Path that connects k nodes in a graph

texts:
I was wondering if there are algorithms for finding the shortest path that contains some selected $k$ nodes in a weighted graph. More specifically, the path that we are looking for needs to pass through all the $k$ nodes, but can contain other nodes from the graph and can visit those $k$  nodes in any order. In addition, any node can be traversed more than once. Also, the path has to start and end with two distinct nodes from the given set of $k$ nodes. For example, if $k=2$, we have two nodes, $u_1$ and $u_2$, and are looking for the shortest path from $u_1$ to $u_2$. We can use UCS or $A^*$ to solve this. If $k=3$, there will be three nodes: $u_1$, $u_2$, and $u_3$. The path can start in $u_1$, pass through $u_2$, and finish in $u_3$, or start in $u_2$, pass through $u_1$, and end in $u_3$, etc. $k$ can take any value from $2$ to $n$, $n$ being the total number of nodes in the graph.

To me, this somewhat looks like a problem of finding the minimal tree whose leaves are those $k$ nodes. A path passing through the leaves could then be obtained by traversing the tree in an appropriate order.