Does a greedy strategy exist for this instance of the Bin Packing Problem? I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 dimensions. Can a solution be found where each item is assigned to a container so that it fits inside? I can have containers left over; however, all of the items must be assigned. Assuming a solution exist, is there a greedy choice I can make for assigning an item to a container?

No, a greedy approach would not guarantee a solution for this problem (regardless of whether this solution is optimal or not). To see why, proceed by reduction. Suppose that you could actually find a solution for your problem in polynomial time using a greedy approach. Then, you could use your algorithm to solve in polynomial time the decision version of the Bin packing problem, which is known to be NP-complete (and, therefore, unlikely to be solvable in polynomial time).

How does this reduction work?

The decision version of the Bin packing problem involves deciding whether a certain number of bins (for example, 9) is optimal. If your hypothetical polynomial-time greedy algorithm finded a solution for 9 bins and failed to find a solution for 8 bins, then the answer for the decision problem would definitely be yes, and no otherwise.

Greedy is actually good.

All that being said, to obtain an approximate solution, a greedy approach is, probably, the best heuristic: sort the items in decreasing order of size and insert them one by one into the first bin that has room for it. This heuristic is called first-fit decreasing. The main appeal of this heuristic is that we pack the big items first and hope that the little ones fill up the spaces.


how to find a node that is known to everyone but doesn't know anyone? Problem I am trying to solve is this:

There are n nodes, and for every pair of node $X$ and $Y$,
the relation "$X \space  knows \space Y$" is either $T$ or $F$. It is possible that "$X \space knows \space Y$" but "$Y \space doesn't \space know \space X$".

We are trying to find if a special node exists: that is known to everyone but doesn't know anyone.
How can you find out if such node exists by using only this type of query:
For any nodes $X$ and $Y$, ask $X$ "$if \space X \space knows \space Y$". This query can be asked unlimited amount of times,
but the total number of queries should be $O(n)$.
I can think of $O(n^2)$ case but how to do it with $O(n)$ queries?
Thanks!

This can be done with the help of an auxiliary stack and elimination technique.
Let us call the node we are looking for the special node. We can make certain conclusions by examining the relation of any two nodes as following :

If node A knows node B, then A is surely not the special node and B may be the special node.
If node A doesn't know node B, then B is surely not special node and A may be the special node.
We repeat above two steps till we are left with only one node.
Examine the last node if it doesn't know anyone and is known to everyone.

Algorithm: (uses auxiliary stack)

Push all the nodes on the stack.
Pop off top two nodes from the stack, discard one node based on the observations made.
Push the remained node onto stack.
Repeat step 2 and 3 until only one node remains in the stack.
Check the remained node is the one we are looking for.

Why do we need the last step?

Because we have examined all the nodes relative to only one node which is adjacent to it on the stack but we don't know its relation with other nodes. So we need to ensure that the potential candidate for the special node is actually the special node.

This will require $3(n-1)$ comparisons in total. So the complexity is $O(n)$.


Linear programming with inequality constraints treated lexicographically I'm trying to solve optimization problems of the form: $\min\{cx|Ax\preceq b,\;x\geq 0\}$, where $\preceq$ means lexicographic order; that is, the set of linear inequalities need only to be satisfied lexicographically. I'm guessing these inequalities are treated conditionally by means of binary variables thus transforming the problem into a mixed integer linear program. I'm also aware of the more direct approach, which is solving a sequence of linear programs, starting with $\min\{cx|A_{1}x\leq b_{1},\;x\geq 0\}$ and continuing with linear programs of the form $\min\{cx|A_{i}x=b_{i},\;A_{k}x\leq b_{k},\;1\leq i<k,\;x\geq 0\}$ whenever the inequality constraint at $k-1$ is satisfied in strict equality.

I'm interested in a solution by means of binary variables if there is any, or any other approach. Thanks in advance for your help.

If you want to have only initial constraints to be strictly equal and rest of them should be strictly less

First, add regular constraints:
$$
A_i x \le b_i
$$
Next, add checks for equality as in https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ :
$$
e_i = A_i x \stackrel{?}{=} b_i
$$
Finally, we want only some initial of these variable to be true, and for that we can use material implication as in https://blog.adamfurmanek.pl/2015/08/22/ilp-part-1/ :
$$
e_{i+1} \implies e_i = 1
$$
or we can simply add the following constraints:
$$
e_{i+1} \le e_i
$$

Disclaimer: I am the author of the blog posts but I don't want to advertise here, only include them as a reference.

If you want some initial of the constraints to be strictly equal, the next one should be strictly less, and rest of them can be not satisfied

Do not add any regular constraints.

Create equality constraints as before:
$$
e_i = A_i x \stackrel{?}{=} b_i
$$

Calculate prefix conjunction of equality constraints:
$$
E_i = e_1 \wedge e_2 \wedge \ldots \wedge e_{i}
$$

Variables $E_i$ indicates whether first $i$ constraints are strictly equal.

Next, calculate less than constraints:
$$
l_i = A_i x \stackrel{?}{<} b_i
$$

Finally, make sure that after $i$ initial strictly equal constraints there is a strictly less constraint or another strictly equal constraint satisfied:
$$
E_i \implies \left( l_{i+1} \vee E_{i+1} \right) = 1
$$


Sequential subsequence removal with arbitrary predicate I want to extract sub-sequences from a sequence of float values.
The "scale" and range of these values is arbitrary (as I can manipulate it at will) but the "shape" is consistent.

For a visual example:

I want to extract the above five stacks as five "chunks". I want them in the order they occur (left-to-right). Do not be too distracted with the visual, though, as there can be an arbitrary number of points within the interval, but guaranteed $N_{points} < 2000$.

I have tried framing this problem as a dynamic partitioning problem, as an iterative subsequence extract problem, and something like $argmax$ but applied multiple times on a shrinking sequence.

Please pardon the ambiguity; I am struggling to even articulate the problem in a useful fashion. Critique and guidance would be much appreciated

Set threshold to, say 30 (arbitrary value greater than noise in the plot) and start from left to right, if value is greater than threshold, keep it as run - collect data to temporary array, if values drop below threshold then discard data and create new array for another run.

This will cut 5 bars and discard data between, if you want to keep data, you have to decide the shape (divide evenly between bars, keep it to left or to right).
It may happen that data drops below threshold in the bar (not visible in plot), then keep counter of dropped values, if it is small, add them to last run.


Big O - Equivalence: "Standard" definition vs Limit definition This question is related to: Landau Notation, Definitions: Limits vs. Cormen's.

Consider functions $f, \ g : N \rightarrow R^{\geq0}$.

For small-$o$, the definition:
$$f(n)\in o(g(n)) \iff \forall c>0,\exists n_0>0, \forall n\geq n_0: f(n) < c \ g(n)$$

Can also be expressed as a limit (i guess this assumes the limit exists):
$$f(n)\in o(g(n)) \iff \lim_{n\to\infty}\frac{f(n)}{g(n)}=0 $$

This can be verified introducing the definition for $\lim_{n\to\infty}$ on $N$, and then both definitions are identical.

Now, the "standard" definition for big-O would be something like (near exactly to Cormen's, except the codomain here is $R^{\geq0}$):
$$f(n)\in O(g(n)) \iff \exists c>0,\exists n_0>0, \forall n\geq n_0: f(n) \leq c \ g(n)  \qquad  (1)$$

Im trying to see if the following is true (again, this assumes the limit exists):
$$f(n)\in O(g(n)) \stackrel{?}{\iff} \exists c>0: \lim_{n\to\infty}\frac{f(n)}{g(n)}=c$$

Im not sure both directions of the equivalence are true. More specifically, i am having trouble with the $\Rightarrow$. According to this general answer, both directions should be true for $\Theta(g(n))$, wich is stronger than $O(\_)$. On the contrary, this answer (for roughly the same question, but in math SE) says big-$O$ cant be defined in that way (it was downvoted).

So, the questions are:

How exactly def (1) implies the $\lim$ definition?:

$$\forall \epsilon>0,\exists n_0>0, \forall n\geq n_0: \left| \frac{f(n)}{g(n)}-c\right| < \epsilon$$

Is the above still true considering generic functions $f, \ g : X \rightarrow R^{\geq0}$, where $X$ is some reasonable domain, maybe $Z$, $N^k$ or even $R^k$ (although reals are not turing-computable, im thinking in algorithms in the more general sense possible).

If $f = O(g)$ then there exists $C>0$ such that for large enough $n$, we have $f(n)/g(n) \leq C$. Hence under mild assumptions,
$$
f = O(g) \Longleftrightarrow \limsup_{n\to\infty} \frac{f(n)}{g(n)} < \infty.
$$
As Raphael mentions in a comment to your post, your definition is symmetric in $f,g$ and so is more appropriate for $\Theta$.


NAE SAT reduction to weighted MAX CUT I am trying to reduce NOT-ALL-EQUAL SAT to MAX-CUT with weighted edges.

I know that if there are weights to the edges, then I can reduce NOT-ALL-EQUAL SAT to MAX CUT by have a $G$ with $2n$ nodes ($x_i$ and $\bar{x}_i$) and edges between the nodes based on each clause. And, adding edges between $x_i$ and $\bar{x}_i$, so on.
But, I am not sure how to assign weights if I have to reduce a NOT-ALL-EQUAL SAT to weighted MAX CUT.

How should I go about this problem?

NAE-SAT is clearly in NP, while MAX-CUT is NP-complete. So by the definition of NP-complete, there is some reduction from NAE-SAT to MAX-CUT.


Stabilization of lower approximation Let $f:\mathbb{N} \to \mathbb{R}$ be a lower semicomputable function, i.e. there exists a recursive function $g:\mathbb{N}\times \mathbb{N} \to \mathbb{Q}$ s.t.

$$\forall x \in \mathbb{N} \quad \lim_{k \to \infty} g(k,x) = f(x) \qquad\qquad (1)$$
$$\forall x \in \mathbb{N} \quad g(k,x) \le g(k+1,x)\qquad\qquad (2)$$

Question: can we assume that if $f(x)$ is rational then eventually $g(k,x)$ stabilizes on the true value? Formally, can we prove that there exists a recursive function $g':\mathbb{N}\times\mathbb{N}\to\mathbb{Q}$, possibly different from $g$, s.t. $(1)$ and $(2)$ holds for $g'$ and additionally

$$ \forall x \in \mathbb{N} \quad \left( f(x) \in \mathbb{Q} \Rightarrow \exists k_0 \in \mathbb{N}\, \forall k>k_0 ~~g'(k,x) = f(x) \right)$$

I tried many different strategies but they all seem to a dead end.

Notice that $g'$ need not to be build from $g$ (there may be no relations among the two) and we need not to be able to know when $g'$ stabilizes. Think for example to the function $f$ that prints 1 if the $n$-th TM halts otherwise 0 (i.e. the characteristic function of the halting set). If you pick $g'$ as $g'(k,n)=$"$1$ if the TM $n$ halts in $k$ steps and $0$ otherwise" you clearly get that $g'$ eventually stabilizes on all $n \in \mathbb{N}$ even though we will never be able to say when.

Currently I don't even know whether this should be true or false. Maybe I'd bet on true, but it's just a feeling and that can be totally wrong of course.

Define $h(k,x)$ as the maximal $\ell \leq k$ such that program $x$ halts on inputs $1,\ldots,\ell$ after at most $k$ steps. Clearly $h(k,x)$ is computable. Define $g(k,x) = -1/h(k,x)$. Clearly $g(k,x)$ is computable and monotone.

If $x$ computes a total function then $\lim_{k\to\infty} g(k,x) = 0$. Otherwise, if $s$ is the first input on which $x$ doesn't halt then $\lim_{k\to\infty} g(x,k) = -1/(s-1) < 0$.

Suppose now that some computable function $g'(k,x)$ satisfies $\lim_{k\to\infty} g(k,x) = \lim_{k\to\infty} g'(k,x)$ for all $x$, and $g'(k,x)$ eventually stabilizes for all $x$. Thus $x$ is total iff $\exists k.g'(k,x) = 0$, putting TOT in $\Sigma_1$. However, TOT is known to be $\Pi_2$-complete, and in particular doesn't belong to $\Sigma_1$.


Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel Given integers $n,m$, I want to find a $m \times n$ binary matrix $X$ such that there does not exist any non-zero vector $y \in \{-1,0,1\}^n$ with $Xy=0$ (all operations performed over $\mathbb{Z}$).  What algorithm could I use for this?

In more detail: We are given parameters $n$ and $m$.  The problem is to determine if there exists $x$ such that $x_{i,j} \in \{0,1\}$, and there does not exist $y\ne (0,0,\dots,0)$ where $y_j \in \{-1,0,1\}$ for all $j$ and for all $1 \leq i \leq m$,

$$\sum_{1 \leq j \leq n} x_{i,j} y_j = 0.$$

(Notice that we require that at least one of the  $y_j \ne 0$ to avoid the trivial solution.)

For example, consider $m=3,n=4$.  Then, expressing $x_{i,j}$ as a matrix $X$,

$$
X=\begin{pmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 \\
\end{pmatrix}
$$

is a valid solution for $m=3$ and $n=4$.

What algorithm can I use to solve this problem?  Can I formulate this as an integer linear programming problem or maybe as a constraint programming problem?

I have a method for you that will help you find valid solutions (matrices) for many possible values of $m,n$.  However, it is not a complete answer to your question.  It can try to find a matrix for a particular value of $m,n$, but it might fail, and if it fails, you've learned nothing; my method cannot prove that no such matrix exists.
The method is based upon the following observation:
Theorem. If we have a valid $m_1\times n_1$ matrix $X_1$ that meets all your requirements (for parameters $m_1,n_1$) and a valid $m_2\times n_2$ matrix $X_2$ that meets all your requirements (for parameters $m_2,n_2$), then we can find a valid $m\times n$ matrix that meets all your requirements (for parameters $m,n$), where $m=m_1+m_2$ and $n=n_1+n_2$.
Proof.  Use the following matrix:
$$X = \begin{pmatrix} 0 &X_1 \\ X_2 &Z \end{pmatrix},$$
where $Z$ is arbitrary.  Suppose $Xy=0$, where $y \in \{-1,0,1\}^n$.  Then since the last $m_1$ coefficients of $Xy$ are zero, and since $X_1 y_1 =0$ implies $y_1=0$, it follows that the last $n_1$ coefficients of $y$ are zero.  Thus by letting $y_2$ be the restriction of $y$ to its first $m_2$ coefficients, we find that $X_2 y_2 = 0$.  But this implies $y_2 = 0$, i.e., $y=0$.  In other words, if $Xy=0$, then $y=0$.  This proves that $X$ is a valid matrix.

Now this lets us find many values of $m,n$ where it is possible to find a valid matrix $X$.  In particular, seed things with some small matrices for various small values of $m,n$ (using any convenient method); then you can derive some larger values of $m,n$ that also have such a matrix.
Here are some observations that will help you identify seed values $m,n$ where such a matrix $X$ exists:

First, a trivial observation: Obviously, if $n \le  m$, it is easy to find a valid solution $x$: just use the identity matrix (if $n<m$, fill in the extra rows arbitrarily).  No need to use integer linear programming.  So this problem is only interesting when $n>m$.

Second,  if $n$ is small enough, you can express this as a SAT instance and apply an off-the-shelf SAT solver.  The SAT instance will be of exponential size: it will have more than $3^n$ constraints, so this is only helpful for very small values of $n$, but it will still help you construct some values of $m,n$ where you can find a valid matrix $X$.

Third, you can use bcorso's answer to handle all cases where $n=m+1$ (there is always a valid solution, for $m\ge 3$).
In particular, you can construct a SAT instance where the $x_{i,j}$ are the variables.  Now, for each possible non-zero vector $y \in \{-1,0,1\}^n$, you can add a complicated constraint enforcing the requirement that $Xy \ne 0$.  (You'll need to have $m$ adders, each of which adds up to $n$ 0-or-1 values, and then a comparison to test whether the results of all of the $m$ adders are all zero or not.)

In this way, I would expect that, for each $n\le 8$ (or so), you can probably find the largest value of $m$ such that there exists a valid $m\times n$ matrix.  Now once you have those seed values, you can use the Theorem above to help you find additional values of $m,n$ where such a matrix exists.
As I stated above, this is not a complete solution, but it might help you solve your problem at least some of the time.

For general $m,n$, I doubt that there's any straightforward formulation of this as a polynomial-size integer linear program (unless $\text{NP} = \text{NP}^\text{co-NP}$ or the polynomial hierarchy collapses or something like that, which is not expected to hold; or unless you use some special knowledge about the solution to this problem).
Just telling whether a candidate value of $x$ is indeed a valid solution to this problem is $\text{co-NP}$-complete.  See https://cstheory.stackexchange.com/q/20277/5038.  In other, recognizing a solution to this problem can't be done in polynomial time (as far as we know); just recognizing a valid solution is $\text{co-NP}$-complete.  This means that the problem of finding a valid solution is in $\text{NP}^\text{co-NP}$.  In contrast, integer linear programming is in $\text{NP}$.  Therefore, without using some special knowledge about this problem, I don't think you can find a generic reduction from your problem to integer linear programming unless $\text{NP}^\text{co-NP} = \text{NP}$ (something that most complexity theorists believe is not likely to hold).
Don't take this too seriously.  I'm not trying to prove a formal theorem or anything like that; I'm just trying to give some weak evidence why this problem does not look like it has a straightforward, generic formulation as an instance of integer linear programming.
Of course, you can probably get a formulation as an integer linear program with a number of constraints that is exponential (say, in $m$), similar to how we got a SAT instance.  It'll be uglier, because expressing the constraint that some vector (namely, $Xy$) is not identically zero is ugly in ILP.  But it's doable.  See, e.g., Express boolean logic operations in zero-one integer linear programming (ILP).  However, I'm not sure this will be any better than the SAT-based method.  If I were implementing this, I would start by trying the SAT-based method, because (if you use a suitable front end, like STP) I think it will be easier to implement and might work just as well or better than an ILP-based formulation.


Is the complement of every non Turing recognizable language a Turing recognizable language? One thing I understand is that the complement of every Turing recognizable(but not decidable) language is non Turing recognizable.

What about the complement of non Turing recognizable language? Is the complement of every non r.e a recognizable language.

I don't know how to approach this problem.

But one idea I had was this:

If the complement of every non r.e were a r.e language then there would be a bijection from r.e to non r.e. This bijection maps a r.e to a non r.e . The set of r.e languages is countable(even though infinite). If a bijection exists then non r.e would also be countable. But the union of r.e and non r.e is uncountable. This means one of them must be uncountable. So the original supposition must be wrong.

I am new to coutability and such things. So it may be possible that the idea is compeletely wrong.

Anyhow can someone provide an approach to this problem.

Your proof is fine. There are also explicit languages which are neither r.e. nor co-r.e., for example the language of all total Turing machines (Turing machines halting on every input).

In fact, the language of all total Turing machines is $\Pi_2$-complete, which means, in a sense, that there is no better way to "solve" it than to run all on inputs and see whether the given machine halts on each of them (of course, you can't do this with a Turing machine, but perhaps with a more powerful device...). Take a look at the arithmetical hierarchy for more on this.


How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph? I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List Representation.
What I did is as follows:

• Do a simple BFS Traversal using a Queue while maintaining the parent node of nodes enqueued in the queue.
• If I come across a node u that has a neighbor v such that v is already visited but v is not the parent of u then that means there is cycle in the graph.

Pseudocode:
#adjList is the adjacency list given as a dictionary
#myQueue is a double-sided queue containing node and its parent node ([Node, parNode])
#visited is a set containing visited nodes

while(myQueue):
    currNode, parNode = myQueue.pop() #dequeue operation
    visited.add(currNode) #Marking currNode as visited
    for childNode in adjList[currNode]: #Traversing through all children of currNode
        if currNode not in visited:
            myQueue.appendleft([childNode, currNode]) #Enqueue operation
        else:
            if childNode!=parNode: #Main logic for cycle detection
                print('CYCLE DETECTED')
                break

The above approach is working except in cases when I have more than 1 edge between 2 vertices for e.g. in following case we have 2 edges between vertices 0 and 1:

Adjacency list of above graph is: adjList = {0:[1, 1, 2], 1:[0, 0], 2:[0]}. Here we can clearly see that the graph contains a cycle (In the adjacency list, it is represented by the fact that 1 appears twice in the adjacency list of 0 and 0 appears twice in the adjacency list of 1) but above algorithm is not able to detect the same because when BFS will reach vertex 1, vertex 0 is already visited but vertex 0 is also the parent of vertex 1 so this cycle will go undetected.
My question is how I can modify above algorithm to detect such cases?
Edit: I tried the same logic on directed graphs also, and I am facing similar problem i.e. case when I have a directed edge from vertex 0 to vertex 1 and another directed edge from vertex 1 to vertex 0

If the case arrives where you see the case of a node being already visited but it is the parent of your current node, you just have to check whether there is a double edge between them. How to do that depends on your data structure, but if your adjacency list is sorted it would just amount to searching for the edge and checking how often it is in there.

Another problem I see is that your adjacency list doesn't actually contain any information that the edge is doubled.

For directed graphs, you can just completely get rid of the "parent check", as the only time that case arrives is when you have two edges going from $u$ to $v$ and vice versa.

Additionally, be careful if the graph is not connected, your BFS will not cover all of it, so you would need to start another BFS from an unvisited vertex again. This is especially important for directed graphs, as even if the graph might be connected, your BFS will probably not cover all of it.


How can I compare two recurrence relation to find which one is better on large inputs I have two recurrences:

$T_1(n) = 2 T_1(n-1) + n$ if $n > 1$, $1$ if $n = 1$

$T_2(n) = 2 T_2(\frac{n}{2}) + n^2$ if $n > 1$, $2$ if $n = 1$

Does this mean $T_1$ is better than $T_2$ because it has less operations to do?

Edit: I looked at the master theorem and found out that the 2nd one has an $O(n^2)$ runtime.

The simplest way is to solve both recurrence relations, and see whether one of them grows faster. In your case there is actually no need to do that, since we can observe that on the one hand
$$
T_1(n) \geq 2T_1(n-1) \geq 2^2T_1(n-2) \geq \cdots \geq 2^{n-1}T(1) = 2^{n-1},
$$
and on the other hand
$$
T_2(n) = O(n^2),
$$
by the master theorem. This is enough to deduce that $T_2(n) = o(T_1(n))$, that is, $T_1(n)$ grows faster than $T_2(n)$.


If one shows that UNIQUE k-SAT is in P, does it imply P=NP? Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time.  Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the question is, if someone shows that UNIQUE k-SAT is in P,  does it imply P=NP?

References

L. G. Valiant and V. V. Vazirani, "NP is as easy as detecting unique solutions." Theoretical Computer Science 47:85–93, 1986. (PDF on ScienceDirect.)
C. Calabro, R. Impagliazzo, V. Kabanets and R. Paturi, "The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs".  Journal of Computer and System Sciences 74(3):386–393, 2008. (PDF at ACM Digital Library; free PDF.)

This is still an open question; UP is not known to be equivalent to NP.  In the paper "NP Might Not Be As Easy As Detecting Unique Solutions," Beigel, Burhman and Fortnow construct an oracle under which P contains UP but P is still not equivalent to NP.


Contrast Enhancement For An Image Using A Gaussian Function I am working on a program that involves detecting faces in photos, i am reading a paper that someone has wrote and they said that they had more success detecting faces once he they applied some enhancements to the image, one of these being a contrast enhancement. The exact words are...

  Contrast enhancement improves the overall quality of the image. Gaussian convolution using
  the Gaussian function G(x, y) is first applied with the input value channel image in the HSV
  space. The convolution process can be expressed as follows

They then give you Equation 3: $V_{con} = V_1(x,y) \oplus G(x,y)$ NOTE: $V_1$ is the original value

  $V_{CON}$ in Eq. 3 denotes the convolution result, which contains the luminance information from
  the surrounding pixels. The center pixel value is now compared with the Gaussian convolution
  result in order to find the amount of contrast enhancement of that center pixel. This process is
  described by the following equation

Equation 4: $V_{ce}(x,y) = 255V_{le}(x,y)^{E(x,y)}$ NOTE: $V_{le}$ is the result of another enhancement done previously.

  where $V_{CE}(x, y)$ is the result of contrast enhancement and $E(x, y)$ is given by the following relation

$E(x,y) = (V_{con}(x,y)/V_1(x,y))^g$

  Here g is the image dependent parameter determined by using the standard deviation of the
  input value channel image. If the center pixel is brighter then the surrounding pixels, the contrast
  of the pixel is pulled up. On the other hand, if the center pixel is darker then the neighboring
  pixel then the contrast of the pixel is lowered.

The problem is that with my understanding of maths (NCEA Level 3, Last year at collage) i don't understand how to do the first part, any help would be much appreciated

The full paper is here: http://jips-k.org/dlibrary/JIPS_v09_no1_paper9.pdf

Convolution is a relatively simple operation to perform, but to make it fast involves a little extra work (Wikipedia article on convolution theorem). In general, if you convolve a discretized function F by a different discretized function G, you are simply performing the following operation:

$$(F\otimes G)(x) = \displaystyle\sum_{i=0}^NF(x-i)*G(i)$$

Where N is the number of discrete values of G. Notice this is effectively just summing the product of F and G "centered" around $x$.

In 2D (which is what an image is), this looks like:

$$(F\otimes G)(x,y) = \displaystyle\sum_{i=0}^N\displaystyle\sum_{j=0}^MF(x-i,y-j)*G(i,j)$$

The paper you're reading tells you that F is the V channel of the image in HSV space, and G is a 2D gaussian function. Code-wise, the above form should translate very simply into a double-nested for loop.

The paper should also tell you what the mean/variance of the gaussian function is as well as the number of samples it contains, but sometimes that information is omitted.


Context Free Grammar: at least 2 1's, at most 2 0's Been having some trouble trying to come up with a CFG for this language: all binary strings that contain least 2 1's and at most 2 0's

So far, I've come up with this:

S --> T | 0T | T0 | T0T | 00TT | TT00 | 0T0T | T0T0 | 0TT0 | T00T

T--> 1T | V

V--> 11Z | 1Z1 | Z11

Z--> 1Z | epsilon

I realize this is mostly likely incorrect/redundant, so any feedback would be extremely helpful. Thank you!

Hint

If $L_{i j}$ is the language with at least $i$ $1$s and at most $j$ $0$s

$$\begin{align}
L_{2 2} &= 1 \, L_{1 2} \, | \,?\\
... \\
L_{0 0} &= \,?
\end{align}$$

Edited to answer the correct question.


Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard
Let $G$ be a cyclic group of size $m$, and let $g \in G$ be a generator.
We say the the discrete log problem is $(T,\epsilon)$-hard if for every algorithm $A$ of complexity at most $T$, it statisfies:
$$P[A(a) = log_g(a)] \le \epsilon$$
when $a$ is chosen uniformly from $G$.
This means that $A$ can give the correct value of $log_g(a)$ with probability $ \le \epsilon$.
Now I assume that the discrete log problem is $(T, 1-\epsilon)$-hard and want to prove that it's $$(O(\frac{T}{\frac{1}{\epsilon}log\epsilon} -nlog(m)), \epsilon)\text{-hard}$$ where $n$ is the time to compute a group operation on $G$.
The complexity of $O(nlogm)$ it is what needed to calculate $g^a$ for an arbitrary $a \in G$, which makes me think that such thing can be used here.
I would want to assume that there is an algorithm $A$ of size $K$ that guesses the correct discrete log for an arbitrary $a \in G$ with probability $ > \epsilon$.
Then, somehow use $A$ to solve the discrete log problem with probability $> 1-\epsilon$.
However, I don't really see how to do it. Maybe run $A$ with the input $a \in G$ and return the opposite answer in some way. Help would be appreciated.

Suppose that there exists an algorithm $A$ which runs in time $T_A\le \frac{T}{\frac{1}{\epsilon}\log\frac{1}{\epsilon}}-n\log m$, and $\Pr\limits_{a\sim U(G)}\left[A(a)=\log_g a\right]\ge \epsilon$. We want to enhance the success probability of $A$. The trick is to evaluate $A$ on different elements $b_1,...,b_k$ (who of course depend on the input $a$) whose logarithm will allow us to recover $\log_g a$. Define $A'$ as follows, given input $a$ pick independently $i_1,...,i_k\in [m]$ uniformly at random, and evaluate $A$ on the inputs $ag^{i_1},...,ag^{i_k}$. For each $1\le j\le k$ check whether $A(ag^{i_j})=\log_g ag^{i_j}$ (the verification requires $n\log m$ time), and if there exists $j$ for which the equality holds return $A(ag^{i_j})-i_j \pmod m$. The running time of $A'$ is bounded by $k(T_A+n\log m)\le \frac{k}{\frac{1}{\epsilon}\log\frac{1}{\epsilon}}T$. I leave it to you to show that $ag^{i_1},...,ag^{i_k}$ are independent and therefore we can write $\Pr\limits_{a\sim U(G)}\left[A'(a)=\log_g(a)\right]\ge 1-(1-\epsilon)^k\ge 1-e^{-\epsilon k}\ge 1-\epsilon$, for $k=\frac{1}{\epsilon}\log\frac{1}{\epsilon}$.


Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$ Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$   and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $.

I´ve made a program to check this statement and it seems that for any given $c>0,\forall n\geq16$  it holds, however i don´t know how to formally proof this ,because i can´t find any simplification for $t_b$.

I know that i must prove $ \exists c
 : \forall n \geq N:t_b(n) \leq c *t_a(n)$ using big-O-Notation.

A hint/solution-idea would be really great.

In order to compare two quantities/expression, it is often easier if they are in the same form. Here try expressing $t_a(n)$ as $2^{s_a(n)}$ and compare $s_a(n)$ with $\sqrt{\log_2 n}$.

Additionally, beware of using a program to check asymptotic comparisons: e.g. $f(n)=n^{10^6}$ and $g(n)=(1,0000000000000001)^n$


Counting substrings with a given number of different characters in O(N) Given a string $S$ of length $n$, and a number $k$, count the number of substrings (regardless of their length) that contain exactly $k$ different characters.

The obvious solution takes $O(n^2)$ time (fix substring start point, and move its end point while keeping track of the set of seen characters).

Is there a way to do that in $O(n)$ time? Or at least in $O(n c)$ time, where $c$ is the number  of unique characters in the string $S$?

I tried to keep track of two pointers (start and end) and move only one of them forward at each step, while updating the hash table with character counts. But counting substrings became really messy.

You can solve this in $O(n)$ time using two (well, three) pointers that both move leftward.

Let $S$ be the string.  We'll let $i$ range from $n$ down to $1$, and for each value of $i$, we're going to count the number of substrings that start at position $i$.

For each $i$, find the smallest $j_\text{min} \ge i$ such that $S[i..j_\text{min}]$ has exactly $k$ unique characters as well as the largest $j_\text{max} \ge i$ such that $S[i..j_\text{max}]$ has exactly $k$ unique characters.  You can do this efficiently, by keeping an array (or hashtable) with character counts for $S[i..j_\text{min}]$ and one with character counts for $S[i..j_\text{max}]$; you'll update these each time you decrement $i$, $j_\text{min}$, or $j_\text{max}$.  (In addition to the array/hashtable, also keep track of the number of of characters with non-zero count, and update this each time you update the array or hashtable.)  When you decrement $i$, you can update the array/hashtable with character counts for $S[i..j_\text{min}]$, then use that to see whether you need to decrease $j_\text{min}$ and by how much (updating the array/hashtable each time you decrement $j_\text{min}$).  Same for $j_\text{max}$.

Finally, sum up the counts you get for each value of $i$.

Note that $j_\text{min}$ starts out at $n$ and only ever decreases: when you decrement $i$, $j_\text{min}$ can only ever get smaller (but not bigger).  So, you'll only need to decrement $j_\text{min}$ (and update the array/hashtable) at most $n$ times: it starts out at $n$, and only ever decreases, and never gets smaller than $1$, so it can only be decreased at most $n$ times.  The same is true for $j_\text{max}$.  Consequently, we do at most $O(n)$ updates to the array/hashtable (summed up over all the steps of the algorithm), so the total running time of this algorithm is $O(n)$.

Credit: Thanks to @aaaaajack for a major improvement to my algorithm, and to @Raphael for further improvements.


About Codd's reduction algorithm Codd's Algorithm converts an expression in tuple relational calculus to Relational Algebra.

Is there a standard implementation of the algorithm?
Is this algorithm used anywhere? (It seems that the industry only needs SQL and variants, I'm not sure about database theorists in academia.)
What's the complexity of the reduction?

 This was posted on SO over a year ago, but it didn't receive a good answer.

This reduction is the constructive proof technique to show that a subset (named safe) Tuple Relational Calculus (TRC) is less expressive than Relational Algebra (RA). The other way being true too, Safe-TRC and RA have equivalent expressive power. See Theorem 5.3.10 for instance.
The syntactic "safety" restriction ensures the domain independent property of the calculus and is needed.

In R-DBMS, SQL can be seen as the concrete (declarative) language for TRC. The RA counterpart is the procedural plan (a sequence of operations) in which an SQL expression is compiled to. So, the conversion is actually the formal description of the compilation process. Note that SQL introduces extensions like DISTINCT, ORDER BY, GROUP BY which are clearly outside the scope of TRC and RA theory.

I don't know the precise theoretical complexity of the conversion, but clearly it has to be "cheap". Photon Kolaitis states that it is linear.

I'm not aware of a proof-of-concept implementation of this algorithm.


How to build a label flow graph for static analysis I'm new to world of static analysis and am trying to build a new analysis of C programs for llvm compiler.

I've started with the build of the graph of the constraints of the program:
The edges represent the flow of data through the program (according to the statements or function calls) and the nodes the run-time memory locations.

I'm wondering if for the labeling of the constraints I do need a symbol table with all the constraints and their labels.
I found out that we can build a CFG on top of the LLVM by only parsing the LLVM IR.

for example, we could just have:

//Build list nodes without successors.
for (Function::iterator e = F.end() ; e != BB ; ++BB) {
    BI = BB->begin();
    for(BasicBlock::iterator BE = BB->end(); BI != BE; ++BI){
        Instruction * instruction = dyn_cast<Instruction>(BI);
        StaticAnalysis::ListNode* node = new StaticAnalysis::ListNode(counter++);
        node->inst = instruction;
        helper.insert(pair<Instruction*,StaticAnalysis::ListNode*>(instruction,node));
        CFGNodes.push_back(node);
    }
}

So, my question is:
Would this be possible also for a flow graph? Or a symbol table is needed to construct one?

You want to build a graph where the vertices are the set of runtime locations in memory.  Unfortunately, this isn't possible.  The set of runtime locations can be an unbounded set.

For instance, consider code that creates a linked list to hold $n$ data items provided on the input; the number of memory locations is at least $n$, so if the data items are provided on the input, there is no upper bound on the number of memory locations.  Or, consider code like

while (...) {
    char *p = malloc(..);
    ... do something with p ...
    free(p);
}

Each call to malloc() creates a new memory location, so the number of runtime memory locations is at least the number of iterations of the loop.  There may be no fixed upper bound on the possible number of iterations of the loop.

Different static analysis techniques deal with this in different ways:

Data flow analysis typically deals with this by ignoring everything in the heap, and only trying to reason about local variables.  In this way, you obtain a finite graph.
Points-to analysis deals with this using abstraction.  It builds a points-to graph, where each node in the graph corresponds to a potentially unbounded number of runtime memory locations.  At each node in the graph, we record facts that are known to be true for all of the runtime memory locations that correspond to that node.  For instance, we might have one node per malloc() call site.  In other words, we might have a single node for all runtime memory locations that are allocated by any of the calls to malloc() on line 79 (the first call to malloc() on that line, the second call to malloc() on that line, etc.; they're all merged into a single node).

You might want to spend some time reading up on how data flow analysis and points-to analysis work.

More generally, I suggest you ask a new question where you tell us what you're trying to achieve.  Presumably the graph you were talking about was only a means to an end; what was the end goal?  Presumably you wanted to build it only because you thought it'd help you with some task; what is it you really want to learn about the program?  If you ask a new question telling us what your goal is (what you're trying to infer about the program), we might be able to suggest an appropriate static analysis technique that would be suitable for that goal.


Difficult reccurence with two variables My question is a follow-up for the following thread: Solving unusual recurrence with two variables
I baisically have the same reccurence relation but with a small change---
$$T(n,k) = T(n-1,k)+T(n-m,k+1)$$
The change is the addition of $m$ in the second element in the recursion (instead of 1 in the original question)
The boundary cases remain the same (for some given constant $C$):
For all $x \leq C$ and for any $k$: $T(x,k)=1$
For all $y \geq C$ and for any $n$: $T(n,y)=1$
I'm trying to approximate the value of $T(n,0)$ (with a tight upper bound as possible). In the original question we were able to give a close formula for the reccurence after $i$ steps, which helped bounding its value. But due to the addition of $m$, this formula doesn't hold anymore.
A direction for how to address such reccursions or any idea for the solution would be very helpful.

It will be less confusing to reparametrize $T$ by switching the order in which the second parameter increases:
$$
T(n,k) =
\begin{cases}
1 & \text{if } n \leq C \text{ or } k = 0, \\
T(n-1,k) + T(n-m,k-1) & \text{otherwise}.
\end{cases}
$$
Having done this switch, let us get rid of $C$ completely. Including $C$ as the third parameter, notice that $T(n+C,k,C) = T(n+D,k,D)$, and so it suffices to solve the recurrence for some value of $C$. We choose $C = 1$.
Let us now unroll the recurrence. Suppose that $n > m$ and $k > 0$. Then
\begin{align}
T(n,k) &= T(n-m,k-1) + T(n-1,k) \\ &=
T(n-m,k-1) + T(n-m-1,k-1) + T(n-2,k) \\ &=
T(n-m,k-1) + \cdots + T(2-m,k-1) + T(1,k) \\ &=
T(n-m,k-1) + \cdots + T(2-m,k-1) + 1 \\ &=
T(n-m,k-1) + \cdots + T(2,k-1) + m + 1.
\end{align}
This gives us $T(n,1) = n-m-1+m+1 = n$ if $n > m$; you can check that the same formula works for all $n \geq 1$. Continuing,
$$
T(n,2) = T(n-m,1) + \cdots + T(2,1) + m + 1.
$$
If $n > m$ then we can compute exactly
$$
T(n,2) = (n-m) + \cdots + (2) + m + 1 = \frac{(n-m)(n-m+1)}{2} + m.
$$
When $1 \leq n \leq m$, you can check that $T(n,2) = n$.
At this point we can in principle continue and obtain exact formulas. However, they will be quite messy. Fortunately, when $m$ is constant, it is easy to prove by induction that $T(n,k) = \Theta(n^k)$; indeed, $T(n,k) = n^k/k! + O(n^{k-1})$. Obtaining an explicit dependence on $m$ is certainly possible, but unless it's expressly needed, I wouldn't bother.


Simplifying a nested sum I'm trying to analyze an algorithm of a function, I can express the function in term of summation, but I have no clues on how I could simplify this summation down to get the run-time in tern of big $O$ or $\Theta$. I have this pseudo-code below:

f(n)
    for int i = 1 to n
        for int j = i to n
           doThis(n - j)
        end
    end
end

Assuming that doThis(k) takes $c \cdot k$ operations for some constant $c > 0$. I can express the nested for loop in summation as follow:

$\sum_{i=1}^n \sum_{j=i}^n c\cdot(n-j)$

How does one simplify this summation? It has been a while since I touch math so I'm trying to get an idea here. Any help would be appreciated, thank you!

Hint:
$$\sum_{i=1}^n \sum_{j=i}^n (n-j) = \sum_{i=1}^n \sum_{j=0}^{n-i} j. $$
At this point, you can either use exact formulas, or notice that for all $d \geq 0$,
$$\sum_{k=1}^m k^d = \Theta(k^{d+1}).$$
(If you don't know what a $\Theta(\cdot)$ bound is, suffice it to say that it is a "tight" $O(\cdot)$ bound.)

After you handle the inner sum, you will need to use the same trick of replacing $i$ with $n-i$ in order to handle the outer sum.


Is it possible to simulate a fair coin with a finite number of tossing of a biased one? It is a classic problem to simulate a fair coin with a biased one.
According to Fair Coin (wiki),

John von Neumann gave the following procedure:

Toss the coin twice.
If the results match, start over, forgetting both results.
If the results differ, use the first result, forgetting the second.

In the worst case, the procedure may not terminate.
Problem: Is it possible to design an algorithm which guarantees termination in the worst case? What is the technique to solve such an impossibility problem?

No, it's not possible.  Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination.  Then there would be some $n$ such that this always terminates after $n$ coin flips.  Let $S$ denote the set of flip-sequences that causes your algorithm to output 0 (so that $\overline{S}$ is the set of flip-sequences that causes your algorithm to output 1).  The probability of your algorithm outputting 0 is equal to the probability of getting a flip-sequence in $S$, which is a sum of the form

$$\sum_{x \in S} {a_x \over 3^n}$$

where each $a_x$ is an integer.  Thus the probability of outputting 0 has the form $b/3^n$ where $b$ is an integer.  We want this to be $1/2$, for your algorithm to produce an unbiased bit of output.  However since $3^n$ is odd, there is no integer $b$ such that $b/3^n = 1/2$.  Therefore, no such algorithm can exist.


Is the following language recursively enumerable? Let $L =\{  <M> | $ the amount of words $w\in\Sigma^*$ that $M$ does not halt on is finite $\}$.

I would like to prove that $L\notin RE$.

I can show that $\overline{L}\notin RE $ that is $L\notin CoRE$.

I do this with showing a reduction: $\overline{L_{acc}} \leq \overline{L} $ and since $\overline{L_{acc}}\notin RE$  then $\overline{L}\notin RE$.

The reduction goes as follows:

input: $<M>,<w>$
output: $<M_w >$

where $<M_w>$ is a TM that, on an input $x$ ignores it and performs:

Run $M$ on $w$
If $M$ rejected get yourself into an inf loop
If $M$ accepted then accepts as well.

Now if $<M><w>\in\overline{L_{acc}}$ then $w\notin L(M)$, thus $M$ either rejects $w$ or does not end its calculation on it, but in both cases $M_w$ will not end its calculation on all inputs. Otherwise, if $<M><w>\notin \overline{L_{acc}}$ then $w\in L(M)$ and then $M_w$ will halt (and accept) its calculation on every input $x$.

So I have that $\overline{L_{acc}} \leq \overline{L} $ and thus $\overline{L}\notin RE$, that is $L\notin CoRE$.

But I am at a loss on how I can prove $L\notin RE$? I tried a reduction from $\overline{L_{acc}}$, but this idea does not work because $M$ might not halt on $w$.  I also tried from $L_{\Sigma^*}$ or from $L_d$, but could not find a reduction that will prove me that $L\notin RE$.

Does someone have an idea for such a reduction? Or perhaps another method to prove $L\notin RE$?

I'll provide some hint. Try building a reduction $\overline{L_{acc}} \leq L$
changing your argument as follows:

... where $<M_w>$ is a TM that, on an input $x$ it performs:

Run $M$ on $w$ for $|x|$ steps
If $M$ rejected within $|x|$ steps ...
If $M$ accepted within $|x|$ steps ...
If $M$ did not halt within $|x|$ steps ...

When $M$ does not accept $w$, you want the above to diverge only on finitely many $x$s.

When $M$ accepts $w$, you want the above to diverge on infinitely many $x$s.

Alternatively, you can try to exploit the Rice-Shapiro theorem.


What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$? I have seen the formulations

there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time

a problem requires time $n^{2-o(1)}$

a problem requires time $\Omega(n^2)$

being used in the context of lower bounds but I am not sure as to whether there are relevant differences between these notations or if they are simply equivalent. Intuitively, it seems to me like at least the first and third one are while the second one excludes running times like $n^3$ that are included in the others. However, I have also encountered situations where the second one has been used in a similar way to the first one (i.e. the definitions of the Orthogonal Vectors Hypothesis here, p. 6 and here, p. 6) which suggests to me that they are also equivalent. So how do these notations relate to each other?

It is conjectured that 3SUM cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon > 0$; equivalently, it requires time $n^{2-o(1)}$. This is not the same as the stronger conjecture that 3SUM requires time $\Omega(n^2)$. Indeed, the latter conjecture (which was the original form of the 3SUM conjecture) is false: Grønlund and Pettie came up with an $O(n^2/(\log n/\log\log n)^{3/2})$ algorithm (there were improvements since).
The statement "problem X requires time $n^{2-o(1)}$" states that there exists a function $f(n) = o(1)$ such that any algorithm for X runs in time at least $n^{2-f(n)}$. In particular, there is no $O(n^{2-\epsilon})$ algorithm, for any $\epsilon > 0$. The converse should also hold, I believe – could be a  fun exercise to show.


A question about domains in Karp reductions A basic question or request for clarification regarding Karp reducibility:
Let $\Sigma^*$ be the set of all finite strings of 0's and 1's.  Call a subset of $\Sigma^*$ a language.  Let $\Pi$ denote the set of all functions from $\Sigma^*$ into $\Sigma^*$ that are computable in polynomial time.  According to Karp, a language $L$ is reducible to a language $M$, also denoted $L \leq_K M$, if there is a function $f \in \Pi$ such that $f(x) \in M \Leftrightarrow x \in L$.
For many problems, however, we are interested in the difficulty of determining membership in subsets of domains other than $\Sigma^*$.  To address this, Karp briefly discusses encodings:  Given a domain $D$, there is often a natural "one-one" encoding, $e: D \rightarrow \Sigma^*$.  He then says that given a set $T \subset D$, $T$ is recognizable in polynomial time if $e(T) \in \mathcal{P}$.  But don't we, in practice, typically consider $T$ to be recognizable in polynomial time if, for any $x \in D$, we can determine whether $x \in T$ in polynomial time?  On the face of it, this doesn't seem to be the same as Karp's definition, since there is no guarantee that $e(D) = \Sigma^*$.
Similarly, according to Karp, $T \leq_K U$ where $T \subset D$ and $U \subset D'$ if $e(T) \leq_K e'(U)$ where $e: D \rightarrow \Sigma^*$ and $e': D' \rightarrow \Sigma^*$.  However, when we are actually proving $T \leq_K U$ for some real $T$, $U$, $D$, and $D'$, don't we frequently just define an $f: D \rightarrow D'$ computable in polynomial time, confirm that $f(x) \in D'$ for any $x \in D$, and show that $f(x) \in U \Leftrightarrow x \in T$ for any $x \in D$?  Again, this doesn't seem to be the same thing as Karp's definition if $e(D) \neq \Sigma^*$.
What am I missing?

Here is an example. Consider the problem of vertex cover. An instance of vertex cover consists of a graph $G$ and an integer $k$. This is the domain $D$. You can easily come up with a one-to-one encoding $e\colon D \to \Sigma^*$ such that (i) you can recognize whether a string is in the range of $e$ in polynomial time, (ii) given such a string, you can recover $G$ and $k$ in polynomial time. The language $L$ consists of all encodings $e(G,k)$ of graphs $G$ containing a vertex cover of size $k$. If a string is not in the range of $e$, it is not in $L$.
Now suppose that you have a reduction $f$ from the domain $D$ of vertex cover to the domain $D'$ of SAT, and let $e\colon D \to \Sigma^*$ and $e'\colon D' \to \Sigma^*$ be encodings of these domains. We can construct a reduction $g$ from the language $L \subseteq \Sigma^*$ of vertex cover to the language $L' \subseteq \Sigma^*$ of SAT as follows. Given a string $w \in \Sigma^*$, we first check whether it is in the range of $e$. If not, we output some fixed string not in $L$' If it is, we output $e'(f(e^{-1}(w)))$; that is, we decode $w$, apply $f$, and then encode the result.
Most of the time, such encoding details can be ignored. This is the case since we're working in a computation model which is strong enough to be oblivious to such matters. This is why we usually don't bother with these issues too much.


Does any algorithm loops at some point? Given that any implementable algorithm has a finite number of internal states, and given that any state is determined by the previous one, does that implies that any algorithm loops at some point?
If I run the algorithm until the number of state transitions is greater than the number of internal states, by the pigeonhole principle, I should eventually get into a loop. Is that correct?

You are technically correct. A modern practical computer has finitely many states, and so any program it runs will eventually repeat a state.

However, I would like to warn against interpreting this observation in the wrong way. It is not a problem in practice. The number of possible states is huge (it's huuuuuuuuuuuuuuuuuuuuge). Algorithms that are designed for machines with infinite resources (such as Turing machines) typically run just fine on a modern computer. Of course, they may use up all available memory if they are especially memory-intensive, but that's different from them cycling because they somehow repeated a configuration due to computer limitations. And when programs do cycle forever unintentionally, it is not the limited size of the computer that does it, but rather programming errors.

It is more practical to mathematically model modern computers as if they have unlimited memory than to model them as finite-state machines. This situation is a bit like modelling in physics: classical fluid dynamics models a discrete system of atoms as if it were a continuous one.


Theory of Turing machine which outputs Turing machine? I understand the notion of the universal Turing machine ($U$), which receives a pair of Turing machine ($M$) and an input to $M$ ($x$). If $M$, which obtains $x$, outputs $y$, $U$, which obtains $(M, x)$, outputs $y$ as follows:

$M: x \mapsto y \\
U: (M, x) \mapsto y$

My question is whether there is a theory of another type of Turing machine where the output (not input) of Turing machine is another Turing machine like:

$U': x' \mapsto M$

I guess a program which generates another program can be regarded as this kind of Turing machine $U'$. If so, automatic code generator and machine learning algorithm might be regarded as this type of Turing machine.

(Maybe, brains of human programmers can be modeled using a theory of such Turing machines because a source code seems a form of Turing machine.)

It depends on what your are referring as "theory" (which basically means everything or anything).

Something which is closely related to what you are referring can be the
field of Program transformations, which tries to study systematically
programs that modifies other programs. The original interest of this field is the transformers that are semantically invariants (with a bit of hand waving:  you want to study transformers $T$ such that for any program (or a TM) $p$, $T(p)$ does the same thing as $p$). Derives from these original considerations the subfield of program synthesis (here, given some input datas, you want to automatically generate a program that satisfies some conditions encoded by you input).

A good introduction can be the thesis of M. Ward "Proving Program Refinements and Transformations" with an emphasis on the proof of program side.


Find all edges in a tree whose removal doesn't separate color classes Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use Farach-Colton and Bender algorithm to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

Also, for the reference, there’s $O(n \log n)$ approach to solve this task, which doesn’t seem to be optimizable. Let’s store in the vertice the count of all vertices of each color (now the edge is separator if in subtree there’re either no occurrences, or all occurrences of each color), but it’s a quadratic solution. Now we use small-to-large approach (merge these arrays to the one that belongs to the largest child, and pass the reference to that array to the parent), and it becomes $O(n \log n)$.

A useful lemma

First, root the tree arbitrarily if necessary, and orient all edges towards the root.

Denote by $b(v)$ the number of colours that appear at least once in the subtree rooted at $v$, and by $e(v)$ the number of colours that are completely contained in the subtree rooted at $v$.  The following lemma is key to efficiently finding all separators:

Lemma: The edge from $v$ to its parent is a separator iff $b(v) = e(v)$.

Proof sketch: The direction "the edge from $v$ to its parent is a separator $\implies b(v) = e(v)$" is easy to see: some number $k$ of colours appear in their entirety in the subtree rooted at $v$, so it must be that $b(v) = e(v) = k$.  The converse can be shown by induction on the number of colours in the entire tree, but intuitively, if we perform a series of steps, in each of which we insert a set of vertices of a fresh colour into the entire tree, then every step that adds a colour that is completely contained in the subtree rooted at $v$ increases both $b(v)$ and $e(v)$ by 1, every step that adds a colour that appears both inside and outside this subtree increases just $b(v)$ by 1, and there is no way to increase just $e(v)$, so it is impossible to recover the state $b(v) = e(v)$ while an incompletely contained colour remains in the subtree.

Computing $b(\cdot)$ and $e(\cdot)$ using deltas

Define $b^+(v)$ to be the number of colours that appear at $v$ but nowhere else in the subtree below it.  Clearly $b(v) = b^+(v) + \sum_{u \in \{u: (u,v)\in E\}} b(u)$, which we can compute in a single bottom-up pass over $T$ if we can compute $b^+(v)$ for each vertex.  Notice that $b^+(v)$ is either 1 or 0, since the only colour that can possibly contribute is the colour of $v$ itself.

Similarly define $e^+(v)$ to be the number of colours that are completely contained in the subtree rooted at $v$, but not in any proper subtree.  Clearly $e(v) = e^+(v) + \sum_{u \in \{u: (u,v)\in E\}} e(u)$.  Notice that, unlike for $b^+(v)$, $e^+(v)$ can be larger than 1, since a vertex can be the LCA of multiple colours.

Computing $b^+(\cdot)$ efficiently

Perform a bottom-up depth-first traversal, using an array $s$ of $N$ flags to keep track of whether or not a colour has been seen in any of the child subtrees.  Specifically:

Initially, set every element of $s$ to false.
On entry to a vertex $v$ having colour $c(v)$:

Set $s[c(v)]$ to false.
Recurse to process all children.
If $s[c(v)]$ is still false, then colour $c(v)$ appears at $v$ but nowhere below it, so set $b^+(v) = 1$.  Otherwise set $b^+(v) = 0$.
Set $s[c(v)]$ to true.

Computing $e^+(\cdot)$ efficiently

Every colour $c$ for which $LCA(c) = v$ contributes 1 to the value of $e^+(v)$.  Thus it suffices to calculate the LCA for each colour, and increase a counter at the corresponding vertex each time.

The total number of LCA computations is $O(N)$, since the colours partition the tree vertices, and the LCA of a set of vertices $\{v_1, v_2, \dots\}$ can be computed as $LCA(v_1, LCA(v_2, LCA(\dots)))$.  Using Farach-Colton and Bender's LCA algorithm, after $O(N)$ preprocessing each LCA can be computed in constant time, for $O(N)$ computation of all $e^+(\cdot)$ values overall.

Final pass

A final bottom-up pass computes $b(v)$ and $e(v)$ for each vertex $v$ from $b^+(v)$ and $e^+(v)$ and the values of $b(v)$ and $e(v)$ of child subtrees as outlined above.  At each vertex $v$, test whether $b(v) = e(v)$, and if so output the edge leading from $v$ to its parent as a separator.  This takes constant time per tree edge, so $O(N)$ overall, making the entire algorithm $O(N)$-time.


Karnaugh map with don't care: increasing the number of groups instead of simplifying AB
        00  01  11  10
    00 | x | 1 | 0 | 1 |
CD  01 | 0 | 1 | x | 0 |
    11 | 1 | x | x | 0 |
    10 | x | 0 | 0 | x |

The answer to the above Karnaugh map is $F(ABCD) = B D + \bar B \bar D + \bar A \bar C \bar D + \bar A C D$
according to my book and the K-map solvers online.

But what I don't get is that I can further reduce the terms in this answer:
$F(ABCD) = \bar B \bar D + \bar A CD + \bar A B \bar C$
also covers all the min terms in lesser groups.

The answer in my book just has a bigger group covering additional don't cares. Since they are optional shouldn't my answer be correct?

Your answer is correct. It is also more reduced. The reason your book and the solver give you a bigger equation is because they use a greedy algorithm that attempts to match bigger groups (groups with less variable in them). This will have an optimal behavior if the map has no "don't cares" [reference needed].

To have optimal behavior with "don't care", you have to consider that an X can be either a 1 or a 0. That means that for each X, you have two versions of you map. So, if you have $N$ "don't cares", you will have to reduce the $2^N$ versions of the map and choose the smallest reduced operation from the results.

Extra

If you have lots of those maps to reduce, i suggest you use Logic Friday or a similar equation reducer.


How to calculate the number of tag, index and offset bits of 2 different caches? I have two exercises:
1) A 128KB direct-mapped cache, with lines from 32bytes/lines and 36-bit address.
2) A 512KB 2-way associative cache, with lines from 64bytes/lines and 36-bit address.
For both exercises i have to find the number of bits needed for the tag,index and offset fields.
I tried to do both exercises and i found these results:
1)5 bit offset, 17 bit index, 14 bit tag
2)6 bit offset, 12 bit index, 18 bit tag
First exercise:
128KB = 217
32 bytes = 25 so 5 bit offset
17 bit index
36-5-17=14 bit tag
 Second exercise:
64 bytes = 26 so i have 6 bit offset
512KB = 219
512/2 = 219/2 = 218 cache lines number
218/26= 212 so i have 12 bit index
36-(12+6)=18 bit tag

Assuming that your machine is byte addressable(1 word = 1 byte), Let us solve the problem step by step.

1.

Physical address = 36 bits. Since 32 bytes/line and size of cache line = size of main memory block, this means block offset = 5 bits. Hence remaining 31 bits is block number( = tag + index).

number of cache lines = 128KB/32B, therefore, 12 bits for index and hence remaining 19 bits for tag.

2.

Physical address = 36 bits. Since 64 bytes/line and size of cache line = size of main memory block, this means block offset = 6 bits. 2-way associative cache means that two lines in one set.

number of sets = total cache lines/2 = (512KB/64)/2 = 2^12 , therefore 12 bits for set, and hence remaining 18 bits for the tag.


Trying to understand simple bit states I am trying to understand bits, operations and masking. I have a hard time to get this thing into my head. I have tried to read at many different websites without luck.

I have 8 states, going from 1 to 8:

state 1 = 0001
state 2 = 0010
state 3 = 0011
state 4 = 0100
state 5 = 0101
state 6 = 0110
state 7 = 0111
state 8 = 1000

Now I want to get state 1, 3, 6 and 8. I am unsure how to set this state in the bits. Either I can do this:

state 1 = 0001
state 3 = 0011
state 6 = 0110
state 8 = 1000

Which would turn out like this:

combinedStates = 1111

The problem is, if I send in this, state 5 will get triggered as well as:

state 1 = 0001
state 3 = 0011
state 5 = 0101
state 6 = 0110
state 8 = 1000

Because both state 5 and 6 has a 1 in the same place. The second thing would be to add all the state numbers together (1, 3, 6 and 8, which is 18):

combinedStates = 0001 0010 (18)

But then looking at state 6 would not work as:

state 6 = 0110
combinedStates = 0001 0010

There will be a missing 1.

How would I proceed if I want to get states 1, 3, 6 and 8: combine their bits, or add them all together and use that one's bit value? Any other approach? Any operand I should use?

The easiest solution is to use one bit per state for a total of 8 bits:

state1 = 0000 0001
state2 = 0000 0010
...
state8 = 1000 0000

Then you can just bitwise or (or add) them together. Many programming languages have a datastructure for "bitsets" that can help with this, especially if you have more bits than fit in a simple integer. Your example with just 8 states fits in a typical int, so you don't really need such a data structure.


What is an IELR(1)-parser? I try to teach myself the usage of bison. The manpage bison(1) says about bison:

  Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser tables.

What is an IELR-parser? All relevant articles I found on the world wide web are paywalled.

An article that claims to introduce it: IELR(1): Practical LR(1) Parser Tables for
Non-LR(1) Grammars with Conflict Resolution (via archive.org) by Joel E. Denny and Brian A. Malloy, Clemson University, is freely available from Malloy's site.

What they are worth is something I can't answer. (Personally I don't understand the need for such crippled CFG parsing - why limit your expressive power when you can just use GLR?  What does make sense to me is something like TAG or PEG (they seem natural and add expressive power) or tree grammars (for languages such as XML, in which recognizing parse trees is unproblematic by design.)


Showing $2^x$ is a lower bound How do I show that $2^x - x^2 \in \Omega(2^x)$?

Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.

I worked around a bit with this and I seemed to have gotten something that makes sense for the case of an upper bound;
$$2^x -x^2 < 2^x + x^2 < 2^{x+1} = 2.2^n $$
Now, if I were trying to find an upper bound, I'd have chosen $a = 2$ and $x_0 = 1$. How do I work the other way around(basically less than or equal to $2^x - x^2$ and prove this lower bound?

Here is the hint or outline of a proof.

Show that by mathematical induction, that $2x^2< 2^x$ for $x>7$.
Show that $\dfrac12\cdot2^x< 2^x-x^2$ for $x>7$


Can Santa be both fair and efficient? As the net-evergreen The Physics of Santa establishes, it is physically impossible for Santa to get a gift to every kid on the planet. Route planning won't help much there, but can a good planning algorithm at least make sure that every kid gets a gift once in a while while Santa also serves as many kids as possible each year?

Consider a complete graph with real, positive weights and a constant $k$. We want to solve a variant of the Travelling Sales Person problem:

  Is there a circular route of length at most $k$ that serves more than $m$ nodes?

The optimisation version would be:

  Maximise the number of nodes that can be served with a circular route of length at most $k$.

This is motivated by real-world limitations on routes: Santa has one night to deliver as many gifts as possible, a sales person has eight hours for one day's route, and so on.

The first, but not final question is: how hard is this problem? Let's assume we can start at any node, but that should not make too much of a difference.

Now, in order to model fairness, let's assume there are $N$ nodes and we can visit at most $M$ with every tour. Ideally, we would want that every node is visited $t\cdot\frac{M}{N}$ times across $t$ efficient tours. Since there may be bottleneck nodes that have to be visited more often in order to ensure routes visit many nodes, some will inevitably have to be visited less often. That also excludes the trivial approximation of removing once visited nodes until all have been visited.

So, here is the final question. Let $T$ be the number of tours needed until all nodes have been visited by efficient $k$-tours. How can we algorithmically determine the minimal value of $T$ (and all the necessary routes)? How complex is this problem?

I guess this is really a multi-criterial problem: each tour should visit as many nodes as possible while we want to keep tours as disjoint as possible.

I am slightly confused. If $k$ is a constant, then you can try all $O(n^k)$ possible tours. Hence the problem is in ${\sf P}$.

However, if $k$ is part of the input, the decision problem is ${\sf NP}$-complete. This can be shown by reducing $\text{HAM-CIRCUIT}$ to the problem, by the following reduction.

Assume that we want to determine if a $n$-vertex graph $G$ has a Hamiltonian circuit. Then we take the complete graph $K_n$ with the following distance function
$$
w_{ij}:=\begin{cases}
1 & \text{if $(v_i,v_j)$ is an edge in $G$} \\
2 & \text{otherwise}
\end{cases}.
$$
Furthermore we pick $k=n$ and $m=n-1$.

Let me tell you why this is a reduction. If $G$ has a Hamiltonian circuit, then there is a tour in $K_n$ with length $n$. In other words a circular route of length $\le n$ that serves $> (n-1)$ nodes. On the other hand, if there is a Santa-tour that visits $>(n-1)$ nodes is has to visit all nodes. Since the Santa-tour can only have length $\le n$ and every edge length is at least 1, all $n$ edges in this tour have length 1. Hence this tour corresponds to a Hamiltonian circuit in $G$.


Creating all possible subsets and complexity calculation I am a novice programmer and very weak in complexity calculation. I have learnt to write a program for creating all possible subsets from a set of elements, i.e. knapsack algorithm.  Now I would like to know how to calculate the complexity of the algorithm. Can anyone help me with better clarification.
Here is my code:

#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
int N,M,a[15];
map<int,vector<int> >multiple;
void creating_subset(int i,int m,int l)
{
  if(i>=M)
  {
    multiple[l].push_back(m);
    return;
  }
  creating_subset(i+1,m*a[i],l+1);
  creating_subset(i+1,m,l);
}
int main()
{
  cin>>M;
  for(int i=0;i<M;i++)
  cin>>a[i];
  creating_subset(0,1,0);
  for(int i=0;i<multiple[3].size();i++)
  printf("%d ",multiple[3][i]);
  cout<<endl;
  return 0;
}

Your code doesn't really generate all subsets, but it does go over all subsets. The complexity of your code depends on the complexity of the data structures you use, which you'll have to figure out yourself. The proverbial "innermost loop" in your case is the if (i >= M), and this part runs $2^M$ times (once for each subset). If the complexity of the innermost loop is $C$, then the overall complexity of the code would be $O(2^M C)$, since the complexity of all other parts pales in comparison.


how to use type application rule (T-TAPP)? In the following rule,

$$\dfrac{ \Gamma \vdash t_1  : \forall X.T_{12} }
        { \Gamma \vdash t_1 \ [T_2]  : [X \mapsto T_2]T_{12} }
        \textsf{ (T-TApp)}$$

whend doing type checking, how do know what is $X$?

Also, type checking will not give you a term which has a form $[X \mapsto T_2]T_{12}$, so how to deal with that substitution?

We will have $t_1 \ [T_2]$ during type checking and $T_2$ could be any type such as $T, T \to T,\forall X.T$. How do we know $[X \mapsto T_2]$, again?

I just could not understand how to apply this rule during type checking?

Please help!

Type checking and the inference rules for type theory are not an algorithm. They do not tell you how to type check. They tell you what is allowed when you perform type checking.

The rule for application should be read as:

  If you can prove $\Gamma \vdash t_1 : \forall T . T_{12}$ (and we're not telling you how to do that, you'll have to figure it out) then $\Gamma \vdash t_1[T_2] : [X \to T_2]T_{12}$ for whatever $T_2$ you choose to use (and of course we do not know what it is that you're trying to do here, the choice of $T_2$ is entirely up to you).

So, the answer to your question is: you have to figure out how to find the value of $X$ and you have to worry about the subtitution. The rules are not meant to solve that problem. They are just rules, telling you what you may do.

The correct question that you should have asked is: "How do I make an algorithm that will be able to perform type-checking automatically?" This is an important question, and people put a lot of thought into it. I can give you an initial answer: try out all possibilities until you find one that works. But that's a lousy aglorithm and it's possible to do better.


What is the point of traversing a binary tree in preoder, inorder or postorder? Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?

Different traversals of a binary tree exist to suffice different data dependencies between the nodes.

Let's have a comparison between different traversals of a tree. Note that aside from in-fix traversal, the tree doesn't have to be binary.

In case of Postorder, we process the descendants of a node before the node itself, meaning that we want to send some data from the descendants to the ancestors to be able to process the ancestors. For example if you want efficiently to calculate for each node $n_i$ the weight of the subtree rooted at $n_i$, which is the sum of the weights of all descendants of $n_i$ including $n_i$.

In case of Preorder, you process the predecessors before the descendants. One use case is broadcasting data to all descendants of each node in the tree. For example, if you want count the number of predecessors of each node with some characteristic, you propagate the counter of each node to its children and each child add one if it has the characteristic itself.

In case of Inorder you might have a left-right order between the nodes of the tree (Example: binary search tree), and might be interested in visiting the elements according to this order (Printing the keys of a binary search tee in ascending order).

Finally, in case of BFS, we consider the tree as levels, level $l_i$ has all vertices with depth $i-1$, which is at distance $i-1$ from the root of an unweighted tree. BFS has a lot of use-cases. Here we are interested in processing all nodes of each level consequently (starting from the smallest level). Most common use cases are the ones where we want to process the closer vertices to the root before the farther ones for example if we want to assign ids to the vertices so that for two vertices $n_i, n_j$ if $i < j$, $n_j$ is not closer to the root than $n_i$.

Note that in some cases you might be interested in two consequent traversals for example a post-order to gather data from the whole tree in the root and a following pre-order to broadcast the data to each node in the tree in total linear time in the size of the tree.

Note In some cases any of the traversals suffices, if all nodes are independent of each other and you are only interested in visiting all nodes of the tree(For example, to calculate the depth of each node you can use BFS or Preorder with no remarkable differences). However, some times you might still be interested in the order you are visiting the nodes even if there is no data-dependencies between the nodes (For example printing mathematical expression in polish notation vs. infix notation. see link).

Note One interesting application is Euler tour technique in parallel computing. By setting the right weights on the right edges you get pre-order, post-order and the depth of the nodes of a tree. see link.


safe edge for Minimum spanning tree I know this question is posted many times, but i am still posting this because i have my own doubt which pulls me out to move forward to kruskal and prim's algorithm.So Please do help me out $-:$

Question

  Let $G=\left(V,E\right)$ be a be a connected, undirected graph with a real valued weight function $w$ defined on $E$.Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$.Let $\left(S,V-S\right)$ be any cut of $G$ that respects  $A$.Let $\left(u,v\right)$ be a light edge
    crossing $\left(S,V-S\right)$.Then, edge  $\left(u,v\right)$  is safe for $A$.

Terminologies Used

  we say that an edge $\left(u,v \right)$ crosses the cut if one of the endpoint is in $S$ and other in $V-S.$

  Safe edge is edge at each step that we can add in A without violating any invariant.

  we say that a Cut RESPECTS a set A of edges if no edge in A crosses the cut.

  we say that an edge is a light edge satisfying a given property if its weight is the minimum of any edge satisfying the property

MY Approach/Doubt

With the help of book, i am able to understand the proof as-:

We Assume that $T$ is a MST(Minimum Spanning tree) which do not have light edge $\left(u,v \right)$, if we can manage to construct another MST $T^{'}$which contains $\left(u,v \right)$ and have weight less than that of $T$, then we are done! i.e we have to prove that $w \left(T^{'}\right) \leq w \left(T\right)$

Consider the figure below

As MST $T$ will not contain $\left(u,v \right)$(given) ,there must be an edge that crosses the cut, otherwise it will be divided into 2 components.

Let that edge be $\left(x,y \right)$

Now let us construct the MST$T^{'}$ from $T$ by removing $\left(x,y \right)$ and adding $\left(u,v \right)$ given as-:

$$w \left(T^{'}\right)=w \left(T\right)-w \left(x,y\right)+w \left(u,v\right)
$$

$\Rightarrow \left(u,v \right) \leq  w \left(x,y\right)$ as $\left(u,v \right)$ is light edge

$\Rightarrow w(T^{'}) \leq w(T)$

My doubt is -:

  1.Is the above proof explained above correct?am i missing something?

  2.If the above proof is correct, then i have one issue .Issue is that after proving the above inequality $w(T^{'}) \leq w(T)$,the book says that
  $\left(u,v \right)$ is actually a safe edge for A,but is n't this contradictory?

I mean if $\left(u,v \right)$ is safe for $A$ ,then cut $\left(S,V-S\right)$
no longer respect $A$ because  $\left(u,v \right)$  is an cross edge .

please help me out !

For a set $A$ which is a subset of some minimum spanning tree, an edge $e \notin A$ is safe if $A \cup \{e\}$ is a subset of some minimum spanning tree. In particular, if $|A| = n-2$, then any safe edge will cross the cut $(S,V-S)$. There is absolutely no requirement that $e$ not cross the cut.


Is this the correct time complexity of my algorithm? I have an algorithm broken down into the pseudish code below. But the gist of it is, we go through every person in a list, we then ask them to talk to all of their friends. Every time we choose a person to eval in the list, it costs $log N$ time. Every time that person talks to a friend it costs $log N$. What is the time complexity? Is my answer right?

My answer: $O(N \cdot log(E \cdot log(N)))$

List[People] // N

forall People in List:  //O(Log N) to get a person in list
   forall friends of Person:    // Person has a set of Friends E that is [0, N)
       Person.talkToFriend(friend)  //Costs O[LogN] to talk to a friend

For each of the n people in the list you do $|E|\cdot log(n)$ plus the time of getting it from the list, which is $log(n)$. So the time you start with is complexity: $O(n(log(n)+(log(n)|\cdot|E|)))=O(n\cdot|E|\cdot log(n))$

Assuming E could be as big as n, you could simply say the time complexity is $O(log(n)\cdot n^2)$.


Implementing primitive recursive functions in a programming language I started studying Design Concepts in Programming Languages by Turbak, Gifford and Sheldon. In the first chapter, they define a language called POSTFIX, similar to a postfix calculator's input language. This one also has a conditional command and a subroutine-like struct. So, it seemed like it could implement a looping  construct like while. But later, the book gives proof that POSTFIX is not able to encode infinite loops, programs always terminate.

In an exercise, the book wants me to implement a factorial program in POSTFIX, if possible. I tried and failed miserably for hours. I looked up on primitive recursive functions, which factorial is one. Found a language called LOOP, designed by Uwe Schöning that can compute only the primitive recursive functions. I tried implementing in POSTFIX a looping construct that always terminates but could not do it. Because the language does not have any naming or abstraction facilities, I could not see how I can do it.

What I ask is this:

Using the POSTFIX definition given on the below link, can someone implement a language construct that can be used to implement primitive recursive functions, like implementing a looping construct that always terminates? Or give a proof that it is not possible maybe.

Note: There is a draft of the book (thanks @YuvalFilmus) where you can find the description of POSTFIX language (section 1.4, pp5).

You can prove by induction that the number of instructions executed by any given program is bounded (essentially since no command can create instructions). In particular, the number of arithmetic instructions executed by a program is bounded. This means that the output of a univariate function is polynomially bounded. Since the factorial function is not polynomially bounded, you cannot compute factorial.

If, however, we add a pget instruction which is similar to nget but gets a subroutine rather than a number then we can compute factorial, for example with the following program:

(postfix 1 1 (3 nget 3 nget mul 4 nget 1 sub swap 2 nget (3 pget 1 pget exec) () sel exec) 1 pget exec)


Language of lists of words, not all of which are different, is not context-free How do I prove that the following language isn't context-free using the pumping lemma?
$$
L=\{w_1\#w_2\#\dots\#w_k \colon k ≥ 2, w_i \in \{0,1\}^*, w_i = w_j \text{ for some } i \ne j\}
$$
I am having trouble choosing the string to use for the proof. I know that I have to choose a string such that at least two substrings separated by the # are equal to each other but am unsure of how to approach this. If someone could please help me with this, I would appreciate it.

If $L$ were context-free then so would $L' = d(L \cap (0+1)^*\#(0+1)^*)$ be, where $d$ is the homomorphism that deletes $\#$. However, $L'$ is the language of squares (words of the form $w^2$), which is well-known not to be context-free.
If for some reason you have to prove that $L$ is not context-free directly using the pumping lemma, this suggests looking at the proof that $L'$ is not context-free and trying to adapt it.


How to prove LTL-formulas true for all paths? I'm quoting a question from my homework which I don't understand its wording.

Also, I'm not looking for an answer for my problem, I just want to be pointed at some articles/tutorials/reading/tips to solve them.

Gp ⇒ (p U q) U p
(p U q) ∧ (q U p) ⇔ p ∧ q
Fp ⇔ F(Xp)
X(Fp) ⇔ F(Xp)
(p U (q ⇒ ¬Xq)) ∧ (FGq) ⇔ p U (Gq)

They ask me to prove if these formulas are true for all paths but it seems like they want me to prove them to be equivalent instead.

The statements you wrote are tautologies, i.e. they are always true. I will give you an example proof for the arguably easiest statement $FXp \leftrightarrow XFp$ so you see how you could do it yourself for the others. Also, it would be good to know if you are working on finite or infinite paths. I am going to use infinite paths here because that is more common as far as I know.

The statement says "There is a point in the future so that at the next position $p$ holds if and only if there is a point in the future other than the current point at which $p$ holds.

We can describe the path with the single predicate $p$ by a set $A \subseteq \mathbb{N}$ at which $p$ is true, and $\mathbb{N} \setminus A$ at which $p$ is false. Let $n \in \mathbb{N}$ be any position.

If $n \models FXp$, this is (by definition) equal to: there is a position $m \geq n$ such that $m \models Xp$, which is equal to $m+1 \models p$, which is equal to $m+1 \in A$. In other words: $n \models FXp$ if and only if there is an $m \geq n$ such that $m+1 \in A$.

If $n \models XFp$, this is equal to $n+1 \models Fp$, which means there is an $m \geq n+1$ such that $k \models p$, so $k \in A$. Again, this means $n \models XFp$ if and only if there is an $k > n$ such that $k \in A$.

You can see that these two statements are clearly equivalent if you choose $k = m+1$. Therefore, $n \models FXp$ iff $n \models XFp$.


Maximum weight perfect matching in general graphs Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows
$$
\text{maximize}~~\sum_{e\in E} w_e x_e
\\
\text{subject to}~~\sum_{e\in E: v\in e}x_e=1\text{ for all }v\in V
\\
0\le x_{e}\le 1\text{ for }e\in E.
$$
In the corresponding Integer Program $x_e$ is a binary variable s.t.
$$
x_e =
\begin{cases}
1 \text{ if } e \text{ is in the perfect matching}\\
0 \text{ otherwise}
\end{cases}
$$
I am unable to come up with an example where given $G$ has a perfect matching, the LP does not have an all integral optimal solution $x_e^{\text{*}}$. I tried taking small examples with odd length cycles, though there was a fractional optimal for the LP, there was an all integral optimal as well (in the examples I took).
I am aware that for bipartite graphs if the LP is feasible, then there always exists an all integral optimal for the LP. Does it hold for general graphs as well? If not I would appreciate hints so I can come up with such an example.

AB, CD, EF  is the unique perfect matching
Assigning $x_e = 0.5$ to all edges except CD gives the optimal LP solution.


$stCON$ with path of length $≥ n/2$ The following problem seems very similar to the $stCON$ decision problem:

{$G, s,t  |  G = (V, E)$ such as $V$ is a graph, $s,t ∈ V$,
there exists in $G$ a simple path from $s$ to $t$ of length $≥ n/2$}

But from what I've read, it cannot be placed in $NL$. The reason is unclear. Why it cannot be placed in $NL$ using an verifier Turing Mechine like in $stCON$ case and another counter for the path length?

The NL algorithm for $s$-$t$ connectivity proceeds as follows. Start at $s$. For $n-1$ steps, guess a neighbor of the current node, and accept if that neighbor is $t$. The memory requires is two vertices (the current one and the next one), and a counter that counts the length of the current walk.

If you want to check that there is a simple $s$-$t$ path of length at least $n/2$, you need some way to ensure that in the process, vertices don't repeat. It's not so clear how to do that without storing all vertices visited so far, which cannot be done in logspace.