Is there a polynomial algorithm for optimal sorting on trees? There's the classical problem of sorting numbers in a list with the restriction that you can only swap two neighbouring numbers. It's easy to see that getting an optimal number of needed swaps can be achieved by insertion sort or bubble sort.

We can generalize this problem by changing the underlying structure from a list to a graph. Instead of swapping neighbouring numbers in a list we would be swapping numbers connected by an edge. Formally let's have a graph G=(V, E) with V = {1, ..., N} and an assignment of values f: V -> {1, ..., N} where f is a bijection/permutation. In order to do a swap we select an edge {u, v} from E and switch f(u) with f(v). Our goal is to sort f (that is achieve a state when f is the identity) in the least number of swaps. My question is whether there is a (polynomial) algorithm for this.

Since working on general graphs seems really difficult from what I've tried let's restrict ourselves to G being a tree. This should be a simpler question because each number has a clear path to its target.

Some observations:

When G is a path graph the problem is the same as sorting a list which is simple.

When G is a complete graph the problem is also simple since we only need to decompose each cycle into transpositions. You can actually look at the general problem as decomposing a permutation into as few transpositions as possible with the restriction of which transpositions you are allowed to use.

As long as the graph is connected there's a lower bound of "sum of all distances to targets"/2 because each swap decreases the distance to target of at most two numbers. The upper bound is "sum of all distances to targets" because we can select a number that wants to be in a non-articulation vertex (or simply leaf in trees) and drag it there. Then we can forget about this vertex and reduce the problem to a smaller graph.

This problem is called Token Swapping, and you can find more information if you search by its name on google.

I couldn't find a proof that it is NP-complete on trees, but I've found a recent paper that gives a 2-approximation algorithm for trees:
http://erikdemaine.org/papers/TokenReconfiguration_FUN2014/paper.pdf


Why there is forward chaining inference engine (reasoner) for description logics only and not for other logics? Reasoner is forward chaining inference engine (https://en.wikipedia.org/wiki/Semantic_reasoner) as opposite to Prolog backward chaining SAT solver (for queries). Why there is reasoner for description logics and not for other logics?

This question is a bit strange. I see it's based on the Wikipedia article, but that article is also a bit strange. I will try to clarify some concepts.

First, we have a language that can be used to make claims whose meaning are formally defined. Such a language may allow us to say, for example, that if $x$ is a Person, then $x$ is a Human, which can be done in first order logic as $\forall x (\neg\mathsf{Person}(x) \vee\mathsf{Human}(x))$, in a rule language like Datalog as $\mathsf{Person}(x) \rightarrow
\mathsf{Human}(x)$, in description logics as $\mathsf{Person} \sqsubseteq \mathsf{Human}$ and so forth.

Second, we have semantics, which formally defines the meaning of claims in the language. One way in which the semantics of a language can be defined is using model theory, which essentially maps terms in the language to sets, elements, and relations between sets; for example, we can map the term $\mathsf{Person}$ to a (hypothetical) set $P$ and $\mathsf{Human}$ to a (hypothetical) set $H$, and define the above claims as formally meaning $P \subseteq H$. This gives rise to the notion of models, where for example, $P := \{ \mathrm{Fred}, \mathrm{Jill} \}$ and $H := \{ \mathrm{Fred}, \mathrm{Jill}, \mathrm{Tom} \}$ is a model satisfying a given set of formal claims (since $P \subseteq H$), while $P := \{ \mathrm{Fred}, \mathrm{Tom} \}$ and $H := \{ \mathrm{Fred}, \mathrm{Jill} \}$ is not a model (since $P \not\subseteq Q$). In turn, models give rise to entailment between sets of formal claims, where for example, given $\{ \mathsf{Person}(\mathrm{Tom}), \mathsf{Person} \sqsubseteq \mathsf{Human} \}$ (in whatever language), we know this entails $\{ \mathsf{Human}(\mathrm{Tom}) \}$ as any model of the former set of claims must be a model of the latter set of claims.

Third, we have reasoning procedures to decide entailment. One way in which this is done is to use inference rules. For example, we may derive a rule such as $(\mathsf{C} \sqsubseteq \mathsf{D} \wedge \mathsf{C}(x)) \rightarrow
\mathsf{D}(x)$ to support reasoning with respect to the $\sqsubseteq$ operator in description logics. This rule may be applied for forward-chaining or backward-chaining. But there are many forms of reasoning procedures suitable for different types of languages; for example, for more expressive description logics, (a finite set of Horn) rules is not sufficient to guarantee complete reasoning, and so tableau-based methods are often used. Also one reasoning procedure can be useful for reasoning in different languages, where Datalog, for example, is natively based on rules.

Returning to the question:

  Reasoner is forward chaining inference engine (https://en.wikipedia.org/wiki/Semantic_reasoner) as opposite to Prolog backward chaining SAT solver (for queries).

A "reasoner" can adopt multiple strategies, including, but not limited to, forward-chaining on rules. Engines that apply tableau-based methods, backward chaining, resolution, etc., are also "reasoners". (The article you base the question on never claims that reasoners are forward chaining rule engines, but mentions this as one strategy.)

  Why there is reasoner for description logics and not for other logics?

There are reasoners for other logics. For example, Vampire is a reasoner for first-order logic, XSB is a reasoner for Prolog, or just check here for a list of different reasoners for different languages.


Shortest paths among two subsets of nodes Given a directed graph $G = (V, E)$ with all edge weights being non-negative and two disjoint subsets of nodes $S, T \subseteq V$, design an algorithm to find the shortest paths among $S$ and $T$, (formally, $\min\{d(s,t): s \in S, t \in T\}$) in $O(m \log n)$ time, where $|V| = n$ and $|E| = m$.

Note: The first version of my problem is to find all $d(s,t)$ for each $s \in S$ and $t \in T$. As @D.W. argues, it is not likely to do this in $O(m \log n)$ time because taking $S, T = V$ requires all pairs shortest paths. For $\min\{d(s,t): s \in S, t \in T\}$, however, the following method of "adding extra nodes" works:

Add an extra node $s_0$ and add edges of weights 0 from $s_0$ to each node in $S$
Add an extra node $t_0$ and add edges of weights 0 from each node in $T$ to $t_0$
Find the shortest path from $s_0$ to $t_0$.


I'm looking for a construct that is to semantic-analysis what NFA/DFA are to scanning and DPDA is to parsing What maps to Semantic Analysis the way automata like Finite State Machines and Pushdown automatons map to Lexing and Parsing?

A couple of years ago I came across a paper that presented such a construct; I don't remember much about the paper to be useful, but here's what I think I remember:

I think the paper was from the late 80s or early 90s,
The construct had/employed a double-ended queue,
Elements were replaced in the queue until the replacement rules could no longer be applied [and replacements were longer sequences than what they replaced],
The paper mentioned that while it mapped to the Semantic Analysis, it was somewhat unwieldy to use.

Any help locating this paper would be most welcome, as would info on other constructs mapping to Semantic Analysis.

Thank you.

Repeated substring string replacement is Turing complete.

To emulate a Turing machine you can use the following:

The current string encodes the tape with a new symbol $\$$ followed by an encoding of the current state inserted before the position where the current head is. The allowed replacements can be encoded by taking each transition $\delta(n, b) = (m, c, N|L|R)$ by creating the replacement rules to replace $a\$nb$ with $a\$mc$ $\$mac$ or $ac\$m$ for not moving the head or moving it left or right where a is every symbol in the alphabet.


when can i detect the position of error in hamming code I have 4-bit data with the hamming code 0010011.
the parity parameters are: p1=0 , p2=0 , p3=0
and the check codes are: c1 = 0 , c2 = 1 , c3 = 0
so I thought that I have an error in position 2 of my data but the solution says that I can not detect the position of the error.
my question is: when I can find the position of an error in hamming code?

You can never detect the positions of errors with certainty.

You can make the assumption that there is at most a single bit error. Under that assumption, if your code is not a valid code, you can find all different data where the hamming code differs from your code in only one bit position; if there is exactly one such data then you know where the error is (under your assumption).

You can make the assumption that there is at most a double bit error. Under that assumption, if your code is not a valid code, you can find all different data where the hamming code differs from your code in at most two bit positions; if there is exactly one such data then you know where the error or errors are (under your assumption).


Finding the $k$th largest element in an unsorted array What is the complexity of finding the k'th largest element in an unsorted linked list? If we sort the list, I think that the complexity is O(nlogn + k)=O(nlogn) since k < n. Is there a way of finding the kth largest element without sorting the list?

Yes, there is. Selection algorithm. There are two versions: running in worst-case linear time, and in expected linear time (see Cormen's chapter 9).
You can also implement this algorithm to run in sublinear time using data structures.


What algorithm to find end state probabilities I need help identifying what algorithm I need to solve a problem. I'm not asking for programming help here, just identifying the algorithm.

Each row of a matrix represents a state. Each element corresponds to the count of how often the current state transitions to another state. Some states are final states and do not transition at all. Some states are not reachable. There is always at least one path to one of the final states.

I need to calculate the probability of reaching all of the reachable final states and the probability for each final state.

To make this explicit here is an example of what I'm trying to accomplish.

State matrix:
$$
\begin{bmatrix}
0& 1& 0& 0& 0& 1 \\
4& 0& 3& 2& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0
\end{bmatrix}
$$

First state is always 0.
State 1 is non-terminal.
State 2 has probability of 0.
State 3 has probability of 3/14.
State 4 has probability of 2/14 or 1/7.
State 5 has probability of 9/14.

If this is a stationary distribution, then that's what I need to code to solve the problem. If not is it something else.

Take your matrix, and normalize the rows to sum to 1. Denote the result by $A$; in your example,
$$
A =
\begin{bmatrix}
0& 1/2& 0& 0& 0& 1/2 \\
4/9& 0& 1/3& 2/9& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0
\end{bmatrix}
$$
Let $v$ be a row vector with $v_0 = 1$ and $v_i = 0$ otherwise. In your example,
$$
v = \begin{bmatrix} 1&0&0&0&0&0 \end{bmatrix}
$$
Then $vA^t$ gives the probabilities of being in each state after $t$ steps, and so $w := v \sum_{t=0}^\infty A^t$ gives the expected number of times in each state. Since a final state terminates the process, for each final state $i$, $w_i$ is in fact the probability of the process ending at $i$. The vector $w$ can be calculated using the formula
$$
w = v (I-A)^{-1}.
$$
In your case, we get
$$
w = \begin{bmatrix} 9/7 & 9/14 & 3/14 & 1/7 & 0 & 9/14 \end{bmatrix}
$$
In particular, the probabilities of terminating at the final states $2,3,4,5$ are (respectively) $3/14,1/7,0,9/14$.

Regarding algorithms, we can rephrase the problem as follows: given $v,A$, find the vector $w$ such that
$$
w(I-A) = v.
$$
This requires solving a system of linear equations, for which there are many algorithms.


Average number of exchanges during first partition stage in Quicksort I am trying to understand average no of exchanges in Quicksort.
Here is the code to partition the array -
 private static int partition(double[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        double v = a[lo];
        while (true) {

            // find item on lo to swap
            while (less(a[++i], v))
                if (i == hi) break;

            // find item on hi to swap
            while (less(v, a[--j]))
                if (j == lo) break;      // redundant since a[lo] acts as sentinel

            // check if pointers cross
            if (i >= j) break;

            exch(a, i, j);
        }

        // put v = a[j] into position
        exch(a, lo, j);

        // with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
        return j;
    }

To start with in first partition stage -
There are total comparisons as below $ C_N= N +1 $
so exchanges in worst case should be  $ \frac{N}{2} - 1 $
But am not able to deduce number of exchanges in first partition
stage which is  $ \frac{(N-2)}{6} $
can someone explain how to deduce this?

The partition method in the question, partition(a, lo, hi) is called Hoare’s partition scheme, which is the most classic partition scheme used in quicksort.
Here is the situation. There are $n$ numbers that are non-equal pairwise. Array $a=(a_0, a_1, \cdots, a_{n-1})$ is a uniformly-random permutation of those $n$ numbers. We will run the method partition(a, 0, n-1). What is the number of exchanges executed inside the loop while(true)? (Note that the exchange exch(a, lo, j) outside the loop is not counted.)
WLOG, let the $n$ numbers be $1, 2, \cdots, n$.
Suppose the first element of $a$ is $p$ (for pivot). Excluding that first element, split $a$ into one segment of $p-1$ numbers followed by another segment of $n-p$ numbers.
$$a = (p,\ \underbrace{a_1,\ a_2,\ \cdots,\ a_{p-1},}_{p-1\text{ numbers}}\ \ \underbrace{a_p,\ a_{p+1},\ \cdots\ a_{n-1}}_{n-p\text{ numbers}})$$
Observe the number of elements greater than $p$ in the front segment is always the same as the number of elements smaller than $p$ in the back segment. (Proof: let the two numbers be $x$ and $y$ respectively. The total number of elements greater than $p$ in $a$ is $x + ( n-p-y)$. On the other hand, the total number of numbers greater than $p$, which are $p+1, p+2, \cdots, n$, is $n-p$. That means, $x+(n-p-y)=n-p$, which means $x=y$.)
In the while loop of partition(a, 0, n-1), the first element greater than $p$ in the front segment is exchanged with the last element smaller than $p$ in the back segment. Then the second element greater than $p$ in the front segment is exchanged with the second last element smaller than $p$ in the back segment. And so on, until we have exhausted elements greater than $p$ in the front segment (and, in the meantime, we have exhausted elements smaller than $p$ in the back segment as well). So the number of exchanges made is equal to the number of elements greater than $p$ in the front segment.
To calculate the average number of exchanges made, let us run partition(a, 0, n-1) as $a$ ranges over all permutations of $1, 2, \cdots, n$. Then
$$\text{total number of exchanges}=\sum_{p=1}^n\sum_{a_0=p}\text{number of exchanges on }a\\
=\sum_{p=1}^n\sum_{x}^{}x\cdot(\text{number of permutations that starts with }p\text{
 with }x\text{ exchanges performed})$$
As we have explained above, for a permutation that starts with $p$, $x$ exchanges will be performed on it if and only if that permutation has $x$ elements greater than $p$ in its front segment of $p-1$ elements. The number of such kind of permutations is the product of the following four factors.
$$
\underbrace{\binom{n-p}{x}}_{\text{the number of ways to choose }\quad\ \  \\x\text{ elements out of all }n-p\\\text{numbers that are greater than }\ \\p \text{ for the front segment}}
\underbrace{\binom{p-1}{p-1-x}}_{\text{the number of ways to chose }\\p-1-x\text{ elements out of all}\\p-1 \text{ numbers that are smaller }\quad\ \ \\\text{than }p\text{ for the front segment}}
\underbrace{(p-1)!}_{\text{the number of ways}\\\text{to permute all }p-1\\\text{elements in the}\\\text{front segment}}\quad\ \
\underbrace{(n-p)!}_{\text{the number of ways}\\\text{to permute all }\\n-p\text{ elements in}\\\text{the back segment}}\\
$$
So,
$$\begin{aligned}&\quad\text{total number of exchanges}\\
&=\sum_{p=1}^n\sum_{x=0}^{\min(n-p, p-1)}x\binom{n-p}{x}\binom{p-1}{p-1-x}(p-1)!(n-p)!\\
&=\sum_{p=1}^n\left((p-1)!(n-p)!\sum_{x=0}^{\min(n-p, p-1)}x\binom{n-p}{x}\binom{p-1}{p-1-x}\right)\\
&=\sum_{p=1}^n\left((p-1)!(n-p)!\sum_{x=1}^{\min(n-p, p-1)}(n-p)\binom{n-p-1}{x-1}\binom{p-1}{p-1-x}\right)\\
&=\sum_{p=1}^n\left((p-1)!(n-p)!(n-p)\sum_{y=0}^{\min(n-p-1, p-2)}\binom{n-p-1}{y}\binom{p-1}{p-2-y}\right)\\
&\stackrel{\bigstar}{=}\sum_{p=1}^n(p-1)!(n-p)!(n-p)\binom{n-2}{p-2}\\
&=\sum_{p=1}^n(p-1)(n-p)(n-2)!\\
&=(n-2)!\left((n+1)\sum_{p=1}^np-\sum_{p=1}^nn-\sum_{p=1}^np^2\right)\\
&=(n-2)!\left((n+1)\frac{n(n+1)}2-n^2-\frac{n(n+1)(2n+1)}6\right)\\
&=n-2)!\,\frac{n(n-1)(n-2)}6=n!\,\frac{n-2}6.\\
\end{aligned}$$
The average number of exchanges is
$$\frac{\text{total number of exchanges}}{\text{number of permutations}}
=\frac n6-\frac13 \color{#d0d0d0}{\quad\text{for } n\ge2}.$$

You might wonder the equality above that is marked with a $\bigstar$. It can be established by splitting into two cases, when $n-p-1\lt p-2$ and when $n-p-1\ge p-2$, and then using Vandermonde's identity.

Another way to prove it uniformly is to rewrite the Vandermonde's identity as, for any
non-negative integer $m, n, k$,
$$\sum_{r=-\infty}^{\infty}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r},$$
where we extend the definition of the binomial coefficient $\binom nk$ so that for all $n\ge0$ we have $\binom nk=0$ for all $k\lt 0$ or $k\gt n$. Note that the summation on the left-hand-side ranges is well-defined, since it contains, in fact, only finitely many non-zero items. We have,
$$\sum_{y=0}^{\min(n-p-1, p-2)}\binom{n-p-1}{y}\binom{p-1}{p-2-y}=\sum_{y=-\infty}^{\infty}\binom{n-p-1}{y}\binom{p-1}{p-2-y}\\=\binom{(n-p-1)+(p-1)}{y+(p-2-y)}=\binom{n-2}{p-2}.$$


Context-free grammar for $a^ib^ic^id^{3i}$ I'm trying  to make a context-free grammar for $L=\{a^ib^ic^id^{3i}\mid i>0\}$.
I could make a grammar for $a^ib^jc^jd^{3i}$. But I can't make the grammar for the special case that $i=j$ as it is in $L$.

You can use the pumping lemma to show that this language is not context-free.
Suppose it is context-free and let $n$ be the constant of the pumping lemma. Consider the word $u = a^nb^nc^nd^{3n}$. $u$ can be written $u = vwxyz$ with:

$|wxy| \leq n$
$|wy| > 0$
$\forall k \in \mathbb{N}, vw^kxy^kz\in L$.

Now using the first condition, $wxy$ can be written with at most two letters from the initial four. You can take it from here to find a contradiction.


Why do we need/use operator precedence for Arithmetic operators? Why do we use operator precedence rule for Arithmatic operators? Can't we simply just do the operation in a linear manner from left to right or vice-versa and deal with the operator that comes first.
For e.g. 2+3*4 = (2+3)*4 , if we do the operation from left to right.

My guess why we might do it is that, since * and / (divide and multiply) are complicated and gets even more complicated if the operands are larger, whereas + and - (plus and subtract) are simple operations.

As you note, there is no need for operator precedence. There are a number of other conventions that have been used in various contexts. A few programming languages have implemented the left-to-right convention you mention in the question, and a larger number have avoided the problem entirely by using Polish notation or its reverse.

The purpose of operator precedence conventions is to reduce the number of parentheses that are required to unambiguously communicate ideas that occur in practical mathematical usage. The most important rules—that multiplication has a higher precedence than addition, and exponentiation has a higher precedence than multiplication—exist primarily for the convenience of writing polynomials. Without these rules, polynomial expressions would require far more parentheses. Polynomials are so central to mathematical practice that they bleed into the notation, in operator precedence and elsewhere.

Rules for operator precedence beyond the basic arithmetic and relational ($=$, $\leq$, etc.) operators are domain-specific, and authors of papers occasionally have to specify the convention they are using in their notation section. Again, the purpose of having such rules is to improve communication in situations where specifying a convention that the reader has to remember is better than writing parentheses everywhere.

When precedence rules are standardized across an entire mathematical field, it is often because the rules have a clear analogy to arithmetic or relational operators on numbers. For example, concatenation has a higher precedence than union in regular expressions because the regular languages form a semiring, just like all your favorite number systems, and regular expressions are polynomial expressions in this semiring.


converting for loop into mathematical notation I am a bit confused with a problem that I am having.I am trying to do an amoritized analysis and I am able to represent the function that I want to use using code. I coded the function as follows:

sum = 1;
for(i = 1;i < n;i++){
    sum = ceil(1.5 * sum);
}

The code is suppose to represent $\lceil....\lceil\lceil\lceil1.5 \times 1\rceil\times 1.5\rceil\times1.5\rceil...\times1.5\rceil$ and is suppose to keep going $n$ times. How would I represent this mathematically.

Thanks.

Edit: So I am trying to do an amoritized analysis on an array that grows by a factor of 1.5. So what I am trying to do is mathematically write what the code does.

What the code is suppose to represent is it is doing $\lceil...\lceil\lceil 1.5 \times 1\rceil \times 1.5\rceil...\times1.5\rceil$ The ... is suppose to represent the function multiplying by 1.5 $n$ times.

Also as an example if you post the following into desmos it will give you ceil(...ceil(ceil(1.5 * 1))...) 8 times.

\operatorname{ceil}\left(\operatorname{ceil}\left(\operatorname{ceil}\left(\operatorname{ceil}\left(1\cdot1.5\right)\cdot1.5\right)\cdot1.5\right)\cdot1.5\right)

I want to be able to have the behaviour of what is represented above mathematically so I can use it in an analysis. If anything is unclear again please comment.

Is the sequence $(a_i)_{i<n}$, where $a_0=1$ and $a_{i+1}=\lceil 1,5\cdot a_i\rceil$, what you need?


Upper bound for the union of $n$ DFAs of size at most $m$? Let $\Sigma$ be an alphabet of size $2$, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ minimal DFAs $D_i$ whose size are bounded by $m$. As the number $k$ of minimal DFAs of size at most $m$ is finite, there exists a function $f$ that returns this number $k=f(m)$.

Let $L \subseteq \Sigma^*$ be the language resulting from the union of the $n$ regular languages $L_i$.

Is the size of the smallest DFA $D_L$ recognizing $L$ always below $m^{f(m)}$ ?

And if so, how can we find a precise definition/close-form of $f(m)$ ?

My intuition is as follows : the size of a DFA resulting from the union of two DFAs $A$ and $B$ is not greater than $|A|.|B|$. Thus, if there are not more than $f(m)$ minimal DFAs of size at most $m$ then the size of the minimal DFA for the union of the $D_i$ can not exceed $m^{f(m)}$. Sounds correct ?

Considering that for $|\Sigma|=2$ the transition function of a DFA of size at most $m$ is a graph. Since the nodes degree is bounded by $2$, for each node there are $m^2$ possibilities of pairs of arcs. In this graph there are at most $m$ possible choices of initial state and at most $2^m$ possible choices of final states sets. Thus, the maximum number of DFAs of size at most $m$ is $f(m) \leq m^{2m}.m.2^m = 2^m.m^{2m+1}$.

Thus we can conclude that for $|\Sigma|=2$ the maximal number of states required for the union of $n$ DFAs of size at most $m$ is bounded by $m^{f(m)} = m^{2^m.m^{2m+1}}$.

We can then generalize to an arbitrary alphabet $\Sigma$ : the bound becomes $f(m) \le 2^m.m^{|\Sigma|m+1}$. But it looks like this bound could be tighter though...

Does someone have a better estimate ?

One motivation to find a tighter bound is that if we fix the amount $S$ (in number of states) of memory that is available on a computer then we could easily get the maximal size $m$ that the $n$ DFAs must not exceed in order to guarantee the complete computation of the minimal DFA $D_L$ for the union of the $n$ DFAs.

I would appreciate if possible, some papers related to this problem or a proof/counter-example.

Many thanks, Luz

Yes.  There is a simple proof.

You say that $L_i$ are recognized by DFAs of size $\le m$, and that there are at most $f(m)$ possible such DFAs.  Therefore, there are at most $f(m)$ possible such languages.  If $n \ge f(m)$, then $L_1,\dots,L_n$ must contain some repetitions (some language appears multiple times).  Remove all repeated instances, so the $L_i$ are unique.  Then at that point we have $n \le f(m)$.  In other words, without loss of generality we can assume $n \le f(m)$.

Now the union of $n$ such languages can be recognized by a DFA of size at most $m^n$ (by a product construction), and $n \le f(m)$, so the union of $n$ such languages can be recognized by a DFA of size at most $m^{f(m)}$.


Computing with the Monster The Monster M is the largest of the finite sporadic groups that arises in the classification of finite, simple groups in mathematics.

M can be realized as a (very large!) set of 196882 X 196882 matrices with nothing more than entries of 1's and 0's, so long as we compute arithmetic as follows:

1+1=0
1+0=1+0=1
1*1=1
0*0=0
1*0=0*1=0

I have two simple questions for the reader. What is the minimum amount of bytes needed to store a single matrix? What is the computational cost (i.e., in FLOPS) of a single matrix multiplication in the most efficient implementation (i.e., taking into account that the entries are binary, not taking into account mathematical properties about the Monster)?

This is a question purely at the computational side of the problem. In other words, treat the matrices as general 196882 x 196882 matrices with binary entries. This is not a question about the Monster. That was just added as motivation.

If you are storing a matrix of 0's and 1's, you could consider using a bitvector for storage. This can pack some fixed number of bits (say, 32 bits or 64 bits) into a single integer, which decreases the required storage by a very large factor. In your case, your matrices need a total of 38,762,521,924 entries, so you'll need at least 4,845,315,241 bytes, or about 4GB, of storage per matrix. Since the Monster group has size about 8 × 1053, though, I seriously doubt you can fit everything into memory.

Another note: the arithmetic you're describing happens to have the plus operator defined as binary XOR and the multiplication operator defined as bitwise AND. Therefore, you could, in a language like C or C++, use the ^ operator to denote addition and the & operator to denote multiplication.

Finally, the complexity of multiplication depends on the matrix multiplication implementation. The naive method takes time O(n3), where n is the dimension of the matrix, but since the matrices are large you could probably use either the Strassen algorithm (time complexity about O(n2.8)) or Coppersmith-Winograd, the latter of which requires about O(n2.37) multiplications. You'd probably have to empirically profile these algorithms to see which is best, since the constant factors hidden here are pretty huge.

Hope this helps!


Asymptotics of a recurrence defined with two variables What is the asymptotic behaviour, in Θ notation, of the smallest function that for any $n_1$ and $n_2$ satisfies the following:

$$t(n_1+n_2)≥t(n_1)+t(n_2)+c·\log_2(1+n_2)$$
where $n_1≥n_2≥1$ and $t(1)=1$

I tried to see what happens if $n_1 = n_2$:

$$t(2n)≥t(n)+t(n)+c·\log_2(1+n)$$
$$t(n)≥2t(n/2)+c·\log_2(1+n/2)$$

Also if $n_2=1$:

$$t(n+1)≥t(n)+t(1)+c·\log_2(2)$$
$$t(n)≥t(n-1)+1+c$$

But I am not sure where to go next, or if this is a correct approach.

Interesting recurrence. Let's take a crack at this. Just a heads up, this answer is a bit wordy/explicit.

Clearly the first issue/difficulty is that we're trying to define this in terms of two variables ($n_1, n_2$). This seems hard so let's go ahead and redefine this relation:

$$t(n_1 + n_2) \geq t(n_1) + t(n_2) + c \log_2(1 + n_2)$$

Let $\alpha$ be a constant such that $0 < \alpha \leq \frac{1}{2}$. We can then define $n$ and $n'$ as:

$$n = n_1 + n_2$$
$$n' = \lceil \alpha n \rceil$$

You also asked for the smallest function that satisfies this. I'm taking this to mean when the left side if smallest, so we will redefine $t(n_1 + n_2)$ as:

$$t(n) = t(n') + t(n - n') + c \log_2(1 + n - n')$$

or possibly:

$$t(n) = t(n') + t(n - n') + c \log_2(1 + n')$$

If we were just looking for the upper bound of $t(n_1 + n_2)$ then we would only need the first case because it is the worst case, but we are looking for the tight bound. In any case, we now have a more manageable form of our recurrence.

You can prove by induction that:

$$an \leq t(n) \leq bn - c\log_2 n + d$$

for some constants $a,b,c > 0$. Constant $d$ will be defined momentarily.

Induction step for Lower Bound

$$
\begin{align}
t(n) & = t(n') + t(n - n') + c \log_2(1 + n - n')\\
 & \geq t(n') + t(n - n') + c \log_2(1)\\
 & = an' + an - an' + 0\\
 & = an
\end{align}
$$

Induction step for Upper Bound

$$
\begin{align}
t(n) &= t(n') + t(n - n') + c \log_2(1 + n - n')\\
 &\leq t(n') + t(n - n') + c \log_2 n\\
 &= bn' - c\log_2n' + d + b(n-n') - c\log_2(n-n') + d + c \log_2 n\\
 &= bn + 2d - c\log_2n' - c\log_2(n-n') + c \log_2 n\\
 &= bn + 2d - c\log_2(n'(n-n')) + c \log_2 n\\
 &= bn + 2d - c\log_2(\alpha n(n- \alpha n)) + c \log_2 n\\
 &= bn + 2d - c\log_2(n^2 \alpha (1- \alpha )) + c \log_2 n\\
 &= bn + 2d - 2c\log_2 n - c\log_2( \alpha (1- \alpha )) + c \log_2 n\\
 &= bn - c \log_2 n + 2d - c\log_2( \alpha (1- \alpha ))
\end{align}
$$

Now we can define $d$ in terms of constants $c$ and $\alpha$.

$$ d = c\log_2( \alpha (1- \alpha ))$$

Therefore

$$t(n) \leq bn - c \log_2 n + d$$

Clearly $an \leq t(n) \leq bn$. It's worth noting this is because $d$ will always be negative.

Now we can conclude

$$t(n_1 + n_2) = \Theta(n_1 + n_2)$$


Which is easier for human perception: type of variable before or after its name? In some programming languages type of variable goes before it's name.
In another - name goes first and then type.
Which version loads brain less and allow easier think about problem ?

I don't think there is any research (with good methodology) on this. The language I'd most expect to have actually thought about this and made an empirically-based decision is the Quorum programming language. It uses a "type before variable name" approach (though it does put the return type of a method declaration after the parameter list). However, what I believe is the primary source for the language design decisions, An Empirical Investigation into Programming Language Syntax (available via the first author's web site), does not mention this aspect or suggest that it was studied in the research reported on in that paper. There is other research by that group and research by others that was used to design Quorum, so it's possible it is covered in that other research. I haven't read it all. You can try contacting one of the creators of Quorum and asking them if they made that decision based on empirical research. If you do and you get a positive response, I would highly recommend self-answering this question with a reference to the research.


Distributed vs parallel computing I often hear people talking about parallel computing and distributed computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty easily, while I believe it is very different:

Parallel computing is more tightly coupled to multi-threading, or how to make full use of a single CPU.
Distributed computing refers to the notion of divide and conquer, executing sub-tasks on different machines and then merging the results.

However, since we stepped into the Big Data era, it seems the distinction is indeed melting, and most systems today use a combination of parallel and distributed computing.

An example I use in my day-to-day job is Hadoop with the Map/Reduce paradigm, a clearly distributed system with workers executing tasks on different machines, but also taking full advantage of each machine with some parallel computing.

I would like to get some advice to understand how exactly to make the distinction in today's world, and if we can still talk about parallel computing or there is no longer a clear distinction. To me it seems distributed computing has grown a lot over the past years, while parallel computing seems to stagnate, which could probably explain why I hear much more talking about distributing computations than parallelizing.

This is partly a matter of terminology, and as such, only requires that you and the person you're talking to clarify it beforehand. However, there are different topics that are more strongly associated with parallelism, concurrency, or distributed systems.

Parallelism is generally concerned with accomplishing a particular computation as fast as possible, exploiting multiple processors. The scale of the processors may range from multiple arithmetical units inside a single processor, to multiple processors sharing memory, to distributing the computation on many computers. On the side of models of computation, parallelism is generally about using multiple simultaneous threads of computation internally, in order to compute a final result. Parallelism is also sometimes used for real-time reactive systems, which contain many processors that share a single master clock; such systems are fully deterministic.

Concurrency is the study of computations with multiple threads of computation. Concurrency tends to come from the architecture of the software rather than from the architecture of the hardware. Software may be written to use concurrency in order to exploit hardware parallelism, but often the need is inherent in the software's behavior, to react to different asynchronous events (e.g. a computation thread that works independently of a user interface thread, or a program that reacts to hardware interrupts by switching to an interrupt handler thread).

Distributed computing studies separate processors connected by communication links. Whereas parallel processing models often (but not always) assume shared memory, distributed systems rely fundamentally on message passing. Distributed systems are inherently concurrent. Like concurrency, distribution is often part of the goal, not solely part of the solution: if resources are in geographically distinct locations, the system is inherently distributed. Systems in which partial failures (of processor nodes or of communication links) are possible fall under this domain.


Is there a well-known algorithm for arranging inputs according to their category? Background:

(I’m a complete beginner in computer science in general, so I do apologise if my question is not formulated in a sensible way. E.g. I have avoided technicalities in formulating my problem, but perhaps this causes issues. I'm willing to edit accordingly if so).

I’m trying to get to grips with the way that algorithms are/can be used in economics. I think I understand the (very) basics of how sorting algorithms and clustering algorithms could apply to some problems, but there is a (seemingly) elementary problem which I can’t find a well-known algorithm for.

The problem:

Suppose my entire input consists of a set of different quantities of two types of good. For example, apples and oranges:

Input: { 1 apple, 1 orange, 10 apples, 10 oranges }

Is there a well-known algorithm which can arrange these inputs by type of good, such that the output is the following two sets?:

Set 1 (apples): { 1 apple, 10 apples }

Set 2 (oranges): { 1 orange, 10 oranges }

Clustering and sorting algorithms do not seem to be appropriate:

From my (very, very basic) knowledge of clustering algorithms, they would not be appropriate here, as clusters are meant to represent closeness of data points in space. But, if I were to plot these goods as data points, I would have a representation of their values, whereas I'm trying to group them via their categories.

I also don’t think that a comparison based sorting algorithm would work, as these algorithms produce an ordering (total preorder) of the values input. Whereas, again, I'm trying to group them via their categories.

Is my definition of algorithm the issue?

Perhaps I'm misunderstanding the type of thing that can be input into an algorithm? Cormen et al. (Introduction to Algorithms, 2009, §1.1) informally define an algorithm as

  ...any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

So perhaps an algorithm can only take numerical values as an input and not numerical values attached to a category label (like 'apple', or 'orange')?

I’d be very grateful for any help :)

An algorithm can be seen as the steps needed to go from a well defined type of input to some well defined output. The input can therefore be everything that one can represent within a computer.

In the algorithm you are asking for it seems like the input has already been classified as specific good as in apples are already classified as apples, had it not been defined one could use clustering to find out what separates the types of goods from each other depending on the data of each entry of a good in the database.
That means that clustering is a way of data mining.

One way of solving your problem could use sorting like this:

1: def separate_goods(List S):
2:    sort S on the type of good
3:    A := a list
4:    B := a list
5:    current_type := S[0].type
6:    B.add(S[0])
7:    i := 1
8:    while(i < length(S)){
9:       if(current_type == S[i].type):
10:          B.add(S[i])
11:          i := i + 1
12:      else:
13:          A.add(B)
14:          B := a new list
15:          B.add(S[i]
16:          current_type := S[i].type
17:          i := i + 1
18:   }
19:   A.add(B)
19:   return A

The idea behind this algorithm is to first sort the input list such that all the apples are next to each, the oranges are next to each other and so on. From there we can go through the list and put all apples in a list together (the list B), then add that list to A, which simply just stores a list for each type of good.

When we go through the list (in the while loop) and sees that we go from a good of type say apples to another of type orange, then know that we finished collecting apples (since they are all together due to the sorting) and we can therefore add the list B of all the apples to list A. Then we make B contain a new list for all goods of type oranges and continuous through the list adding goods of type oranges until we either have categorized all goods or finds a new type of good.

This is not the most effective algorithm one could make, however it illustrates that sorting can be used to solve this problem.

 I'm not sure if this answers your question however feel free to reach out to me :)  This does not answer your question, here is another try:

Your problem is somewhat simple and can be solved in many ways, a particular fast way would be to use a hash table. Here you could hash each entry on the type of good, with this you can then access a list of all apples by using apple as key. I believe there is a chapter in Cormen et al about hashing that explains how this is done :)


Shannon Entropy to Min-Entropy In many papers I've read that it is well known that the Shannon entropy of a random variable can be converted to min-entropy (up to small statistical distance) by taking independent copies of the variable.
Can anyone explain to me what exactly this means?

This is a consequence of the asymptotic equipartition property (AEP), which is a form of the law of large numbers. The AEP states that if a random variable has (binary) entropy $H$ and you take $n$ copies of it, then most of the data points have probability roughly $2^{-nH}$. This is only true for most data points, which is the source of the small statistical distance that you mention.

As an example, consider a $p$-biased coin. If you throw $n$ coins with bias $p$, then most likely you will get roughly $pn$ heads, each of which events has probability roughly
$$ p^{pn} (1-p)^{(1-p)n} = 2^{-nh(p)} .$$


Strategic vertex labeling We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0. The problem is to assign labels to the vertices in $G'$ in such way that this sum is maximized $\sum_{e_{u,v}\in E} w_{i}l_ul_v.$ The question is whether this problem is NP-complete or not. If it is not then what is the polynomial algorithm?

Personally I believe that this problem is essentially a form of 3-Coloring. The challenge is to chose the labels {1,-1} depending on the neighbors. Say the boundary between $G$ and $G'$ has a lot of 1s  then it is better to chose 1s for the labeling of vertices in $G'$, similarly if the boundary has lots of -1s then it is better to chose -1s for labeling because $-1*-1=1$. So essentially this becomes some sort of reverse 3-Coloring problem where the neighbors have to have matched color.

Can you help reduce this problem to 3-Coloring (or vice-versa) ? Or perhaps there is polynomial time algorithm ?

Hint: Your problem looks a lot like minimum $(s,t)$-cut.


Reducing optimization problem to decision problem I'm trying to reduce an optimization problem to a decision problem, more specifically, consider the Max-Cut problem in its decision version:
Given $(G=(V,E),k)$ as input, where $G$ is an undirected weighted graph (all weights are positive integers, formally: $w: E\rightarrow \mathbb{N}$ is the weight function) and $k\in\mathbb{N}$, one should decide whether there exist a cut $(V_1,V_2)$, s.t its weight is at least $k$, meaning $k\leq \sum _{u\in V_1, v\in V_2}w(u,v)$.
The optimization version is simply finding the maximum weighted cut.
What I'm trying to achieve is, given an algorithm $A$ that can solve the decision problem, I want to describe an algorithm that can find the maximum cut in $G$.
So, first of all, this is what I had in mind:

Find the weight of the maximum cut in $G$ (this can be done with a simple for loop that starts with 1 and stops at $m$, where $m=\sum _{e\in E}w(e)$ while in each iteration the algorithm queries $A$), define $k$ to be the weight of the maximum cut.
Initialize new set $S\leftarrow \phi$
For $e\in E$ do:

Omit edge $e=(u,v)$ from $G$, to create new graph $G_e$.
If  $A(G_e,k)=0$ (both ends of $e$ are at the same set), $S\leftarrow S\cup \left \{ u,v \right \}$
else if $A(G_e,k)=1$ then...(?)
This is where I'm stuck, I'm not sure how can I tell which end of $e$ should be in $S$...
In fact, I'm not even sure if this is the right way to do it.

Any help and thoughts will be appreciated.

Given the formulation of your decision problem, first of all notice that you can do binary search to find the max-cut weight $k$, rather than linear search. Secondly, when you test each edge, you get that either the two end points are in the same set, or the two end points are in different sets. Let $S$ be a set on one side of the cut, and let $x_u,x_v$ be boolean indicator variables for whether $u,v$ are in $S$. Then if edge $(u,v)$ crosses the cut, you want $(x_u,x_v) = (1,0)$ or $(0,1)$, and otherwise you want $(x_u,x_v) = (0, 0)$ or $(1,1)$. You can formulate this as a 2-sat problem and solve it in linear time (linear in the number of edges) to determine membership in set $S$. For example, if $(x_u,x_v) = (0, 0)$ or $(1,1)$ then you would add the two clauses $(x_u \vee \neg x_v) \wedge (\neg x_u \vee x_v)$ to your 2-sat formula.


Set cover problem with sets of size 2 I have a question about the Set Cover problem: If I get a universe $U$, and $m$ subsets of size exactly $2$, and an integer $k$. Is this problem is still NP-C or I can solve it on a polynomial time?

Thanks.

This is exactly the edge cover problem, which can be solved in polynomial time by finding a maximum matching.  Then, for each unmatched vertex, add an arbitrary edge containing that vertex.

In fact, if all you want to know is whether there's an edge cover of size at most $k$, you don't need to construct the cover: the size of a minimum edge cover is $M + n - 2M = n-M$, where $n$ is the number of vertices in the graph and $M$ is the number of edges in a maximum matching.  (The reasoning here is that the cover is the $M$ edges of the matching plus one more edge for each unmatched vertex, and there are $n-2M$ unmatched vertices.)


Difference between First Order Logic and Predicate Calculus I see the two used interchangeably. Is one the subset of the other or are they both the same thing?

First-order logic and first-order predicate calculus are the same thing, which is exactly why the terms are used interchangeably. See, for example, Wikipedia:

  First-order logic [...] is also known as first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic.


More efficient maximum bipartite matching I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and papers, I've noticed that the Hungarian/Kuhn's algorithm tends to get mentioned a lot as a solution/approach. My sticking point is that it runs in $O(n^3)$ time and I've read in a few sources that there are better implementations.

My challenge is that these sources will often just mention these better approaches at the very end of a discussion and offer little insight into the implementation. So I guess my question is: are there indeed better than $O(n^3)$ runtimes? I think I remember coming across references that $O(nm\log n)$ and better exist, just having a hard time finding either reference implementations or more direction. Any help would be appreciated, especially examples as that's how I tend to grok things best after going through the theory.

The Hungarian method can be implemented in time $O(mn + n^2 \log n)$. Details are found for example in Alexander Schrijver's book on Combinatorial Optimization, Chapter 17. For a more implementation-oriented guide to this version of the algorithm, have a look in Chapter 7 of Mehlhorn and Näher's book.

The running time is dominated by the time it takes to compute $n$ shortest paths via Dijkstra's algorithm. Each invocation of Dijkstra's algorithm costs $O(m + n \log n)$. (This assumes that Dijkstra's algorithm is implemented with Fibonacci heaps; the simpler implementation based on standard heaps would give $O(m \log n)$ for each invocation.)


What difference does it make when universal classical gates in quantum computation are reversible but not unitary? As I've come across Grovers algorithm I dont understand why when computing F(X), which is an oracle function people use classical reversible circuits(toffoli, fredkin) to evaluate the circuit. Why can't it just be done using classical logic gates(and, or, etc) when the function doesn't have any thing to do with changing the superposition of the bits.

Reversible gates are unitary, see for example https://en.wikipedia.org/wiki/Quantum_gate. The eigenvalues are $\pm 1$. The quantum computation model requires all gates to be unitary, so you can't just use classical gates.


Difference between diameter of a graph vs longest path of the graph I am curious what is the difference between diameter of a graph vs longest path of a graph. I just read diameter of a graph can be solved using Floyd warshall in O(V^3) while longest path can be calculated in O(V + E) using topological sort.

The longest path of the graph is the longest path between any two vertices. There may be several with the same longest length.

Since you are comparing with the diameter, which is an integer, you probably mean the length of the longest path

The diameter is the length of the longest of the shortest path between any two
vertices. That means that you compute the shortest path for any pair
of vertices, and take the longest one of them.

The distance between two vertices being the shortest path, the diameter is the longest distance between two vertices,


Approximation factor for graph problems I am attempting to figure out how to use approximation factors to determine the answers an algorithm can return for graph problems.

For example, if a graph G actually has a maximum clique with 13 vertices, and we use a 1.5-approximation algorithm to approximate the maximum clique - what is the minimum size clique that can be returned by this algorithm?

My first thought was to simply divide 13 / 1.5 since this would represent the worst that the algorithm could do. However, since that is ~ 8.6, would the minimum the algorithm returns be 9 or 8?

An approximation algorithm for a maximization algorithm has an approximation ratio of $\alpha \geq 1$ if whenever the true answer is $m$, the algorithm is promised to return a solution with value at least $m/\alpha$.

In your case, $m = 13$ and $\alpha = 1.5$, and so by definition, the algorithm must return a clique whose size is at least $13/1.5$. Since the size of the clique is an integer, if a clique is of size at least $13/1.5 \approx 8.6$, then it is in fact at least $\underline{\quad}$ (fill in the blanks).


IEEE 754 addition wrong result floating point numbers I want to add two IEEE 754 numbers.
I followed the steps to add two 754 numbers. However the result it not correct.
Number 1:
S:0
E:01111111
M:11111111111111111111111
Number 2:
S:0
E:01111111
M:00000000000000000000000
Here is my calculation:

The site http://weitz.de/ieee/ gives this result:
S: 0
E: 10000000
M: 10000000000000000000000
in my calculation the mantissa is 01111...
Why?

You forgot the implicit leading 1 in the mantissa. The mantissa is not 23 bits, it's 24 bits with a 1 as the leading bit.


Why don't we emphasize "length of input string" when considering time complexity of sorting algorithms? The knapsack problem is $O(c\,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it's exponential because the size of the input is $\log(c)$.

However, why don't we emphasize length of input in other algorithms? To name one example, what would be the input size $n$ and worst case time complexity $T$ of the following input when using insertion sort:

111111111,101,11,10,1,0

Answer A: $n=6$, $T=O(n^2)$
Answer B: n = space(all_digits)+space(delimiters_between_numerics)

If B is correct, what is the time complexity $T$?

First, note that the input length of a Knapsack instance is $\Theta(n \cdot \log \max \{c,w_1,\dots,w_n\})$. Assuming the instance is "pruned", namely that all weights are at most $c$, this is $\Theta(n\log c)$.

In order to answer such questions, you need to fix

the machine model,
the cost model,
the set of valid inputs and
the algorithm.

You don't give the first three.

So your question is not well defined. In order store this particular set of numbers on a Turing machine tape, six symbols are indeed sufficient (one per number), and then the algorithm would run in time $O(1)$ on its only input. In order to get a general algorithm, however, you need to "properly" encode the numbers, namely B is the correct answer. I'll assume the latter.

Insertion sort has worst-case complexity $\Theta(n^2)$ in the RAM model with uniform cost model (elementary operations on naturals cost $1$), $n$ being the number of elements. In particular, it is independent of the size of the numbers. Since $n \leq |i|$, $i$ the input, you get an $O(|i|^2)$ time algorithm.

If you apply the logarithmic cost model (elementar operations on naturals have cost depending on their encoding length, cf. elementary school), you get time $\Theta(n^2 \cdot \log E)$ with $E = \log \max\{e_1, \dots, e_n\}$ the length of the largest input number, because the $\Theta(n^2)$ comparisons on the elements dominate the runtime. With similar reasoning as above, we note that the algorithm has runtime $O(|i|^2)$.

So as you can see, the qualitative result does not change when considering the input length for this kind of algorithms, so it is often glossed over. When analysing e.g. radix sort this is no longer valid, and you have to look more closely.


Least Significant Bit (LSB) vs Little Endian - Are they equivalent in anyway! For a multiple choice question: What do we call the LSB?
(i)Little Endian    (ii)Upper bit   (iii)Big Endian (iv)Lower Bit

I feel ideally none of them is a true correct choice, but my best bet was (iv) Lower Bit.

However, our professor claims that the correct choice should be (i)Little Endian. He even said "LSB stands for Least Significant Bit which is right most bit of a binary equivalent and it is Little endian format."

I don't agree with the last part i.e. "..it is Little endian format."

My understanding (primarily from the book  “Computer Organization and Design” by Patterson and Hennessy,) is that LSB (and MSB) concepts were introduced to clearly identify bits at both extremes while avoiding any confusion arising due to writing styles like vertically or horizontally which can be confusing when read/written from different directions. Further it (LSB) has nothing to do with byte ordering such as Little endianness. For example any number will have both LSB and MSB, and can be stored in a little endian hardware as much as it can be stored in a big-endian hardware.

Pls let me know if I'm misunderstanding the professor's statement in any way.

LSB (least significant bit) and MSB (most significant bit) apply purely to the values of an integer. The least significant bit is the bit with value 1, the second least significant bit is the bit with value 2, and so on.

"Little endian" and "Big endian" are just artefacts from the fact that the bytes of a number can be accessed individually as they are stored in memory. But if an integer is stored in 4 bytes, there are actually 24 different ways in which order these bytes could be stored in memory; big endian and little endian are just two of those 24.

With all this said, if you have been understanding your professor correctly, and reported accurately what he said, then he is absolutely wrong. Actually the multiple choice answer "lower bit" is already nonsense (maybe not nonsense, but we really like precision in CS). If you have 32 bits, 31 of them are "lower" than some other bit, but ONE of them is the lowest bit. The Least Signficant Bit.

When "Little Endian" and "Big Endian" are abbreviated, they are abbreviated as LE and BE (for example UTF-16 LE and UTF-16 BE).


Prove that language of possible stack content is regular So, here's the problem:

Suppose that $A=(Q,\Sigma,\Gamma,\delta,s,\bot, F)$ is a PDA, let
 $$L = \{ \gamma \in \Gamma^* \hspace{5pt}|\hspace{5pt} \exists_{x,y\in \Sigma^*} \exists_{q\in Q}: (s,x,\bot)\vdash_A^*(q,y,\gamma)\}$$

Show that $L$ is regular.

So far solution has been eluding me, any hints are welcome.

Here is the basic idea. Assume for simplicity that each transition increases the size of the stack by at most one (you can always arrange that using epsilon transitions).

Suppose that the stack at some point is (bottom to top) $A_1 \ldots A_n$. At the time $t$ of the snapshot, $A_1$ is at the bottom of the stack. Consider the earliest time $t_1$ such that from time $t_1$ to time $t$, $A_1$ was always the bottom of the stack. At time $t_1$, the stack is simply $A_1$.

Similarly, there is an earliest time $t_2$ at which $A_2$ was second from last symbol on the stack, and at time $t_2$, the stack is $A_1 A_2$. We can similarly define times $t_3,\ldots,t_n$. We can describe the state of the stack schematically as follows:
$$
\bot \vdash^* A_1 \vdash^* A_1 A_2 \vdash^* \cdots \vdash^* A_1 A_2 \ldots A_n.
$$
The first step is special, so let's consider any other step. Think about what information is required to known whether you can get from $A_1 A_2 \ldots A_i$ to $A_1 A_2 \ldots A_{i+1}$, without every removing $A_1 A_2 \ldots A_i$. If the amount of information is finite, then you can use it to construct an automaton for your language.


Computing Nash equilibria in discrete auctions I am trying to compute the (pure strategy) Nash equilibria of some discrete auctions.

More precisely, let us define the strategy of each player as a function mapping from every valuation that they might have to their bid (i.e. the 'bidding function'). Let us suppose that each player's valuation is drawn from some finite set and that their bid must belong to this same (finite) set. I am interested in finding the set of bidding functions, one for each player, such that each player's bidding function is optimal given the bidding functions of all the other players.

If it makes things easier, we can assume that valuations are symmetric (i.e. each player's valuation is generated by the same probability distribution) and that there are only two bidders. Ideally, however, we would proceed without these simplifications. I am interested in computing the equilibrium for the first price sealed bid and all pay auctions (in the latter, you pay your bid even if you lose; in the former, you don't.)

I have considered writing down the discrete auction game in normal form and finding the equilibria using software like Gambit. However, this would seem tricky since the strategy space is so large.  For example, if a player chooses bids from $ \{1,...,10\} $ and draws values from $ \{1,...,10\} $, then already they have $10^{10}$ pure strategies.

Does anyone have any ideas about how to proceed here?

If there are only two players, you could use integer linear programming.

I'll introduce some zero-or-one integer variables to encode the (unknown) bidding functions (via a one-hot encoding).  Let $x_{v,b}=1$ if player $0$'s bid is $b$ when their valuation is $v$, and $0$ otherwise; and $y_{w,c}=1$ if player $1$'s bid is $c$ when their valuation is $w$, and $0$ otherwise.  In this way, if there are $n$ possible valuations, we obtain $2n^2$  zero-or-one integer variables.  We will write down linear inequalities on these variables that characterize the  optimality condition, then use an integer programming solver to find a solution that satisfies all of these inequalities.

Note that if player $0$'s valuation is $v$ and player $1$'s valuation is $w$, then player $0$'s payoff (in a first-price auction) is

$$\sum_{b>c} x_{v,b} y_{w,c} (v-b).$$

Therefore, if player $0$'s valuation is $v$, player $0$'s expected payoff is

$$\sum_w p_1(w) \sum_{b>c} x_{v,b} y_{w,c} (v-b),$$

where $p_1(w)$ represents the probability that player $1$ gets valuation $w$.  Now, we need this to be at least what it would be if player $0$ used any other bid for valuation $v$, i.e., any other choice of $x_{v,\cdot}$'s.  If there are $n$ possible valuations, there are only $n$ possible bids, so we obtain $n$ inequalities

$$\sum_w p_1(w) \sum_{b>c} x_{v,b} y_{w,c} (v-b) \ge \sum_w p_1(w) \sum_{b'>c} y_{w,c} (v-b'),$$

where we obtain one such inequality for each possible value of $b'$.  (The sum on the left-hand-side is over $w,b,c$ that satisfy the condition $b>c$; the sum on the right-hand-side is over $w,c$ that satisfy the condition $c<b'$.)

This is a quadratic inequality.  We'll turn it into a linear inequality using the techniques of Express boolean logic operations in zero-one integer linear programming (ILP).  In particular, introduce new zero-or-one variables $t_{v,w,b,c}$, with the intention that $t_{v,w,b,c}=x_{v,b} y_{w,c}$.  This can be enforced using the linear inequalities $t_{v,w,b,c} \ge x_{v,b} + y_{w,c} - 1$, $t_{v,w,b,c} \le x_{v,b}$, $t_{v,w,b,c} \le  y_{w,c}$, $0 \le t_{v,w,b,c} \le 1$.  Now the optimality condition becomes

$$\sum_w p_1(w) \sum_{b>c} t_{v,w,b,c} (v-b) \ge \sum_w p_1(w) \sum{b'>c} y_{w,c} (v-b'),$$

for each $v,b'$.  We obtain one such inequality for each $v$ and each $b'$.  These $n^2$ inequalities ensure that player $0$'s strategy will be optimal (given player $1$'s strategy).

Then, add similar inequalities to require player $1$'s strategy to be optimal (given player $0$'s strategy).

Also add the $n^2+n$ constraints that $0 \le x_{v,b} \le 1$ and $\sum_b x_{v,b}=1$ to require the $x$'s to correspond to a bidding function, and similarly for the $y$'s.

Finally, take all of these inequalities and feed them to an off-the-shelf integer linear programming solver.  If it finds a solution, then you have found a Nash equilibrium for your game.  ILP is NP-hard, so there is no guarantee that it will terminate in a reasonable amount of time, but in my experience often the solvers can handle surprisingly large systems of inequalities.

The same approach can handle all-pay auctions as well as first-price auctions.

In practice, you might be able to speed up the solver by adding some extra constraints to help it identify a solution faster.  In particular, I have a hunch that without loss of generality the optimal bidding function can be assumed to be monotonic: if we increase my valuation, my bid should never decrease.  We can add extra inequalities to the system to characterize this additional assumption, and this might narrow the search space and thus help the ILP solver find a solution more rapidly.

One big limitation is that this seems limited to two players (or a very small number of players).  If there are multiple players, the number of variables and inequalities will explode, and this might not be an effective approach.


How "coplanar" is a set of points? Assume that we have 10 points. If all those points are on the same plane, they all are coplanar. But some of them might be at a different place. That disrupts the structure of the plane if we were to draw the surface that passes from all the points.

I need a metric that tells me how fine the structure of the plane is preserved. Or how planar is the surface.

What I have thought is, take random 3 points among 10 and derive the plane equation in terms of $ax + by + cz = d$. Then, for each remaining point $p(p_x,p_y,p_z)$, calculate the summation $ap_x + bp_y + cp_z$. Store the results and take the standard deviation.

However this method fails for the following reason:
If there are 9 points on the same plane and only 1 point is far away, and if I pick the point who is far away, then the equation I generate is way too different then the plane defined by remaining 9 points.

Plugging the coordinates of remaining points into the equation of the plane, I'll get too many different results. Therefore, even though the surface is almost planar, standard deviation will be so high, depending on the generated equation.

This problem (I think) can be reduced to line cover problem (covering a set of points in 2D with minimum number of lines), hence, NP-Complete.

Or is it really? Is there a polynomial time algorithm that guarantees to find a value for all types of point sets?

I thought about starting not with 3 but with 4 points, then testing the other points. Does that work?

Option 1: Use least squares fit to find the closest plane.  Then, measure the average squared error (the sum of the squared residuals).

Option 2: Use robust regression instead of least squares.  Or, use RANSAC.  These will handle outliers better.

All of these run in polynomial time.


Test cases for graph embeddability problem Suppose that I have a polynomial-time algorithm to solve the graph embeddability problem.

$k$-embeddability problem :
Given an edge-weighted and undirected graph $G = (V,E)$, can we assign coordinates to each $v \in V$ in $k$-dimensions such that Euclidean distance between $u,v \in V$ is equal to the weight of the edge $\{u,v\}$?

And, suppose that I want to check if I have settled P vs. NP. The algorithm has 100% success rate when tested with random graphs.

However, I might be lucky while generating random data. Is there any finite set of test cases, such that if an algorithm solves each of them, that implies the algorithm is able to solve graph-embedding problem for all possible problem instances?

(I've already verified that the algorithm runs in polynomial time; now I just want to verify whether the algorithm is correct.)

No finite set of test cases can prove correctness of an algorithm, if we have no information about the form or structure of the algorithm and if the set of possible inputs is infinite.

For any finite set of test cases you might have in mind, I can come up with an algorithm that works correctly on all of those test cases, but is incorrect (works incorrectly on another input, or on infinitely many inputs).  For instance, if your test cases are the inputs $t_1,\dots,t_k$, and the correct answers are $y_1,\dots,y_k$, then my algorithm can be:

Algorithm FooledYou(x):
1. If $x=t_i$ for some $i$, then output $y_i$.  Otherwise, output 42.

This algorithm has polynomial time and works correctly on those $k$ test cases, but is not a correct solution to the problem.

This is a fundamental limitation of using testing to check program correctness.  Testing cannot prove a program is correct; it can only prove the program is incorrect.

Now, suppose you want to test your program in practice.  Here is a heuristic that will likely be effective.  You link to a paper that shows that 1-embeddability is strongly NP-complete, by showing a polynomial-time reduction from 3SAT to 1-embeddability.  There are standard ways of generating hard instances of 3SAT.  So, use that polynomial-time reduction to convert them into (hard) instances of 1-embeddability, and test whether your algorithm gives a correct answer and solves the corresponding 3SAT problem.  Odds are, this will reveal a problem of some sort somewhere.

For instance, one standard way to generate hard 3SAT instances is by using the reduction from Factoring to 3SAT: generate a random 2048-bit RSA modulus (product of two 1024-bit primes), then ask what its factors are.  For more details, see Fast Reduction from RSA to SAT and Generating 3SAT circuit for Integer factorization example.


Genetic Algorithms - Tournament Selection I know this should be a fairly simple concept but I have been Googling a lot and can't seem to find a definitive definition.

If we had the following random population:

[12,2,3,99,73,32,53,8]

And a tournament size of 3. What could be a possible outcome?

Is there lots of variations of Tournament Selection?

A simple version of tournament selection is as follows.

  Select $k$ random Individuals from the population.
  Select the best Individual from the $k$ Individuals.
  Repeat from 1 until you have selected the desired amount of Individuals.

As an example. Consider your data, $k=3$ and that we wish to select 3 Individuals.

$[12,2,3,99,73,32,53,8]$ (your data).

$[12,2,99]$ (3 random Individuals).
$99$ is the best Individual.

$[2,73,53]$ (3 random Individuals).
$73$ is the best Individual.

$[99,8,53]$ (3 random Individuals).
$99$ is the best Individual.

We have selected the Individuals $73,99$ and $99$.

Note that we have selected $99$ twice.
If this is not desired, you can delete an Individual from the population if it has been selected.

It is also possible, instead of always selecting the best Individual, to select an Individual according to some stochastic scheme. For example, assign the best Individual from the tournament pool (the $k$ randomly selected individuals)  $i=0$, the second best $i=1$, ... (etc), and the worst Individual $i=k-1$. Then Individual $i$ is selected with chance $\frac{2(k-i)}{k(k+1)}$.

I just made this stochastic scheme up. You can use your fantasy on how to extend/alter tournament selection or any other genetic operator :)


Counting trees (order matters) As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In other words, order matters. Certainly it will be much more than the Catalan number.

What would the problem be if you have n-ary trees instead of binary ?

Are these known problems?  reference ?

I am not sure, if I understood the question correctly, but are you asking for the number of rooted binary trees of size $n$, with nodes labeled from $1,...,n$, where isomorphic trees with different labelings are counted as different?

If so, isn't your labeling just adding $n!$ different possible labelings for each class of isomorphic trees? I.e. your total number of trees would be $n!C_n$, where $C_n$ is the $n$-th Catalan number.


Walk around a coordinate in circular order to a distance of N For my development purpose, I need to work on all the 2D coordinates (in whole number) around [0,0] from 0 to N distance. For example, with N=1, I need

N0: [0, 0]
N1: [-1, -1] [0, -1] [1, -1] [1, 0] [1, 1] [0, 1] [-1, 1] [-1, 0]

The order is important. I want to walk these values in a circular way, starting from 0, incrementing the distance each round.

I first created two for-loops, from -N to N on each axes, but the resulting order is the one as you read a book: from top left to bottom right.

Here's the order I aim (the first coordinate to walk on each circle is not important):

Here's a first algorithm I tried, in pseudo code

int totalSize = (2*N+1, 2)*(2*N+1, 2)
Vector2[] coordinates = new Vector2[totalSize]
int index = 0
coordinates[index++] = new Vector2(0, 0)
for (int d = 1; d <= N; d++) {
    for (int x = -d; x <= d; x++) {
        coordinates[index++] = new Vector2(x, -d)
        coordinates[index++] = new Vector2(x, d)
    }
    for (int y = -d+1; y <= d-1; y++) {
        coordinates[index++] = new Vector2(-d, y)
        coordinates[index++] = new Vector2(d, y)
    }
}
for (int i=0; i<coordinates.Length; i++) {
    print(coordinates[i])
}

But:

It seems too cumbersome. I don't like the creation of a scructure that retains the coordinates. And 4 for-loops seems not optimized.
The order of the circles is ok, but the order inside each circle is not the one I described.
I have the feeling trigonometry can help me, but I can't see how to implement it on discrete values

Any idea?

You can do this in a stateless manner.

Here is python code that generates the infinite walk:

def circular():
    yield (0,0)
    x,y = -1,0
    while True:
        yield (x,y)
        if x < 0 and 0 <= y < -x:
            y += 1
        elif y > 0 and x < y:
            x += 1
        elif x > 0 and y > -x:
            y -= 1
        elif y < 0 and x > y:
            x -= 1
        elif x < 0 and y < -1:
            y += 1
        elif x < 0 and y == -1:
            x -= 1
            y += 1


Find a polynomial in two or three queries Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.

Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$.
Output: The $d$ coefficients of polynomial $f(x)$.

My algorithm: let

$$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$

Evaluate polynomial $\mathcal{f(x)}$ at $d$ many points using the black box and get a system of linear equations. Now I can solve the system of linear equations to get the desired coefficients.

However, in this case, I need $\mathcal{O(d)}$ many queries to the black box. I want to minimize the number of queries. Is there any way to reduce the number of queries to just two or three?

You can determine the polynomial using two queries. First query the polynomial at $x=1$ to get an upper bound $M$ on the value of the coefficients. Now query the polynomial at $x > M$ of your choice and read off the coefficients from the base $x$ expansion.

Curiously, if you allow the coefficients to be negative then you cannot do better than $d$ queries. Indeed, I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero, and this does not fix the value of the polynomial since all polynomials of the form $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$ are consistent with my answers.


Using Union find to check whether there is a cycle in a graph I'm trying to learn about DSU, and I came across a point stating if two vertices belong to the same sub-set, then a cycle exists. In terms of implementation of DSU, I'm unable to make sense of this. Could you share a proof or explain this?

The way it works is that your sets are connected components of the graph. You build such components incrementally, adding one edge at a time. When you add each edge, you ask if the vertices are part of the same component, if so then you have a cycle, if not, then you join the two components (perform a set union). Keep adding edges until you run out of them or found a cycle.

If we look at the definition of connected component, it implies that for each two vertices $u$ and $v$ in the same component, there's a path connecting them.

The algorithm works as follows: you start adding a Singleton set for each vertex to your dsu. These are your first components. Then add the first edge, obviously, the two vertices will be on separate sets (components), and you just found an edge connecting them, so that means they belong to the same component. So you join the two sets (components) into a single one, as your edge is the path connecting them.

You keep going, everytime you find an edge connecting two vertices in different components, you can join the components, as that edge will be a bridge connecting them: if the vertices are $u$ and $v$, and you have $w$ in $u$'s component, you can assert that there's a path from  $w$ to $v$ passing through your current edge. Is easy to see now that all vertices in both components are now connecting. So join the two sets (components) in one.

Finally, when you process an edge which vertices $u, v$ are on the same component, you just found a cycle: since both are on the same component, you know there's a path between them, and your new edge happens to close the cycle.

DSU is typically used for implementing Kruskal's algorithm,  and uses the same properties. You can do a quick Google search for Kruskal with DSU, for examples.


Finding a segment which has equal number of segments before and after it I got this question in a past test that I'm trying to solve but i don't have the solutions to check my self:

Given a set of n segments $[a_i ,b_i]$ where $i=1,..,n$ and $a_i < b_i$.
write an algorithm which find a segment that the number of segments $[a_l ,b_l]$ before it $(b_l < a_i)$ are equal to the number of segments $[a_r ,b_r]$ after it $(b_i < a_r)$
the algorithm will return its index if found else null

The algorithm should work in $O(n\log n)$ in worst case.

My solution is:

 running heapsort by $a_i$ (runs in $O(n\log n)$)
 running bucket sort by $b_i$ which each bucket is $a_i$ (runs in $(O(n))$)
 loop on each member (X) in reverse order and finding using binary-sort on the rest of the set the segment (Y) which its $b_i$ is equal or max close to $a_i$ and writing in the Y the distance of X from the end of list (number of segments which are right of Y) and writing in X the index of Y (number of segments which are left of X). that happens in (runs in $O(nlgn)$)
 loop on each member the looking up for an element with (left_count equals right_count) not equals zero and return it  (runs in $O(n)$)
 if nothing found - return null

So finally the algorithm works in $2lgn + 2n$ which is $O(nlgn)$

Am I right? There is a better solution?

Here is an algorithm that achieves $O(n\log n)$ complexity without any elaborate data structures. Just a simple sort and a couple of loops.

Sort all the $\{a_i,b_i\}$ together. Call the resulting sequence $(x_1,\ldots,x_{2n})$.
Set $n_a\gets0$, $n_b\gets0$.
Loop for $n_b$: For $t$ going from $1$ to $2n$ do:

If $x_t=b_i$ for some $i$, increment $n_b$
Else if $x_t=a_j$ for some $j$, set $L_j\gets n_b$

Loop for $n_a$: For $t$ going from $2n$ down to $1$ do:

If $x_t=a_i$ for some $i$, increment $n_a$
Else if $x_t=b_j$ for some $j$, set $R_j\gets n_a$

Now for each interval $[a_i,b_i]$, $L_i$ and $R_i$ contain the number of intervals to its left and to its right, respectively
Final loop: For $i$ going from $1$ to $n$

If $L_i=R_i$, return $i$

Found nothing: Return null.

You might need to make some additional checks to take care of cases where $a_i=b_j$ for $i\not=j$.

Note that equality checks of the form $x_t=b_i$ can be done by saving the sorting indices. In other words, if you sort an array $u$ into another array $v$, you can save indices $\pi_t$ such that $u_t=v_{\pi_t}$.


Inserting vertex in an adjacency matrix If a graph with $v$ vertices is represented in the form of adjacency matrix .

Then, adding a new vertex to the existing graph requires how much time ?

Is it $O(v^2)$ or $O(2v)$ .

We have the adjacency matrix of the graph with $v$ vertices , by adding a new vertex we have to enter a row (for edges leaving the new vertex) and a column(for incident edges of new vertex) and an entry for self loop . So ,there is a need to update $2v+1$ new entries. So i am in favor of $O(2v)$. Did i miss something ? Is there any need for creating new empty matrix of size $(v+1)^2$ and then copying $v^2$ existing elements and updating remaining $2v+1$ entries of new vertex , which takes $O(v^2)$ time.

Thanks in advance .

This is completely implementation-dependent. As you say, if you need to copy the existing matrix, you have $n^2$ entries to copy, which takes $\Theta(n^2)$ steps; if you only need to add the new entries (for example, if you've pre-allocated a large matrix but you're adding the vertices one at a time), you only need to write $O(n)$ entries each time.

If you did have to copy the matrix every time you grow it, a more time-efficient option would be to start with a small matrix (say, $10\times 10$) and double it every time it fills up. Doing it that way means you need fewer expensive copies but the potential down-side is that you could waste a lot of space.  For example, if your graph ends up having 21 vertices, you'll have allocated a $40\times 40$ matrix, most of which is empty. You could mitigate that by not growing the array so aggressively (say, making it 25% bigger each time it grows, instead of 100%).


Discrete optimisation in 5 variables I need to solve the following optimisation problem and I can't come up with any solutions. Is there any algorithm to solve this type of problem. I tried to think of a greedy algorithm or brute force, but couldn't solve it.

Input :
$ n_1, n_2, n_3, n_4, n_5$ : Positive integers
$ a_1, a_2, a_3, a_4, a_5 $ : Positive integers
$ p_1, p_2, p_3, p_4, p_5 $ : Positive integers
$ Q $ : Positive integer

Output :
$ m_1, m_2, m_3, m_4, m_5$ : Non- negative integers

Minimize :
$ \sum_{i=1}^{5}{m_i a_i p_i}$

Constraints :
$ \forall i : m_i \geq n_i $ OR $ m_i = 0 $
$ \sum_{i=1}^{5}{m_i a_i} \geq Q$

First of all, we can enumerate over all 32 possibilities of which of the two alternatives is chosen for each $m_i$ (whether $m_i \geq n_i$ or $m_i = 0$). We will analyze, for simplicity, the case where $m_i \geq n_i$ for all $i$. Let $\mu_i = m_i - n_i$, so that $\mu_i$ is some arbitrary non-negative integer. We now want to minimize the quantity $\sum_i \mu_i a_i p_i$ under the constraint $\sum_i \mu_i a_i \geq P$ (where $P$ is a function of other known parameters).

You can now reduce your problem to KNAPSACK as described in a question on cstheory.


Proving the security of Nisan-Wigderson pseudo-random number generator Let $\cal{S}=\{S_i\}_{1\leq i\leq n}$ be a partial $(m,k)$-design and $f: \{0,1\}^m \to \{0,1\}$ be a Boolean function. The Nisan-Wigderson generator $G_f: \{0,1\}^l \to \{0,1\}^n$ is defined as follows:
$$G_f(x) = (f(x|_{S_1}) , \ldots, f(x|_{S_n}) )$$
To compute the $i$th bit of $G_f$ we take the bits of $x$ with indexes in $S_i$ and then apply $f$ to them.

Assume that $f$ is $\frac{1}{n^c}$-hard for circuits of size $n^c$ where $c$ is a constant.
How can we prove that $G_f$ is $(\frac{n^c}{2}, \frac{2}{n^c})$-secure pseudo-random number generator?

Definitions:
A partial $(m,k)$-design is a collection of subsets $S_1, \ldots, S_n \subseteq [l] = \{1, \ldots, l\}$ such that

for all $i$: $|S_i|=m$, and
for all $i \neq j$: $|S_i \cap S_j| \leq k$.

A function $f$ is $\epsilon$-hard for circuits of size $s$ iff no circuit of size $s$ can predict $f$ with probability $\epsilon$ better than a coin toss.
A function $G:\{0,1\}^l \to \{0,1\}^n$ is $(s, \epsilon)$-secure pseudo-random number generator iff no circuit of size $s$ can distinguish between a random number and a number generated by $G_f$ with probability better than $\epsilon$.
We use $x|_A$ for the string composed of $x$'s bits with indexes in $A$.

Here is Ran G.'s answer mentioned in the comments: Google gives quite nice results: 1, 2.


Is language {M | M halts and print "Hello World"} recursively enumerable? Is language {M | M halts and print "Hello World"} recursively enumerable?
I'm not sure my proof is correct.
Let universal Turing machine U start another Turing machine M2 that reads result of work of given Turing machine M1, which halts on "Hello World" and goes to infinite loop otherwise. Then M2(M1) halts if and only if M1 prints hello  "Hello World".

Enumerate all turning machines $M_1, M_2, \dots, $ and simulate them in a dovetail fashion, i.e., proceed in rounds:

In the first round simulate $M_1$ for $1$ step;
In the second round simulate $M_1$ and $M_2$ for one (more) step each;
In the third round simulate  $M_1$, $M_2$ and $M_3$ for one (more) step each;
...

In general, at the $i$-th round you perform one additional step for all turning machines in $\{ M_1, \dots, M_i \}$ that have not yet halted. Whenever a Turing machine $M$ halts, check if its output is "Hello World" and, if so, return $M$.


How does facial recognition work? I'm interested in learning about how facial recognition works.  I'm especially interested in the algorithms or approach that is used.  What are the leading methods for facial recognition?  Is there a good overview or source to learn about a few of the most widely used algorithms for facial recognition?  What would be the best handful of research papers to read first?

The simplest Face Recognition 101 would be run a PCA on the data, followed by a K-nearest neighbor classification.

but now there are more advanced techniques that you pick along, it might be using "better" classifiers like SVMs or Neural Networks or apply Bayesian learning, but then, as you move up the knowledge tree, you will realize you need your data itself to be more robust.. so you will then want to learn about about SIFT and other techniques.

One of the nice places you can start looking for papers and algorithms is face-reg

Have fun learning :)


Floyd Warshall with constraints I was wondering if its possible to use floyd warshall with constraints meaning lets say you have a group of "special vertices" of size logn and you want to calculate all the shortest paths but each path has to go through at least one "special vertex" is this even possible or is it hard n

Yes, and you can even use the Floyd–Warshall algorithm as a black box, together with a post-processing step to achieve this.
First, compute the shortest path between every pair of vertices using the Floyd–Warshall algorithm. Then, for each pair of vertices u and v and every special vertex w, compute the sum of the two shortest paths, the one from u to w and the one from w to v. The constrained shortest path from u to v is realized by the special vertex w that minimizes the sum of the u-w path's length and the w-v path's length.
Since the number of special vertices is obviously at most n, the computational complexity of the post-processing step is O(n^3). Because the computational complexity of the Floyd–Warshall algorithm is O(n^3) as well, the total computational complexity of this algorithm is O(n^3).
(credit to snakile)


Analyzing time complexity for change making algorithm (Brute force) I'm new to analyzing time complexities and I have a question. To compute the nth fibonacci number, the recurrence tree will look like so:

Since the tree can have a maximum height of 'n' and at every step, there are 2 branches, the overall time complexity (brute force) to compute the nth fibonacci number is O(2^n).

Now, looking at the coin make change problem. If the coin denominations are [1, 5, 10, 25] and the input number to make change for is 'C', the recurrence tree should look something like this:

In this case, the tree can have a maximum height of 'C' and the number of branches per step is 4 (The number of coin denominations we are given. Let's call this 'n'). With that being the case, shouldn't the time complexity be O(n^C). I read everywhere that the time complexity is O(C^n). Can someone please explain?

First, when computing the $n$-th fibonacci number $F(n)$, the number of branches (leaves) is not $2^n$, but exactly $F(n)$. But you can say it is $O(2^n)$.

As for the coin change problem it is not $O(n^C)$. $n^C$ is a polynomial, while the number of branches in the tree  grows exponentially. In other words, given $n$ number of coin denominations and constant $C$, each node has no more than $C$ children, and so the number of branches/leaves is at most $C\times C\times \dots C$ ($n$ times). In fact the actual number of branches is less than $C^n$, but is definitely bounded from above by $C^n$, and so is $O(C^n)$ (recall that big-O denotes the upper bound of a function).


How to query and update ranges of arrays? I have an array of size $N$ $(N \leq 10^5)$. I need to perform two types of operations on the array.

Decrease elements in range $[L,R]$ by $X$.
Count the number of negative elements in range $[L,R]$.

There are $10^5$ queries. All I can think about is using a segment tree with lazy propagation, but I believe there would be a better method. The segment tree method will probably time out because in case of alternate update/count queries, this will be close to linear.

Break the array up into $O(\sqrt{n})$ contiguous groups, each of size $O(\sqrt{n})$. With each group, store:

A balanced binary search tree (BBST) containing the values of the elements in the array as keys and a pointer to their location in the group as a value.
A modifier, $\delta$, indicating some offset that all of the elements have from $0$. For instance, if the elements are stored as $1,2,3$, but actually have the values $-11,-10,-9$, $\delta$ should be $-12$. The idea of $\delta$ is that decreasing the value of all of the elements in a group takes $O(1)$ time.
The array elements themselves in array order

To decrease the elements in a range $[R,L]$ where $R$ and $L$ are in the same group, just walk the array and update the BBST for each element. This takes $O(\sqrt{n} \lg n)$ time.

Te decrease the elements in an entire group at once, update $\delta$. This takes $O(1)$ time.

Every range contains $O(\sqrt{n})$ groups at most, and at most two of them are not wholly contained in the range - the end groups. Thus, to decrease a range $[R,L]$ takes $O(\sqrt{n} \lg n)$ total time

To count in a group, find the number of elements in the binary tree less than $-\delta$. This takes $O(\lg n)$ time in a BBST where the nodes are annotated by the sizes of their subtree.

To count in a part of a group, iterate over the array values in that part of the group and count how many are less than $-\delta$. This takes $O(\sqrt{n})$ time.

Again, every range contains $O(\sqrt{n})$ groups at most, and at most two of them are not wholly contained in the range - the end groups. Thus, to count a range $[R,L]$ takes $O(\sqrt{n} \lg n)$ total time


Does an algorithm exist that transforms any connected graph, cyclic or not, into tree form? I developed an algorithm that transforms any simple connected graph, cyclic or not, into a tree.
The resulting tree is syntax-preserving, in a sense that it allows to reconstruct the original input graph and only the original input graph. In other words, the constructed tree preserves adjacency information, while resolving cycles.
Moreover, I assume that with the constructed tree allowing to reconstruct only the original input graph, no other graph that is structurally different can exist that would result in an identical tree form.

I did some research on algorithms that transform graphs into tree form, but I was unable to find another algorithm that would work for any simple connected graph like described above.
However, I am pretty such there must exist something.

So maybe one more experienced in graph theory can help me out.
It would be highly appreciated.

Alex

In a general graph, the number of edges can go up to $\mathcal{O}(n^2)$ (where n is the number of verticies). But in a tree, that number is always $n-1$.

Then, we understand that its impossible to convert a graph to a tree preserving syntax without increasing the memory for each node by a linear factor, or increasing the number of nodes significantly.

Let us define a unique number for every node (in any way you like).

The algorithm now will be:

Let $\mathcal{T}$ be the tree from the BFS algorithm on the graph (starting from node 1, for uniqueness)
For every edge $e=(i,j)$ in the graph, that is not in $\mathcal{T}$ already, w.l.o.g assume $i\le j$, and add a new node with value $j$ to $\mathcal{T}$, and a connection between it and the (original) node $i$ in the tree.

Note that in the new tree, there will be a lot of nodes that have the same number.

To reconstruct the original graph, we will do the following:

Create a node for every unique number in $\mathcal{T}$.
Add an edge $(i,j)$ if there is a node with number $i$ that has an edge to some node with value $j$


Why is KMP preprocessing O(N)? My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from len_ = lps[len_- 1] .
def computeLPSArray(pat, M, lps):
    len_ = 0 # length of the previous longest prefix suffix

    lps[0] = 0 # lps[0] is always 0
    i = 1

    # the loop calculates lps[i] for i = 1 to M-1

    while i < M:
        if pat[i]== pat[len_]:
            len_ += 1
            lps[i] = len_
            i += 1
        else:
            # This is tricky. Consider the example.
            # AAACAAAA and i = 7. The idea is similar
            # to search step.
            if len_ != 0:
                len_ = lps[len_- 1]

                # Also, note that we do not increment i here
            else:
                lps[i] = 0
                i += 1

```

Each len_ = lps[len - 1] decreases $lps$ by at least 1, thus, it can only happen for lps[i - 1] + 1 - lps[i] times, since you initialize lps[i] as lps[i - 1] + 1. Therefore, the maximum number of times len_ = lps[len - 1] can happen is $\displaystyle \sum_{i=1}^n (lps[i - 1] + 1) - lps[i]$. As you know, $lps$ can increase by at most $n$ in total, therefore, it can decrease by at most $n$ in total, since $lps$ can never be negative, or equivalently, for each $+1$ $lps$ gets, it can get at most one $-1$. thus $\displaystyle \sum_{i=1}^n (lps[i - 1] + 1) - lps[i]$ will be $O(n)$.
I hope my answer was helpful.


3-coloring a graph with propositional formulas I am trying to tackle a specific problem so any help would be greatly appreciated:

Let $G = (V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. A 3-coloring of $G$ is a map $\chi:V\to \{R,G,Y\}$ such that if $\{x,y\}\in E$ then $\chi(x)\neq \chi(y)$. (Let $R,G,Y$ stand for red, blue, and yellow respectively).
Suppose $n > 1$ and let $V_n = \{0,1,\cdots,n-1\}$ and let $G_n = (V_n,E_n)$ be an undirected graph with vertex set $V_n$. For each $i$, $0 \leq i < n$ let $R_i,B_i,Y_i$ be propositional variables. We can think of $i$ being a node so $R_i$ says node $i$ has a color of red.
Give a propositional formula $A_n$ using the variables $\{R_i,B_i,Y_i | 0 \leq i < n\}$ such that $A_n$ is satisfiable iff $G_n$ has a 3-coloring. Do this in such a way that $A_n$ can be computed efficiently from $G_n$ (e.g. don't define $A_n$ to be $R_1$ if $G_n$ has a three coloring and ($R_1 \wedge \neg R_1$) otherwise).

My inclination for a question like this is to set up some sort of CNF formula, that is come up with a set of clauses that set out to take care of different properties. For instance I believe for something like this I need a clause that deals with the case that every node has a color, maybe one that deals with every node cannot have more than one color, and that every node cannot be the same color as an adjacent node? I am not really sure how to illustrate that last one or if there are cases that I am missing.

Hint: Try to formalize the following:

Every node has at least one color.
Every node has at most one color. (This is actually not necessary.)
Any two adjacent nodes cannot have the same color.

Another hint:

   The first can be formalized as $R_i \lor B_i \lor Y_i$ for all $i$.


Set of DAG vertices disconnecting a vertex from forbidden vertices Let $v$ be a vertex with in-degree 0 in an (acyclic) DAG $G$, and let $F$ be a subset of $G$'s vertices (the "forbidden") vertices. Now suppose $U$ is a set of vertices such that every path from $v$ to $F$ intersects $U$.

Is there a commonly-used term for such sets? I was thinking about using the term "Front", but a (cursory and lazy) search tells me that's not a popular term. I can't use "cut", because that's reserved for sets of edges with the similar property (cutting off $v$ from $F$; usually $F$ is the subgraph of all vertices reachable from $A$ but not in $A$).

Also, suppose that $U$ is minimal, in the sense that for every $u$ in $U$, there's a path from $v$ to $F$ which intersects no other vertex of $U$. Is there a commony-used term for this kind of sets?

If it helps, I'm willing to refer to $v$ as a "source" and to $F$ as the set of "sinks".

Wikipedia says that, for an undirected graph, you can say:

$A$ is the vertex separator for $v$ and $F$.
$A$ is the separating set for $v$ and $F$.
$A$ is the vertex cut for $v$ and $F$.

perhaps these terms are used for digraphs as well, even though "connected components" are not quite the same thing in digraphs.

edit:  @PålGD suggests the variant "separator", similar to the second option.


What's wrong with this "proof" that $\mathbb{R}$ is enumerable? The fake proof:

We know that $\mathbb{R}$ is uncountable, hence we cannot enumerate over it.
But what we do know is that $\mathbb{Q}$, the set of rationals, is countable, and even denumerable.
We also know that we can construct $\mathbb{R}$ through what are called Dedekind cuts.
We choose to let the partition itself denote a new number and go forth to define mathematical operations on it as to be compatible with the rest of the numbers (mainly $\mathbb{Q}$ and our new number $x$)

Sidenote: I think so far this is standard, and contains nothing false. The actual argument starts below this line.

Let us denote the set containing $x$ as $S_1 := \mathbb{Q}\cup\{x\}$. For convenience, the superscript of $S_1$ is how many new such numbers we have added through the cuts.

Since $\mathbb{Q}$ is countable, we can enumerate over every single rational $q\in\mathbb{Q}$ to produce an $r\in\mathbb{R}$. Do this process $n$ times and you end up with $S_n = \mathbb{Q}\cup{x_1}\cup{x_2}\cup\dots\cup{x_n}$.

But $S_n$ is also enumerable since it has a finite more elements than $\mathbb{Q}$.

Hence - After enumerating over the entirety of $\mathbb{Q}$ - Start enumerating over the entirety of $S_{|\mathbb{N}|}\setminus\mathbb{Q}$

Now we will end up with even newer numbers to put in our set, which we will now call $S_{n = |\mathbb{N}|,k}$ where $n$ represents the enumeration over $\mathbb{Q}$ and $k$ represents the enumeration over $S_{|\mathbb{N}|}\setminus\mathbb{Q}$. Do this ad infinitum and you will eventually describe $\mathbb{R}$.

I know I went wrong somewhere, I just don't know where.

"Do this ad infinitum and you will eventually describe $\mathbb{R}$."

The "ad infinitum" takes uncountably many steps to complete.


Getting output of dynamic programming, (contiguous sub array, box stacking) I am attempting to output the largest stack of boxes given an input of a set of boxes.
Currently I have an array called maxWeight that has the values of the boxes sorted from largest to smallest, this is the array being operated and changed, I then have another array that also has the values of the boxes going from largest to smallest.

 for(int i = 1; i < array.length; i++) {
     for(int k = 0; k < i; k++) {
          if(array[i].canStackOn(array[k])
             && maxWeight[i] < maxWeight[k] + temp[i].weight()) {
              maxWeight[i] = maxWeight[k] + array[i].weight();
              }
          }

  }

I am absolutely beating my brains out trying to find a way to keep track of each of the items added to the location of the largest sum on the array. Could anyone be so kind as giving pointers to a solution?

You are computing inductively an array maxWeight. The value of maxWeight at a certain point $i$ is the maximum over several possibilities. Currently you are remembering only the maximum itself. If you also store which possibility was maximum, then you will be able to use this additional information in order to construct an optimal solution.