texts: Estimated vs actual period in Two-Way string search

texts:
Both the original paper and all implementations I've seen of the Two Way string search algorithm estimate the period of the needle as $\max(|u|,|v|)$+1 (where $u$ and $v$ are the critical factors). However, this seems to be throwing a lot away; the estimated period is the amount you get to skip forward upon a mismatch in the left side, and in the worst case it's off by a factor of 2 (consider for example a needle of the form $c^ndab^n$, which factors as $u=c^nd$, $v=ab^n$, but has period $2n+2$ vs $n+2$).

Is there a good reason not to prefer just computing the exact period of the needle directly?


texts: Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution

texts:
I have to solve this using the substitution method.

Floor functions cannot be skipped.

IH: Assume that $T(k) \geq  ck\log(k) $ for all $k \leq n$, where c is a constant.

IS: Must prove $T(k) \geq  ck\log(k) $

Proof:

\begin{align*}
T(n) &= 2T(\left \lfloor{k/2}\right \rfloor ) + k\\
     &\geq 2 c\left \lfloor{k/2}\right \rfloor\log(\left \lfloor{k/2}\right \rfloor) +k
\end{align*}

We now have two cases: $k$ is even and $k$ is odd. It is easy to prove this case when $k$ is even, however I run into trouble when $k$ is odd.

When k is odd, $\lfloor k/2\rfloor = (k-1)/2$, which gives

\begin{align*}
T(n)&\geq 2 c\tfrac{k-1}2\log(\tfrac{k-1}2) +k\\
&=  c(k-1)\big(\log(k-1)-1\big) +k \qquad\qquad\text{(Since $\log2 = 1$)}\\
&=  c\big(k\log (k-1) - k -\log(k-1) + 1\big) +k\\
&=  ck\log (k-1) - ck -c\log(k-1) + c +k\\
&=  ck\log k  + ck\log\big(1-\tfrac{1}k\big) - ck -c\log(k-1) + c +k\,,
\end{align*}
where the last equality is because $\log(a-b) = \log\big(a\big(1-\tfrac{b}a\big)\big)$.

And here is where I am stuck. I have gotten the $ck\log k$, but cannot find the $c$ that will let me finish the problem.

Any help would be appreciated.


texts: Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e

texts:
An example from Sipser's book, Introduction to the Theory of Computation, shows that it is not decidable for a $TM$ to recognize whether a $CFG$ (or a type 2 grammar) generates $\Sigma^*$, where $\Sigma$ is the alphabet. Call this language $CFG_{all}$

But the above language is also not computably enumerable.  There can be a reduction from $CFG_{all}$ to $\bar{A_{TM}}$, where $\bar{A_{TM}}$ is the language s.t. the input $TM$ does not accept any input. $\bar{A_{TM}}$ is not computably enumerable.

But could we say that whether or not a type 3 grammar generates $\Sigma^*$ is also not c.e. ? (since type 3 grammars are a subset of context-free grammars). While it is true that a finite automaton can recognize $\Sigma^*$, this language is different right from whether a type 3 grammar generates $\Sigma^*$?

Just to clarify the source of my confusion, in summary, it is decidable for a $TM$ to decide whether a pushdown automaton recognizes $\Sigma^*$ or accepts any input, but it is not decidable or even computably enumerable for a $TM$ to recognize that a CFG generates $\Sigma^*$. Similarly, it is decidable for a $TM$ to check if a finite automaton accepts $\Sigma^*$, but it may not be decidable for a $TM$ to check if a type 3 grammar generates $\Sigma^*$. It's somehow the difference between recognizing and generating.

EDIT: apparently for a pushdown automaton to recognize $\Sigma^*$ is not decidable


texts: If in all satisfying assignments all pair of variables can take all possible values is this tautology?

texts:
I suppose this is both easy and false.

Let $\phi$ be propositional boolean formula on variables
$x_1 \ldots x_n$.

Suppose in all satisfying assignments of $\phi$,
all pairs of variables $(x_i,x_j),i \ne j$ can take all possible
values, i.e. any of $\{(F,F),(F,T),(T,F),(T,T)\}$.

  Is $\phi$ tautology?

In case the answer is negative, is there simple characterization
of those $\phi$ which are not tautologies?


texts: Cantor's diagonal method in simple terms?

texts: Could anyone please explain Cantor's diagonalization principle in simple terms?


texts:
I have an even number of points, each with coordinates $(x, y, z)$. I need to group these points into pairs. The cost of pairing two points is the Euclidean distance between them. I'd like to find the optimal pairing such that the total cost is minimized. What would be a good way/algorithm to solve this?

For example, if you have points $\{a, b, c, d\}$, one possible pairing might be $\{a,d\}, \{b,c\}$. Points can only belong to a single pair.

My Ideas:
The problem seems similar to finding the minimum weighted bipartite matching for a graph. However, I'm not trying to match between two sets of points, just find pairs in a single set. It seems like you might be able to convert this problem to a bipartite graph by duplicating the set of points. This doesn't seem like the right way to do it though (seems like you'd be solving for each pair twice).

You could solve it using an algorithm for weighted matching on general graphs. Just convert the set of points to a complete graph (drawing edges between all possible pairs). It doesn't seem like those algorithms were designed to solve this kind of problem, though (I could be wrong though). So I can't help but wonder if there is a better way to do it.


texts: black-box function optimization with binary vector input: terminology and NP-hardness proof

texts:
I have a black-box function optimization problem:
$$\arg\max_{\vec{x}} \; f(\vec{x}, \vec{y}) \\\text{subject to } \vec{x} \in \mathbb{Z}_2^N, \|\vec{x}\|_1=K, K<N, \vec{y} \in \mathbb{Z}_2^M$$

The function $f(\cdot)$ is a black-box function whose output I can only simulate: I cannot access its exact form. The variables $\vec{x}$ and $\vec{y}$ are two binary vectors as the inputs of $f(\cdot)$. Given $\vec{y}$, I am seeking the optimal $\vec{x}$ that maximizes $f(\vec{x},\vec{y})$.

My questions:

Is there similar research having the same form as my problem? What is the terminology for such problems?
The brute force method to do the optimization is to exhaust all $\binom{N}{K}$ possible $\vec{x}$. Is this problem NP-hard? How can we prove this problem is an NP-hard problem?
In practice there should be some heuristics and techniques to be used to speed up the search and return an approximate optimal solution. Can someone point me out the names of possibly feasible techniques?


texts: Is this a correct description of Dijkstra's algorithm

texts:
I am on a journey understanding Dijkstra's algorithm.

My familiarity with mathematical terms is not great, so I have put the algorithm into my own English. I understand this is not ideal, but this is part of my learning process.

What are the major areas of misunderstanding in the description below?

We maintain a list D of all the tentatively known shortest distances to nodes.

Each item in D comprises a node name, a shortest (yet known) distance and a "via" node, indicating the node the path arrives via.

ie. [{ node, tentativeDistance, via }, ...]

We start with a list G of all the nodes in the graph.

ie. [{ name, edges }, ...]

We use G to keep track of the nodes we have visited. Each time we visit a node we remove it from G. In this way we never visit a node more than once.

We pull a node N from G. At the start we pull the start node with cumulative distance of zero.

If this is the start node we add it to D.

We calculate the cumulative distance to it, given the node we have arrived via.  At the start we arrive via itself.

eg. if we arrived at node C via node B, we know that the shortest path to B is, say, 2 because we must have previously explored other options to arrive at B; if the cost of the edge from B to C is 1 the cumulative distance is 2 + 1 = 3.

We then review the unfollowed edges from every node that we have visited already (in D). This is akin to choosing which part of the advancing "wavefront" to advance from.

For each of the unfollowed edges if the cumulative distance to the destination node is shorter than any previously recorded distance for that node in D (or we do not yet have a distance for it) then we replace (or add) the entry for the node in D, together with the "via" value (the current node). In this way we build up a list of best-known distances to nodes.

We pick the new destination node with the shortest cumulative distance.

Again: in this way, we can be confident that when we arrive at a node, we have found the shortest path to it.

When we arrive at the destination node, or when we have visited all the nodes we stop, otherwise we repeat the edge-reviewing process described above.


texts:
I've just learned While-Programms. In case you're not familiar with it, a W-P is inductively defined as...

$x_i \leftarrow x_j+c$  (Addition for every $i,j \in \mathbb{N}$)
$x_i \leftarrow x_j-c$  (modified subtraction for every $i,j \in \mathbb{N}$)
If $P_1, P_2$ are While-Programms, so is their composition
If $P$ is a W-P, so is WHILE $x_i \neq 0$ DO $P$ END for every $i$

I'd like to know what exactly "composition" means in this context. Does it mean a W-P in a W-P or one W-P after another W-P? (Or something different?)
Also, I'd like to know how to do following task as a While-Programm...

If $x_i=c$, then $P$ else $Q$ END; $c\in \mathbb{Z}$

I'd do it like that (see below) but I'm not really sure if I used the right notation. Maybe someone can help me out there.

WHILE 1 DO
WHILE $x_i = c$ DO
$P$
END
WHILE $x_i \neq c$ DO $Q$ END
END


texts: What graph to plot in order to meet theinstructions and apply the Bellman algo?

texts:
I'm actually studying the Bellman algorithm. I have to draw a graph from this array.

\begin{array}{|l|c|r|B|d|}
Rhythme & A & B& C& D\\
\hline
Normal & 5 & - & - & -\\
Rapide & 4 & 3 & 5 & 2\\
Prioritaire & 2 & 2 & 3 & 1\\
\end{array}

The instructions are: each vertex corresponds to a possible progress where some phases has been realised using some amounts (thus a vertex is characterized by the last phase done and the total amount spent to realize the phases). Each edges are valued by costs.

My question is: do I have to plot a graph like this one?

Or this one


texts: CFG. Ensure that $n\neq m$ twice in $L=\{a^m b^n c^m d^n, m\neq n\}$

texts:
During the formal language exam, the professor allowed to find a CFG to following language: $\{a^m b^n c^p d^q, m\neq n\wedge p\neq q\}(1)$, because neither he saw a solution (He passed a test without resolve it before!!!) to $L=\{a^m b^n c^m d^n, m\neq n\}(2)$. First language I can resolve in seconds, but I cannot visualizate how to ensure $m=p, n=q$ and to ensure $m\neq n$.

For $(1)$ I only need to construct a CFG to $\{a^m b^n, m\neq n\}$ twice. But for $(2)$ I need to ensure $a^m b^n$ substring is correlated with $c^m d^n$ substring. Someone can see how to build the $(2)$ CFG?


texts: Complexity for checking if an array is a min-d-heap

texts:
The problem is this: Let us have an int array of length n. Find an algorithm to determine if the array represents a min-d-heap.

My solution: We start from the first index in the array, and compare its value to the value of its children (all the nodes at locations $i*d+k$ where $k \in \{1,2,...d\}$, assuming we start the array at index 0). We do it for every index until we reach an index that "has no children", meaning $i*d+1>n-1$. If at every point the value of the parent's key was lower than the value of all of its children' keys we return $True$, meaning the array represents a min-d-heap.

Now - my problem is calculating the time complexity for this algorithm:

I have managed to prove that if we look at a "complete" d-tree, we get a time complexity of $O(n)$ worst case. This is my proof:

Let us assume the tree is of height $h$. We note that at the last level we have $d^{h-1}$ items. Now, we can show that the tree excluding the last level has $O(\frac{n}{d})$ items: $$\frac{\sum_{i=0}^{h-1}d^i}{d^{h-1}} = \frac{d^{h-1}-1}{(d-1)d^{h-1}} = O(\frac{1}{d})$$
Therefore, for every node excluding the last level we make $d$ comparisons, and we get that the time complexity for the algorithm is $O(d*\frac{n}{d}) = O(n)$.

My problem is that my proof was based on the fact that we have  a complete tree. There are cases which are asymmetric and I found harder to prove for the general case. I did check it by hand and showed that it is indeed the same time complexity but couldn't prove it.

Would like your help in the last part, Thanks!


texts: Pointwise mutual information vs. Mutual information?

texts:
I am learning about information theory and mutual information. However, I am quite confused with MI(Mutual information) vs. PMI(Pointwise mutual information) especially signs of MI and PMI values. Here are my questions.

Is MI values a non-negative value or it can be either positive or negative? If it is always a non-negative value, why is it ?
As I search online, the PMI can be positive or negative values and the MI is the expected value of all possible PMI. However, expected value can be positive or negative. If MI is really the expected value of PMI, why is it always positive ?

Did I misunderstand anything of MI and PMI here ? Thank you very much,


texts: Return course order with class prerequisites

texts:
Question:
Given Input: Courses and their dependencies(prerequisites)
such as A < B; A < C; B < D; C < D return course order in the order a student can take. i.e answer should return A, B, C, D or A, C, B, D

I solved the problem, but the running time is very slow, I cannot seem to figure out how to improve my algorithm. FYI: This isn't for schoolwork or project, just curious.

Answer:

  function getCourseOrder(input) {
  let result = [];

  while(Object.keys(input).length !== 0){
    for (let item in input) {
        let depencies = input[item];

        if (!depencies || depencies.length === 0) {
          delete input[item];
          result.push(item);
          continue;
        }

      let hasAlreadyTakenClasses = depencies.every((currentValue) => {
        return result.indexOf(currentValue) > -1;
      })

      if (hasAlreadyTakenClasses) {
        delete input[item];
        result.push(item);
      }

    }
  }

  return result;
}

var input =  {a: [], b: ['a'], c: ['a'], d:['c','b'] }


texts: Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

texts:
Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M).
You must realize that M is not one specific machine and can be any turing Machine with the same alphabet.
My goal is to determine whenever this problem is decidable or not.
My idea was to use mapping reducibility. The goal was to see if we can translate all problems from $A_{TM}$ which is known to be undecidable into our current problem. This would make our current problem undecidable by contagion. However I'm struggling in doing so because I'm not sure if it's possible. $A_{TM}$ is defined as a Turing machine M that accepts the word w.
Any help to get unstuck would be appreciated.


texts: What is a real-world use-case/need for a left-recursive grammar?

texts:
I understand the basics of how left-recursion works, and why some people say it's bad. And I've also ready opinions such as:

  ...like LL and LR parsing, PEGs are often frustrating to use in practise. This is, principally, because they don't support left recursion.

http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt

But this leaves me confused.

I haven't read about an actual real-world use case of why you'd even need left-recursion in the first place, especially if there are techniques to convert left recursion to right recursion. In addition, left-recursion feels less intuitive than right-recursion.

What is a real-world use case or need for a left recursive grammar to help me better understand? By "real world" I'm looking for an example grammar that is more human readable than the typical theoretical examples such as:

$A \to B\alpha \mid C$

$B \to A\beta \mid D$

For example:

$filePath \to pathSegment*$

$pathSegment \to pathSegment \mid slash$

$slash \to /$

Part of the reason I ask is b/c left-recursion doesn't seem very intuitive; it seems more intuitive to use right-recursion. And also because I wonder if it's even a practical problem to try to solve.

Update

This makes sense, but seems to be the only major reason:

  $E \to E - n \mid n$

  converted becomes

  $E \to nT*$

  $T \to - n$

  "10 - 5 - 3" is then parsed:

  L-recursive : (((10) - 5) - 3)

  R-recusive : (10 (- 5 (- 3)))

http://etymon.blogspot.com/2006/09/why-i-prefer-lalr-parsers.html

Is that all?


texts: How is the formula for calculation in row/column major obtained?

texts:
In my book, this formula is given for calculation of address of row major order's element $[I,J]$:

Address of $[I,J]$th element in row major order  $= B + W[n(I-L_r)+ [J-L_c]]$

where B denotes base address, W denotes element size in bytes, n is the number of columns; $L_r$ is the first row number, $L_c$ is the first column number.

A similar formula is given for address in column major order.

I would like to know how this formula is obtained.


texts: Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?

texts:
Where $\Omega(f)$ denotes the set of functions with f as lower bound, why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?

How can the function on the left be compared to a whole set? I thought usually a function is an element of the set, i.e. $g\in\Omega(f)$ or it is not, i.e. $g\notin\Omega(f)$.
If it would say $\sum_{i=0}^n\sqrt{i}\log_2^2i \in \Omega(n\sqrt{n}\log_2n)$ instead, I still would not understand why it is true. How do you evaluate the limit of the left side?


texts: How to find spanning tree of a graph that minimizes the maximum edge weight?

texts: Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am having a lot of trouble proving that my idea is actually correct. Can anyone show me a proof sketch or give me some hints as to how to construct the proof? Thanks!


texts: Can Quantum Computing solve Problems not even a Turing Machine can solve?

texts:
In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first machine ever to perform non-trivial computations that no Turing machine could perform".

My question: Do we really know that quantum computing is powerful enough to solve problems that not even Turing machines can solve? (Or is this just a personal belief of David Deutsch?)


texts: Time complexity of function vs return value

texts:
I came across following problem:

  Find the time complexity of below recurrence relation:

  $T(n)=\begin{cases}
 & 2T(n/2)+C; & n>1\\
 & C;&n=1 \\
\end{cases}$

The solution was given as follows

  $\begin{align}
T(n) & = C+2C+4C+...nC\\
     & = C (1+2+4+...+2^k)  \\
     & = C \left(\frac{1(2^{k+1}-1)}{2-1}\right) \\
     & = C (2^{k+1}-1)   \\
     & = C (2n-1)   \\
     & = O(n)   \\
\end{align}$

I feel above gives order of return value, but not the order of computation involved.

This function makes two recursive calls with argument $n/2$. Each of these two make another two recursive calls, making total 4, with argument $n/2/2=n/4$. Each of these four make another two recursive calls, making total 8, with argument $n/2/2/2=n/8$. And so on. Thus this form complete binary tree. This tree terminates when $n/2^h=1$. That is, when $2^h=n$.
$\therefore $ Height of binary tree $h=\log_2n$.
And the order of computation will be, number of nodes in the complete binary tree for height $h$ which equals $2^{h+1}-1=2^{\log_2n+1}-1=O(2^{\log_2n})$.

Am I correct with this final time complexity and the overall interpretation (of first being the time complexity of the return value and the one which I came up with, the time complexity of computation involved)?


texts: Construct initial marking for marked graph so that the graph is live and safe

texts:
I am learning something about P/T petri nets from the book from Wolfgang-Reisig authors and on the seventh chapter's end there is an exercise I can not really work out.

It asks me to construct initial marking such that the following marked graph is live and safe. Note that yellow highlighted place is for the latter part of the question and does not bear any other special significance.

Right after this exercise, there is following task, which asks me to do this: Show that the initial marking of each marked graph can be modified such that live and safe marked graph is obtained.

Based on that, I assume that it must be possible for any marked graph to have initial marking such that the graph is live and safe. But still I was not able to construct such initial marking. Is there an algorithmic approach to the task? And if I were to remove the highlighted part of the marked graph, would it still be possible to construct such graph?


texts:
I am trying to understand why the modular exponentiation algorithm has a running time of about $\log(n)$ where $n$ is the exponent. Here is the algorithm:

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

I think it has something to do with the number of bits for the binary representation of the exponent. What is also an intuitive numerical example?


texts: Minimum vertex cover with minimum overlap of one side

texts:
In a bipartite graph $(X+Y,E)$, it is possible to find a minimum vertex cover in polynomial time, by Konig's theorem.

Suppose the minimum size is $s$. Is there an efficient algorithm for finding a vertex cover $S$ of size $s$, such that $S\cap X$ has a minimum cardinality?

What I could do so far is to formulate this problem as an ILP where each vertex $u\in X$ has a variable $x_u$ and each vertex $v\in Y$ has a variable $y_v$. Its LP relaxation is:

\begin{align}
\text{minimize} && \sum_{u\in X} x_u  &&
\\
\text{subject to} && x_u + y_v \geq 1 && \forall (u,v)\in E
\\
&& \sum_{u\in X} x_u + \sum_{v\in Y}y_v = s
\\
&& 1\geq x_{u}\geq 0, 1\geq y_v \geq 0  && \forall u\in X, v\in Y
\end{align}

But I do not know how to check whether this ILP has an integer solution.

Is there a better approach to this problem?


texts: Derandomization of an approximation algorithm for solving a linear system

texts:
I was given a HW assignment that asks me the following:

Given a system of $m$ linear equations in variables $x_1,x_2,...,x_n$ over $\mathbb{F_p}$, find a randomized algorithm that find an assignment for all the $x_i$ such that the expected number of equations solved are $m/p$. Then do a derandomization that gives an efficient deterministic algorithm that solves at least $m/p$ of the equations.

A randomized algorithm is easy - assign each variable a value uniformly from $\mathbb{F_p}$, by the principle of deferred decisions each equation is satisfied with a probability at least $1/p$, since there are $m$ equations and by the linearity of the expectation we get the desired result.

I am having difficulty with the second part, I wish to use the method of conditional expectation: choosing an assignment for the first variables then choosing an assignment to the next variable etc', and the expectation at each point is at least $m/p$ so that after $n$ iterations we have assigned all variables and the expected number of satisfied equations is the number of satisfied equations. I have seen this method used for derandomization of MAX-CUT.

My problems making adjustments:

Unlike MAX-CUT - I can only bound the expected number of solved equations by $m/p$ and not calculate the exact expectancy, this gives me problems when trying to figure out the next best assignment since I can't choose one that maximizes the  conditional expectancy
Unlike MAX-CUT - Choosing an assignment for some of the variables can determine the value of another variable (e.g choosing $x_1,x_2$ when we have $x_1+x_2+x_3=1$)

I have a suggestion, but I can't manage to prove it works: At iteration $k$ choose an assignment for  $x_k$ s.t the number of equations that are false is minimal (that is equations with one free variable that is not assigned a value contradicting the equality such as $x_j=t$ when we assigned $x_j$ a different value)

I would appreciate help analyzing my suggested algorithm or a point in the right direction


texts:
I have this Question , I want the answer and show me how to solve it Please :

Analyze the running time of the following algorithm  using Big-Oh notation

maxerea =0; maxpt1 =maxpt2 = maxpt3 =0;
for(i =1;i<=n;i++)
    for(j =i+1;j<=n;j++)
       for(k =j+1;k<=n;k++){
           empty = True;
         for(l =1;l<=n;l++){
         if((l != i) && (l != j) && (l != k))
            if insideTriangle(i,j,k,l) then empty = False;
            }
              area = TriangleArea(i,j,k);
            if (area < maxarea) {
                maxarea =area;
                  maxpt1 = i; maxpt2 = j; maxpt3 = k;
               }
           }
  print, maxpt1, maxpt2, maxpt3


texts: Incremental View Maintenance for projection

texts:
I was reading https://www2.cs.duke.edu/courses/spring02/cps296.1/lectures/08-view.pdf

Or in the paper "Incremental Maintenance of Views with Duplicates," by Griffin and Libkin, SIGMOD, 1995. figure 2.

I don't understand why we need to min(R,ΔR) before -.
Is there any counterexample?


texts: Enforcing application layer consensus on top of a distributed consensus protocol

texts:
If I understand correctly, the term "consensus" in distributed consensus algorithms means that all the participants ("peers") achieve a common understanding of some data value.  Different algorithms can handle different types of failures or misbehavior by some of the peers, network disconnections or partitions, lost messages, and so on.  For example, PBFT has the property that any small group of peers (less than a third) cannot prevent the remaining peers from achieving a common understanding of the data value.

BUT there is nothing in these algorithms that prevents any peer from setting the data to a value that they shouldn't set it to.  So "consensus" just means we all agree that the value has been set to X.  It does not mean we all agree that X is the correct value.

Is that right?  And, if so, is there some general research into how to enforce a set of application-specific rules about who is allowed to set the data to a given value?

For example, Bitcoin has a set of rules that ensure that only "valid" transactions are accepted by the network.  So, for example, Joe can't give Fred the same bitcoin that he's already given to Mary.  Joe can't give Fred a bitcoin unless someone else already gave Joe that bitcoin, or Joe earned that bitcoin by mining.  And so on...

So what we have in Bitcoin are a set of application-layer rules that make sense for money, and these rules are embedded in the distributed consensus protocol used by Bitcoin (i.e. blockchain and proof-of-work and the bitcoin reference implementation).

However, what if I have a different set of rules that make sense in MY application - how can I ensure that a distributed consensus protocol (e.g. PBFT) not only ensures consensus across all peers about what the data value is, handling various failures and misbehavior by peers, and ALSO ensures that only "legal" values are set by the peers.

For example, I might have rules like: The value can only increase - nobody is allowed to decrease it.  Except on Sundays, when it can be decreased, but must only be set to an even value.  Except peer P can set it to whatever value they want to.  And if the value=5, then peer Q is the only one who can change it.  And so on...  (Believe me, I have a real-world problem that requires this kind of complexity.)

Ideally, the rules would be expressed in a formal language, and the distributed consensus protocol would reject any attempts by any peers to change the data value in a way that does not conform to the rules.

Could I do this by implementing PBFT and adding in a check where each peer checks that a proposed new value is consistent with the rules, and then refusing to accept (possibly broadcasting a NACK) if the proposed change is not valid?

I'm wondering if this has already been studied.  Perhaps this is the same as the concept of "consistency" in a distributed database, but I don't want to use a database replication solution, because I want eventual consistency, not strong consistency, and I want the kind of fault-tolerance that PBFT provides.

Thanks!

Duncan


texts: The use of master theorem appriopriately

texts:
I have a recurrence relation and trying to use master theorem to solve it. The recurrence relation is:

$T(n) = 3T(n/5) + n^{0.5}$

Can I use the master theorem in that relation? If so, can I say that $T(n)$ is $Θ(n^{0.5})$?


texts: Token-sliding as a kind of Petri net: well-studied subclass?

texts:
Let a directed graph $G = (V, E)$ be given, plus a constraint map $c: E \rightarrow V$ and a set $T \subseteq V$ of initial token locations.  A valid move consists of sliding a token from $v$ to $w$ if:

$v \in T$ — to slide a token, it must be there.
$w \not \in T$ — to move a token somewhere, the new place must be empty.
$c(v, w) \in T$ — (the unusual bit) to use an edge, some token must occupy the "activator" vertex.  Note that the trivial constraint $c(v, w) = v$ is allowed.

(Then $T \Rightarrow^1 (T \setminus \{v\}) \cup \{w\}$.  An interesting decision problem might be this: given $v$, is there a $T'$ s.t. $T \Rightarrow^* T'$ and $v \in T'$; there are plenty others.)

I think this can be reformulated as a Petri net, with transitions $\{v, c(v, w)\} \rightarrow \{w, c(v, w)\}$ when $c(v, w) \neq v$ and $\{v\} \rightarrow \{w\}$ when $c(v, w) = v$.  However, I am very unfamiliar with Petri nets.  Does this have some correspondence to Petri nets at all?  Is the subtype of Petri nets where all transitions are on the above form well-studied?  What are the major results, especially concerning the computational complexity of the most interesting decision and function problems?


texts: Is there an online algorithm for radix conversion?

texts:
Suppose I have $P$, which is the base-$p$ representation of an integer $n$ and I want to calculate it base-$q$ representation $Q$.  The obvious algorithm is: interpret $P$ to obtain $n$, then calculate $Q$ from $n$.  This is easy.

But if $n$ is very large this could require a lot of memory, and it could require a large amount of processing before any of the digits of $Q$ are emitted.  In certain special cases we can do better; there is an online algorithm which can start producing output before all the input is read.  For example, if $p^i = q^j$ then the algorithm can read $i$ digits of $P$ and immediately produce $j$ digits of $Q$ without any further input and with only a constant amount of memory.  This method is used, for example, in converting generic computer data ($p=256$) to “Base64” format ($q=64$).

Is there a general online algorithm for radix conversion?  I expect that if there is such an algorithm, in the worst case it cannot emit any digits of $Q$ without first reading all of $P$, but are there algorithms that can often do better than this, in cases more general than the very unusual $p^i=q^j$ situation?  Or are there any other special cases of interest?

[ Related thread: The math behind converting from any base to any base without going through base 10? but all of the suggestions there ingest the entire input before producing any output. ]


texts: A greedy approximation algorithm for max k-cut

texts:
The max k-cut problem is: Given an undirected graph G= (V;E) with nonnegative edge costs, and an integer k, find a partition of V into sets $S_1,\cdots,S_k$
so that the total cost of edges running between these sets
is maximized. The aim is to find a greedy algorithm for this problem that achieves a factor of $(1-\frac{1}{k})$.

My algorithm is: at the beginning, all the vertices of V is seperated in to $S_1,S_2,\cdots,S_n$. Once we have $S_1,\cdots,S_{t+1}$, we find $S_p,S_q$ s.t. $c(S_p,S_q)=min_{\{i,j\}}c(S_i,S_j)$ and merge $S_p,S_q$ together to get $t$ parts until $t=k$.
Let $ALG_t$ be the solution given by this algorithm for $t$ parts. $OPT_t$ is the optimum value for $t$ parts.
By induction, $ALG_n=OPT_n\ge(1-\frac{1}{n})OPT_n$.
Since there are $\binom{t+1}{2}$ sets of edges between $S_1,\cdots,S_{t+1}$, at least one of these sets with cost $\le\frac{1}{\binom{t+1}{2}}ALG_{t+1}$.
By the construction of the algorithm, we merge these two sets of vertices together, then we have $ALG_t\ge ALG_{t+1}-\frac{1}{\binom{t+1}{2}}ALG_{t+1}=(1-\frac{1}{\binom{t+1}{2}})ALG_{t+1}\ge(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})OPT_{t+1}\ge(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})OPT_{t}$
But it's not true that $(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})\ge(1-\frac{1}{t})$.
Therefore I wonder if there is some other arguments or algorithm?


texts: To check if a chain with $n$ links can be "folded" into a size at most $L$

texts:
Given a chain of $n$ links, each of length $a_1, a_2,..a_n$, where each $a_i$ is a positive integer. $L$ defines the length of the "folded" chain. More formally, we want to decide whether there exists a $t \in [0, L]$ and $s_1,...,s_n \in \{-1, +1\}$ such that $t + \sum_{i=1}^j(s_ia_i)\in[0,L]$ for all $j\in\{0,..,n\}$.

For example, given $a_1 = 5, a_2 = 1, a_3 = 7, a_4 = 2, a_5 = 8,$ and $L = 9$ a possible solution could be $5+1-7-2+8$ such that the entire chain is contained within a space of $9$ units.

We need to provide an $O(nL)$ time algorithm to decide if the chain can be folded or not.

My approach:
I tried a couple of different approaches:

Greedy algorithm: starting with the first link, check if it is greater than $L$, if yes then subtract $(s = -1)$ the second link from the first link. If it is still greater than $L$, the repeat. If it was not greater than $L$ initially, then add the second link to the first. This approach failed.
Tree approach: For every link, we can have $s=1$ or $s=-1$, this gives us $2^n$ possible arrangements. We can create a binary tree of size (layers) $n$ from this. But this method won't work due to the sheer size of the tree.

Any hints or guidance is appreciated.

I was also thinking that if $L$ is not given, is there a way to determine $L$ such that it is the best folding possible?


texts: What is a good general-knowledge-level title description of Dr. Aho's and Dr. Ullman's body of work for which they were awarded the 2020 Turing Award?

texts:
I recently read in the New York Times that my old "Data Structures and Algorithms" class professor Dr. Ullman had received the Turing Award along with Dr. Aho. The article title was "Turing Award Goes to Creators of Computer Programming Building Blocks".
Now, I think of of "computer programming building blocks" as things like class libraries (or maybe data structures and algorithms) but the story mentioned compiler design:
"On Wednesday, the Association for Computing Machinery, the world’s largest society of computing professionals, said Dr. Aho and Dr. Ullman would receive this year’s Turing Award for their work on the fundamental concepts that underpin computer programming languages. ...
Dr. Aho and Dr. Ullman helped refine one of the key components of a computer: the “compiler” that takes in software programs written by humans and turns them into something computers can understand."
Can anyone provide a one-sentence summary of their technical contributions, written in layman's terms?


texts: if traveling salesman problem is decidable in polynomial time, can an actual solution be proposed in polynomial time?

texts: I'm asking because it seems that P problems refer to decision problems rather than actually propose a solution.


texts: Is occurrence typing (flow-sensitive typing) a form of dependent typing?

texts:
I take occurrence typing to be typing that "... allows the type system to ascribe more precise types based on whether a [check] succeeds or fails." (adapted from the Racket docs with "predicate check" replaced with "check")
Here's a TypeScript example:
function foo(x: string | number) {
    switch (typeof x) {
        case "string":
            // the type of x is `string` here:
            x.length
            break
         case "number":
            // the type of x is `number` here:
            x * 3
            break
    }
}

playground link
I take "dependent types" to mean "types that depend on terms". reference reference
The type of x (a type) depends on x (a term). So is there dependent typing in the example above? More generally, is occurrence typing a form of dependent typing?
I could see an argument that the answer is "no" if we interpret "dependency" such that it is expressed via binding. So then a "dependent type" would be a type T x where  T is a type and x is a term. But then maybe even on this definition occurrence typing counts as dependent typing, if we allow T to be something fancy like a type-level x -> if x is a string then string else number.


texts: Check if a row is in the span of a matrix

texts:
Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations:

A xor B xor C = 1

A xor B xor D = 1

X xor A xor Z = 0

etc...

For a new external row, I want the ability to tell if it is a linear combination of the rows of the matrix, or not. I could do this by computing the augmented matrix, and solving it with Gaussian Elimination.

For example I want to know if this is true or not:

X xor B = 1

Now, suppose I have a lot of rows to test (8 billions). I do not wish to recompute a new augmented matrix each time. I heard there is a way to compute the echelon form once and use it to determine whether a given row is in the span of the matrix or not, but I cannot figure out how.

How easy is it to determine whether a given row is in the span of a matrix in echelon form?


texts: Does a computation tree for a probabilistic Turing machine have to be a binary tree?

texts: Ever example of computation on a probabilistic Turing machine that I have read uses only a binary tree to show the computational branches of a probabilistic Turing machine. I know that an NTM may use as many branches as needed during a computation, so is this also the case for a PTM? Or is a PTM limited to only binary branching?


texts: Computational indistinguishability for any distribution using a Chernoff bound

texts:
I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. This is the statement:
For any distribution $D$ over  $\{0,1\}^{n}$, there exists a distribution $D'$ such that $D$ and $D'$ are $\epsilon$ indistinguishable with respect to any classical distinguisher of size $n^{k}$.
Let me restate the proof.

Let $D$ be any distribution over $\{0,1\}^{n}$. Then choose $w$ elements
independently with replacement from $D$, and let $D′$ be the uniform
distribution over the resulting multiset (so in particular, $H(D′) \leq
 \log_{2} n$). Certainly $D′$ can be sampled by a circuit of size $\mathcal{O}(nw)$: just
hardwire the elements. Now, by a Chernoff bound, for any fixed circuit
$C$, clearly $D$ and $D′$ are $\epsilon$-indistinguishable with respect to $C$, with
probability at least $1 − e^{-\epsilon^{2} w}$ over the choice of $D′$. But there
are “only” $n^{\mathcal{O}(n^{k})}$ Boolean circuits of size at most $n^k$. So by the union
bound, by simply choosing $w = \Omega\left(\frac{n^{k} \log n}{\epsilon^2}\right)$, we can ensure that $D$ and $D′$ are $ε$-indistinguishable with respect to all circuits
of size at most $n^{k}$, with high probability over $D′$.

I do not understand how the Chernoff bound is applied. How do we know the action of the circuit $C$? I also don't understand why $w = \Omega\left(\frac{n^{k} \log n}{\epsilon^2}\right)$ in the union bound. Since we need to "protect against" $n^{\mathcal{O}(n^{k})}$ Boolean circuits, shouldn't $w$ be something like $w = \Omega\left(\frac{n^{\mathcal{O}(n^k)} \log n}{\epsilon^2}\right)$?


texts: Why is most research in logic and verification conducted in Europe rather than the US?

texts:
This is the CSRankings output for logic and formal verification for the last 10 years, worldwide:
http://csrankings.org/#/index?log&world
For the International Conference on Computer Aided Verification (CAV), the results are more of a mixed bag, with 4 out of the top 10 highest impact universities (including the top spot) being in the US rather than Europe. For Logic in Computer Science (LICS), the highest impact universities are almost exclusively in Europe. Beyond the top 10, rankings are mostly filled with European universities for both publications.
For most other areas, the top 10 highest impact universiries are almost exclusively in the US (if not top 20 and beyond).
I am curious to know why that is. Why does most research for that particular area of Computer Science take place in Europe, whereas most other research takes place in the US?
It is possible that the premise of this question is false and maybe I am not using the correct tool or metrics. However, my general research on this subject seems to verify (pun intended?) that this is indeed the case, with most well known centers being in Oxford, Paris, Warsaw, the Max Planck Institute etc. Also, I am not implying anything about the quality of the research (for which I don't know anything about since I don't practice in that field) only that the quantity seems to be mostly centered in Europe.


texts: Why do BNF specifications of C-like languages define expressions in terms of seemingly unrelated parent expressions?

texts:
Backus-Naur Form specifications for the grammars of languages like like C or C++ build up expressions with counter-intuitive definitions. For instance, a multiplication expression like

5 * 3

is also a logical-or-expression and an equality-expression and a bunch of other things it doesn't actually look like, because the grammar makes it an:

expression

consisting of an assignment-expression

consisting of a conditional-expression

consisting of a logical-or-expression

consisting of a logical-and-expression

consisting of an inclusive-or-expression

consisting of an exclusive-or-expression

consisting of an and-expression

consisting of an equality-expression

consisting of a relational-expression

consisting of a shift-expression

consisting of an additive-expression

consisting a multiplicative-expression.

A snippet from the grammar looks like:

<exclusive-or-expression> ::= <and-expression>
                            | <exclusive-or-expression> ^ <and-expression>
<and-expression> ::= <equality-expression>
                   | <and-expression> & <equality-expression>
<equality-expression> ::= <relational-expression>
                        | <equality-expression> == <relational-expression>
                        | <equality-expression> != <relational-expression>

So if I were to write a parser that just followed these productions, I'd end up having to interpret the expression 5 * 3 12 different ways, e.g. by making it an instance of a MultiplicativeExpression class which derives from AdditiveExpression... all the way up to a base Expression class. And that seems very wasteful, since those classes would implement adding, AND-ing, OR-ing, etc. but would simply no-op for the single-term case.

By comparison, the Wikipedia example of BNF makes more sense:

<postal-address> ::= <name-part> <street-address> <zip-part>
<name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL>
              | <personal-part> <name-part>
<personal-part> ::= <initial> "." | <first-name>
...

The Wikipedia example reads like "a postal address consists of a [...]", whereas C-like language grammars read more like "a [...] can be treated as an expression". Why are C-like language grammars so "polymorphic"?


texts: Is there an algorithm for selecting best matching data in a data set given a set of parameters?

texts:
What I am trying to do is for a diet app that I am planning to build. The goal is the users will input their desired macros (carbs, fat, protein) and the system should find all recipes that match the provided macros. It does not have to match it exactly, just the best match.
Another idea is users provide their daily calorie intake and the system will find the best match, regardless of the macros.

Links and study materials are much appreciated.


texts: Checking whether a given Hashing Function fulfills Uniform Hashing Condition

texts:
I am learning about Hashing and have struggles with the following assignment:

$U$ is a universe of keys with $Z(m)=\{0,\ldots, m-1 \}$  the amount of possible hash-values.
Given $U= \mathbb{Z}_{55} = \{0, \ldots, 54 \}$ and $m=5$.
Does the function $h(k,i)= (k+i) \bmod{5}$ fulfill the conditions for Uniform Hashing?

Uniform Hashing should be given when the probability that to a random key, a specific probe sequence trough the hash function is assigned, is $1/m!$ for all possible probe sequences...
But I don't know how to proceed with checking whether this is given for the function above.
Any help and suggestions would be appreciated! :)


texts: Time complexity of ArrayList Insertion : Calculating sum of X + X/2 + X/4 + X/8 + ... 1


texts: What is average number of cycles in an undirected ordered graph of size n?

texts:
What is average number of cycles in an undirected ordered graph of size $n$?
I've tried finding out sum of number of cycles in all sorts of a graph of size n but I couldn't find that out.


texts: How to compute the loss and backprop of word2vec skip-gram using hierarchical softmax?

texts:
So we are calculating the loss

$$J(\theta) = -\frac{1}{T}\sum_{t=1}^T\sum_{-m \leq j \leq m} \log P(w_{t+j}|w_t;\theta)$$

and to do this we need to calculate

$$P(o|c) = \frac{\exp(u_o^Tv_c)}{\sum \exp(u_w^Tv_c)},$$

which is computationally inefficient. To solve this we could use the hierarchical softmax and construct a tree based on word frequency. However, I am having trouble on how we could get the probability based on the word frequency. And what exactly is the backprop step if using hierarchical softmax?


texts: CRC computation speed vs polynomials features

texts:
I tried to find information about how features of a CRC polynomials influence computation speed of implementations.

It is obvious that (depending from the CPU architecture the algorithm runs on) algorithms can be optimized for special CRC widths.

However, even when comparing CRC polynomials of the same width there still seems to exist differences in computation speed:

I read a statement that low polynomial weights would
increase computation speed.
Also Prof. Koopman wrote on his 6sub8 CRC page: "Consider only
polynomials with bits set in the bottom 8 bits (in addition to the
topmost bit). This can help speed up computation and reduce lookup
table sizes for CRC calculations in application programs."

I can see why pre-calculated CRC tables can be more compact using a sub8 polynomial.
But I could not wrap my mind around the speed related statements. All implementations I had a look at (various C implementation of bit-wise and table-based algorithms) seem not to benefit from low-weight or sub8 polynomials.
Maybe I missed the point or there are environments (like other algorithms, hardware implementations, special CPU architectures) that would benefit.

My question:
Given a certain CRC width, in which way and under which circumstances does a low polynomial weight and/or a sub8 polynomial speed-up the computation of a CRC?


texts: Eke a better compression ratio out of Huffman coding by mixing 1-grams and 2-grams


texts:
Let $$A= (Q,Σ,δ,s,F)$$ be a NFA. Prove the following statement:

$∀q ∈ Q: (∃ w_2 ∈ Σ^* :δ (q, w_2) ∩ F \ne  ∅ ⇒ ∃w_1 ∈ Σ^*:w_1w_2 ∈ L(A))$

I figured out that it means that if all the states have a path to the final state, that the word describing their path is a suffix of a word that is accepted from the NEA.

The thing is: How can I be sure that the NEA accepts all words with that suffix if it doesn't start from the s state.

Any leads?


texts:
How can I show that the lower bound for getting a triangulation from a point set in the plane is $\Omega(n \log n)$?

I know that the lower bound for finding the convex hull for a point set is also $\Omega(n \log n)$. Is it valid to argue that since the convex hull is also part of the triangulation it can't be done faster or else the lower bound for the hull would also be lower?

Edit: By Triangulation I mean connecting all the points via non-crossing edges such that they form triangles: https://en.wikipedia.org/wiki/Point_set_triangulation


texts:
Corollary 23.2
Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, and let $C = (V_C,E_C)$ be a connected component (tree) in the forest $G_A = (V,A)$. If $(u,v)$ is a light edge connecting $C$ to some other component in $G_A$, then $(u,v)$ is safe for $A$.
Proof The cut $(V_C,V-V_C)$ respects $A$, and $(u,v)$ is a light edge for this cut. Therefore, $(u,v)$ is safe for $A$. $\quad\blacksquare$

I did understand the original proof for the Cut property in CLRS (Theorem 23.1). But I am unable to grasp how does the above corollary follow from the original proof? Why does the cut $(V_C,V-V_C)$ respect $A$?


texts: Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

texts:
I have found an exercise where it tasks to provide a grammar and a pushdown automata for
$L = \{ 0^x1^y0^z1^w | x+w=y+z\}$
While finding a pushdown automata for it is quite easy (four states and two stack symbols $p$ and $t$, where $0^x$'s push $p$, $1^t$'s and $0^z$'s pop $p$ or push $t$ if there are no $p$'s, and $1^w$'s pop $t$), I am unable to find an equivalent grammar for it. Perhaps there is some trick for this?


texts: The applicability of the Master Theorem and calculation of asymptotic limits

texts:
Given the following recursive equation
$T(n)=3T(\dfrac{n}{8})+ Θ(n^{1/3})$

I want to know how to explain the applicability of the Master theorem in a rigorous
 way and what means asymtotic limits of complexity exactly?

I remarked the two cases are not satisfied. So I have to check the third case and i saw that
$n^{1/3} \notin Ω(n^{1/3*log_2 3 + ε})$


texts: What are the practical uses of ontologies?

texts:
I have read many papers and books about ontologies and I am trying to figure out that how they are used in a real project?

For example how the ontology for a soccer player robot can be defined and used with a cognitive architecture in order to make it intelligent?

Are ontologies relations between terms in that domain of knowledge ( for example relation between the ball and foot word and physical rules definition and their relation with the foot and ball movement , ...) or relations between tactics , strategies and different mixtures of tactics ?

Are there any clear examples of ontology usage in real projects and their combining usage with the cognitive architectures like ACT-R for augmenting the cognitive architecture?


texts:
Let $P$ be any nontrivial property of the language of a Turing machine. Prove
that the problem of determining whether a given TM’s language has property $P$ is undecidable.
Proof:(This is from sipser's book).
Assume for the sake of contradiction that $P$ is a decidable language satisfying the properties and let $R_P$ be
the TM that decides $P$.
We show how to decide $A_{TM}$ using $R_P$ by constructing TM $S$.
First let $T_∅$ be a
TM that always rejects, so $L(T_∅)$ = ∅.
You may assume that $<T_∅> \notin P$ without loss of generality, because
you could proceed with $\bar{p}$ instead of $P$ if $<T_∅> \in P$.
Because $P$ is not trivial, there exists a TM $T$ with
$<T> \in P$.
Design $S$ to decide $A_{TM}$ using $R_P$ ’s ability to distinguish between $T_∅$ and $T$.
$S = $“On input $<M, w>:$

Use $M$ and $w$ to construct the following TM $M_w$.
$M_w$ = “On input $x:$

Simulate $M$ on $w$. If it halts and rejects, reject. If it accepts,
proceed to stage $2$.
Simulate $T$ on $x$. If it accepts, accept.”

Use TM $R_P$ to determine whether $<M_w> \in P$. If YES, accept. If NO, reject.”

TM $M_w$ simulates $T$ if $M$ accepts $w$. Hence $L(M_w)$ equals $L(T)$ if $M$ accepts $w$ and $∅$ otherwise.
Question:  I'm having trouble understanding the last few lines of this proof. $R_p$ is a decider that decides $p$. It tells us that a  machine has the property $p$ or not. When we run $R_p$ on the description of $M_w$ and suppose $M_w$ accepts $w$ then the language of $M_w$ equals the language $T$ otherwise $\phi$. Now i don't understand how this proves that acceptance problem is also solvable if we have a decide for $P$. I'm stucked at his point , any help would be great.


texts: How to draw an LTS based on the parallel process "|" in CCS Milner's logic?

texts:
I'm trying to provide a Hennessy-Milner logic formula for CCS expressions that are not (strongly) bisimilar. An example with a sketch:

  For each of the following CCS expressions, decide whether they are strongly bisimilar and if no, find a distinguishing formula in Hennessy-Milner logic.

$b.a.Nil+b.Nil$ and $b(a.Nil+b.Nil)$

I first draw these two to get a better understanding as follows (excuse my awful drawing skills but I couldn't figure out how to put it in LaTeX so I used draw.io):

You can clearly see the Right Hand Side could do $b.b$ but the Left Hand Side can't respond to that. And my distinguishing HML formula is $[b]<b>tt$. On the LHS you get: $[b]\{b.a.Nil+b.Nil\} = \emptyset$
and on the RHS you get:
$[b]\{b(a.Nil+b.Nil), a.Nil+b.Nil\} = b(a.Nil+b.Nil)$.
Therefore this is a valid distinguishing formula.

Hopefully, I made what the exercise is about clear. Now, the following CCS expressions that I have to distinguish are:

$a.Nil|b.Nil$ and $a.b.Nil + b.a.Nil$.

I know how to draw the RHS because the + denotes a choice but I don't have any idea of how the parallelism work in CCS and couldn't understand it after reading. My guess is the following but it doesn't make sense and is probably wrong:

Could someone help me understand how to sketch the LHS so that I can complete this exercise?

P.S My tags are probably not correct but I couldn't find any tags to Hennessy-Milner logic, so feel free to edit them.


texts: It is known that when a Random Access Machine halts the output on the registers is going to be $R_1,\ldots,R_{||R_0||}$ after going through its instruction set where $||R_0||$ denotes the length of the binary representation of $R_0$. Is there any implication changing the output on the registers as $R_1,\ldots,R_{R_0}$.


texts: inclusion and concatenation of languages

texts:
so for a homework assignment i need to prove the following:

We have arbitrary languages L1⊆∑1*, L2⊆∑2*, L3⊆∑3*, L4⊆∑4*

Prove that the followging is either true or false:

If L1 ∪ L2 ⊆ L3 ∩ L4, then L1◦L2 ⊆ L3◦L4 (◦ = concatenation)

Now i know this is true, but i don't know how to approach this problem...

Any tips on pointing me into the right direction are appreciated!


texts: Distinction between statements, declarations, and expressions in formal grammar

texts:
I am learning basic grammar and parsing concepts and ran into this statement:

  Nonterminal symbols represent syntactic entities: statements, declarations, or expressions.

But the three terms (statements, declarations, expressions) were not really defined. I have plenty of programming experience so I have a fairly intuitive grasp of the terms, but I'm wondering, from a language grammar standpoint, what are the generally accepted definitions for each? When I searched online I found several language-specific discussions but nothing that gave a general definition of these terms that can apply across any language.

Are there such definitions out there? Thanks.


texts: Can anyone explain how look-up tables are used for optimal Rubik's cube solvers such as Thistlethwaite's or Kociemba?

texts: I have implemented Thistlethwaite's algorithm however, it is far too slow as it is only using graph traversal over many Rubik's cube states. I am currently unsure of how look-up tables are implemented so any help on how I could do so would be greatly appreciated.


texts: Assign team members to groups to maximize outcome

texts:
Team A has 2 Spots

Team B has 1 Spot

Player 1: 10 Units when on team A, Can't work on team B

Player 2: 8 Units when on team A, Can't work on team B

Player 3: 9 Units when on team A, 2 Units when on team B

I'm trying to craft an algorithm that will maximize the total units of output between the two teams. I'm representing the teams and players as nodes in a graph and the number of units as edges.

I initially attempted a greedy algorithm which would choose the heaviest weighted edge possible. However, this results in players 1 and 3 on Team A with no one able to contribute to Team B.

How would I arrive at a more nuanced approach in which Team A would get players 1 and 2, and Team B would get player 3? Is this more of a graph theory or combinatorics problem? Or both?


texts: How can ships in Battleship be partitioned into B subsets, each with a capacity C?

texts:
I have been doing some research on the reduction of Battleship to bin-packing, but I do not completely understand the input to the problem from this academic paper: http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf
The paper states that the input would be an array of positive integers (the items), C (an integer capacity), and B (an integer number of subsets). The question that is posed then becomes: can the items be partitioned into B subsets, each of which has total capacity C? How is this even guaranteed to be possible? For example, if the total size of 6 ships is 19, it seems actually impossible to partition them according to the requirements of the problem? Maybe I am just understanding the reduction wrong. Any ideas?


texts:
Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we still didn't make its DFA.

I am trying to make Deterministic Finite Automata (DFA) of this lang which is defined on alphabet={a,b} and all strings present in this language are either start or end on double letter i.e aa or bb. The RE is given in title.

I made a DFA by using Kleene Theorems but its pretty complex. How i can directly make a DFA.


texts: modify Dijkstra's algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex

texts:
i want to modify Dijkstra algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex

I tried it with BFS(breadth first search). Initially calculates the number of edges away from source to each vertex v. Then run Dijkstra's algorithm with a constraint like relaxation u if and only if edges size from the source to u is no longer than three. Is it correct or Are there another method to find it.(using Dijkstra algorithm)


texts: What is the Time complexity of $\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$

texts:
What is the time complexity of

$$\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$$

and how do you calculate it?


texts: How does an operating system implement the C library?

texts:
I have an idea of how a C program is turned into machine code by the compiler. I also know how the processor processes the instructions (https://www.youtube.com/watch?v=cNN_tTXABUA this video has a good introduction). But what I don't understand, is how an operating system (most times written in C or some low-level language) can run programs also in C (or other low-level language). I don't understand this. Does the OS read the code and then processes it with some internal functions, or does it only open the machine code and send it to the processor, that makes the rest? In case of the second option, how the OS take care of which instructions are allowed to be executed, and which are not? (example: I may write a program that has an instruction that jumps to a forbidden part of the memory RAM, how the OS protect it from happening?)

I don't expect to understand it fully in this post's answers, but if you guys could give me an idea and then some books or tags to search, I'd be happy!


texts: Find internal surfaces in an oriented mesh

texts:
I have a solid with internal holes. My solid is mostly a union between walls/floors/ceilings. Each of them is a mesh with polygons oriented counter-clockwise. Then with those polygons I do a union that serves to delete the intersection between the solids. Which leaves me with only one solid made of polygons.

In term of data I have as I have a data structure that looks like that :
Class Building Element:

Object ID (Input)
Implicit geometry  (Input)
Explicit geometry :  calculated from implicit geometry. It's a list of polygons which is in turn an ordered list of points

Class room:

List of object ID of walls/floor... (Input)
Explicit geometry : Union of explicit geometries of the objects listed

A room is represented by one solid, and the room is inside it and makes a hole. I want to be able to distinguish the polygons that bound the space inside from those that bound the space outside. Which would in theory split my polygons into two lists, one of the surfaces you would see if you were inside the room, and the other with surfaces visible from outside (assuming the input doesn't have any geometrical error).

Distinguishing this surfaces surely exists in literature but I can't find it. I think BSP-trees can help me solve such a problem, but I can't find out how.

Here is an example of my situation:

I have an idea on how to do it. My algorithm seems robust, but a bit stupid, I'm sure in literature there is something smarter :

First I need to get a point inside my object

I calculate the bounding box containing my polygons
I can then easily have a point outside if its x,y,z are superior or
inferior to any other x,y,z of the bounding box

Find one external face

From this point I do take a ray (the choice of the may be random, but
a ray may fail to intersect the object. A ray between my exterior
point and the center of the boundingbox should always be good)
With ray tracing, I can find out the first polygon it touches. It may
touch a vertex first. Then I'd just take one of the polygon that
contains this vertex.

Split my list of polygons into smaller lists

Let's call P my list of polygons, and L a list of list of polygons, then li a list of polygons included in L.
li should include only polygons that touches each other.
Let's define what is touching each other :
We define a polygon as a list of edges.
A general definition would be that two polygons (polygon1,polygon2) touch each others if ∃(edge1,edge2)∈ polygon1 x polygon2

For my simplified case : My polygons are list of points, and I know that two polygons that touches each others implies that they have a common vertex. I will use this simplified definition in practice, but it doesn't alter the methodology.

I take the first polygon in P
I remove it from P and add it to li
I see if it touches any other polygon  in P
I get those polygons, remove them from P and add them to li
I see if those polygons touch other polygons in P
With those newly touched polygons, I repeat the step 4. But if it didn't touch anything at step 5, I go to next step.
I put li in L
if P still contains at least one item, I go to step 1

Only one of the sublists contain external li the external polygon I have found above. The others are internal.
When to check which sublists contain the external polygon probably depend in the data structure, but it's a matter of optimization, not robustness.


texts: Possible to construct a probabilistic halting problem solver?

texts:
I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions.

So I was thinking, much in the way that some primality testers are probabilistic(they give you yes or no but have a chance to be wrong). Would it be possible to build a probabilistic halting problem solver? One that reports within a certain degree of error, whether a problem halts or not?


texts:
An instance of PATH is given by  where G is a directed graph, s and t are nodes in the graph, it's a true instance if G has a path from s to t.

DISTANCE-PATH is similar, but with an extra requirement d and on an undirected graph. A true instance of this would be  where G is an undirected graph and there exists a path of length d from s to t, and there isn't a shorter path.

Given directed , construct an undirected G' such that G' has a path from s to t of shortest length d iff G has a path from s to t.

The idea is to construct G' by making n copies of G, and each edge in G' connects one copy to the next.

I don't understand how d comes into play and how to ensure there are no shorter paths, should d be the number of copies of G made? Should G' connect the copies of G by connecting one t node to the next s node? I'm not sure how to approach this problem


texts: Number of optimal solutions for Longest Common Subsequence (Substring) problem

texts:
The Longest Common Subsequence (or Substring) problem (LCS) asks, given two strings $s_1$ and $s_2$, to find one string which is substring both of $s_1$ and $s_2$ and it is of maximum length.

Each instance of the problem (i.e. each choice of $s_1$ and $s_2$) can have multiple optimal solutions.
The size input of the problem is the sum of the length of $s_1$ and $s_2$.

Is the number of optimal solutions polynomial with respect to the size of the instance?


texts: Worst-case input for median-of-medians with groups of size 3

texts:
Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a recurrence of:

$$\begin{align*}
  T(n) & \leq T(n/3) + T(2n/3) + O(n)\\
       & = O(n \log n)
\end{align*}$$

However, this assumes that there exists an input which would always split the recurrence in the worst possible case. I am not convinced that this input always exists.

Question: Is there a general procedure to create a worst-case input for the median-of-medians algorithm with $k=3$ for an input of any length $n$?

If it helps, you can assume $n$ is of some particular format and that we are always searching for the exact median (as opposed to querying the $i$-th order statistic). You can also assume that the algorithm groups elements deterministically (e.g. incrementally group 3 elements).

You can choose any deterministic implementation if it helps, here is one for reference. Given an input array $A$ of $n$ distinct elements and query $i$ for the $i$-th order statistic, the $\mathrm{SELECT}(A, i)$ procedure is as follows:

Divide $A$ into $\lfloor \tfrac{n}{3} \rfloor$ groups of length $3$.

We can do this by putting $\{a_1, a_2, a_3\}$ as group $G_1$, then $\{a_4, a_5, a_6\}$ as group $G_2$, and so on...
If $n \neq 3k$ then we can create one more group with the remaining 1 or 2 elements.

Find the median of each group $G_i$ and store them in a list $M$.

We can do this by creating $M = [\mathrm{med}(G_1), \mathrm{med}(G_2), \ldots ]$.

Recursively call this function to get the median of medians $x = \mathrm{SELECT}(M, \lfloor \tfrac{n}{6}\rfloor)$.
Partition $A$ about $x$ into $A_1$ and $A_2$.

Let all elements in $A_1$ be less than $x$. (Assume order is retained)
Let all elements in $A_2$ be greater than $x$. (Assume order is retained)

If $i = |A_1| + 1$ return $x$
If $i < |A_1| + 1$ return $\mathrm{SELECT}(A_1, i)$.
If $i > |A_1| + 1$ return $\mathrm{SELECT}(A_2, i - |A_1| - 1)$.

The biggest issue I am having for constructing a worst case input, is that we need $A$, $M$, and $A_1$ or $A_2$ to exhibit worst-case behavior. Since $M$ is nested in $A$ and $A_1$ or $A_2$ are subsets of $A$, getting all of this coordinated is very difficult.

Additional Notes:

We can always show that the initial recurrence will split into a problem of size $n/3$ and $2n/3$, perhaps we can also do this for the next level down, however I doubt it can be done consistently for levels below. This is relevant and important, because if you can show that our second recurrence will in fact be on something less than $2n/3$, then we have a linear time algorithm! This is because we'd get a recurrence:

$$T(n) \leq T(n/3) + T(\alpha n) + O(n)$$

Where $\alpha < 2/3$ thus, by the uneven split theorem this must be linear a la $T(n) = O(n)$.


texts:
Given the language $K$ $=\{<M> $ where $M$ is a turing machine ( that is on the alphabet {0,1})  and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$
I would like to know if my proof makes sens. I am using the reduction.
Considering the function $f$ given $<M,w>$ ( where M is a turing machine and $w$ is an entry for $M$) returns the description of the following program:
$N_{M,w}$ = entry x
If x is not of form $0^k1^l$ reject x
If x is of form $0^k1^l$ then we simulate $M$ on the entry $w$
If $M$ accepts $w$ then accept $x''$
Note : $f$ is calculable
If $M$ accepts $w$ then $N_{M,w}$ only accepts words of form $0^k1^l$ then $<N_{M,w}>$ is in language $K$.
If $M$ doesn't accept $w$ then $N_{M,w}$ doesn't accept any words and in particular, doesn't accept any words of form $0^k1^l$. So $<N_{M,w}>$ isn't in $K$
So, $<M,w> \in Acc_{MT} \leftrightarrow$  $<N_{M,w}> \in K$ so $f$ is a reduction of $Acc_{MT}$ to $K$ and since $Acc_{MT}$ is undecidable, $K$ is also undecidable.
Does my proof work, if not what do i need to change, it seems to me that i am just applying a recipe seen in class without really understanding totally.. ?
Thanks a lot.


texts: Proof that if a function is computable with standard programs it is computable with Turing Machines

texts: Where can i find a proof related to the subject mentioned?


texts:
Consider the following problem, which can be called "2-SET-PARTITION":

  Given two sets of positive numbers, $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, where $\sum_{i\in[n]}a_i = \sum_{i\in[n]}b_i = 2 S$, decide whether there exists a subset of indices $I\subseteq [n]$ such that:
  $\sum_{i\in I} b_i \geq S \geq \sum_{i\in I} a_i$.

It is easy to prove that this problem is NP-hard by reduction from PARTITION:

  Given an instance $p_1,\ldots,p_n$ of PARTITION, create an instance of 2-SET-PARTITION with:
  $\forall i\in[n]: a_i = b_i = p_i$. Obviously the answer to the first problem is "yes" if and only if the answer to the second problem is "yes".

But, this proof considers only a small subset of the 2-SET-PARTITION --- the subset in which the two sets of integers are equal.  Theoretically, it could be that a "typical" instance of the problem is easy: it could be that there is a subset of instances, which includes all instances except a subset of measure zero, in which 2-SET-PARTITION can be decided in polynomial time. There are similar problems in which this is the case.

To prove that this is not the case with 2-SET-PARTITION, one can use the following reduction:

  Fix some vector of perturbations, $e_1,\ldots,e_n$, such that $\sum_{i\in [n]} e_i < 1/2$.
  Given an instance $p_1,\ldots,p_n$ of PARTITION, create an instance of 2-SET-PARTITION with:
  $\forall i\in[n]: a_i = p_i, b_i = p_i + e_i$. Here, too, it is possible to show that the answer to the first problem is "yes" if and only if the answer to the second problem is "yes".

Intuitively, the second proof is much stronger than the first, because it shows that even arbitrary perturbations cannot make the problem easy.

MY QUESTIONS:

What is a term for this stronger NP-hardness concept, that is robust to perturbations?
What are some references showing proof techniques for this hardness concept?


texts:
I am implementing the dynamic programming algorithm for computing tree alignment distance as described in "Alignment of trees — an alternative to tree edit". But I got stuck in lemma 3 on page 141 (page 5 of pdf). The notations are given at the beginning of section 2. The last case in lemma 3 says

However, there is no recurrence formula given to compute . How did we obtain this?

I don't think the following holds either:
?


texts: Concentration bound for sum of dependent geometric random variable?

texts:
consider following persudocode:

i=0
while(i< k):
    uniformly pick u,v in V
    if(uv in E):
        remove uv form E;
        i++;

let $T$ be the number of iteration of this process,
I know how to compute the expectation, but what is well bound for
$P(|T -E[T]|)$? And is this process independent?


texts:
I am starting a personal bibliographic research on type-checking algorithms and want some tips. What are the most commonly used type-checking algorithms, strategies and general techniques?

I am particularly interested in complex type-checking algorithms that were implemented in widely known strongly static typed languages such as, for example, C++, Java 5+, Scala or others. I.E, type-checking algorithms that are not very simple due to the very simple typing of the underlying language (like Java 1.4 and below).

I am not per se interested in a specific language X, Y or Z. I am interested in type-checking algorithms regardless of the language that they target. If you provide a answer like "language L that you never heard about which is strongly typed and the typing is complex has a type-checking algorithm that does A, B and C by checking X and Y using the algorithm Z", or "the strategy X and Y used for Scala and a variant Z of A used for C# are cool because of the R, S and T features that works in that way", then the answers are nice.


texts: Why does Randomized Quicksort have O(n log n) worst-case runtime cost

texts:
Randomized Quick Sort is an extension of Quick Sort in which the pivot element is chosen randomly. What can be the worst case time complexity of this algorithm. According to me, it should be $O(n^2)$, as the worst case happens when randomly chosen pivot is selected in sorted or reverse sorted order. But in some texts [1] [2] its worst case time complexity is written as $O(n\log{n})$

What's correct?


texts: n-state DFA that requires n-2 steps to check equivalence

texts:
We have a DFA $A = (Q,\Sigma, \delta, q_0, F)$.
States $p, q$ $\in Q$ are equivalent, $p \sim  q$ if $ \forall w \in \Sigma ^ \ast$ $ \delta^*(p,w) \in F \iff \delta^*(q,w) \in F$

States $p,q$ are equivalent after $i$ steps, $p \sim ^i q$, if $ \forall w \in \Sigma ^ \ast$ such that $|w|\le i$ $ \delta^*(p,w) \in F \iff \delta^*(q,w) \in F$

$p \sim q$, if $ \forall i$  $p \sim ^i q$

State equivalence $\sim$ creates a partition $Q/\sim$ of states to equivalence classes.

I am trying to find a $n$-state DFA for all $n \ge 2$ where the state equivalence relation $\sim$ is equal to the state equivalence relation after $n - 2$ steps, $\sim^{n-2}$, but is not equal to the state equivalence relation after $n - 3$ steps, $\sim^{n-3}$.

So I'm searching for DFAs which require exactly $n - 2$ transitions to check the equivalence. I don't know how to approach this problem.


texts: Research in Graph Theory versus Graph Algorithms

texts:
I have a very generic question to ask.  It is related to
research.  I'm interested in Graph theory.  I have done a course in
it.  I have done some topics related to both graph theory as a point
of view of doing it as a mathematics student and also studied some
graph algorithms.  I'm going for research internship in graph theory.
But there is some glitch in my mind that I'm unable to fix about my
real interest in graphs because of lack of proper distinctive ideas
about the real difference in doing research in graph algorithm or
doing graph theory as a mathematics student.  I would like to know the following things:

What is the real difference in doing graph theory as a mathematics student or doing graph algorithms? Do both of them have some real difference?
Can someone tell me some good source for getting research papers on graph theory and graph algorithms.
Is it good to start doing graphs as a mathematics student?

I don't know if it is a right place to put forward such kind of problems.
Please let me know if it doesn't fit here.


texts: Find the minimal subset of rows of some matrix such that the sum of each column over this rows exceeds some threshold

texts:
Let $A$ be a an $n\times m$ real valued matrix. The problem is to find the minimal subset $I$ of rows (if there is any) such that the sum of each column $j$ over the corresponding rows exceeds some threshold $t_j$, i.e. $\sum_{i\in I}A[i,j]>t_j$ for all $j\in\{1,\dots m\}$.

Or, stated as optimization problem:

Let $A\in\mathbb{R}^{n\times m}, t\in\mathbb{R}^m$. Now solve
\begin{align}\min_{\xi\in\{0,1\}^n}&\sum_{i=1}^n\xi_i\\\text{s.t.}&\,A^\top\xi>t\,.\end{align}

Actually, i would need a solution only for $m=2$, but the general might be interesting too.


texts:
Consider the following problem.

The input is a Directed Acyclic Graph. Each vertex $v_i$ may have exactly 0 or 2 incoming edges with associated vertices $v_{i1}$ and $v_{i2}$. If it has 0 incoming edges, it is considered an input vertex. The input of the problem specifies with each input vertex exactly two numbers out of {0,1,2} that may be associated with that input vertex.

Each vertex may have any number of outgoing edges. All vertices that don't have any outgoing edge, are considered output vertices.

The goal of our algorithm is to associate with each vertex a number 0, 1 or 2 that respects the constraints:

each input vertex must be associated with one of its two numbers in the input.
each output vertex must be associated with 0 or 1.
each non-input vertex $v_i$ must be associated with $(v_{i1} + v_{i2}) \bmod 3$.

Example problem and solution:

The general case for this problem should be NP-complete. But in my case, all paths from any input vertex to any output vertex have length at most $c$, where $c=27$. Does this make the problem feasible?


texts: The concept of the creation of a trapdoor in NP-complete or NP-hard problems

texts:
I am reading the book An Introduction to Mathematical Cryptography. In its chapter 7, there is the following statement:

In real world scenarios, cryptosystems based on NP-hard or NP-complete problems tend to rely on particular subclass of problems either to achieve efficiency or to allow the creation of a trapdoor.

Questions:
Is is possible to explain what does it mean the phrase "to allow the creation of a trapdoor"?
Thanks for any help


texts: Modified Bellman Ford to find minmum cost cycle in O(E²V) time?

texts:
I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in $O(VE^2)$ times, and Bellman Ford runs $O(VE)$ time so we are looking at a modification that runs $O(E)$

My approach is first make a directed graph by doubling the edges in both directions, then run Bellman Ford to come up with the shortest path, then compute the strongly connected components in this graph. After you have a tree of strongly connected components, calculate the weights around the perimeter of the SCC and then compare the weights. But I'm not sure how you could calculate SCC using Bellman Ford and this algorithm is going to take too long.

Does anyone see an obvious solution?


texts: If $f(n)=n^a$ for a given $a>0$, find $g(n)$ such that $f(n)\notin O(g(n))$ and $f(n)\notin \Omega (g(n))$

texts:
If $f(n)=n^a$ for a given $a>0$, I need to find a function $g(n)$ such that $f(n)\notin O(g(n))$ and $f(n)\notin \Omega (g(n))$.
I am not sure how to find such function, which satisfies both of the conditions.


texts: Explicit algorithms and algorithms involving unknowns

texts:
Let's assume the you have two algorithms for computing some single but complicated number (e.g., the Ramsey number $R(5,5)$). Both are provided as high-level, half-formal textbook descriptions.

The first algorithm, by means of some textual reformatting and filling in the usual gaps in high-level reasoning, can be easily (say, within several days of coding) turned into a (relatively large) computer program in some imperative programming language, including that of Turing machines (provided appropriate tooling support, of course).
The second algorithm can almost be turned into code in some imperative programming language, except there are some unknown constants (e.g., the algorithm contains an assignment "$x := c^2$", where $c$ is nonconstructively defined by Theorem 5.19.38, which says $\exists\,c\in \mathbb{N}\colon\dots$). In the best case, this algorithm has some merits such as creating a connection to some other area of mathematics, and in the worst case, this algorithm is simply "'print $r$;', where $r$ is the constant $R(5,5)$". We know that the second algorithm solves our task, i.e., that a Turing machine corresponding to our high-level description exists, but we don't know some part of this algorithm exactly.

In mathematical writing, how do you call these algorithms when you provide the reader with them? I mean, how do you distinguish between them? Do you say explicit/nonexplicit? Effective/noneffective? Any other pair of terms?


texts: Can two neighbors in a graph be at the same depth in a DFS tree?

texts: In an undirected graph, can two nodes at an identical distance n from the root of a DFS tree be neighbors in the original graph? I'm thinking no, but I'm not sure (because of back edges)


texts: Steiner tree problem with the known optimal subset of Steiner vertices in approximation algorithms

texts:
I want to prove that the hardness of the Steiner tree problem lies in determining the optimal subset of Steiner vertices that need to be included in the tree and I need to show this by proving that if this set is provided, then the optimal Steiner tree can be computed in polynomial time.

It is clear that we can find an MST on the union of this set and the set of required vertices with Kruskal algorithm, and by contradiction proof, can be said that if this union of sets didn't give the MST so the subset of Steiner vertices is not the optimal subset.  Any hints or tips would be appreciated.


texts: Sorting using k stacks with operation poppush(original stack, adjacent other stack)

texts:
I've been trying to read about sorting algorithms on stacks optimizing the amount of push and pops. One of a number of related probems I'm interested in can be formalized like that:

There is a set of $k$ stacks containing $n$ stack items in total ($n>>k$). The stack items are numbered from $1$ to $m$ where $m < n$ (i.e. several items have the same number). It is given how many items are on each stack including their number and position on the stack. The stacks are arranged linearly so stack $i$ is adjacent to stack $i-1$ and $i+1$ for $1<i<k$. There is no pop or push or peek operation, the only operation on the stacks is a combined pop and push operation which pops an element from one stack and pushes it on a neighbouring stack without returning its value. What is the minimal amount of poppush operations needed to get all items sorted on a single stack and what is such a sequence of poppush operations?

An example problem instance would be: $3$ stacks, $5$ items numbered ${1,2,2,3,4}$ and the first stack is empty, the second has $(1,3,2)$ and the third $(2,4)$ (first number in sequence is on top). I don't know the optimal solution, an arbitrary solution would be

initial ($(),(1,3,2),(2,4)$)
poppush(2,1) ($(1),(3,2),(2,4)$)
poppush(3,2) ($(1),(2,3,2),(4)$)
poppush(2,1) ($(2,1),(3,2),(4)$)
poppush(2,3) ($(2,1),(2),(3,4)$)
poppush(2,1) ($(2,2,1),(),(3,4)$)
poppush(3,2) ($(2,2,1),(3),(4)$)
poppush(2,1) ($(3,2,2,1),(),(4)$)
poppush(3,2) ($(3,2,2,1),(4),()$)
poppush(2,1) ($(4,3,2,2,1),(),()$)

Probably I'm missing some terms for getting better search results, I assume such things have been studied extensively since problems like that occur in sorting physical items using a machine.


texts: Transform 2D range query matrix into segment tree to make memory usage lower

texts: Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x_1, y_1, x_2, y_2)$ which will return the number of ones in the sub-rectangle described with those two points. Since $N$ can be up to $10^4$ we cannot create standard DP matrix for answering the queries in $O(1)$. Is it possible to answer such queries without generating the DP matrix?


texts: Complexity of Monotone (+,2) SAT problem?

texts:
To continue this post, let us define the Monotone$(+, 2^-)$-SAT problem:

Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $F_2^-$ defined on the same variables as $F^+$, where all variables are negated. Is $F^+ \land F_2^-$ satisfiable ?

Is this problem NP-complete?


texts: Pattern calculus : Can I define function for data type with variadic number of type variables?

texts:
apply1 : (a -> b) ->           Foo a ->     b
apply2 : (a -> b -> c) ->      Bar a b ->   c
apply3 : (a -> b -> c -> d) -> Baz a b c -> d

As you see there is a repeating pattern, we obtain a function and a data structure, then we apply that function and return its result...

Is it possible to abstract over this pattern with Pattern Calculus?

How would the definition for generic apply look like?


texts: Application deployement and network models

texts:
I am a self-taught in computer science. I am interested on have a robust test book on which study the nut and bolt of application deployment.
I mean all the processes involved in getting new software up and running properly in a given network. (entry point, rest interfaces etc etc) I went through books of computer networking like Tanenbaum and Kurose but I don't know if these are good choice.
Should I focus on something else?
Many thanks


texts: "Greater than AND smaller than" condition in integer linear program with a binary variable

texts:
I found this related question, but that's not quite it

Is it possible to model this with integer programming:

$$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{cases}$$

where $A \in \{0,1\}$, $B, D \in \mathbb R$ and $C \in \mathbb N$. We have upper and lower bounds on $B$, $C$ and $D$.


texts: Are linear languages always unambiguous?

texts: Deterministic Context free languages are always unambiguous. Now DCFL are a subset of linear languages. Are there any linear languages which are inherently ambiguous?


texts: EVEN-CFL Decidable / Undecidable - Rice-Theorem

texts:
Let EVEN-CFL $=\left\{w | M_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\}$

Question : Is EVEN-CFL decidable?

Am trying to learn this type of proofs

Now the Rice-Theorem states, that semantic properties that are non-trivial are undecidable.

For this, EVEN-CFL is not a syntactic property of a TM, it's a property of the language and it's non-trivial because there exists languages that are context free and others that are not, like recursive languages or they have the length or not.

Is this right so far? How do I proceed now is this it? The use of the RICE-THEOREM

Thanks


texts: A complicated variant of Weighted Median problem

texts:
Suppose, we have an array of numbers $x_j$ and their corresponding weights $w_j$ where $\sum_j w_j \gt 1$. Now we need to find $x_m$ such that

$$\sum_{j=1}^{m-1} w_j \lt 1/2 \quad \text{and} \quad \sum_{j=m+1}^{n} w_j \ge 1/2$$

Moreover, $x_m > x_j$, $x_m < x_k$ where $j \ne k$. i.e. a solution should be like this --

$$\underbrace{x_1, x_2, \ldots, x_{m-1}}_{\lt \, x_m}, x_m, \underbrace{x_{m+1}, \ldots, x_{n-1}, x_n}_{\ge \, x_m} \\
\underbrace{w_1, w_2, \ldots, w_{m-1}}_{\lt \, 1/2}, w_m, \underbrace{w_{m+1}, \ldots, w_{n-1}, w_n}_{\ge \, 1/2}$$

Moreover, it was also mentioned that I may use Dynamic Programming that could be bounded by $O(n\lg n)$.

EDIT:

$\{x_j, w_j\}: \quad x_j \text{ is the value and } w_j \text{ is the weight.}$

Example Input: $\{10, 0.4\}, \, \{5, 0.1\}, \,  \{6, 0.9\}, \, \{2, 0.3\}, \, \{3, 0.1\}$

Example Output: $\{2, 0.3\}, \, \{3, 0.1\}, \,  \underbrace{\{5, 0.1\}}_{x_m}, \, \{6, 0.9\}, \, \{10, 0.4\}$

How I tried

Step 1: First sort the list according to $w_j$. -- $O(n \lg n)$

Step 2: Start from the first element from the left, add the weights $w_j$ until
$\sum_j w_j \ge \, 1/2$. The current $x_j$ is the $x_m$. -- $O(n)$

Step 3: Stop, now we have two lists. One is on the left $L=\{x_1, x_2, \ldots, x_{m-1}\}$ and the other is on the right $R = \{x_m, x_{m+1}, \ldots, x_n\}$.

Step 4: Go through the list $L$, if there is any value $x_k > x_m$, move $x_k$ into $R$ at an appropriate position. Do this until all elements in $L$ is smaller than $x_m$. -- $O(n^2)$

Step 5: if $L \ne \emptyset$, $x_m$ is the answer, otherwise $x_1$ is the answer.

The overall complexity will be $O(n \lg n) + O(n) + O(n^2) \approx O(n^2)$. I got confused about the DP stuff at the end of the question, so I was wondering if there is really any way to do it in $O(n \lg n)$ (or better), how do I build the optimal substructure in the case of DP?


texts: Where does 1.3606 approximation ratio come from for vertex cover approximation?

texts:
I was watching a coursera video on Approximation algorithms and I understood the 2-approximation algorithm.

Later, the professor asks if we can do any better. The lecturer went on to say that computing 1.3606 approximation is NP-hard in the following words at 8:14.
Here's the transcript for that part.

Actually, what is also interesting to note is that okay, maybe we still have some hope that we can get a little bit below two for the approximation ratio, but as the second staple that you see here shows is that it's not possible to get really close to one, but it's impossible to get something better than roughly 1.3, because already computing a 1.36 approximation as you see here, already that problem is NP-hard.

How does he skip from nobody found a 1.99-approximation algorithm
to getting 1.3606 is NP-Hard?
Where does 1.3606 come from?


texts: Algorithm to minimize the damage received from the monsters

texts:
I have been puzzled by the following question on an exam for quite a while: given a set of monsters with their health and attack damage (per second), design an algorithm that minimizes your overall damage received given that you can do one damage to one monster each second. Note: all monsters that are alive attack simultaneously, and the game ends only when all monsters are killed.

Since a greedy algorithm is not going to work, my guess is that there might be a dynamic programming solution to it. The DP algorithms we covered are the knapsack type of problems that are more or less in the form of subset selection, where the only decision made is to determine whether to include the current element in the set or not. However, the problem posted here is about the ordering of the elements (the order I attack the monsters). So it seems to me knowing the optimal solution to a subproblem of any kind would not help me obtain the solution to a larger problem.

I would appreciate hints on how to think about this problem.


texts: How "add" could be implemented in only bitshift operations

texts: Typically, add/subtract/multiply/divide are primitive operations in an Instruction Set Architecture (ISA). I am interested to know if they can instead be implemented efficiently using only bitshift operators. I'm interested to know what sequence of bitshift operations can reproduce the addition operation.


texts: Why is the k-bounded spanning tree problem NP-complete?

texts:
The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$.

I realize that for the case $k=2$, this is the Hamiltonian path problem. However I'm having trouble with cases where $k>2$. I tried thinking about it in the sense that you can add more nodes onto an existing spanning tree where $k=2$ and maybe since the base is NP complete, adding things on will make it NP-complete as well, but that doesn't seem right. I'm self-studying CS and am having trouble with theory, so any help will be appreciated!


texts:
Considering a network of $n$ IT centers $1,...,n$ we can connect by lines which heve different characteristics. Among these charateristics, we take an interrest in the reliability of a line. Thus, let be the error rate $p_{ij}$ which represents the probability for a message channeled by a line tio be corrupted. We admit that the probability are independant. Furthermore, the mise en place of a line entails noteworthy costs that we admit to be be identic for each lines.
The network administrator wants to pass a message toward every center. In order to do that he has to select with the least cost some lines from which the message would go from center to center. All lines and centers form a sub-network. The administrator which that this sub-network would be of maximal realiability.

After having characterzied the type of the graph you are searching for, and defined the reliability of a sub-network, formalized clearly the problem

Show that affecting to each edge the value $\log (1-p_{ij})$, we get a classical problem of graph theory (please do not answer this question wich I wrote because I tought it could help understand the $1^{st}$one)

I have said that it was about the algorithm of Sollin. Indeed, we are
looking for a spanning tree which will allow messages to transit
towards every centers. It has to be with minimal values because we
are searching to minimze the error rate $p_{ij}$ .

After applying Sollin's algorithm we may have:

The reliability of a line is the probability that every center of a sub-network get the message. The reliable rate is $1-p_{ij}$ between two edges. Here it may be $r=(1-p_{12})(1-p_{25})(1-p_{35})(1-p_{45})$

I would "clearly formalize this problem" saying that: We are looking for the spanning tree with the most reliable rate. We want to maximize $\prod (1- p_{ij})$ from a chosen vertice toward the others with Sollin's Algorithm.

But it seems to me that this is not enough. I do not show clearly mathemiatcally the potential cases I may face if I have odd trees... Furthermore, I don't know how the second question help me concluding with this first one...
How can I formalize according to the graph theory and mathematically such a problem?
Don't hesitate to give me only hints if you think I can found it on my own.


texts:
In the context of compilers, what exactly is a loop variable (if there is a standard definition)?

Every read/write make up for the loop variable, or only writes make them up? Or is it writes in the body and reads in the condition?


texts: Rearrange a sequence of real numbers to satisfy polynomial inequalities

texts:
Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$).
Consider a list of real numbers $a_1,\ldots,a_n$, does there exist a permutation $\pi$, such that for all $i\leq n-k$
$$ f(a_{\pi(i)},a_{\pi(i+1)},\ldots,a_{\pi(i+k-1)}) \geq 0$$

How hard is this problem?


texts:
I am wondering if there is an instance where FIFO results in less page faults than LRU. For example:

2,6,5,7...

In this string, if I have to complete it by giving 3 additional terms, can I prove FIFO shows less page faults

I have proved how LRU can show less Page faults. But I cannot think of the initial problem statement solution. Any hints would really be great!


texts: Solving linear system of nonhomogenous equations that are known to have natural solutions

texts:
Any idea is appreciated. A generic approach that works for any system would be best but if you want more info about what I'm looking for, the equations are usually short (having few variables, from 1 to 4 at most), but in exchange, there are a lot of equations (30-60).
The system is known to always have these properties:

The equations are linear and nonhomogenous, coefficients and solutions are natural. In other words, equation $k$ has form $a_{k1}x_{k1}+a_{k2}x_{k2}+...+a_{kn}x_{kn}=b_k$ where

$b_k\in N$
$a_{k1},a_{k2},..,a_{kn} \in N$
$x_{k1},x_{k2},..,x_{kn} \in N$

There is at least one non trivial solution.

Currently I am going with a bruteforce and heuristic approach that tries to narrow down the range I need to bruteforce before trying out all possible values but it can get messy pretty quick when I get a tricky system.


texts: How do I find the intersection of subgraphs in a directed acyclic graph efficiently?

texts:
I have a directory structure in which each directory can have multiple parents (IOW, a cd .. is ambiguous).  AFAICS this means this is equivalent to a directed acyclic graph.

Now, a set of directories (aka vertices) is given.  I need to know all directories which are below all of those given directories.  Thus, I need the intersection of subgraphs.

In my case, getting the set of sub-directories is a rather costly operation.  However, I can do it in parallel, i.e. I can do ls on multiple directories at the same time.

While one can easily think of a brute-force algorithm to do that (collect all vertices in sets, find the intersection of the sets) I wonder whether these is a more efficient algorithm.


texts: Are there any exponential-time iterative algorithms?

texts:
Is it possible to implement an exponential-time algorithm using iteration, as opposed to recursion? I didn't have any particular algorithm in mind, I was just thinking theoretically.

The way I was thinking was to iterate not by adding 1, but by adding a small number j at the end of each loop. So the 3rd parameter in the for-loop would look like i+j instead of i++, and j would be really small (negative exponent perhaps? Like 2^-n)... Still, I'm not sure how such an algorithm could actually work, though.

Thanks for any input.


texts: Summing two array using FFT: time complexity analysis

texts:
This is the problem :

  Given two arrays of $n$ elements A and B, let's define their sum as
  $$ A + B = \{ a + b \mid a \in A \text{ and } b \in B \}. $$
  Calculate $A + A$ in optimal time given that $A[i] \in [1,10n^{1.5}]$ for all $i$.

In order to solve this problem I used FFT by representing a polynomial in the following way:

$$ p(x) = \sum_{i=0}^n x^{A[i]}. $$

After multiplying this polynomial with itself using FFT in linear time, I get the desired result in $\Theta(n^{1.5} \log n)$ time.

However, basic combinatorics gives us that there are $O(n^2)$ elements in the sum of $A + A$, How can I possibly produce them and copy them to a result array all in less than $O(n^2)$ using FFT?