texts: Can an alphabet be extended in a reduction proof? (with sample problem)

texts:
So I am working on solving a problem on whether following language is decideable:

  $L = \{n \in \mathbb{N} \mid M_n$ never freezes (for any input)$\}$, where $n$ is the Gödel-number of a Turing machine.

The model for Turing machines that we use operates on a one-side-unbounded tape, so "freezing" in this context means going "out-of-bounds" on the other side of the tape. We also define a Turing machine as the tuple $(K,\Sigma,\delta,s)$, where $K$ is the set of states, $\delta$ is the transition function and $s$ is the starting state ($\notin K$).

Now I have an idea on how to prove it is not decideable by reduction, but it requires me to construct a new DTM which operates on a new alphabet $\Sigma' := \Sigma \cup \{§\}$, and assume that $§ \notin \Sigma$. (where $\Sigma$ is the alphabet of the machine $M_n$)

My idea is as follows: We prove that $L^c=\{n\in\mathbb{N}\mid M_n $freezes for at least one input$\}$ is undecideable. For that, we construct a DTM $Extend$ which takes $n$ as input. $Extend$ modifies the $n$ so that we get a new machine that operates exactly as $M_n$ would, except with the following tweaks:

For any (state,letter) pair with the $\delta$ function value $\delta(q,\sigma)=(h,\sigma')$ (where h is the halting state), we replace the function value with $(q_{|K|+1},\sigma')$ (so now the machine never halts on its own)
Introduce a new state $q_{|K|+1}$, where $\delta(q_{|K|+1},\sigma)=(q_{|K|+1},\sigma)$ (so if this state is reached the TM goes into an infinite loop).
We introduce a new letter to the alphabet, let's say '$§$', and set it so that $\delta(q,§)=(h,\#)$ (where # is the blank symbol) (so it only halts if any point it reads '$§$')
All of these are turing-computable steps (if we look at $\delta$ as a table of values for every (state,letter) pair (finite), it's the same as going through the table once, changing values as necessary, adding a row and adding a column).

Now we create a new DTM $M_j$ which works as follows (on input $n$):
$>Extend \to L_{\#} \to S_R \to L \to § \to R \to R_{\#}$, where $L_{\#}, R_{\#}$ is a TM which goes left or right respectively until it encounters a blank, and $S_R$ is a TM which shifts the word to the right of it by a blank (so $s,\underline{\#}w\# \vdash^*_{S_R}h,\#\underline{\#}w\#$).
So $M_j(w)$ works as follows: $s,\#n\underline{\#} \vdash^*_{M_j} h,§\#n_{Extend}\underline{\#}$

We know that the set $\mathcal{E}=\{ n\in\mathbb{N} \mid M_n$ accepts $\emptyset \}$ is in $\text{co-RE}$. This means $\mathcal{E}^c = \{ j\in \mathbb{N} \mid M_j$ accepts at least one input $\}$ is recursively enumerable, but not decideable. Since our new DTM $M_j$ only accepts iff $n$ would freeze for at least one input, this means that $n\in L^c \Leftrightarrow j\in \mathcal{E}^c$ and the reduction proof would be complete.

But again, I am not sure if the transformation of $n$ I made (by introducing the letter '$§$' to $\Sigma$) is allowed. Can someone clarify this for me?


texts: What progress has been made on persistent catenable deques in the last decade?

texts:
I'm interested in persistent catenable deques: deques that can be concatenated.

Kaplan and Tarjan came up with the first such data structure in 1995; Okasaki came up with a simpler, amortized version in 1997 using lazy evaluation (see Okasaki for references). Then a couple years later, Kaplan, Okasaki, and Tarjan came up with a simpler implementation using more general mutation in a disciplined manner. Then in 2003, Mihaesau and Tarjan came up with a simpler, non-bootstrapped strictly functional version.

My questions:

The Mihaesau and Tarjan catenable deques appear, to my untrained eye, to offer $O(\log n)$, or possibly even $O(\log(\min(i, n-i)))$ random access (lookup and modify). Is this correct?
Has anyone come up with any simplifications since then?
Has anyone either found a way to combine $O(\log n)$ (or, better yet, $O(\log(\min(i,n-i)))$) splitting along with $O(1)$ concatenation, or proved that it can't be done? For that matter, what about $O(\log n)$ arbitrary insertion and/or deletion?


texts: Arbitrary depth nested for-loops without recursion

texts:
Suppose I have an array of n values I want to apply nested for-loops over to an arbitrary depth m.

const array = [1, 2, 3];

// 2-depth for-loop
for (const i of array) {
  for (const j of array) {
    // do the thing
  }
}

// 3-depth for-loop
for (const i of array) {
  for (const j of array) {
    for (const k of array) {
      // do the thing
    }
  }
}

The obvious solution is to use recursion.  In JavaScript/TypeScript, a generator lends itself well here.  For an example problem, let's calculate the probability distribution of the sum of rolling m 6-sided dice.

type Reducer<T, TResult> = (current: T, accumulator?: TResult) => TResult;

function* nestForLoopRecursive<T, TResult>(
  array: T[],
  depth: number,
  reduce: Reducer<T, TResult>
): Generator<TResult> {
  for (const value of array) {
    if (depth === 1) {
      yield reduce(value);
    } else {
      for (const next of nestForLoopRecursive(array, depth - 1, reduce)) {
        yield reduce(value, next);
      }
    }
  }
}

function reduceSum(current: number, prev = 0): number {
  return current + prev;
}

const pips = [1, 2, 3, 4, 5, 6];

interface RollDistribution {
  [key: number]: number;
}

function rollMDice(m: number): RollDistribution {
  const results: RollDistribution = {};

  for (const result of nestForLoopRecursive(pips, m, reduceSum)) {
    results[result] = results[result] !== undefined ? results[result] + 1 : 1;
  }

  return results;
}

for (let m = 1; m <= 3; m++) {
  console.log(`Rolling ${m} ${m === 1 ? 'die' : 'dice'}`);
  console.log(rollMDice(m));
  console.log();
}

Output

Rolling 1 die
{ '1': 1, '2': 1, '3': 1, '4': 1, '5': 1, '6': 1 }

Rolling 2 dice
{
  '2': 1,
  '3': 2,
  '4': 3,
  '5': 4,
  '6': 5,
  '7': 6,
  '8': 5,
  '9': 4,
  '10': 3,
  '11': 2,
  '12': 1
}

Rolling 3 dice
{
  '3': 1,
  '4': 3,
  '5': 6,
  '6': 10,
  '7': 15,
  '8': 21,
  '9': 25,
  '10': 27,
  '11': 27,
  '12': 25,
  '13': 21,
  '14': 15,
  '15': 10,
  '16': 6,
  '17': 3,
  '18': 1
}

My understanding is that any recursive function can be rewritten iteratively, though it usually requires some augmentation.  (For example, an in-order traversal of a binary tree can be done iteratively if you augment each node with two bits and a parent pointer.)

How can I rewrite nestForLoopRecursive() without using a stack or any other recursive data structure?  In particular, is it possible to do this in at most O(n lg(m)) space?

Here's a CodeSandbox with everything needed written in TypeScript.  The code yet to be written starts at line 16.  Feel free to answer using whatever language you choose, though, including pseudocode.


texts: Efficiently finding the min-cost path of an AVL tree

texts:
It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree:

The min-cost path would be 8-6-5. However this is not the case with other AVL trees. Take the previous tree with an additional 4 inserted:

Here the min-cost path would be 8-6-7 rather than 8-6-5-4.

What is the most efficient algorithm to find the min-cost path in any AVL tree? Given the characteristics of AVL trees, is this algorithm faster than it would be for a standard BST?


texts: How to test image segmentation algorithms?

texts: What would be an ideal environment/manner to judge the effectiveness of multiple segmentation algorithms? The goal is to determine which algorithms provide the best results for pre-clinical imaging. Our group has considered a GUI in MATLAB, and have different modules for different algorithms. Various papers have conducted such algorithm analyses in clinical scenarios, but none give an indication to their environment.


texts: Are cache contents specific to a process?

texts: Suppose the L1 cache is filled up with data from some process. Now CPU loads another process. Does the new process share cache contents? Or the cache has to be invalidated completely in each context switch?


texts: Can this equation be solved in polynomial time?

texts:
I came across a more general form of this question.

Can we find the value of variables in polynomial time ?

Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ values can only take positive integer values ranging from 1 to $n$.

We have equation generator,
$$a\cdot f(x)+b\cdot f(y)+c\cdot f(z)+\cdots=k$$

for variables $x,y,z\in \{1,2\ldots, n\}$.

$f$ can be any thing such as $x, x^{2}, \log x$ etc.

Given that the constants are rational numbers and that there exists a solution, can we solve for the variables in polynomial time?

Update: Please note that I am not giving a single instance of $a\cdot f(x)+b\cdot f(y)+c\cdot f(z)+\cdots=k$, instead I am giving you the entire family of all possibilities of the above equation.

Basically I am giving you a black box, if you input $f$ it gives you corresponding $k$, given that $f$ is computable in polynomial time. We can do this multiple times. The goal is to solve for variables using this black box, in a polynomial time.

So we have:
    1. The values of $m$ and $n$
    2. The constants $a,b,c ...$
    3. The equation generator $a\cdot f(x)+b\cdot f(y)+c\cdot f(z)+\cdots=k$

We can go on choosing different $f$ and the generator will give us corresponding equation, with a new $k$.

Goal:
To solve for variables in the equation when $f(x) = x$

Update 2: For people wondering the origin of the question and its purpose. If the answer for this question is yes, then I think Sudoku can be solved in polynomial time. I tried to make use of the numerical property of Sudoku, that the sum of the entries of any row or column is known. By dealing each unknown cell as a variable we could treat each row and column as an equation. For a Sudoku of $n*n$ it would result in $2n$ equations with $n^2-k$ variables where $k$ is the number of already filled cells. This is an underdetermined system of equations. We could represent this in a matrix and it can be reduced to Echelon form. This can be repeated for sum of squares, cubes etc etc of the values. If we could solve this we could solve Sudoku.


texts: Which function grows faster: N Log N or N^(1+ε/√(log N))

texts:
How would you go about solving this problem?

I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation.


texts: Unary notation representation in Turing Machine

texts: What can be a good convention to represent positive and negative integers in unary notation on a Turing machine? I want to design a Turing machine which acts as a subtractor.So should I partition the integer range to represent positive and negative integers in unary notation or is there some other way?


texts: Set that keeps unique categories of objects

texts:
I would like to know if this type of special set operator exists, and if yes what is it called and if it has any other special properties.

Lets say I have this set $S$ of items. Like all sets, if the same item is added twice in the set, the set will not add it again. However, when adding an item, using this special operator, it also checks if it is 'better' than another item already in the set, and if yes it replaces it with the new item rather than letting both.

For a more concrete example:

$S_1 = \{apple, orange, pear\}$

$S_2 = \{betterApple, orange, banana\}$

$S = S_1 \cup_\succ S_2 = \{betterApple, orange, pear, banana\} $

So in this case $\cup_\succ$ checked some relationship, lets say $\succ$ where $betterApple \succ apple$, and if such a relationship existed it dropped $apple$ rather than allowing both in the set, keeping the stronger one in the set.


texts: Is boolean validity a harder problem than satisfiability?

texts: I am aware that satisfiability is NP complete and unsatisfiability is co-NP complete. But somehow I feel that labeling satisfiability as NP-complete and unsatisfiability as co-NP complete is papering over the fact that unsatisfiability (or equivalently validity) is inherently a harder problem than satisfiability. Suppose I have a NDTM. Then given a potential model I can surely check it in polynomial time. However to check unsatisfiability I would need to check all possible assignments, surely this makes the problem EXPTIME?


texts: Sum of heights in a complete binary tree (induction)

texts:
I need to prove the following statement using induction on the number of nodes in the tree:

The sum of heights of a complete binary tree is $\theta(n)$.

Note: I've tried proving this using mathematical sums. I did manage to show that the sum of heights (lets call it $sum(n)$) is in fact $sum(n)≤c_1n$ for some $c_1$. But, I couldn't show the lower bound ($sum(n)≥c_2n$ for some $c_2$).

The base case is a complete binary tree, with 3 nodes in the height of 1.

The assumption is that for a complete binary tree $T$ with $n$ nodes $sum\in\theta(n)$

I got stuck when i got to the phase of the step. My intuition is to add to the tree another depth of leaves and to prove for the new tree.

Can someone explain how to complete this step?


texts:
Recently I came up with a traveling-salesman-esque problem. As usual, we have $n$ vertices, and a weighted edge between any two vertices. However, each vertex is associated with a color, which may be repeated. Then, you are given a sequence of colors, and you want to find the shortest path that follows this sequence. If all vertices are the same color, this is the same as TSP. However, if all vertices are different colors, there is only one solution.

Is this variant at all studied? Let $c$ be the maximum number of vertices which are the same color. Is the decision problem this variant NP-complete for some fixed, $c$, or alternatively is there a simple way to solve the decision problem polynomially for any finite $c$? Alternatively, one can bound $k$, the mamximum amount of times a given color appears in your path.

For $k=1$, it is polynomial. WLOG we can assume the path goes through colors $1,2,3,\ldots,x$. For each vertex of color 1, we consider each edge to a vertex of color 2. We keep track of the shortest path from color 1 to each vertex of color 2. Rinse and repeat for each color. This only requires $|\mathrm{color}\  i||\mathrm{color}\  i+1|$ additions and comparisons to get the shortest paths to each vertex of color $i+1$.

Additionally, I realize $k$ only matters if it is less than $c$, so bounded $c$ is polynomial if bounded $k$ is polynomial and bounded $k$ is NP-Complete if bounded $c$ is NP-Complete.


texts: Efficient queriable data structure to represent a screen with windows on it

texts:
(this is related to my other question, see here)

Imagine a screen, with 3 windows on it:

I'd like to find an efficient data structure to represent this, while supporting these actions:

return a list of coordinates where a given window can be positioned without overlapping with others

for the above example, if we want to insert a window of size 2x2, possible positions will be (8, 6), (8, 7), ..

resizing a window on the screen without overlapping other windows while maintaining aspect ratio
insert window at position x, y (assuming it doesn't overlap)

Right now my naive approach is keeping an array of windows and going over all points on the screen, checking for each one if it's in any of the windows. This is $O(n\cdot m\cdot w)$ where $n, m$ are the width, height of the screen and $w$ is the number of windows in it. Note that in general $w$ will be small (say < 10) where each window is taking a lot of space.


texts: Why can't exhaustive search parsing stop after |w| + 1 derivations?

texts:
If my grammar does not have productions of the form $A\rightarrow\lambda$ and $A\rightarrow B$ for some variables $A$ and $B$ then I know that each step in the derivation must involve an increase in the sentential length. Therefore if I do an exhaustive search for some word $w$ then I know I can stop searching after $|w|$ derivations.

My question is why then do textbooks assert that we can stop after $2|w|$ derivations instead? Yes, I agree that this is true, but wouldn't it be easier just to stop at $|w|+1$ and above? What am I missing for this condition?


texts:
Crossposting due to recommendation.

I formulated a MIP problem which I didn't expect to be unimodular. The problem is to find a minimum complete sequence in a strongly connected digraph. That is, minimize the number of edges such that connectivity is preserved, using only previously existant edges. This will be a Hamiltonian cycle if such a cycle exists.

I've verified it with AMPL/CPLEX and it at least seems to be a correct formulation. Solving the LP-relaxation, I found that it consistently provides IP-feasible solutions.

But the issue is that the minimum complete sequence problem is NP-complete. Is it even possible that I have a correct formulation given that I get a TU constraint matrix? Any ideas on how to prove that it's TU (I'm far from an expert on this thing)?

Here's the model (option relax_integrality 1; for the LP-relaxation)

$\begin{align}
\min \sum_{i,j} x_{ij} &\\
\sum_j x_{ij} &\geq 1 & \forall i\\
\sum_i x_{ji} &= \sum_i x_{ij} & \forall j \\
\sum_n y_{ij}^n &\geq 1 & \forall i,j \\
y_{ij}^1 &= x_{ij} & \forall i,j\\
x_{ij} &\leq z_{ij} & \forall i,j\\
y_{ij}^n &\leq (y_{ik}^{n-1}+x_{kj} - 1) + M(1-b_{ij}^{nk}) & \forall n \neq 1, i, j, k\\
\sum_k b_{ij}^{nk} &\geq 1 & \forall i,j,n \\
x,y,b &\in \{0,1\}
\end{align}
$

$y^n_{ij} = 1$ iff there exists a path of length $n$ from $i$ to $j$. $z_{ij} = 1$ implies that the edge $i,j$ exists in the original graph. $b$ is a binary hack to formulate the connectivity constraint.

edit: $i,j,k,n$ all range from $1$ to $N = $ number of nodes. I realize that the constraint matrix actually can't be unimodular due to the presence of $M$ which is some arbitrarily large number. But the LP-relaxation constantly spits out integer feasible solutions, which for smaller graphs actually correspond to known optima and for larger graphs seems to check out as well.

edit: After examining the problem closer, I found that

a) the formulation is indeed correct

b) the linear relaxation consistently provides integer solutions with respect to x and y, but NOT b. It seems as though the b:s are basically conspiring to turn the problem totally unimodular. Setting $M = 10000$, b would constantly set itself to 0.99999 to minimize slack. This makes the x and y variables ONLY take on binary values. This is maybe obvious to experts but I found it extremely surprising. I have yet to see a case where it doesn't find the actual optimum, but this is probably due to a lacking setup of example graphs.


texts: Does Bloom filter with false positive rate greater than 0.5 make sense?

texts:
If the false positive error rate is greater than 0.5 then a Bloom filter is no different from coin flip, right?

Still, if one does implement this data structure with, say, P=0.55 then it would still work.

Should the constructor method of a Bloom filter implementation forbid values of P greater than 0.5?


texts: Prove the crossing number of complete graph with 7 vertices is greater than or equal to 7

texts:
I am trying to prove that the crossing number of complete graph with 7 vertices is greater than or equal to 7. I know that edges (m)=21 if it is complete, and if the graph were planer 2n = degree of faces, which I think is a minimum of 3 per face. So 2m gte 3f. Based on Euler's formula 3n-3m+3f gte 6 (scaled by 3) then I sub in 2m as 3f and rearrange for m and get m gte 15. If there are 21 edges to begin with and only 15 when it is planer, then 6 edges were removed which means 6 crossing points were removed, however I need to prove that the number of crosses is gte 7 not 6.

I am not sure where I am going wrong/ what I am missing


texts: Various implementations of adjacency list representation of a Graph

texts:
Just started learning about graph and it's various representations (matrix and adjacency list). Now I found that the adjacency list representation can be implemented in various ways:

Array of arrays (where we have one index in main array for each
vertices and adjacent vertices are in subarrays at each of this
index)
Array of linked lists (most common implementation I have seen)
Map of array (same as array of arrays, except that outer array is
now a Map)

Was wondering why would I prefer one of these implementation over the other. Is one implementation more common or efficient in any way or they all the same?


texts: How to prove $L \notin \texttt{DSPACE}(f)$

texts:
I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to prove:

$$
L \notin \texttt{DSPACE}(f(n))
$$

How would I do this?

My first attempt was to reduce a language $L'$ from $\texttt{DSPACE}$ to the language $L$, but I don't know of any language in $\texttt{DSPACE}$ and I don't know if I can "simply" reduce it. Does anyone have a reduction that I see and try to understand?

The exact exercise specifies the language $L$: it is $\{ w\mid w \in T(M_w),M_w \text{ needs space |w|}\}$.

Also, we are given that $f(n) \in \Omega(\log{n})$.


texts: Can we see all of mathematics as an attempt to simplify computations?

texts:
This is a rather strong claim, and therefore likely to be incorrect, but hear me out.

Firstly, when I talk of “computations”, I mean this in a broader sense than normally used, because I am including “infinite computers”, e.g. Turing machines that can perform computations not in a finite amount of steps, but infinite or even uncountable. e.g., a Turing machine that can check (using an uncountable number of computations for any subset of an uncountable $X$ whether it is open in $(X,T)$ is allowed.

This means my question is inherently a bit vague, because I don’t know a lot about infinite Turing machines, and I am not sure how “computational complexity” is defined for such infinite Turing machines (and not sure if it has been studied at all).

But it seems to me that if you squint your eyes, many theorems in math can be seen as performing the role of “simplifying computation”:

  Claim. Every mathematical definition gives a (possibly incomputable in finite time) algorithm.

Example. Definition: A function $X$ to $Y$ is continuous iff every open set in $Y$ has open preimage. This gives an algorithm: Check for each open set in $Y$ whether the preimage is open in $X$. (algorithm requires infinite computational time for uncountable spaces).

Many theorems can be seen as “simplifying computations”:

Some theorems turn incomputable algorithms into computable algorithms. For example, the algorithm that checks whether a function $f$ is made up of a composition of a database of other continuous functions, is computationally simpler than the algorithm induced by the definition of continuity (though can only verify, and only for a subset of functions)
some theorems turn incomputable algorithms into still incomputable but “less complex” algorithms.

I’m gonna make a (largely unwarranted) generalization from this:

  Bold and weakly substantiated claim. Every non-trivial theorem in mathematics can be seen as motivated by an attempt to reduce an algorithm (possibly requiring infinite computation) that answers questions $Q$, to a simpler algorithm that answers questions $Q$ or some subset thereof.

Do you think there is something to this? Are there a preexisting ideas about this?


texts: Finite Automata: Final vs Accepting States

texts:
What is the difference between a final and accepting state when addressing an automaton?

As I understand it, a final state is depicted (traditionally) with a double circle, and apparently so is an accepting state. So if they are both depicted with the same symbol, what makes  a state particularly accepting?


texts: How to calculate the number of tag, index and offset bits of different caches?

texts:
Specifically:

1) A direct-mapped cache with 4096 blocks/lines in which each block has 8 32-bit words. How many bits are needed for the tag and index fields, assuming a 32-bit address?

2) Same question as 1) but for fully associative cache?

Correct me if I'm wrong, is it:

  tag bits = address bit length - exponent of index - exponent of offset?

  [Is the offset = 3 due to 2^3 = 8 or is it 5 from 2^5 = 32?]


texts: Reduction from $A$ to $B$ as execution of Turing machines

texts:
As explained in answers to this question, reduction from $A \le B$ can be represented in the following way.

But in this example:

from here
At least as I understand it:
The reduction is from $\overline{HP}$ to $L_2$, so $A$ is $\overline{HP}$ and $B$ is $L_2$.
But it's implemented in the way that $M'$ is TM of $L_2$ and $M$ is TM of $\overline{HP}$, and $M'$ execute $M$ (I mean $L_2$ is the external and $\overline{HP}$ is the internal).
Where am I wrong?


texts: CFG to CFL conversion (production rule with both left and right recursion)

texts:
Is there a general rule to convert a CFG to its CFL?
For example, how do I approach the following question?

What is the language generated by the following CFG?
$$ S \to aS \mid Sb \mid \epsilon $$

As per my understanding, $S\to aS$ is $a^*$ and $S\to Sb$ is $b^*$.
But how do I make sure that the language is $a^* b^*$ without having to derive a lot of strings?
In particular, is there a way to make it either in left or right recursion, so that it is easier to understand the structure?


texts: Combining these two results into one asymptotic notation

texts:
Assume you have two parameters, $N \gg 1$ and $\epsilon < 1$.

I have an algorithm (and matching lower bounds) that runs in $\Theta(\epsilon^{-1}+\log N)$ for $\epsilon > N^{-1}$, and $\Theta\big(N\log\big(\frac{2}{N\epsilon}\big)\big)$ otherwise.

I would like to write it using one notation (possibly with $\max$ or $\min$ operands), but can't get it right.

The problem is that $\log\big(\frac{2}{N\epsilon}\big)$ is negative for large values of $\epsilon$, so it doesn't seem to fit.

Any help will be appreciated :D.


texts: A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements

texts:
I am familiar with the decision tree based argument for the minimal number of comparisons required to sort $n$ distinct elements - Since there are $n!$ permutations on the $n$ elements, the decision tree for any comparison based sorting algorithms must have at least $n!$ leaves, and therefore at least one path of length $\left\lceil \log_{2}\left(n!\right)\right\rceil $, corresponding to the worst case performance of said algorithm.

Question: The condition $$\left\lceil \log_{2}\left(n!\right)\right\rceil \leq\#\text{ of comparisons in the worst case}$$

is a necessary  condition for any comparison based sorting algorithm. Is it also sufficient? e.g. if I am asked if it is possible to sort 5 elements in 7 comparisons, does it suffice to observe that $\log_{2}\left(5!\right)<7$ to deduce that such an algorithm must exist?


texts: Difference between memory access and write-back in RISC pipeline

texts:
I'm a little confused about the difference of the memory access and the write-back stage in a RISC pipeline.

We learned in class these following assumptions:

arithmetic & logic: IF, OF, EX, WB
load: IF, OF, EX, MA, WB
store: IF, OF, EX, MA
branch: IF, OF, EX

IF=Instruction Fetch, OF=Operand Fetch, EX=Execution, MA=Memory Access, WB=Write-Back

Lets say we have the following code now:
    I1: LD R1, 0(R2) ; load R1 from address 0 + R2
    I2: ADD R1, R1, #1 ; R1 = R1 + 1
    I3: ST 0(R2), R1 ; Store R1 at address 0 + R2

According to what I've learned I1 will pass all five stages, I2 won't have to access the memory, and I3 won't have a write-back.

But then I wonder, how and where does I3 store the value then? Just in the memory? And I2 fetches the value from memory, but needs to write-back to some place other than the memory? So does that mean that write-back is always to the HDD?

I think I'm missing some core concepts here, as to where the operand is fetched from and where it gets stored to.


texts: Prove that the number of edges is at least twice the number of vertices

texts:
I need to prove that

  In a simple graph $G$, if all the $n$ vertices have a degree of at least $4$, then the number of edges is at least twice the number of vertices.

I already know that $\deg(n) = 2E$.

Then for the question
$$\deg(n) \ge 4 = 2E$$

but then I couldn't solve further.


texts: Turing Machine remembering copied symbols

texts:
So, I know that any multiple-tape TM can be in theory turned into a one-tape TM. However, it is too easy to copy, let's say, binary numbers from one tape to another. That's why I thought about putting a separator between the two copies and then taking symbols one after the other and writing them after the separator until the separator itself is encountered. The problem, however, is that I am not sure how it could remember places where it has already been/copied the characters. Example:

First we have:

##1011##

Then we put the separator '&' at the end

##1011&##

Read back to beginning and change the state accordingly so that it will write $1$ or $0$ after the separator. So far, so good, then we read back again, and now:

How could we know that we have already copied the first $1$ and must now copy the $0$ without putting any restriction on the input length (in regards to the number of states)? In other words, how could we remember the last copied symbol?

I have thought of putting an extra parameter - just a integer ≤ length (something like $\delta (z_1,1,L,1)$ where the last one would be the number of already written-out symbols). This would be easy to understand, but would be nowhere near the definition of Turing machine. So, any useful ideas?

Thanks.


texts: Reducing Vertex Cover to Half Vertex Cover

texts:
I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction:

Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects all edges?

Half Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects exactly half the edges?

I will be happy if you can tell me how to do that and why the reduction works (both directions of the proof).


texts:
Let's consider the following problem (buckets/pails  of water problem) (This problem may be known with different name. If does, please correct me).

Let $B=\{b_1,...,b_n\}$ be a set of $n$ buckets. Suppose each bucket has a maximum capacity $c_i \in \mathbb{Z}$. This also can be written as a maxium capacity function $f:B \rightarrow \mathbb{Z}$ such that $f(b_i)=c_i$.

Let $g:B \rightarrow \mathbb{Z}$ be a function such that $g(b_i)$ is the current amount of water in bucket $b_i$.

Suppose that we can do the following operations.

1.Fill bucket $b_i$ from tap until its full, i.e. $g(b_i)=f(b_i)$.

2.Move water from bucket $b_i$ to bucket $b_j$ until $b_i$ is empty or $b_j$ is full.

3.Empty bucket $b_i$.

Now, the problem is given a number $m \in \mathbb{Z}$ to find a sequence of operations $s_1,...,s_k$ such that after $s_k$ we have a bucket with $m$ amount of water, i.e. $g(b_i)=m$ for some $i \in \{1,...,n\}$, or return that such sequence doesn't exist.

My questions are :

1.How to solve this problem? Is this problem NP Hard? If it is NP Hard, why? How to prove this?

2.What about the case when we are interested in the optimal $k$, i.e. we want minimum number of steps?

3.Does this is a well known problem? If yes, what is the known name for the problem and what good references exists for this problem?

I want to note that I fully understand the case of $n=2$, and I am interested in the generalization of $n$ buckets instead of just $2$. The $n=2$ case described in https://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle.

Edit: I now know how to prove that this is NP Hard problem. I want to know if there is an efficient algorithm for solving this (maybe some pseudo polynomial algorithm).


texts:
I have a problem that can be reduced to an assignment problem.
(In a previous question i found out how to do that.)

Which means we have a set $A$ of agents and a set $T$ of tasks as well as a cost function $c(i,j)$. We need to find an assignment so that the total cost is minimal.

The hungarian algorithm can find an optimal solution in at least $O(n^4)$. Which sounds good to me.

My new Problem is:
There is a given number of days. I have to solve the assignment problem for each day so that every task is done every day and no agent does the same task twice.

What I have tried:
We could run the hungarian algorithm separately for each day and limit the number of possible combinations based on the result of the previous day. But this would get us into trouble at some of the later days, where most likely it will be impossible to find a feasibly solution.

Another idea is to somehow integrate local search to change decisions made at a previous day. But I think we can't rely on this.

The problem instances I have to face will be somewhere around $|A| = |T| = 500$. The cost matrix $C(i,j)$ will have lots of same values (E.g. mostly 1 or infinity, only some 2 or 3). So during the hungarian algorithm there is a lot of space to create different optimal solutions for a single day.

I'd be glad to hear some ideas or advises how to find a good solution for the problem.
Thanks in advance.


texts: What crossover operator should I use for arranging students in classrooms?

texts:
I am building a genetic algorithm to solve a "classroom map" problem. The goal is to place correctly students depending on several factors (shortsighted students, turbulent students...).
Here, the genomes is the classroom layout, each classroom has a fixed blackboard and tables positions, what varies is the position of the students.
Now, if I want to cross two classrooms genomes, I can't simply mix both together, otherwise, say that on genome A student "Bob" is on table #3, and that on genome B the same student "Bob" is on table #15, and that the "child genome" gets table #3 from genome A and table #15 from genome B, then, "Bob" would be on two tables at the same time... no really great.

How can I solve this issue ?

Thank you.


texts: Language of rationals is regular, what is the number set equivalent to PDA?

texts:
Consider rational numbers given as their decimal expansions, then for every number we can build a finite automaton able to accept it.  To simplify the argument, assume that finite rational expansions are followed by an infinite number of zeros.  In such case it is easy to see that the automaton that accepts such numbers would have to have a finite (possibly empty) non-repeating part and a repeating part.  The automaton accepts the number in the same sense as $\omega$-automata do, i.e.

  A run of a Büchi automaton on an $\omega$-word is an infinite sequence  of states and transitions.

  A run is accepting if it visits the set of final states infinitely often.

Source (Wikipedia article is non-functional in this regard)

Looking for a similar equivalence with PDA I thought of continued fractions as a good candidate, but I don't have a good way to get convinced / dissuaded that is the case.

Some of my thoughts in this direction: what is the number representing the Dyck language? Suppose you encode open parenthesis as 1 and closing parenthesis as 0, and the number is thus given by $\{w\;|\;\#(w)_0 = \#(w)_1 \land \forall vu = w: \#(v)_0 \leq \#(v)_1\}$. To me this seems like a whole class of numbers rather than a single number, but maybe my example is unhelpful.


texts: Gas Station Problem - Dijkstra's Algorithm variation

texts:
I am trying to find an algorithm which finds the least expensive route from one town to another.

This is the general setup.

There are a series of one-way roads from some towns to other towns. Not all towns have roads between them. Let R be the set of all the roads and let T be the set of all towns. For two towns u, v ∈ T, let (u→v)∈ R be the one-way road from u to v and let w(u, v) be the amount of gasoline required to travel along this road.

Let S ⊂ T be the set of towns which have gas stations. At a town u ∈ S, one can choose to pay c(u) dollars to fill up the gas tank. Note that the cost does not change depending on how much gas must be bought; if you need to buy gas, fill up the whole tank. The cost is only affected by which town u is.

The car’s tank can hold k units of gas and it is full at the start.

My ideas:

I believe this uses a shortest path graph algorithm, but I am unsure how to implement it. I believe it uses Dijkstra's algorithm. I also recognize that the run-time depends on |T|, |R| and |S|.

Any advice will help! thanks :)


texts:
I am a beginner to complexity theory and I came up with the following proof of decidability of

$A_{Cfg}$ = {$<G,w>|G$ is a context free grammar that generates string $w$}

The Turing machine which decides $A_{Cfg}$ first converts the given grammar into a non-deterministic push down automata NPDA. And then we do an epsilon closure to this NPDA to get a non-determinstic push down automata without any $\epsilon$ moves N.

Now we can directly simulate N on a turing machine. Since we can be sure that N halts, our turing machine also halts deciding $A_{Cfg}$.

Is there any mistake in this proof because Sipser uses Chomsky normal form for this and I think this is simpler?


texts: Given a directed graph G(V,E) and a node s, how do we determine what nodes are reachable from s? Do I need simple traversal algorithms or do I need to look at Tarjan's algorithm?


texts: Generate all non-isomorphic bounded-degree rooted graphs of bounded radius

texts:
I need to generate/enumerate isomorphism classes of vertex-rooted graphs with the following properties. Let $\Delta$ be the maximal degree (say 3 for subcubic graphs) and $r$ the maximal distance of a vertex from the root (something like radius, even though the formal definition of radius of a graph is different). Note that the requirement also means the graphs are connected.

Note that rooted graphs are isomorphic if there exists an isomorphism that respects the root, i.e., sends root to root.

It is clear that for fixed $\Delta$ and $r$ there exist only finitely many such graphs. The number of them will be huge, but still drastically smaller than the number of all graphs or all bounded-degree graphs on the same number of vertices.

Example: For $\Delta=2$ and $r=1$ we would get exactly $4$ graphs: (1) just the root, (2) an edge with one vertex the root, (3) a cherry with the root in the middle and (4) a triangle with one vertex the root.

The case I am mostly interested in is $\Delta=3$ but if possible I would like to be more general.

Question: Is there some software or a collection that provides this? If possible, I would like to avoid coding the whole thing myself as this seems to be a rather complex task (generating non-isomorphic graphs in a reasonable efficient way).

I am aware of nauty, which can check isomorphism and also generates certain types of graphs. But after reading the manual, I think there is no option to generate rooted graphs (there is option to generate bounded-degree graphs, though).

Does anyone have an idea how to do this without spending a lot of time writing my own generator?


texts: What's the best non-amortized disjoint set?

texts:
In practice, the amortized O(α(n)) data structure is good for every case. But if I want to be pedantic and require each operation to be under a certain time complexity, what's the currently known best complexity, and is it optimal?
The normal disjoint set implementation with recorded rank (height before optimization) could make it into O(log n). One could also get O(log n) using trees or heaps. But could it be better?
One possible use case is, if I found an algorithm mostly in O(log log n) but also has a disjoint set operation, it seems awkward to say it's amortized O(log log n) but at most O(log n) for each operation. Much better if it's just O(log log n) without "amortized".


texts: NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

texts:
In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if:

They are vertex-disjoint.
Each one is itself an induced path.
No edge connects two vertices of two different paths.

Given a set of sources $\{s_1,\dots,s_k\}$ and a set of sink $\{t_1,\dots,t_k\}$, a set of $k$ path connecting the given sources to the given sinks is such a set of paths that:

For each source $s_i$, there exists exactly one path that connects it to some sink $t_j$
For each sink $t_j$, there exists exactly one path that connects some source $s_i$ to it.

  Input: A graph $G(V,E)$ and a set of $k$ sources $\{s_1,\dots,s_n\}$  and a set of $k$ sinks $\{t_1,\dots,t_k\}$

  Output: YES if there exists (a set of) $k$ induced paths connecting $\{s_1,\dots,s_k\}$ to $\{t_1,\dots,t_k\}$ for every $1\leq i\leq k$, NO otherwise.

Is this problem NP-complete?

Note that there is a related earlier question here, but its input is slightly different.


texts: Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard?


texts: What is the difference between "for infinitely many n" and "for all n"?

texts:
I have read some complexity papers in which "for infinitely many input sizes" is used.

What is the difference in the computational complexity context between "for infinitely many input sizes" and "for all input sizes"?


texts:
I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data.

Basically it uses prime numbers to uniquely construct a representation of 4-byte data chunks which are easy to decompress given that every number is a unique product of primes. In order to associate these sequences with the primes it utilizes a dictionary.

My question is:

Is this really feasible as the authors suggest it? According to the paper, their results are very efficient and always compress data to a smaller size. Won't the dictionary size be enormous?
Couldn't this be used to iteratively re-compress the compressed data using the same algorithm? It is obvious, and has been demonstrated, that such techniques (where the compressed data is re-compressed as many times as possible, dramatically reducing the file size) are impossible; indeed, there would be no bijection between the set of all random data and the compressed data. So why does this feel like it would be possible?
Even if the technique is not perfect as of yet, it can obviously be optimized and strongly improved. Why is this not more widely known/studied? If indeed these claims and experimental results are true, couldn't this revolutionalize computing?


texts: Analyze undirected weight graph and generate two sub graphs

texts:
I have a weighted undirected graph $G_0$, from which I want to derive weighted undirected graphs $G_1$ and $G_2$.

All nodes in $G_0$ have a degree of at least one.
$G_1$ and $G_2$ can contain the same node but not the same edge.
All nodes in both $G_1$ and $G_2$ should have a degree of at least one.
All edges from $G_0$ should be contained in either $G_1$ or $G_2$
Both $G_1$ and $G_2$ are subgraphs of $G_0$ and cannot contain additional nodes.
Edit (Added constraint): $G_1$ and $G_2$ are both traversable trails

Let's assume that the sum of all the edges in $G_0$ is $x$.

I need to find the pair of $G_1$ and $G_2$ for which the sum of all edges in $G_1$ is closest to $x/2$.

How would you go about solving that?

Edit: After much hassle due to my lack of explanatory powers, here is a better explanation of the problem (this is for an unweighted graph, but it will at least point me in the general direction of a suitable algorithm, also it avoids technical terms because is obvious that I struggle understanding them at the moment)

Lets assume that we have an undirected Graph with Vertices A,B,C,D,E

A --- B
|   / | \
|  /  |  C
| /   | /
D --- E

Which means an adjacency matrix like this one:

  A  B  C  D  E
A -  1  0  1  0
B 1  -  1  1  1
C 0  1  -  0  1
D 1  1  0  -  1
E 0  1  1  1  -

Assuming all edges are undirected, we have the following edges:

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

What I want is to generate two groups of edges of roughly the same size. (In this particular case, since we have 7 edges, we would get a group of 3 edges and another one of 4 edges.

Group 1: (a,b) (a,d) (b,d) (e,d)
A --- B
|   /
|  /
| /
D --- E

Group 2: (b,e) (b,c) (e,c)
B
| \
|  C
| /
E

Notice that all edges in each group are connected by at least one node, that is a requirement.

Another valid solution could be, for example:

Group 1: (d,a) (a,b) (b,c) (c,e)
A --- B
|      \
|       C
|      /
D     E

Group 2: (d,b) (b,e) (e,d)
      B
    / |
   /  |
  /   |
D --- E

And so on, as you see there are many valid solutions but I want to know if there's an algorithm to find one.


texts:
As part of some blockchain-related research I am currently undertaking, the notion of using blockchains for a variety of real-world applications are thrown about loosely.

Therefore, I propose the following questions:

What important/crucial real-world applications use blockchain?
To add on to the first question, more specifically, what real-world applications actually need blockchain - who may or may not currently use it?

From a comment, I further note that this disregards the notion of cryptocurrencies. However, the use of smart contracts can have other potential applications aside from benefits they can pose to the area of cryptocurrencies


texts:
I have a set of images. The length is variable. It could be anything up to about 30 images. Each image can have up to 10 tags. Images may share some, all or none of their tags. I need to select a random 5 from this set of images. This selection should follow the following rules in order of high priority to low:

Two images with the exact same tag(s) MUST NOT appear next to each other unless no other option is available.
Which two images appear next to each other should be decided by a weight system that favours images that share less tags or none at all. The more different tags two images have, the more likely they should be to appear side by side and vice versa.
Rule 2 also applies to the entire set of 5, but to a lesser degree. It means we prefer the selected 5 to share as few tags with one another as possible, but this should not take priority over rule 1 and 2.
(Optional) When selected images share tags, the more tags they share, the further apart they should be from each other.
(Optional) As a bonus, it would be nice not to sacrifice randomness because of rule 3 and 4, but this is more of a nice-to-have and is not necessary.

I'm looking for an algorithm that can help me solve the above problem. This is part of a real-world application UI and as a result, it'd be best if it doesn't take more than a second to calculate the set of 5. Anything longer than a second is bad. Even a second is too long.

If anyone has a solution that takes up to a minute or so, I might be able to do some pre-processing on the data so I am still open to it.


texts: Loopless NFA equivalent in strength to NFA

texts:
For every nondeterministic finite state automata (NFA) that has self-loop(s), there exists an equivalent NFA that does not have any self-loop.

How do I prove this?


texts: Non-discrete edit distance for range maps

texts:
I'm looking for some kind of edit distance measure between what may be called 'non-discrete symbols sequences'.

By a discrete symbol sequence I would mean something like a string, where each symbol has a fixed length and there are fixed positions for symbols. A well-known edit distance measure between strings is the Levenshtein distance.

levenshtein('abc', 'abde') = 2

However the data that I want to compare is not strings. It's what I think is called a 'range map', for example:

{
    (0, 1.4): 'a',
    (1.4, 3.2): 'b',
    (3.2, 5): 'c'
}

So there is still a linear sequence of symbols ('a', 'b' and 'c') but the symbols are different 'sizes' (1.4, 1.8 and 1.8) and the boundaries are not in fixed positions (0, 1.4, 3.2, 5).

Now given two of these range maps I would like to get a distance measure similar to Levenshtein for strings. There are a lot of intuitions that I have about what certain differences between two range maps would mean for the distance between them, but I wonder if there is an existing measure. I thought about how to adapt Levenshtein to this data but didn't get very far.

I did come up with one slow, inaccurate possibility: cut the range up into tiny intervals, get the values of the range maps for each interval, and then use those discrete sequences to do Levenshtein. This works but it requires choosing the interval size, and the algorithm gets slower with higher accuracy (smaller intervals).

However I do believe that, taking inspiration from Python's difflib, 2.0 * M / T converges for the above algorithm as the interval size is decreased. Is there a faster algorithm (no tiny intervals) that computes the number that this algorithm converges on?


texts: Counting number of sequences summing to target

texts:
This is a problem that I have been struggling to understand in a theoretical computer science book I've been reading:

We call a sequence of $n$ integers $x_1, \dots, x_n$ valid if each $x_i$ is in $\{1, \dots, m\}$.
How would you design a dynamic programming-based algorithm that takes in $n$, $m$ and “target” $T$ as input and outputs the number of distinct valid sequences such that $x_1 + \dots + x_n = T$? Your
algorithm should run in time $O(m^2n^2)$. How would you design an algorithm with the same constraints, but with an $O(mn^2)$ run time?

I'm not sure how to go about designing an algorithm with these constraints. From what I have gathered, I would let $f(s, i)$ denotes the number of length-$i$ valid sequences with sum equal to $s$ for the second part of the problem, but I'm not sure where to start. Any advice would be appreciated.


texts: Can a Turing Machine decide if an NFA accepts a string of prime length?

texts:
I want to know if the following problem is decidable:

Instance: An NFA A with n states

Question: Does there exist some prime number p such that A accepts some string of length p.

My belief is that this problem is undecidable, but I can't prove it. The decider can easily have an algorithm to figure out if a particular number is prime, but I don't see how it would be able to analyze the NFA in enough detail to know exactly what lengths it can produce. It could start testing strings with the NFA, but for an infinite language, it may never halt (and thus not be a decider).

The NFA can easily be changed to a DFA or regular expression if the solution needs it, of course.

This question is something I've been pondering as a self-made prep question for a final I have coming up in 2 weeks.


texts:
How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ?

Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I cannot understand What kind of function lays there?


texts: Is it a tautology or not? According to my truth table its not

texts:
If $\bigr((q\leftrightarrow p)\leftrightarrow s\bigl)$ is a tautology and $p\rightarrow s$ is contingent, does it follow that $q\rightarrow s$ is contingent?

Since I can't show $\bigr((q\leftrightarrow p)\leftrightarrow s\bigl)$ is a tautology, I'm unsure how to proceed.


texts: Reduction from 3-partition to ABC-partition

texts:
The ABC-partition problem is a variant of 3-partition in which, instead of a single set $S$ with $3 m$ positive integers, there are three sets $A, B, C$ with $m$ positive integers in each. The goal is to construct $m$ triplets with the same sum, each of which contains exactly one integer from $A, B$ and $C$.
Here is a reduction from ABC-partition to 3-partition. Given the sets $A, B, C$ and the target sum $T$, construct a set $S$ as the union of the following sets:

$\{1000a+100 | a\in A\}$
$\{1000b+10 | b \in B\}$
$\{1000c+1  | c\in C\}$

and the target sum $1000T + 111$. Obviously, every solution of $A,B,C$ is a solution of $S$. Conversely, in every solution of $S$, there must be exactly one element that ends with 100, one that ends with 10, and one that ends with 1; therefore, it corresponds to a solution of $A,B,C$.
Question: what is a reduction from 3-partition to ABC-partition?


texts: Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1

texts:
Problem statement: Solve $T(n)$ for $T(n)=2T(n-1)+n$, $n > 1$, and  $T(1)=1$.

My attempt: I tried back substituting but I am unable to find a general pattern:
$$\begin{align*}
T(n) &=2^2 T(n-2)+3n-2 \\
&=2^3 T(n-3)+7n-10 \\
&=2^4 T(n-4)+15n-34 \\
&=\cdots
\end{align*}$$


texts:
Given a set of 2d trajectories/paths, where a trajectory is a list of [x,y,time] coordinates, and a new trajectory, how can I recognize which one in the set is most similar to it? The lists may not be of the same length, the time differences not the same.

I've tried using perceptual image hashes of the resulting lines, but this approach seems unreliable.

The measure of similarity should be scale and translation, but not rotation invariant.

I'm trying to recognize 2d gestures that are input with a mouse or touchpad in order to execute commands[0]. For this application, the velocity/acceleration of the movement will not matter.

I found this library that contains a few algorithms: https://github.com/bguillouet/traj-dist

[0] https://github.com/void4/termagic


texts: Could a Van Emde Boas tree be used for storing matrices?

texts:
I'm aware that typical techniques to store matrices in sparse form are compressed formats or maps where the key is the pair of indices and value the value of the entry in a matrix.

I was wondering if vEB trees could be used to such purpose as well. At the end of the day the dynamic set to be stored would be the pairs $(i,j)$ in lexicographic order. If $MN$ is the size of the matrix a vEB tree would allow the access to a specific entry in time $O(log(log(MN))$ which isn't bad, though the space requirement doesn't change, but maybe with some improvements something interesting could come out.

Is there some research in this direction? I quickly looked up on google doesn't seem anything specific comes out.

Thank you


texts: How to design a LL(1) grammar for basic regular expression?

texts:
I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.（\| is the escape character, since | is a special character in grammar's pattern).

E -> E \| T | T
T -> TF | F
F -> P* | P
P -> (E) | i

To remove the left recursive, import new Variable

E -> TE'
E' -> \| TE' | ε
T -> FT'
T' -> FT' | ε
F -> P* | P
P -> (E) | i

now, for pattern F -> P* | P， import P'

P' -> * | ε
F -> PP'

However, the pattern T' -> FT' | ε has problem. Consider case (a|b):

E => TE'
  => FT' E'
  => PT' E'
  => (E)T' E'
  => (TE')T'E'
  => (FT'E')T'E'
  => (PT'E')T'E'
  => (iT'E')T'E'
  => (iFT'E')T'E'

Here, our human know that we should substitute the Variable T' with T' -> ε, but program will just call T' -> FT', which is wrong.

So, what's wrong with this grammar? And how should i rewrite it to make it suitable for the recursive descendent method.

More

Now i've learn that there is a kind of grammar called "operator precedence grammar", its evaluation is similar to arithmetic expression's. It require that the pattern of the grammar cannot have the form of S -> ...AB...(A and B are non-terminal). Does it means that i just cannot directly use this method to parse the regular expression?
https://stackoverflow.com/questions/53211961/how-to-deal-with-the-implicit-cat-operator-while-building-a-syntax-tree-for-re


texts: Question about idempotent and Dominance Laws in Boolean Algebra

texts:
If I have the following statements:

For Idempotent:

Since X * X = X, would that imply that ~X * ~X = ~X

For Dominance:

Since X + 1 = 1 would that imply that ~X + 1 = 1


texts: Decidability of the language of all deterministic LBA where all states are reachable

texts:
I have a exam task with 3 parts. (b) is no problem. I got a solution for (a) but the way (c) is asked makes me wonder if I even understood (a)

(a) L := { < A > | A is a DFSA, where all states are reachable }. Is L decidable? Why or why not?

(b) M is a DLBA and k is the input length. There exists a function g(M,k) which returns the maximum number of steps a DLBA can possibly do, which halts on an input the size of k. Why?

(c) L' := { < M > | M is a DLBA, where all states are reachable }. Show that L' is semi-decidable. Use g(M,k) from (b)

My solution:

(b) Limited amount of configurations. I get that.

For example how I understand (a):
L is a language and every word of L is the encoding of a FSA. But only FSAs where every state can somehow be reached from the starting state or is the starting state.

So is it decidable?

My answer: Yes, for any word w you could check if its a valid FSA-encoding, if not: reject, if it is: Construct a FSA from this encoding and check if you can reach all states like this:

Mark the starting state;
Repeat until no new marked states:
   Mark all states you can reach from the marked states.
Check if all states are marked.
Reject or Accept

My Question:

Is (c) just semi-decidable and how do I use g(M,k) to show this?
Because I would think I could solve (c) exactly like (a) and show that it is decidable (which would mean it is also semi-decidable)

Edit: Hi, if you give me a downvote I would appreciate a comment on how to improve my questioning. I know it is a long post but I just try to lay out how I understand questions like this to be solved so you can correct me if I have key misunderstandings. I now reduced the amount of questions I asked and the length of my post.


texts:
How am I supposed to read the P=?NP relativization proof? I am reading the classical paper Relativization of the P=?NP problem by Baker, Gill and Solovay, in particular the proof that there exist an oracle $B$ such that $\mathsf{P}^B \neq \mathsf{NP}^B$ on page 436. I have some questions and your help will be appreciated.

The procedure does not seem to be an oracle but a deterministic algorithm.
Is this construction a counterexample to P = NP?
What does this mean "Run query machine $P_i$ with oracle $B_i$ on input $x_i = 0^n$?" Does it mean that $P_i$ asks

if $B_i$ accepts $0^n$
if $B_i$ accepts any string of length $n$
ONE BY ONE if $B_i$ accepts a string of length $n$ from the canonical enumeration?

I assume that the set $B$ or $B_i$ is initially empty. Does it mean that the FIRST string of length $n$ from the canonical enumeration will always be added?


texts: Complexity of minimizing the maximum inter-cluster distance?

texts:
Given $n$ non overlapping points $x_i \in \mathbb{Q}$, and an integer $k\geq 2$, what is known about the complexity of finding $k$ means ($a_1, a_2, ..., a_k$) that minimize the maximum inter cluster distance:
$$\min_{a_1, ..., a_k \in \mathbb{Q}}\max_{1\leq j \leq k} \sum_{x_i \in C_j}||x_i-a_j||^2$$

Do we have any polynomial time algorithms for general $k$?, specific $k$ (say $k=2$)? Does the problem have a special name?


texts: Why is $coNP\subseteq NP/O(1)$ and $coNP\subseteq NP/O(\log n)$ not same as $coNP=NP$?

texts: If $NP\subseteq P/log\implies P=NP$ why does $coNP\subseteq NP/O(1)$ or $coNP\subseteq NP/O(\log n)$ not implies $coNP=NP$?


texts: How to make efficient path minimum queries in a tree?

texts:
Given a tree in which each node has a given value, I want to process "Path Minimum Queries": given two nodes, what is the minimal value of any node on the shortest path between them?
My original idea was to solve Least Common Ancestor Queries on any two nodes (using an Eulerian Tour Tree or the Binary Lifting Method), then to split any path into one or two vertical paths that pass through the LCA. After this, we could process the path minimum query on the vertical paths.
However, processing the path minimum query on a vertical path proved to be pretty hard: in path sum queries (finding the sum of all node values on a path), if we know the sum of all nodes from an ancestor to the parent of node A, and also the sum of all nodes from that ancestor to node B, then the sum of all nodes from node A to node B is just equal to the second value minus the first one. In Range minimum Queries, however, this does not work.
Is there any efficient way to solve this problem? Am I missing something in my current approach?


texts: Runtime of good suffix table creation in Boyer-Moore algorithm

texts:
According to Wikipedia, both bad character table and good suffix table can be created in $O(n)$ time, where $n$ is the length of the pattern. It is pretty obvious how bad character table can be computed in linear time, but I don't understand how good suffix table can be computed in linear time. I thought about it a lot, and could not come up with an $O(n)$ algorithm to generate that table. I also looked at the Java implementation provided in Wikipedia, but I think it runs in $O(n^2)$ time. For example, look at the following two lines taken from makeOffsetTable method.

for (int i = needle.length - 1; i >= 0; --i) {
    if (isPrefix(needle, i + 1)) {

Outer for loop iterates needle.length (i.e. $n$) times, and within the loop body isPrefix is called, which contains a loop that starts with the following header.

for (int i = p, j = 0; i < needle.length; ++i, ++j) {

Just to make it easier on the eyes, here is the two loops shown together.

for (int i = needle.length - 1; i >= 0; --i) {
    for (int i2 = i + 1, j = 0; i2 < needle.length; ++i2, ++j) {

I can get rid of j of the inner loop to further simplify it.

for (int i = needle.length - 1; i >= 0; --i) {
    for (int i2 = i + 1; i2 < needle.length; ++i2) {

What I see here is that with each successive iteration of the outer loop, inner loop will have one additional iteration. So, the number of iterations for the inner loop will be $0, 1, 2, 3, 4, ..., (n-1)$ which adds up to $(n-1)n/2$, which is $O(n^2)$, which is not linear.

So, the question is, does it really take more than linear time to compute the good suffix table, or am I making a mistake with runtime calculation?


texts: Regular Expressions to accept strings where every two successive 0s are followed by a 1

texts:
How do I define a Regular Expression for the language L = {w|every two successive 0s are followed by a 1} ?

I don't have any idea on how to even approach this problem, primarily because it says "every two 0s".


texts: Shortest paths between given red vertices and arbitrary blue vertices

texts: Given an undirected weighted graph, where each vertex has one of two colors - red or blue. I have to answer queries to find the shortest path between a given red vertex and any blue vertex in the graph. I have tried using Dijkstra algorithm with source the given red vertex, then finding the shortest path among all shortest paths, but I have to answer many queries for the red vertices and this method proved inefficient. Are there any more efficient algorithms for this problem ?


texts:
Speedback is the merging of speed-dating with feedback: a 2 min. 1-on-1 talk with all members of a group of people.

I'm in a team and I want to plan the ideal speedback setup: all team members have to give feedback to eachother.
I want to group people in a way that maximizes the concurrency of simultaneous pairs so we reduce the total time of the sessions.

Consider the input:
"alexandre", "sergiu", "joana", "tiago", "susana", "david"

combinations(6,2) = 15 possible pairs

1st session:

"alexandre" with "sergiu"
"joana" with "tiago"
"susana" with "david"

2nd session:

"alexandre" with "joana"
"sergiu" with "tiago"
"joana" with "david"

3rd session:

...

you get the ideia.. until everyone "dates" everyone.

I need all the possible pairs to be matched in the end.

Do you how to get this output? (or can you hint about the solution)?


texts: Descriptors in key-features during mapping

texts:
This question is related to this question.

In SLAM-type applications the feature detectors like SIFT are used for finding keypoints in the images to be matched. The candidate keypoints are matched by aligning warped patches around these points (as far as I can understand).
What is the role of the descriptor vector in this process. Is it used for selecting the best candidate in the neighborhood?


texts: Closure properties of the class of inherently ambiguous CFLs

texts: is set of inherently ambiguous context free languages close under operations such that union, intersection, kleene star, concatenation, reverse, complementation and etc. how many of theme are answered?


texts: Struggling to understand the symbolism around the big oh formal definition

texts:
I'm struggling to understand what exactly T(n), and f(n) is in the above text:

  When we compute the time complexity T(n) of an algorithm we rarely get
  an exact result, just an estimate. That’s fine, in computer science we
  are typically only interested in how fast T(n) is growing as a
  function of the input size n.

  For example, if an algorithm increments each number in a list of
  length n, we might say: “This algorithm runs in O(n) time and performs
  O(1) work for each element”.

  Here is the formal mathematical definition of Big O:

  Let T(n) and f(n) be two positive functions. We write T(n) ∊ O(f(n)),
  and say that T(n) has order of f(n), if there are positive constants M
  and n₀ such that T(n) ≤ M·f(n) for all n ≥ n₀.

  image

  This graph shows a situation where all of the conditions in the
  definition are met.

I'm taking Tim Coughgarden course and reading his books. I'm still in the beginning and I can understand the explanations, but sometimes I struggle to understand the mathematical meaning of things... there are some implicitly about what is T(n) or f(n) (in this case) that is not explained at all.


texts: Polynomial variable of inapproximability after reduction

texts:
I proved the inapproximability of a problem that, given a multigraph $G = (V, E)$ and a set of vertices $U \subseteq V$ tries to maximize a score $f(U)$ whose value depends on the edges of the graph, so it takes values in $\{0, \dots, m\}$, $m$ being the number of edges in the graph.
As the result was obtained by (exactly) reducing from the Maximum Independent Set which is known for being inapproximable within $n^{1- \epsilon}$, I am not sure how this is translated to my problem: Is it inapproximable within $n^{1- \epsilon}$ or within $m^{1- \epsilon}$ (as, in a certain sense, it counts the number of edges)?
(In the proof we build a multigraph in which each edge contributing to the score is associated with an independent vertex in the original graph and vice versa)


texts:
I know that some operations are definitely constant time, such as accessing an item in a list, however there are other operations that are assumed constant time sometimes, but non-constant other times, such as multiplication.

So if we were to deal with very, very large operations, which operations would be truly constant time, or at least polynomial for exponentially large data


texts: Proof: Sum of weights of paths in a network

texts:
I was given problem 6.7 out of the book "Networks: An Introduction" as a question. The problem is defined as follows:

Consider the set of all paths from node $s$ to node $t$ on an undirected network with adjacency matrix A. Let us give each path a weight equal to $\alpha^r$, where $r$ is the length of the path.
a) Show that the sum of the weights of all the paths from $s$ to $t$ is given by $Z_{st}$ which is the $st$ element of the matrix $Z = (I - \alpha A)^ {-1}$, where $I$ is the identity matrix
b) What condition must $\alpha$ satisfy for the sum to converge?

Where do I even start on this problem?
Since the graph is undirected, I know that A must be a symmetric matrix. Other than that I don't quite know what more information there is to go on.


texts: Playing video games to solve SAT instances

texts:
This paper shows that computer games, such as Super Mario, are NP-hard, by reduction from SAT. It may be possible to use this reduction to help solve hard instances of SAT: use the reduction to construct a Super Mario level and let experienced gamers play it. In the worst case, it might take them exponentially long; but, in some cases, there may be heuristics that experienced gamers may be able to notice, and this may lead them to quick solutions.
The main problem with this scheme is that it is one-sided: if a satisfying assignment exists, then the gamers may find it; but if no such assignment exists, then they will not find any proof for it.
So my question is: is there a way to construct a video game for solving SAT instances, such that if the instance has a solution - a gamer will eventually find it (after possibly exponentially long time), and if the instance has no solution - a gamer will eventually find an evidence for it? Can such a game be useful for solving hard SAT instances?


texts: Is there a "sorting" algorithm which returns a random permutation when using a coin-flip comparator?

texts:
Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft's prominent failure to write a uniform permutation generator, my question is thus:

Is there a comparison based sorting algorithm which will, depending on our implementation of the comparator:

return the elements in sorted order when using a true comparator (that is, the comparison does what we expect in a standard sorting algorithm)
return a uniformly random permutation of the elements when the comparator is replaced by a fair coin flip (that is, return x < y = true with probability 1/2, regardless of the value of x and y)

The code for the sorting algorithm must be the same. It is only the code inside the comparison "black box" which is allowed to change.


texts: Refuting $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ for homomorphisms

texts:
I want to prove that $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ is not always true.

If $L_1 = (ab)^*$ and $L_2 = (ba)^*$ with mapping $H(a) = 1$ and $H(b) = 1$, $H(\epsilon) = 2$, then $H(L_1 \cap L_2) = 2$ while $H(L_1) \cap H(L_2) = (11)^*$.

Is the above example correct to prove the above statement? Is it allowed to map two symbols to one same symbol?


texts: Proof that $A_{DFA}$ is decidable in Sipser

texts:
It seems like the proof that $A_{DFA}$ is decidable in Sipser (2nd ed.) assumes the computation will halt... and hence only really proves that $A_{DFA}$ is recognizable.
The language $A_{DFA}$ is defined by $A_{DFA} = \{\langle B, w \rangle \mid B \text{ is a } \mathsf{DFA} \text{ that accepts input string } w \}$.
Here is the passage (I've bolded the most relevant sentence):

First, let's examine the input $\langle B, w \rangle$. It is a representation of a $\mathsf{DFA}$ $B$ together with a string $w$. One reasonable representation of $B$ is simply a list of its five components, $Q$, $\Sigma$, $\delta$, $q_0$, and $F$. When $M$ receives its input, $M$ first determines whether it properly represents a $\mathsf{DFA}$ $B$ and a string $w$. If not, $M$ rejects.
Then $M$ carries out the simulation directly. It keeps track of $B$'s current state and $B$'s current position in the input $w$ by writing this information down on its tape. Initially, $B$'s current state is $q_0$ and $B$'s current input position is the leftmost symbol of $w$. The states and position are updated according to the specified transition function $\delta$. When $M$ finishes processing the last symbol of $w$, $M$ accepts the input if $B$ is in an accepting state; $M$ rejects the input if $B$ is in a nonaccepting state.

Am I missing something or is this proof bogus?
EDIT: Never mind, I think I see my problem. A Turing machine may move back and forth, never halting, but an automaton like $B$ given finite input $w$ finishes after $|w|$ steps, correct? So $M$ does halt. Feel free to post an answer explaining this yourself - I don't want anyone to miss out on a chance to answer by me deleting the question. If no one responds within a day, I'll post an answer myself.


texts: Lately graph theory has come into everyday practice with graph databases. So I wonder if any object can be written as a graph? I don't have the formal definition of an object, but say it is a C struct or a Java Object, isn't it so that we can express objects as graphs and that it is a more convenient and advantageous representation than an algebraic relational representation (rdbms)?


texts:
I have one formula that I do not understand why it is CNF and one that is not CNF, namely.

p && !q (NOT NCF)

and

!!p(CNF).

According to the exercise where I found these examples, 1 is not CNF and 2 is CNF.
How can the first formula not be CNF, when for example p && q is CNF.
If for example !!p is part of a formula we will translate it to p, how can we say that it is CNF?


texts: How can I explain lossless compression to a misguided audio engineer?

texts:
I have recently been involved in a discussion with someone who doesn't accept that lossless compression is possible, even in principle. This person considers himself to be technically literate, and an expert in his field of audio engineering.
I and several others have patiently tried to explain how lossless compression is possible, using simple examples such as run-length encoding and delta encoding, but he refuses to believe that it's possible for a lossless audio codec such as FLAC, for example, to exactly reproduce the input bitstream from the raw PCM data.
His response is always along the lines of:

it's getting smaller, so it must be losing data
"lossless" is just a buzzword used by software companies to sell their software, it doesn't actually mean lossless

Are there any other examples I can use to demonstrate conclusively that lossless compression is actually possible?


texts: The order of growth analysis for simple loop

texts:
What would the order of growth for this loop be:

int sum = 0;
for (int n = N; n > 0; n /= 2)
    for(int i = 0; i < n; i++)
        sum++;

The first loop seems to run for $\log N + 1$ times and the second loop runs $n$ times.

So is the correct answer $O(n \log n)$?


texts: Can threads use resources from other processes?

texts:
This is how I see threads. Please do correct me if I'm wrong:

A thread is a part of a process that runs a sequence of program code. There can be many threads within a process that run different parts of a program (one thread manages keyboard input, one manages auto-saving, one manages printing etc.).
The process allocates resources while the thread(s) are responsible for getting tasks executed by being scheduled for CPU time.

My question is:

  Are threads always bound to their own process or can they exchange
  resources with other threads outside of their process?


texts: Regular expression for the language where every a is surrounded by b's

texts: I had a question on an assignment where we were supposed to write a regular expression for a language where every $a$ in $w$ is immediately preceded and followed by a $b$. My answer was $\epsilon + (b + bab)^*$. The teacher pointed out that my answer makes an $a$ surrounded by at least two $b$s, which isn't correct. I can't for the life of me figure out how to fix it to make it correct. Can anyone help?


texts: how to calculate $2^{5000}$ mod 10 without calculator in fast way?

texts:
How is it possible to calculate $2^{5000}$ mod 10 without using a calculator in a fast way?
The result with calculator was 6.


texts:
I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n | $ $n \geq 0\}$.

Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and $d$'s respectively won't work because that would mean number of $a$'s $= $number of $c$'s and number of $b$'s$ =$ number of $d$'s. I can't come up with an accurate solution.


texts: Does it make sense to examine the dual of a feasbility problem?

texts: Consider a standard feasibility problem. The goal is to examine the state of feasible solutions for $Ax=b$ to find an $x$ that satisfies some property. Does the dual of this problem tell us anything about the solution? Since there is no objective function that we're examining I think the dual looks like $A^Tx \leq 0$. Is this right?


texts: Explanation of the knowledge representation hypothesis (Brian Smith)

texts:
In 1982 Brian Smith proposed his Knowledge Representation Hypothesis:

  Any mechanically embodied intelligent process will be comprised of
  structural ingredients that

  we as external observers naturally take to represent a propositional account of the knowledge that the overall process
  exhibits, and
  independent of such external semantic attribution, play a formal but causal and essential role in engendering the behavior that
  manifests that knowledge.

Can someone simplify this statement or add some explanations to it?

In particular I don't understand what is meant by "propositional account" and "formal but causal role".

Thanks!


texts: If X reduces to a problem in NP, is X in NP?

texts:
Let $X$ and $Y$ be problems, and let $X \le_p Y$.  Is it true that
\begin{equation}
Y \in NP \rightarrow X \in NP\ ?
\end{equation}

I do mean $NP$ here, not $NP$-complete or $NP$-hard.

The solution is simple if the reduction from $X$ to $Y$ transforms an instance of $X$ to an instance of $Y$; to verify that a solution to $X$ is correct, we could transform it to an instance of $Y$ and then verify that the transformed instance is a solution to $Y$.

All we know from $X \le_p Y$, though, is that you can solve $X$ with a polynomial number of solutions to $Y$; we're not guaranteed a simple one-to-one transformation.

I suspect that
\begin{equation}
Y \in NP \rightarrow X \in NP
\end{equation}
is true for all $X,Y$ such that $X \le_p Y$, but I would like confirmation, and I would like to know how to prove it.


texts: Relation between $\sqrt{x^2+y^2}$ and $|x|+|y|$

texts: I have a problem in which I was given $n$ points and an integer $k$, and I need to find the $k$ points that are the closest to origin. My approach is to find the distances from origin of all points and sort them. Instead of using distances $\sqrt{x^2+y^2}$, can I use $|x|+|y|$ as my key? Also, I would like to find out the complexity for both approaches.


texts: Using naturality to prove $f: \forall\alpha. \alpha\times\alpha\to\alpha$ must be a projection

texts:
Suppose we have a System F term $f : \forall \alpha. \alpha\times\alpha\to\alpha$, interpreted in a parametric model which is a bicartesian closed category.

I was wondering if in such context it is possible to prove that (in the model) $f$ must be a projection (either $\pi_1$ or $\pi_2$), exploiting the naturality of $f$ and little else.

So far, I got the following sketch.

By naturality, for all $g: A\to B$, we have
$$ (g \times g); f_B = f_A ; g$$
In particular, we can take $A = 2 = 1+1$ (the coproduct of the final object with itself), and take ${\sf tt},{\sf ff}: 1\to 2$ to be the inclusions.

We get that, for all $g: 1\to B$, we have
$$ \langle {\sf tt}, {\sf ff} \rangle ; (g \times g); f_B =
   \langle {\sf tt}, {\sf ff} \rangle ; f_2 ; g$$
Now, we have a morphism
$$ h = \langle {\sf tt}, {\sf ff} \rangle ; f_2 : 1 \to 2 $$
and we assume that (*) in the model $h$ must be one of $\sf tt,ff$ -- i.e., that no other morphisms exist.

W.l.o.g., assume $h=\sf tt$ (the other case being symmetrical). Then, we have
$$ \langle {\sf tt};g , {\sf ff};g \rangle ; f_B =
   {\sf tt} ; g$$
and, taking $g = [m,n]$ for some $m,n : 1\to B$
$$ \langle m , n \rangle ; f_B = m$$
which is "close" to stating that $f_B$ is the first projection.

Questions:

1) Can we weaken the assumption ($*$) in some way?
Or, can we strengthen ($*$) by requiring some standard property that "usually" holds in known models?
I mean, I could work in a specific model (e.g. PERs) where we only have two inclusions $1\to 2$, but maybe there's some more general standard-ish assumption which can guarantee that?

2) Can we prove that $f_B$ is really a projection? Proving that it is such seems to require a sort of extensionality principle like

$$ (\forall x:1\to A. x;f=x;g) \implies f=g $$

but this, I guess, might not hold in general.

A final note: I'm aware that one can prove $f$ to be $\beta\eta$ equivalent to a projection through syntactic means (Krivine does so, if I remember correctly), but I am really interested in the consequences of naturality.


texts: Lower bounds: queues that return their min elements in $O(1)$ time

texts:
First, consider this simple problem --- design a data structure of comparable elements that behaves just like a stack (in particular, push(), pop() and top() take constant time), but can also return its min value in $O(1)$ time, without removing it from the stack. This is easy by maintaining a second stack of min values.

Now, consider the same problem, where the stack is replaced by a queue. This seems impossible because one would need to keep track of $\Theta(n^2)$ values (min values between elements $i$ and $j$ in the queue). True or false ?

Update: $O(1)$ amortized time is quite straightforward as explained in one of the answers (using two min-stacks). A colleague pointed out to me that one can de-amortize such data structures by performing maintenance operations proactively. This is a little tricky, but seems to work.


texts: Probability of finding the maximum element in a heap

texts:
You are given a minimum heap, with probability going to left is 50% and going to right is 50%. What is the probability that You will land up on a maximum element in the heap? For this scenario since going to right and left have equal probabilities we can state the answer to be
$(1/2)^{O(\log n)}$ .
As at each step we have two possible decisions and we can choose the correct path with a probability of 1/2. We have to make this decision $\log n$ number of times (height of the heap).
It doesn't matter whether we take a left or a right from the present node as both are equally probable.
But if the probabilities are not equal for left and right is this model still valid?

The Question

How can we model the above situation where the probability of going to right is $x$ and to the left is $1-x$, where  $0<x<1 $

Is the concept of random walks on graphs involved?

Assumptions :
There exists a unique maximum element which by the definition of heaps exists at some leaf node.


texts: Another version of the 3-coloring decision problem?

texts:
Given a graph $G$, is there a 3-coloring with colors $c1$, $c2$ and $c3$ such that at most $k$ nodes are given the color $c1$ and that no two adjacent nodes are given the same color?
Is there a decently fast algorithm to solve this? My only solution is to go through every subsets of size $1$ to $k$ and remove those nodes and check if the graph is bipartite. I am also not sure if this runs in polynomial time.


texts: What is the meaning of idiosyncratic when refering to multiprocess abstractions?

texts:
I am currently reading this paper on library operating systems, more specific on Graphene. I stumbled over the following sentence:

"Because multiprocess abstractions, such as signals or System V IPC, tend to be idiosyncratic, an essential problem is identifying a minimal, host-independent substrate upon which to implement OS-specific abstractions." (Page 3, design options paragraph)

But I don't understand what is meant by idiosyncratic multiprocess abstractions? What is the meaning of idiosyncratic in the context of multiprocess abstractions?


texts: Why is the language of even-length non-palindromes context-free?

texts:
We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$
is a context-free language.

Can anyone help me produce a PDA or give me any hint how I can quickly understand why this is context-free?


texts: Is there any toolbox for Markov Random Field Structure Learning?

texts: I need a toolbox or software that takes a dataset as input, detect independencies among its random variables and produces the relative Markov Random Field graphical structure from that. Can anyone suggest a proper toolbox for doing this task automatically?


texts: Proving the algorithm that orders an array according to the specified positions

texts:
I have the following task:

  Given an array a holding positions and array b holding values,
  order the elements in the array b according to the positions in the array a. For the
  input:

a = [3, 0, 1, 2];
b = ['a', 'b', 'c', 'd'];

  the output should be

[ 'b', 'c', 'd', 'a' ]

I have written a simple algorithm which simply an item into the specified position by swapping:

// a.lenght -1 since the last element will end up in the correct vacant position
for (let i = 0; i < a.length - 1; i++) {
    const position = a[i];
    swap(b, i, position);
}

Although I've tested it and it seems to produce correct results, I can't figure how to prove it works correctly. Can anyone please help with reasoning?


texts: How can union-find algorithm be used with "real" data

texts:
In the beginning of the Princeton algorithms course the Dynamic connectivity problem is presented (quick-find, quick-union). Here is how it's described:

  The input is a sequence of pairs of integers, where each integer
  represents an object of some type and we are to interpret the pair p q
  as meaning “p is connected to q.” We assume that “is connected to” is
  an equivalence relation, which means that it is

  Reflexive : p is
  connected to p.
  Symmetric : If p is connected to q, then q is
  connected to p.
  Transitive : If p is connected to q and q is
  connected to r, then p is connected to r.

And it has one simple implementation called quick-find:

  One approach is to maintain the invariant that p and q are connected
  if and only if id[p] is equal to id[q]. In other words, all sites in a
  component must have the same value in id[].This method is called
  quick-find because find(p) just returns id[p], which immediately
  implies that connected(p, q) reduces to just the test id[p] == id[q]
  and returns true if and only if p and q are in the same component...To
  combine the two components into one, we have to make all of the id[]
  entries corresponding to both sets of sites the same value, as shown
  in the example at right.

My question is how can this be used for real objects? It works for integers, but what if I need to know whether the object A is connected to the object B, not if 3 is connected to 5? One solution I can think of is to have an array of objects where each object's index in the array corresponds to the index of the array used for connectivity. For example:

   1   2   3   4   5
[ { } { } {A} { } {B} ]   <---- real data

   1   2   3   4   5
[  1   2   3   4   3 ]    <---- connections (3 and 5 have the same group id 3)

Is that how it's applied?


texts: How can we get a Las Vegas algorithm from a Monte Carlo one?

texts:
I am trying to solve some exercises on random algorithms from this book, randomized algorithms. This is not a homework. I am only trying to improve my skills.

Here is the exercise:

Exercise 1.3: Consider a Monte Carlo algorithm $A$ for a problem $\Pi$ whose expected running time $T(n)$ on any instance of size $n$ and that produces a correct solution with probability $\gamma(n)$. Suppose further that given a solution to $\Pi$, we can verify its correctness in time $t(n)$. Show how to obtain a Las Vegas algorithm that always gives a correct answer to $\Pi$ and runs in time at most $(T(n)+t(n))/\gamma(n)$.

My attempt to solve this exercise is:

Algorithm LA
1) for i = 1 to 1/gamma(n) do
2)     solMC = MC(n)
3)     if solMC is correct
4)         return solMC
5)     else
6)         solMC = MC(n)
7)     end
8) end

The idea of my Las Vegas algorithm LV was to re-run the Monte Carlo algorithm, MC in my code, some iterations until the correct answer is given.

I found that $\Pr[MC(n) \text{ is called at iteration } i]=(1-\gamma(n))^i$. So I choose the iterations from 1 to 1/gamma(n). In this case, $\Pr[MC(n) \text{ is called at iteration } i]=(1-\gamma(n))^{1/\gamma(n)}$ which goes either to $0$ or $1/e$ as $\gamma(n)$ goes to either $1$ or to $0$, respectively. I think this does not answer the question.

How would you solve this problem?


texts: Turn MST of G to MST of G with one new edge

texts:
Given $T$, an MST of $G(V,E)$ connected and undirected.
Assume we add an edge $e'$ with weight $w(e')$.
Suggest an algorithm which takes $T$ as input, and outs $T'$ MST of $G'(V,E\cup\{e'\})$.So i thought about adding $e'$ to $T$ and removing the heaviest edge in the cycle that was formed. Can anyone suggest how to go about proving that $T'$ is indeed the MST of $G'$?


texts: how to get rows with more than 1 appearance of a specific column in relational algebra

texts:
I have a table like this:

PostId   |    Body    |    AuthorId
  2             b               F
  2             b               E
  2             b               C
  4             d               A
  4             d               E
  8             h               F

So what I want is to get all the rows that have more that 1 appearance of PostId. Here the result would be 2 and 4 because they appear more than 1 time. I want this in relational algebra.
I have already a relation that works just fine but in this relation I use aggregation methods and I don't really what to use count in my relation. I am wondering if there is a way to this with subtraction or division operators?
What I do for now is π PostId (σ c ≥ 2 ( γ Body; COUNT(PostId)->c R2)) to get the row with more than 1 appearance of PostId.
Thanks in advance for help


texts: Suppose a comparison between elements takes 1ms to execute. If an algorithm is O(logN), for example, deletion in an AVL Tree, and the AVL Tree contains 100 elements. Does that mean that the time to execute the algorithm would be log100 * 1ms? Do I need more information to calculate this or is this enough?


texts:
I'm simulating a procedure that assigns tasks to servers and want to estimate the average waiting time until a task is served (finds a free server).
This procedure runs periodically, thus every task that is rejected in a run can try in the next runs until it finds a free server.
The inter-arrival times of tasks follow an exponential distribution.
Between runs, some tasks may finish.

Is there a way to estimate the average waiting time of tasks?


texts: 2-clause satisfiability associated graph

texts:
A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P:

2-SAT:
Input : A conjunction $\Phi$ of 2-clauses.
Question : Is it satisfisable?

For each set of 2-clause $C$ we associate  $G_C$ defined as

$V_{G_C}$ contains two vertices $x$ and $\neg x$ for each variables in $C$.
$E_{G_C}$ contains an edge $\alpha \rightarrow \beta$ if and only if $\neg \alpha \vee\beta$ or $\beta \vee\neg\alpha$ is in $C$.

This graph should help me show this problem belongs to P. Yet,

Why is $C$ satisfiable if and only if $G_C$ doesn't have any loop?
Why does $G_C$ space is polynomial?
Why is $G_C$ calculation from $C$ is polynomial?


texts: Finding non-trivial NFA that accepts all short strings

texts:
It is well-known that every non-trivial NFA of $k$ states (an NFA that does not accept all strings) rejects a string of length at most $2^k$.

But is this upper bound asymptotically tight ?

I found a rough sub-exponential bound in this strategy.

Let $p_i$ be an $i$-th prime.

On the singleton alphabet, $\Sigma = \{a\}$, the following NFA rejects only

$\{a^n:n>0, p_1\cdots p_k|n\}$. With $p_1+p_2+\cdots+p_k+O(1) = \Theta(k^2\log k)$ states.

Initial state $q$, is an acceptance state and it is branched into $k$ cycles with $\epsilon$ marks.

Every $i$-th cycle has $p_i$ states, and only rejecting state is the state directly linked into initial state $q$. All of its transition are marked by $a$.

It is clear that the complement of accepting language is $\{a^n:n>0, p_1\cdots p_k|n\}$ as given.

But $p_1\cdots p_k=O(e^{\Theta(k\log k)})$. which is sub-exponential with respect to $\Theta(k^2\log k)$.

In this unary and multiplication strategy it seems to be this is optimal because $\text{lcm}\{p_1,p_2,\cdots,p_n\}$ is probably maximized with constraint $p_1+\cdots+p_n=C$ under this prime summation partition.

It seems we should use multi-ary language to improve this bound. Is there any suggestion or results in research?


texts: How realistic of a concern is data corruption?

texts:
Similar to this question, but I wanted to be more specific to my real-world situation.

I am a college software engineer currently working on a project that involves a large number of read cycles. Essentially, I have a bunch of text files of various sizes (i.e. ranging from 10 KB to 1 GB) that get read each time the code runs, and this code is run many, many times in a day for testing purposes as it is tweaked and improved - probably a couple hundred times per day.

Recently I began to wonder if data corruption might become a problem. I've read some literature that suggests a very small chance of read errors/bit flipping each time you read a file, so obviously if you read a lot of times, the practical chance of such a thing occurring gets higher. The files I am reading are pretty important and it would be an issue if they got corrupted or damaged in any way, and so far I've always been careful to back them up each day and take typical precautions in case any corruption occurs. However, I wonder if I could do more, and thus here is my question:

How realistic is a concern about data corruption when reading large numbers of files a large number of times, and in this case, is it even worth worrying about at all? Should I worry about it and/or take more steps to protect any important data files in the future, or is it just not a realistic concern? Would appreciate any help or advice on this matter, as I'm obviously not a very experienced developer yet - hopefully this isn't a silly question!


texts: How do i prove this language is regular?

texts: I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?


texts: What does it mean by "not recursively enumerable"?

texts:
I came across following therem:

  There exists a recursively enumerable language whose complement is not recursively enumerable.

Now, I know following definitions:

  Recognizable language is one which have one-to-one correspondence with the natural number with the additional property that we could specify an algorithm to enumerate the language elements.
  Given the string not in the co-recognizable language, we can give Turing machine which can eventually confirm that the string indeed does not belong to the language.

Then what does the above theorem mean?:

$L'$ does not have one-to-one correspondence with the natural numbers?
We cannot give an algorithm to enumerate the $L'$s elements?
$L'$ is co-recognizable.


texts:
Complexity zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dtime states $DTIME(f(n))$ with $PP$ oracle is not in $P/Poly$ if $f(n)$ is superpolynomial.

We know $SUBEXP=\cap_{\epsilon>0}DTIME(2^{n^\epsilon})\not\subseteq DTIME(p(n))$ for any polynomial $p(n)$.

So do we have $SUBEXP^{PP}\not\subseteq P/Poly$? So can we say either $SUBEXP\not\subseteq P/Poly$ or ${PP}\not\subseteq P/Poly$ holds?

I am trying to understand if $C^O\not\subseteq D$ for classes $C,O,D$ then does it follow either $C\not\subseteq D$ or $O\not\subseteq D$?

In other words if we have two classes $C,O$ with $C\subseteq D$ and $O\subseteq D$ then does it mean $C^O\subseteq D$?


texts: Incremental over-approximation of DAG reachability

texts:
I'm looking for a data structure that stores an approximation of a DAG:

If a node $x$ is reachable from a node $y$ in the DAG, then it is reachable in the approximation.
For a given fairly small root set of nodes that have no incoming edges, it supports getting an over-approximation of nodes reachable from a root and removing those returned nodes.
It supports insertion of roots and of non-roots.

Although I'm more concerned with practical performance (and space usage) than theoretical complexity, I'm just trying to figure out what to search for


texts: Comparison of time-dependent traveling salesman heuristics

texts:
I'm looking into implementing a heuristic for the time-dependent traveling traveling salesman problem (TDTSP) that completes in a certain amount of time.

There are a wide range of possible ways to approach the problem, from dynamic programming to simulated annealing to genetic programming.

How do these approaches compare? Are there any metastudies on this?


texts: Time complexity of finding median in data stream

texts:
I was reading a solution to the problem in the title on leetcode and the article says that the time complexity of the following solution is O(n)

setup a data structure to hold stream value and insert new element in the right place using linear search or binary search
return median

my solution is as follows:
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.arr = []

    def addNum(self, num: int) -> None:
        idx = bisect.bisect_left(self.arr, num)
        self.arr.insert(idx, num)

    def findMedian(self) -> float:
        # self.arr.sort()
        if len(self.arr) % 2 != 0:
            return self.arr[len(self.arr)//2]
        else:
            return (self.arr[len(self.arr)//2 -1] + self.arr[len(self.arr)//2 ])/2

My question is about the time complexity of the push method. the binary search will take O(log n) to find the index. the insert will take O(n). but since the method will be called on the stream, will the complexity be O(n^2) or O(n) ?