Is the Source Coding Theorem straightforward for uniformly distributed random variables? Shannon's source coding theorem states the following:

  $n$ i.i.d. random variables $X_1,\dots,X_n$ each with entropy H(x) can be compressed into more than n⋅H(x) bits with negligible risk of information loss, as n→∞; conversely if they are compressed into fewer than n⋅H(x) bits it is virtually certain that information will be lost.

I was thinking about the easy case when the $X_1,\dots,X_n$ are uniformly distributed on the integers $[1,n]$. Now suppose I want to transmit a value of $(X_1,\dots,X_n)$.
Clearly, each $X_i$ has entropy $\log n$ and thus, if we were to send $o(n\log n)$ bits, we would lose information about some of the $X_i$, with high probability $1 - o(1)$.

The way to argue the Theorem for this case, is that it $\log n$ bits suffice to reconstruct any $X_i$, and conversely, if you receive, for example, only $(1/4)n\log n$ bits, then, you would need to correctly guess $3/4 n\log n$ bits, which happens with probability of only $2^{-3/4n\log n}$.
Is my reasoning correct?

The theorem you quote is not stated formally, so it is in fact impossible to prove it. That said, the idea behind the source coding theorem is that a variable of entropy $H(X)$ behaves (roughly) as if it was uniformly distributed on $2^{H(X)}$ values. When the distribution of $X$ is uniform, the theorem becomes trivial, once stated formally. So it's a good idea for you to look up a formal statement of the theorem, and then verify that it indeed holds for uniformly distributed random variables.


Padding a 2SAT clause In http://web.mit.edu/neboat/www/6.046-fa09/rec8.pdf, I see that they pad a 2SAT clause $(x\vee y)$ to make it a 3SAT clause by writing $(x\vee y\vee p) \wedge (x\vee y\vee \neg p)$. Why doesn't $(x\vee y\vee y)$ work instead? Isn't the truth table identical?

Sometimes we insist that the three literals in a 3SAT clause belong to different variables. This ensures, for example, that a random assignment satisfies a clause with probability exactly $7/8$. The translation $x \lor y \lor y$ doesn't satisfy this condition, but the other one does.


How do I select a subset such that the sum and the product are greater than some value? I have asked few days ago this question. Now I am simplifying the problem a little bit.

Given two sets $A=\{a_1,\ldots,a_n\}$, and $B=\{b_1,\ldots,b_n\}$ of non-negative integers, a positive integer $k<n$ and a positive integer $\Delta$. The question is: is there a subset of $S$ of $\{1,\ldots,n\}$ of size $|S|\leq k$ such that
$$\left(1+\sum_{i\in S}a_i\right)\left(1+\sum_{i\in S}b_i\right)\geq\Delta$$
Say no, if no such subset exists.
Note.$ \Delta$ is greater than $1$ and not big enough.

My question is:

How do I solve this problem? I do not know if this is an NP-complete problem or not. Do you see some hardness or reduction?

My attempt: First I failed to to prove that it is a hard problem. I tried to reduce from PARTITION but no way. I give up and I tried to design an algorithm. Here is my algorithm.

Choose $S=\emptyset$ and $P=0$
Choose the $i$ of the largest sum $a_i+b_i$ and add it to $S$
Let $j$ go from $1$ to $n$ except $i$ do

3.1. Add $j$ to $S$
3.2. Calculate the product above with $S=\{i,j\}$ and store it in $P$

Pick the $j$ with the highest $P$
Re-do this $k$ times.

In this algorithm optimal?

Note: The real question is about the hardness of the problem. Thanks.

Thanks to Yuval for the link. I think I can prove now that the problem, called PRODUCT, is NP-hard by a reduction from EQUAL-PARTITION, the variant of PARTITION in which we require both parts to have equal sizes.

Given an instance $\{x_1,\ldots,x_n\}$ of EQUAL-PARTITION (with $x_i > 0$ and $n$ is even), consider an instance of my problem with $k = n/2$, $\Delta=\left(1+nM/2+A/2\right)^2$ for large enough $M$ (i.e., $M = \max_i x_i$ ) and $A=\sum_{i}x_i$ , and let $a_i=M+x_i$ for all $i$ and $b_i=M+2A/n-x_i$ for all $i$.

This is a polynomial time reduction.

Now let us prove that EQUAL-PARTITION is solved $\iff$ PRODUCT is solved.

"$\Rightarrow$" Suppose that EQUAL-PARTITION is solved. Then there exists $S$ of size $|S|=n/2$ such that
$$
\sum_{i\in S}x_i=\sum_{i\in S'}x_i=A/2,
$$
where $S\cup S'=\{1,\ldots,n\}$ and $S\cap S'=\emptyset$ and $|S|=|S'|=n/2$.
Now take the solution to PRODUCT to be $S$. We have
\begin{align}
&\left(1+\sum_{i\in S}a_i\right)\left(1+\sum_{i\in S}b_i\right)\geq\Delta\\
\iff&\left(1+\sum_{i\in S}(M+x_i)\right)\left(1+\sum_{i\in S}(M+2A/n-x_i)\right)\geq\Delta\\
\iff&\left(1+nM/2+\sum_{i\in S}x_i\right)\left(1+nM/2+A-\sum_{i\in S}x_i\right)\geq\Delta\\
\iff&\left(1+nM/2+A/2\right)\left(1+nM/2+A/2\right)=\left(1+nM/2+A/2\right)^2\\
\end{align}
"$\Leftarrow$" Suppose that PRODUCT is solved. Then there exists $S$ of size $|S|=n/2$ such that
\begin{align}
\require{overset}
&\left(1+\sum_{i\in S}a_i\right)\left(1+\sum_{i\in S}b_i\right)\geq\Delta\\
\iff&\left(1+\sum_{i\in S}(M+x_i)\right)\left(1+\sum_{i\in S}(M+2A/n-x_i)\right)\geq\Delta\\
\iff&\left(1+nM/2+\sum_{i\in S}x_i\right)\left(1+nM/2+A-\sum_{i\in S}x_i\right)\geq\Delta\\
\iff&\left(\alpha+\sum_{i\in S}x_i\right)\left(\alpha+A-\sum_{i\in S}x_i\right)\geq\Delta\\
\iff&\alpha^2+\alpha A+A\sum_{i\in S}x_i-\left(\sum_{i\in S}x_i\right)^2\geq\Delta\\
\iff&\left(\sum_{i\in S}x_i\right)^2-A\sum_{i\in S}x_i+\Delta-\alpha^2-\alpha A\leq 0\\
\iff&X^2-AX+\Delta-\alpha^2-\alpha A\leq 0\\
\overset{(a)}{\iff}&X^2-AX+\Delta-\alpha^2-\alpha A= 0\\
\iff&X= A/2\\
\end{align}

Finally, PRODUCT is NP-hard.


New Idea for accessing memory across an inter-network connected system I have the following idea for a network-based operating system.

Suppose we have two computers A and B in a network. If computer B wants to access the memory of computer A, it can access by using the following addressing method which uses Media Access Control (MAC) address of the machines,

(MAC Address of target machine).(memory address on target machine)

This should work both ways as well as all the computers connected in a network. This will also remove the constraint of passing reference of variables in Remote Procedure Call (RPC).

Is the above method feasible ? What sort of modifications are required to make this possible, if feasible ?

NOTE:-I am also assuming that there is no MAC spoofing.

This would be an instance of a distributed shared memory architecture.  There's been lots of research on such systems.  I would recommend spending some quality time on Google Scholar to read relevant research papers on those kinds of systems, to learn about what's been tried so far.

You might also be interested in the literature on distributed in-memory databases, caches, and data stores.


Is longest-path with a specific source and destination impossible in polynomial time? The problem of finding the longest path in a graph is known to be not be possible in polynomial time, that I am aware of. I am also aware that using DFS or BFS can give the shortest distance between a given origin and destination in a graph. Is it possible to find a longest
path from a source vertex to a destination vertex in polynomial time?

The longest-path problem is $\mathsf{NP}$-hard even when a source vertex $s$ and a target vertex $t$ are specified. To see this, you can reduce an instance of (the decision version of) longest path on a graph $G =(V,E)$ with no source/destination specified to (the decision version of) this variant by:

Adding to $G$ a new path $\langle u_0, \dots, u_n \rangle$ of length $n = |V|$, and connecting $u_n$ to each of the vertices $v \in V$ via the edge $(u_n, v)$; and
Adding to $G$ a new path $\langle z_0, \dots, z_n \rangle$ length $n$, and connecting each of the vertices $v \in V$ to $z_0$ via the edge $(v, z_0)$.

Call the resulting graph $G'$. It is easy to see that there is path of length $k$ in $G$ if and only if there is path from $u_0$ to $z_n$ of length $2n + k$ in $G'$.

This shows that, if $\mathsf{P} \neq \mathsf{NP}$ your variant does not admit any polynomial-time algorithm.

If $\mathsf{P} = \mathsf{NP}$, then there is a polynomial time algorithm for the decision version of longest path (given a graph $G$,  two vertices $s$ and $t$, and an integer $k$, decide whether there is a path from $s$ to $t$ in $G$ of length at least $k$), which is $\mathsf{NP}$-Complete.

Your version of longest path can then solved in polynomial time by first finding the length $k$ of a longest path $P$ and then recursively guessing the next vertex of $P$: delete $s$ from $G$ and check, for every neighbor $u$ of $s$, whether there exists a path $P'$ from $u$ to $t$ in $G-s$. When you find a $u$ for which the answer is affirmative, solve the problem recursively on $G-s$ to find $P'$ and construct $P$ as $s \circ P'$, where $\circ$ denotes concatenation.


Regular expression for a binary string containing even number of 0's To get the regular expression I made a finite automata as the following (not sure if you can directly write regular expression without it):

The regular expression for the above according to me should be $(1+01^*0)^*$ but elsewhere I have seen it can be $(1^*01^*01^*)^*$. Why is it different?

(1∗01∗01∗)∗ is actually wrong because it doesn't handle a string consisting of all 1's


What are different ways to provide a semantics to a language? Suppose you have 1. a grammar for terms of a language; 2. type-assignment rules, 3. a set of reduction rules. You want to prove that your language is adequate for mathematical reasoning. If I understand correctly, the right way to do it is to develop a semantics for it, and then prove certain desirable properties such as soundness and consistency.

I've seen different approaches to this. Usually, a model in set theory is involved. But I believe that is not the only way to do it. Wouldn't, for example, an interpreter for that language on the untyped λ-calculus count as a semantics? So, my question is: what are the different ways to provide a semantics to language?

There are many possible approaches. Here's a few "classic" styles.

Operational semantics (e.g. small step / reduction, or big step)
Denotational semantics (e.g. domain-theoretic, or category-theoretic)
Axiomatic semantics (e.g. hoare logic)

You can also define the semantics of a language through a translation to another language (already having its semantics). CPS transforms could also be mentioned here.

Also note that many languages admit several distinct semantics. Lazy & eager semantics of functional programs are possible, for instance. Prolog also has many different semantics (I recall someone stating "there's no such a thing as THE semantics of Prolog").

Further, concurrent languages like CCS or $\pi$-calculus have a LTS semantics. Game semantics is also used sometimes (but I don't know much about it).

I'm pretty sure there are many other kinds of semantics. I'd be surprised if in the future someone does not invent a new kind of semantics.


Intuition for “run” function of monads I'm learning about monads, I understood why they are useful, I understood in general what bind, join, return do.

I also looked at basic usage examples for the basic reader / writer / state / list / maybe monads.

Still, being a beginner, I still don't feel I have a grip on what the "run" function means in general. It does not seem to have a generic signature like the above functions, and I don't get it if it's definable / makes sense for all monads.

Short answer:

There isn't a run-function for all monads, and its use is evaluating data structures.

Medium answer:

Certain monads build data structures that will be evaluated afterwards. Let's say we want to build our own IO monad (I'll need to use GADT notation, basically I just talk about inhabitants and their specific types):

data SimpleIO a where
  PutStr :: String -> SimpleIO ()
  GetLine :: SimpleIO String
  Bind :: SimpleIO a -> (a -> SimpleIO b) -> SimpleIO b
  Return :: a -> SimpleIO a

Like this, we can build a few IO actions, like one that just reads a string and prints it: Bind GetLine PutStrdoes exactly that.
However, our monad doesn't do anything: We don't know how to execute those actions, so we need some kind of conversion function:

runSimpleIO :: SimpleIO a -> IO a
runSimpleIO (PutStr x) = putStrLn x
runSimpleIO GetLine = getLine
runSimpleIO (Bind x f) = x >>= f
runSimpleIO (Return x) = return x

This is some kind of run function, it uses the monad-made structure to make use of it. It definitely isn't unique though: You might as well write a run function SimpleIO a -> Maybe a. That's nothing defined within the monad, but more of an interpretation.


Is there a name for the "tree" aproach to listing things? I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question.

Suppose we're trying to list all elements of the set $$C(r) = \{(x,y,z) \in \mathbb{N}^3 : \sqrt{x^2+y^2+z^2} \leq r\}.$$

An obvious approach would be this: first, list all integers between $0$ and $r$; these become our $x$-values. Then, for each $x$-value, list all integers between $0$ and $\sqrt{r^2-x^2}.$ These become our $y$ values. Then, for each $(x,y)$ pair, list all integers between $0$ and $\sqrt{r^2-x^2-y^2}$. These become our $z$ values. We can visualize this process as a tree; the branches of the tree are the elements of $C(r)$.

A similar approach can be applied to solve the Knapsack problem a little quicker than brute force. Begin by forgetting the value of each item and just focusing on its weight. Now go through the items from left to right, bifurcating each node into two as you go, so that one edge corresponds to "take the item" and the other corresponds to "don't take the item." If taking the item would send you overweight, you refrain from adjoining the edge that corresponds to taking the item, but you still adjoin the one corresponding to not taking the item. In the end, we get a binary tree whose branches can be viewed as subsets of the set of items, which ultimately means fewer numbers that need comparing.

Well, I can see my computer running out of memory pretty quickly trying to do this - I'm sure there's better approaches out there - but nonetheless, if there's a name for this kind of thing, I'd like to know it.

Your technique is known as exhaustive search (with some pruning). It consists of trying all possibilities. In many cases, the way to implement exhaustive search is using a search tree. There are several possible optimizations:

Tree pruning algorithms like A* avoid going through paths which are known to be suboptimal.
Greedy algorithms, when they apply, are able to make the correct choice at each step without going over all possibilities.
Dynamic programming corresponds, morally, to exploring a DAG instead of a tree, thus reducing the number of vertices explored. (The actual details are rather different.)


What is an upper bound of T(n) = 2 T(3n/10) + T(4n/10) + n if assume that T(n) = 2T(3n/10) + T(4n/10) + n <= cnlogn

T(n) <= 6cn/10 * log(3n/10) + 4cn/10 * log(4n/10) + n
= cn/10 * (6(log3 + logn - log10) + 4(log4 + logn - log10)) + n
= cn/10 * (10logn - 10log10 + 6log3 + 4log4) + n
= cnlogn - cn/10 * (10log10 - 6log3 - 4log4) + n <= cnlogn

because (10log10 - 6log3 - 4log4) > 0, there exists c that satisfy the equation.

I think it is the tight upperbound because I failed when I assumed the T(n)<=cn
so I think that upper bound of T(n) = O(nlogn)

am I doing right?

You can prove this using induction, but it will be messy. I'll show you a better approach below (unless you explicitly want to solve it  using induction).

Yes, the answer is $O(n \log n)$, which follows most easily using the Akra-Bazzi method. (This is a generalization of the better-known Master theorem, and is extremely useful for solving these types of recurrences.)

Clearly, the recursion satisfies the form from the statement of the Akra-Bazzi theorem: $g(x)=x$, and the constants $a_i$ and $b_i$ obviously satisfy the requirements.

In your case, $b_1=3/10$ and $a_1=2$; and $b_2=4/10$ and $a_2=1$. Thus $a_1\cdot b_1 + a_2\cdot b_2=1$, thus we take $p=1$. By the Akra-Bazzi theorem, the solution is $T(x) = O(x \cdot (1 + \int_1^x \frac{g(u)}{u^{p+1}} du))$. Because $p=1$ we are integrating the function $x/x^2=1/x$.

Since $\int_1^x \frac{1}{u} du = \log x$, we have that $T(x) = O(x (1 + \log x))$ which is $O(x \log x)$.

Using variable $n$ instead of $x$, we state this in more familiar notation: $T(n) = O(n \log n)$.

In fact, Akra-Bazzi gives us a stronger result that $T(n) = \Theta(n \log n)$, from which it immediately follows that $T(n) = O(n \log n)$. This is because $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ AND $f(n) = \Omega(g(n))$.


What are some of the practical applications of functions that extract the exponent and mantissa of a floating point number? I'm talking about functions such as Python's math.frexp() :

  math.frexp(x)

  Return the mantissa and exponent of x as the pair (m, e). m is a float
  and e is an integer such that x == m * 2**e exactly. If x is zero,
  returns (0.0, 0), otherwise 0.5 <= abs(m) < 1. This is used to “pick
  apart” the internal representation of a float in a portable way.

  https://docs.python.org/3.4/library/math.html

And:

  In some applications it is useful it obtain the mantissa and exponent
  of floating point numbers.
  http://www.technicalc.org/tiplist/en/files/pdf/tips/tip6_58.pdf

That said, what would be the usefulness of functions such as math.frexp() in real-world applications? What can I use it for?

They are among other things very useful for calculating logarithms, or square roots and cubic roots.

For example: log x = log ($2^e * m$) = e * log 2 + log m. With 0.5 ≤ m ≤ 1, you can approximate log m using a polynomial, which wouldn't work for x which can be in the complete range of floating point numbers.

$x^{1/3}$ = $(2^e * m)^{1/3}$. Let e = 3k, 3k+1, or 3k+2, then this equals $2^k * m^{1/3}$ for 0.5 ≤ m ≤ 4. You can either use approximation by a polynomial for m, or you use Newton iteration which will be much faster for m in the small interval.


Square sub-grid with maximum sum Given $N$ points in a grid having some weight, I have to find the side length of a square sub-grid with maximum sum of weight of points contained in that square sub-grid. Also square sub-grid must have side length less than $L$ (given integer).

$ 1\le N \le 100000$, $1 \le L \le 100000$ , $1 \le x_i \le100000$, $1 \le y_i \le 100000$, $1 \le \text{weight}_i \le 10^9$, where $i$ is the $i^{th}$ point.

I have tried using prefix sum array and iterating over all the possible square sub-grids, but this is not efficient.

I need to know in which direction should I start thinking.

Firstly you did not write the complete question, to complete it, if $S$ is the maximum sum of weights in any sub-grid of lenght $ \le L$, then we have to report $S$ and length of the sub-grid with smallest integral side where sum of weights inside it is $S$ ( hint: it won't change the complexity of the solution ). But that is slight detail which I leave to you to figure out. In this answer my aim is to calculate $S$.

Now we come to some pre-requisites for solving the problems. Firstly you should be comfortable with segment tree implementation. Second you need familiarity with binary search. Lastly I also assume ( as you have mentioned ) you also have familiarity with computing the prefix/suffix sum arrays. Plus I assume the points are given in the array $arr$ .

Now I describe the algorithm.

It can be argued that one of the corner points of the square sub-grid we make should be a point from the set of points that is given to us. Thus for each point from $(x,y)$ from the set of points given to us, we consider the four possible squares, one with $(x,y)$ as bottom left corner, one with $(x,y)$ as top right corner, one with $(x,y)$ as bottom right corner and one with $(x,y)$ as bottom left corner.
I describe it for one case say when $(x,y)$ is bottom left corner of a square grid with size $L$ ( as to calculate $S$ we should take the side of the square sub-grid as long as possible which is $L$ ). That is our question reduces to finding the sum of weights of points in the red region in the figure below.
I have labelled the sum of weights of the other eight regions by using letters $a$-$h$. One way to calculate the sum of weights of the red region is to subtract the from total $a+b+c+d+e+f+g+h$.
I can calculate $b+a+h$ by using combination of binary search and prefix/suffix sum arrays. In a similar manner I can find the sums $b+c+d$,$d+e+f$ and $h+g+f$. But now the problem is that I have summed each of $b$,$h$,$d$ and $f$ twice. Thus I need to find the sum of weights $b$,$h$,$d$ and $f$ separately.
You can find the sum $h$ ( and similarly the three others ) using segment tree in $O(log(n)^2)$ where $n$ is the total number of points given. The trick is to build the segment tree on say the $x$ co-ordinate. And if there is a node
in the segment tree denoting the range $i$-$j$ ( $1 \le i \le j\le n$ ) then that node should store the $y$ co-ordinates of all points of array $arr$ from index $i$ to $j$ in sorted order, plus a suffix sum array for the same sorted array ( this is the main point, comment if you can't understand ). In this way by combination of querying on segment tree and binary search ( thus the $O(log(n)^2)$ factor comes ) you can find the sum of weights $h$.
So in nutshell you repeat the procedure for each point from the given set and for each point you try all $4$ square-sub grids of length $L$ and then select the one having maximum sum of the red region overall. The complexity will come out to be $O(nlog(n)^2)$ which is sufficient to pass the online judge.


Timely lower bounded Turing machines Let M be a deterministic Turing machine wich has the properties:

1) $\forall x,y \in \Sigma^* : t_M(xy) \ge t_M(x) + t_M(y)$

2) $\forall a \in \Sigma: t_M(a) \ge 1$
 (Also 2) should be obvious for every DTM).

Then it follows that for all $x \in \Sigma^* : t_M(x) \ge |x| $.
The graph $G_M$ induced by the transition function contains a cycle:
To see this choose a word $w$ whose length $|w|$ is $> |Q|$ where $Q$ is the set of states of $M$. Then we have $t_M(w) \ge |w| > |Q|$. Since $M$ is at every time step on exactly one state, $M$ must visit in $t_M(w) > |Q|$ time steps one state at least twice, hence the graph $G_M$ must contain a cycle.

My question is this:
Can we construct to every DTM $M'$ an equivalent DTM $M$ with the properties above?
In my intuition this is possible: Just construct $M$ such that it reads all the input, writes what it has read, move the pointer to the beginning of the word and then gives control to $M'$. But is it possible to give a more formal proof for this? Or is my intuition wrong?

Use the following recursive procedure to construct $M'$ from $M$:

Run $M'$ on all non-trivial prefixes and suffixes of the input (if any), and ignore the results.
Run $M$ on the entire input, and output the result.

If $M$ always terminates, so does $M'$. The first step guarantees your first condition. The second condition is virtually automatic.


Number of inversions in an array of pairs of integers I have a problem like this:
we have an array of elements like this :
(a0,b0)
(a1,b1)
.
.
.
(an,bn)

and I wanna find the number of elements which have one of this two condition:
1) if ai>aj and bi<bj then:count:=count+1
or
2) if ai<aj and bi>bj then:count:=count+1
I've already found an algorithm that is $O(n^2)$, but I need the  faster algorithm.
Example:
suppose we have this:
(1,5)
(4,7)
(8,2)

I wanna find the number of time that condition satisfied, so
1<8 and 2<5 so condition is satisfied but 1<4 and 5<7 so condition is
not satisfied.

You can visualize the problem like so (using a = [1,4,8], b = [5,7,2]):

As you can see, I have sorted a, with each element pointing to a position in b sorted in reverse. All we need to do now is iterate over a, counting how many previous indices were lower than us. We can can compute that with a Fenwick tree, all in $O(nlog(n))$. Here is a python implementation:
import bisect

def query(bit, i):
    ret = 0
    while i > 0:
        ret += bit[i]
        i -= i & -i
    return ret

def update(bit, i, delta):
    while i < len(bit):
        bit[i] += delta
        i += i & -i

def csFindInversions2(a, b):
    assert len(a) == len(b)

    def solve(a, b):
        tmp = sorted(b)
        lut = [
            len(b) - bisect.bisect(tmp, b[i])
            for i in sorted(range(len(a)), key=lambda i: a[i])
        ]
        bit = [0]*(len(a) + 1)
        ret = 0
        for i in lut:
            ret += query(bit, i)
            update(bit, i+1, 1)
        return ret
    return solve(a, b) + solve(b, a)

Note that this solution does not account for duplicates.


Hyper parameter and complexity in $K$ nearest neighbors I'm wondering if choosing K in the Nearest Neighbors Classifier can be stated as model selection, since the computational complexity is getting higher, the higher K is.

My understanding is: since the complexity increases it means, that K is a hyper parameter.

Am I getting the concept of hyper parameters correctly?

First let's define what a hyper parameter is. In the context of statistical learning, a hyper parameter is a fixed constant that describes the prior distribution for a model's parameters. For example, if $X \sim \text{Binomial}(n,p)$ and $p \sim \text{Beta}(\alpha, \beta)$, then $\alpha, \beta$ would be hyper parameters where $n, p$ would be the "parameters" (I use quotes because $p$ is a random variable now).

$k$NN is  non-parametric in the sense that you aren't explicitly modeling your data as a function of underlying parameters. $k$ only describes how many neighbors to "learn" from. As $k$ increases the computational complexity can increase; however, it doesn't explicitly control the complexity of the model. An example where model size $k$ acts as a hyper parameter is linear regression. Imagine trying to determine a-priori which $k$ of the $N$ features you would like to select for inclusion in the model.

Given this, I would not say that $k$ describes $k$NN model complexity in the sense that typical Bayesian model selection is and therefore should not be viewed as a hyperparameter.


In which category is the supercomputer SUMMIT according to Flynn's taxonomy? I have read that the POWER9 processor is an SIMD processor.
I have also read that most supercomputers are MIMD based.

So is the SUMMIT supercomputer SIMD? And if it is can you name a supercomputer that is MIMD?

Summit is a parallel system that apparently contains many nodes, where each node is powered by one or more POWER9 processors.  Each POWER9 processor contains a vector scalar unit that Wikipedia says can be described as a SIMD unit.  However, the Summit system as a whole would normally be used in a MIMD mode, as each POWER9 processor can run a separate program. It doesn't have to -- you could run the same code on each node, or different code on each node -- but each node runs asynchronously and independently, so I would classify the entire system as MIMD.


How is tamper-proofing of software evaluated for effectiveness? How is tamper-proofing of software evaluated for effectiveness?

I've been implementing a few algorithms listed within Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection. The algorithms include tamper-proofing of software by means of introspection (or computing a hash at runtime over some region of code).

However, nothing is said about the evaluation of such tamper-proofing algorithms: How are they compared to each other and how are their effectiveness measured?

Searching Google, I've come across few articles discussing the subject. One of the articles made an emperical evaluation, where they asked "hackers" to break their implementation and then measured the time taken.

Does anyone know how to evaluate tamper-proofing at a theoretical level?

Unfortunately, we don't know of any way to reliably measure the effectiveness of software obfuscation schemes (or the security of pretty much anything else).  The best we can do is publish the scheme, wait for other researchers to try to attack it, and see what the best attacks that someone has been able to find are.

As you can imagine, there are many limitations and caveats with that approach.  How do we know whether anyone has tried to break it, or whether the right people with the right skills have tried?  Or maybe there is some devastating attack that no one has thought of yet, but might be discovered tomorrow.

Anyway, that's the approach typically taken in practical work on software obfuscation.  There is also theoretical work on software obfuscation, which tries to prove security theorems (under some complexity-theory assumptions about the hardness of some well-studied problems).  Unfortunately, at present there is a significant gap between practice and theory.  For the most part, the provably secure schemes aren't practical, and the practical schemes aren't provably secure.  There are exceptions, but they tend to be very special-purpose -- they can only obfuscate a small class of special programs -- and can't be used to obfuscate an arbitrary program.  The theoretical work is very interesting and has made many advances but still has a way to go before we can find a truly practical, provably secure, and general scheme for software obfuscation.

Finally, if you are interested in practical schemes for practical use, let me share one last caveat.  My personal perspective is that none of the practical schemes for software obfuscation appear to be terribly secure.  They provide a speedbump that will slow down an attacker or require some effort and skill to break, but I would not expect any of them to resist a dedicated, motivated attacker.  So, while they're fine if you just want to increase the cost of reverse-engineering, I wouldn't rely on them to hold up to serious attack.  That's just my own personal sense and opinion, which others in the field might not agree with.


What is coinduction? I've heard of (structural) induction. It allows you to build up finite structures from smaller ones and gives you proof principles for reasoning about such structures. The idea is clear enough.

  But what about coinduction? How does it work? How can one say anything conclusive about an infinite structure?

There are (at least) two angles to address, namely, coinduction as a way of defining things and as a proof technique.

  Regarding coinduction as a proof technique, what is the relationship between coinduction and bisimulation?

First, to dispel a possible cognitive dissonance: reasoning about infinite structures is not a problem, we do it all the time. As long as the structure is finitely describable, that's not a problem. Here are a few common types of infinite structures:

languages (sets of strings over some alphabet, which may be finite);
tree languages (sets of trees over some alphabet);
execution traces of a non-deterministic system;
real numbers;
sets of integers;
sets of functions from integers to integers; …

Coinductivity as the largest fixpoint

Where inductive definitions build a structure from elementary building blocks, coinductive definitions shape structures from how they can be deconstructed. For example, the type of lists whose elements are in a set A is defined as follows in Coq:

Inductive list (A:Set) : Set :=
  | nil : list A
  | cons : A -> list A -> list A.

Informally, the list type is the smallest type that contains all values built from the nil and cons constructors, with the axiom that $\forall x \, y, \: \mathtt{nil} \ne \mathtt{cons} \: x \: y$. Conversely, we can define the largest type that contains all values built from these constructors, keeping the discrimination axiom:

CoInductive colist (A:Set) : Set :=
  | conil : colist A
  | cocons : A -> colist A -> colist A.

list is isomorphic to a subset of colist. In addition, colist contains infinite lists: lists with cocons upon cocons.

CoFixpoint flipflop : colist ℕ := cocons 1 (cocons 2 flipflop).
CoFixpoint from (n:ℕ) : colist ℕ := cocons n (from (1 + n)).

flipflop is the infinite (circular list) $1::2::1::2::\ldots$; from 0 is the infinite list of natural numbers $0::1::2::\ldots$.

A recursive definition is well-formed if the result is built from smaller blocks: recursive calls must work on smaller inputs. A corecursive definition is well-formed if the result builds larger objects. Induction looks at constructors, coinduction looks at destructors. Note how the duality not only changes smaller to larger but also inputs to outputs. For example, the reason the flipflop and from definitions above are well-formed is that the corecursive call is guarded by a call to the cocons constructor in both cases.

Where statements about inductive objects have inductive proofs, statements about coinductive objects have coinductive proofs. For example, let's define the infinite predicate on colists; intuitively, the infinite colists are the ones that don't end with conil.

CoInductive Infinite A : colist A -> Prop :=
  | Inf : forall x l, Infinite l -> Infinite (cocons x l).

To prove that colists of the form from n are infinite, we can reason by coinduction. from n is equal to cocons n (from (1 + n)). This shows that from n is larger than from (1 + n), which is infinite by the coinduction hypothesis, hence from n is infinite.

Bisimilarity, a coinductive property

Coinduction as a proof technique also applies to finitary objects. Intuitively speaking, inductive proofs about an object are based on how the object is built. Coinductive proofs are based on how the object can be decomposed.

When studying deterministic systems, it is common to define equivalence through inductive rules: two systems are equivalent if you can get from one to the other by a series of transformations. Such definitions tend to fail to capture the many different ways non-deterministic systems can end up having the same (observable) behavior in spite of having different internal structure. (Coinduction is also useful to describe non-terminating systems, even when they're deterministic, but this isn't what I'll focus on here.)

Nondeterministic systems such as concurrent systems are often modeled by labeled transition systems. An LTS is a directed graph in which the edges are labeled. Each edge represents a possible transition of the system. A trace of an LTS is the sequence of edge labels over a path in the graph.

Two LTS can behave identically, in that they have the same possible traces, even if their internal structure is different. Graph isomorphism is too strong to define their equivalence. Instead, an LTS $\mathscr{A}$ is said to simulate another LTS $\mathscr{B}$ if every transition of the second LTS admits a corresponding transition in the first. Formally, let $S$ be the disjoint union of the states of the two LTS, $L$ the (common) set of labels and $\rightarrow$ the transition relation. The relation $R \subseteq S \times S$ is a simulation if
$$ \forall (p,q)\in R, %\forall p'\in S, \forall\alpha\in L,
   \text{ if } p \stackrel\alpha\rightarrow p'
   \text{ then } \exists q', \;
   q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R
$$

$\mathscr{A}$ simulates $\mathscr{B}$ if there is a simulation in which all the states of $\mathscr{B}$ are related to a state in $\mathscr{A}$. If $R$ is a simulation in both directions, it is called a bisimulation. Simulation is a coinductive property: any observation on one side must have a match on the other side.

There are potentially many bisimulations in an LTS. Different bisimulations might identify different states. Given two bisimulations $R_1$ and $R_2$, the relation given by taking the union of the relation graphs $R_1 \cup R_2$ is itself a bisimulation, since related states give rise to related states for both relations. (This holds for infinite unions as well. The empty relation is an unintersting bisimulation, as is the identity relation.) In particular, the union of all bisimulations is itself a bisimulation, called bisimilarity. Bisimilarity is the coarsest way to observe a system that does not distinguish between distinct states.

Bisimilarity is a coinductive property. It can be defined as the largest fixpoint of an operator: it is the largest relation which, when extended to identify equivalent states, remains the same.

References

Coq and the calculus of inductive constructions

Yves Bertot and Pierre Castéran. Interactive Theorem Proving and Program Development — Coq'Art: The Calculus of Inductive Constructions. Springer, 2004. Ch. 13. [website] [Amazon]
Eduardo Giménez. An application of co-inductive types in coq: verification of the alternating bit protocol. In Workshop on Types for Proofs and Programs, number 1158 in Lecture Notes in Computer Science, pages 135–152. Springer-Verlag, 1995. [Google Books]
Eduardo Giménez and Pierre Castéran. A Tutorial on [Co-]Inductive Types in Coq. 2007. [PDF]

Labeled transition systems and bisimulations

Robin Milner. Communication and Concurrency. Prentice Hall, 1989.
Davide Sangiorgi. On the origins of bisimulation and coinduction. ACM Transactions on Programming Languages and Systems (TOPLAS), volume 31 issue 4, May 2009. [PDF] [ACM] Associated course slides: [PDF] [CiteSeer]
Davide Sangiorgi. The Pi-Calculus: A Theory of Mobile Processes. Cambridge University Press, 2003. [Amazon]

More references suggested by Anton Trunov

A chapter in Certified Programming with Dependent Types by A. Chlipala
D. Sangiorgi. "Introduction to Bisimulation and Coinduction". 2011. [PDF]
D. Sangiorgi and J. Rutten. Advanced Topics in Bisimulation and Coinduction. Cambridge University Press, 2012. [CUP]


Must a decision problem in $NP$ have a complement in $Co-NP$, if I can verify the solutions to in polynomial-time? Goldbach's Conjecture says every even integer $>$ $2$ can be expressed as the sum of two primes.

Let's say $N$ is our input and its $10$. Which is an integer > 2 and is not odd.

Algorithm

1.Create list of numbers from $1,to~N$

2.Use prime-testing algorithm for creating a second list of prime numbers

3.Use my 2_sum solver that allows you to use primes twice that sum up to $N$

for j in range(list-of-primes)):
  if N-(list-of-primes[j]) in list-of-primes:
   print('yes')
   break

4.Verify solution efficently

if AKS-primality(N-(list-of-primes[j])):
    if AKS-primality(list-of-primes[j]):
        print('Solution is correct')

5.Output

yes 7 + 3
Solution is correct

Question

If the conjecture is true, then the answer will always be Yes. Does that mean it can't be in $Co-NP$ because the answer is always Yes?

I think you might be confusing a couple of things.

First, the complement of any problem in NP is in CoNP by definition. No further conditions are required. Second, admitting a polynomial time algorithm to verify solutions, and belonging to the class NP, are equivalent statements.

Third, Goldbach's conjecture is a mathematical statement, which under standard axioms is either true or false. That means that as a decision problem, in the same fashion that any other mathematical statement, Goldbach's conjecture has a constant time solution: machine A answers "true", machine B answers "false". Necessarily one of them is right, and they both take constant time. Obviously this is not helpful at all.

So you probably meant to ask about the problem that given an even integer N > 2 asks you to decide whether it can be expressed as the sum of two primes. This problem is indeed in NP as you said, because if N = p + q for primes p, q. Then $\left<p,q\right>$ is a solution that can be verified in polynomial time, by using the poly-time algorithm to first check that p and q are indeed primes, and then any addition algorithm. I don't know if there is a polynomial time algorithm for this problem, but I wouldn't be surprised if there is one.

If Goldbach's conjecture is true, then the machine that answers "yes" without even looking at the input accepts the language described above and runs in constant time.


Relationship between dependent sum type and dependent product type? Since dependent sum type ($\sum_{n\in \mathbb{N}} P(n)  $) is interpreted as ($\exists n\in \mathbb{N}:P(n) $) and dependent product type ($\prod_{n\in \mathbb{N}} P(n)$) is interpreted as ($\forall n\in \mathbb{N}:P(n)$), is it correct to say that an element of dependent product type represents a set(in a vague way) of elements of corresponding dependent sum type for every n?

I believe you meaning the following.

A value of type $\prod_{n : \mathbb{N}} P(n)$ is a function which takes a value $n$ of type $\mathbb{N}$ as input and outputs a value of type $P(n)$. So the domain of such a function is $\mathbb{N}$. What is its codomain? Well, the type of the result depends on the value of the input, which is why it's called a dependent product. So it doesn't really have a codomain in the traditional sense.

But we can also view this situation as follows: Yes, such a function $f$ has a codomain, namely the dependent sum $\sum_{m : \mathbb{N}} P(m)$; but with the condition imposed that $(\mathsf{fst} \circ f)(n) = n$ for all $n : \mathbb{N}$, where $\mathsf{fst} : \sum_{m : \mathbb{N}} P(m) \to \mathbb{N}$ is the first projection.

More precisely, the following types are indeed equivalent ("equivalent" as in the HoTT book):

$\prod_{n:\mathbb{N}} P(n)$
$\prod_{f : (\mathbb{N} \to (\sum_{m : \mathbb{N}} P(m)))} \prod_{n:\mathbb{N}} ((\mathsf{fst} \circ f)(n) = n)$ (the type of functions satisfying the stated condition)


How rule 110 would be proven to be universal if the tag system did not exist? I was reading about Cellular Automata and I read in this question that
Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system.  Is there another method or information that would still prove the universality of rule 110?  In other words, is there another way to to do that without considering tag systems, and if so, can you explain the proof or give a reference to it?

More a bunch of references than an answer ....  :-)
As said by @vzn in its comment Cook's proof is very complex and required a lot of work; nevertheless the universality of rule 110 renewed the interest on small model of computations.

Among the most notable results was the proof that rule 110 can simulate a deterministic Turing machine efficiently, i.e. with only a polynomial-time slowdown:

Turlough Neary, Damien Woods: P-completeness of Cellular Automaton Rule 110. ICALP (1) 2006: 132-143
Damien Woods, Turlough Neary: On the time complexity of 2-tag systems and small universal Turing machines. FOCS 2006: 439-448

Along the direction of a simplified/different proof of the universality of rule 110, you can find some work, e.g.:

Richard G.:  Rule 110: universality and catenations. In: Durand B
(ed) Proceedings of the first symposium on cellular automata "Journees
Automates Cellulaires", pp 141-160 (2008)
Juan Carlos Seck Tuoh Mora, Genaro Juárez Martínez, Norberto Hernandez-Romero, Joselito Medina Marín: Elementary cellular automaton Rule 110 explained as a block substitution system. Computing 88(3-4): 193-205 (2010)

For a good survey on universality in cellular automata and other ideas for proving universality:

Nicolas Ollinger: Universalities in Cellular Automata*. Handbook of Natural Computing pp 189-229

Finally a *personal* idea on an alternative approach that could be investigated:

Proving universality of larger CAs (with larger neighbourhood or more states) is much easier and you can even get rid of the intermediate tag-system simulation, so you could investigate if using rule 110 gliders it is possible to simulate an arbitrary larger CA; a slightly similar approach has been used by Nicolas Ollinger and Gaétan Richard in A Particular Universal Cellular Automaton to prove the universality of colliding particles systems (they prove that a particular system can simulate an arbitrary CA)

And don't forget that instead of working on a different proof for rule 110 universality, you can work on the open problem  regarding rule 54 ... is it (weakly) universal ? :-)


How does one find a non-quadratic residue modulo $p$? I was wondering how one can find a non-quadratic residue modulo $p$ and what the runtime of this algorithm would be.

I thought that one can use the Legendre Symbol

$$ \left( \frac{a}{p} \right) = a^{ \frac{(p-1)}{2} } \pmod p $$

if the Legendre Symbol returns -1 then its a non quadratic residue and if its a quadratic residue it would return 1. To do this it's easy find a randomized algorithm, since only half the elements are quadratic residues, then one guesses any element at random, say $a \in Z^*_p$ and if the Legendre Symbol returns -1 the return success. Since half the elements are not quadratic residues, it would take about 2 iterations in expectation to find one.

I was wondering, is this algorithm correct? It seems that its completely symmetrical for finding quadratic residues. I am not sure that is strange, but it seems weird to me. Is it correct that the two algorithms are basically the same?

You are completely right, and your algorithm is a randomized polynomial time algorithm for finding a quadratic non-residue modulo a prime. A major open question in algorithmic number theory is finding a quadratic non-residue deterministically in polynomial time. This is possible assuming the generalized Riemann hypothesis, but unknown unconditionally. It is also equivalent to extracting square roots modulo a prime. This is all explained in notes by Booher.


Primes not dividing sequence $a_{n+1} = 1 + a_0 a_1 \cdots a_n$ Prove that there are infinitely many primes that divide none of the elements of the integer sequence
$a_{n+1} =1+a_0 a_1 \cdots a_n$, with a starting point of $a_0 \geq 0$.

I thought about $$\log (x_n-1)=\log x_0x_1\cdots x_{n-1}= \log x_0 + \log x_1 +\cdots+\log x_{n-1} $$ to solve the problem but couldn't.

Let me write it here, because I had a typo in the comment.
First observe that
$$
\begin{align}
a_{n+2}&=1+a_0a_1\dotsm a_na_{n+1}\\
&=1+a_0a_1\dotsm a_n(1+a_0a_1\dotsm a_n)
\end{align}$$
So $$4a_{n+2}=(2a_0a_1\dotsm a_n+1)^2+3$$
This implies that for an odd prime $p$ that divides $a_{n+2}$, we must have that $-3$ is a quadratic residue modulo $p$. By quadratic reciprocity, $-3$ is a quadratic residue modulo $p$, when $p$ itself is a quadratic residue modulo $3$. Therefore, any odd prime of the form $3K+2$, with $K\in\mathbb{Z}$ doesn't have $-3$ as quadratic residue and  cannot divide $4a_{n+2}$ for any $n\geq0$.
Since there are infinitely many primes of the form $3K+2$ (see here for example), then an infinite collection of primes that don't divide any of the elements of the sequence are the primes of the form $3K+2$, excluding from them $2$, the primes that divide $a_0$ and the primes that divide $a_1$.


How to draw Turing machine for multiplying a number by 2 in base 10 I'm trying to design a turing machine that given a number in base 10 multiplies it by 2.
The problem seems trivial if the number is represented in binary so what I've thought is try to convert it from base 10 to base 2, multiply it by 2 and convert it again.
But I'm not quite sure if I'm taking the wrong path or not. Maybe there is a simpler way. Any hints or suggestions?

To elaborate on the method described by Yuval in the comment, first, construct a DFA with output as follows: Let the state space be $Q=\{q_i \mid 0 \le i \le 9\}$, and input and output alphabet be $\Sigma = \{i \mid 0 \le i \le 9\}$. The initial state would be $q_0$. Let the DFA read the decimal number in reverse. For any state $q_i$, on reading $d$, you move to state $q_j \in Q$ and output $k \in \Sigma$ if $10j + k = 2d + i$ (Why can you always find such $j,k$?).
Basically, you are trying to store the carry while outputting the least significant digit of the multiplication of the current digit by 2 after adding the last carry, just as the grade-school multiplication.
Then, you can readily create a TM using this DFA with output that does the required multiplication.


What happens when ε-clos(X) contains duplicate elements? Example: (1+0)*1 I am learning about state machines from the Stanford online cs143 course. Here I have tried to build a nondeterministic finite automaton for the regular expression (1+0)*1, but when I attempt to convert it to a DFA I find that the epsilon closure of the initial state A ends up having two outputs for the value 1, which I imagine would be impossible for a deterministic automaton.

I understand that my NFA differs from the instructors, but I'm unsure of whether or not it is valid. If it is valid, why am I having difficulty converting it to a DFA?

Yes, your NFA is correct. You are probably making some mistake during your conversion to a DFA.

Note that after the conversion from the NFA to the DFA, the states will no longer be $S = \{A,B,C,D,E\}$. Instead they will be all possible subsets of $S$. So in your case $A$ is not giving two different transitions to $C$ and $E$, instead it is giving one single transition to the state $\{C,E\}$


Feeling guilt tripped in linked list Okay, so I have been doing competitive programming for the past few days in C++. And day before yesterday, I stumbled upon this concept of linked list.

Now, what I do while implementing most problems pertaining to linked list is that I store all the values of the linked list nodes in a vector, and do operations on them which has been asked as per the question, then refill the nodes with the newly updated values of the vector. Now, most of the questions can be done by me really easily, as I am pretty comfortable with using vectors now. I just wanted to ask this community if this was a bad approach towards using linked list, and should I stop using it altogether.

I will give an example to sort a linked list in $O(N\log N)$ time, which I used. Following is a function that sorts a linked list-

ListNode* Solution::sortList(ListNode* A) {
    vector<int> vect;
    ListNode* temp=A;
    while(A!=NULL)
    {
        vect.push_back(A->val);
        A=A->next;
    }
    A=temp;
    sort(vect.begin(), vect.end());
    for(int i=0; i<vect.size(); i++)
    {
        A->val=vect[i];
        A=A->next;
    }
    return temp;
}

Let's show that $\{a^n b^n : n \geq 0\}$ is not regular using Myhill's criterion (there are infinitely many equivalence classes):

  The pumping lemma shows that $\{a^n b^n : n \geq 0\}$ is not regular. According to Myhill's criterion, if a language is not regular then it has infinitely many equivalence classes. Therefore the language has infinitely many equivalence classes, and consequently, by Myhill's criterion is not regular.

This may sound silly, but it is very similar to how you are using vectors to solve questions "using linked lists".

The alternative is to look for algorithms that can be implemented directly on linked lists. For example, one sorting algorithm which can be implemented directly is merge sort. Merge sort consists of the following operations:

Divide the input into two sublists of nearly equal size. Easy to do on a linked list using a simple scan.
Recursively sort each sublist.
Merge the two sorted sublists. The merge algorithm is also easy to implement on a linked list.

In contrast, an algorithm like quicksort seems hard to implement directly without having random access.


What is language of repeat(L) = {ww | w ∊ L}? What is language of repeat(L) = {ww | w ∊ L} ?

My try:
I know it {ww | w ∊ (a,b)*} is context sensitive language. Here , what is meant by "repeat(L)" ?  Can you explain it ? It is not a homework question.

$repeat(\cdot)$ is an operator on languages. It takes as an input a language $L$, and outputs a language defined by $\{ xx \mid x \in L\}$. That is, for any word $x\in L$ the string $xx$ will be in the output language $repeat(L)$.
A Few examples:

$L=\{ 0,00, 11\}$  =>  $repeat(L) = \{ 00,0000,1111\}$
$L=\{ \}$   => $repeat(L) = \{ \}$
$L=\Sigma^*=\{\epsilon,0,1,00,01,10,11,...\}$ => $repeat(L)= \{\epsilon, 00,11,0000,0101,1010,1111,...\}$


Hardness of $2$ edge-disjoint spanning trees decomposition The question is clear from the title. What is the complexity of the following decision problem:

Input: An undirected graph $G(V, E)$
Output: $\mathrm{YES}$ if $G$ can be decomposed into two edge-disjoint spanning trees, $\mathrm{NO}$ otherwise

Your problem is in $\mathrm{NP} \cap \mathrm{co}$-$\mathrm{NP}$.

First, it is obviously in $\mathrm{NP}$. The verifier receives the certificate consisting of two edge-disjoint spanning trees that consumes all the edges in $\mathrm{E}$

Second, by Tutte & Nash-Williams theorem [1], your problem is also in $\mathrm{co}$-$\mathrm{NP}$. The co-nondeterministic machine guesses any partition $\mathrm{P}$ of $\mathrm{V}$ and check that $|\mathrm{E}_\mathrm{P}(\mathrm{G})| \geq 2(|\mathrm{P}| - 1)$. Also, it must check that $|\mathrm{E}| = 2(|\mathrm{V}| - 1)$ to be sure that the tree packing of the above theorem is indeed a decomposition by trees.

[1] Tomas Kaiser, A short proof of the tree-packing theorem, https://arxiv.org/pdf/0911.2809.pdf


shortest notation for "set of all maps from $A$ to $B$"? I usually write the following:

$$\{m| m:A\to B\}$$

Is there a more succint notation?


Complexity of general polynomial map evaluation is polynomial? A polynomial map is equal to another polynomial map iff they take on the same values at each point.  So this is different from formal polynomials.   So since in $\Bbb{Z}_p$, $x^{p-1} = 1$ for all $x \neq 0$, and is $0$ on $0$, we have that there are a finite number of polynomial maps in $\Bbb{Z}_p[x_1, \dots, x_k]$.  For now let's work in $\Bbb{Z}_2$ for simplicity.

The coefficients are arbitrarily chosen $c_i \in \Bbb{Z}_2$, and polynomials are in $\Bbb{Z}_2[x_1, \dots, x_k]$.  Then

$c_0 + c_1x_1$ obviously has complexity $2$ (2 operations explicitly required).

$c_0 + c_1x_1 + c_2 x_2$ needs $4$ ops.

$c_0 + c_1x_1 + (c_2+ c_3 x_1) x_2$ needs $6$ ops max.

$c_0 + c_1x_1 + c_2 x_2 + c_3 x_3 + c_4 x_1 x_2 + c_5 x_1 x_3 + c_6 x_2 x_3 + c_7 x_1 x_2 x_3 = \\ c_0 + x_1(c_1 + x_2 (c_4 + c_7 x_3) + c_5 x_3) + x_2 (c_2 + c_6 x_3) + c_3 x_3$

needs $14$ ops.  The pattern seems to be

$1 + (k + (k-1) + \dots + 1) + ((k-2) + (k-1) + \dots + 1) + \dots + 1$ which is $O(k^3)$, so is polynomial complexity polynomial?

Where did I make any mistake?  Thanks.

This doesn't make sense as there are about $p^k$ coefficients, and each one must be visited.

$* + x_1(* + x_2(* + x_3(* + *x_4) + *x_3 + *x_4)) + x_2 (* + x_3(* + *x_4) + *x_4) + x_3(* + *x_4) + *x_4$

You are basically doing an induction definition on $k$, where you evaluate a polynomial in $k+1$ variables by evaluation two polynomials of $k$ variables (by removing $x_1$.) So you have that the complexity $f(k+1)\approx 2f(k)$, which doesn't look polynomial to me.


Prove that regular languages and context-free languages aren't closed under $Perm(L)$ Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$

  Prove that both regular languages and CFLs aren't closed under $Perm(L)$.

I've tried to use several well-known languages (like $\{0^n1^n\}$) and applying $Perm(L)$ and afterward manipulate them or using the pumping lemma in order to get a contradiction, but nothing worked out.

Hints:

For regular languages, consider $Perm((01)^*) \cap 0^* 1^*$.
For context-free languages, consider $Perm(0^n 1^n 2^m 3^m) \cap 0^* 2^* 1^* 3^*$.


How will the value, A(2) be available in, line 2, if A(2) is being calculated in, line 3? How will the value, A(2) be available in, line 2, if A(2) is being calculated in, line 3?

The point is that it doesn't use the new value, it uses the old value. You want to take the current value of A[i+1] and use it to calculate a new value for A[i]. If you do each operation in order, you'll always do the operation which uses the old value, before overwriting it with a new value.

The problem is, when you vectorize this, you might end up changing A[i+1] at the same time as you're trying to read its old value. But ideally vectorization shouldn't change the result of a process, only how fast it runs. This is why you need the TEMP array, to keep the result the same.


How to construct a max heap that preserves insertion order for duplicate elements? I have a priority queue (using a max heap) that preserves insertion order for duplicate priorities, such that equal priorities fall back to FIFO behaviour. I'm doing this by creating a node with the value, the priority, and an 'insertion stamp' that is basically an incrementing number on the structure. I'd like to remove the need for this stamp, but I'm not sure if it's possible.

How might this work?

That's a perfectly reasonable approach.  Use (priority, insertion timestamp) as the priority value for your heap, with comparisons using lexicographic order (compare by priority, breaking ties by insertion timestamp).  That's all simple and easy to implement, and has no downsides that I can see.

Alternative, you can have one node in the priority queue per priority, with a pointer to a queue of items with that priority.  That also works and is easy to implement.


Problem complete for the class of ALL languages $\text{ALL}$ is literally the class of ALL languages.

Are there $\text{ALL}$—complete problems?  That is, are there problems for which a solution would allow one to solve any problem whatsoever?  Such problems could reasonably be considered"the hardest problems, bar none".

One such problem seems to be: given a problem and an input size, output it's truth table.

You haven't specified your notion of reduction, so I will assume that you choose some countable class of functions $\cal F$ which can be used for reductions (any subset of the computable functions would work here). Let $\cal L$ be any class of languages over some fixed alphabet $\Sigma$, say $\Sigma = \{0,1\}$. A language $K$ is hard for $\cal L$ (with respect to $\cal F$) if for every $L \in \cal L$ there exists $f \in \cal F$ such that $x \in L$ iff $f(x) \in K$. If also $K \in \cal L$ then we say that $K$ is complete for $\cal L$.

I will now show that no language is hard for $\mathsf{ALL}$. Suppose that $K$ were $\mathsf{ALL}$-hard. Let $f_x : x \in \Sigma^*$ be an enumeration of the functions in $\cal F$ (such an enumeration exists since both $\Sigma^*$ and $\cal F$ are countable). Define a language $L$ by
$$
L = \{x : f_x(x) \notin K \}.
$$
Since $L \in \mathsf{ALL}$, there exists a function $f \in \cal F$ such that for all $x \in \Sigma^*$, $x \in L$ iff $f(x) \in K$. Since $f \in \cal F$, there exists $x \in \Sigma^*$ such that $f = f_x$. For this particular $x$, $x \in L$ iff $f_x(x) \in K$. However, by definition $x \in L$ iff $f_x(x) \notin K$.


Changing preference in Gale-Shapley algorithm? Suppose, in the context of the classic marriage problem, two equal size groups of $n$ men and $n$ women are being matched, with the GS algorithm.

If a man were to switch the order of a pair of women, low on his preference list, say $x$ and $y$, would this yield any sort of advantage with regards to being matched with a woman higher than $x$ and $y$?

This seems like a fairly simple problem; I don't see how switching a pair low on the preference list would increase the chance of being matched with something higher on the list. How would one prove the existence or non-existence of such an advantage?

I've come to the conclusion that this would not yield an advantage, but would still appreciate some guidance with regards to proving that.

The property your wish to prove is known as strategy proofness: Is it possible for an agent to report a preference $P'$ such that it gets matched to a strictly better result w.r.t. its true preference $P$ than reporting truthfully?

Note that while the GS algorithm is strategy proof for the men, it is not for the women: they can use misrepresenting the preference to their advantage, as you can see with a simple example. In fact, there exists no stable matching mechanism that is strategy proof for all agents.

The proof of strategy proofness for men in the GS matching algorithm is, although it seems an obvious statement, rather involved. The clearest presentation I've been able to find is in the paper Machiavelli and the Gale-Shapely algorithm by Dubins and Freedman. In this paper, after proving strategy proofness, the authors proceed to prove the even stronger property of coalition strategy proofness:

  (17) THEOREM Suppose several students collude in a Gale-Shapley algorithm, each using a false
  rank ordering. They cannot all get better universities. "Better" is relative to each student's true rank
  ordering, and indicates strict inequality.

If you want a simple proof of strategy proofness of some matching mechanism, you can look at the Serial Dictatorship mechanism (also known under the perhaps less ominous name of Deferred Acceptance (DA) with single tie-breaks).

This is perhaps the simplest matching mechanism for the case with one-sides preferences and can relatively simply be shown to be both Pareto efficient and strategy proof.


How Can I Recognize When to Use ε-Transitions in an NFA? I am learning about finite automata for the first time.  I am having trouble understanding the purpose of ε-transitions in an NFA, which seem to be crucial to counting the number of states in an NFA and therefore an equivalent DFA.

Here is an example question that confuses me: What is the minimum number of states a DFA recognizing the language of a(bc)*d can have?

To answer this question, I first drew this NFA (dashed line indicates acceptance):

Because I think the above NFA is already a DFA, I thought the answer was "5".

However, the correct NFA and equivalent DFA look like this:

Which means the answer is "4".  I understand why these are correct.  But, I have some questions:

1) Is my original drawing actually an NFA?  If not, why?

2) If the original drawing is an NFA, does it describe the language a(bc)*d?  If not, why?

3) If the original drawing is an NFA that describes the language a(bc)*d, is it also a DFA?  If not, why?

4) If the original drawing is an NFA and DFA that describes the language a(bc)*d, why should I have known to draw the NFA with ε-transitions instead?

Your first drawing is a DFA (and thus an NFA) and does match the language described.  The NFA with $\varepsilon$ transitions is a fairly natural (and mechanical) translation of the regular expression, but other than that, it isn't inherently "more correct" than the NFA you started with.

The only confusion I see here other than uncertainty is once you validated that your NFA was a DFA you seemed to have just taken it for granted that it was minimal.  Starting from your DFA, you could have noticed that S4 has the same out-transitions as S2 and that they might possibly be joined.  Doing so would have immediately produced the final DFA.


Checking whether two paths are intersecting in a tree The problem I have is given a Tree graph , and two paths from u1 to v1 and u2 to v2 where u1,u2,v1,v2 are vertices of the Tree . How efficiently can we check that whether they are vertex disjoint paths or not ? The solution I thought was that the LCA of (u1 and v1) should be the ancestor of u2 or v2 or vice versa . But this is a wrong solution since it does not always work out correctly .

This is a standard exercise.  Try drawing some pictures with the different cases, and you'll see how to formulate a criterion for when they overlap, in terms of the lowest common ancestor.

Just computing $LCA(u_1,v_1)$ isn't gonna be enough, because that only gives you information about the first path, and doesn't depend at all on the second path.  So try computing the LCA of some other pair of nodes.

Since this looks like an exercise, I'm not going to solve your problem for you, but I'll describe for you how you can approach this problem so you can solve it yourself.

Every path falls into one of two categories: either it goes down (i.e., $v_1$ is a descendant of $u_1$); or it goes up and then down (i.e., $u_1$ and $v_1$ are descendants of some common ancestor, $w_1 = LCA(u_1,v_1)$, where $w_1 \ne u_1$ and $w_1 \ne v_1$).  So, there are two possibilities for the first path, and two possibilities for the second path: four cases in all.
You can quickly classify each path, put it into these categories, and find the endpoints and the common ancestor.  (Exercise for you: How?)

Now, you have four cases.  For each case, draw some pictures and work out the criteria under which the two paths intersect.  It's straightforward.

For instance, let's take the first of the four cases.  Suppose both paths go only down: $u_1$ is an ancestor of $v_1$, and $u_2$ is an ancestor of $v_2$.  Can you figure out how to tell whether they overlap?  Some tips: If $LCA(u_1,u_2)=u_1$, what can you conclude?  If $LCA(u_1,u_2)=u_2$, what can you conclude?  If $LCA(u_1,u_2)$ is something else, then what can you conclude?

Now do similar reasoning for each of the four cases.

Note: I am also assuming that you have a rooted tree; otherwise, the problem is not well-defined (as the LCA is not defined in non-rooted trees).

My thanks to @babou for his helpful comments and feedback on an earlier version of this answer.


Can the processor just turn off the interrupt request line? I was doing some of the interrupts question online and found this Multiple choice question

How can the processor ignore other interrupts when it is servicing one

a) By turning off the interrupt request line
b) By disabling the devices from sending the interrupts
c) BY using edge-triggered request lines
d) All of the above

The answer was (D) but I wonder how are we allowed to turn off the interrupt request line ?

What if we have a high priority interrupt that comes after ? We just ignore it ?
I mean (a) seems counter intuitive for me, because I don't think under any circumstances we should be turning off the interrupt request line ?

It depends on the processor arhitecture, but yes, most processors can turn off interrupts.  Shutting them completely off is usually only done in special situations like booting or critical error handling.

More commonly, interrupts are blocked until the CPU returns from the interrupt handling routines.  These routines should typically do the minimum amount of processing required, then return from interrupt to finish any work (forking down to a lower level for most of the work).

An older system I'm most familiar with, the VAX architecture, allowed for multiple interrupt levels (up to 31) and when an interrupt occurred the CPU would run at an IPL level corresponding to that interrupt.  All other interrupts at or below that IPL would be blocked until the IPL was lowered below the level of pending interrupts, then the pending interrupt would be delivered.  There was also a SETIPL instruction that allowed critical system code to block certain types of interrupts while critical code executed.  On single processor systems this was an effective synchronization technique that prevented multiple streams from changing data structures in an uncontrolled manor (multiprocessor systems required using other techniques like spinlocks).  Some problem with blocking interrupts are that multiple pending interrupts would be delivered as a single event and devices with unserviced interrupts sometimes get timeout errors.  So running at elevated levels for extended periods is discouraged.


NFAs with more than one initial state I'm trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it mentions that "There is an easy construction that translates a NFA with multiple initial states to a NFA with single initial state, which provides a convenient notation."

I believe the power set construction could help me on this matter but I'm having a hard time understanding it. It could probably be modified so that it can be applied into the definition I want to give, but i don't know how.

I would appreciate any help I can get on this matter.

An NFA with multiple starting states makes a non-deterministic choice of the starting state, in the same way that it makes non-deterministic choices throughout its operation. It is equivalent to an NFA with a single new starting state connected to the former starting states with $\epsilon$ transitions.

For example, here is an NFA which accepts the language of all words not containing all letters in the alphabet $\Sigma$. For each $\sigma \in \Sigma$ there is a state $s_\sigma$. For each $\tau \neq \sigma$, there is a self-loop labelled $\tau$ around $s_\sigma$. All $s_\sigma$ are starting states as well as accepting states. The state $s_\sigma$ is supposed to represent all words not containing $\sigma$.

In order to convert this to an NFA with a single starting state, add a new state $s$ which is the new starting state, and connect $s$ to all $s_\sigma$ with $\epsilon$ transitions. The semantics of both NFAs are exactly the same.


Proof by Reduction: From Empty Language to Halting Problem on Empty Input Question:
Let language $E$ = {$\langle M \rangle$ | $M$ accepts no inputs whatsoever}
Let language $H$ = { $\langle M \rangle$ | $M$ halts on an empty string input}.

Is it possible to show that $H$ is undecidable by reducing $E$ to it? (You can take it as a given that we know $E$ to be undecidable.) If so, show the work. If not, explain why not.

My attempt:

Assume that $H$ is decidable (that there exists a Turing Machine that decides $H$) and write a subroutine that maps the input, a machine description $\langle M \rangle$, to some other machine description $\langle N \rangle$, as follows:

def $R(\langle M \rangle)$:
  def $N(x)$:
    Check whether $M$ accepts no input whatsoever.
    If so:
      accept and halt on all inputs $x$ (including when $x$ == '')
    else, if $M$ accepts some input:
     loop forever on all inputs $x$ (including when $x$ == '')
     return $\langle N \rangle$

Does the above mapping work?

The subroutine $N(x)$ completely ignores the input $x$, and first checks whether $M$ accepts nothing. IFF so, $N$ will halt on every input $x$. Otherwise, IFF $M$ accepts something, then N will loop forever on all inputs $x$.

So, IFF $\langle N\rangle$ is accepted by a decider Turing Machine as belonging to $H$ (meaning $N$ halts on all inputs, including the empty string), we know $\langle M \rangle$ is accepted as belonging to $E$ (meaning $M$ accepts nothing).

Vice versa: IFF $\langle N \rangle$ is not accepted as belonging to $H$ ($N$ loops forever on all inputs, including the empty string), we know $\langle M \rangle$ is not accepted as belonging to $E$ ($M$ accepts something).

So we have a mapping where $\langle M \rangle$ is an element of $E$ IFF $\langle N \rangle$ is an element of $H$, Thus the mapping works. A decider Turing Machine for $H$ would be able to tell the difference, thereby leading us to be able to decide $E$. But since we know a priori that $E$ is undecidable, $H$ is also undecidable.

I'm just getting my feet wet on mapping-reducibility and am unsure whether the above is correct. Any help would be greatly appreciated.

See (Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)).

$H$ is Turing-recognizable but not co-Turing-recognizable.

$E$ is co-Turing-recognizable but not Turing-recognizable.

Their undecidabilities are of different kind. So we need to reduce $M$ to $N$ in such a way that:

$\langle M \rangle \in E$ if and only if $ \langle N \rangle \not\in H$.

Consider the following reduction from $M$ to $N$. Turing Machine $N$ on empty input will simultaneously generate all input and run $M$  as a universal Turing Machine on that input (again simultaneously) and halts (either accept of reject, doesn't matter) if some simultaneous thread of $M$ accepts on some input. On non-empty input it does not matter what $N$ will do.

We can easily see that if $M$ does not accept anything then it implies $N$ will never halt on empty input.
If $M$ accepts something then it implies that $N$ will halt on empty input.

Therefore, $\langle M \rangle \in E$ if and only if $ \langle N \rangle \not\in H$.

So, we have got a Turing  reduction (in fact, a polynomial time Karp reduction).

$E \leq_M \overline{H}$


warm/neutral/cool tone of one image I wanna determine whether an image belongs to warm/neutral/cool tone. I find Kelvin color temperature to calculate the average temperature of an image over all piexls. But the result seems not good. Can anybody point in the right direction to determine the tone of one image?

I would like to point that determining the color temperature of the image is still an open problem.
If you convert the RGB image to CIE XYZ Tristimulus color then calculate normalized chromacity to get the temperature, it works for pixel, kinda, it is a lot of effort to simply feed it a mean. Indeed it cannot work. The average over all pixels gives artificial color (if you do it over RGB it is not even chromacity preserving).
Whenever it is possible use CIE RGB (it is physical based color space, using the actual human sensitivity to colors) or some color space naturaly separating hue and lightness like HSL.

perform image segmentation or alternatively perform edge detection and subtract edges from reduced image
take from results only big enough blobs - this is arbitrary and depends on the image resolution, but more than 50 pixels is good default value. Blobs are segments of the image with small inner variance - they pixels are similar to each other, not varying too much in intensity and chromacity.
Calculate the average of blobs in the HSL space. Take into account the area and assign greater weights to bigger blobs (if blob spans over 200px it will be better perceived than 4x50px).
take into account the placement of the blob (calculate how far it is from the center)
the the center is weight 1, slightly decreases to suddenly drop. This weights reflect what is better exposed (assuming that there are no important features at the corners, but it is safe to assume that the main focal points are in the center).
take this weighted areas (blobs) average them in HSL space and now calculate color temperature - sorry for obvious link but the equations are ok.
This method performs quite good experimentaly, some parameters should be adjusted per type of image, sorry I do not remember exact parameterts (proven to give good results experimentally).

Unfortunately your task must be heavily modified to reflect how people perceive images, how they neglect the color of edges (which give quite big boost RGB-wise). What they focus at and how they remember. By the way, the reception of the image tone is a bit skewed by the represented objects - the attraction makes the tone warmer while repulsion makes it colder.
So please take a look at awesome articles:

Kraft, T. W., Schneeweis, D. M., & Schnapf, J. L. (1993). Visual transduction in human rod photoreceptors. The Journal of Physiology, 464, 747–765.
Ho, H.-N., Iwai, D., Yoshikawa, Y., Watanabe, J., & Nishida, S. (2014). Combining colour and temperature: A blue object is more likely to be judged as warm than a red object. Scientific Reports, 4, 5527. http://doi.org/10.1038/srep05527
Evaluating color texture descriptors under large
variations of controlled lighting conditions


Construct a Circuit computing all boolean functions over n bits Let $ n∈N $ . Construct a circuit with $ C_n(x_1,\dots,x_n) $ with $ 2^{2^n} $ outputs $ y_1,\dots,y_{2^{2^n}} $ which computes all
  distinct boolean functions $ f_i:\{0,1\}^n→\{0,1\}$ such that $ y_i $ is the
  output of $ f_i $ and satisfying $ Size(C_n)\in O(2^{2^n}) $

Remark: The circuit is in a model of fan-in 2.

I've already found a solution in $ O(2^{2^n + n}) $ but I can't find less even recursively.

Given the circuit $C_n$, you can compute $C_{n+1}$ using $O(2^{2^{n+1}})$ additional gates. Indeed, each output gate of $C_{n+1}$ is of the form
$$
(\lnot x_{n+1} \land y_i) \lor (x_{n+1} \land y_j)
$$
for some $i,j$, so can be computed from the outputs of $C_n$ using $O(1)$ additional gates.

In total, the circuit $C_n$ uses $O(2^{2^n} + 2^{2^{n-1}} + \cdots) = O(2^{2^n})$ gates.


Is chess game movement TM decidable? If we have a finite chess board and two figures x and y. Is it possible to get y from x by following chess rules and when white is y and white starts from y placement. Is this decidable?

My reasoning is, that we have a finite sets of moves  and since all finite languages are decidable and at some point x is going to get y this problem is decidable. What do you think?

The chess board problem is, although complex, a finite problem. Specifically, the number of moves, starting from any board position, is finite.

Then, a TM can just go over all the possible moves (there are only $C$ such moves, for some "small" constant $C$), and verify if a certain position is feasible continuation of a prior position. Hence, any such question is decidable.


How would a DFA be designed to accept a language defined as the string comprised of every other character in each string in another language? For example, you have a DFA that accepts the language comprised of strings aabbbaa and aaabbbbaaa, and you want to create a new DFA that accepts a language comprised of strings abba and aabba (strings made up of every other character in the strings in the original language). What would be the generalized construction technique for creating the new DFA that could be applied to any DFA to produce the same results?

I think there's something to it involving creating an NFA using lambda transitions from each state to the following state in the original DFA, then converting the NFA to a DFA, but that creates a DFA that accepts more strings than originally intended.

Any suggestions?

This is a closure property. For language $L\subseteq \Sigma^*$, define the language $even(L) = \{ x_2x_4\dots x_{2n} \mid x_1x_2x_3\dots x_{2n-1}x_{2n} \in L, x_i\in\Sigma\}$. Now for regular $L$ the language $even(L)$ is again regular. This is a special case of closure of the regular languages under finite state transductions.

In case of this specific property an automaton $M_1$ for $even(L)$ when $M$ for $L$ is given, can be found as follows. For every pair of consecutive transitions $(p,a,q)(q,b,r)$ for $M$ introduce the transition $(p,b,r)$ in $M_1$.

Additionally one needs a somewhat formal argument that this will in fact work.

Alternatively, this closure property can be deduced from known closure properties: (inverse) morphisms and intersection with regular languages.
Make a copy of $\Sigma$: $\bar\Sigma=\{\bar a \mid a\in \Sigma\}$.
Define the morphisms $g,h:(\Sigma\cup\bar\Sigma)^*\to \Sigma^*$ where $g$ removes the bar (but keeping the letters), and $h$ removes letters from $\bar\Sigma$. $R$ is the regular language $(\bar\Sigma\Sigma)^*$
Then $even(L)$ is the composition $h(g^{-1}(L) \cap R) $.


How a NTM guessing depends on the input? After looking at the definition of nondeterministic TMs, it seems that, while guessing, the machine could go to at most $|Q|\times | \Gamma |$ configurations, being in a particular one.

However, if we look at several concrete NTMs, the guessing part depends on the size of the input, i.e. it's not bounded. For instance, let's take this machine finding Hamiltonian Path here:
How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

A part of the algorithm says "Each number in this list is non-deterministically selected to be from 1 to x.", where x is the number of nodes of the graph(and we may have arbitrarily big number of nodes).

I know the answer is perhaps trivial, but I couldn't find it.

Suppose that the input has length $n$, and suppose that the machine already knows $n$. In order to non-deterministically choose a number from 1 to $n$, it performs the following algorithm:

Choose $m = \lceil \log_2 n \rceil$ bits non-deterministically, and interpret them as a number $x$ from $0$ to $2^m-1$.
Increase $x$ by one.
Reject if $x > n$.

The first step is implemented by a loop.


LTL: Show $\neg(aUb) \Leftrightarrow \neg b U (\neg a \land \neg b) \lor G \neg b$ I got as far as
\begin{align}
w \vDash \neg (a U b) &\Leftrightarrow  \neg (w \vDash a U b)
\Leftrightarrow \neg (\exists_{i\geq0} : w^i \vDash b \land \forall_{0\leq k < i} : w^k \vDash a)  \\
&\Leftrightarrow \forall_{i\geq0} :  \neg(w^i \vDash b) \lor \exists_{0\leq k < i} : \neg(w^k \vDash a)
\end{align}

but got stuck.

If you could offer some advice as on where to start I would very much appreciate it. Thanks in advance

$aUb$ means that $a$ holds up to (and not necessarily including) the first point where $b$ holds, which must exist. There are two ways in which this can fail: $b$ never holds, or the first time that $a$ fails precedes the first time in which $b$ is true. The first case is handled by $G \lnot b$. The second case is handled by $\lnot b U (\lnot a \land \lnot b)$ (why?).


How to prove a greedy algorithm that uses the longest increasing subsequence? Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy algorithms.

The problem says: I need to sort an array of $n$ numbers, but the only operation I am able to do is to move an element from position $i$ to $j$, and if $i<j$ then every elements in the interval $[i+1, j]$ (inclusive) are moved one position backwards. On the other hand if $i>j$ then every element in the interval $[j, i-1]$ increase their position by one. That operation has a cost of $i+j$ for doing it. So I need to sort the array using the lowest cost possible using a series of only that kind of operations.

Assume that I need to sort the array in decreasing order.

After a lot of thinking, I came up with the idea of finding the (first) longest increasing subsequence from right to left. If I have that sequence, we are to assume that those elements in that sequence are already sorted. So, I wouldn't need to use them (i.e selecting them (from $i$) to move them (to $j$)), cause they are already sorted. That way, the cost of moving them would never be calculated into the final cost of making every operations. And also I will be doing fewer operations and then guaranteeing that the ones I am doing has the lowest cost.

The cost will be easily calculated because the subsequence was created using a sort of Tuple element, with the value and the actual position in the array, so I'll use the value of the position to calculate cost.

After having that subsequence in hand, I am to insert the remaining elements in that sequence (the first longest increasing subsequence from right to left). After that I insert the remaining elements in a Queue to easily Dequeue them in the order of their position (from lowest to highest). That way, we guarantee that the cost of moving them will be minimum. After inserting we update the position of the elements in the sequence (in the Tuple) in the Queue and in the sequence (say I am using a List of Tuple for the sequence).

That algorithm is working, and have thrown a correct answer for several cases I tested against a brute force algorithm version.

Now I need to proove it works, but I have no clue how. It can easily be seen I am using a greedy aproach to insert the elements, but I how does it guarantee what I am looking for!

Hope anyone can point me into the right direction of that proof!
Thanks in advance

EDIT: I have done some progress here, and I am in a point where I have proven that the optimum must have selected a decreasing subsequence to avoid those items of being moved, but I need to prove that this is the maximum decreasing subsequence. In order to do that I am trying to prove that the cost of moving $X$ elements is less than the cost of moving $Y$ elements with $X<Y$. I haven't been able to prove it, but I can't come up with an example that prove me wrong.

Do you think this happens? How could I prove it?

Thanks

EDIT: This is the problem itself SPOJ Problem RSORTING - RANKLIST SORTING
I have a solution but I need to prove its correctness

The most intuitive way to prove such an issue, where you're ordering elements by rank in a list, is to use an exchange argument. In short, it comes down to proving that whenever an inversion exists in the list, your algorithm inverts them so that they become ordered correctly. By proving this to be the case for every value/index pair it follows naturally that the list ends up completely ordered.

Many universities have publicly available courses on the matter. For example the TU Delft has an excellent Open CourseWare page on algorithmics that includes the subject, to be found at:

https://ocw.tudelft.nl/course-lectures/3-greedy-algorithms/


Are finite state transducers and Mealy machines the same machines? There are several versions of the definitions of the FST and the Mealy machine.
Some of the definitions are almost same. Some have a little differences.
But it seems that they both are a kind of DFA with an output function $G \colon \Sigma \times Q \rightarrow \Gamma \times Q$, where $\Sigma$ is the input alphabet and $\Gamma$ is the output alphabet.

I'm not sure about the differences between them.

Are they the same machines? Why is there two different names?

BTW, I found that there is not the set of final states in the definition of Mealy machines or Moore machines. On the other hand, final states do exist in the definition of FST, although Mealy machine is one type of FST. Does it mean that final state is not important when we are talking about the Mealy machines?

Mealy machine (by G. Mealy) is a deterministic finite state transducer with output associated with transition (edge) instead of state. It could handle multiple inputs and multiple outputs but by definition cannot be non-deterministic. According to definition it must be defined for all possible combinations of states and inputs.

Finite State Transducer is a generalization of Finite State Machine (M. Rabin, D. Scott) which can be both deterministic and non-deterministic. The output is associated with states, not all combinations of states and input must be present. Not all NFST can be determinized.

The computational power of both is equal in the Chomsky hierarchy, but there exist machines that cannot be expressed by other type. In special transduction hierarchy FST is higher than Mealy.
There are extensions to create nondeterministic Mealy machines, but nondeterminism for transducers is not really exploited, it would generate the family of outputs when one is really needed, unless it was the goal then NFST wins here.

From physical point of view it makes difference, Mealy equivalent machines are shifted in time, but considering only the result it does not matter.


All pairwise shortest paths in a graph: does knowing the path weights help? This question concerns the all-pairs shortest paths (APSP) problem (where we are given a graph with edge $(i,j)$ given weight $w_{i,j}$ by the distances between the two nodes $i$ and $j$, and where we want to get the lowest-weight path from every starting vertex $i$ to every ending vertex $j$),

The "Path reconstruction" subsection of the Wikipedia article on the Floyd-Warshall algorithm, claims:

  Floyd–Warshall algorithm typically only provides the lengths of the
  paths between all pairs of vertices. With simple modifications, it is
  possible to create a method to reconstruct the actual path between any
  two endpoint vertices. While one may be inclined to store the actual
  path from each vertex to each other vertex, this is not necessary, and
  in fact, is very costly in terms of memory. Instead, the Shortest-path
  tree can be calculated for each node in Θ(|E|) time using Θ(|V|)
  memory to store each tree which allows us to efficiently reconstruct a
  path from any two connected vertices.

In general (not simply on the FloydWarshall algorithm), if we were given the optimal path distances (i.e., the distances of the most efficient routes) between every starting vertex $i$ and every ending vertex $j$, but not given the paths themselves, is this of any help to finding the best paths? I can think of trivial uses (like branch and bound to discard any paths that exceed the provided optimal path length), but am curious if there are other uses for the minimal distances.

Do you know if starting with the minimum final path distances would help find the corresponding paths?

Yes, given the lengths of the shortest paths it is easy to actually find these paths. Suppose for example that you want to find the shortest path from $s$ to $t$. Let $d(s,t)$ be the length of the shortest path, and $w(s,t)$ the length of the edge from $s$ to $t$, or $\infty$ if there is none.

If $d(s,t) = w(s,t)$ then the shortest path is simply $s,t$. Otherwise, there must be a vertex $x$ such that $d(s,t) = w(s,x) + d(x,t)$ (why?). The shortest path then starts $s,x$ and continues with the shortest path from $x$ to $t$, which you can find recursively.

You can also go from $t$ back to $s$ if you prefer. You can also make progress by finding some point $u$ such that $d(s,t) = d(s,u) + d(u,t)$.


Prove its not a regular language I have a question. Assume $L = \{ a^m b^m \mid m ≥ 1 \}$ is not a regular language.  Prove that $I = \{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0 \}$ is not a regular language.

I can prove it with pumping lemma but the question is to solve it by using the assumption.

Thanks.

Here's a hint: we know that $L = \{x^m y^m \mid m ≥ 1 \}$ is a non-regular language.

Is there some part of $I = \{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0\}$ which looks similar to $x^m y^m$?

Could you somehow extract that part?

If you could, could you use the fact that $L$ is not regular to conclude that the extracted part is not regular?

Given this, can you then conclude that $I$ is not regular?


What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$? In these notes about quantum computation by Scott Aronson, he explains that the computation classes $\mathsf{BPP}$ is contained in $\mathsf{BQP}$, but that they are not equal, and

  So, the bottom line is that we get a problem -- Simon's problem -- that quantum computers can provably solve exponentially faster than classical computers. Admittedly, this problem is rather contrived, relying as it does on a mythical "black box" for computing a function f with a certain global symmetry. Because of its black-box formulation, Simon's problem certainly doesn't prove that $\mathsf{BPP} \neq \mathsf{BQP}$. What it does prove that there exists an oracle relative to which $\mathsf{BPP} \neq \mathsf{BQP}$. This is what I meant by formal evidence that quantum computers are more powerful than classical ones.

What does he mean by an oracle separation?

My understanding of an oracle for a Turing machine is one that solves the halting problem. Surely that can't be the case here?

No, an oracle is a black box that solves a problem in a single step. The problem that it solves can be any problem, it doesn't need to be the halting problem.

What Scott is saying is that there is some black box that a BQP machine with it can do more than what a BPP machine can do with it. However, it doesn't mean that without that black box BQP is more powerful than BPP.

A simpler case is P vs. NP. By Baker, Gill, and Solovay's result there is a black box that P with that black box is not equal to NP with that black box. But it doesn't tell us much about what should be the answer to P vs. NP.


Is there an affordable experiment which shows chips can't get much smaller? If I am correct, chips cannot get much smaller because of Heisenberg's uncertainty principle. My friend and I want to perform an experiment (which is cheap, i.e. doesn't require million-dollar equipment) which shows that if a chip is too small, it will mess up. Is there any such experiment?

I think you are right that the Heisenberg uncertainty principle is involved in the limit.  I don't think we are anywhere near the Heisenberg limit.  The limit we are currently approaching is that we currently compute with devices based on atoms.  An atom is about 1 angstrom = .1 nm wide.  We are currently making transistors that are about 22 nm wide, so we're getting close to needing to make 1 atom transistors.  If we want to scale beyond that we're going to need to find ways of computing that involve storing and manipulating multiple states per atom.

The wikipedia article on fundamental limits of computation is a good starting point.  I think what you really want is the Bekenstein bound.

The researchers that I know of in this area are Rolf Landauer, Charles H Bennett, and Seth Lloyd.  (I think Charles H Bennett considers himself a computer scientist while the other two consider themselves physicists.)  Richard Feynman was also very interested in this question and has a book called Feynman Lectures on Computation (which you can read about at http://quantum.quniverse.sk/buzek/zaujimave/p257_s.pdf).  Also @PeterShor is an active member here and is the expert on quantum computation.

Here's a Scientific American article by Bennett and Landauer:

http://web.eecs.umich.edu/~taustin/EECS598-HIC/public/Physical-Limits.pdf

Here's Seth Lloyd's article in Nature: http://arxiv.org/abs/quant-ph/9908043

Here's a web page at Cambridge: http://www.sp.phy.cam.ac.uk/~SiGe/Fundamental%20Limits%20of%20Computation%20-%20Landauer%20and%20Heisenburg.html


Mixed-strategy Nash equilibria Is the following statement always true:

  if there is a mixed-strategy Nash equilibria then it is unique.

I know that there can be several pure strategy Nash equilibrias.

Shameless Advertisement: Game Theory proposal
  on Area 51 that you should totally follow!

No. The easiest way to prove this is by counterexample. Expanding matching pennies, we can create a game with two mixed strategies (players either mix between A and B or between C and D):

What might be true about that statement is for a mix of particular pure strategies for two players, there is a unique mixed strategy equilibrium. This presumes that there is a threshold  after which you switch from using strategy $0$ to strategy $1$. At this threshold, your opponent is ambivalent between her strategies. As depicted below, the intersection (and hence mix) will be unique.


Are Epsilon-NFAs a way to make designing NFAs easier? It seems that their purpose is in making designing certain NFAs less onerous? Does this mean that no automata that are implemented have Epsilon-transitions, and that they are kind of a mathematical conceit we adopt for our own ease of design? I'm having a lot of trouble understanding what is "happening" when an Epsilon-transition occurs - is it a way of saying, "have the NFA now switch, automatically, to this next state"?

EDIT: I'm  a CS student taking CS Theory for the very first time, so apologies if this question is very rudimentary. I'm a narrative person and I often understand abstract ideas through examples or by trying to understand the problems the ideas are engaging with. I ask very basic questions, but those questions help me hook into the ideas I'm studying.

An epsilon-NFA is a mathematical formalization.  Mathematics doesn't have a purpose, per se.

Why do we use this formalization?  Sometimes, because it is convenient.  Yes, it sometimes makes designing certain NFAs less onerous, and that's useful.  So, yes, your suggested rationale/motivation is reasonable.  It also makes some algorithms (e.g., Thompson's construction) simpler and easier to understand.  It's also intellectually interesting to know what power epsilon-transitions add.  There are multiple reasons why one might study this concept; different people might have different reasons for studying it at any point in time.  See also Why is non-determinism useful concept?.

What is "happening" when we execute an epsilon-transition?  Well, a NFA is not a physically implementable machine; it is an abstract concept.  So it is hard to map it to physical, real-world intuitions.  See also Why NFA is called Non-deterministic?.


Situations where Kleene star of A is context-free, but A is not This question appeared on my Theory of Computer Science final:

True | False: $A^*$ is context-free $\implies$ $A$ is context-free.

My professor says the answer is false, and I believe him, but am having trouble constructing a counterexample or even just convincing myself why. It seems to me that if a grammar can describe repeated concatenation, there must be some nonterminal that is concatenated.

Does anyone have a counterexample?

Let $L$ be any non-context-free language, then we can construct the language $A = \Sigma\cup L$ - i.e. $A$ is either an element of $\Sigma$ or a string from $L$ (these can happily overlap too). This is clearly not context free either (if it were, then we would have a PDA for  it, and we can easily modify this PDA to recognise $L$).

If we now take $A^{\ast}$ however, we get $\Sigma^{\ast}$, which is most certainly context free.


Min/max height of B-tree I have a question asking for the minimum and maximum height $h$ of a B-Tree with 1000 elements under following conditions:

each block can save 1 to 4 records,
the number of internal nodes is between 3 and 5 and
the root has between 3 and 5 children.

The solution is given as $4\leq h \leq7$. How this is reached?

In the worst case you will store 1 record per node, so you will need 1000 nodes.

In the best case you will store 4 record per node, so you only need 1000/4 = 250 nodes.

In the worst case you will have 3 children per node, so your tree will only grow by multiples of 3 for each level.  So we can say that $3^h \geq 1000$, where $h$ is the height.  So $h=\lceil\log_3 1000\rceil=7$

In the best case you will have 5 children per node, so your tree will be $h=\lceil\log_5 250\rceil=4$


Finding minimum/maximum value in a Binary Indexed Tree I know how a BIT works. But I was wondering if a BIT can be used to find the minimum/maximum element in the complete range, or more specifically, to find the minimum (or maximum) value after all the update processes have been completed. Now, I know that this can very well be achieved using Segment Trees, but is it possible to do the same using a BIT?

I know the obvious way of traversing the complete BIT and calculating the value at each index. I am looking for a more efficient/optimized way.

You cannot do better than $O(n)$.

Consider a set, where all values are $k$, except $2i$ and $2i-1$, which are $k-l$ and $k+l$ respectively. Any entry in the tree that contains a sum of $m$ values will be $mk$, with the single exception of the entry $2i-1$.

Thus, even if we knew we had a set of the form described, we had to look at $\frac n2$ entries in the worst case, in order to determine the minimum and maximum value.