Find member of CFL that is Levenshtein-closest to non-member string Is there an (efficient?) algorithm which given a context-free language $L$ (given as a grammar) and a string $x$ with $x \not \in L$ computes a $y$ with $y \in L$ and $\forall y': y' \in L \implies d(x, y) \le d(x, y')$, where $d$ is the Levenshtein distance? (Secondarily, can one enumerate all such $y$?)

The motivation is to give more useful parse error messages: if you give me an almost-valid C program, I would like to tell you "if you delete these parentheses and insert a semicolon here, it'll parse".

A family of related questions:

What happens when you vary the distance function? (Can you think of other candidates? Do non-metric distance functions make sense? Do they change the answer?)
Does the answer change if you restrict $y$ to e.g.

$x$ is a prefix of $y$ (i.e. you can do append-only error-correction)
$y$ is a prefix of $x$ (i.e. you can do pop-last-only error-correction)
all the characters of $x$ occur in $y$ and in the same relative order, but maybe not adjacently (i.e. you can error-correct by inserting anywhere)
[...] $y$ occur in $x$ [...] by deleting anywhere.

Does the answer change if you change the optimization criterion? E.g. "find a $y$ in $L$ which maximizes the length of common_prefix(x, y)", or something else?
Does the answer change for other language classes, e.g. regular?
Does this change if the language is given as $LALR(k)$, $LL(k)$, deterministic or other sub-CF grammar?

Yes.  This can be done, using Levenshtein automata.

Let $S_k = \{y \in \{0,1\}^* : d(x,y) \le k)\}$.  Then the set $S_k$ is regular, and one can construct a finite-state automaton for it, called a Levenshtein automaton.  Now the intersection of a CFL and a regular language is another CFL.  Also, given a CFL, you can efficiently determine whether it is non-empty or not, and if not, you can efficiently find an example of an element of it.

So, we obtain the following simple algorithm:

For $k:= 1,2,3,\dots$, do:

If $L \cap S_k$ is non-empty, find $y \in L \cap S_k$ and output it.

This can be sped up by using binary search to find the smallest $k$ such that $L \cap S_k$ is non-empty.

The same approach can handle your proposed restrictions as well, as those simply amount to intersecting with another regular language.  It also works if $L$ is regular, as any regular language is necessarily context-free.


Prove that the number of edges is at least twice the number of vertices 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.

Hint: if you add up the degrees of all the vertices, you've counted each edge twice.


Is $k$-CLIQUE W[1]-hard for parameter $n - k$? It is well-known that the problem of deciding if a graph contains a clique of size $k$ is W[1]-hard with respect to parameter $k$.

Is it also known to W[1]-hard (or perhaps FPT) in parameter $n - k$, where $n$ is the number of vertices of the graph?

I believe this is FPT.

FInding a $(n - k)$-clique is equivalent to finding an independent set of size $n - k$ on the complement.  This is equivalent to finding a vertex cover of size $k$.  And the latter is FPT.


Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2 If I have $f(n) = 2n + 1$ and I  have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n_0$ such that $f(n)<cn^2, \forall n\ge n_0$, can I do this all in one step by putting in values of $c$ and $n_0$ at once or do I have to put in values of c first and then get n on one side and put in values for $n_0$, the for all $n \ge n_0$ confuses me.

It all depends on the case and how easy it is to search $n_0$ or use $c$, in your case you can show that $2n + 1$ belongs to $n^2$, taking the constant $c = 1$, so that in the proof of BigO, $g (n)$ dominates $f(n)$, what is the same $2n + 1 \le c (n^2)\to  2n + 1 \le n^2$; now you can search a $n_0$.


Knapsack problem with multiple constraints I am unsure if I have even identified the problem correctly, but reading up on knapsack problem seems the closest to what I am trying to solve:

  A cook has $k$ ingredients of $p$ quantities. Given a
  list of $n$ unique recipes, each consisting varying ingredients of varying
  quantities.
  Now, the cook would like to use all ingredients on ONE recipe with minimal leftovers.

What is his solution? And can it be determined in $O(\log n)$ time?

Sample input

500 pounds of flour
300 mg sugar
5 mg of vanilla pods
20 eggs

Database of possible recipes:

Thai Fried Noodles (doesn't contain vanilla or flour, but contains 1 tablespoon of sugar)

Tiramisu (doesn't contain flour and vanilla but contains 3 tablespoons of sugar and 8 eggs)

Anna's Special Tiramiu (doesn't contain flour and vanilla but contains 1 tablespoons of sugar and 8 eggs)

Truffle Tagliatelle (doesn't contain any input ingredients)

EDIT Cost/benefit decision:

Given the sample input, Tiramisu recipe is the most preferred because among the 4 recipes in the database, it contains the most number of input ingredient type (2 of 4 types), and the most number of input ingredient quantity.

Expected result where 1) is the top search result of relevance:
1) Tiramisu
2) Anna's Special Tiramisu
3) Thai Fried Noodles
4) Truffle Tagliatelle

EDIT: I believe my question is a variant of the integer knapsack problem

I assume you can compare two recipes and say which would be preferable to the other. That is, you can define an order between them. Then:

You need to find appropriate recipe only once (or very few times). A simple scan through all the recipes is the only way possible. You need to look at every recipe at least once to be able to see if it is good enough or not. This will give linear complexity.
You have to find appropriate recipes repeatedly for a lot of different baskets. Then, it would make sense to order the recipes in a way that searching would be faster. You might want to sort the recipes first once, in $O(n\log n)$ time. Then, whenever you encounter a basket of ingredients for which you want to find the best recipe, you search the sorted list of ingredients using binary search in $O(\log n)$ time. Thus, the pre-processing phase (sorting) will be slow, but subsequent queries will be fast. This will be beneficial only when you have millions of recipes and want to search the best matched recipe for different baskets hundreds or thousands of times each second.

Admittedly, this is a little vague, but based on the given information, this is the best I can give.


Expected distance between tree nodes I have been given a tree with n nodes and n-1 edges with it's weight.
There are two people A and B.
I have been given a list of nodes of size k.

A will pick a random node x from this list and B will independently pick a random node y from this list.

I have to find expected distance between these two nodes.

My way of solving it was to find the distance between all the (k*(k-1)/2)nodes of the list and dividing it by number of nodes in the list.

for ex:
n=6,k=6 list=[1,2,3,4,5,6]

                    Node--------> 1
                                   \(1)<-----------Weight
                                    \
                                     3
                                (3) / \(2)
                                   /   \
                                  4     2
                             (4) / \ (5)
                                /   \
                               5     6

My answer was coming out to be 87/6 but the actual answer was 29/6.Please help me find whatever i am doing wrong here.

Let $d(i,j)$ denote the distance between $i$ and $j$. Calculation shows that
$$
\sum_{i<j} d(i,j) = 87.
$$
Hence the average distance is
$$
\frac{1}{6^2} \sum_{i,j=1}^6 d(i,j) = \frac{1}{36} \left(\sum_{i<j} d(i,j) + \sum_{i>j} d(i,j) + \sum_{i=j} d(i,j)\right) = \frac{2\cdot 87}{36} = \frac{29}{6}.
$$

A simple way to do the calculation is as follows. Suppose that there are $n$ nodes, and that edge $e$ of weight $w_e$ cuts the tree into parts of size $k_e,n-k_e$. Then the average distance is
$$
\frac{2}{n^2} \sum_e w_e k_e (n-k_e).
$$
For example, in our case we get
$$
\frac{2}{36} (1 \cdot 1 \cdot 5 + 2 \cdot 1 \cdot 5 + 3 \cdot 3 \cdot 3 + 4 \cdot 1 \cdot 5 + 5 \cdot 1 \cdot 5) = \frac{29}{6}.
$$


What complexity class is this ciruit problem? I'm exploring an algorithm that solves k-SAT.  It uses a ton of preprocessing, so I'm thinking that this will be a circuit bounds.

Without knowing the runtime, I speculate on how quickly it will solve k-SAT instances.  It will either solve all instances of k-SAT with probability $p$, or it won't be able to solve any instances.  The runtime is based on $p$.  Essentially, it runs in quasi-polynomial time.

So essentially, what we have is an algorithm that runs in time $2^{O((\log{n})^{c_1})}\cdot O(c_2 + q)$, and solves all instances with probability $\frac{2^q-1}{2^q}$, or it can't solve any instances.  Here, $c_1$ and $c_2$ are constants.

It also requires space polynomial in $q$.

I'm trying to find what complexity class this is, and what is known about it.

SOME NOTES

Just to ensure I've described this correctly, I have an algorithm that either solves all instances, or it can't solve any.  We can say it uses $2^{2^n}$ preprocessing.  Then, it runs in time that is quasi-polynomial multiplied by a function of $q$.

THE QUESTION, AGAIN

What complexity class is this, and what is known about it?

Assuming that the probability is over the randomized preprocessing and $p > 0$, by fixing the correct random choice you get a circuit of size $S = O(2^{\log^{O(1)} n} q^{O(1)})$ for $k$-SAT. The corresponding complexity class is non-uniform circuits of size $S$. If, for example, $q$ is quasipolynomial ($2^{\log^{O(1)}n}$), the you get a non-uniform circuit of quasipolynomial size.

We usually don't care too much about the time required to construct the circuit unless it is very low.


How to analyse the time complexity of an algorithm based on the input values in addition to input size I saw a joke on twitter today that got me thinking on how to perform a time complexity analysis of this algorithm such as you can express that the worst case is dependent on the input value in addition to the input size.
The joke algorithm was this sleep sort algorithm in javascript
const arr = [20, 5, 100, 1, 90, 200, 40, 29]

for(let item of input) {
   setTimeout(() => console.log(item), item)
}

// Console Output
1
5
20
29
40
90
100
200

If we were to describe its Time Complexity and only took into consideration the size of the input, it would be O(n). But from a practical standpoint that wouldn't be really accurate as the Worst Case Time of the implementation is heavily dependent on the actual value of each array element, so is it possible to convey this in a Time Complexity Analysis notation? Is there such a thing as O(max(n) + n), for example?

If we analyze a Time Complexity dependent also on the values of a given input, then as you say a more defined notation would be O(max(n)).
Though, saying O(max(n) + n) in O notation means O(max(n))
So it will still be accurate, since in both outcomes the Complexity is linear in the given input.


Is the set of LL(*) grammars the same as the set of CFG grammars? Is the set of LL(*) grammars the same as the set of context-free grammars?

Static LL(*) grammar analysis is undecidable. In other words, there are some grammars that are LL(*) but we can't figure this out statically. ANTLR v3 fails over to backtracking in this case and therefore can exhibit the PEG A->a/ab problem where ab is dead code in the cases where grammar analysis failed.

In ANTLR v4, I'm introducing adaptive LL(*), which does all grammar analysis at runtime. Because I have an actual input stream in my paw, I can discover every LL(*) decision. I'm also including full LL context (vs Strong LL == SLL context which is weaker). Because I also rewrite all immediate left recursion on-the-fly, ANTLR v4 handles all CFG except for indirect left recursive ones. These are much less common than the immediate left recursive ones like expressions.

e : e '*' e
  | e '+' e
  | INT
  ;

This works fine in v4.  operator precedence is assumed to go from highest to lowest for ambiguous alternatives.


Which computational model is used to analyse the runtime of matrix multiplication algorithms? Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory reference to a model of computation, which is used to measure this complexity. In fact, I have found three possible answers, neither of which seems to me as absolutely satisfactory:

Wikipedia says that the model used here is the Multitape Turing Machine. This does not seem to make much sense to me, since in the analysis of matrix multiplication, scalar multiplication is supposed to have a constant time complexity. This is not the case on Turing Machines.
Some texts describe the complexity only vaguely as the number of arithmetic operations used. However, what exactly are arithmetic operations in this context? I suppose that addition, multiplication, and probably subtraction. But what about division, integer division, remainder, etc.? And what about bitwise operations - how do they fit into this setting?
Finally, I have recently discovered an article, which uses the BSS machine as the model of computation. However, this also seems little bit strange to me, since for, e.g., integer matrices, it does not make much sense to me to disallow operations such as, e.g., integer division.

I would be grateful to anyone, who could help me to sort these things out.

Matrix multiplication algorithms are analyzed in terms of arithmetic complexity. The computation model is straight-line programs with instructions of the form $a \gets b \circ c$, where $\circ \in \{ +,-,\times,\div \}$, $a$ is a variable, and $b,c$ could be either variables, inputs or constants. Additionally, certain variables are distinguished as outputs. For example, here is how to multiply two $2\times 2$ matrices using the usual algorithm, with input matrices $a_{ij},b_{ij}$ and output matrix $c_{ij}$:

$$
\begin{align*}
x_{11} &\gets a_{11} \times b_{11} & y_{11} &\gets a_{12} \times b_{21} & c_{11} &\gets x_{11} + y_{11} \\
x_{12} &\gets a_{11} \times b_{12} & y_{12} &\gets a_{12} \times b_{22} & c_{12} &\gets x_{12} + y_{12} \\
x_{21} &\gets a_{21} \times b_{11} & y_{21} &\gets a_{22} \times b_{21} & c_{21} &\gets x_{21} + y_{21} \\
x_{22} &\gets a_{21} \times b_{12} & y_{22} &\gets a_{22} \times b_{22} & c_{22} &\gets x_{22} + y_{22}
\end{align*}
$$
The complexity measure is the number of lines in the program.

For matrix multiplication, one can prove a normal form for all algorithms. Every algorithm can be converted into an algorithm of the following form, at the cost of only a constant multiplicative increase in complexity:

Certain linear combinations $\alpha_i$ of the input matrix $a_{jk}$ are calculated.
Certain linear combinations $\beta_i$ of the input matrix $b_{jk}$ are calculated.
$\gamma_i \to \alpha_i \times \beta_i$.
Each entry in the output matrix is a linear combination of $\gamma_i$s.

This is known as bilinear normal form. In the matrix multiplication algorithm shown above, $x_{jk},y_{jk}$ function as the $\gamma_i$, but in Strassen's algorithm the linear combinations are more interesting; they are the $M_i$'s in Wikipedia's description.

Using a tensoring approach (i.e. recursively applying the same algorithm), similar to the asymptotic analysis of Strassen's algorithm, one can show that given such an algorithm for multiplying $n\times n$ matrix with $r$ products (i.e. $r$ variables $\gamma_i$), then arbitrary $N\times N$ matrices can be multiplied in complexity $O(N^{\log_n r})$; thus only the number of products matters asymptotically. In Strassen's algorithm, $n = 2$ and $r = 7$, and so the bound is $O(N^{\log_2 7})$.

The problem of finding the minimal number of products needed to compute matrix multiplication can be phrased as finding the rank of a third-order tensor (a "matrix" with three indices rather than two), and this forms the connection to algebraic complexity theory. You can find more information in this book or these lecture notes (continued here).

The reason this model is used is twofold: first, it is very simple and amenable to analysis; second, it is closely related to the more common RAM model.

Straight-line programs can be implemented in the RAM model, and the complexity in both models is strongly related: arithmetic operations have unit cost in several variants of the model (for example, the RAM model with real numbers), and are otherwise related polynomially to the size of the numbers. In the case of modular matrix multiplication, therefore, arithmetic complexity provides an upper bound on complexity in the RAM model. In the case of integer or rational matrix multiplication, one can show that for bilinear algorithms resulting from tensorization, the size of the numbers doesn't grow too much, and so arithmetic complexity provides an upper bound for the RAM model, up to logarithmic factors.

It could a priori be the case that a RAM machine can pull some tricks that the arithmetic model is oblivious to. But often we want matrix multiplication algorithms to work for matrices over arbitrary fields (or even rings), and in that case uniform algorithm should only use the arithmetic operations specified by the model. So this model is a formalization of "field-independent" algorithms.


Boolean variable that captures whether an inequality holds I have an integer linear program with variables $x_1,\dots,x_n$.  I have an inequality $a_1 x_1 + \dots + a_n x_n \ge b$ that I care about; it may or may or not hold.

I want to introduce a boolean variable $y$, with the intent that $y=1$ if this inequality holds or $y=0$ if it doesn't.  How can I write linear inequalities to constrain $y$ to take this value?

All of $a_1,\dots,a_n,b$ are constants.  I know upper and lower bounds for all of the $x_i$'s.

Add the inequalities

$$\begin{align*}
a_1 x_1 + \dots + a_n x_n &\ge b - M (1-y)\\
a_1 x_1 + \dots + a_n x_n &< b + M y,
\end{align*}$$

where $M$ is chosen sufficiently large.

Why does this work?  If $y=1$, then the first inequality forces $a_1 x_1 + \dots + a_n x_n \ge b$ to hold.  If $y=0$, then the second inequality forces $a_1 x_1 + \dots + a_n x_n < b$ to hold, i.e., $a_1 x_1 + \dots + a_n x_n \ge b$ to be false.

How large does $M$ need to be?  If the $x_i$'s are zero-or-one variables, then it suffices to take $M$ to be at least $\max(b,a_1+\dots+a_n-b+1)$.  In general, if you have upper and lower bounds for each $x_i$, you can derive how large $M$ needs to be.


What is the name of this size method calculating the size of a node? My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called?

int size (BinaryNode t) {
  if (t == null)
    return 0;
  else
    return 1 + size(t.left) + size(t.right);
}

Remember that to get the actual value of size(t.left), you have to evaluate the method size at the node t.left, i.e. assuming t.left has left and right children the algorithm with call size((t.left).left) and size((t.left).right).


k-disjoint pair paths where any source can pair with any sink I have a question regarding a problem I'm working on.

The problem is given an MxN grid with k sources and sinks, find non intersecting paths (vertex disjoint) such that all sources are paired with a sink. Each source must be paired to a single sink, and each sink must be paired to a single source, however all of the sources are compatible with all of the sinks. This could be imagined as k identical locks and k identical keys, all that matters is that its possible to move the keys into locks without having paths that intersect.  By contrast in the original problem, sink Si must be paired with source Di and this is an input parameter of the problem.

The underlying problem is NP-Hard but according to a vague comment I found, with the given restriction it can be solved in polynomial time. Unfortunately I can't find any relevant literature that could help.

https://stackoverflow.com/questions/19404033/all-pairs-maximally-disjoint-paths-algorithm/19411277#19411277

If anyone could point me towards proofs or papers that discuss this problem I would appreciate it.

Your link refers to edge-disjoint paths -- i.e., vertices can visited by multiple paths, but no edge can be visited by multiple paths.  It sounds like you want vertex-disjoint paths -- is that right?  Please edit to clarify.

Both problems can be solved in polynomial time with a Maximum Flow algorithm.

For edge-disjoint paths, put unit-capacity bidirectional edges (i.e., one edge in each direction) between every pair of adjacent vertices; make a super-source $s$, with unit-capacity out-edges to each of the $k$ sources, and a super-sink $t$, with unit-capacity in-edges from each of the $k$ sinks.  The capacity constraints ensure that no edge is used by more than one path.

For vertex-disjoint paths, do the same -- but then replace every vertex $v$ with two vertices, $v_-$ and $v_+$, with all of $v$'s in-edges incident on $v_-$ and all of $v$'s out-edges incident on $v_+$, and add a single directed edge of unit capacity from $v_-$ to $v_+$.


Algorithm to find pairs Task: There are N persons. Some of the persons were meet before. I need to find pairs of persons, that were not meet before.
Example: 4 persons - A, B, C, D.
A and B were meet before.
Good solutions: (A + C, B + D) OR (A + D, B + C).
Bad solution: (C + D) because it is forrbidden to create pair (A + B).
What algorithm can help to resolve this task?

It seems that you are looking for a maximum matching in a graph where vertices represent people and an (undirected) edge $(u,v)$ means that $u$ and $v$ have not met before.
This problem can be solved in time $O(n^{1/2} \cdot m) = O(n^\frac{5}{3})$, where $n$ is the number of people and $m$ is the number of pairs of people that have not yet met.


Why there is no Turing Machine that accepts the Diagonal Language? Given the diagonal language
$$L_d = \{ i : \sigma_i \notin L(M_i) \}$$
Where $M_i$ are all Turing Machines and $\sigma_i$ are all the words, if you put in in a Matrix like this:
$$\begin{array} {|c|c|c|c|c|c|c|}
\hline
& \sigma_1 & \sigma_2 & \sigma_3 & \sigma_4 & \sigma_5 & ...\\ \hline
M_1 & 1 & 0 & 1 & \dotsb & \dotsb & \dotsb \\ \hline
M_2 & 0 & 0 & 1 & \dotsb & \dotsb & \dotsb \\ \hline
M_3 & 1 & 0 & 1 & \dotsb & \dotsb & \dotsb \\ \hline
M_4 & \vdots & \vdots & \vdots & 1 & \dotsb & \dotsb \\ \hline
M_5 & \vdots & \vdots & \vdots & \vdots & \ddots & \dotsb \\ \hline
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\\ \hline
\end{array}$$
Then $L_d$ is represented by the numbers in the diagonal of the matrix.
In class I was told that there is no TM that accept $L_d$, but I do not quite understand why is that, could somebody help?
PS: The above explanation was included because I did not know if this is called Diagonal Language in English, Spanish is my mother tongue.

In the following I assume that the matrix has an 1 in coordinates $(i,j)$ if $M_i$ accepts $\sigma_j$ and a $0$ otherwise (swapping all 1s and 0s does not affect the argument).
Consider the language $L = \{\sigma_i \in \Sigma^* : \sigma_i \not\in L(M_i) \}$ that contains all the words $\sigma_i$ such that the entry at coordinates $(i,i)$ of the matrix is $1$. I will first show that $L$ is not acceptable.
Suppose towards a contradiction that there is some Turing machine $M^*$ that accepts $L$.
Since the set of Turing machines is enumerable, and the rows of the matrix are associated with an enumeration of all Turing machines, there must be some integer $i \ge 1$ such that $M_i = M^*$.
Then consider the word $\sigma_i$ and suppose that the entry at coordinates $(i,i)$ is $1$.
From the way the matrix is constructed you know that $M_i$ accepts $\sigma_i$. However, by the definition of $L$, you also know that $\sigma_i \not\in L$. This implies that $M^* = M_i$ cannot accept $\sigma_i$. This is a contradiction.
If the entry at coordinates $(i,i)$ is $0$, then $M_i$ does not accept $\sigma_i$. However, $\sigma_i \in L$ implying that $M^* = M_i$ accepts $\sigma_i$. Again, this is a contradiction.
Going back to your language $L_d$: if $L_d$ were acceptable then so would be $L$.
Suppose towards a contradiction that there is a Turing Machine $M$ that accepts $L_d$.
To accept $L$ proceed as follows:

find the index $i$ such that $\sigma_i = x$. This can be done by enumerating the words in $\Sigma^*$.
Simulate $M$ with input $i$.
If $M$ with input $i$ halts and accepts, accept.

Since this is a contradiction, $L_d$ cannot be acceptable.


Proving $\{xx^R \mid x\in L_1, x^R\in L_2\}$ is context-free I have this problem:

  Let $L_1$ and $L_2$ be two regular languages.  Show that $L_3 = \{xx^r : x \in L_1, x^r \in L_2 \}$ is a context-free language.

I am unsure how to prove that some language is context-free. Could someone please provide the steps?

One way to prove that a language is context-free is to find a context-free grammar that recognizes it. Just go through the definition (on Wikipedia for example) and try to find a context-free grammar for $L_3$ (it's easy). Good luck!


Problems understanding the Union functionality of the Union-Find Algorithm I am currently doing a course based on algorithms (Coursera). I've come across an algorithm called quick find. The course does have reference to Big O Notation. Despite the fact that I do not have much knowledge of Big O, I have been doing some basic reading.

Implementation (Java):

Initializes the array:

public QuickFindUF(int N)
{
    id = new int[N];
    for (int i = 0; i < N; i++)
    id[i] = i;
}

Checks if two input values are connected:

public boolean connected(int p, int q)
{
    return id[p] == id[q];
}

Union Implementation:

public void union(int p, int q)
{
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i < id.length; i++)
    {
        if (id[i] == pid)
        {
            id[i] = qid;
        }
    }
}

The id variable is a private instance variable.

My Problem:

1) In the study material it says:

  It takes N2 array accesses to process a sequence of N union
  commands on N objects

How can it take N2 if the union method only has a single for loop?

2) It also says that the union method takes

  at most 2N + 2 array accesses

What does this mean? My speculation is that 2N could mean that the array is accessed twice (line 7 and line 9 of the union method). I have no idea what + 2 refers to though.

I apologize if I have incorrectly stated something.

Any help would be highly appreciated. Thank You.

The answer to your first question is that while it takes (roughly) $N$ array accesses to perform one union operation, it takes (roughly) $N^2$ to perform $N$ of them. This is what is meant by the phrase "a sequence of $N$ union commands".

Regarding your second question, the first two operations are those that initialize pid and qid, and the body of the loop (which runs up to $N$ times) contains two more, one which compares an entry to pid, and another which assigns qid to the same entry.


Knapsack Problem with Constraints on Item Values Given $n$ items with weights $w_1,...,w_n$ and values $v_1,...,v_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight limit). Now, a new constraint is, once an item with value $v_i$ is taken, all items whose value is greater than $v_i$ must also be taken. (It is okay to assume that all $v_i$'s are different)
My purpose is to achieve this in $O(n)$ time, and here is my attempt (suppose the input is an array $A$ of tuples $(w_i, v_i)$):

Calculate total weight of the items: $W_{\mathrm{total}}\gets \sum_{i=1}^n w_i$;

while $(W_{\mathrm{total}} > W)$ do:
2.1 $p\gets$ median of values in $A$;
2.2 $R\gets$ items whose value is greater than $p$;
2.3 $L\gets A\setminus R$; (items whose value is smaller than $p$)
2.4 $W_R\gets$ $\sum_{A[i]\in R}w_i$;
2.5 $W_{\mathrm{total}}\gets W_R$;
2.6 $A\gets R$;

$W\gets W- W_{\mathrm{total}}$; (the remaining capacity)

Repeat step 2 for the array $L$, generating the array $L'$;

Return $L'\cup A$;

Notice that the algorithm for finding the median costs linear time.
I presume that my algorithm costs $O(n)$ time since, for every iteration in each while loop, the input size halves--but I am not 100% confident of that. So does this algorithm really cost linear time? If not, what amendments can be made, or is there a general idea for designing such an algorithm that costs linear time? Any help will be much appreciated! :)

Yes your algorithm runs in $O(n)$ time if you use the median of medians algorithm.
You can prove that to yourself by looking at your algorithm and noting that in every loop the size of the array we are considering is cut in halve. And the runtime of the loop body is $O(n)$ (if we use median of medians and array copying/filtering is $O(n)$ anyway). Now we get the following sum:
$$\sum_{i=0}^{\log(n)} \frac{n}{2^i} \leq \sum_{i=0}^{\infty} \frac{n}{2^i} = n\cdot\sum_{i=0}^{\infty} \frac{1}{2^i} = 2n \in O(n)$$
The $\log(n)$ comes from the fact that you can only divide the array size $log(n)$ times in halves until you arrive at $1$ (because $2^{\log(n)} = n$). Every term of the sum expresses the cost of one execution of the loop body.


How is A* search superior to Dijkstra's algorithm Dijkstra's algorithm is often quoted as being used to find the shortest path route however I was surprised to know that there exist A* search which is a extension of Dijkstra's algorithm.

How is it that A* search algorithm is able to perform better compared to Dijkstra's algorithm , what sort of technique does it used that Dijkstra's algorithm did not use ???

Consider providing driving directions from an origin to a destination. Although sometimes traveling away from the destination for short distances is required (think highway on ramp), in general it is best to travel toward the destination. In this case A* is likely to outperform Dijkstra's algorithm because it (probably) will traverse less of the graph.

Dijkstra's algorithm uses a single heuristic, $g(n)$, which is the distance from the origin. In selecting the next road to evaluate, the road with the least $g(n)$ is selected; however, this road may travel away from the destination. A* adds an estimate of the remaining distance, $h(n)$, to bias the search towards the destination. The full A* heuristic is $f(n) = g(n) + h(n)$. Note that as the search progresses, $f(n)$ must monotonically increase or else the path found may not be the shortest.  Thus, $h(n)$ must be optimistic and never underestimate the remaining distance (in the directions example, assume the remainder of the trip can be a straight line).


Validity of reduction (3-SAT) I'm trying to show that a special variant of the common 3-SAT is NP-complete by reducing 3-SAT to this special variant.

This special variant works like the normal 3CNF-SAT, except every other clause is conjunctive instead of disjunctive. For example an instance of this variant could be
$(x \vee y \vee z) \wedge (x\wedge w\wedge k) \wedge (y \vee \neg{}z \vee f)$.

EDIT:

Would the following work?
If I want to reduce $from$ 3-SAT, I would propose an instance of the 3-SAT variant, and via an algorithm running in polynomial time, transform every other clause (the conjunctive ones) into 3 new disjunctive clauses like the following example.

Instance of 3-Sat Variance
$(x \vee y \vee z) \wedge (x\wedge w\wedge k) \wedge (y \vee \neg{}z \vee f)$

Transformation/Reduction
$(x \vee y \vee z) \wedge (x\vee x\vee x) \wedge (w \vee w \vee w) \wedge (k \vee k \vee k) \wedge (y \vee \neg{}z \vee f)$

EDIT 2:

Or do you mean I should look at it the other way around?

If I want to prove that this 3-SAT variant is NP-complete, could I for example simply add a new, trival term $z$ not used in the original list of terms (give it TRUE as truth value), and add a clause $(z \wedge z \wedge z)$ inbetween all the original clauses of the original 3-SAT instance?

Hint 1. If the conjunctive "clauses" are trivially satisfiable, then any unsatisfiability must be due to the ordinary disjunctive clauses.

Hint 2. You don't have to change any of the clauses of the original CNF.


Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters? Question: Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters? And how many words can we form with up to 4 letters?

I was thinking about the logic behind this and came up with this: perhaps the number of words that can be formed with 4 letters is $4^3 = 64$ words. Is that correct?

I could not think about how many words up to 4 letters, because that includes words with 1, 2 and 3 letters.

Assume you have the alphabet $\{A,B,C\}$ and you want to form words of length 4.

For the first letter you have 3 choices, $A, B$ or $C$. For the second letter you have again 3 choices, $A,B$ or $C$ and so on. In total: $ 3 \cdot 3 \cdot 3 \cdot 3 = 3 ^ 4 = 81 $ possibilities.


Maximum number of nodes connected when the link has a large buffer A link of capacity 100 Mbps is carrying traffic from a number of sources. Each source generates an on-off traffic stream;when the source is on, the rate of traffic is 10 Mbps, and when the source is off, the rate of traffic is zero. The duty cycle,which is the ratio of on-time to off-time, is 1 : 2Assuming that all sources are synchronized and that the link is provided with a large buffer, the maximum number of sources that can be multiplexed so that there is no data loss is_____.

My solution manual claims that the max. no of nodes connected can be found out by dividing total link capacity from expected bandwidth utilization.

I dont understand why we need to take the expected bandwidth. Why can't we simply use the maximum bandwidth utilization?

Thanks in advance!

You can have ten of them going at once.  If they're on a third of the time and you decree that, for instance, ten operate for twenty seconds, then the next ten, then the next ten, then you can have thirty of them total.

If you just focused on the max you'd think that you could only have ten (which would be the case if you weren't able to synchronize them, and thus couldn't rule out that they might all try to talk at once.)

By averaging over the available time you can get the same result without having to speculate about how exactly to schedule them.  Over its uptime, each node transmits at an average of 3+1/3 Mbps.  Dividing 100 MBps by this number gives 30.


AVL trees are not weight-balanced? In a previous question there was a definition of weight balanced trees and a question regarding red-black trees.

This question is to ask the same question, but for AVL trees.

The question is, given the definition of $\mu$-balanced trees as in the other question,

  Is there some $\mu \gt 0$ such that all big enough AVL trees are $\mu$-balanced?

I presume there is only one definition of AVL trees and there is no ambiguity.

Claim: No, there is no such $\mu$.

Proof: We give an infinite sequence of AVL trees of growing size whose weight-balance value tends to $0$, contradicting the claim.

Let $C_h$ the complete tree of height $h$; it has $2^{h+1}-1$ nodes.

Let $S_h$ the Fibonacci tree of height $h$; it has $F_{h+2} - 1$ nodes. [1,2,TAoCP 3]

Now let $(T_h)_{i\geq 1}$ with $T_h = N(S_h,C_h)$ the sequence of trees we claim to be a counter example.

Consider the weight-balancing value of the root of $T_h$ for some $h \in \mathbb{N}_+$:

$\qquad \displaystyle \begin{align*}
  \frac{F_{h+2}}{2^{h+1} + F_{h+2} - 1} &= \frac{1}{1 + \frac{2^{h+1}}{F_{h+2}} - \frac{1}{F_{h+2}{}}} \\
&\sim \frac{F_{h+2}}{2^{h+1}} \\
&= \frac{\frac{1}{\sqrt{5}}(\phi^{h+2} - \hat{\phi}^{h+2})}{2^{h+1}} \\
&\sim \frac{\phi^{h+2}}{\sqrt{5}\cdot 2^{h+1}} \underset{h \to \infty}{\to} 0
\end{align*}$

This concludes the proof.

Notation:

$F_n$ is the $n$th Fibonacci number
$\phi \approx 1.6$ is the Golden Ratio, $\hat{\phi} \approx -0.62$ its conjugate.
$f \sim g$ means that $f$ and $g$ are asymptotically equal, i.e. $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$.

Nota bene: Fibonacci trees are exactly those AVL trees with the least nodes for a given height (or, equivalently, the maximum height for a given number of nodes).

Addendum: How can we come up with Fibonacci trees if we had not overheard a professor mentioning them? Well, what would an AVL tree of height $h$ with as few nodes as possible look like? Certainly, you need a root. One of the subtrees needs to have height $h-1$, and we have to choose it with as few nodes as possible. The other one can have height $h-2$ without violating the height balancing condition, and we choose it also with as few nodes as possible. In essence, we construct the trees we want recursively! These are the first four:

[source]

We set up a recurrence for the number of nodes $f(h)$ in the thusly constructed tree with height $h$:

$\qquad \displaystyle \begin{align*}
  f(1) &= 1 \\
  f(2) &= 2 \\
  f(h) &= f(h-1) + f(h-2) + 1 \qquad n \geq 3
\end{align*}$

Solving it leads to $f(h) = F_{h+2} - 1$ which we used above.

The same proof is given (with less detail) in Binary search trees of bounded balance by Nievergelt and Reingold (1972).


Sort deck of cards with least no of moves We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

4 3 1 2
3 4 1 2
2 3 4 1
1 2 3 4

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

2 3 1 4
1 2 3 4

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2

Given a permutation $\pi:[n]\to[n]$ of cards from $1$ to $n$ you can find the first card to move to the front the following way:

$c \leftarrow n$
for each $k$ from $n$ down to $1$ do
$\space\space\space$ if $c = \pi(k)$ then
$\space\space\space\space\space\space$ $c \leftarrow c - 1$
$\space\space\space$ end if
end for
return $c$

In other words, choose the highest card, for which there is another card of higher value in front of it. More formally, choose a maximum $c\in[n]$ such that there exists a $c' > c$ with $\pi(k') = c'$, $\pi(k) = c$ and $k' < k$. Clearly, this card is not in order yet and since it is the one with the highest value it must be moved first if we want to keep the number of moves minimal. For the permutation $3,1,4,2$ this card is clearly card number $2$.


What is this question asking for?-->Test this code, find an error in the program and "construct an instance to demonstrate the error" (in C) I am learning the basics of the language C, and so far we have covered up to loops. This question is related to my assignment. The problem is I do not understand what the question is asking.

I know the error in the code, but I don't understand what this question is asking me to do? What is an instance? Am I supposed to make a different piece of code? Because I am pretty sure the error is a semantic one(knowledge based rather than syntax). Here is the code anyways just for context:

As noted by Tom van der Zanden in a comment, and given you already know what's wrong with the code, think of an input that will cause the program to fail, just run the program with that input and you have your instance. Does it make more sense if you think of the phrase, "for instance"?

You may be overthinking it (a good sign actually), if this is just a very basic C language course, they are probably being rather obvious in what they are asking for.

KISS -- Keep It Simple, Sailor


Is Unification "an Implementation of Existential Quantification"? I read a comment (I've forgotten the source), "Unification is an implementation of existential quantification." (Emphasis mine.)

If true, this point of view clears up many things.

For instance why omitting the "occurs check" in unification can lead to unsound inference:  it would be the same as using the assumption of the existence of a thing in your proof(-term) of the existence of that thing.

It would also explain why the algorithms for unification in logic programming language engines I've looked at seem (to me) more arbitrary than other operators such as conjunction and disjunction.

But - is the statement true?  Is it an over-simplification?

It's possible you're paraphrasing me. I've certainly said things similar to that e.g. here.

A more precise statement would be that existential quantification in logic programming languages is (typically) handled by introducing a unification variable. To perform existential introduction, you need to have a term $t$. The rule looks like: $$\dfrac{\Gamma\vdash P[t/x]}{\Gamma\vdash\exists x.P}$$

One way to implement this is to just guess a term $t$ and then see if we can backchain $P(t)$. Of course, for a language like Prolog, there are an infinite number of possible terms, and you have no guidance on what term to guess. A different option is to have $t$ be a meta-variable that stands for a term and continue execution on the hope that we can constrain $t$ enough to know what to decide later. This is essentially what a unification variable is. Unification itself just constrains what possible terms that meta-variable can be. Then, instead of actually enumerating the (now constrained) terms, we usually return the (simplified) constraints themselves as a compact representation of the set of possible terms, assuming they aren't contradictory (i.e. that that set isn't empty).

The occurs-check is simply the enforcement of the fact that usual term languages don't have infinite terms. You can consider other term languages that can represent these terms leading to things like rational tree unification.

Unsurprisingly, the operation unification itself most directly implements is equality. If we did the "exhaustively enumerate terms" approach to handling existential quantification, all the places where we (implicitly) use "unification" could just be straightforward syntactic checks of ground terms. With meta-variables, they instead produce constraints. Of course, this suggests the natural and common generalization of allowing constraints other than syntactic equality, and this leads to constraint logic programming. One generic example of such a constraint is disunification which states what a term (potentially containing meta-variables) cannot be. It is the negation of unification, $t\not\equiv s$ states that for all substitutions $\sigma$, $t[\sigma]\neq s[\sigma]$.


Is the language of words with equal number of 010s and 101s as substrings regular? Is the language of words containing same number of 101s and 010s regular?
If yes, how can I design a DFA for it?

In general, is the language of words containing equal number of strings which one is "one's complement" of the other one is regular (like the language of words containing equal number of 01s and 10s which is regular)? Is there any counterexample?

No, the language of words containing same number of 010s and 101s is not regular.

Consider $x_n=(0100)^n$ and $y_n=(1011)^n$. Then $x_iy_j$ contains $i$ number of 010s and $j$ number of $101s$. That is, $x_iy_j$ is in the language if and only if $i=j$.

So $x_i$ represents a distinct Nerode-Myhill equivalence classes for all $i$. Since there are infinitely many such $x_i$, there are infinitely many Myhill-Nerode equivalence classes. By Myhill–Nerode theorem, the language is not regular.

Here are several related exercises. Exercise 2 answers the more general situation in the question. Exercise 3 is a further generalization.

Let $\Sigma=\{0,1\}$.

Exercise 1. The language of words over alphabet $\Sigma$ containing the same number of 01s and 10s is regular. The language of words over alphabet $\{0,1, 2\}$ containing the same number of 01s and 10s is not regular.

Exercise 2. Let nonempty $w\in \Sigma^*$. Let $\overline w$ be the one's complement of $w$. For example, $\overline{010010111}=101101000$. Let $E_w$ be the language of words over $\Sigma$ containing the same number of $w$s and $\overline w$s. Show that
$$ E_w\text{ is regular} \iff w=01\text{ or }w=10$$
(It may take a while to do this exercise.)

Exercise 3. Let $u$ and $v$ be two different non-empty words in $\Sigma^*$. Let $E_{u,v}$ be the language of words over $\Sigma$ containing the same number of $u$s and $v$s. Let $N_{u,v}$ be the language of words over $\Sigma$ containing no $u$ nor $v$ as a subword. Show that
$$ L_{u,v}\text{ is regular } \iff
\{u,v\}=\{01,10\}\text{ or } E_{u,v} = N_{u,v}.$$
(It may take a while to do this exercise.)


How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix? Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such a rule can be modeled as a function that takes as input a 3 by 3 matrix of bits, and outputs a bit.

Such a rule can be represented easily using a string of 512 bits representing the output for each of the $2^{3 \times 3}$ input states. Since this representation is bijective, a rule can also be randomly generated by sampling 512 bits.

However, it is sometimes preferable for reasons of aesthetics and comprehensibility that the output of the rule be the same when the input matrix is rotated or flipped horizontally or vertically. The rule for Conway's Game of Life is an example of a function satisfying this restriction.

Given a function $r : 2^9 \to 2$ which does not necessarily obey this restriction, we can obtain a function that does by mapping the input to the lexicographically smallest matrix obtainable by reflecting or rotating it before passing to $r$. However, this provides little insight into the questions I am interested in:

How many functions obey this restriction?
How can they be compactly representing using a bit string?
How can they be efficiently randomly generated?

I won't go into the details of your specific case but try to answer the general problem.

In the unrestricted case there is a mapping from each of the $n$ (=512) input states to one of 2 output states and you want to restrict the function as follows:

Create a partitioning of the initial $n$ input states into subsets.
Your adapted function maps each of these subsets to an output

Proceed as follows:

Enumerate all input states from 1 to $n$ (this is then the index of that state)
Write a function $f(i)$ that generates all rotations/symmetric versions of an input state $i$ and take the lowest index of that set
Partition the set $1..n$ according to $f$, i.e. if $f(x) = f(y)$, they are in the same class. The result is a pairwise disjoint set of sets, where each set consists of 'similar' input states that should therefore also have the same output.
Let $P$ be the number of these sets.

Answering your questions should then be easy:

You could assign each of the $P$ sets an arbitrary output to get a unique function. $\Rightarrow 2^P$ functions
A bitstring of length $P$
Generate random integers (with more than $P$ bits each) and take the last $P$ bits.

a. Maybe consider the distribution of values generated by your RNG, i.e.: are the last $P$ bits uniformly (or whatever you desire) distributed?


Complexity of checking whether linear equations have a positive solution Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $<n$. What is the complexiy to check
whether it has a solution $x$ such that all entries of $x$ are stricly greater than 0 (namely, $x$ is a positive vector)? Of course, one can use Gauss elimination, but this seems not to be optimal.

First, this can be solved by linear programming. Let $x_1$, $x_2$, $\ldots$, $x_n$ be your variables. The linear program that solves your question is then

$\max t$
subject to
$t \leq x_i$, for $i=1 ... n$,
$Ax = 0$.

If the maximum is 0, then there is no positive solution. If the maximum is $\infty$ (i.e., the linear program is unbounded) then there is a positive solution.

Second, using standard transformations on linear programs, the feasibility problem for an arbitrary linear program with strict inequalities can be reduced to your problem. We start with the feasibility problem

Does there exist $x$ such that
$A x < b$ ?

We can now add a new variable $x_{n+1}$ to the right-hand-side of all these equations and an inequality $x_{n+1} > 0$ to make everything homogeneous. So for the $k$th equation, we now have

$a_{k,1} x_1 + \ldots + a_{k,n} x_n - b_k x_{n+1} < 0$.

This gives an equivalent problem on a new matrix $A'$:

Does there exist $x$ such that
$A'x < 0$ ?

Next, we can turn the inequalities into equations by adding some variables $y_i$ and requiring that $y_i > 0$. The $k$th equation on the new problem turns into

$a'_{k,1} x_1 + \ldots + a'_{k,n} x_n + a'_{k,n+1} x_{n+1} +y_k = 0$.

Finally, we want to allow all the variables to be positive. How we do this? For every variable $x_i$ with an arbitrary sign, we replace $x_i$ by $z_i - w_i$, and require $z_i>0$, $w_i > 0$.

The feasibility problem is essentially as hard as an arbitrary linear programming problem, so in general there won't be any easier way to solve your problem than using linear programming.


How to Formally define $\delta$ in a DFA? I have made a draw of a DFA, and I have to formally define the automaton in the following format. Let $A$ be the necessary automaton :
$$A=<\Sigma,Q,q_0,\delta,F>$$

Where $\Sigma=\{a,b,c\}, Q=\{q_0,...,q_4\}, F=q_3$ and $q_0$ is the initial state.

The drawing is attached to this post:

Can I do something like $\delta_{A}(q_0,\sigma)=q_1$ for each state? should I unite a few states together?

Thank you!

You're over-thinking this.

You need to define the value of $\delta(q,\sigma)$ for every $q\in Q$ and $\sigma\in\Sigma$ and, ideally, make it clear that you have done so. What format you use is a matter of your and your instructor's personal preferences.


Relation between MAX CUT and MIN CUT I'd like to ask a question about MAX CUT and MIN CUT on graphs with unit edge-weight. I know that MAX CUT is NP-Hard, but MIN CUT is in P (i think)?

Barahona, in 1982, showed (Lemma 1) finding a cut of at least k on a unit-weight graph is equivalent to finding a cut of at most -k on a graph in which each edge is replaced with a chain of edges, each of weight +1 except for one with weight -1. http://yaroslavvb.com/papers/barahona-on.pdf

Is this not technically MIN CUT on that extended graph? Wouldn't this show that MAX CUT can be reduced to MIN CUT, and therefore belong in P or is there something about MIN CUT I don't understand properly?

Both problems you mention have the stated complexity only when edge weights are non-negative. With these constraints, the reduction you describe no longer works.


Prove the following language is regular using closures How can I prove this language is regular using just closures and homomorphism?
$$
L = \{a_1b_1a_2b_2\dotsm a_nb_n \mid a_i \in L_1 , b_i \in L_2\}
$$
and we know $L_1$ and $L_2$ are regular.

To get you started, consider a restricted version of your languge:
$$
L'=\{ab\mid a\in L_1, b\in L_2\}
$$
Notice that $L$ is the concatenation $L'=L_1\circ L_2$. Can you carry on from there?


Finding the minimum value of all subsets in a 2D array Imagine a N by M 2D array of random positive integers and two coordinates (i1,j1), (i2,j2), which represent the upper-left bound and bottom-right bound of a subarray, respectively.  Is there a efficient algorithm to calculate all the minimum values of each subarray?
[[4, 10, 9, 7],
 [9, 8,  1, 2],
 [1, 21, 3, 1]]

In this example of a 3 by 4 grid, if the two coordinates were (0,1) and (2,2), the minimum in this case would be 1, out of the values 10,9,8,1,21,3.
Other than the naive solution of finding all subsets and calculating the minimum in this subarray, which would be well beyond O(n^4), I have also considered using a method similar to prefix sum by creating a separate 2D array and storing the minimum from (0,0) to (i,j) at the value (i,j), but this issue here is you can't account for the overlap like you do in prefix sums.
Is there a way to account for overlap or another, more efficient algorithm?
Thank you!

In one dimension, looking for the maximum sum, this is solved by Kadane's algorithm. The referenced page does discuss some of the history and gives pointers to efficient solutions for the two-dimensional problem.
Bentley in his seventh "Programming Pearls" column (see e.g. here) discusses the one-dimensional problem in depth, devising ever more efficient algorithms for it's solution. Bentley's columns (and much more) are collected in his book "Programming Pearls" (Addison-Wesley, 2nd edition 1999).


How to compare algorithms having the same complexity I am new to programming and want to learn how to compare algorithms having the same complexity and pick the best one. Certain problems can be sloved using several algorithms which have the same complexity. How do i compare such algorithms

By "having the same complexity" I assume you mean having the same time complexity.

If you have done fine analysis of time complexity of these algorithms then there may be hidden constants or factors of lower degree polynomials which are ignored when you compare using big-O notation but have effect in practice. For example, if one algorithm always takes $n^2 + 100n + 10000$ steps and the second one takes $0.3n^2$ then the second one would be a better  choice, though both run in $O(n^2)$.

You could also consider their space complexity and choose one which consumes less memory if the memory consumption matters and more important than the time complexity.

If you aim to implement these algorithms yourself and use it in your commercial application (or something like that) then you could think about how easy they are implemented and how easy these algorithms scale.


RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1 I want to make a following proof but I got some difficulties with it.
Would be super if you people have any tips / advises.
Introduction:
Let (N,e) be our public key and (N,s) our private key with $N=pq$ and $ggT(\varphi(n),e)=1$, as well as $es\equiv 1\mod N$.
I want to show that since Lemma of Bézout shows, that there are $a,b\in \mathbb{N}$ so that $ap-bq=1$, the message of $x=ap\mod N$ is equal to the encrypted message $y=x^e \mod N$.
My Plan:
I started by using the Chinese remainder theorem. To show $x\overset{!}{=}y=x^e\mod N$ we need to show, that $x\overset{!}{=}x^e\mod p$ and $x\overset{!}{=}x^e\mod q$. I could also use the Chinese remainder theorem on $x=ap\mod N$.
So I need to show, that $ap \mod p=(ap)^e\mod p$. Since ap is a multiple of p, it should be $ap\equiv 0\mod p$ and so $(ap)^e=0\mod p$. It follows that $ap\mod p=(ap)^e\mod = p= 0 \mod p$.
I now need to show, that $ap\mod q=(ap)^e\mod q$. This is the part I am struggling with. I know that $ap-bq=1$ but I have no glue how this is going to help me. I was thinking about something like $ap=(bq+1)\mod q$ but i am not sure if this works / what to do next.

You can show that $ap\mod q =(ap)^e\mod q$ by using the fact, that $ap-bq=1\Longleftrightarrow ap=bq+1$.
You know that $q|bq$ and therefor $ap\mod q = bq+1\mod q \equiv 1\mod q$.
This implicates that $(ap)^e\mod q = (bq+1)^e\mod q \equiv 1\mod q$. Therefor $ap\mod q \equiv (ap)^e\mod q.$
Now with the chinsese remainder theorem we know that $ap\equiv_N(ap)^e$.


Single Layer Perceptron vs Multi Layer Perceptron Why the single layer perceptron has a linear activation function while the Multi Layer Perceptron has a non-linear activation function ?
What is the potential of the Multi Layer Perceptron respect of the Single Layer perceptron ?

Your premise is wrong.  A single-layer neural network (perceptron) can use a (nonlinear) activation function.  Nothing prevents you from doing that.

It's common that the last layer of a neural network doesn't use any activation function, and instead is input into a softmax layer.  If there's only one layer, that means that no activation function is used.  But this is just a standard convention.  There's no ironclad law that says you have to do it this way.  You could have an activation function after a single-layer neural network, if you wanted.


Universal simulation of Turing machines Let $f$ be a fixed time-constructable function.
The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given

the description of a TM $\langle M \rangle$, and
an input string $x$,

runs for $g(|x|)$ steps and returns $M$'s answer on $x$. And $g$ can be taken to be any function in $\omega(f(n)\lg f(n))$.
My questions are:

What is the best known simulation result on a single tape TM? Does the result above also still hold?

Is there any improvement on [HS66]? Can we simulate TMs on a two-tape TM for $f(n)$ steps in a faster way?
Can we take $g(n)$ to be in $\omega(f(n))$ in place of $\omega(f(n)\lg f(n))$?

What is the best known simulation result on a single tape TM? Does the result above also still hold?

We can simulate a multiple-tape TM on a single-tape TM with quadratic increase in time. The simulation time is $O(n^2)$. The quadratic increase is required since there are languages (e.g. palindromes) that require time $\Omega(n^2)$ on a single-tape DTM but can be solved in time $O(n)$ on a two-tape DTM.

In short, the result above does not work when the simulator is a single-tape TM.

For simulation of single-tape TMs on a single-tape TM (with arbitrary finite alphabet), the result holds, i.e. the simulation can be done with $\lg$ factor increase in time. See   (2) and (3). The reference seems to be (6).

  Is there any improvement on [HS66]? Can we simulate TMs on a two-tape TM for $f(n)$ steps in a faster way? Can we take $g(n)$ to be in $\omega(f(n))$ in place of $\omega(f(n)\lg f(n))$?

It seems that there hasn't been any improvement since that would imply a better time hierarchy theorem than currently known.

Correction: The usual hierarchy theorems are based on time complexity classes defined using single tape TMs. For $n$-tape TMs a tight result similar to the space hierarchy theorem is proven by Furer in 1982 (5). The $\lg$ factor is not needed. Also see (4).

References:

Peter van Emde Boas, "Machine Models and Simulation", in Handbook of Theoretical Computer Science, 1990
(in particular, pp. 18-21)
Michael Sipser, "Introduction to the Theory of Computation", 2006
(time complexity classes are defined using TMs with single-tape infinite in both directions and arbitrary finite alphabet, see pages 140 and 341)
Odifreddi , "Classical Recursion Theory", vol. I & II, 1989 & 1999
(definitions are similar to Sipser, see Def. I.4.1 in vol. I page 48, Def. VII.4.1 in vol. II page 67, and Thm. VII.4.15 in vol. II page 83)
Piergiorgio Odifreddi, "Classical Recursion Theory", vol. II, 1999
(page 84)
Martin Fürer, "The Tight Deterministic Time Hierarchy", 1982
Juris Hartmanis, "Computational Complexity of One-Tape Turing Machine Computations", 1968
F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", 1966
Other related questions:

Lower bounds and class separation,
Justification of $\lg f$ in DTIME hierarchy theorem,
Alphabet of single-tape Turing machine,
For the time hierarchy theorem, how is the input translated efficiently?,
a comment by Luca Trevisan.


About P2P networking In P2P(peer-to-peer) networking, it is possible for the server program(software) and the client program(software) to be running on the same computer.

So the two must have the same IP address.

I am confused about this. Is there nothing going wrong if both of them uses the same IP address?

Please clarify.

Sure.  That's fine.  Nothing wrong with that.  Transport-layer protocols (such as UDP or TCP) use port numbers so that you can run multiple applications on the same machine without any difficulty.


Proof: Sum of weights of paths in a network 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.

A few hints:

Find out what the entries of $A^2$ mean. How about $A^k$? (Start by a very small adjacency matrix, multiply it with itself and try to think what each entry means).
Lookup and understand the Taylor expansion of $f(x) = 1/(1-x)$.
Realize that the sum of weights of all paths from $s$ to $t$ is the sum of weights of paths of length 0, 1, 2, ...


Context-free grammar for"not-at-all" palindromes I need to bulid a context-free grammar for

$\qquad \mathscr{L_4}=\{w\in\{a,b,c\}^* \mid w\text{ is not palindrome at all}\}$

Not palindrom at all:
We will say that a word $w$ is not palindrome at all if for all $i$ such that $1\leq i\leq |w|$ the $i$ letter from the beginning of $w$ is not the same like the $i$ letter of $w$ from the end, for example $abbacb\in \mathscr{L_4}$ but $ca\color{gray}bba\color{gray}bcb\notin\mathscr{L_4}$, the word must contain a even number of digits, because if there were an odd number of digits, so the middle digit "equals to itself".

My attempt:
 Let's denote $S_{\text{pal}}$ from palindrome grammar and  $S_{\neg\text{pal}}$ for the not palindrome at all grammar

$$\\S_{\neg\text{pal}}\to a S_{\neg\text{pal}}b\big|bS_{\neg\text{pal}}a\big|aS_{\neg\text{pal}}c\big|cS_{\neg\text{pal}}a\big|cS_{\neg\text{pal}}b\big|cS_{\neg\text{pal}}b\big|\epsilon$$

Similar question here.
I'm not sure if my attempt is correct or not

Just use something like:

$
S \rightarrow a S b \mid a S c \mid b S a \mid b S c \mid c S a \mid c S b \mid a b \mid a c \mid b a \mid b c \mid c a \mid c b
$

This ensures the $i$-th symbol from the beginning is different from the $i$-th from the end.


Why is the class of recursively enumerable languages not closed under complementation? I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed under complementation?

Explanation also says,

  This fails because $M$ only needs to halt if $w \in L(M)$ - doesn't have to say "no".

What does it mean?

The statement you quote is an argument why the proof for showing that $\mathrm{R}$ (the set of recursive languages) is closed against complement does not work for $\mathrm{RE}$ (the set of recursively enumerable languages). It's not a proof of the reverse in itself -- another proof may still work!

The problem is that flipping the result of a TM only works if you get a result; $\mathrm{RE}$ promises only an acceptor, not a decider, which may loop if the input is not in the language. Therefore, you can not flip properly; all you'd get is a machine that says "no" of the word is not the language but loops otherwise. That's a machine for $\mathrm{co\text{-}RE}$, not $\mathrm{RE}$.

As for why $\mathrm{RE}$ is not closed against complement, the site you link contains all the answers; let me reiterate.

If $L$ and $\overline{L}$ are both semi-decidable, then both are decidable.
Hence, if $\mathrm{RE}$ was closed against complement, we'd have $\mathrm{R} = \mathrm{RE}$.
But we know that $\mathrm{R} \subsetneq \mathrm{RE}$ (by witness of the halting problem), so this can't be true.


What is Simultaneous Multithreading I come from an electronics background. I know that there are three types of implementations of multithreading (see Computer Architecture: A Quantitative Approach, 5th Edition):

Fine-grain multithreading issues instructions for different threads after every cycle.
Coarse-grain multithreading only switches to issue instructions from another thread when the current executing thread causes some long latency events (like page fault etc.)
Simultaneous multithreading issues multiple instructions from multiple threads in one cycle. The processor must be superscalar to do so.

Does that mean that SMT is an extension of fine-grain and coarse-grain multithreading, and fine-grain and coarse-grain multithreading are only suitable for single core processor?

What is the exact difference between SMT and the other approaches?

Hennessy and Patterson (Computer Architecture: A Quantitative Approach) use the term "multithreading" to refer to running more than one thread on a single core.

Their distinction between "fine-grain", "coarse-grain" and "simultaneous" involves different approaches for how the threads share the issue logic (the logic that moves instructions from the decode pipeline stage to the execute pipeline stage.)

In "coarse-grain multithreading" the issue stage will issue instructions from one thread for many cycles (dozens or hundreds) and then switch to issuing from another thread only when the first thread gets a cache miss or some other long-latency operation.

In "fine-grain multithreading" the issue stage can issue instructions from a different thread each cycle, but all the instructions issued together in a cycle must come from the same thread.

In "simultaneous multithreading" the issue stage can issue instructions from different threads in the same cycle.  The restriction is lifted that instructions issued together in the same cycle must come from the same thread.  The distinction between fine-grain multithreading and simultaneous multithreading only matters on machines that can simultaneously issue two or more instructions.


Infinite non-regular decompositions of regular languages The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular.
When is this the case?

Or, from a different perspective:
Given some regular language $L$, I want to find a family languages $(L_i)_{i \in \mathbb{N}}$ such that

$L_i \cap L_j = \emptyset$ whenever $i \neq j$
$\bigcup_{i \in \mathbb{N}} L_i = L$
$\forall i \in \mathbb{N}: L_i \notin \mathsf{REG}$

More specifically: When is such a decomposition possible (clearly, not every regular language is decomposable in this way, e.g. finite languages)?

A class of (motivating) examples is the following: Given some congruence relation $\sim$ on $\Sigma^\ast$ such that the elements of $\Sigma^\ast /\sim$ are non-regular, every language saturated by $\sim$ admits a decomposition as above. One such congruence is the congruence $\sim_R$ generated by the identities $\{a^2 \sim_R \lambda ~:~ a \in \Sigma\}$, assuming $|\Sigma| > 1$. An example for a language saturated by $\sim_R$ is the language consisting of words containing an even (odd) number of occurrences of some symbol from $\Sigma$. More generally, languages accepted by complete deterministic automata with symmetric transition relations (that is, $q\cdot aa = q$ for all states $q$ and symbols $a$) are saturated by $\sim_R$.

However, I fail to see some general criterion for a language being decomposable in this way.

Your intuition does not match mine, I think this is possible for every initial (infinite) regular language. My idea is that every infinite language has an (infinite) non-regular subset, such that the complement is also infinite. You then can repeatedly find the next language which together form a non-regular decomposition.

How to prove the basic observation? Just set half of the words apart (for the complement, the set of words is countable, so order them). In the remaining words you choose a subset that has ever greater sizes, not growing linearly but at least say exponential. Such a subset cannot be regular.

How do we obtain a decomposition that way: we might omit a string in each step. This is dealt by taking the shortest remaining string in the next language. That choice does not influence any regularity.


Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. More precisely, the algorithm should find an upper and a lower bound on the chromatic number. The closer the bounds are to the chromatic number, the better.
If it isn't clear, the input to the algorithm is a graph. The exact representation of a graph isn't fixed (that is, I will switch data structures if it makes sense).
I already know about Brooks' theorem, which gives an upper bound in linear time and constant space, but I'm hoping for something stronger.
Related Mathoverflow question: https://mathoverflow.net/questions/33812/lower-bounds-for-chromatic-number-of-a-graph

The result of Zuckermann tells you that the chromatic number of an $n$-vertex graph cannot be approximated in polynomial time to within $n^{1-\epsilon}$, for any $\epsilon > 0$ unless P = NP. In other words, the problem is extremely hard to approximate, so you won't find good theoretical algorithms for the problem.
However, if you care about a practical solution as you claim, i.e., you just want a solution that is computed in a short amount of time and the result is good, there are many things you can try. First, quite a bit depends on the actual instances you want to compute the chromatic number for - what do you know about their structure? For instance, are they sparse or dense?
There a many approaches to try out here. For starters, I would take some sample - representative as possible - of your instances, and see how far their chromatic number is from their clique number (i.e., the size of a maximum clique). Especially if your graphs are sparse, there are very good heuristics and exact solvers available for computing the clique number that can work even on billion-scale graphs. So that will give you a lower bound. If you want a decent algorithm for testing whether that is optimal, you can try a SAT solver. It's simple to map the graph coloring problem to an instance of SAT, and the solvers are highly practical.
Of course, you can also consider a metaheuristic for the problem, say a genetic algorithm or ant colony optimization. For any of these, you can also exploit the lower bound information given via the clique number or upper bound information given by e.g., the maximum degree.


are the activations of hidden nodes in an ANN binary or real valued? this may seem to be a pretty basic question, but it is something i have been puzzling over for some time.

when calculating the activations of nodes in a hidden layer in an ANN using sigmoid neurons for use with the backpropagation algorithm - should the output of the neuron be thresholded or not?

say the activation vector for layer $i$ is calculated by:

$\mathbf{a}_i = \sigma(\mathbf{w}_i\mathbf{a}_{i-1} + \mathbf{b}_i)$

where $\sigma$ is the sigmoid activation function

should it actually be:

$\mathbf{a}_i = (\sigma(\mathbf{w}_i\mathbf{a}_{i-1} + \mathbf{b}_i) > 0.5$)

to ensure that $\mathbf{a}_i$ is binary vector? or should the real value from $\sigma$ be passed on to the next layer?

my main reason for asking this is that biological neurons don't transmit real valued data, but i haven't really been able to find any definitive answer anywhere to this question or anyone who explicitly says to threshold the value; it seems like a pretty fundamental question to the functioning of ANNs, so either i am missing something in my reading, or it is considered so common-sense that it doesn't need to be mentioned much.

any help would be greatly appreciated

When you do thresholding your activation function becomes a step function. The problem with that is that step functions are not differentiable, so you would not be able to do basic gradient descent to learn the parameters. You can see the sigmoid as a continuous approximation of a step function.


Machine learning algorithm to play Connect Four I'm currently reading about machine learning and wondered how to apply it to playing Connect Four.

My current attempt is a simple multiclass classificator using a sigmoid function model and the one-vs-all method.

In my opinion, the input features have to be the state (disc of player 1, disc of player 2, empty) of the 7x6=42 grid fields.

The output would be the number of the row to put the disc into. Because that is a discrete number between 1 and 7, I guess this can be treated as a multiclass classification problem.

But how do I generate training examples usable in supervised learning?

The main goal is to win the game but the outcome obviously isn't known when doing every but the last turn.
If I just let two players who decide randomly what to do play against each other thousands of times, will it be sufficient to simply take all turns made by the winner of each game round as training examples? Or do I have to do this in a completly different way?

Edit: As suggested in the comments I read a little about reinforcement learning.
From what I know understand, Q-Learning should do the trick, i.e. I have to approximate a function Q of the current state and the action to take to be the maximum cumulative reward beginning in that state. Then each step would be to choose the action which results in the maximum value of Q. However, this game has way too many states in order to do this e.g. as a lookup table. So, what is an effective way to model this Q-Function?

Just to offer a simpler alternative to reinforcement learning, you can use the basic minimax algorithm to search for good moves, and use machine learning to evaluate board positions.

To clarify, minimax builds a game tree where each node is labeled with the outcome from the leaves up (1=player A wins, 0=player B wins), assuming that A chooses the moves that maximize this number, and B chooses the moves that minimize it.

Unless the game is very simple, you won't be able to construct the whole game tree down to the terminals. You'll instead need to stop at unfinished board positions and evaluate the leaves with some heuristic (essentially the probability that player A will win from the given position). You can let a machine learning algorithm like a neural network try to learn this probability from connect four positions with known outcomes.

To generate training examples you could build your minimax player with a simple heuristic, let it play itself a thousand times, use those games to train your first neural network, then let that pay itself a thousand games and so on. With a little luck, your system will improve with each generation.


NSPACE for checking if two graphs are isomorphic I was studying nondeterministic Turing Machines and came across the following question:

Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are isomorphic, and provide the NSPACE. The NTM should use as little space as possible.

My attempt at answering this question goes something like this:

If G1 and G2 have different no. of vertices and/or edges, reject
Nondeterministically reorder the vertices v1 thru vn in G1. Leave G2 alone.
Check if there is a bijection from G1 to G2, with the above vertex mapping. If so, accept.

At some point, the above algorithm will go thru all n! possible orderings of G1's vertices, and will exhaustively check to see if there's a bijection.

Not quite sure what the NSPACE() value is, though, or how I would go about computing it. My guess is that re-ordering G1's vertices v1 thru vn will take up n cells of the work tape, and checking every pair of vertices for bijection will require a small additional amount of space that can be reused for each subsequent pair? Or do we actually need to store all C(n, 2) pairs per graph?

This is all very confusing, and I'm unsure whether I'm thinking thru this problem the right way. I'd appreciate any help.

The algorithm you proposed can be made to work in $O(n \log n)$-space, where $n$ is number of vertices. While permuting the vertices of graph $G_1$, you can also keep the mapping and reverse mapping from and to original vertices. That way you need not rewrite the whole graph. And you can still check if a particular edge in $G_1$ maps to an edge in $G_2$ and vice-versa.

Also, planar graph isomorphism is log-space.


Complexity of Block edit distance with Swapping only Suppose I have distinct letters in an alphabet $\sum = \{a_1,a_2,...,a_n\}$. I also have two permutations of these letters, let's call them $A,B$. How can I find the Edit distance between $A$ and $B$ with block edit operations allowed?

To make it clearer, an example would be $\sum =\{a,b,c,d \}$. Two possible permutations are $A=``abcd",B=``dabc"$. The edit distance here would be $1$ because we can swap the block $``abc"$ with $``d"$ to get one string to the other.

Clearly, there won't be any deletions/insertions in this form of the problem, it will purely be swaps since the two strings are permutations of the same letters.

Now I know that the original edit-block problem with all operations is NP-Hard, however, would the restriction of only block swaps perhaps make this solvable in polynomial time? Most text I've read don't address this version and instead address variations of the original problem. Any help would be appreciated.

When one operation is exactly "removing a block and inserting it between two other positions", the problem of computing the string distance is known as Transposition Distance. It is NP-hard even if both input sequences are $p$-sequences, that is, if every letter occurs only once in each input sequence:

Laurent Bulteau, Guillaume Fertin, Irena Rusu:
Sorting by Transpositions Is Difficult. SIAM J. Discrete Math. 26(3): 1148-1180 (2012)


Proving that the language SPACE TMSAT is PSPACE-complete? I'm trying to prove that the language SPACE TMSAT (where SPACE TMSAT = {⟨$M$, $w$, $1^n$⟩ : DTM $M$ accepts $w$ in space $n$}) is PSPACE-complete.

My solution is as follows:
SPACE TMSAT $= \{<M,w,1^{n}> :$ DTM $M$ accepts $w$ in space $n\}$ can only be computed by running machine $M$ on $w$. As this forces the allowance of the computation of any PSPACE language, SPACE TMSAT is PSPACE-complete.

Does this solution make sense? Am I being too hand wavy? Any other suggestions or critiques? Thanks!

To prove that a problem $P$ is PSPACE-complete, you need to do two things:

Show that $P$ can be computed in PSPACE.
Show that every problem $Q \in $PSPACE reduces to $P$, in the sense that there exists a polytime function $f$ such that $f(x) \in P$ iff $x \in Q$.

As mentioned by dkuper, you forgot about the first part. Your argument for the second part (PSPACE-hardness) unfortunately does not constitute a proof. You need to follow the definition: given an arbitrary $Q \in $PSPACE, produce a polytime function $f$ such that $f(x) \in P$ iff $x \in Q$.

Apart from not being a proof, your argument is also not convincing: there could be some trick that avoids simulating $M$. Such tricks are behind results such as L=SL or NL=coNL in complexity theory. For example, the second result states that given a non-deterministic Turing machine $M$ that runs in logarithmic space, there is a  ways to decide non-deterministically in logarithmic space whether a given input is not accepted by $M$. The obvious way to do this is to run all possible execution paths of $M$, but since $M$ could make polynomially many non-deterministic decisions, that would require polynomial space (we need to keep track of all these decisions so that we can run through all of them). Yet there is a trick that enables us to do it non-deterministically using only logarithmic space.

Hint for the second part: Given $Q$, consider a Turing machine $M$ that computes $Q$ in space $O(n^k)$ for some $k$.


Is it possible to obtain dynamic tree with two dimensions in big matrix Let's say we have given matrix of size $n \cdot m$, such that both $n, m$ are big numbers and we cannot keep the whole matrix in memory (up to 10 millions).

In some of the coordinates of the matrix there are positive numbers and all other fields are zeroes (at most 100000 elements are with value different from 0). For each element we are keeping three values, the $x, y$ coordinate and the value of it.

How could we answer queries of type $q(i, j)$ to return the sum in the fields that are in the submatrix from $(0, 0) \text{ to } (i, j)$.

Is there way to create tree that will be able to answer such queries. Thanks in advance.

Yes.  Use a persistent data structure.  Build a tree data structure to answer queries of the form $q(i,0)$.  Then, advance $j$, updating the persistent tree data structure as you do.  This will build a data structure of size $k$ and let you answer queries in $O(\log k)$ time, where $k$ is the number of non-zero entries in the matrix.


Remove contiguous subsequence so the remaining numbers will created a sorted sequence You are given $N$ numbers. Remove contiguous subsequence of those numbers, so the remaining numbers will create a sorted sequence. For example, if the sequence is $5$, $7$, $8$, $2$, $1$, $9$ then we have to remove subsequence $2$, $1$. I am only interested in the minimal amount of numbers removed. If this task wasn't about removing contiguous subsequence, then I would find longest non-decreasing subsequence in O(n log n) and output $N$ - $L$, where $L$ is length of this subsequence.

This task was taken from an old programming competition. I am asking this question, because I'm practising and got really stuck on this one.

Let the original sequence be $a_1,\ldots,a_n$. After removing a contiguous subsequence $a_{i+1},\ldots,a_{j-1}$, we are left with $a_1,\ldots,a_i,a_j,\ldots,a_n$ (possibly $i = 0$ or $j = n+1$). In particular, if $a_1 \leq a_2 \leq \cdots \leq a_I > a_{I+1}$ then $i \leq I$, and if $a_{J-1} > a_J \leq a_{J+1} \leq \cdots \leq a_n$ then $j \geq J$. In other words, we can remove all elements $a_{J+1},\ldots,a_{I-1}$. Renaming elements, we are left with two non-decreasing sequences
$$a_1,\ldots,a_s,b_1,\ldots,b_t.$$
Merge both sequences, and consider all places in the merged sequence in which a $b$-element follows an $a$-element, say $a_i,b_j$. This corresponds to the sorted sequence $a_1,\ldots,a_i,b_j,\ldots,b_t$ of length $i+t-j+1$. Go over all such places and choose the one maximizing the length of the corresponding sequence. (You also need to consider some corner cases, which I leave to you.)

This algorithm runs in linear time, and so is asymptotically optimal.


Raft algorithm: What's the meaning of concept `index`? When reading the description of Raft algorithm from Wikipedia, I noticed there is a special word index.

For web developer, index usually refers to database index.

When it comes to Raft algorithm, what does index mean? Is it similar with database index? e.g. B+ tree.
What is raft index used for?

Wikipedia: Raft

  Log Matching: if two logs contain an entry with the same index and
  term, then the logs are identical in all entries up through the given
  index.

https://en.wikipedia.org/wiki/Raft_(computer_science)#Safety_rules_in_Raft

TL;DR Just as said by Yuval Filmus, a log index in Raft algorithm is just an integer that tells the position of a log entry in a series of log entries.

Here is a figure that show clearly the meaning of an index of a log entry in Raft algorithm. The figure is taken from the award-winning paper In Search of an Understandable
Consensus Algorithm by the creaters of Raft algorithm.

This usage of index is in accordance with the most common usage of index as in mathematics and computer programming, which is "a value that identifies and is used to locate a particular element within a data array or table" as said in its entry in dictionary.com. You can also check index notation.

Specifically, a log index in Raft algorithm is used by each server to identify the log entry that is numbered with that index in that server's log. All (indices for) committed log entries will always be consistent across all servers having those entries. Non-consistent (indices for) log entries across servers will be replicated or repaired, depending on the situations.

"For web developer, index usually refers to database index." It looks like that you come with a training in computer databases. As a web developer myself, I would not agree with you readily at all. Indices are used much more frequently to access array elements in everyday programming in just about every programming language. For example, in JavaScript, if there is an array persons=["alice", "bob", "Diego"], then we can use index 1 to access its second element "bob", persons[1]. You will find the same or similar usage that are also abundant in Java, C, C++, C#, Python, Ruby, Go, etc.

If you want to understand Raft algorithm, one of the best introductory material is the video presented by Diego Ongaro.


Is the language of Turing machines that calculate a given function $f$ in RE or coRE? For a function $f$, consider the language $$L=\{\langle M\rangle\mid M\text{ computes }f\}\,.$$

Where does the language above is and how do I prove it?
To me it seems that it's not in RE nor coRE but I struggle to prove so.
what I have so far is reduction from HP to $L$ as follows:

$$R(<M>,w) = <M'>$$
$$
Define \ M': \\ M(w) \\
\qquad \qquad \qquad Write \ x \ on \ the \ tape$$

$$ 1. \ Run \ M \ on \ W \\
   2.\ write \ x \ on \ the \ tape $$

But I can't prove that this language is in RE.

So how do I proceed from here ?

Below, we assume $f$ computable, otherwise $L$ is empty, so RE and coRE.

For the "RE" part

This can be done with reductions, but the easy way is to exploit the Rice-Shapiro theorem.

Now, take a set of partial recursive functions $F$ ($F=\{f\}$, in your case), and define $L$ to be the set of TMs that implement some function in $F$.
If $L$ happens to be in RE, then by Rice-Shapiro we must have

if $g\in F$ has infinite domain, some finite restriction of $g$ must belong to $F$ as well
if $g$ is non-total, every computable extension of $g$ must belong to $F$

Often, one of these cases is false, implying that $L$ was not RE (provided it has the form above).

In your case, $L$ can not be RE since $F$ only contains $f$: if $f$ has an infinite domain, 1) is violated, otherwise 2) is violated.

In both these cases, you can replace Rice-Shapiro by suitable reductions from the complement of the halting problem, but doing that you are essentially repeating the proof of Rice-Shapiro. It is still a nice exercise, though: one can define one reduction for each case.

Even more in general, $F$ can never be finite if $L$ is RE. But $F=\{f\}$ is finite.

For the "coRE" part

If $f$ is the always-undefined function, $L$ is coRE. Indeed, for $M$ to implement a different function from $f$, it is enough that $M$ halts on some input, which is a RE problem.

If $f$'s domain is nonempty, say $f(x)=y$, $L$ is not coRE. To prove that, it suffices to reduce the halting problem to $L$.
Given $M$, craft $M'$ which on input $w\neq x$ outputs $f(w)$. When $w=x$, instead, run $M$, and if that halts output $y$ (otherwise we diverge).


Points at distance $k$ or less in 2D grid How can we prove that the total number of mesh points k or fewer jumps away from an arbitrary point in a 2D mesh is: $2k^2 + 2k + 1$.

I tried making a $3 \times 3$ mesh.

     a --- b --- c
     |     |     |
     d --- e --- f
     |     |     |
     g --- h --- i

For point $e$, the number of points $k=1$ jump away is four: $b$, $d$, $f$, $h$.
But, according to the formula, it should be $2\times1^2 + 2\times1 + 1=5$.
I am stuck!

Read your question more carefully. The formula you give is for

  the total number of mesh points $k$ or fewer jumps away

(my emphasis).  And there are indeed five points one jump or fewer away from $e$: $b$, $d$, $f$, $h$ and $e$ itself.


Real life description for (~A->A)->A It can be shown that the logical preposition [ :- (~A->A)->A ] is a theorem (always true).
I want to know if anybody knows a real life description for the preposition above?
I mean an expression in computer, economics, mathematics, politics or anything that fits in that preposition.

Since $A$ is always the same atomic statement, every direkt translation is going to be weird. Also, natural language does not do well with (nested) implications; we typically say "leads to" not "logically implies" in reality.

I suggest you transform the formula to

$\qquad\begin{align*}
         &(\lnot A \to A) \to A \\
  \equiv &\lnot(\lnot A \to A) \lor A \\
  \equiv &\lnot(A \lor A) \lor A \\
  \equiv &\lnot A \lor A,
\end{align*}$

which is, of course, a tautology (as you've stated):

  You will help me, or you won't [, your choice].

Coming up with more complicated sentences won't give you more (logical) meaning -- all tautologies are equivalent (in Boolean logic), after all.


Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular Show that the following language $L$ is regular by describing it using a regular expression.
  $$L = \{1^n w 1^n \mid n > 0 \text{ and }w ∈ \{0,1\}^*\} $$

My (apparently incorrect) answer:

Given $w ∈ \{0,1\}^*$ , we can rewrite $L$ as:  $1^n(0\cup1)^*1^n\ for\ n ≥ 0$

However, since the language specifies that the number of leading and trailing $1$s must be the same - this language is not regular.

My justification:

For every regular language, there is (by definition) a finite automaton that accepts that language
The given language $L$ requires an equivalent count of leading and trailing $1$s
Finite automata are not capable of maintaining a count.

Since no finite automata can accept the language $L$, $L$ is not regular.

Can anyone explain to me why this language is regular?  I'm completely stumped.  I can see that it could be pumped using the Pumping Lemma (thereby proving regularity), but my brain just refuses to recognize that an FSM could accept this language.

My answer is just a hint. The following pattern should lead you to the right answer:

These strings belong to the language:
$w = 11 \Rightarrow 1^1\epsilon 1^1, n=1$
$w = 1011 \Rightarrow 1^1(01) 1^1, n=1$
$w = 11011 \Rightarrow 1^1(101) 1^1, n=1$ or $1^2(101) 1^2, n=2$
$w = 1001011 \Rightarrow 1^1(00101) 1^1, n=1$
$w = 11111 \Rightarrow 1^1(111) 1^1, n=1$ or $1^2(1) 1^2, n=2$
$w = 101010011 \Rightarrow 1^1 (0101001) 1^1, n=1$
$\cdots$
Finally, if $w=1^nw 1^n$ then it can be written as $1v1$, where $w,v \in (0+1)^*$.

These strings DO NOT belong to the language:
$w=0$
$w=01$
$w=100$
$w=0000$
$w=0001$
$w=1000010$
$\cdots$

Yo may want to look at the first and the last symbols of each string.


Complexity of finding a majority element I was given a question that is stated that;

  Suppose you’re consulting for a bank that’s concerned about fraud
  detection, and they come to you with the following problem. They have
  a collection of n bank cards that they’ve confiscated, suspecting them
  of being used in fraud. Each bank card is a small plastic object,
  containing a magnetic stripe with some encrypted data, and it
  corresponds to a unique account in the bank. Each account can have
  many bank cards corresponding to it, and we’ll say that two bank cards
  are equivalent if they correspond to the same account. It’s very
  difficult to read the account number of a bank card directly, but the
  bank has 1 a high-tech ‘equivalence tester’ that takes two bank cards
  and, after performing some computations, determines whether they are
  equivalent. Their question is the following: among the collection of n
  cards, is there a set of more than n/2 of them that are all equivalent
  to one another? Assume that the only feasible operations you can do
  with the cards are to pick two of them and plug them into the
  equivalence tester. Show how to decide the answer to their question
  with only O(nlog n) invocations of the equivalence tester.

I proposed an algo for this problem that is like this;

  For the equivalent majority there must be majority of the equivalent
  cards on one side of the n cards if we divide them into two halves. So
  one of the two sides must return one card that has majority more than
  n/2 in whole list.

  Let’s say equivalentTest is the function that takes two bank cards
  and, after performing some computations, determines whether they are
  equivalent.

Function checkMajority(c, M)
    i = count = 0
    While i less than length of M:
        if (M[i] is not actual c) and (equivalentTest(M[i], c) == true) then:
            count ++
        Endif
    Endwhil
    If count is greater than half the length of M then:
        Return true
    Else
        Return false
    Endif

Function divide_and_find(M)
    If M.length = 1
        Return M[0]
    Else if M.length = 2
        If equivalentTest(M[0], M[1]) == true
            Return M[0] or M[1]
    Divide M
    M1 = assign first half
    M2 = assign second half
    c = divide_and_find(M1)
    if c is returned then
        found = checkMajority(c, M)
        If found = true then
            Return c
        Else
            c = divide_and_find(M2)
            found = checkMajority(c, M)
            If found = true then
                Return c
            Else
                Return ‘not found’
            Endif
        Endif
    Endif
    Return ‘not found’

According to my understanding,

  The algorithm complexity is O(nlogn) because we have used divide and
  conquer strategy. There would be (logn) steps and each step would take
  O(n) time for checking the majority. So the complexity would be
  O(nlogn)

But at the same time, I think it will take O(n*n).. that is big O of n square, In worst case scenario. Because then it will check n cards for n cards, to find duplicate cards.

Can any one help me out in resolving my confusion??

Let us denote the running time of your algorithm on arrays of size $n$ by $T(n)$. Then
$$
T(n) = \begin{cases}
T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n), & \text{if } n > 2, \\
O(1), & \text{if } n \leq 2.
\end{cases}
$$
The master theorem now shows that $T(n) = O(n\log n)$.

Here is an $O(n)$ algorithm:

find-majority-element(A):
  n = len(A)
  if n = 0:
    return "none"
  if n is odd:
    y = last element of A
    if y is a majority element:
      return y
    A' = A with last element removed
    x = find-majority-element(A')
    if x is a majority element:
      return x
    otherwise:
      return "none"
  partition A into m = n/2 pairs (a_1,b_1),...,(a_m,b_m)
  construct an array B consisting of all a_i such that a_i = b_i
  x = find-majority-element(B)
  if x is a majority element:
    return x
  otherwise:
    return "none"

Clearly if there is no majority element, the algorithm returns "none". Now suppose that $x$ is a majority element. We will show that the algorithm returns $x$. We will do this by proving the following claim by induction on $n=\mathrm{len}(A)$:

  If $A$ contains a majority element $x$, then find-majority-element($A$) returns $x$.

Suppose first that $n=2m+1$ is odd, so that $x$ appears at least $m+1$ times. If $x$ is the last element, then find-majority-element($A$) will return it. Otherwise, $x$ is a majority element of $A'$ as well, and so find-majority-element($A'$) will return $x$, causing find-majority-element($A$) to return it as well.

We can now assume that $n = 2m$ is even. Suppose that $B$ contains $k$ many $x$'s and $\ell$ many other elements. We can upper-bound the number of copies of $x$ in $A$ by $2k + (n-2k-2\ell)/2 = m + k - \ell$. On the other hand, the number of copies is at least $m+1$, and so $k > \ell$. In other words, $x$ is a majority element in $B$ as well. Therefore find-majority-element($B$) will return $x$, causing `find-majority-element($A$) to return it as well.

Denoting by $T(n)$ the maximum running time of the procedure on arrays of length at most $n$, we get the recurrence
$$
T(n) \leq \begin{cases}
O(1), & \text{if } n = 0, \\
T(n-1) + O(n), & \text{if $n$ is odd}, \\
T(n/2) + O(n), & \text{if $n$ is even},
\end{cases}
$$
whose solution is $T(n) = O(n)$.


Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$ In the sources I consulted it states that in the Baum Welch algorithm the reestimate of the initial probability of state $i$ of the HMM is $\pi^*_i = \gamma_i(1)$. But $\gamma_i(t)$ is the probability of being in state ${\displaystyle i}$ at time ${\displaystyle t}$ given the observed sequence ${\displaystyle Y}$ and the parameters ${\displaystyle \theta }$ (quote wiki)

So, then why does this probability not need to be normalised like so? :

$$\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$$

After all normalizing is what is done for the reestimate of the transition probabilities and the emission probabilities too.

It is defined to be a probability.  A probability is by definition already normalized.  In particular, we are guaranteed that

$$\sum_{j=1}^N \gamma_j(1) = 1,$$

as there are only $N$ possibilities for the state that you're in at time $1$, and these $N$ cases have no overlap.