Use of Activation Units in Facial Expression Understanding The topic of extracting the Facial Action Coding System (FACS) Action Units (AUs) [1] from images and it's translation into emotion prediction [2] is pretty well studied, but I'm not clear on how it stacks up against alternative approaches such as Convolutional Neural Networks (CNN). How much does the accuracy of AUs effect the accuracy of emotion detection?

"Joint Facial Action Unit Detection and Feature Fusion: A Multi-conditional Learning Approach", Eleftheriadis S, Rudovic O, Pantic M. (2016)
"Emotion Detection From Facial Expression And Its Use In The Evaluation Of Stress" Suvashis Das (2013)

As a preliminary answer, I can't imagine the extraction of AUs affecting their ability to detect emotions, since according to Do Deep Neural Networks Learn Facial Action Units When Doing Expression Recognition?, CNNs trained to extract emotions already correspond to AUs (called FAUs in the paper), as shown in the table below taken from their paper:

Additionally, this is a very basic CNN with only three convolutional layers and grayscaled inputs. Given a larger CNN using Inception-layers and residual connections, more specialisation would probably be seen.

However, this conclusion also makes me feel like I'm dismissing a whole area of research, so it's probably a little hasty.


UNDIRECTED HAMCYCLE to HAMPATH reduction I'll define the problems

  UHAMPATH

  Input: A undirected graph G and 2 nodes, s and t

  Question: Is there a hamiltonian path from s to t in G?

  UHAMCYCLE

  Input: A undirected graph G

  Question: Is there a hamiltonian cycle in G?

$$UHAMCYCLE \leq_p UHAMPATH$$

my reduction is as followed $(G) \to (G', s, t)$

function(G)

    for each e = (u, v) in E(G)
        G' = G
        add nodes u' and v' to G'
        add edges (u', u) and (v, v')
        s = u'
        t = v'
        if there is a hamilton path from s to t:
            return (G', s, t)

Basically if there is a hamilton cycle in G then some edge in $G$ will form a hamilton path in $G'$.

An example to further illustrate the reduction:

 Graph G

(a) ---- --(d)
 | \        |
 |   \      |
 |    \     |
 |     \    |
 |      \   |
 |       \  |
 |         \|      |
(b) ------ (c)

Has a clear Hamilton cycle (a, b, c, d).

If we choose edges (a, d)

 Graph G'

(s)--(a) ---- --(d)
      | \        |
      |   \      |
      |    \     |
      |     \    |
      |      \   |
      |       \  |
      |         \|
     (b) ------ (c)--(t)

Doesn't have a hamilton path from s to t. However if you choose any other edge such as (a, d) then

(s)--(a) ---- --(d)--(t)
      | \        |
      |   \      |
      |    \     |
      |     \    |
      |      \   |
      |       \  |
      |         \|
     (b) ------ (c)

$(s \to a \to b \to c \to d \to t)$. Holds.

I'm confused whether or not I can use this line:

if there is a hamilton path from s to t:
    return (G', s, t)

Checking to see if a graph has a hamilton path is NP complete but since we are looking to reduce it to it I think we can?

No. Since you are performing a many-one reduction, you have no capabilities beyond the model you are using for the reduction, in this case a poly-time Turing machine. Queries to the problem you are reducing to are only allowed if you are performing a Turing reduction, but that is a different notion and (strictly) more powerful than a many-one reduction (and is not what is used when establishing NP-completeness).

Of course, the line would be allowed if you managed to prove HAMPATH is solvable in polynomial time. I don't think you will be able to.


Why is encrypting with the same one-time-pad not good? To encrypt a message $m_1$ with a one-time-pad key $k$ you do
$Enc(m_1,k) = m_1 \oplus k$.

If you use the same $k$ to encrypt a different message $m_2$ you get
$Enc(m_2,k) = m_2 \oplus k$, and if you perform Xor of the two ciphertext you get
$$( m_1 \oplus k) \oplus ( m_2 \oplus k) = m_1 \oplus m_2$$

so, OK, there is some information leakage becuse you learn $m_1 \oplus m_2$, but why is it not secure? I have no way to learn (say) $m_1$ unless I know $m_2$. So why is it wrong to use $k$ twice??

I have no way to learn (say) $m_1$ unless I know $m_2$.

That is exactly the problem - if you re-use the same key, and someone has access to one message you encrypted in both plaintext and encrypted form, they can use that to find your key:
$$
(m_2 \oplus k) \oplus m_2 = k
$$

As an alternative scenario, if you use the same key over and over, the attackers may be able to guess just pieces of various encrypted message, and each successful guess reveals a piece of the key $k$, so that over time more and more of the key is revealed.

This general strategy for breaking a cryptosystem is known as a known plaintext attack. Many systems, like AES and RSA, are believed to be secure against these attacks. But a one-time pad becomes completely insecure against them unless a new pad is used for every encryption, which is why they are named "one-time pads".


function application of N x N -> N Let the function cane and its auxiliary helping function down be the smallest functions satisfying the following requirement. For every x∈ℕ, for every y∈ℕ, and for p=(x,y), all of the following statements hold:

down(x+1,y)=(x,y+1)

down(0,y+1)=(y,0)

cane(p)= 0 if down(p) is undefined

cane(p)=1+cane(down(p)) if both down(p) and cane(down(p)) are defined.

(NOTE: p above is a pair.)

For every x ∈ ℕ and y ∈ ℕ such that x+y ≤ 2 (there are six such pairs), calculate the value, if there is one, of down(x,y) and also of cane(x,y). Put your answers in two tables, one for down and one for cane, of this form:

Hint: It might help you for the later parts of this question if you he k these two functions with more values for x and y.

Describe in words how the function cane and its auxiliary helping function down work, and what they accomplish. Explain any wider significance ane these functions might have. My question is how am I supposed to fill in this table;

for example, if I take in x to be 0 and y to be 0 then my down function would be as follows;

down(0+1,0)=(0,0+1)==(1,0)=(0,1) and down(0,0+1)=(0,0)==(0,1)=(0,0) I believe then that when x=0 and y=0 then the position in the table is "undefined" and true for all other coordinates of the table because they form a trail back to (0,0).

Could someone please help me understand this?

A more formal way to define the down function is
$$
\mathit{down}(x,y) =
\begin{cases}
(x-1,y) & \text{if } x > 0, \\
(y-1,0) & \text{if } x = 0 \text{ and } y > 0, \\
\text{undefined} & \text{if } x=y=0.
\end{cases}
$$


Encoding of graphs as an input to neural nets Given a directed graph $G=(V,E)$ with a node labelling function $l:V\rightarrow L$, how would you encode this best for a neural network?

If it simplifies the problem, we can add the following assumptions about $G$:

$|V|$ is of fixed size $n$.
Every node $v$ in $V$ has exactly two successors.
$l:V\rightarrow L$ is injective; in particular, instead of using node labels, a total ordering of the nodes would be good enough to "infer" the original graph labels.

What I'm trying to learn is a successor selection for every node $v$ in $V$; in other words, a map $m:V \rightarrow V$ with $m$ subset $E$.

Taking all assumptions into consideration, we more or less only have to encode $E$. Obviously, we could use a "two hot encoding" for every node $v$, resulting in a quadratic number of inputs, but is this the preferred way of going about it?

Thanks!

So I ask myself this question:

  Suppose 2 encoding contains the same amount of information, that is,
  all the information about the graph. What factor would make one
  encoding better than the other in terms of performance of neural nets
  (trained with the same number of iterations, etc)

The my personal answer to that is:

Trained neural net (in its simplest version) is just a linear function of its input. So, do you suspect that the function you want to learn can be expressed as a linear function of the input? And this is where the choice of encoding makes a difference.

My stance on these kind of algorithm is that. Ultimately, if you want it to perform well, you need to have a good hypothesis on what kind of function your answer should actually be.


Given a tree, find a vertex which maximizes the minimum distance to any leaf If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf.

I am sure this problem has been studied before.
Does anybody know the name of this problem or an algorithm for solving it?

To find a vertex of maximum distance from any leaf, you can perform a breadth-first search starting from many starting points, i.e. the leaves. Because a BFS visits each node by the shortest possible path from the source(s) of the search, we can easily attribute to each node the distance to the nearest leaf.

Insert into a queue a collection of pairs $(\ell,0)$ for $\ell$ ranging over all leaves, and record $\textrm{max} = 0$.
Repeat the following until the queue is empty:

Pop a pair $(v,d)$ off the queue. If $d = \textrm{max}$, insert $v$ in a collection of maximum-distance elements.
If there are nodes adjacent to $v$ which haven't been visited, push a pair $(w,d+1)$ into the queue for each such neighbour $w$, marking them as having been visited. If there are any such $w$ at all, empty the collection of maximum-distance elements (if it is non-empty), and set $\textrm{max} = d+1$.

The result is a collection of nodes which are all at distance at least $\textrm{max}$ from any leaf.

Let $n = |V|$ (note that $m = |E| = n-1$). Assuming that we can populate the queue with the leaves of the tree in time $O(n)$ by examining all nodes of the graph, and that the vertices have adjacency lists of their neighbours, we "traverse" each edge twice to consider the neighbours of each vertex; then this algorithm takes $O(n+m) = O(n)$ time. It also works for non-trees, taking again $O(n+m)$ time.


Condition for perfect matching in bipartite graphs Let $G = (S, T, E)$ be a bipartite graph without isolated vertices.

For each edge $e ∈ E$, $e = st$ (where $s ∈ S$, $t ∈ T$), the inequality
$d_G (s) ≥ d_G (t)$ holds. Prove that there is a matching in $G$ saturating all
of $S$'s vertices.

Here is a proof for the following related result:

  A $d$-regular bipartite graph contains a perfect matching.

According to Hall's criterion, a perfect matching exists if for all $A \subseteq S$, $|N(A)| \geq |A|$. Take any $A \subseteq S$. There are $d|A|$ edges connecting vertices in $A$ to $T$. A given vertex $t \in T$ can be the target of at most $d$ such edges. Hence there are at least $d|A|/d = |A|$ such targets, that is, $|N(A)| \geq |A|$.

Try modifying this proof for your case.


Solving equations without side effects Consider the example of solving for $x$ where $Ax=b$.  This is not in general function, there can be more than one solution.  So if you make such a solver in a functional style...does this count as a side effect?

def solve(A:Matrix[Float],b:Matrix[Float]):Matrix[Float] = ...

Obviously the solution will be dependent on several internal factors such as the method to solve, e.g. the type of echolonization, or perhaps it uses randomization (Krylov methods for example).  And that appears to be all you could expect because solving is not a function.  Still, it is evident that the return is a representative of an equivalence class, and so subject to the interpretation that the outputs are representative of an equivalence class then this would be a function -- just we don't want to implement it as some coset of a subspace as that might be slower or impossible.

In purely functional programming is there a loop-hole of sorts for implementing relations -- which interpretted under an equivalence relation, become fucntions, even if we don't explicitly wrap it up that way?

E.g. could I implement a version of the signature above for solve in Haskell without a monad?

As far as I know, I think it is possible to build a functional implementation of solve that does behave as a deterministic function, with no side effects.  Yes, there might be multiple possible outputs that are all valid.  However, I think it's possible to pick an implementation where it always outputs the same answer.  (Certainly, the existence of multiple possible outputs doesn't on its own render it impossible to build such an implementation.)

Here is a simpler example, to give you some intuition.  Suppose we want to find a solution to $|x|=c$, where $c$ is a constant given in advance.  Then there are two solutions ($x=+c$ and $x=-c$).  Nonetheless, you can still build a functional program to output a solution to this, i.e., on input $c$, the code returns a solution to $|x|=c$.  An example implementation is the identity function (always return whatever the input was).  This is functional and has no side effects.

So just because there are multiple valid outputs doesn't require the code to randomly or nondeterministically choose among them.  Often you can write code that outputs one of them, and is consistent and deterministic about which one it outputs.

For instance, here is a plausible such implementation for your particular problem:

Solve the linear system "minimize $x_1$ such that $Ax=b$" using linear programming.  (Here I write $x_1$ for the first variable of $x$, i.e., I am assuming $x=(x_1,\dots,x_n)$.)  (If it has no solution, return "No solution".)  Let $u^{(1)}$ denote the resulting such solution.
Solve the linear system "minimize $x_2$ such that $Ax=b$ and $x_1 = u^{(1)}_1$" using linear programming.  Let $u^{(2)}$ denote the resulting such solution.
Solve the linear system "minimize $x_3$ such that $Ax=b$ and $x_1 = u^{(1)}_1$ and $x_2 = u^{(2)}_2$" using linear programming.  Let $u^{(3)}$ denote the resulting such solution.
Repeat, until you have obtained $u^{(n)}$, where $n$ is the number of variables.  Return $u^{(n)}$.

Note that this algorithm returns the lexicographically least solution to $Ax=b$.  Because linear programming is in P, I believe each "solve the linear system" step can be implemented with a deterministic, functional algorithm.


Negligible Function in Cryptography In the field of Cryptography and Computation Complexity there is a notion of negligible function.
I have some difficulties in understanding intuition behind this notion. The following are some definitions from Chapter 9. Cryptography from the textbook Computation Complexity. A modern approach by Arora and Barak with extensive use of negligible function. There my question after every definition about negligible function.

Before proceeding further, we make a simple definition that will greatly  simplify notation throughout this chapter.
Definition of negligible function. a function $\epsilon : \mathbb{N} \rightarrow [0,1]$ is called negligible if $\epsilon(n)=n^{-\omega(1)}$.
Because negligible functions tend to zero very fast as their input grows, events that happen with negligible probability can be safely ignored in most practical and theoretical settings.

So far so good, it's just the definition of negligible function, the only point is why do we need to care about this function if it "can be safely ignored".

The notion of computational secure function.$k \in_R \{0,1\}^n, x \in_R \{0,1\}^m, Pr [A(E_k(x))=(i,b) s.t. x_i=b] \leq \frac{1}{2}+\epsilon(n)$.

Less intuitive usage of negligible function. As I understood, in general, $A$ can with probability 0.5 guess uniformly distributed $x_i$, therefore it makes sence to expected lower bound of success to be $\leq \frac{1}{2}$, however it's $\leq \frac{1}{2} + \epsilon(n)$, it we can "safely ignore" $\epsilon(n)$ why to mention it, and the second point is it possible to run $A$ some fixed finite number of times to get probability infinitely close to 1?

Definition of one-way function. $x\in_R\{0,1\}^n, y=f(x), Pr[A(y)=x' s.t. f(x')=y] < \epsilon(n)$

In this case, the usage of negligible function is very intuitive, the success probability is upper bounded by negligible function $\epsilon(n)$. I am not sure how it's correlated with existence of computationally secure encryption scheme (of course =0 is preferable by encryption scheme), however if $\epsilon(n)$ can be safely ignored than it's ok.
The problem is I am not quite understand why do we need negligible function. By mentioning few definition I tried to be more specific about what exactly I don't understand.
I would appreciate if anyone can shed the light on the usage of negligible function

If you repeat an Algorithm $A$ with negligible probability  $\epsilon(n)$ of success for an input of length $n$ the number of times until the first success happens is a geometrically distributed random variable $S$. The expected value of $S$ is

$$\mathbb{E}(S) = \frac{1}{\epsilon(n)} = n^{\omega(1)} \quad .$$

So an attacker using $A$ polynomial many times  (say $p(n)$) can't have non negligible probability of success, which we'll see by comparing expected values. Let $A'$ be the algorithm which repeats $A$ $p(n)$ times and the random variable which represents the number of times $A'$ has to be repeated until the first success shall be named $S'$. Then:

$$\mathbb{E}(S) \leq p(n) \mathbb{E}(S')\quad,$$

so a non negligible success probability for $A'$ would mean a non negligible probability for $A$, since the product of two polynomials is again polynomial. So allowing negligible probabilities does no harm (at least for polynomial bounded adversaries).

This is essentially contains an indirect proof that $p(n)\epsilon(n)$ is still negligible for any polynomial $p$, which can also be proven directly: $p$ is dominated by its largest exponent, so $p(n)\in \mathcal O(n^c)$ for some $c \in\mathbb{N}$. On the other hand $\epsilon(n)\in o(n^{-d})$ for all $d\in\mathbb{N}$. Define $d'=d-c$ and you'll get $\epsilon(n)\in o(n^{-(d'+c)})$ for all $d'\in\mathbb{N}$. So $p(n)\epsilon(n)\in o(n^{-(d'+c)})\mathcal O(n^c)=o(n^{-d'})$ for all $d'\in\mathbb{N}$, which is again negligible.

If you insist on a probability of $0$ (or $\frac{1}{2}$ in the case of distinguishers) many applications become (nearly) impossible. Consider a cryptographic hash function $h$ and an unknown argument $x$. The probability of finding a preimage $x'$ s.t. $h(x')=h(x)$ taken over all $x$ can't be $0$, because testing all possible inputs will lead to success eventually. You could however choose to limit the probability with $2^{-n^{\Omega(1)}}$ or similar and call only those functions negligible. But most of the time only unbounded adversaries or efficient (i.e. polynomially bounded) adversaries are considered, so the different notions wouldn't matter, as an efficient adversary can break none and and unbounded can break both.


Prize collecting Steiner tree on graph without weights on edges I have been trying to find an easy-to-implement approximation algorithm on the problem of Prize collecting Steiner tree on node-weighted graph without weights on the edges. The closest I have come is the one in The prize collecting Steiner tree problem: Theory and Practice by Johnson, Minkoff and Phillips, but the GW algorithm provided won't work without weights on edges (I think).

The problem I'm trying to solve is:

Given a graph $G=(V,E,w)$, $w$ being a function assigning non-negative weights to nodes, and a set of query nodes $Q$, find a connected subgraph $H$ of $G$, spanning all nodes in $Q$, and also maximizing the following function

$$f(H) = \sum_{v\in V_H}w(v) + \min_{v \in V_H}\deg_H(v)$$

with $V_H \subseteq V$ being the set of nodes in $H$.

Keep in mind I need an easy to implement approximation algorithm to use as a baseline for comparison, so any LP or SDP ways to solve it, won't be of much help.

Something seems not quite right.  Your problem can be solved in polynomial time, so I doubt that it is NP-hard.  Let me explain how to solve it in polynomial time.

First note that there exists a positive integer $t$ such that your problem is equivalent to finding $H$ that maximizes

$$f_t(H) = \sum_{v \in V_H} w(v) + t,$$

subject to the additional constraint that $\deg_H(v) \ge t$ for all $v \in V_H$.  Also, $1 \le t \le n$, where $n=|V|$ is the number of vertices in $G$, so there are at most $O(n)$ possible values for $t$.  That means we can try them all and, for each $t$, find the optimal choice of $H$.  Given $t$, maximizing $f_t(H)$ can be done by a simple iterative fixpoint algorithm, where you keep as many vertices of $V$ as possible.

In this way, we obtain the following algorithm:

For $t := 1,2,\dots,n$:

a. Repeatedly delete vertices of degree $\le t$ until there are no more to delete.  In other words, while there exists $x \in V$ such that $\deg(x) \le t$, delete $x$ from $V$.

b. If there exists a single connected component of $G$ that contains all vertices of $Q$, set $H$ to be that component, compute $f(H)$, and if this $f(H)$ is better than anything found before, remember this $H$.

Correctness follows from the above discussion.  This can be implemented so that its running time is $O((n+m) \alpha(n))$, where $n=|V|$ and $m=|E|$ and $\alpha(\cdot)$ is the inverse Ackerman function.


What are the rules for positive recursive types in dependent type theory? I've recently started independently learning type theory, using a combination of papers found online and ncatlab.org (but have not worked with category theory), and am about to start reading TAPL.

I'm interested in understanding how recursive types can be substituted for inductive types in dependent type theory (we assume dependent sums, dependent products, identity types and finite types 0, 1, 2 in our background theory), however I am unable to find a definition for recursive types that doesn't use unrestricted fixpoint operators and hence lack strong normalisation.

I've attempted to do this myself, but the dependent eliminator seems slightly too weak, and a restriction on if b then x else y such that the boolean expression is evaluated before x and y can be reduced seems to be required for normalisation.

$$\frac{A:\text{Type} \vdash F(A):\text{Type} \\ A\text{ is positive in }F(A)}{\mu A.F(A):\text{Type}}$$

$$\frac{a:F(\mu A.F(A))}{S(A):\mu A.F(A)}$$

$$\frac{B:\text{Type}, b:B \vdash C(b,B):\text{Type} \\ B:\text{Type}, e: \prod_{b:B}C(b,B))\vdash R(B,e) : \prod_{f:F(B)}C(f,F(B))}{rec(R):\prod_{a:\mu A.F(A)}C(a, \mu A.F(A))}$$

$$\frac{B:\text{Type}, b:B \vdash C(b,B):\text{Type} \quad a:\mu A.F(A)\\ B:\text{Type}, e: \prod_{b:B}C(b,B))\vdash R(B,e) : \prod_{f:F(B)}C(f,F(B))}{rec(R)S(a)=R(\mu A.F(A),rec(R))a:C(a, \mu A.F(A))}$$

Where A is positive in F(A) precisely when A does not occur in any type indexing any dependent product types in F(A).

Is my formulation correct? What is the correct way to formulate rules for normalising recursive types, and are there any references that I could look at that expand on these?

Why are recursive types seldomly seen in dependent type theory?

The point of inductive types is precisely that you get normalization. Unrestricted recursive types simply lead to non-normalizing terms.

Given any type $A$, we may inhabit $A$ with a non-normalizing term as follows. Consider the recursive type
$$D = D \to A.$$
The term $\omega \mathrel{{:}{=}} \lambda d : D . d \; d$ has type $D \to A$ and it also has type $D$, since they are equal. Therefore $\omega \; \omega$ has type $A$, and in addition $\omega \; \omega$ reduces to itself, giving a non-normalizing term.

If instead of $D = D \to A$ we have just $D \cong D \to A$ then an easy adaptation of the above argument leads to the same conclusion. You just have to coerce $d$ to have type $D \to A$.

Is this bad? If you're using type theory to write programs then it probably isn't that bad. It's actually kind of cool. But if you're using type theory to do reasoning, i.e., you want ot use types as propositions, then it's bad because every type has an inhabitant and so every propostion has a proof. It just depends on what you want from type theory.

What are the rules for recursive types?

$\newcommand{\Type}{\mathsf{Type}}$
Let us try to formulate the rules for recursive types. A reasonable attempt goes along the same lines as what you've suggested:
$$\frac{\Gamma, X : \Type \vdash F(X) : \Type}{\Gamma\vdash \mu X . F(X) : \Type}$$
$$\frac{\Gamma \vdash e : F(\mu X . F(X))}{\Gamma \vdash S(e) : \mu X . F(X)}$$
$$\frac{\Gamma, y : \mu X . F(X) \vdash C(y) : \Type \qquad
  \Gamma, x : F(\mu X . F(X)) \vdash f(x) : C(S(x)) \quad
  \Gamma \vdash u : \mu X . F(X)
}{\Gamma \vdash \mathsf{rec}_F([x . f(x)], u) : C(u)}$$
We shouldn't forget to ask about equations that we expect to hold. The $\beta$-rule would be
$$\mathsf{rec}_F([x . f(x)], S(e)) = f(e)$$
and let us throw in an $\eta$-rule
$$S(\mathsf{rec}_F([x . x], u)) = u.$$
The $\eta$-rule says that if we take apart $u : \mu X . F(X)$ and put it back together, we will get $u$.
So far we have a map $S : F(\mu X . F(X)) \to \mu X . F(X)$, but we also want $R : \mu X . F(X) \to F(\mu X . F(X))$ together with
$$S(R(u)) = u \qquad\text{and}\qquad R(S(e)) = e \tag{1}$$
These say that $S$ and $R$ form an isomorphism between $F(\mu X . F(X))$ and $\mu X . F(X)$. We can get such an $R$, namely
$$R \mathbin{{:}{=}} \lambda y : F(\mu X . F(X)) . \mathsf{rec}_F([x . x], y).$$
Indeed, we have by the $\beta$-rule
$$R(S(e)) = \mathsf{rec}_F([x . x], S(e)) = e$$
and by the $\eta$-rule
$$S(R(u)) = S(\mathsf{rec}_F([x . x], u) = u.$$

We could have started with having $S$ and $R$ satisfying equations (1), and that would allow us to derive the eliminator as
$$\mathsf{rec}_F ([x . f(x)], u) = f(R(u)).$$
Such an eliminator satisfies the $\beta$-rule and the $\eta$-rule, quite obviously. This should give us pause. We discovered that our rules say precisely that $\mu X . F(X)$ is isomorphic to $F(\mu X . F(X))$ and nothing else. This is not good, because the rules should fix the meaning of $\mu X . F(X)$ up to equivalence of types.

To see that the rules are no good, consider the case $F(X) = X$. Every type is a fixed point of $F$, and our rules say nothing about which one $\mu X . X$ should be. Indeed, we can take an arbitrary type $A$ and set $R$ and $S$ to be the identity maps. That will satisfy all the rules for $\mu X . X$.

We should somehow state which fixed point of $F$ we have in mind when we write down $\mu X . F(X)$. a reasonable choice would be to ask for the smallest or initial one. But what does that mean? In category theory it means that there is a unique homomorphism from the algebra $S : F(\mu X . F(X)) \to \mu X . F(X)$ to any other $F$-algebra. Here we rely on the fact that $F$ is a functor so that we can reasonably talk about $F$ applied to a map. But our $F$ is not going to be a functor in general because it might break covariance (try to extend $F(X) = X \to X$ so that it takes $f : A \to B$ to some $F(f) : F(A) \to F(B)$ and you will see what the problem is). We are stuck, as we have no good criterion for picking one of possible fixed points of $F$!

The way out is to decompose $F : \Type \to \Type$ according to covariant and contravariant arguments,
$$F : \Type \times \Type^{\mathrm{op}} \to \Type.$$
For example $F(X) = X \to X$ becomes $F(X_1, X_2) = X_2 \to X_1$.  But now it's not clear what a fixed point of $F$ might be. All this leads to Freyd's notion of algebraically compact categories and a beautiful theory surrounding them. The theory can be applied to categorical models of programming languages to explain how recursive types work there. When we throw in dependent types, then as far as I know, things break and nobody knows what to do. But I would love to be proved wrong!

The sort of recursive types we spoke about here goes under the name isorecursive types. The other option are equirecursive types, see the same link.


Transition diagram for following token number number ->  digits(.digits)?(E[+ -]?digits)?
This transition diagram runs the  above mentioned token I can not understand this how this is work.what is meaning of "?"Symbol and digits. can anyone explain me this

digits(.digits)?(E[+ -]?digits)? is a regular expression for the set of strings that the pictured automaton accepts. That is, all of the strings accepted by the automaton will match this pattern. If you're unfamiliar with regular expression syntax, you can check out this explanation from Wikipedia.

In particular, if you see some pattern followed by the ? operator, it means that pattern is optional. So something like digits(.digits)? will match strings of the form digits.digits or just digits because the last (.digits) part is optional.

I would guess that digits is a placeholder for a series of numeric digits (0-9). So something like digits(.digits)? would match strings like "33.5", "0.8", "1.892", "7", etc.


Elements in a less than a value in a subarray Let A be an fixed array of size n. Q(i,j,k) is number of elements from A[i] to A[j] which are less than k.

Currently I am using segment tree with each node containing sorted array of leaf elements. This answers the query in O((log n)^2) with O(n*log n) space and per-processing.

Is there a way to answer this in O(log n) while keeping the per-processing and space complexity same.

This is essentially the 2D orthogonal range counting problem from computational geometry, which has attracted a lot of attention over the years. Fractional cascading definitely could be applied to reduce the query time to logarithmic while preserving the other big-O bounds. In a nutshell, the idea is to make auxiliary data structures that relate the positions of elements in each parent array to positions in the child array, so that, given the results of a search in the parent, searching the child for the same key is constant-time.


Proof high-entropy sequences are hard to compress When comparing random-variable sequences generated from probability distributions, what's a formal proof that a distribution with higher entropy produces a sequence that's "harder" to compress?

In background reading, I haven't come across this analysis for a general, abstract probability distribution. The information theory texts I've looked at, rather, tend to focus their analysis on comparing compression algorithms rather than comparing the distributions producing the data.

You are looking for Shannon's source coding theorem.


TM decidability using pigeonhole principle I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question?

I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question?

You can easily simulate any DFA in your model, and so your model accepts all regular languages. In particular, it also accepts some infinite languages, for example the language of all words.

Your class of machines is two-way finite automata, and it is known to accept the regular languages, that is, it coincides in power with one-way finite automata such as DFAs and NFAs.
However, that is not the answer that the setter had in mind. Rather, imagine the working of such a machine, having $m$ states, on an input word of length $n$. The head could be in $n+2$ different positions, and consequently the machine can be in $(n+2)m$ different configurations. Therefore, after that many steps, either the machine has halted (either accepting or rejecting the input), or some configuration has repeated (by the pigeonhole principle), in which case the machine is in an infinite loop, and will never accept. Hence after $(n+2)m$ steps we can already tell the fate of the input.


Query: Given a graph, is edge x in an optimal TSP tour? Consider the decision problem that when given a graph, we need to decide if a particular edge belongs to any optimal solution to the traveling salesman problem on that graph.

It may be argued that the complexity of this problem is strictly greater than any co-NP problem. The idea is that it's perhaps impossible to come up with a counter-example, since we need e.g. an optimal tour candidate before we can consider a counterexample (but no optimal tour candidate is given in this problem statement).

On the other hand, it may be argued that the complexity of this problem is strictly smaller than any P-space-complete problem, as our problem may be seen as

$\exists$"a tour A containing x" $\forall$"tours B": (some formula stating that A <= B)

whereas some probably "minimal" P-space-complete problem has O(n) alternations of $\exists$ and $\forall$: the quantified boolean formula problem (QBF).

Based on this argument, is it reasonable to expect that there's a complexity class between co-NP and PSPACE? Does this particular class have a name? Can we expect to find arbitrarily more such classes by adding another one alternation of $\forall$ or $\exists$ to the previously found such class?

The complexity class $\Sigma_2^P$, which is the second level of the polynomial hierarchy, consists of all languages $L$ for which there exists a polytime predicate $f$ and a polynomial $p$ such that
$$
x \in L \Longleftrightarrow \exists y \forall z \, f(x,y,z), \text{ where } |y|,|z| \leq p(|x|).
$$
This is the natural location for your problem:

$x$ is a pair $(G,e)$, where $G$ is a graph and $e$ is an edge of $G$.
$y$ is a TSP tour.
$z$ is a TSP tour.
$f(x,y,z)$ holds if (i) $y,z$ are TSP tours of $G$; (ii) $e \in y$; and (iii) $w(y) \leq w(z)$.

More generally, $\Sigma_k^P$ is defined similarly with $k$ quantifier alternations, and $\Pi_k^P$ is defined the same but starting with a universal rather than an existential quantifier. For example, $\Sigma_1^P$ is NP and $\Pi_1^P$ is coNP. We also define $\Delta_k^P = \Sigma_k^p \cap \Pi_k^P$, generalizing the class NP∩coNP.

We define $\Sigma_k^P$-hard and $\Sigma_k^P$-complete in analog to NP-hard and NP-complete, using polynomial time reductions. The obvious question to ask in your case is whether your language is $\Sigma_2^P$-complete.


How do I approach inductive design problems with no information or context given? As a starting point for our course in Artificial Intelligence, we are being taught induction. We received a number of homework assignments where we have to show our inductive approach for a given problem.

An example of such a problem: "Sort an array of N numbers".

Reading through the course material and online sources I feel I have grasped the first concepts of induction. I have successfully proven some statements using induction, such as the number of steps for the Tower of Hanoi problem. However, I was able to prove it because I had some information beforehand, such as the number of steps required to move the tower in the form of a formula.

In the problems handed to us, we get a sentence like the one above and are asked: "Describe the inductive approach"

Should I select an arbitrary sorting algorithm, make my own assumptions and devise my own hypothesis and try to prove that? I just want to prove that the array is indeed sorted for any given number of N. What are some exemplary steps I could take in order to provide the inductive approach given that single sentence of "Sort an array of N elements"

Most questions in AI textbooks of this style are intended to be open ended so that the student can experiment on its own with the problem. So the golden rule is do as you see fit to provide the best learning!

In particular for this problem, your approach seems appropriate.

Since most sorting algorithms fall into a divide and conquer schema, you won't have problem fitting it into an inductive schema.

For example, you could take quicksort, which is usually implemented recursively. And then prove that it indeed sorts an array of size $n$ assuming that it sorts an array of size less than $n$.


Recognizer to check if the language of a Turing machine contains a finite subset Let $B = \{ 123 \}$.

Note that $B$ is finite.

Let $L = \left \{ \left\langle M \right\rangle | M \text{ is a Turing machine such that } B \subseteq L(M)  \right\}$.

Is it sufficient to show that $L$ is recognizable by checking if $M$ accepts on input $123$, and therefore $\left\langle M \right\rangle \in L$?

Yes, it is sufficient.

$\langle M \rangle \in L \Longleftrightarrow B\subseteq L(M) \Longleftrightarrow M\text{ accepts all strings in }B \Longleftrightarrow M\text{ accepts }123$.


Properties of Reverse Polish Notation expressions that are algebraically invariant The RPN expressions

a b + c *

and

f d e + *

are algebraically equivalent, though the names of the variables are different and the order of evaluation is slightly different. The expressions

a b * c +

a b * c *

though they have the same length and number of variables as the first expression, are not algebraically equivalent, i.e. in general

c (a + b) ≠ c + a * b
c (a + b) ≠ a * b * c

Without substituting values for any of the variables, is there a property that we could compute which is the same for a b + c * and f d e + * but not for a b + c * and a b * c + or a b * c *?

Assume the variables are real numbers, not e.g. matrices, so + and * are commutative, but - and ÷ are not.

This is a simple example of a broader question I am interested in: what are some properties that RPN expressions (i.e. unambiguous expression trees) have that are different for algebraically different expressions but do not change when the names or order of evaluation of the variables change?

This would be useful because it would be a kind of fingerprint for algebraic expressions that would not change merely because of choice of variable names.

I realize that this could be a big topic; references to sections of textbooks or research articles are welcome.

You ask for a computable property that can be used as a fingerprint for equivalence (algebraic equivalence in your case).
There are two general approaches to this kind of question:

Take a canonical element of the equivalence class (a normal form) as the fingerprint.
Take the equivalence class itself as the fingerprint. Of course this requires classes to be finite. For computability of the equivalence class we also need a computable bound on the size of members of the class. (Plus decidability of equivalence. But that is a general requirement, because fingerprints imply this decidability.)

In this answer I only consider the case where you only have addition, subtraction, and multiplication. None of your examples has division, so I assume that this restriction already is relevant for you. In this case, an algebraic expression essentially (up to syntax) is a multivariate polynomial.
For example, the expression $x\cdot(x-z-z)$ yields the polynomial $x^2-2xz$ (more precisely $\sum\{x^2, -2\prod\{x,z\}\}$, to stress that polynomials do not carry information about the order of additions or multiplications. That is, $x^2-2xz$ is the same polynomial as e.g. $-2zx+x^2$).
This polynomial is already close to the fingerprint you want: Different polynomials are extensionally different over the real numbers. Which means that they can be shown to be different by subtituting suitable real values.
Hence polynomials are normal forms for expressions.

Renaming of variables is not yet covered. (Also observe that normalizing to polynomials may have the effect of losing variables: $x+y-x$ would be normalized to $y$, in which $x$ does not occur any more.)
But we can take equivalence classes of polynomials: The degree and number of monomials imply a size bound. Equivalence is decidable just by trying out variable renamings.
With canonical variable names $x_1, x_2, x_3, \ldots$, the above polynomial $x^2-2xz$ yields the equivalence class $\{x_1^2-2x_1x_2, x_2^2-2x_1x_2\}$.

While we have achieved computability, we do not yet have efficiency. So, can we do any better? Can we have a normal form for polynomials? If you consider the special case where all monomials are the product of two distinct variables (like $x\cdot y$), the problem of canonizing polynomials becomes graph canonization, whose complexity is unknown.


Determining if an integer appears more than $n/2$ times What is the minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers?

I am trying binary search on the array A.

Algorithm(A):

x = A[mid], where mid is the middle element of the array.
Compare x with A[n/4] and A[3n/4].
If x = A[n/4] and x ≠ A[3n/4] then search in A[1] to A[3n/4 + 1].
If x ≠ A[n/4] and x = A[3n/4] then search in A[n/4 + 1] to A[n].
If x ≠ A[n/4] and x ≠ A[3n/4] then it is a no instance.
If x = A[n/4] and x = A[3n/4] then it is a yes instance.

Running Time: $T(n) = T(3n/4) + O(1)$ which is $O(\log n)$ in asymptotic sense. At each step I am doing two comparisons so $2\log_4n$ if $n = 4^k$.
Is there any better (optimal) algorithm to solve the problem mentioned above?

Also, I don't know how to prove the lower bound.

You are asking two questions. I will only answer the second one. Consider the following set of possible inputs: the array is contains either $n/2$ or $n/2+1$ copies of $0$, all elements preceding it are $-1$, and all elements following it are $+1$.

I claim that any algorithm which works correctly for this set of inputs must query, in the YES instances, the first and the last position of the stretch of zeroes. Indeed, if it never queries the first position for example, then the input could have been the NO instance in which the value at that position is replaced by $-1$.

Since the first and last position of zero are at distance exactly $n/2$, and are the only two positions at that distance of equal value, we see that any correct algorithm for your problem can be modified (without any additional comparisons) to give an algorithm for the following problem:

  Given an array consisting of $n/2+1$ zeroes, preceded by $-1$ entries and followed by $1$ entries, find the location of the zeroes.

Since there are $n/2$ different answers to this problem, the usual decision tree argument shows that any comparison-based algorithm must make $\log_3 n - O(1)$ three-way comparisons, or $\log_2 n - O(1)$ two-way comparisons of the form "$x=y$ or $x \neq y$?". This shows that for two-way comparisons, your algorithm is nearly optimal. (Note that $2\log_4 n = \log_2 n $.)


Linear algorithm to measure how sorted an array is I've just attended an algorithm course, in which I've seen many sorting algorithms performing better or worse depending on how much the elements of an array are sorted already. For example, for what I've heard, quicksort is preferred most of the times, yet still it has $O(n^2)$ complexity in case the array is sorted already.

My question is if there is a way to measure in linear time how sorted the array is, and then decide which algorithm is better to use. By measure I mean an algorithm that outputs 1 if the array is sorted already, values closed to 1 if just a few values are unordered, 0 if the input is sorted from the highest to the lowest value. Depending on this output, we could decide if it's a good idea to use quicksort, or we should use some other sorting algorithm.

Meanwhile knowing how "sorted" an array is gives some information about the array and might help sorting it more efficiently, it is not quite right, that quick-sort runs in $O(n^2)$ if the array is sorted. The running time of quick-sort depends on the pivoting rule and your statement holds only if we always choose the first (or last) element as the pivot. A good way to avoid this problem is to shuffle the whole input randomly before we start sorting.

Now to gain more information about how "sorted" the array is, we have to define this quantity formally. We need a formal mathematical definition of "sortedness" before we can design an algorithm to measure it. Here are two different quantities that show in some way the "sortedness" of the array. Let us call the input array $A := a_1, \dots a_n$ where $n$ is the length of the array.

The first of which is the number of "inversions". So what are inversions? - you might ask. Inversions are pairs $(i, j)$ such that $i < j$ and $a_i > a_j$. Of course in a sorted array we have no inversions. Counting inversions can be done in running time $O(n\log n)$ using different methods among which are divide and conquer and using balanced search trees. However since counting inversions is not faster than sorting, I would not recommend it to find how sorted an array is as a pre-sorting routine.

Another measure is the minimum number of elements to be removed to turn the array sorted. This problem is equivalent to finding the longest increasing subsequence and it has an $O(n \log n)$ algorithm using dynamic programming. However, there is an simple linear time two approximation algorithm for this problem. Intuitively, the algorithm removes pairs of adjacent inversions until the array contains no more inversions. In pseudo-code the algorithm goes as follows:

- Let L be an empty linked list
- For each a := a[1] .. a[n] do
 - Append a to L.
- Set i := 1
- While a[i] is not the last element in L
 - while  a[i] no the first element in L
     and a[i] < a[i-1] do
  - remove a[i] and a[i-1] from L
  - Set i to the next element.
 - Set i to the next element.

Each time we remove two elements from $L$, they form an inversion an at least one of them should be removed. Hence we remove at most twice as many as the total number of elements that must be removed. Note that the running time can be bounded in $O(n)$ since the outer while iterate over all elements once and each call of the inner loop removes two elements and hence it can not be called more than $O(n)$ times in total.

One way to use this measure to sort arrays more efficiently is to use the previous algorithm to find all such pairs. Let $L_1$ be the list above after removing the elements from it and $L_2$ the list of all removed elements. Now since we know that $L_1$ is sorted, all we need to do is to sort $L_2$ in $O(h\log h)$ assuming $h$ is the number of elements has to be removed to turn the array sorted. Using some kind of sliding window (the conquer part of merge sort), we can build a sorted version of $A$ combining $A_1$ and the sorted version of $A_2$ in linear time. In total we get an adaptive sorting algorithm running in $O(n + h \log h)$.


What is usually the next step after showing the VC dimension? I am new to statistical learning. I have a structure $X$ where I showed its hypothesis class $H$ has VC dimension $d$. All I know now is that I can bound the number of examples by $m\geq \frac{1}{\epsilon}ln \frac{d}{\delta}$ and with probability at least $1-\delta$ I will get a hypothesis with error at most $\epsilon$.

My question concerns what is usually the next step(s),with regard to the big picture of learning a structure $X$, after showing its VCD?

I thought about studying other complexity measures for $X$ but wish to hear others suggestions.

A distinction should be made between constructing practical machine learning algorithms and theoretical algorithms, such as PAC learning algorithms. A machine learning practitioner doesn't usually invoke the concept of VC dimension — indeed, many of them probably have never heard of it, especially if they're applying machine learning in some other subject. While VC dimension might be useful in coming up with algorithms (as in the case of SVMs), it appears to have no practical import.

When constructing theoretical algorithms such as learning algorithms under the PAC model, the story could be different, but unfortunately I don't know too much about that. From the little I've seen, VC dimension doesn't get mentioned even there. In fact, it seems that VC dimension is mentioned mostly in literature attempting to relate it to other parameters.


Checking for intersection of $d$-dimensional spheres Is there a simple algorithm to check whether $n$ different balls (of the same radius) in $\mathbb{R}^d$ intersect? That is, coordinates of their centers $x_i$ are given, radius $R$ is given and we need to determine if there exists a point $p$ such that $$\| p - x_i \| \leq R \quad \forall i.$$
In other words, check whether there is a point $p$ that is contained in all $n$ balls.

This is an instance of the smallest enclosing ball problem.

An equivalent statement of your problem is: Given points $x_1,\dots,x_n$, we want to determine whether there exists a point $p$ such that every point $x_i$ is at distance at most $R$ from $p$, i.e., we want to find a sphere of radius $R$ that encloses all of the points $x_1,\dots,x_n$.

So, find the smallest enclosing ball that contains all of $x_1,\dots,x_n$; then check whether the radius of that ball is at most $R$ or not.  The smallest enclosing ball problem is well-studied and you can find references and algorithms in the Wikipedia page I linked to.


Is it possible to make a grammar LL($1$) which recognizes palindroms? Is it possible to make an algebraic grammar LL($1$) which recognizes palindroms for an alphabet $\{a,b\}$?

No. The language of palindromes over any alphabet with at least two elements is not deterministic, and thus has no LR or LL grammar.
The language of even-length palindromes $L_{epal}=\{ww^R \mid w\in\Sigmạ^*\}$  is a classic example of a non-deterministic context-free language, and you can find the outline of a proof in Hopcroft & Ullman (and other standard texts). The restriction to even-length palindromes simplifies the proof, but it can be extended to the language of all palindromes $L_{pal}=\{w \mid w=w^R, w\in\Sigmạ^* \}$. Without doing more work, though, it's evident that $L_{epal}=L_{pal}\cap (\Sigma\Sigma)^*$, and deterministic CFLs are closed against intersection with regular languages.


Number of path with given length within an unrooted Tree Given a Tree (without a root) function w : v -> N and a number C - How can we count the number of verticies with distance between them equal to C.

I was thinking about some smart vertice numbering so we could use dynamic programing to do it but after some thinking it is no good.

I would be really thankful for any tips.

Hint: divide-and-conquer.  How many paths are there of length C in the left subtree of the root?  How many in the right subtree?  How many others not covered by either of those two cases?


How should I choose the neighborhood structure for simulated annealing for my problem? There are $n$ students and $m$ courses. Each student $i$ wants to attend a subset $C_i \subseteq \{1,\ldots,m\}$ of the courses. There are $k$ time slots on a weekly schedule. The goal is to select a time slot for each course such that the students can attend as many courses as possible, that is, find a mapping $f: \{1,\ldots,m\} \rightarrow \{1,\ldots,k\}$ such that the following objective function is maximized:

$$\sum_{i = 1}^n \big| \bigcup_{j \in C_i} \{f(j)\} \big| $$

For my (artificial) instance $n = 10^5, m = 5000, k = 25$, and any student wants to attend at most 16 courses. I have tried a hill climbing algorithm which moves in the search space by changing one course at a time in the mapping $f$ if it improves the objective function, until it can improve no more. This gives a local maximum, but I'd like to do better. I've tried to implement a simulated annealing approach with the same neighbourhood structure, but I haven't been able to tune the parameters to beat the hill climbing algorithm.

I've read that the number of moves from any part of the search space to another part should be small. In my solution I need at most $5000$ moves, is this too much? If make bigger changes into the mapping, the evaluation of the cost function becomes expensive, as I have to recompute the objective function for every student affected by the change. What kind of a neighbourhood structure would suit this problem the best?

Simulated annealing can cope with neighborhood structures where you have to walk quite a bit to reach a distant point. Of course, the minimum distance between two points in the state space should at most be polynomial in the problem size, but any reasonable optimization heuristics will also require this restriction. The 5000 moves are completely reasonable for simulated annealing, especially since this is linear in $m$.

Don't implement any moves which would be very expensive to evaluate. The strength of simulated annealing is that it can work with moves which are cheap to evaluate, and hence evaluate a large number of candidate solutions. But if your state space is large, then you should also let simulated annealing evaluate a large number of candidate solutions. So your cool down schedule becomes important in this case. I could go into more detail here, but the question was about the neighborhood structure only, and the answer to this question is that your neighborhood structure is basically OK, and you should not use a neighborhood structure which would lead to expensive recomputations.


Efficiently partition tree into clusters of similar diameter I am looking for a way to split a tree into $k$ clusters so that the cluster with largest diameter is as small as possible. All edges have the same length.  I'm hoping for an algorithm that can handle arbitrary trees (with arbitrary branching factor), not just binary trees.

Your problem is equivalent to the following:

Input: a tree $T$, an integer $r$ (the radius)
Find: a set $S$ of $k$ vertices, such that every vertex in the tree is at distance $\le r$ from one of the vertices in $S$; or failure if no such set exists

Why is this equivalent?  Well, if you have such a set $S$, then you immediately can find $k$ clusters of diameter $\le 2r$ (for each $s \in S$, you get a cluster of nodes that are at distance $\le r$ from $s$).  Conversely, if you have $k$ clusters of diameter $\le 2r$, then you can find such a set $S$: given a cluster, pick a pair of nodes $x,y$ in the cluster that maximizes $d(x,y)$; then find a shortest path from $x$ to $y$, and let $s$ be a node halfway along that shortest path; then one can prove every node in the cluster is at distance $\le r$ from $s$.  So, if you can solve the above problem, then linear search or binary search on $r$ will find the smallest such diameter.

The best algorithm I can find for this problem is the trivial $O(n^{k+1})$ algorithm: enumerate all subsets of size $k$, and test each to see whether it satisfies all the requirements.  The number of sets you must enumerate is $C(n,k) = O(n^k)$, and given a candidate set you can test whether it is valid in $O(n)$ time.  Unfortunately, for modest or large values of $k$, this will be totally impractical.

As an optimization, you can let $S'$ be the set of vertices that are at height $\ge r$.  (The height of a vertex $v$ is the length of the longest downward path from $v$ to a leaf; in other words, the height of a leaf is $0$, and the height of an internal node is one more than the height of its highest child.)  Then, you only need to enumerate subsets of $S'$ of size $k$.  In practice, this might provide a significant improvement, even though asymptotically it might not make much of a difference to the worst-case running time.

I don't know whether it is possible to do better, or whether a polynomial-time algorithm exists.  I think the problem can be solved in polynomial time for binary trees using dynamic programming, but you want to handle arbitrary trees, and I don't know what happens in that case.


SImple NP-hard proof question $3SATplus$

Input: 2 CNF formulas $F_1$, $F_2$ where all clauses have exactly $3$ literals.

Question: Does every truth assignment satisfy at-least as many $F_2$ clauses as $F_1$'s?

Assume $3SATPLUS \in NP$
Prove $3SAT \leq_p$ $3SATplus$
The reduction is as follows
$F_1 = (x \lor \bar{x} \lor x) \land \dots \land (x \lor \bar{x} \lor x)$
For $n$ clauses. This means it will always accept $n$ clauses.
$F_2 = F$
This is polytime because its $2n$ clauses only $n$ more than $F$
if $F \in 3SAT$, then $F_1 = F_2$ since they both satisfy $n$ clauses so $F_1, F_2 \in 3SATplus$
I'll prove the contrapositive
If $F \notin 3SAT$, then $F_1$ satisfies $n$ clauses and $F_2$ can satisfies only up to $n-1$ so $F_1 > F_2$ always. Hence,  $F_1, F_2 \notin 3SATplus$
Is there anything else left to say or does this confirm its $NP-hard$?

If $F\in 3SAT$ it means that there is some assignment that satisfies $n$ clauses. It doesn't mean that every assignment satisfies all clauses. This makes the reduction wrong, since there might be an assignment for $F\in 3SAT$ that satisfies fewer than $n$ clauses. The reduction you've proposed would be valid if you started with $Tautology$, but then, that problem isn't known to be $NP$-complete.

Your problem is $coNP$-complete (as the reduction from $Tautology$ shows), so finding a reduction from $3SAT$ would prove $NP\subseteq coNP$.


Exercise 11 of section 3.2.2(The art of computer programming) I'm asking about its part a.

a) If $f(z),\space a(z),\space b(z)$ are polynomials with integer coefficients, let
us write $a(z)\equiv b(z) (\operatorname{mod} f(z)\space and\space m)$
if $a(z) = b(z) + f(z)u(z) + mv(z)$. Prove that the following statement
holds when $p^e>2$ (p prime) , $f(0)=1$:
If $z^\lambda \equiv 1 (\operatorname{mod} f(z)\space and\space p^{e})$ and $z^\lambda \not\equiv 1 (\operatorname{mod} f(z)\space
and\space p^{e+1})$ then $z^{p\lambda} \equiv 1 (\operatorname{mod}
f(z)\space and\space p^{e+1})\space but\space z^{p\lambda} \not\equiv
1 (\operatorname{mod} f(z)\space and\space p^{e+2})$

Here's my reasoning:
We have $z^\lambda$ has the form of
$$f(z)u(z) + p^ev(z) + 1$$
where $p^{e+1}|f(z)u(z),f(z)|p^ev(z)$ and $v(z)\not\equiv 0(\operatorname{mod} p)$  (*)
Or we can just simplify it as: $z^\lambda = Z + 1$, where Z is a multiple of $f(z)$ and $p^e$ but not $p^{e+1}$'s one.
So:$$z^{p\lambda} = 1+{p\choose 1}Z+{p\choose 2}Z^2+...$$
$z^{p\lambda}-1$ is certainly divisable by f(z). Also, we can see that ${p\choose k}Z^k(1\leqslant k\leqslant p-1)$ is a multiple of $p^{e+1}$ and $p^{e+2}|Z^p$(due to the fact $p^e>2$,$p^{pe}|Z^p$ implies $p^{e+2}|Z^p$). We now can conclude:
$$z^{p\lambda} \equiv 1 (\operatorname{mod}
f(z)\space and\space p^{e+1})$$
Next, it's easy to establish: $p^{e+2}|p^{(e+1)k}$,where $k\geqslant$ 2. And that shows:
$$z^{p\lambda} \equiv 1 + p^{e+1}v(z) (\operatorname{mod} p^{e+2}\space and\space f(z))$$
Due to (*),$1+ p^{e+1}v(z) \not\equiv 1(\operatorname{mod} p^{e+2})$, completing the proof

My proof is based on the answer of excercise 11. And the difference between it and mine makes me confused.

If $p^{e+1}v(z) \equiv 0 (\operatorname{mod} f(z)\space and\space p^{e+2})$, there must exist $a(z)$ and $b(z)$ such that $p^{e+1}(v(z) +pa(z)) = f(z)b(z)$.
Since $f(0)=1$, this implies $p^{e+1}|b(z)$(by Guass's lemma 4.6.1G); hence $v(z) \equiv 0 (\operatorname{mod} f(z)\space and\space p)$, a contradiction.

So, my questions are:
1. Why is the above argument necessary?
2. Is the Gauss's lemma 4.6.1G the one in wikipedia?

We have $z^\lambda$ has the form of
  $$f(z)u(z) + p^ev(z) + 1$$
  where $p^{e+1}\mid f(z)u(z),f(z)\mid p^ev(z)$ and $v(z)\not\equiv 0\pmod p\ $  (*)

You misunderstood the definition of $a(z)\equiv b(z)\pmod {f(z)\text { and }m}$. If $z^\lambda \equiv 1 \pmod{ f(z)\text{ and }p^{e}}$, then $$z^\lambda=1 + f(z)u(z) + p^ev(z)$$
for some $u(z), v(z)$. There is no further requirement on $u(z)$ and $v(z)$. It is incorrect to deduce $p^{e+1}\mid f(z)u(z)$. It is incorrect to deduce $f(z)\mid p^ev(z)$.

However, if we also have $z^\lambda \not\equiv 1 \pmod{ f(z)\text{ and }p^{e+1}}$, then we must have $v(z) \not\equiv 1 \pmod{ f(z)\text{ and }p}.$

  Why is the above argument necessary?

Now that you can understand the notation correctly, you can figure it out by yourself.

  Is the Gauss's lemma 4.6.1G the one in Wikipedia?

Yes, lemma 4.6.1G in the book is the same as the Gauss's lemma on Wikipedia.


I can not understand some petri net properties ( quasi-liveness and liveness ) Can anyone please help me understand the quasi-liveness and liveness properties of petri nets. Suppose that you explain that to a person with 10 years old.

For my part, i have the following definitions.
- quasi-liveness petri net: its mean that every transition in the net can be enabled at least one time for specific marketing. So may be enabled many times.
-liveness petri net: its mean that every transition in the net can be rechargeable from any marketing.

Am i right ?, can you give me a simple example. Finally what is the best method to find these properties ?

To answer your first question:

An attempt to explain Petri nets in terms some 10-year olds will understand (see, for instance, Murata's well-known description):

A Petri net is a diagram that consists of three kinds of elements. We call them transitions, places, and arcs. In the example above, the transitions are green boxes and the places are white rounds. The arcs are arrows that run from places to transitions and from transitions to places. Transitions and places have names. A place may contain tokens. A token is usually drawn as a little dot.
A Petri net describes a set of circumstances in which changes can happen in certain ways. It describes exactly how the changes can happen. For each change, it describes the conditions under which it can occur, and the conditions that result from the change.
A transition describes a possible change. Its name should name that change. For example: a customer arrives, or: switch the light off, or: the light breaks, or: the sun goes down.
A place describes a possible condition. Its name should name that condition and should be of the form: something (for example: a person, thing, place, etc.) is something (a condition that that person, thing, place, etc. is in).  For example: the sun is shining, or: a customer is waiting, or: a spot is available, or: the light is broken.
A token describes a particular something for which the condition holds, and to which the change applies. For instance: the sun shining, or: a customer waiting, or: a spot being available, or: the light being broken.
The arcs describe which conditions must hold for a change to occur, by running from exactly those places to that transition. They describe which conditions will hold as a result of the change, by running from that transition to exactly those places. In the example given above: switch light on is only possible if the light is off; after switch light on, the light is on. Etcetera.
As we said above, the places of a Petri net can contain tokens. In some Petri nets, like the example above, they never contain more than one token; in other examples they do contain more than one token. When a change occurs (we say: a transition fires), usually the count of tokens changes: some places get fewer tokens and other places get more. We can describe the state we are in by saying how many tokens are in each place. We call such a listing a marking of the Petri net. So a marking lists for each place how many tokens are in that place.

In the example above, the marking has only one token, in light is on.
Only two transitions can fire: the upper light breaks and light is off.

If light breaks fires, we end up in the marking that has one token in light is broken and no tokens elsewhere. After that, no transition can ever fire again.

If instead, switch light off fires, we end up in the marking that has one token in light is off and no tokens elsewhere. In that marking, two transitions can fire, namely the lower light breaks and switch light on.

If light breaks fires, we end up in the marking that has one token in light is broken and no tokens elsewhere. After that, no transition can ever fire again.

If instead, switch light on fires, we end up in the marking that we started with.

With that out of the way, we can describe quasi-liveness and liveness:

A transition is said to be quasi-live if it can be fired at least once.  That is, from the present marking, either it can fire directly, or by firing transitions it is possible to arrive in a marking in which it can fire directly.  In other words: in the present situation, there is a way in which this change can occur, either now or in the future.

In the example above, every transition is quasi-live: as we have seen, two transitions can fire directly, while for the other two, a transition can fire such that they can then fire.

A marking is said to be quasi-live if all transitions are quasi-live for that marking.   In other words: in the present situation, all changes can still occur, either right away or later. This is the case in the example above.

A marking is said to be dead, a deadlock, if no transitions can fire. No changes can ever occur. This is the case for the marking we reach after firing one of the light breaks transitions.

A transition is said to be live if it is quasi-live in every possible marking.  That is to say: in any situation, that change can still occur, either right away or later. In the example above, no transition is live: we have found a dead marking, in which none of them can fire.

A Petri net is said to be live if all of its transitions are live. In any situation, all of the changes can still occur.  Clearly this is not the case in the example above.

We can change the example by adding new transitions: repair light. That would give us a live Petri net.

To answer your second question: a standard reference for how to determine liveness of Petri nets is Murata's article mentioned above. I recommend it; it is readable and the techniques it describes are readily applicable.

Deciding whether an arbitrary Petri net is live is possible, but very hard.
See, for instance, this informal discussion by prof. Javier Esparza. A fairly recent article (E. Best and H. Wimmel, Structure Theory of Petri Nets in: Transactions on Petri Nets and Other Models of Concurrency VII, 2013) says:

  For liveness we know that it is at least as hard as the reachability problem. The latter is EXPSPACE-hard, and no upper complexity bounds are known at the present time.

So researchers have focused on defining limited classes of Petri nets for which properties such as liveness are easier to decide; for instance, it is co-NP-complete for free-choice nets.


If $PSPACE^{SAT}=PSPACE$ and $PSPACE \subseteq EXP$, then why does $EXP^{SAT}$ not necessarily equal to $EXP$? I read the following claim:

$PSPACE^{SAT}=PSPACE$
$EXP^{SAT}$ is not necessarily the same as $EXP$

The first claim makes sense; $PSPACE \subseteq PSPACE^{SAT}$ trivially, and for any language $B \in PSPACE^{SAT}$ decided by an oracle machine $M_B$, we can define a non-deterministic machine $M'_B$ that works like $M_B$, except instead of querying an oracle, $M'_B$ instead guesses a witness and calls $M_{SAT}$ (a machine deciding $SAT$). It can easily be shown that $M'_B$ decides $B$ in polynomial space, and so $B\in NSPACE$. But from Savitch's Thoerem, $NSPACE=PSPACE$, and so $B \in PSPACE$. Thus, $PSPACE^{SAT}=PSPACE$.
I assumed that since $PSPACE \subseteq EXP$, then it should follow that $EXP^{SAT}=EXP$ as well. After all, it only needs to be shown that $EXP^{SAT}\subseteq EXP$ to prove the claim, but I can't see where the problem lies.
For that matter, my assumption was that if $X$ was any complexity class such that $X\subseteq Y$, then $Y^X=Y$. After all, any X-oracle doesn't allow Y to decide any language it couldn't already decide. But if the two claims are true, then obviously my assumption is wrong.

The fact that the base class can simulate the oracle does not mean that the oracle does not give additional power. Consider the polynomial hierarchy, $\mathsf{NP,NP^{NP},NP^{NP^{NP}}},...$ at the $i$'th level you get an oracle for the $i-1$ level, so following your line of thought we should not gain additional power. However a naive simulation of the oracle does not suffice, since taking the wrong path may lead us to accept an input outside the language (we need to be sure of the oracle's answers).
A class which is famously not low on itself is $\mathsf{EXP}$, since $\mathsf{EXP^{EXP}=2EXP}$. A naive simulation in your case fails for similar reasons, as a machine in $\mathsf{EXP^{SAT}}$ can ask the about the satisfiability of exponentially long formulas.


Maximizing the boolean combination of given real numbers with dependencies Let $x_i,x_{ij}\in\mathbb{R}$ and $b_i\in\{0,1\}$ for all $i,j\in\{1,2,\ldots,n\}$ and $j>i$. I want to know which of all the possible boolean combinations make(s) the following expression maximal: $$\sum_i b_ix_i+\sum_{j>i}b_ib_jx_{ij}$$

I can think of greedy heuristics (for example, identify the $x_{ij}<0$ and then set either $b_i$ or $b_j$ to zero if $x_i<0$ or $x_j<0$, respectively), but these don't necessarily have always to give the best answer. Is there any optimal algorithm for this or, at least, an approximation one?

It is often more natural to consider $b_i \in \{\pm 1\}$ rather than $b_i \in \{0,1\}$, and it is not difficult to convert your formulation to an equivalent one which uses $\pm 1$ variables rather than $0/1$ variables, using essentially the substitution $b'_i = 2b_i-1$. It is then possible to eliminate the linear term by adding a new variable $b_0$ and replacing $x_i$ with $x_{0i}$. The new problem can be formulated as:

  Maximize $x' M x$ over $\{\pm1\}^n$, where $M$ is a symmetric matrix with zeroes on the diagonal.

(We can assume without loss of generality that $M$ is symmetric and that its diagonal elements are zero, the latter since $(\pm 1)^2 = 1$.)

This problem is known variously as quadratic programming, binary quadratic programming, Boolean quadratic programming, unconstrained binary quadratic programming, and so on; only the first term is ambiguous, since it could also refer to the continuous version of the problem.

Binary quadratic programming generalizes MAX-CUT, and so is NP-hard. In general it is (almost) NP-hard to approximate to within any constant factor, see for example On Non-Approximability for Quadratic Programs by Arora et al. For an up-to-date survey taking a more practical perspective, see The Unconstrained Binary Quadratic Programming Problem: A Survey by Kochenberger et al.


How does a two-way pushdown automaton work? Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape.

I recently had the question of determining the computational power of two-way PDAs in the Chomsky hierarchy. I don't entirely understand two-way PDAs, but I can see how with the ability to read in both directions on the input, it could handle languages of the form $L=\{0^n 1^n 2^n\}$. I can't say that for sure, but it seems that would make it powerful enough to least handle context-sensitive languages.

This is all a guess because I don't know exactly how they work. Can someone explain the process of how a two-way PDA operates, maybe even on my example?

UPDATE:

  The model is a generalization of a pushdown automaton in that two-way motion is allowed on the input tape which is assumed to have endmarkers.

A two-way PDA can accept the canonical context-sensitive language $\{0^{n}1^{n}2^{n} | n \geq 1\}$. Such an automaton could work by checking whether the largest prefix of the form $0^{i}1^{j}$ had $i = j$, using the stack, after which it could empty the stack, and check whether the largest suffix of the form $1^{j}2^{k}$ had $j=k$, again using the stack. So $CFL \subsetneq L(2PDA)$.

In more detail, the 2-way PDA would read from left to right as many 0 symbols as it finds, pushing a 0 onto the stack for each 0 it reads on the input tape. If it reads any 0 symbols and finds a 2 symbol before finding a 1, it crashes. When it gets to a 1, it changes state, and begins reading all the 1 symbols, until it comes to a 2. If it reads a 0 symbol while doing this, it crashes. It pops a 0 symbol from the stack for each 1 it reads on the input tape. If, when it reaches the first 2, the stack is empty, the PDA moves the tape head to the end of the input tape. Otherwise, it crashes. If it encounters any 0s or 1s, it crashes. It then reads the input tape left to right, pushing a 2 for each 2 it reads on the input tape. When it gets to a 1, it switches states and begins reading 1s and popping 2s. If, when it gets to a 0, the stack is empty, the string is accepted.

The machine would crash if the input string weren't a string of 0s, followed by 1s, followed by 2s; and it would have crashed if the longest prefix of 0s and 1s weren't in the canonical CFL $\{0^{n}1^{n}\}$; and it would have crashed if the longest suffix of 1s and 2s weren't in the canonical CFL $\{1^{n}2^{n}\}$. In this case, the ability to rewind the tape allows you to accept languages which are the intersection of CFLs, by essentially stringing PDAs together, and rewinding the tape in between.

Therefore, the languages accepted by two-way PDAs are trivially closed under intersection, a property not shared by languages accepted by regular PDAs.


How can average queuing delay exceed 1 if the $La/R \leq 1$? Consider a router with a packet arrival rate of $a$ where each packet has $L$ bits, and a transmission rate (in bits/s) of $R$. My textbook describes the traffic intensity as $\frac{La}{R}$ and states that as $\frac{La}{R} \to 1$, the average queueing delay approaches $\infty$. I'm just struggling to understand why this is the case. Is it because this increases the chance that $La$ exceeds $R$ during periods of time, and that long queues can accumulate?

It depends on the r.v's of the arrival  the service process.

For example, suppose the arrival and service process are all deterministic  process. For example, a packet of one bit ($L=1$) arrives in every second ($a=1$), and the router transmits  a bit in every second ($R=1$). Of course that in such case the average queuing delay equals to 1.

However, if for example in a system where the packet arrivals are determined by a Poisson process with parameter of $\lambda=a$ seconds  and job service times have an exponential distribution (M/M/1) with average of $1/\mu=\frac{L}{R}$ seconds (which describes a system with packet length $L$ and average transmission rate of $R$), i.e., $\mu=\frac{R}{L}$ the service time equals to $\frac{1}{\mu-\lambda}- \frac{1}{\mu}$. As $\frac{La}{R}$ approaches $1$, then $\mu-\lambda$ approaches $\infty$ the service time approaches infinity.

Now for the strange behavior of  $\frac{La}{R}=1$ for M/M/1 queue: When $\frac{La}{R}=1$ that means that the probability a packet enters the router equals the probability that a packet exits the router. That means, the probability that the router contains $i$ packets equals  the probability that the router contains $j$ packets, for every $i$ and $j$. Thus, the number of packets in router approaches $\infty$,  as well as the queuing delay.


Reducing subset sum to even subset sum I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even positive integers. I'm trying to show this problem is NP-hard by reducing the problem subset sum to it but I'm not sure where to start.

Hint: suppose that we are able to solve your problem efficiently. Then what if we take an arbitrary subset sum problem and multiply all elements by $2$, as well as the target?


How to solve recursion with two separate converges rates What is the correct way to solve the following recursion:
$T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$
Or basically any recursion that has two parts which converge in a different rate.
I'm trying to get big $O$ approximation, as tight as possible, but I couldn't figure it out with any "traditional" approach.

If you take the initial conditions $T(0) = 0$ and $T(1) = 1$ then you get A018819 (up to shift), which is essentially A000123. The asymptotics are known to be $T(n) = n^{\Theta(\log n)}$. The references under the second entry contain more accurate asymptotic information.
More explicitly, A018819 satisfies the recurrence $a(2m+1) = a(2m) = a(2m-1) + a(m)$, with $a(0) = a(1) = 1$. You can show inductively that $a(n) = T(n+1)$. Indeed:

If $n = 2m+1$ then $$T(n+1) = T(2m+2) = T(m+1) + T(2m) = a(m) + a(2m-1) = a(2m) = a(2m+1) = a(n).$$
If $n = 2m$ then $$T(n+1) = T(2m+1) = T(m+1) + T(2m-1) = a(m) + a(2m-2) = a(m) + a(2m-1) = a(2m) = a(n).$$


Huffman Coding and Depth Calculation? I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without drawing tree.

Specific Example is : 10-Input Symbol with Frequency 1 to 10 is 5. the above question mentioned depth is 5.

I read about max depth of Huffman and Entropy, but not well description for me.

Edit:

We know in my specific example the frequency is: $1$ to $10$ which means probability is: $(1/55)+(2/55)+(3/55)+(4/55)+(5/55)+(6/55)+(7/55)+(8/55)+(9/55)+(10/55) = 1 $

In each step of the Huffman coding algorithm the list of probabilities is being sorted and the 2 lowest of them are merged into a new node of the tree, resulting into a new probability. As for your  example probabilities the below illustration shows:

step 1:  [1/55,2/55,3/55,4/55,5/55,6/55,7/55,8/55,9/55,10/55]
step 2:  [3/55,3/55,4/55,5/55,6/55,7/55,8/55,9/55,10/55]
step 3:  [4/55,5/55,6/55,6/55,,7/55,8/55,9/55,10/55]
step 4:  [6/55,6/55,7/55,8/55,9/55,9/55,10/55]
step 5:  [7/55,8/55,9/55,9/55,10/55,12/55]
step 6:  [9/55,9/55,10/55,12/55,15/55]
step 7:  [10/55,12/55,15/55,18/55]
step 8:  [15/55,18/55,22/55]
step 9:  [22/55,33/55]
step 10: [1]

So in each step the set of the corresponding probabilities is reduced by 1. This corresponds to the size of the tree being increased by one.
Without drawing the tree we can quickly deduce that the length (or height depending on how you visualize it) will be 10.This is because the algorithm terminates when we reach the root of the tree that corresponds to probability of 1. As you can see there is absolutely no difference with the case of probabilities being all equal or any other specific distribution of probabilities among the symbols.

Note that there is not direct link to the average length of the resulting code and the length/height of the Huffman tree. The former depends very much on the probability distribution of the alphabet symbols. The best metric that we can use to address this issue is the entropy of the source that uses the alphabet under consideration. Entropy is a measure of the average uncertainty that we have about which symbol will appear next (at source's output) and is defined as this
$$H(\Phi) =\sum_{i=1}^{N} p(s_i)\cdot log_2(1/p(s_i))$$
Entropy indicates the minimum average codelength that we can achieve in coding the source $\Phi$. In general, when the symbols have all equal probabilities of appearance the entropy is maximized and $H(\Phi)=log_2N$. The intuition behind this is that when all symbols are equiprobable then our uncertainty about the source's output is maximized.


Is there a name/interest for regular languages that have a non-ambiguous ending? The basic idea is to have one or more symbol that clearly indicate the end. For example:

Non-ambiguous:

  $ab^*c$
  $(a|b)c$
   $ab^+c$
   $ab?c$
   $a(b|c)$
   $c(ab)^*ccc$
   $acc^*d$
   $abc|bcd$

Ambiguous:

  $abc^*$
  $abc^+$
  $abc?$
  $acc^*$ or $ac^*c$

An alternative definition of a non-ambiguous ending would be that the corresponding DFA can have multiple final states, but none of them can have a outgoing transition.

According to your alternative definition, you're looking for a  language such that $u\in L\Rightarrow \forall v\neq\epsilon, uv\notin L$ (where $\epsilon$ denotes the empty string).

That property defines a useful kind of language in coding, called prefix-free codes. Note that this language class doesn't include nor is included in regular languages.

So what you're looking for is the intersection of those two classes. That would be a prefix-free regular language.

As for the interest, it seems to have some, since a google search returned this research paper.


Optimal algorithm for finding all ngrams from a pre-defined set in a text I'm thinking about the optimal algorithm for the following problem:

Input data:

a text, say it's an article about 5-50 pages.
a set of ngrams (ngram strings, n>2), of arbitrary length, could be more than 20k n-grams.

The algorithm should output the following:

a dictionary of all ngrams that were found in the text with the corresponding quantities, it should also take into account that ngrams could partially intersect or consist of each other (like 'probability density', 'probability density function', 'probability density distribution')

So the question is what would be the most time-efficient algorithm to compute this?

Both all words in a text and all words in ngrams are reduced to the canonical forms.

What you want to solve is a string matching problem. Wikipedia (and any textbook on the matter) contains a rich list of algorithms with their respective runtimes.

Be aware that they give worst-case runtimes. Different algorithms behave differently on natural text; some perform better because of the large alphabet and some worst because of its repetitive nature. Therefore, you should benchmark the respective algorithms with data similar to which you expect to get.


What is the time complexity in solving a polynomial equation of degree N in one variable? How easy/difficult(in terms of big-O) is it to solve polynomial equations of high degrees of N?

Do apps like Desmos actually solve equations to get roots or do they approximate roots by iterating through a range of values for x?

What mechanisms are at play in solving a univariate polynomial equation algorithmically?

The time complexity doesn't just depend on N. It's possible that due to the coefficients, you have to evaluate the polynomial with very high precision to determine whether some minimum of the polynomial near a point x has a value >0, =0 or <0, and you need to know this to know the number of roots near to x (0, 1, or 2).


Ways to perform "batch" Approximate Member Queries efficiently In this problem, I'm first given n number of values which I have to store in a space efficient manner. Then I'm given m number of values which I have to check if they were added to the data structure before (such that after the operation, I know which value was a member, and which weren't).

I could use a Bloom Filter and simply iterate through m, but because m is considerably large, I wanted to see if there are more efficient ways. One potentially exploitable property of the data is that most values will not be present. I'm thinking I could construct an "aggregated query" which tells me if any of the value is present or not in one operation, and do something like a binary search, but wanted to see if there is already something out there.

Some additional details:

I can tolerate both false positives and false negatives (with predictable error rate)
n is very large (trillions)
m is considerably large (millions)
Only very few values in m will be members (ca. 1 in 100K)
The data structure can be immutable (no need for frequent writes)

If the query results are mostly false, the answer will be returned in $O(1)$ on average. (In traditional Bloom filters, negative results are faster than positive ones.)

This might be slow, however, since the lookups are random and have bad cache behavior. There are a few ways to fix this.

I'd suggest:

Use a blocked bloom filter (from Cache-, Hash- and Space-Efficient Bloom Filters) in which each item is mapped to a single cache-line-sized Bloom filter.
With the hash function that is used to map each item to a cache-line-sized Bloom filter, sort your queries in hash-value order.
Do the queries as usual, but in order.

Another approach is:

Use a split bloom filter, in which instead of setting $k$ values from a single array on each insert, set one value from each of $k$ arrays on insert.
After doing the inserts, use your first hash function to sort the values you wish to query in hash value order.
Query the first of your $k$ arrays for these values. Only a constant fraction will remain - $O(m)$ will be eliminated.
Take the remainder and repeat the last two steps, but using the second hash function, and the second bit array. Repeat $k$ times.

Sorting is expensive in internal memory, but it might be cheaper than all the random accesses. It depends on your machine and your data sizes.


Categorization of Binary search as Divide and Conquer Why do we call binary search as 'Divide' and 'Conquer' strategy? It does not combine the results unlike other Divide and Conquer strategies.

This might seem silly but here we go.

Let our array be $A$ and the current range we are searching in be denoted as $[L,R]$ and let $mid = \frac{L+R}{2}$.

The divide step - We divide our search space into two ranges - $[L,mid-1]$ and $[mid,R]$.
The conquer step - Let's assume that WLOG the element $x$ that we are searching for is such that $x < A[mid]$. Then we combine the knowledge that $x$ can be in $[L,mid)$ and $x$ cannot be in $[mid,R]$ to reduce our search space to $[L',R'] = [L,mid-1]$


Algorithm that finds the number of simple paths from $s$ to $t$ in $G$ Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$.
I have an algorithm in which I will run a DFS(Depth First Search) but if DFS finds $t$ then it will not change the color(from white to grey) of any of the nodes which comes in the path $s \rightsquigarrow t$ so that if this is the subpath of any other path then also DFS goes through this subpath again.For example consider the adjacency list where we need to find the number of paths from $p$ to $v$.
$$\begin{array}{|c|c c c|}
\hline
p &o &s &z \\ \hline
o &r &s &v\\ \hline
s &r \\ \hline
r &y \\ \hline
y &v \\ \hline
v &w \\ \hline
z & \\ \hline
w &z \\ \hline
\end{array}$$
Here DFS will start with $p$ and then lets say it goes to $p \rightsquigarrow z$ since it doesnot encounter $v$ DFS will run normally.Now second path is $psryv$ since it encounter $v$ we will not change the color of vertices $s,r,y,v$ to grey.Then the path $pov$ since color of $v$ is still white.Then the path $posryv$ since color of $s$ is white and similarly of path $poryv$.Also a counter is maintained which get incremented when $v$ is encountered.

Is my algorithm correct? if not, what modifications are needed to make it correct or any other approaches will be greatly appreciated.

Note:Here I have considered the DFS algorithm which is given in the book "Introduction to algorithms by Cormen" in which it colors the nodes according to its status.So if the node is unvisited , unexplored and explored then the color will be white,grey and black respectively.All other things are standard.

Your current implementation will compute the correct number of paths in a DAG. However, by not marking paths it will take exponential time. For example, in the illustration below, each stage of the DAG increases the total number of paths by a multiple of 3. This exponential growth can be handled with dynamic programming.

Computing the number of $s$-$t$ paths in a DAG is given by the recurrence,
$$\text{Paths}(u) = \begin{cases}
    1 & \text{if } u = t \\
    \sum_{(u,v) \in E} \text{Paths}(v) & \text{otherwise.}\\
\end{cases}$$

A simple modification of DFS will compute this given as

def dfs(u, t):
    if u == t:
        return 1
    else:
        if not u.npaths:
            # assume sum returns 0 if u has no children
            u.npaths = sum(dfs(c, t) for c in u.children)
        return u.npaths

It is not difficult to see that each edge is looked at only once, hence a runtime of $O(V + E)$.


What is the difference between A-normalization and K-normalization in compilers? Administrative normal form is a program intermediate representation in which each immediate instruction has a name. It is used in GHC and OCaml.

K-normalized form is an intermediate representation in which each instruction consists of one assignment and operation. It's used in MLKit, Min-Caml, and GoCaml.

Both A-normalization and K-normalization involve generating a let expression with a continuation.

A-normalization and K-normalization seem to be exactly the same transformation. What is the difference between them such that they deserve different names?

As far as my search-foo led me; K-Normal Form is inspired by A-Normal Form, but instrumented for use in Storage Mode Analysis, which is a static program analysis used for inferring memory mangement directives for functional programs.

The term seems to originate from the following publication:
L. Birkedal, M. Tofte, and M. Vejlstrup. From region inference to von Neumann machines via region representation inference.

A copy of the publication can at the time of writing be obtained from L.Birkedal's faculty webpage under publications.


Time complexity for count-change procedure in SICP In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem statement suggests drawing the tree for (cc 11 5) - which looks like this):

 ; count change
 (define (count-change amount)
   (define (cc amount kinds-of-coins)
     (cond ((= amount 0) 1)
           ((or (< amount 0) (= kinds-of-coins 0)) 0)
           (else (+ (cc (- amount
                           (first-denomination kinds-of-coins))
                        kinds-of-coins)
                    (cc amount
                        (- kinds-of-coins 1))))))
   (define (first-denomination kinds-of-coins)
     (cond ((= kinds-of-coins 1) 1)
           ((= kinds-of-coins 2) 5)
           ((= kinds-of-coins 3) 10)
           ((= kinds-of-coins 4) 25)
           ((= kinds-of-coins 5) 50)))
   (cc amount 5))

Now... there are sites with solutions to the SICP problems, but I couldn't find any easy to understand proof for the time complexity of the algorithm - there is a mention somewhere that it's polynomial O(n^5)

Order of growth of number of steps: $\theta (n^5)$

We can prove that, in general, the order of growth of number of steps is $\theta (n^m)$, where $m$ is the number of types of coin available. Here is my (very) crude reasoning using induction:

When there is only one type of coin, the number of steps is obviously proportional to n.
Suppose it would take (cc n m) steps to change an amount of $n$ with $m$ types of coin. Now let's consider (cc n m+1): ($A$ is the denomination of the $m$th kind of coin.)

  (cc $n$ $m+1$)
  = (cc $n$ $m$) + (cc $n-A$ $m+1$)
  = (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m+1$)
  = (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m$) + (cc $n-3A$ $m+1$)
  = ......

It would eventually computes to

(cc n m) + (cc n-A m) + ... + (cc <something-negative> m+1)

There are approximately $n/A$ items. So the total number of steps would be proportional to $n/A*n^m$, which is proportional to $n^{m+1}$. Thus, the order of growth for number of steps of (cc n m) is $\theta (n^m)$.

Let $m$ be 5, and the order of growth of number of steps is $\theta (n^5)$.


How does it possible that $ZPP=RP\cap coRP$? How does it possible that $ZPP=RP\cap coRP$ ?
After all, it must be that $RP\cap coRP = \emptyset$
Where Am I wrong ?

The complexity class P is obviously contained in their intersection (since the probability to err on either side is zero), so the intersection isn't empty.

(The complement of a complexity class isn't the same as the complement of a specific language.)


Structural induction over list I want to prove that unique(reverse(L)) = reverse(unique(L)) where L is a List.

List has the following constructors:
[] : -> List
[e] : Element -> List
cons(e, L) : Element x List -> List

I defined unique and reverse as follows:
unique : List -> List
reverse : List -> List

unique([]) = []
unique([e]) = [e]
unique(cons(e, L)) = cons(e, unique(L)), if member(e, L) = false
unique(cons(e, L)) = unique(L), if member(e, L) = true

reverse([]) = []
reverse([e]) = [e]
reverse(cons(e, L)) = append(reverse(L), [e])

also,
member : Element x List -> {true, false}
member(e, []) = false
member(e, [a]) = (e == a) (true, if a is equal to e; false, if a isn't equal to e)
member(e, cons(a, L)) = (e == a) V member(e, L) (V is logical disjunction)

append : List x List -> List
append([], L) = L
append([e], L) = cons(e, L)
append(cons(e, L1), L2) = cons(e, append(L1, L2))

Both base cases are easy to verify.

Induction hypothesis: I assume unique(reverse(L)) = reverse(unique(L)) is true

Inductive step: I have to prove that unique(reverse(cons(e, L))) = reverse(unique(cons(e, L))) is true

I consider two cases:

member(e, L) = true, then:

unique(reverse(cons(e, L))) = unique(append(reverse(L), [e]))

reverse(unique(cons(e, L))) = reverse(unique(L)) = unique(reverse(L))

Those are obviously true, but I don't know how to formally prove it (I can explain it in words, but that's not the point).
member(e, L) = false, then:

unique(reverse(cons(e, L))) = unique(append(reverse(L, [e])))

reverse(unique(cons(e, L))) = reverse(cons(e, unique(L))) = append(reverse(unique(L)), [e]) = append(unique(reverse(L)), [e])

I'm stucked here.

unique, reverse, append and member don't have to be defined that way, but they have to do the same thing.

I am not entirely sure that what you're trying to prove is right.

unique [] = []
unique (x : xs) = if x `in` xs then unique xs else x : unique xs

reverse [] = []
reverse (x : xs) = reverse xs ++ [x]

If we take xs = [a, b, a, c] then:

unique [a, b, a, c]
= { unique.2 }
if a `in` [b, a, c] then unique [b, a, c] else a : unique [b, a, c]
= { ... }
[b, a, c]

reverse [b, a, c] = [c, a, b]

reverse [a, b, a, c] = [c, a, b, a]

unique [c, a, b, a]
= { unique.2 }
c : unique [a, b, a]
= { unique . 2 }
c : [b, a]
= [c, b, a]

Hence, unique (reverse [a, b, a, c]) = [c, b, a] and reverse (unique [a, b, a, c]) = [c, a, b].


Intelligent use of XOR operator to find missing number I've come across the following problem on leetcode & tried to solve it with the following code however there seems to be an even better solution that takes advantage of XOR. Leetcode has a description for XOR solution however I can't grasp it in its entirety.
I just can't wrap my head around why we need to initialize missing variable with length of array, why not initialize it with Zero & when we do initialize it with Zero, why can't this algo find the missing number? Can someone please explain it?

Following was my solution before I learned Leetcode suggested XOR solution is even better & faster
class Solution {
    public int missingNumber(int[] nums) {
        if(nums.length == 1)
            return nums[0] == 0 ? 1 : 0;

        int missing = 0;
        boolean tempNums[] = new boolean[nums.length+1]; //cuz one is missing

        for(int i:nums) {
            tempNums[i] = true;
        }

        for(int i=0; i<tempNums.length; i++)
            if(!tempNums[i]) {
                missing = i;
                break;
            }
        return missing;
    }
}

Start with a list of any n integers. Duplicate the integers and calculate the XOR if these 2n integers. What’s the result? Rearrange the 2n integers in any way and calculate their XOR. What’s the result. Remove a number x from the list and calculate the XOR. What’s the result? Remove another number y and calculate the XOR. What’s the result?
Now go back to your problem, and the answers you gave before tell you immediately what your result will be.


Dynamic changes to classes or context activation -- how to treat existing objects in a consistent way? I am looking for references and papers on the following topic.

In general, some programming languages allow dynamic changes to classes. As an example, a new instance variable ‘weight’ can be added to the class Edge (the class of unweighted edges of graphs). But what should happen with existing edge objects?
They can be upgraded to include the new instance variable with a default value, perhaps weight 0, in the edge example. Or existing objects stay the same.

In context-oriented programming, similar situations can arise, when a context is dynamically activated at run-time. This may affect changes to methods which are currently executed (although I am concerned at the single thread execution at the moment).

Considering design patterns, when a proxy object wraps another object, references to the old object may expect certain invariants that the proxy object doesn’t adhere to. This may also lead to inconsistencies when an object is wrapped/’updated’ with a proxy object.

Are there any references that list possible ways to treat the problem in case of dynamic changes/activation? Like the options to keep the state consistent?
I looked primarily in the communities of dynamic software evolution, context-oriented programming and software components. Are there other important communities I can search to find references?

A recent paper on this topic that I stumbled upon is
Incremental Dynamic Updates
with First-class Contexts by
Erwann Wernli, Mircea Lungu, and Oscar Nierstrasz. The approach taken in the paper is not based on global updates. Rather, multiple versions of a system run simultaneously in what is called a context. Objects are gradually migrated from one context to another, at which time an update is performed. Bidirectional transformations are used to maintain consistency between old an new contexts.

In general, I think you need to have a pair of update functions for any update, one for updating classes, the other for updating objects. The real issue is when/how do you apply the update functions to objects. In any case, you will often have multiple versions of classes around at the same time. UpgradeJ (by Biermann, Parkinson and Noble) is one programming language that deals with multiple versions of a class in a type safe fashion.

The bibliography of these papers provides a few leads that you could follow. Also look on google scholar to see what paper build on these.