Terminology for a graph with ports on its nodes A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain domain or application requires that edges don't merely connect vertices, but instead connect ports that exist on these vertices. In a directed graph, this would imply separation between input ports and output ports, wherein typically an edge starts at an output port and arrives at an input port.

Examples are easy to find: shader design tools, signal flow graphs in compiler theory, electronic schemas, high-level ETL scripting... all these tools require that vertices have named or distinct inputs and outputs.

Now for my question: is there any theory and nomenclature on these kinds of graphs, or is this considered to be an "implementation problem" of the engineering sciences? As you notice from my question, I can't quite pinpoint what this kind of thing is called ("A Graph With Node Ports"), and I'd love to see that answered.

I was wondering the same thing. It seems that there are a number of publications revolving around this idea, most of them at the TERMGRAPH workshop. They are usually called “port graphs” there.

Tracing the related work of a random sample of papers yields that the following might be the prime paper that introduces this formalism:

  Andrei, O. and H. Kirchner, A Rewriting Calculus for Multigraphs with Ports., in: Proceedings of RULE’07, Electronic Notes in Theoretical Computer Science 219, 2008, pp. 67–82.

One that I find particularly interesting is

  Sandra Alves, Maribel Fernández, and Ian Mackie. A new graphical calculus of proofs. In TERMGRAPH, volume 48 of EPTCS, pages 69–84, 2011


Lovasz theta of even cycle How does one show Lovasz theta of even $n$-cycle ($n$ is even) is of form $\frac{n}{2}$? Why is the Lovasz theta of such cycles not of form $\frac{n \cos(\frac{\pi}{n})}{1+\cos(\frac{\pi}{n})}$. Could someone provide a derivation for even cycle Lovasz theta number. It is clear that the Shannon Capacity is $\frac{n}{2}$. why is the cosine form tight only for odd cycles?

The Lovász theta function is bounded between the independence number and the clique covering number (the chromatic number of the complementary graph). For even cycles, both numbers are $n/2$. For example, for the $6$-cycle with vertices $1,2,3,4,5,6$, there are independent sets of size $3$, e.g. $\{1,3,5\}$, and the graph can be covered with the $3$ cliques $\{1,2\},\{3,4\},\{5,6\}$.


Replace 1's with -1's and vice versa in a matix Assume that we have an anti-symmetric matrix that consists of 1's and -1's and 0's. All the elements of the main diagonal are 0 and each row and each column has exactly one 1, and one -1. Design an algorithm that replaces all 1's with -1's and vice versa only by swapping some rows and some columns.

Your matrix encodes a directed graph in which the in-degree and out-degree of each vertex is 1. In other words, your graph is a collection of directed cycles.

If you swap rows $i$ and $j$ and columns $i$ and $j$, then you have swapped vertices $i$ and $j$ in the graph. This has the effect of switching the direction of the edge between $i$ and $j$, but also affects other edges touching $i$ and $j$.

In order to finish the solution, it suffices to consider a single directed cycle involving all vertices, say $1 \to 2 \to \cdots \to n \to 1$. We would like to swap vertices so that the the cycle becomes $1 \gets 2 \gets \cdots \gets n \gets 1$.

We now consider two cases:

$n = 2k+1$ is odd. In this case, we swap $(1,n), (2,n-1), \ldots, (k,k+2)$ to get
$$
n \to n-1 \to \cdots \to k+2 \to k+1 \to k \to \cdots \to 1 \to n.
$$
$n = 2k$ is even. In this case, we swap $(1,n), (2,n-1), \ldots,(k,k+1)$ to get
$$
n \to n-1 \to \cdots \to k+1 \to k \to \cdots \to 1 \to n.
$$


Turing Machine Encoding and Complement of the Diagonal Language In trying to understand how Turing Machine encoding works, there is a question that I have come across that goes something like this:

Given that the diagonal language, $L_d = \{ w_i \mid w_i \space is \space not \space accepted \space by \space M_i \}$, what is the first string of the encoding of the complement of $L_d$ which is $\bar{L_d}$?

I am assuming also that this is operating with the alphabet of $\Sigma = \{0, 1\}$. Is there any way that it is even possible? I am confused also since $L_d$ is an undecidable language how this is possible?

Also by encoding I think that the question is referring to binary encoding with a tape alphabet $\{0, 1, B\}$ with Turing machine $M$ defined as:

$M = < Q, \{0, 1\}, \{0, 1, B\},\delta,q_1,B,\{q_2\} >$

with moves defined by:

$\delta(q_i,X_j) = (q_k,X_n,D_m) \rightarrow 0^i10^j10^k10^n10^m $

where $X_1 = 0, X_2 = 1, X_3 = B$
and Direction is given by: $D_1 = L, D_2 = R$,

and the Binary encoding of $M$ as $<M>$: $111 \space move_1 \space 11 \space move_2 \space 11 \space ... \space 11 \space move_{last} \space 111$

Update: If my understanding is correct, the correct encoding should represent a Turing machine which accepts every string since originally we do not accept any string? How would one go about formulating an encoding for such a Turing machine? Does it have to be a unique encoding, or does it just imply that any Turing machine that accepts every string is valid?

The following hint repeats my comments and assumes that the question asks for the first encoding of a Turing machine which is in $\overline{L_d}$.

Hint: Make a list of the first few encodings of Turing machines, in lexicographic order. For each one, check whether it's in $\overline{L_d}$. The first one which is in $\overline{L_d}$ is the answer.

By the way, how does your encoding handle termination? Does it mark accepting/rejecting states in some way, or does it use another convention?


Confused on Variational AutoEncoder I'm a bit confused on how Variational Autoencoders are trained. In particular I'm confused on how the latent variable is generated for each input.

My questions are as follows:

When running stochastic gradient descent does the sampled latent variable stick with the data point during the entire run or does a new latent variable get sampled each time descent is run?
If running batch or full gradient descent, each data point gets its own set of sampled latent variables right?
How do you check for convergence? Assuming the latent variable is sampled at each iteration, it's not clear to me how you can evaluate if you have converged or not given the stochastic nature of the performance function.

VAE's have an encoder.  The encoder maps an input to a latent vector. The latent vector doesn't "stick".  Instead, in each iteration, we use the encoder to map to a latent distribution, sample from that latent distribution, then use the decoder to map to a reconstruction, and compute the loss.  Yes, each data point is mapped to its own latent vector.  Yes, you run the encoder anew and sample anew for each point and each iteration of training.

You check for convergence in the standard way for any neural network: you look for the value of the loss function to plateau.


Exponential-size numbers in NP completeness reduction In the proof of Theorem 4 in [GS'12], the authors reduce an instance of PARTITION to their problem. Therefore, they create for each element $a_i$ in the instance of PARTITION a number $2^{c \cdot a_i}$ for a suitable constant $c$, which is later used in the reduction. They argue, that the instance remains of polynomial size since these exponential-size numbers can be encoded implicitly. Nevertheless, can we really work with those numbers in polynomial time? What if we add such two numbers $2^{c \cdot a_i}$ and $2^{c \cdot a_j}$ for $a_i \neq a_j$ in the course of the algorithm, then the resulting number cannot be encoded in this way any longer. Is this reduction valid?

[GS'12]: Martin Groß and Martin Skutella, "Generalized maximum flows over time", 2012.

Changing the encoding of the inputs changes the problem.
When inputs are given succinctly the problem can become much harder.
On the surface of what you are saying
they are proving the NP-hardness of a succinct version of the problem,
not the original problem.

You can also think of it as a reduction from Partition
where numbers are given in unary to the original problem.
The unary version of Partition is in P.
So does not show the problem is NP-hard.
(It might be possible to use 3-Partion in place of Partition
which remains NP-hard even when numbers in the input are encoded in unary.)

The issue is that it is not clear what are the inputs to the problem.
They seem to be working with a version of the problem where $\gamma$s are not
part of the input to the problem
but are  determined from $\tau_e$ which is part of the input.
In the theorem it seems that
$\gamma_e$ is fixed to be $2^{c\tau_e}$ (where $c$ is a fixed constant)
and are not part of the input.
If $\gamma$ is not part of the input and fixed to be determined from $\tau$ as stated
then it doesn't matter that they are exponentially large.

In summery, the paper is not very clear in its treatment of the issue.
It seems that in the theorem
they are considering those numbers as not being part of the input to the problem (determined from $\tau_e$).
Or that they are given in a succinct form of $a2^e$.
The paragraph after the theorem
where they say that it is open whether the results holds in case the usual binary encoding of numbers is used seems to support that.
So they are not proving that the problem where $\gamma$ is part of the input
and encoded as normal binary numbers is NP-hard.
That is still open according to them.
They are proving that variants of the problem mentioned above are NP-hard.


ZigZag sequence without dynamic programming I just came across the maximum zigzag sequence problem, defined as follows:

  A zigzag sequence is defined as a sequence of numbers such that the difference between two consecutive numbers alternates between positive and negative.

  Given a an array of N integer number, find the length of the longest zigzag subsequence. A subsequence is formed by deleting zero or more elements of the original sequence, but preserving the order in the original sequence.

  For example given the array {1, 2, 4, 2, 3, 5, 1} the subsequence {1, 4, 2, 5, 1} is the longest zigzag.

  A sequence of one element is a trivial zigzag of length 1.

I've found several references to a dynamic programming formulation of the solution which is O(N^2) and very complex. See for example this.

However, I've come with a much simpler solution with O(N) and based on finding all the local maximum and minimum of the original sequence, that is, the elements of which the sign of the difference between consecutive elements change. Here is the code in Java:

public static int zigZagLength_pablochacin(int[] sequence) {

    if (sequence.length == 0)
        return 0;

    int lastDiff = 0;
    int length = 1;

    for (int i = 1; i < sequence.length; i++) {
        int diff = Integer.signum(sequence[i] - sequence[i - 1]);
        if ((diff != 0) && (diff != lastDiff)) {
            lastDiff = diff;
            length++;
        }
    }

    return length;
}

Apparently,this approach has also been proposed elsewhere.

My question is, am I missing something that makes this simple solution wrong?

Note: I originally asked this question in Code review Stack, but was considered off-topic, as it doesn't relate to code style but to the solution.

Your simple algorithm is correct.

In fact, you have proved the correctness of your algorithm basically since your algorithm is, as you have written, based on finding all the local maximum and minimum of the original sequence. The simple mathematical reason is that for each zigzag, i.e., $a[i]<a[i+1]>a[i+2]$ or $a[i]>a[i+1]<a[i+2]$, there must exist a local maximum or a local minimum respectively.

A more rigorous and rather tedious proof is needed to convince all of us that there is no off-by-one error in your program. However, I will skip it since it is routine and not enlightening at all.


How to solve Assigment problem on SPOJ? Problem Link - Assign .This problem is known as assignment problem.

I read few solutions  Here is one   and they are trying to solve it using Bit-masking and DP .I tried and thought hard to understand how to solve it but i was unsuccessful ..

Let us enumerate the students $s_1, \dots, v_n$. Let $A$ be the set of students and $B$ the set of subjects. Moreover, let $S_i$ be the set of subjects the student $s_i$ likes. The dynamic programming table will be $C\left(A, 2^B\right)$, where $C(s_i, S)$ says in how many ways we can assign the subjects in $S$ to the first $i$ students. Note that if $|S| \neq i$ we have $C(s_i, S) = 0$.

The recursive function is given by the formula $$C(s_i, S_i) = \sum_{p \in S \bigcap S_i} C(s_{i-1}, S\setminus {p}).$$

To implement the solution you need a loop over all the students and for each student iterate over all possible bit masks. For the student $i$ ignore all bitmasks with number of ones not equal to $i$. Now use the formula above to compute the value for each student and bitmask based on the values of previous students.

Notes:

Checking if $M$ contains $k$ by $M \& (1<<k)$
Adding subject $k$ to bitmask $M$ by $M = M | (1 << k)$
Removing subject $k$ from bitmask $M$ by $M = M \& (((1<<n) - 1) - (1<<k))$.


Does $DTIME(2^n)$ contain $NSPACE(n)$ ? As in title. Does $NSPACE(n) \subseteq DTIME(2^n)$ ?

Generally, for functions $f(n) \in \Omega(\log(n))$, we have that
$$
 \mathrm{NSPACE}(f) \subseteq \mathrm{DTIME}(2^{O(f)})
$$
A proof can be found on slide 28 onwards of the slide set from:

 http://www.informatik.uni-leipzig.de/alg/lehre/ws12_13/KOMPL/folien-eng.pdf

I don't know if $\mathrm{NSPACE}(n) \subseteq \mathrm{DTIME}(2^{n})$ is true. TSP is in $\mathrm{NSPACE}(n)$, but the best deterministic algorithm known is in $ \mathrm{DTIME}(n^22^{n})$ (as far as I know).


How are the web based compilers designed? Is it possible to design a compiler that can safely compile and run untrusted code?

As a practical example, I want to know how the online compilers are designed/programmed?(Like the one on codepad.org) Are they similar to our traditional day-to-day compiler. How they are hosted on servers?

This question is asked on stackoverflow:

  How do sites like codepad.org and ideone.com sandbox your program

A short summary from the answers:

Using geordi (codepad does this)
Systrace
Virtualization (VM)
OS level jailing functionality

chroot
Permissions
ulimit
nice, ionice, cpulimit,
disk quotas

AppArmor, SELinux
Restrict compiler access to headers/libraries
Restrict interpreter access to libraries
Static analysis
libsandbox

A more theoretical answer would be that it is possible to restrict all calls out of the program, (syscalls, function calls etc.), in a manner similar to how native client works, if you have control of the compiler (and even moreso, if you control the CPU and OS). For time and memory consumption, you can simply have have cut-offs that would kill the compilation process/running program. This should only leave you vulnerable to bugs in the compiler, runtime libs, and the OS/hardware level; which a VM can mostly eliminate the danger of.


What is the difference between a 'page' of memory and a 'frame' of memory? WP has an adequate discussion of paging, which I think I understand.. However I am confused by the articles repeated use of the term Page Frame.

I thought frames and pages were different things.  Could someone please clarify the difference.

Short version: "page" means "virtual page" (i.e. a chunk of virtual address space) and "page frame" means "physical page" (i.e. a chunk of physical memory).

That's it, pretty much. It's important to keep the two concepts distinct because at any given time, a page may not be backed by a page frame (it could be a zero-fill page which hasn't been accessed, or paged out to secondary memory), and a page frame may back multiple pages (sometimes in different address spaces, e.g. shared memory or memory-mapped files).


TAPL: Explanation and example(s) for satisfied This question arises from my reading of "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce.

On page 36 is the definition for satisfied

  A rule is satisfied by a relation if, for each instance of the rule,
  either the conclusion is in the relation or one of the premises is
  not.

On page 36 is the definition for instance

  An instance of an inference rule is obtained by consistently replacing
  each metavariable by the same term in the rule's conclusion and all its
  premises (if any).

  For example

  if true then true else (if false then false else false) -> true

  is an instance of E-IFTRUE, where both occurrences of $t_2$ have been
  replaced by true and $t_3$ has been replaced by if false then false else
  false.

On page 15 is the definition for relataion

  An n-place relation on a collection of sets $S_1, S_2,..., S_n$ is a
  set $R\subseteq  S_1\times\;S_2\;\times\;...\;\times\;S_n$ of tuples
  of elements from $S_1$ through $S_n$. We say that the elements $s_1\in
> S_1$ thorugh $s_n\in S_n$ are related by $R$ if $(s_1,...,s_n)$ is an
  element or $R$.

On page 36 is the definition for one-step evaluation relation ($\rightarrow $)

  The one-step evaluation relation $\rightarrow $ is the smallest
  binary relation on terms satisfying the three rules of Figure 3-1.
  When the pair $(t,t')$ is in the evaluation relation,  we say that "the
  evaluation statement (or judgment) $t \rightarrow t'$ is derivable."

On page 34 are the three rules from Figure 3-1

E-IFTRUE

  \begin{equation}if\;true\;then\;t_2\;else\;t_3\;\rightarrow\;t_2\end{equation}

E-IFFALSE

  \begin{equation}if\;false\;then\;t_2\;else\;t_3\;\rightarrow\;t_2\end{equation}

E-IF

  \begin{equation}\frac{t_1\rightarrow\;t_1'}{if\;t_1\;then\;t_2\;else\;t_3\;\rightarrow\;if\;t_1'\;then\;t_2\;else\;t_3}\end{equation}

Can someone explain this definition and give an example for parts of the defintion.
1. The conclusion is in the relation.
2. One of the premises is not.

Note: I am aware that there is a forum dedicated to questions for the book here.

Note: You can use Google Scholar to see more of the details to this question in context.

EDIT

To connect some of the dots about my comment regarding unification and term rewriting.

When I saw

$$(A\rightarrow B)\equiv (\neg A \vee B)$$

it reminded me of Horn claues from Prolog, that along with the example then connected with my understanding of term rewriting. Having the book "Term Rewriting and All That" (WorldCat) by Franz Baader and Tobias Nipkow, I quickly looked up satisfiability and found satisfiable on page 58. This is actually the start of whole chapter on Equational Problems; but it also covers unification. At that point I realized that the definition was dealing with Satisfiability and from there is was a topic I was already familiar. What threw me was the way Benjamin defined it. He used a very precise definition right up front in a manner I didn't associate with my knowledge.

If you work through the code as I am and understand logic programming, then the definition makes perfect sense.

One way of reading the definition of satisfied that might help is to change

  A rule is satisfied by a relation if, for each instance of the rule, either the conclusion is in the relation or one of the premises is not.

to the logically equivalent statement

  A rule is satisfied by a relation if, for each instance of the rule, if all the premises are in the relation, then the conclusion is in the relation.

Thus if  the rule says, for instance,

$$
\dfrac{A \to B \quad B\to C}
{A\to C}
$$

Then binary relation $R$ satisfies this rule whenever for each instance of the rule, such as

$$
\dfrac{a \to b \quad b\to c}
{a\to c}
$$

if $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$.

Another way of stating this is that $R$ is closed by the rule (though this probably doesn't make it clearer).

Now let's return to the original statement. What

  A rule is satisfied by a relation if, for each instance of the rule, either the conclusion is in the relation or one of the premises is not.

is saying is that is it okay to have $(a,c)$ in the relation without the premises, but if all of the premises are in the relation, then  $(a,c)$ must be. That is, it is okay to have not all of the premises in the relation, without imposing any additional constraint.

Personally, I think that thinking about this definition in terms of an implication is simpler, so I help this explanation helps.


If $L$ is context-free and $R$ is regular, then $L / R$ is context-free? I'm am stuck solving the next exercise:

Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-free.

I know that there should exist a PDA that accepts $L$ and a DFA that accepts $R$. I'm now trying to combine these automata to a PDA that accepts the right quotient. If I can build that I proved that $L/R$ is context-free. But I'm stuck building this PDA.

This is how far I've made it:

  In the combined PDA the states are a cartesian product of the states of the seperate automata. And the edges are the edges of the DFA but only the ones for which in the future a final state of the original PDA of L can be reached. But don't know how to write it down formally.

Here is a hint.

You need your machine to initially accept part of a word from $L$, consuming the tape as it goes. Then, without consuming anything, you need to find some word from $R$ that will push the machine into a final state. The chosen word from $R$ plays the role of the input word for the second half of the computation.

Clearly, non-determinism will have a role, as will the product between the two machines. The trick in formalising this is adjusting the product to deal with the fact that the input comes from $R$ not from the input.


Using coloring optimization or coloring decision to solve coloring search How can you show that coloring search can be solved by making a polynomial number of calls to the solution for coloring optimization or coloring decision? (Coloring search is the algorithm to color the vertices of a graph such that adjacent vertices have a different color.)

I wasn't sure how to solve it, but here is what I attempted (I chose to use coloring optimization):

  Coloring search can be solved by calling coloring optimization and finding the value $m$, which is the amount of colors needed so
  that no two adjacent vertices have the same color. Once $m$ is found,
  coloring search can color the vertices of the graph by rotating through the $m$
  different colors for each vertex.

Am I on the right track?

Given a graph $G$, we want to do two things:

Find the smallest $k$ such that $G$ is $k$-colourable,
Given such a $k$, find a colouring of $G$ with $k$ colours.

If we have an oracle for the decision version of the colouring problem, we can do both.

For the first part we can perform a search to find the optimal $k$. Even the naive approach here is okay, we can just sequentially ask if $G$ is $k$-colourable for $k=1,2,\ldots,n$. Then we make at most $n$ calls to the oracle. Of course we can perform a binary search and cut this down to $\log n$ calls. (Note that this is also how we solve the optimization version with the decision version).

Then given that we've worked out what $k$ is optimal, we can find a $k$-colouring of $G$ using the decision oracle. The only wrinkle is that the oracle doesn't take partial colourings, so we need a way of encoding in the graph that a particular vertex has been coloured a particular colour.

To do this we actually use the oracle on an auxilliary graph, which we will call $G^{+}$, that is $G$ plus a $K_{k}$ with some additional edges. Of course the $K_{k}$ needs exactly $k$ colours, so we can use its vertices to indicate which colours are available for a vertex. Let the vertices $\{k_{1},\ldots,k_{k}\}$ of the $K_{k}$ correspond to the colours $\{c_{1},\ldots,c_{k}\}$. Then we will indicate that a vertex $v$ in $G$ cannot be coloured with colour $c_{i}$ by making it adjacent to $k_{i}$. Furthermore if we colour a vertex with colour $c_{j}$ we will make it adjacent to every $k_{i}$ with $i\neq j$ (and not adjacent to $k_{j}$).

Then we repeatedly do the following:

Pick an 'uncoloured' vertex $v \in V(G)$.
For every vertex $u \in N(v)$, if $u$ has been coloured, then there is one $k_{i}$ such that $uk_{i} \notin E(G)$. Add the edge $vk_{i}$ to $E$.
For the remaining vertices $k_{j}$ such that $vk_{j}$ is not yet in $E$, we add all other edges between $v$ and the $K_{k}$ and ask the oracle if the new graph is $k$-colourable. If it is, we keep this graph and move on to the next vertex, if the answer is No, we undo step 3 and try with the next $k_{j}$.

Note that as $G$ is $k$-colourable, there is some $k_{j}$ that step three will work with. Then when we have processed every vertex, each vertex in $G$ is not adjacent to exactly one vertex in the $K_{k}$, this indicates which colour the vertex can be coloured with to obtain the colouring. From step 2, we see that this cannot be the same colour as any of its neighbours.

At step three we make at most $k$ calls to the oracle, and we do this for each vertex in $G$, so in total we make at most $(k+1)n$ calls to the oracle (including the search for $k$).


Decidability of the language of all TMs whose languages reduce to a fixed decidable language Given that $L_1$ is decidable language. That means it has a TM  ($M_1$) decider.
Now we consider a language, $L_p$;

  $$L_p = \left \{ \langle M \rangle \mid L(M) \text{ is reducible to } L(M_1) \right \}$$

$L_p$ consists of all the encodings of the Turing machines whose language is reducible to $L_1$.

What can we say about $L_p$, Or, $L_p$ is decidable or undecidable ?

I understand if we assume to have a decider for $L_p$ and using this as component if we can construct a TM which decides a problem $P$. If $P$ is already known as undecidable then we can conclude that out assumed decider for $L_p$ does not exist.

How to come up with this reduction idea for $L_p$ ?

Let $L_1$ be a decidable language. Consider the class of Turing-recognizable languages

$$\mathcal{S} = \{ L \mid L \mbox{ reduces to } L_1 \}$$

This class is non-trivial in the sense of Rice's theorem, as no recognizable but undecidable language can be an element of $\mathcal{S}$, and since we obviously have that $L_1 \in \mathcal{S}$.

You can now apply Rice's theorem to get that $L_p$ is undecidable.


How to find unambiguous grammar for palindromes I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc.

S -> a S a
   | b S b
   | a
   | b
   | ε

Is there a way to convert this to an unambiguous grammar? Or is there another solution?

First, I believe you are looking for a different word than 'unambiguous'.  A grammar is ambiguous if some string in its language has two or more derivations; I'm sure that a palindromic string must have only one derivation in this grammar.

I suspect the word you really mean is 'deterministic'.  YACC must declare that this grammar has 'shift-reduce' conflicts - e.g if the next letter is 'a' one cannot decide if the first, third, or fourth rule is to be applied.  This is an inherent problem with palindromic languages; the core problem is that there is no way to know, during a left-to-right scan of the input string, exactly where the midpoint of the string is.

If you are permitted to change the language, you could add a new letter 'c' and use it to always (and ONLY) mark the center of each string.


Not convincing claim for Master Theorem Case 3 In a practice exam given in class, we were asked to solve the following recurrence

$$T(n) = 2T(n/4) + \frac{n}{\log n}$$

The given solution claims that this falls in the third case of the Master Theorem and starts with the following claim:

$$f(n) = n / \log n = \Omega (n^{1/2 + \epsilon}) \ \textrm{for any} \ 0 < \epsilon < 1/2$$

Is there a quick way to show this holds. Seeing the $\log n$ is the reason why I am doubting this claim.

Yes, this holds since $\log n = O(n^\epsilon)$ for any $\epsilon > 0$. You can prove this formally as follows. We will show that $\log n = o(n^{1/k})$ for all $k > 0$, or equivalently, that $\log^k n = o(n)$ for all $k \geq 0$. The proof is by induction. The base case $k = 0$, is clear. For the induction step, L'Hôpital's rule gives
$$
\lim_{n\to\infty} \frac{\log^k n}{n} = \lim_{n\to\infty} \frac{k\log^{k-1} n}{n} = 0.
$$


ALL_{REGEX} in PSPACE algorithm $ALL_{REGEX}$ is the computational problem of determining for regular expression x if $L(x) = \Sigma^*$.  In a proof for $ALL_{REGEX} \in PSPACE$, the following non-deterministic turing machine $M(R)$ on regular expression $R$ is given

Convert R to an NFA $N = (Q,\Sigma,\delta,S,F)$;   $K = S$;

While $K \cap F \neq \emptyset$

Non-deterministically guess a character $a \in \Sigma$
S' = Compute the new set of states from character $a$ and states $K$
K = S'

The proof states that iff $M$ does not halt, then $L(R) = \Sigma^*$.  Suppose we have $\Sigma = \{a,b\}$ and R = a*. Why doesn't this machine halt?  Won't there be a single path of guesses (namely, a*) that goes on forever, implying the whole machine does as well?

The algorithm goes prove that after $2^{|Q|}$ steps, we know the language must be $\Sigma^*$, so we accept instead of looping.  I understand the intuition of the algorithm and how it would be implemented deterministically  , but I'm confused as to how the algorithm above works when the NTM formalism accepts if any path accepts and it is making me question my understanding of NTMs.

The idea is that if a DFA having $n$ states isn't universal (doesn't accept $\Sigma^*$) then there must be some word of length at most $n$ which it doesn't accept. The proof is similar to the proof of the pumping lemma: take any word not accepted by the DFA, and trace its route through the DFA. You can always shorten it to a word which ends up in the same state, and additionally all states encountered are distinct. Since there are only $n$ distinct states, this finished up the proof.

An NFA having $n$ states is equivalent, via the powerset construction, to a DFA having $2^n$ states. Therefore if it is not universal then it rejects some word of length at most $2^n$. The non-deterministic algorithm you describe guesses such a word and verifies that it is indeed rejected by the NFA. Since NPSPACE=PSPACE, we can convert this into a deterministic algorithm (in fact, one using space $O(n^2)$).


Finding an interval in a binary search tree that contains a point I have a binary search tree where nodes are non-overlapping intervals. I'm given a point, and I need to determine which interval the point belongs to (if any). This is easy to do because I can compare against the low and high of each interval and descend either left, right, or exit.

Is it possible to only compare against the low, or the high, or some kind of median to reduce the number of comparisons in the average case? I know the optimal lower bound would be O(lg n) but in many cases the max of a predecessor is very close to the min of a node, which seems redundant.

I'm wondering if there is a way to branch more aggressively at first and make small adjustments along the way. Potentially determining the next step based on which direction we branched previously.

I could not find any literature on this. Interval trees don't quite match this setup and almost all other resources relate to overlapping intervals.

What would be an optimal algorithm to find an interval?

You can't find a better algorithm for your problem using comparisons, because a lower bound of $\Omega(\log n)$ can be proven for these setings (proof below).

What you can do is some minor optimizations; if each node in your tree saves the end of the rightmost segment and the beginning of the leftmost segment, by adding $2$ comparisons to each query, you can immediately decide $x$ is outside any segments when it becomes out of bounds. These comparisons do not increase your overall complexity, but they also don't improve it.

Let us consider the data as $n$ disjoint line segments. Or to be formal, $I = \{(i_1,j_1),\dots (i_n,j_n) \} $

Suppose given a query $x$ we wish to determine in which interval $(i_t,j_t)$ our query $x$ is located at, or whether no $ 0 \leq k \leq n$ exists s.t $x \in (i_k,j_k)$.

Since your algorithm performs comparisons, it can be represented as a decision tree; a node represents a comparison $x : q$; the left child are the comparisons you would make if $x < q$ and the right child the same for $x>q$.

Note that since in your case, your values $q$ are medians, if $x=q$ you can finish your algorithm (and $x$ belongs to that segment).

Let's denote the decision tree $T$.

Some observations about $T$:

$\bullet$ $T$ MUST have at least $n+1$ unique leaves; one for each segment $(i_t, j_t)$ and one that represents the decision that $x$ belongs to no segment.

$\bullet$ Each inner node $v$ of $T$ has three children ($=, <, >)$

$\bullet$ A trenary tree of height $h$ has at most $3^h$ leaves;
$3^h \geq n+1 \rightarrow h \geq \log_3{(n+1)} \geq \log_3{n}$

Since $\log_3{n} = \Omega(\log n)$, we proved a lower bound for comparison based search, and thus any search as described by your algorithm must perform at least $\log n$ queries.


Why is crossing paths bad in Traveling Salesman? I'm learning about Traveling Salesman in an online course (sorry I can't share the link it's paid only) and the first step to solving it then just state "as a heuristic we avoid crossed paths" and never really explained why. Why are crossed paths bad in traveling salesman?

The statement is for Euclidean TSP only, and as you mention yourself, it is only used as a heuristic.
But try to create an example yourself and see what happens when you have crossing links as part of your solution:

From Urban OR:
Property 1: The optimum traveling salesman tour does not intersect itself.


Is there any correspondence between SUM type in type theory and arithmetical summation? Is there any correspondence between the coproduct(sum) type in type theory and arithmetical summation?

For example what does 3+4 or x+6 mean in type theory?

The arithmetic notation in type theory is motivated by the behaviour on sets, where the disjoint union $A + B$ has $|A| + |B|$ elements; the cartesian product has $|A| \times |B|$ elements; and the set of functions $B^A$ has $|B|^{|A|}$ elements. Sum, product and function types satisfy many of the usual identities you expect of arithmetic (although typically up to isomorphism, rather than equality).

The paper Objects of Categories as Complex Numbers by Marcelo Fiore and Tom Leinster explores this in some detail, though it helps to have a little experience with algebra or category theory.

Sometimes a natural number $n$ will denote a type with exactly $n$ terms in any context (analogous to a set with $n$ elements). In this setting, $3 + 4 \cong 7$ as types. $x + 6$ isn't well-formed without placing $x$ in some context.


VC dimension and optimal mistake bound I have a question regarding optimal mistake bound for learning algorithm

There is a famous fact that $VC(C) \leq Opt(C)$,

where $C$ - set of learning concepts,

VC(C) - VC dimension of C,

$Opt(C)$ - the smallest mistake bound (of the best learning algorithm) on the hardest learning concept $c \in C$ .

I don't understand why $VC(C) \leq Opt(C)$, in my opinion the notion of best algorithm $A$ is so vague that you cannot for sure say that $VC(C)$ is not more than $Opt(C)$

For example,  $VC(line\ on\ the\ plane)$=3 , it means that $Opt(C) \geq 3$ in words it means for the hardest concept $c \in C$ (represented as a line on the plane) the number of mistakes of the best learning algorithm is more than 3.

Why the above fact is so strong?

So this result pertains to the online mistake bound framework. I found a proof here in Shai Shalev-Shwartz's lecture notes. I'll give a rough sketch of it here for the sake of keeping things self contained.

One way to think of online learning is a game between the learner and an adversarial environment. The environment produces an example $x_t$ at time $t$. The learner then outputs a label $\hat{y}_t \in \{-1,1\}$. Finally the environment outputs the true label of $y_t$ and the learner suffers a mistake if $\hat{y}_t \neq y_t$.

The thing to note for the above bound is that it doesn't matter if the environment switches the true hypothesis mid-game, provided the new hypothesis is consistent with all previous labelings. This is because it would be the same as selecting the new hypothesis in the first place.

Assume the learner is trying to learn some some finite hypothesis class $C$ over an instance space $\mathcal{X}$ with $\text{VCdim}(C) = d$. Let $X = \{x_1, \cdots, x_d\} \subseteq \mathcal{X}$ be a shattered set. At any time $1 \le t \le d$ the environment reveals $x_t$ and the learner outputs $\hat{y}_t$. The environment then selects a new hypothesis $c \in C$ such that $c(x_t) = -\hat{y}_t$ and $c(x_i) = y_i$ for $1 \le i \le t$. There will always exist such a hypothesis $c \in C$ since $X$ is shattered by $C$. So the learner makes at least $d$ mistakes. Since this argument was independent of the learning algorithm it follows that
$$
\begin{align*}
\text{VCdim}(C) &\le \text{Opt}(C).
\end{align*}
$$


How can we know if a Turing machine halts, given that it writes to finite memory? I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine
writes to an arbitrary amount of memory, and false if it writes to a finite amount of memory cells. I am now thinking, can we somehow deduce if the machine halts based on if it writes to a finite amount of memory cells?

Link to related post: Turing machines: can a machine write to a finite number of memory cells, but not halt?

To answer your question, if you know that a Turing machine uses only $M$ cells, then you can tell whether it halts by running it for enough steps. If the Turing machine uses only $M$ cells, then it can be in one of $N$ configurations, where $N$ depends on $M$, the number of states, and the alphabet size. If you run it for $N$ steps and it doesn't halt, then altogether it will have gone through $N+1$ configurations, two of which must be equal, hence it is in an infinite loop and won't halt.

However, your actual question is different. You want to show that the following set is undecidable:
$$
L = \{ \langle M \rangle \colon M \text{ uses a finite amount of memory} \}.
$$
We will do so by reduction from the halting problem. Given a Turing machine $M$, construct a new Turing machine $M'$ which acts as follows:

for i from 1 to infinity:
    simulate M for one step, and halt if M halts
    move the head i steps to the right
    move the head 2i steps to the left
    move the head i steps to the right
end for

If $M$ halts, then $M'$ also halts, and in particular uses a finite amount of memory. Otherwise, $M'$ will necessarily use an infinite amount of memory.


A schedule is not conflict-serializable. Is it serializable? While reading this solved quiz on concurrency control, I got stuck on exercise 2, which reads as follows:

  2) Consider the following schedule:

  S: r1(X), w2(X), r3(X), r1(Y), w2(Z), r3(Y), w3(Z), w1(Y)

  (a) (2 points) Draw the precedence graph.

  (b) (1 point) Is S conflict serializable?

  No.

After reading that S is not conflict-serializable, my question is: can we say that S is serializable? Any suggestions?

Thanks to anyone who help me.

A schedule is considered serializable if it is equivalent to a serial one. The conflict graph that appears on the answer to item (a) is proof that the schedule is not conflict-serializable, and it is also not view-serializable, because there is still a cycle between $T_1$ and $T_3$, when considering just the history of the data they visualize. That means the schedule cannot be considered serializable at all.

Conflict-serializability is stronger than view-serializability. It is the criterion used for the implementation of most schedulers, and that is why the quiz emphasizes this point.


Saving time finding a result by guessing first? I am currently taking a graduate course about Image Processing in electrical engineering and while this question doesn't particularly relate to the class itself but rather some concepts in the algorithms we utilize.

One of the algorithms that we utilized was called, "Image Correlation" in order to find a "match" from using a segment of the picture and almost convolving it into the main picture. Below is an example of how this algorithm is implemented to find the correlation in the picture.

From Digital Image Processing by Rafael C. Gonzalez and Richard E. Woods...

My question is, instead of starting from the top left, why can't we estimate where the result is first before implementing the algorithm? Wouldn't it save time to know where you would like to start the process?

Yes, it absolutely would save time.  You are quite right, and you are onto a good idea -- that idea is frequently used to speed up image matching.

The core challenge is: how do we come up with an estimate where the result might be, more efficiently than using the correlation algorithm?  It's not obvious how to do that, short of doing a correlation (which wouldn't actually save any time).

Fortunately, there are ways to do that.  A standard approach is to use an image pyramid.  You downscale the image to a lower resolution, then look for a downscaled version of the T in that smaller image (again using correlation).  Because the image is smaller, the correlation calculation goes faster.  Then that gives you a pretty good estimate where the T is, and instead of searching the entire full-resolution image, you only need to check a small portion of the full-resolution image.  If you find multiple matches in the downscaled image, you can check all of them on the full-resolution image.


What becomes of context-sensitive grammars if $\epsilon$ productions are allowed? The original formulation of the 3 restricted grammar types of Chomsky all included the restriction that the right-hand side of a replacement cannot be $\epsilon$ (non-contracting). This, however, can be (and usually is) lifted for regular and context-free grammars (i.e. they are allowed to have productions of the form $X \to \epsilon$) without altering the class of languages generated.
The rule, however, remains for context-sensitive grammars.
My question is, given a grammar with productions $\alpha X \beta \to \alpha \xi \beta$ where $\alpha, \beta, \xi\in (N \cup T)^*$ (i.e. a context-sensitive grammar with $\epsilon$-rules), what class of languages does that describe? The recursively enumerable ones (same as unrestricted grammars) or something else?

It can be shown that the context sensitive grammars you describe are equivalent to just asking for productions $\alpha \to \beta$ with $\lvert \alpha \rvert \le \lvert \beta \rvert$. So allowing productions $A \to \varepsilon$ just removes the restriction on lengths, and you have landed on unrestricted grammars.


One-way function is not injective when it is in NP Let us $\Sigma = \{0,1\}$ and $f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that $\exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \rvert ^ k$. Thus, we can say that the function $f$ is one-way function.

We have language $L = \{ w \; | \; \exists z \in \Sigma^*, w = f(z)\}$. The question is, how to prove that $f$ is not injective if $L \in NP \setminus UP$, where $UP$ is the class of unambiguous TM.

It is clear, that if $L \in NP \setminus UP$ then exists NTM which decides this language and may exist at least one acceptable path for $w \in L$.

Suppose that $f$ is injective. Consider the following nondeterministic machine for $L$: on input $w$, the machine guesses $z$ of size between $|w|^{1/k}$ and $|w|^k$, and verifies that $f(z) = w$. Since $f$ is injective, if $w \in L$ then there is exactly one witness $z$, and so $L \in \mathsf{UP}$.

Since $L$ is always in $\mathsf{NP}$ (using the very same machine), the contrapositive is exactly the statement you're after.


Does closure under union and concatenation imply closure under Kleene star? For decidable languages (or a particular subset of decidable languages, e.g., regular, context free) does closure under Kleene star follow from the proof of closure under union and concatenation? The only thing that the latter seems not able to produce is an empty string.

You haven't stated whether you're interested in finite or infinite union, though as you mention, it doesn't really matter due to problem with the empty string. However, instead of giving the answer, let me explain how to answer such questions.

Showing that a language class is closed under operation $O$ given that it is closed under operations $O_1,\ldots,O_m$. You show how to simulate $O$ using $O_1,\ldots,O_m$. For example, suppose that a language class is closed under union and complement. Then it is also closed under intersection, since $A \cap B = \overline{\overline{A} \cup \overline{B}}$.

Showing that if a language class is closed under $O_1,\ldots,O_m$ then it is not necessarily closed under $O$. You given a language class which is closed under $O_1,\ldots,O_m$ but not under $O$. For example, let us show that a language class which is closed under finite union isn't necessarily closed under infinite union. Consider the language class consisting of all finite languages. This class is closed under finite union but not under infinite union.

Given this information, you should be able to answer your question on your own.


If i use other peoples code for my final year project does that come under Plagiarism? I want to make a facial recognition project but my coding ability is very limited so I am going to be relying on other peoples code but if i use their code even if i change the variables and make different functions to add their code under would that still be considered plagerism ?

You should clearly talk to your supervisor or advisor about this, however there are some general principles you are often overlooked by students when doing their final year projects in computing disciplines.
Firstly you should be clear what plagiarism really is and fully understand it. Plagiarism is presenting someone else's work as your own to gain credit for it as if you had created it yourself. However, we all use the work of others. We read books, we read tutorials on the Internet, we read things on Stack Exchange. We should, if doing this properly be citing the work of others properly so it is clear when ideas, code, formulas and other elements of our work are attributable to others. If we have properly attributed the work, then those who assess you can clearly see which parts are yours and which are not. Then no plagiarism is involved. A good student will be reading much and citing much and will be including the work of others. It is just they cite it well. A weak student may often be someone who has read little, used little, cites nothing and hands in little. A really bad student would just hand in someone else's stuff. Hopefully the boundaries are a little clearer.
The next element, particularly for Computer based projects, is to realise that we are using the work of others and including it in our project all the time. You will be using an operating system, you will be using a language invented by someone else a compiler built by someone else that interacts with run-time libraries that were supplied with it. Yet, despite doing this all the time students worry little about these elements that were included in their submitted project. Where is the dividing line between the bits that are incorporated in your work and what you did? Who can tell? This is why citing everything you used is important.
The only way to really make the whole project fully self-created, you would in extremis have to start with clean sand, make your own processor chips to your own design, write the operating system and compilers for them to your own design and then use that as a platform for your project. But, of course, that is totally preposterous.
As Isaac Newton is credited with saying, we can see so far because we are standing on the shoulders of giants. You should do the same. Select the best components and use your skill and education to assemble them into the best creation that is your project. All good things are just made from components that are acknowledged and this is not plagiarism. The skill is in using the right components assembled in the right way.
How many of those things should be hand-crafted by you and how many are imported is the guidance you get from your project supervisor.


Compute cache miss rate for the given code Problem Description:

We consider a 128-byte data cache that is 2-way associative ($E=2$) and can hold 4 doubles in every cache line. A double is assumed to require 8 bytes.

For the below code we assume a cold cache. Further, we consider an array A of 32 doubles that are cache aligned (that is, $A[0]$ is loaded into the first slot of a cache line in the first set). All other variables are held in registers. The code is parameterized by positive integers $m$ and $n$ that satisfy $m*n = 32$ (i.e., if you know one you know the other). Recall that the miss rate is defined as $\frac{\text{number of misses}}{\text{number of accesses}}.$

// Code:
float A[32], t = 0;
for(int i = 0; i < m; i++)
  for(int j = 0; j < n; j++)
      t += A[j*m + i];

Problem:
Determine the miss rate for when $m=1,2$ and $16.$

My Attempt:

When $m=1$ we access the elements,
$$A[0],A[1],A[2],\cdots,A[31]$$
and since each block in the cache can hold $2$ doubles, this means that for every miss we get one hit and so the miss rate is $1/2.$

When $m=2$ we access the elements,
$$A[0],A[2],A[4],\cdots,A[30].$$
Here we first miss $A[0]$ but then we load the block with $(A[0],A[1]).$ However, this does not help since we need to access $A[2]$ and therefore we miss every time and thus the miss rate is $1.$

When $m=16$ we access the elements,
$$A[0],A[1],A[2],\cdots,A[31].$$
And so like before this should have a miss rate of $1/2.$

However, the answers are:
$$m=1, \text{miss rate} = 1/4$$
$$m=2, \text{miss rate} = 1/2$$
$$m=16, \text{miss rate} = 1/4.$$

I am not sure how to obtain these answers and so any help will be much appreciated.

As the cache is 4 doubles, for m=1, after accessing A[0], there are in the cache A[0]...A[3]. So next access A[1] is a hit and it is the same for A[2] and A[3]. Only access A[4] will be a miss. Hence miss rate is 0.25

For m=2, After accessing A[0], the cache holds the same line. Next access is A[2] which is a hit, and A[4] is a miss and so on. So miss rate is 0.5. Note that total cache size is 8 doubles. So when accessing A[8], cache line 0 is cleared and when A[1] will be accessed on later iterations, it will be again a miss.

For m=16 and n=2, one needs to look closely at the access patterns. Also do not forget that the cache is associative with two lines.

iteration 1 i=0, j=0 ->       A[0]  miss in line 0
iteration 2 i=0, j=1 16j+i -> A[16] miss in line 1
iteration 3 i=1, j=0 16j+i -> A[1]  hit in line 0 (because cache is 2 ways associative)
iteration 4 i=1, j=1 16j+i -> A[17] hit in line 1

and all access will be hits until iteration 8 (i=4, j=0). In that case, we access  A[4] that isn't in any cache and we restart a new cycle. So we have 2 misses for 8 iteations and miss rate is 0.25


Karatsuba Multiplication with n/3 division of large number I was studying Karatsuba multiplication where the complexity is reduced as compared to classical algorithm by splitting each number into two parts.

Now I'm trying to understand how the multiplication will take place when a number is divided into three parts instead of two.

I tried to solve the math but only came up with more number of multiplications than in Karatsuba.

Can someone help me out with this problem?

The algorithm you are looking for seems to be the Toom-3 algorithm.


Is every subset of a decidable set, also decidable? Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable?

I believe it would be true because all the subsets of B should also be decidable making A decidable. I'm not sure if my thought process is right or if there's a easier more intuitive way to explain this.

This is a common misconception: complexity is not a measure of size. That is, it's not that "bigger" language are harder.
Intuitively, a language becomes harder when it's harder to describe it (TMs being a form of description). For example, as @Yuval Filmus points out in the comments, the language whose description is "everything" is very easy to decide.

Similarly, the converse is not true - that is, smaller languages are not "harder" as well. For example, the language "nothing" is also easily decidable.

So the containment relation does not preserve hardness. Indeed - that's why we use the relatively complicated notion of reductions between languages, rather than showing containment.

So the simple answer to your question is that it's false, and an example, as in the comments, is $\Sigma^*$, which is decidable, but contains an undecidable language (indeed, every undecidable language).


Negative lookahead in LR parsing algorithm Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.):

Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ;

It's an ordinary rule, except that it has a restriction: a phrase produced with this rule cannot begin with Terminal1, ..., TerminalN. (Surely, this rule can be replaced with a set of usual rules, but it will result in a bigger grammar). This can be useful for resolving conflicts.

The question is, is there a modification of LR table construction algorithm that accepts such restrictions? It seems to me that such a modification is possible (like precedence relations).

Surely, it can be checked in runtime, but I mean compile-time check (a check which is performed while building parsing table, like %prec, %left, %right and %nonassoc directives in yacc-compartible generators.)

Yes, there is such a modification. A negative lookahead assertion at the END of a production means taking special care in computing FOLLOW sets. Before a terminal makes no sense. Before a nonterminal is a bit more complicated: the optimal strategy depends on the context. Special care while generating the shift relationship is part of the answer. On balance, this is an algorithm design problem more than a theoretical computer science problem.


termination of two concurrent threads with shared variables We're in a shared memory concurrency model where all reads and writes to integer variables are atomic.

do: $S_1$ in parallel with: $S_2$   means to execute $S_1$ and $S_2$ in separate threads, concurrently.
atomically($E$)   means to evaluate $E$ atomically, i.e. all other threads are stopped during the execution of $E$.

Consider the following program:

x = 0; y = 4
do:                 # thread T1
    while x != y:
        x = x + 1; y = y - 1
in parallel with:   # thread T2
    while not atomically (x == y): pass
    x = 0; y = 2

Does the program always terminate? When it does terminate, what are the possible values for x and y?

 Acknowledgement: this is a light rephrasing of exercise 2.19 in Foundations of Multithreaded, Parallel, and Distributed Programming by Gregory R. Andrews.

This trace is possible, in two separate threads T1 and T2. $state$ is $(x,y)$.

T1: ... $state=(0, 4)$
T1: x = x + 1; y = y - 1 $~~state=(1, 3)$
T1: x = x + 1; y = y - 1 $~~state=(2, 2)$
T2: x == y evaluates to true, pass and then x = 0; $~~state=(0, 2)$
T1: x != y evaluates to true, x = x + 1; y = y - 1 $~~state=(1, 1)$
T2: y = 2 $~~state=(1, 2)$
T1: x != y evaluates to true, x = x + 1; y = y - 1 $~~state=(2, 1)$
$state=(3, 0)$
$state=(4, -1)$
...

(Note that it works even if x = expr; is atomic)

There are other possible interleavings. The point $(2,2)$ is common to all of them, where T1 has pending (logically) atomic instructions:

T1: push x; push y; eq ? stop : push(x + 1); pop@x; push(y - 1); pop@y; repeat
T2: (x != y) ? repeat : x = 0; y = 2;

In the first case, T1 proceeds to stop and then T2 can only proceed and the final state is $(0,2)$.

If T2 finally skips the repeat and (T1:push x) is run before (T2:x = 0) then T1 will stop looping and the same final state is reached.

If T2 finally skips the repeat and (T1:push x) is run after (T2:x = 0) then T2 can proceed after the stop independently of (T1:y = 2).

state = (0, 2)
T1: push(x + 1); pop@x; push(y - 1); pop@y; ...
T2: y = 2;

If T2 is run now then it will loop as above, so T1 proceeds:

state = (1, 2); stack = 1
T1: pop@y; ...
T2: y = 2;

If T2 is run now, this will go to the final state $(1,1)$. Otherwise:

state = (1, 1)
T1: push x; push y; eq ? stop : push(x + 1); pop@x; push(y + 1); pop@y; repeat
T2: y = 2;

If T2 does not act before push y, this will stop and go to the state $(1,2)$. If it does, then the state is $(1, 2)$ and this will loop into $(2,1)$, $(3,0)$, ...

To sum up the possible final states are $(0,2)$, $(1,1)$, $(1,2)$. I don't think it was worth the effort though, since I probably made mistakes.


Why does Union-Find have time complexity O(N + M lg* N) with the "log star N"? The time complexity of Weighted Union-Find with Path Compression, for M union-find ops and N objects is said to be

$$ O(N + M \lg^*N) $$

and the $ lg^*N $ is "log star N" and is iterated logarithm. It can be almost taken to be a constant, as $ lg^*2^{65536} $ is only equal to 5. Why is it $ lg^*N $ and what kind of operations / algorithm typical can produce $ lg^*N $?

Check out the analysis of path compression in Union-Find by Seidel and Sharir "Top-Down Analysis of Path Compression", SIAM Journal of Computing 34:3 (2005), pp 515-525. Somewhat heavy going, the result you cite is a step on the way to the best-possible bound by their method.


Do we know something about this refutation method for SAT? Let we have a formula $\varphi(x_1,x_2...x_k)$. Now we apply a refutation method: $\varphi(x_1,x_2...x_k)\Leftrightarrow(\varphi(x_1=1,x_2...x_k)\lor\varphi(x_1=0,x_2...x_k))$. Latter formula seems to be longer, but no, good algorithm reduces number of literal occurences. On each step we can modify the formula without changing it's solution space. This gives much more power than resolution has. For example, Tseytin contradiction can be refuted this way in linear time using deterministic algorithm.

But what is the worst case for this algorithm?

Example:

$$\varphi=(x\lor y\lor z)(x\lor\overline y\lor t)(x\lor\overline z\lor\overline v)(\overline x\lor\overline t\lor\overline v)(\overline x\lor\overline z\lor v)(y\lor\overline z\lor v)(\overline y\lor\overline t\lor\overline v)\land(\overline y\lor z\lor t)$$

Step 1. Getting rid of $t$.

Putting $t$. Affected remaining clauses: $(\overline x\lor\overline v)(\overline y\lor\overline v)$. Reducing them: $\overline v\lor \overline x\overline y$.

Putting $\overline t$. Affected remaining clauses: $(x\lor\overline y)(\overline y\lor z)$. Reducing them: $\overline y\lor xz$.

Combining them using OR: $\overline v\lor\overline y\lor xz$.

Step 2. Getting rid of $y$.

Putting $y$. Affected subformula: $\overline v\lor xz$.

Putting $\overline y$. Affected subformula: $(x\lor z)(\overline z\lor v)$.

Combining them: $\overline v\lor xz\lor(x\lor z)(\overline z\lor v)$. Reduction: $x\lor z\lor\overline v$.

Step 3. Getting rid of $x$.

Putting $x$. Affected subformula: $\overline z\lor v$.

Putting $\overline x$. Affected subformula: $(z\lor \overline v)(\overline z\lor\overline v)$. Reduction: $\overline v$.

Combining them: $1$.

All clauses are covered, formula is satisfiable.

But what would be the hardest case for this and is it possible to break exponential bound using this method? Is this method general enough (we can modify formula by any ways until solution space is unchanged and this is checkable in polynomial time) that saying it requires superpolynomial time (for unsatisfiable formula) will imply $\mathsf{NP\ne coNP}$?

Note that for unsatisfiable formula it's possible to non-deterministically ignore some clauses if refutation can be done without their usage.

As far as I can tell the earliest mention of the procedure you outline, later described in the literature as variable elimination by clause distribution, was in the paper "ZRes: The old Davis-Putnam procedure meets ZBDD" by Philippe Chatalic and Laurent Simon.  The procedure was described again, along with other formula simplification techniques, in "Effective Preprocessing in SAT through Variable and Clause Elimination" by Niklas Eén and Armin Biere.

The procedure was shown to be a workable way to improve SAT solver performance if care is taken to minimize clause growth as the implicants of removed terms are distributed, or to use data structures that efficiently manage large clause sets.


Lambda Calculus: How do evaluation contexts "work" In the pure lambda calculus, we have the inductively defined set of terms (the grammar):
$$e::= x \mid \lambda x . e \mid e_1 e_2$$

Under the call-by-value evaluation strategy, we have the inference rules for beta-reduction and rules on how to evaluate applications (congruence rules). I am trying to understand how evaluation contexts can replace the congruence rules without actually changing the syntax of the language. Without evaluation contexts, we have the following:

$$
\frac{e_1 \rightarrow e_1'}{e_1e_2 \rightarrow e_1'e_2}
$$
and
$$
\frac{e_2 \rightarrow e_2'}{ve_2 \rightarrow ve_2'}.
$$

This makes sense, since if we have an instance of an expression $t = (\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w$, it is clear that it is of the form $e_1e_2 \rightarrow e_1'e_2$ and thus $$(\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w \rightarrow (\lambda f . \lambda x. f x)(\lambda z .z)\lambda w.w$$

If we replace the congruence rules with evaluation contexts:
$$E::= [\cdot] \mid Ee \mid vE$$
then we need only a single rule to express the congruence rules of the language:
$$
\frac{e \rightarrow e'}{E[e] \rightarrow E[e']}.
$$

I am confused as to how evaluation contexts can tell us how to evaluate the expression $t$ from above without changing the syntax of the language. I don't understand how the evaluation context "works" without rewriting $t$ as

$$E_t = (\lambda f . \lambda x. f x)[\cdot]\lambda w.w$$

where $t = E_t[((\lambda y .y)\lambda z .z)]$. There is no obvious a priori reason to evaluate $t$ under call-by-value without knowledge of $E_t$. I really have no idea where I am going wrong. Can someone help correct my thinking?

The subtlety lies in where the distinction between language and metalanguage is made. As René Magritte put it:

$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda  z.z)) (\lambda  w.w)$ is a lambda-term, written in the syntax for lambda-terms. Let's call this lambda-term $t$. Let $M$ be the lambda-term $(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda  z.z))$. I can write $t = M \, (\lambda w.w)$ (and this is a true equality): all I did was to give a name to a subterm. If you consider the right-hand side of this equality “$M \, (\lambda w.w)$”, it is not written in the syntax of lambda-terms; it is written in a mathematical notation where we allow a letter to stand for a lambda-term.

When we write a rule like
$$
  \frac{e_2 \to e_2'}{v \, e_2 \to v \, e_2'}
$$
it states the following axiom: for any lambda-terms $e_2$ and $e_2'$ and any value $v$, if $e_2$ reduces to $e_2'$ then $v \, e_2$ reduces to $v \, e_2'$. Here we're again using meta-notations (i.e. mathematical notations to reason about a language): the arrow $\to$ to express the reduction relation; metavariables where a letter indicates the sort ($e$ for lambda-terms, $v$ for values) and subscripts and primes distinguish between metavariables of the same sort; the fraction notation to write an inductive axiom.

When we write the rule
$$
  \frac{e \to e'}{E[e] \to v E[e']}
$$
then again $E[\cdot]$ is a meta-notation, part of the metalanguage and not of the lambda-term syntax. The rule means: for any lambda-terms $e$ and $e'$ and any evaluation context $E[\cdot]$, if $e$ reduces to $e'$ then $E[e]$ reduces to $E[e']$.

If we call the context $(\lambda f. \lambda x. f x)[\cdot] (\lambda w.w)$ by the (meta-)name $E_t$, then $t = E_t[(\lambda y.y)(\lambda z.z)]$. Again, this is an equality between two lambda-terms, i.e. the same lambda-term is on both sides of the equal sign. What we have on the left and on the right are two different meta-notations for the same lambda term $(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda  z.z)) (\lambda  w.w)$: one that uses a name that we gave to it, another that's a bit more complicated involving a context that we gave a name to.

Given the term $t$, how do you find how it can reduce?

With the notation using multiple rules, you have to find a deduction tree (in general — here the derivation is linear, so you merely have to find a chain leading to an axiom).
With the notation using evaluation contexts, you have to find a suitable evaluation context.

The grammar of evaluation context follows the structure of the evaluation rules, so these are in fact not really two methods but two different ways of expressing the same definition.

To understand this, I strongly recommend the following exercise: in your favorite language, implement lambda-term call-by-value evaluation in a straightforward way, with a type representing lambda-terms and a function performing one reduction step.


Efficiently deciding whether TM accepts all inputs in at most $k$ steps I want to decide if a deterministic TM $A=(Q, \varGamma, \delta, q_s, q_h)$ halts on every input in at most $k$ steps. If the TM $A$ stops after $k$ steps, then  the positions $A$ can reach are limited by $2k$. Thus I can create a NFA with state set:

$$ Q' \subseteq \{1,\dots,k\} \times Q \times \varGamma^{2k} \times \varGamma \times \{-k,\dots,k\} $$

which keeps track of all necessary information to simulate $M$ with a suitable transition function. This construction is exponential in $k$ and I wonder if this can be avoided by using a PDA. Does the stack give ma enough information to avoid this exponentail blow up?

Given a 3CNF formula on $n$ variables, we can construct in polynomial time a Turing machine with polynomially many states $a(n)$ that accepts a truth assignment and in polynomial time $b(n)$ checks whether it satisfies the formula, and if so, enters an infinite loop. If you believe ETH, then checking whether this machine halts on all inputs in $b(n)$ steps should take time $2^{\Omega(n)}$, indicating some kind of exponential blow-up.


Why don't these 2 algorithms take the same time to detect duplicate lines in a file? I'm trying to write a small algorithm to detect and delete duplicate lines inside a subset of consecutive lines in a file.
I've come up with 2 similar solutions.
After some quick tests, I've noticed that one of them is much faster than the other, especially on large files.
But I don't understand why.

Here's the quick solution written in pseudocode, first_line and last_line are the first and last lines in the file where the algorithm looks for duplicate lines (I don't know exactly how to write pseudocode sorry):

i = last_line
while i > first_line
    j = i-1
    while j >= first_line
        if line i = line j
            delete line i
            break
        endif
        j = j-1
    endwhile
    i = i-1
endwhile

And here's the slow solution:

i = last_line
while i > first_line
    j = i-1
    while j >= first_line
        if line i = line j
            delete line j
        endif
        j = j-1
    endwhile
    i = i-1
endwhile

In the first solution, when 2 duplicate lines are detected and whose addresses are i and j,
line i is deleted, and the inner loop exits.
In the 2nd solution, line j is deleted, and the inner loop goes on without being broken.

At first, intuitively, I thought that choosing to delete i or j didn't matter.
But after some tests, it seems deleting i results in a much quicker process than deleting j.
I don't understand the asymmetry.
I suspect it's because the purpose of the outer loop is to test the uniqueness of the line whose address
is i, so it would make more sense to delete it as soon as we have an answer and not let the loop goes on.
But I still don't understand completely.

Deleting line i and exiting earlier in the inner loop of the first solution save comparison operations.
But by deleting line j in the 2nd solution, I also save comparison operations, since this j line won't
be processed by the outer loop later.

Why is the first saving of operations much more important than the 2nd one?

I'm sorry if the question is too simple for this site, but I don't know much about algorithms,
and I'm looking for a reasoning which I can understand and would prove that in the general case, deleting i
reduce the number of operations.

In case it matters, here's the real code I'm using, it's written in vimscript:

com! -range=% DelDup call s:del_dup(<line1>,<line2>)

fu! s:del_dup(line1, line2) abort
    let view = winsaveview()
    let p    = a:line2
    while p > a:line1
        let q = a:line1
        while q < p
            if getline(p) ==# getline(q)
                exe p . 'd_' | break
            endif
            let q += 1
        endwhile
        let p -= 1
    endwhile
    call winrestview(view)
endfu

Edit:

I've compared the 2 algorithms with this simple file:

apple
banana
grape
kiwi
orange
tangerine

Then, duplicate each line 256 times:

for i in range(1, 8) | sil %t$ | endfor

Which gives a file with 1536 lines.

Then, I've measured the time it takes for the :DelDup command to delete duplicate lines with the fast algorithm which I wrote earlier:

:Time DelDup

On my machine, the time reported is around 0.1s.

But if I replace the lines:

if getline(p) ==# getline(q)
    exe p . 'd_' | break
endif

With these lines:

if getline(p) ==# getline(q)
    exe q . 'd_'
endif

Then :Time DelDup reports that the command took more than 8s on average.

In case it matters, here's how the :Time command is defined:

com! -count=1 -nargs=+ -complete=command Time call s:time(<q-args>, <count>)

fu! s:time(cmd, cnt)
    let time = reltime()
    try
        if a:cnt > 1
        let i = 0
        while i < a:cnt
            exe a:cmd
            let i += 1
        endwhile
        else
            exe a:cmd
        endif
    finally
        redraw
        echomsg matchstr(reltimestr(reltime(time)), '\v.*\..{,3}') . ' seconds to run :' . a:cmd
    endtry
endfu

When you delete line j, each line which was after that line will be moved by one line upwards. That means, that your line i, which is below, also will be moved. So, since it was moved, it has changed it's number. And it means that you need to decrease i : i = i - 1.

As an example see this:

Given file:    Lines 2 and 3 are equal    Remove line 2:
1 00                                      1 00
2 01
3 10                                      2 10
4 01                                      3 01

And your second algorithm didn't see that their positions have changed. However, if it wouldn't be file, but an array/list/etc, you'd got an error.


Is it possible to reconstruct graph if we have given matrix of shortest pairs I'm trying to reconstruct graph if we have given the result of floyd-warshall algorithm, more formally:

Let's say we have given undirected weighted tree (graph without cycles) with $N$ nodes, such that from this graph we only have given matrix $g$ of size $N \cdot N$ elements, such that $g(i, j)$ gives the shortest path between nodes $i$ and $j$, note that it doesn't mean that nodes $i$ and $j$ are directly connected with edge.

What I think

We can say that node $x$ belongs on the path from node $a$ to node $b$ if and only if: $g(a,b) = g(a, x) + g(x, b)$.

If we fix nodes $a$ and $b$ in $O(N \cdot N)$ and we iterate over all other nodes, we will get total complexity of $O(N^3)$.

Is it possible to reduce this complexity to $O(N^2)$.

Thanks in advance.

I would suggest the following approach.

Maintain a data structure $H$ of $(i,j, g(i,j))$ triples so that you can efficiently find and remove a triple $(i,j,w)$ that minimises $w$.

Maintain a partition $P$ of nodes $V = \{1,2,\dotsc,N\}$.

Maintain a tree $T$.

We will maintain the invariant that $T$ contains some edges of the tree that we are trying to reconstruct, each part $X \in P$ is some subtree that we have not reconstructed yet. Eventually, $T$ will be the tree and $P$ will consist of singleton sets.

Initially, $P = \{V\}$ and $T = \emptyset$.

Apply the following operation repeatedly until $H$ is empty:

In $H$, find and remove a triple $(i,j,w)$ that minimises $w$.
See if $i$ and $j$ are in the same part of $P$. If not, discard this triple and try again.
Now we have a pair $(i,j)$ and a part $X \in P$ such that $i\in X$, $j \in X$. We now know that $\{i,j\}$ has to be an edge in the subtree induced by $X$.
Add $\{i,j\}$ to $T$.
For all nodes $v \in X$, see if $v$ is closer to $i$ or $j$. Based on this information, refine the partition $P$ by replacing $X$ with $X_i$ and $X_j$, where $X_i \subseteq X$ contains the nodes that are closer to $i$, and $X_j$ similarly.

If I am not mistaken, the time complexity is roughly as follows, assuming appropriate data structures:

We extract $O(N^2)$ triples.
Only $O(N)$ triples will result in something added to $T$. These are the triples that require nontrivial work.
For nontrivial triples, the operation that dominates is splitting. There we will need to check in the worst case $O(N)$ nodes.
So overall the running time is something like $O(N^2) + O(N) O(N) = O(N^2)$.
On top of this we pay whatever time we used to construct $H$. A simple solution is to just sort the triples $(i,j,w)$ by $w$. The cost depends on what kind of $w$ values you might have, but it isn't much worse than $O(N^2)$.


Construct Optimal Directory Trees Efficiently Question:

I want to construct a optimal directory tree structure to access $n$ ($n < 256$) elements using only the keyboard with as few key presses as possible. For this one could consider the directory as double linked list with connections between the first and the last element. To access element E, one then would traverse the list until the appropriate subdirectory S, enter S and restart from there until E is selected.

There are some natural requirements:

the elements in the tree structure are lexicographically ordered
the arity of the tree might be >2.
I would like to apply custom weights to some elements
the cost to be minimised is the weighted average of the total click count to access all elements (i.e. $c = \sum_{e \in E} w(e)*c(e)$, where $E$ is the set of elements, $w(\cdot)$ the weight for each element and $c(\cdot)$ the cost to access each element. $c(\cdot)$ depends on the chosen directory structure, of course.)

I'm struggling to find a good solution here. I do not know any standard tree that would fit in here as there might be no elements in intermediate nodes.

So, I'm looking for hints to literature. Maybe someone even knows an efficient algorithm? Bruteforce in Python takes too long to run, Bruteforce in C++ take too long to code :).

Motivation

I feed my stereo from a single board computer using the DLNA protocol. I want to access my music (artist-folders are the elements) as fast as possible. The stereo only supports "up", "down", "enter" and "escape" to navigate.

Clarifications

$c(e)$ is the number of clicks needed to access element $e$ from the top of the directory. $c(\cdot)$ depends on the directory structure. To access the lexicographically third element in a long list, one needs exactly 3 clicks (2x down, 1x enter). For the directory structure $((a, b), (c, d))$ one would only need 2 clicks to enter $c$ (2x enter).

Naming the subdirectories will not be a problem. Since the elements keep their order, I can use the names of the first and the last elements, as in a dictionary.

One way is to use a Huffman code, over an alphabet of size $k$, whre $k$ is the number of letters you're willing to use on the keyboard.  Make the weight for an entry be the "probability" for that entry (how often that entry is selected).  Then a Huffman code will minimize the expected number of key presses.  There's a standard algorithm for constructing a Huffman code.

The potential drawback is that it doesn't use the keys of the keyboard in the way you suggest; rather than using up/down to move forward/backward in a directory, the $k=4$ keys are all treated as equal, and each keypress moves you one level down in the tree.  In other words, each directory has at most $k$ entries, and you select an entry with a single keypress.  You might or might not be happy with the user experience.  If you prefer, you can set $k=2$ and use only the up/down keys for selection (each directory has two entries; press 'up' to select the first or 'down' to select the second, and it will jump immediately to that entry).  This will require fewer key presses than the approach you are imagining, but does require you to find a way to name each of the resulting nodes in the tree with a human-understandable category (i.e., pick a name for that directory/entry).


Is Conjunctive Normal Form or not? I have one formula that I do not understand why it is CNF and one that is not CNF, namely.

p && !q (NOT NCF)

and

!!p(CNF).

According to the exercise where I found these examples, 1 is not CNF and 2 is CNF.
How can the first formula not be CNF, when for example p && q is CNF.
If for example !!p is part of a formula we will translate it to p, how can we say that it is CNF?

Your examples do not look correct according to my understanding of the definition of CNF.  The first formula is CNF; it has two clauses, each with a single literal.  I would say that the second isn't, but the equivalent formula p is.  See https://en.wikipedia.org/wiki/Conjunctive_normal_form.


Doubt regarding address calculation in two-dimensional arrays I am reading about the address calculation formulas for one and two-dimensional arrays.             I have two related doubts concerning it.

In one of the problems, we are asked to calculate the location of B [1700] for an array B [1300....1900].
Now, I understand that B [1700] is actually the 401th element in the array (correct?), so we can calculate its address.

But in another problem, we are given an array X [-15....10,15.....40] and are asked to determine the location of X [15][20] but I don't see how it is even a part of the array since the "row" subscript(i.e. 15) is not contained in (-15....10). (According to me the last element of this array is X [10][40]).

My second doubt is: In another question, we are given the array M[-3......18,-8......7] (stored column-wise where width of element = 8 bytes) and are asked to calculate the base address given that the address of element M [5][10]=4000.

The solution proceeds as -

  M [5][10] = BA + W*(M*(j-Lc)+(i-Lr)) therefore, M [5][10]=4000 + 8*(22*(10-0)+(5-0))

i.e. my book answer takes Lc = 0 & Lr = 0 but I think it should be Lc = -8 and Lr = -3? So, which is it?
Also can I write a program in which I can verify this for myself (specifically, how can I declare an array in c++ whose subscript doesn't start at 0?)?
Thank you so much.

For the first question, you can calculate an address for it -- languages that don't do array bounds checking will gladly calculate an address and read/write there, even if it is out of bounds.  Of course, if the program is accessing an out-of-bounds element, that's typically a bug of some sort.

For your second question, you are right.

You probably won't run into arrays that start at an index other than 0 in practice very often (if ever), so I wouldn't worry too much about it.  Your understanding seems solid.


Proving Undecidability with reductions - Why do some proofs not use an Oracle? I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf
So as I've learnt it, say we want to prove a new Language L is undecidable using a known undecidable language D, we use Oracle calls to L to solve an instance of D right?
In none of these questions is an oracle used - For example, with L9 :"M' on input w: it
runs M on x and accepts if M halts on x" That's the algorithm; no oracle is used. I understand the reasoning to their solutions, but shouldn't they be using an oracle call? I'm very new to this so sorry if I'm misunderstanding

An oracle call is stronger than emulating a TM: it allows you in constant time to solve the task of checking if some $x$ is in the language specified by the oracle.
What you saw didn't use oracle machines, since it proved by assuming towards contradiction: It assumed there is a machine $M$, and showed how to use its code in order to build a new machine $M'$ solving a problem that can't be solved - hence $M$ doesn't exist.


How do you determine the inputs to a neural network? I'm looking at this tutorial on neural networks. The data that is given from the UCI study includes various attributes, such as "mean x of on pixels", "total # on pixels" etc, which are taken as input to the neural network. However, it seems to me that this choice of input parameters is somewhat arbitrary, and, in this case, would only apply specifically to the black-and-white letter recognition problem, and maybe could be extended to some other image recognition problems.

As a result, my questions are:

How do you determine what inputs you should use for a neural
network?
Are more inputs necessarily better?
Does it matter if inputs are linearly independent?
And, finally.. Could one build a neural network that could determine its own inputs for an arbitrary problem and raw data set?

How do you determine what inputs you should use for a neural network?

Experimentation.  Initially you use a priori knowledge and intuition to guess the features will be useful for classification or prediction or whatever it is your network is doing.  Then you test the network and observe its error rate.  Based on the results you make adjustments; add/discard features, regularize, add/discard layers, adjust the learning rate, and so on.

  Are more inputs necessarily better?

No.  You're trying to find the features that matter to what you're trying classify/predict and discard unrelated features.  Processing input/features that don't matter to the computation just wastes CPU time.

  Does it matter if inputs are linearly independent?

If inputs are linearly dependent then you are in effect introducing the same variable as multiple inputs.  By doing so you've introduced a new problem for the network, finding the dependency so that the duplicated inputs are treated as a single input and a single new dimension in the data.  For some dependencies, finding appropriate weights for the duplicate inputs is not possible.

  Could one build a neural network that could determine its own inputs for an arbitrary problem and raw data set?

This is essentially what neural networks that deal with raw data only must do.  The hidden layers tease features out of the raw data and those features are gradually refined by the feedback that occurs during training.  This is an approach you might use if you have no idea how to proceed given some classification problem.  But usually you have some idea what features are both useful and difficult for the network to compute for itself, and you provide those features as additional input.


How to show the function is not Turing computable? Having the function:

$$f(y) = \begin{cases}
         \ 1 &\text{if }\forall n \Phi_y(n)=n\lor \Phi_y(n) \!\uparrow\\
         \ 0 &\text{otherwise.}
\end{cases}$$

By the rule of thumb it should not be computable. How to prove it formally?
If it's computable, I assumed a function like this exists:
$$g(y) = \begin{cases}
         \ 1 &\text{if $f$(y) = 1 }\\
         \ 0 &\text{if $f$(y) = 0}
\end{cases}$$

I assumed $g(y)$ is computable. Now there exists a function $\Phi_{x_0}(x_0)$ which simulates $g(y)$.
This means: $\Phi_{x_0}(x_0) \downarrow$ iff $\Phi_{x_0} (x_0) \uparrow$, which is a contradiction. Is this sufficient as a proof?

Since I assume this is a homework question, I won't give a fully detailed proof but rather a sketch with some gaps to fill.

Consider the function
$$g(x)=
\begin{cases}
  x+1 & \text{ if } \varphi_x(x)\downarrow\\
  \uparrow & \text{ otherwise}.\end{cases}$$
This function is computable (convince yourself of that!), so it has an index $e$.

Now consider the function $f$ on $e$, then computing $f(e)$ comes down to verifying whether $\forall n\  \varphi_e(n)\uparrow$. Can you see why this contradicts that the halting problem is not computable?


Scheduling Algorithm for aperiodic multiprocessor tasks I've got a System, which is defined as follows:

A limited number of stations is given (n), which can offer different services (for now there are two services). A station can either offer one of the services or both (maybe it will be extended one day, then it should work with x different services and a station can offer 1..x of these services).
The throughput for a service can differ from station to station.
Each service in the system can have a fixed priority assigned by the developer. If multiple services have to be scheduled and the scheduler isn't able to assign each service at once to a single station, it can split up the services and chose the service with the highest priority to run first and run the other service/s later on. (also see next point)
If a task requests multiple services, it is okay to split them up.  For example, there are two services requested (a and b): requested service a is running on station c for 10 minutes, afterwords it is moving to station d to receive service b.  However, you could also think of this as two separate tasks, each of which requests a single service, if you prefer.
A task can arrive at any time, for example the incoming of a new request.
Each task has an arrival time, an execution time (computed by the requested amount of the service and the amount a station can offer. in other words: this is the time, a particular station will need to complete a task) and a deadline
Different tasks have different execution times.
Arrival time: there are "reservations", then the arrival time is known before the task arrives. but there are other cases, in which the arrival time is not known, so the arrival time equals "now".
A station can serve one task at a time, but a task can request multiple services at once (there are stations which offer these services at the same time, the different services doesn't influence each other).
Tasks can be preempted and moved between stations during execution, meaning that if one task is running on a station the task can be assigned to a different station which offers the same service (this station-change can cause costs, based on the distance between different stations). This could be caused by another task which needs the station the first task was running on until now.
The algorithm has to work in real time.

The System is given and works already with one service, I have to adapt it to work with multiple services. For this, I have to look for and implement a new scheduling algorithm, but I have no idea for what I have to look for. Another possibility is to design my own algorithm, but due to the lack of knowledge in this sector I think it would be a bad idea.

Any hints for what kind of scheduling algorithms I have to look for?

One technical term that might help you focus a literature search is "load balancing".  See, e.g.,

The Power of Two Choices in Randomized Load Balancing, Michael Mitzenmacher,  IEEE Transactions on Parallel and Distributed Computing, 12(10), pp. 1094-1104, 2001.


Why is universality of CFG undecidable? Let $\text{ALL-CFG} = \{\left<G\right> \mid G\text{ is a CFG and } L(G) = \Sigma^*\}$.
I have understood the proof of ALL-CFG is undecidable, but I wonder why the following proof is not appropriate.
Let $C$ be a CFG. Then $\bar{C}$ is a CFG by closure under complement. Since the emptiness of CFG is decidable, we can use it to decide whether $\bar{C}$ is empty and therefore whether $C$ is universal.
This problem has confused me a lot. Really appreciate your help. Thanks!!!

The context-free languages are not closed under complement. For example, $\overline{\{a^nb^nc^n : n \geq 0\}}$ is context-free, but its complement isn't.


Similar news detection How do top news portals detect similar news? For example https://www.bbc.com/news/world-asia-china-51431087, if you go to this webpage, you can see the "More on this story" section at the bottom of the page. This news was published today, but it has detected similar news from days ago.

Is there any known algorithm or any library?

This is a proprietary system so we have no way of knowing.

In general, you will find a lot of work and potential solutions by searching for text similarity or document similarity. For starters, you could have a look at the work of Islam and Inkpen [1] on short sentence similarity (it mentions plenty of other references you can widen your search to) or a more general survey of Gomaa and Fahmy [2].

If you are interested in libraries, NLTK might be helpful.

[1] Islam, Aminul, and Diana Inkpen. "Semantic text similarity using corpus-based word similarity and string similarity." ACM Transactions on Knowledge Discovery from Data (TKDD) 2.2 (2008): 1-25.

[2] Gomaa, Wael H., and Aly A. Fahmy. "A survey of text similarity approaches." International Journal of Computer Applications 68.13 (2013): 13-18.


A* graph search time-complexity Some confusion about time-complexity and A*.

According to
A* Wiki the time-complexity is exponential in the depth of the solution (shortest path):

  The time complexity of A* depends on the heuristic. In the worst case of an unbounded search space, the number of nodes expanded is exponential in the depth of the solution (the shortest path) d: $O(b^d)$, where $b$ is the branching factor (the average number of successors per state).

The comment to this accepted answer points out that it makes more sense to give the complexity in termes of the size of the graph and therefore it should be $O((|V| + |E|) \cdot log |V|)$

Obviously, if the heuristic assigns a value of 0 to every node, A* becomes Dijkstra's algorithm and any uniform cost heuristic will essentially disable the heuristic.

If we assume the heuristic to be $O(1)$ (and consistent), it would make sense that the worst case is essentially degrading A* to Dijkstra's algorithm which has complexity

$O(|E|+|V|\log|V|)$

with a min-priority queue implementation (Fibonacci heap).

Am I wrong?

Any book etc I have been looking at always gives the complexity in terms of the depth of the solution

These are basically two different perspectives or two different ways of viewing the running time.  Both are valid (neither is incorrect), but $O(b^d)$ is arguably more useful in the settings that typically arise in AI.

In the algorithms community and CS theory community, folks there tend to like to count the running time as a function of the number of vertices and edges in the graph.  Why?  In that context, worst-case running time is what makes most sense; also, in the problems that are typically considered in that community, in the worst case we need to examine the entire graph, so you typically can't hope to do better than $O(|V|+|E|)$.

In the AI community, folks tend to count the running time differently.  They often consider a specific kind of graph: a tree with branching factor $b$.  Also, in the situations that arise there, the graph is often infinite or very large.  Typically we try hard to avoid examining all of the graph -- that's often one of the major goals of the algorithms.  Thus, counting complexity in terms of $|V|$ and $|E|$ doesn't make sense: $|V|$ may be infinite, and in any case, we don't plan on examining all of the graph, so all that matters is the number of vertices we actually visit, not the number that may exist elsewhere but that we don't care about.

So, for the situations that often arise in the AI community, it's often more meaningful to measure the running time in terms of the branching factor of the tree ($b$) and the depth of the goal node ($d$).  Typically, once we find the goal node, the algorithm stops.    In such a tree, if we examine every vertex at depth $\le d$ before we find the goal node, we'll end up visiting $O(b^d)$ vertices before we stop.  Thus, if you like, you could think of this as visiting a subset of the graph with $|V|=O(b^d)$ (where now $V$ includes only the vertices we visit) and $|E|=O(b^d)$ ($E$ includes only the edges we look at), and you could think of an $O(b^d)$-time algorithm as one whose running time is $O(|V|+|E|)$... though this is a bit of an abuse of the $|V|,|E|$ notation.   Anyway, hopefully you can see why $O(b^d)$ is more informative than $O(|V|+|E|)$ in this context.


Is following grammar has language which is inherently ambiguous? Grammar is as follow:

$S \rightarrow aaAb | aab | A$

$A \rightarrow aaAb | aAb | \epsilon$

I think that this grammar has equivalent unambiguous grammar as follow.

Let’s first rewrite the grammar as below such that this grammar has same language as one in question:

$S \rightarrow aaSb | aSb | \epsilon$

Because this grammar generates $L = \{a^nb^m: m \le n \le 2m\}$

This grammer is just using two production in some order to derive string and then use null production to complete derivation.

So, idea is that we can some how order use of production such that any use of $S \rightarrow aaSb$ production does not come before use of any production of form $S \rightarrow aSb$. And following this idea it’s very easy to generate this grammar.

$S \rightarrow aSb | A$

$A \rightarrow aaAb | \epsilon$

.

Another arguments goes as follow:

Because $2k_1 + k_2 = n$ and $k_1 + k_2 = m$ for some $nonnegetive \space integer \space k_1, k_2$. (here $k_1$ and $k_2$ corresponds to number of use of production of form $S \rightarrow aSb$ and $S \rightarrow aaSb$ respectively.)

After solving the above equations we find that $k_1 = m-n$ hence value of $k_1$ will be unique for any perticular string. Which means that we must have to use some fix number of times the production of form $S \rightarrow aSb$. Which consequenly means that in our last rewritten grammer there is a fix point for a perticular string where you have to perform $S \rightarrow A$.

Please help me with this. I want to know whether this language is inherenly ambigous or not?

Your grammar $$\begin{eqnarray}S &\to& aSb &|& A \\ A &\to& aaAb &|& \epsilon\end{eqnarray}$$ is indeed unambiguous. The production $S \to A$ must occur precisely once in any derivation, and the productions which precede it cannot be replaced with any productions which succeed it or vice versa.


How to find optimal token set for compression? By token I mean the smallest element of source data, that the compression algorithm works on. It may be a bit (like in DMC), a letter (like in Huffman or PPM), a word, or variable-length string (like in LZ).

(Please feel free to correct me on this term, if I use it incorrectly.)

I'm thinking: what if we first find optimal set of tokens, and only then compress our data as a stream of these tokens? Will it improve compression of text or of xml or of some other kind of data? LZ sort of does this, but it is limited to letters. I'm asking about truly general approach when a token can have any bit-length. For example, it can be interesting to do it for compression of x86 executable files. Or in other cases, when sub-byte (and sup-byte) bit-strings behave as individual tokens.

How to find this set of tokens optimally? In a way that maximize average entropy of a stream of such tokens under 0-order Markov model?

Are there existing algorithms for it? Are there any algorithms related to the problem?

How to find approximation of this set? What is complexity of optimal and approximation solution?

And what if we want to maximize entropy for higher order Markov model? How harder the problem will be in this case?

Are there existing algorithms for it? Are there any algorithms related to the problem?

Theoretical one: https://en.wikipedia.org/wiki/Sequitur_algorithm
Practical one: https://encode.ru/threads/1909-Tree-alpha-v0-1-download


Data structures that store efficiently detected features of an image I struggle to find this, suppose I apply any feature detection algorithm. From my references it seems to me it's not usually explained what kind of data structures would be suitable for storing such features.

For example in opencv it seems to me that the Canny Edge detector will return a matrix (I assume the code/gray level code is like relating high pixel value with the the feature in that specific pixel). I think it would be useful to know what data structures could actually be useful in this case to navigate through all the extracted features instead of iterating through all the pixels.

So the question is... in general (or at least line features) what data structure is usually useful? and how is such data structure constructed?

As a specific example... I'd like to extract all the edges of a given image, name such edges $e_1,\ldots,e_n$. Then I need to access to the pixels that lie both to the left and right of such edge(not all, just pixels that are close enough to $e_i$, for all $i$). Finally I need to perform some operations on such pixels.

To summarize something like:

$e_1,\ldots,e_n \leftarrow extractEdges(I)$

$\forall i \in \left\{ 1,\ldots, n\right\}$

$\;\; S_l \leftarrow pixelsLeft(e_i)$

$\;\; S_r \leftarrow pixelsRight(e_i)$

$\; \; doSomething(S_l,S_r)$

Above $I$ representes the input image.

Thank you

A simple solution would be a 2D array containing a 1 in the locations that are detected as an edge, or a sparse 2D matrix.  A more sophisticated solution would be a quadtree.


Do there exist any problems with optimal algorithms beyond $O(n)$? Blum's Speedup Theorem famously shows that there are problems which admit no fastest algorithm. This raises an obvious question: are there any problems that do admit a fastest algorithm? In other words, does there exist a language $L$ which is decided by some algorithm within $f(n)$ steps so that any other algorithm which solves the same problem also runs in $\Omega(f(n))$ steps? If $f$ is linear, this is trivially the case. But what about beyond linear? Just a nonconstructive existence proof would already be cool.

(Deterministic) TMs with a single tape can recognize palindromes in time $O(n^2)$. It has been proven that this time bound is optimal (see, e.g., this paper).

Also, the time hierarchy theorems give you an endless supply of such examples (though they are not natural problems, of course).