What do functions look like, if I stated out with the categoical model of my type theory? I see how objects in a category stand for types, but where do I find the terms and more specifically the rules which tell me which of them are allowed? When I e.g. consider a Cartesian closed category as model of a type theory, how are term constructors represented?

I guess this is the same as asking how do I know or specify appropriately what the homsets of this category are, which I assume are in bijection with the lambda terms. The Curry–Howard–Lambek correspondence as presented at the end of the Wikipedia page Curry–Howard–Lambek correspondence presents all terms conventionally as in a type theory, but if I start out with a category, the model, then I must have specified them in a more algebraic sense.

And once given, does the model also represent $\beta$ and $\eta$ conversion? I actually read on the (quite too high level for me) nLab that morphisms relate to substitutions. Then I guess the lambda terms are somehow elements of the objects.

Your intuition is correct: terms are "somehow" elements of the objects. The only thing left is to figure out what elements in a category are. They cannot be literally elements because objects need not be sets (and more generally there may be no way to even "convert" an object to a set with a functor).

If I say "consider a mass point $p$ moving in $\mathbb{R}^3$" then you will immediately understand that $p$ is not actually an element of $\mathbb{R}^3$ but a map $\mathbb{R} \to \mathbb{R}^3$, i.e., the point is parameterized by time (which we take to be a real number). It is a general phenomenon that "entities" can be parameterized, and so they can be thought of as either variable elements or maps. For instance "temperature" may be thought of as a scalar field mapping the points of Earth's surface to real numbers, or it can be thought of as a real number which varies with position on the Earth.

In any case, this leads to the idea that the elements of an object $A$ in a category are simply all morphisms $B \to A$. When $B$ is the terminal object, we get the global (non-parameterized) elements, but in general we allow elements to be parameterized by any object, and so we call them generalized elements. One way to understand the Yoneda lemma is that an object in a category consists of its generalized elements.

You asked how to pass from a category to its internal type theory. Let me answer the opposite question first. Given a type theory, we can think of terms in context as the generalized elements of a type, while the closed terms are the global elements. But since generalized elements are the same thing as morphisms this tells us how to build a category out of a type theory: the morphisms are just terms in a context, quotiented by whatever equations the theory proves.

To go in the opposite direction, suppose we have a category $\mathcal{C}$ and we want to make a type theory out of it. As you said, we take the types to be the objects of $\mathcal{C}$. According to our view that "generalized elements are morphisms", the morphisms $f : A \to B$ ought to correspond to terms of type $B$ in context $A$. But we cannot just write $x : A \vdash f : B$ because there is no $x$ on the right-hand side. It would make more sense for $f$ to have the type $A \to B$, which is precisely what we do. For each morphism $f : A \to B$ we introduce a constant of type $A \to B$, which we also write as $f$. Then the correspondence is recovered: given $x : A$ there is a term $f\, x : B$.

If our type theory does not have arrow types then we have to do things a bit differently. For each morphisms $f : A \to B$ in $\mathcal{C}$ we add a unary term constructor $f$ and the typing rule
$$\frac{\Gamma \vdash e : A}{\Gamma \vdash f\,e : B}.$$
Note that $f\,e$ is just a syntactic form, namely application of the unary term constructor $f$ to the term $e$. It would make no sense to apply the morphims $f$ to the term $e$!
A type theory consists not only of types and terms, but also of equations. Our category gives us some equations, too: if the morphism $h : A \to C$ is the composition of $f : A \to B$ and $g : B \to C$, then we get the equation
$$x : A \vdash h \, x =_C g (f \, x).$$
There are some further equations. For instance, if $A$ and $B$ are objects and $C$ is their product, then we need to relate the type $C$ with the product type $A \times B$. That is, in the category there are projections $\pi_1 : C \to A$ and $\pi_2 : C \to B$ and a pairing operation $\langle{-}, {-}\rangle$, while in type theory there are projections $\mathtt{fst} : A \times B \to A$ and $\mathtt{snd} : A \times B \to B$ and pairing $({-},{-})$ (where $A \times B$ is the formal product type). We need equations which relate these, but let me skip the technicalities.

The $\beta$ and $\eta$ reduction rules are validated by a cartesian closed category. The rules about product and function types correspond to various parts of the adjunction between cartesian products and exponentials.

In conclusion, it may seem strange that we take all morphisms in a category and make them into unary constructors of the corresponding type theory. If the category is very big that gives us a very large type theory which is not syntactic in any sense of the word syntactic. Just free your mind and the rest will follow.


I'm trying to understand why every language has an infinite number of TMs that accept it I found the following answer:

$L_{17} = \{ \langle M \rangle \mid \text{$M$ is a TM, and $M$ is the only TM that accepts $L(M)$} \}$.

R. This is the empty set, since every language has an infinite number of TMs that accept it.

As I know number of TMs is $\aleph_0$ and number of languages is $2^{\aleph_0}$, so how can it be possible that "every language has an infinite number of TMs that accept it"?
source of the solution here

The correct version of the claim states that every computable language is accepted by infinitely many Turing machines.
Indeed, if $L$ is computable, then there is a Turing machine $T$ that accepts it. Let $T_n$ be $T$ together with $n$ unreachable states. Then $T_n$ also accepts $L$, and the machines $T_n$ are all different from one another.


Understanding Correctness of Bidirectional Dijkstra I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10:

https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf

For a contradiction, they consider an $s-t$ path $p$ that is shorter than the minimum sum $\mu$ of tentative distances from the forward and backward search.
The next step I don't understand: there is an edge $(v,w)$ on this path, such that:

$dist(s,v) < top_f$
$dist(w,t) < top_b$

Where do these relationships come from?

From what I see, after stopping, it holds that $\mu \leq top_f + top_b$.

So if we consider any edge $(v,w)$ of $p$, we have that

$dist(s,v) + length(v,w) + dist(w,t) < top_f + top_b$

We can leave out that edge to get the inequality

$dist(s,v) + dist(w,t) < top_f + top_b$

But from this, I can't derive these two relationships.

I appreciate any help! Thanks!

I came across these slides where on slide 23 another proof is given, however the idea of this proof is the same as in the slides of my original post.

But this still doesn't show, why $dist(s,v)$ and $dist(w,t)$ need to be less than $top_f$ and $top_b$ respectively.

EDIT: Note that with this proof $dist(s,v) \leq top_f$ and $dist(w,t) \leq top_b$ hold, since both vertices have already been settled. I'm in doubt, whether the original statement $dist(s,v) < top_f$ and $dist(w,t) < top_b$ is actually correct and therefore I'm marking this question as 'answered'. However if anyone finds an explanation, feel free to answer!


Is the following recurrence for this program's runtime correct? Let $f$ and $g$ be two functions and $p$ a number. Consider the following program:

Recurs(v,p) :
  find s < v such that f(s,v) < v/2 and g(s,v-s) < p

  if no such s exists then
    return v
  else if s <= v/4 then
    return v-s U Recurs(s,p)
  else if s > v/4 then
    return Recurs(s,p) U Recurs(v-s,p)
end

Can the recurrence for the running time of this recursion be $T(v)=T\left(\frac{v}{4}\right)+T\left(\frac{3v}{4}\right)+1$?

tl;dr: NO.  Well, okay, maybe.

Translating the pseudocode mechanically into a recurrence gives me
$$
T(n) = \Theta(1) + F(n) + \max \begin{cases}
    \max_{0\le s \le n/4} T(s) \\
\\
    \max_{n/4 < s < n} (T(s) + T(n-s))
\end{cases}
$$
where $F(n)$ is the time for the first "find" step.  Every outcome that is not known in advance is folded into the $\max$; since we're bounding the worst-case running time, we always assume the worst possible outcome.  The initial $\Theta(1)$ includes all the time for bookkeeping, comparisons, stack manipulation, and that union operation in the output.  (Performing a set union in constant time is somewhat magical, but I'll let that slide.)  I'm also assuming here that the variable $s$ always lies between $0$ and $v-1$, since otherwise the algorithm never terminates, although this assumption is never specified in the code.

Under the reasonable assumption that $T(n)$ is monotonically increasing, we have
$$
\max_{0\le s \le n/4} T(s) = T(n/4)
$$
Under the further assumption that $T(n)$ is "nice" and convex, we have
$$
\max_{n/4 < s < n} (T(s) + T(n-s)) =
 \begin{cases}
 T(n-1) + T(1) & \text{if $T$ is convex}\\
 T(n/4+1) + T(3n/4-1) & \text{if $T$ is concave}
 \end{cases}
$$
Here, "convex" means that $(T(a) + T(b))/2 \ge T((a+b)/2)$ for all $a$ and $b$, or less formally, that the function "curves upward".  If $T$ is "nice", this is equivalent to assuming $T(n) = \Omega(n)$.  Symmetrically, $T$ is concave (curves downward) iff $T(n) = O(n)$.

("Nice" means a function whose second derivative is well-defined and doesn't oscillate between positive and negative forever; for example, the product of a polynomial and some logarithms is nice.  Wacky functions like $n^{2 + \sin(2\pi n)}$ are not nice, but I'll bet you a dollar that your algorithm doesn't have that function as a time bound.)

So our recurrence is now
$$
T(n) = \Theta(1) + F(n) + \max\begin{cases}
 T(n/4) \\
 T(n-1) + T(1) \\
 T(n/4 + 1) + T(3n/4 - 1)
\end{cases}
$$
If $T$ is increasing, the first case is smaller than the other two, so we can ignore it.  So we have two possibilities to consider.

First, suppose
$$
  T(n) = \Theta(1) + F(n) + T(n-1)
$$
(I folded the extra $T(1)$ into the $\Theta(1)$ term.)  This recurrence unrolls into a simple summation
$$
  T(n) = \Theta(n) + \sum_{i=1}^n F(i)
$$
which implies that $T(n)$ is convex no matter what function $F(n)$ is.  So this  recurrence seems to work.  (The apparently circular argument about convexity can be unwound into a boring and mechanical proof by induction, if you care.)

On the other hand, suppose
$$
  T(n) = \Theta(1) + F(n) + T(n/4 + 1) + T(3n/4 - 1).
$$
Then even with the very strong assumption that $F(n) = O(1)$, a quick recursion tree argument implies that $T(n) = \Theta(n)$.  The same recursion tree argument implies that if $F(n)$ is grows even slightly faster than a constant, then $T(n)$ is strictly convex, which means this is the wrong recurrence.

So this recurrence only works when $F(n) = O(1)$.  In that case, we can simplify the recurrence further to
$$
  T(n) = \Theta(1) + T(n/4 + 1) + T(3n/4 - 1).
$$
We still have those pesky off-by-ones in the recursive arguments, but whatever.  We've already figured out that $T(n) = \Theta(n)$, so who cares about the recurrence any more?


Relationship between Las Vegas algorithms and deterministic algorithms I'm wondering why the following argument doesn't work for showing that the existence of a Las Vegas algorithm also implies the existence of a deterministic algorithm:

Suppose that there is a Las Vegas algorithm $A$ that solves some graph problem $P$, i.e., $A$ takes an $n$-node input graph $G$ as input (I'm assuming the number of edges is $\le n$) and eventually yields a correct output, while terminating within time $T(G)$ with some nonzero probability.

Suppose that there is no deterministic algorithm that solves $P$. Let $A^\rho$ be the deterministic algorithm that is given by running the Las Vegas algorithm $A$ with a fixed bit string $\rho$ as its random string.
Let $k=k(n)$ be the number of $n$-node input graphs (with $\le n$ edges).
Since there is no deterministic algorithm for $P$, it follows that, for any $\rho$, the deterministic algorithm $A^\rho$ fails on at least one of the $k$ input graphs. Returning to the Las Vegas algorithm $A$, this means that $A$ has a probability of failure of $\ge 1/k$, a contradiction to $A$ being Las Vegas.

There is no contradiction here. A Las Vegas algorithm terminates in expected polynomial time, say $Q(n)$. Markov's inequality shows that for any given polynomial $R(n)$, it terminates in polynomial time $Q(n)R(n)$ with probability $1-1/R(n)$. The number of graphs on $n$ vertices, $k(n)$, is exponential in $n$, so the failure probability $1/R(n)$ is much larger than $1/k(n)$.

Another subtle point is uniformity. A deterministic algorithm needs to handle any input size, while your $A^\rho$ can only handle inputs of certain size. In general, a randomized algorithm can use an unbounded number of random bits. However, your argument can still be formulated in terms of non-uniform models such as circuits, and it is still wrong for the reason described above.


How does a regular language satisfies the second condition of the pumping lemma I'm a little bit confused about the second condition of the pumping lemma which are:

$|y|\geq1$
$|xy|\leq p$
$\forall i \geq 0 : x y^i z \in L$

I don't understand why the length of substrings $xy$ has to be less than the pumping length? Considering the example below:

Suppose we have a language $L = \{ w | w ∈ 1^*0+1^*\}$ and a string $s \in L$ which $L$ is a regular language.
Let the string $s = 101$ and $S$ can be split into three substring $xyz$ where $y$ can be pumped.

Therefore:

$x = \text{'1'}$ $y=\text{'0'}$ and $z=\text{'1'}$. It seems that substring $|xy|$ is somehow larger than the pumping length $p$ itself (in this case: $p=1$ since there's only one $0$), Therefore $|xy| > p$, a contradiction ! Does this mean that the language $L$ in this case is not regular ?

Or did I misunderstood something.

The pumping lemma states that if a language $L$ is regular then there exists $p$ such that every word $w \in L$ that is long enough ($\lvert w \rvert \ge p$) can be split as $w = xyz$ such that

$|y| \geq 1$.
$|xy| \leq p$.
For all $i \geq 0$, $xy^iz \in L$.

You give an example of a language $L$ and a string $s \in L$ which can be split as $s = xyz$ such that

$|y| \geq 1$.
$|xy| = 2$.
For all $i \geq 0$, $xy^iz \in L$.

This is a property which is similar to the one guaranteed by the pumping lemma, but perhaps different. The property expressed by the pumping lemma need not be the only property satisfied by a regular language. All the pumping lemma states is that if a language is regular then it satisfies the pumping property. It does not state that if a language is regular then the only property it satisfies is the pumping property.

To give an analog, consider the following statement: if $x$ is a multiple of $4$ then it is a multiple of $2$. Here is a "counterexample": $12$ is a multiple of $4$, but it is a multiple of $3$ (rather than $2$). Your counterexample is similar.

Another issue is the pumping length $p$. If you look at the proof, then $p$ is the size of a DFA accepting $L$. In particular, $p$ doesn't depend on $w$. In your case, it's not clear why you assume that $p=1$; in fact, when applying the pumping lemma, you cannot assume anything about $p$. You're just guaranteed that some $p$ exists. In fact, for your language $p \geq 5$, since the minimal DFA has $5$ states.

The condition $|xy| \leq p$ is supposed to help you apply the pumping lemma. For example, if you look at the language with strings $0^n1^n2^m$ for $m, n \ge 0$, without this condition you wouldn't be able to prove that the language is not regular, since the pumped part could always be in the $2^m$ area. The condition $|xy| \leq p$ allows you to locate the pumped part.

This condition isn't always general enough, for example it doesn't work for showing that $2^m0^n1^n$ is not regular. There is a more general version of the pumping lemma which can handle this called Ogden's lemma.


MIPS pipeline: choosing between slowing down a stage and adding a new stage Suppose a new, more complicated, instruction is desired for this
  simple pipelined MIPS processor. Suppose, also, it could be
  implemented by either (a) adding new logic to the execute stage of the
  pipeline, or (b) adding a new stage (i.e a 6th stage) altogether.
  Assume that choice (a) would slow the execute stage down by 20%. Since
  choice (b) increases the number of stages by 20%, is the overall
  effect on execution the same? If not, describe how each choice affects
  execution time and indicate which choice is better.

This was a question in my exam, but I'm not sure if my answer to it is correct. Here is what I think:

If the execution stage time increased by 20%, then the new cycle time will likely be the time of the execution stage. So cycle time will increase by 20%.

Adding a new stage to the pipeline wouldn't affect the cycle time (assuming the new stage is shorter than or equal to the longest stage). It would increase the throughput, but also increase the latency of individual instructions by 20%.

So, no, they don't have the same affect on overall performance. The second choice is more efficient.

Now, am I correct?

Your answer is probably correct for an exam.

In reality, adding a pipeline stage to MIPS is a major undertaking. The MIPS pipeline is very simple, that’s why it is taught in CS courses. Adding a pipeline stage adds a whole new level of complexity. Take an instruction sequence

X = A+B
X = C+D
Z = X+Y

In the current pipeline design, Z can just about be made to pick up the correct X - when C+D is stored, it goes directly into the first input of X+Y. With an additional pipeline stage, the second X is nowhere near ready when the third instruction starts. So you must make that instruction wait. But only because X isn’t ready in time. Since you don’t want to always wait, you need to detect this and add logic for that. And then the question is how often does this happen.

The alternative is that instructions using the second pipeline stage - and only those - stop all the other stages from progressing. So the timing would be the same as if this instruction was two instructions. In that case you could just make it two instructions.


Three languages and how to decide if they are regular From following languages which one is regular and why others are not?And what is the regular expression for regular one.

$L_1=  \{wxwy | x,y,w \in (a+b)^+\}$

$L_2 = \{xwyw | x,y,w \in (a+b)^+\}$

$L_3 = \{wxyw | x,y,w \in (a+b)^+\}$

Also where can I find these type of problems?

The first two are regular, because they can be written as $aA^*aA^*+bA^*bA^*$ and $A^*aA^*a+A^*bA^*b$ (where $A=a+b$). This is because it is enough to check them for $|w|=1$, as it is implied by longer $w$.

The last language is not regular, because its intersection with the regular language $a^+b^+aba^+b^+$ is $\{a^nb^maba^nb^m| n,m\geq 1\}$ which is not regular (you can show this by pumping lemma).


Determine if the language is $R$ Consider the following language:

$$L = \{ \langle M \rangle \ |\ M \text { is a TM that decides the halting problem} \}$$

  determine whether or not the language is in $R$.

Now, from my understanding an $\langle M \rangle \in L$ doesn't necessarily returns the right answer but rather halts for every $\langle P, x \rangle$ where $p$ is a program (=TM) and $x$ is an input for the program.

I am guessing the language isn't decidable and can be showed as such by some reduction, but couldn't think of something useful.

I'll be glad for help.

comments summary:

The language $L$ is decidable.

Hint:

   $L$ is in fact empty! It contains all the machines that decide the halting problem. But, the halting problem is undecidable => there are no machines that decide it.


How do we make sure in Paxos that we don't propose a different value if a majority has formed? Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was confused about one specific part. How does or why does property $P2^b$ satisfy property $P2^c$?

These are the properties:

$P2^b = $ If a proposal with value $v$ is chosen, then every higher-numbered (i.e. approx. later in time)  proposal issue by any proposer has value $v$.

$P2^c$ = For any $v$ and $n$, if a proposal with value $v$ and number $n$ is issued, then there is a set $S$ (some majority) of acceptors such that either:

(a)no acceptor in $S$ has accepted any proposal numbered less than $n$, or

(b)$v$ is the value of the highest-numbered proposal among all proposals numbered less than $n$ accepted by the acceptors in $S$ (some majority).

The paper uses $S$ to denote some majority and $C$ to denote some majority that has actually chosen a value.

The thing that I am confused about is, for me $P2^b$ is saying, ok once a value has been chosen, say at sequence number $n$ (i.e. roughly time $n$), then after that time, we want to make sure that any proposer is only able to propose the value of the majority (chosen value). If we have that, then, we do not risk the already formed majority from reverting weirdly. i.e. once we have formed a majority, we want it to stick and stay like that. However, it was not 100% clear to me why property $P2^c$ satisfied that requirement. I kind of see why (a) is a nice property to have, since, having (a) means that its safe to issue a new proposal $(n, v)$ since we contacted some majority $S$ and none of them had accepted anything in a time earlier than now $n$. So, if a majority had formed we would have seen at least one value and we did not see anything accepted, its safe to propose something since a majority has not formed.

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

$P2^c\implies P2^b$ since $P2^c\iff (a)\lor (b)$ and the logical statement $(a)\lor(b) \implies P2^b$ is equivalent to $(a)\implies P2^b\land (b)\implies P2^b$.

Let's consider $(a)$. If no acceptor in $S$ has accepted anything below $n$, then $P2^b$ is trivially satisfied (the implication predicate is false).

Otherwise, assume $(b)$. Then there exists a highest-numbered accepted value $(v, n)$ for some acceptor within $S$, which the proposer will decide to send as an accept request. Thus $v$ must have been chosen already, since an acceptor had it.


Example on Referential transparency (wikipedia) I have a rather foolish question on an example
explaining the idea behind Referential transparency
Here is given an example i not understand:

Consider a function that returns the input from some source.
In pseudocode, a call to this function might be GetInput(Source)
where Source might identify a particular disk file,
the keyboard, etc. Even with identical values of Source,
the successive return values will be different.
Therefore, function GetInput() is neither deterministic nor
referentially transparent.

I'm confused about the claim that
even with identical values of (variable) Source,
the successive return values will be different.
Eg if I tap an 'a' on my keyboard and apply GetInput(Source),
it gives my 'a' as output. Then I tap again an 'a',
which of course is identical to my previuos input.
Next application of GetInput(Source) gives me again 'a'.
Therefore I not understand how is it possible that
GetInput(Source1) and GetInput(Source2) might give
different values if the two imputs Source1 and Source2
are identical. Sorry, if it's too dumb, but I not understand
this quoted example.

If Source refers to the keyboard, and the user types a the first time but b the second time, then GetInput(Source) will not return the same value both times.
It's impossible to replace GetInput(Source) by its value without changing the meaning of the program, because there are many possible values, depending on the actions of the user. To replace GetInput(Source) with a would be wrong if the user decides to press b.
An example of a consequence of the fact that GetInput(Source) is not referentially transparent is that if the program calls this twice, which call returns a and which calls return b depends on the order in which the calls are evaluated (or more precisely, on the order in which the calls get their input from the keyboard: you have to get down to this level of detail to be sure).


How to make a directed graph in python? I am working on my own personal project. I took an intro to coding class last semester so I have been exposed to coding but I am still lost with it.
Basically, for my project, I want to build a web map (I'm not even sure if that's the right word for it) using python. Here is an example.

Basically, some numbers will have arrows leading to them and others will have arrows leading out of them. I was wondering if maybe someone knew of any libraries that generated something like this. If not, I was wondering if anyone had any advice on where to start. Or at least can tell me the actual name for this type of graph because I'm not sure if it's actually called a web graph.
Thank you all :)

This looks like a directed graph. For a Python graph library, you can have a look at networkx. There are other libraries too, like igraph and graph-tool.


Computing min and max using median of 3 elements How can I write an O(n)-time algorithm to find the minimum and maximum,  given a list of n elements drawn from a totally ordered set using the subroutine median3(x,y,z) which returns the index of three elements x,y,z?  You are not allowed to read or compare the elements directly; the only operation that is allowed is invoke the median3 subroutine.

Let the list be $x_1,\ldots,x_n$. The algorithm is as follows:

Let $S = \{x_1,x_2\}$.
For $i = 3,\ldots, n$:

Add $x_i$ to $S$.
Compute the median of $S$, and remove it from $S$.

Output $S$.

I'll let you figure out why this works.

Note that we cannot possibly tell which is the minimum and which is the maximum. Indeed, $\operatorname{median3}$ works the same for both the original order and its reverse.


How can I measure the usability of a catalogue? This question might seems vague but heres the context:

When we are focusing on HCI we would most likely be interested on knowing first how the user usually deals with a certain object. We then try to see how our system could take away one of the tasks he would do himself and try to do it itself.

The object of my interest here is a simple paper catalogue. How would you measure its usability (paper one).
Then, how would you map it to a system interface? How would you measure the usability now on the system?
How would you compare the two usabilities measures?

This question narrows down this approach which is suggested on Stones book - User Interface and Evaluation.

What the catalogue is about is not the point, that why I left it without a description: To avoid suggestions trying to measure what the catalogue is about. My focus here is on the particular mapping of this kind of object on the real world as a simple paper and when it is mapped to a system interface. Assume the catalogue to consist of rows and tables, where each matching row and table gives you a suggestion and you must first reason about each row and each column to see if it suits you (Perhaps you would suggest another template for the catalogue?).

In the past I worked on usability of interfaces in the information retrieval area, so I give you some practical ideas on how to measure the usability.

You didn't give details of what a "catalogue" is, so I will assume that a user has a problem (or need) and he is searching your catalogue (in paper or electronic format) for one or more solutions.

Then you can build a set of problems $P = \{p_1,...,p_n\}$, and for each problem a set $S^i$ of (possibly weighted) correct solutions: $S^i = \{ s^{i}_1,...,s^{i}_m\}$.

Then you can setup a test with real users.

Every user must solve all the problems in $P$ (in shuffled order) using your catalogue, in one of the two format (paper or electronic).

For each problem, you measure the time spent solving it. At the end you ask the users to give some judgements of satisfaction (using weighted values) on the two catalogues (covering different aspects of satisfaction, for example: "Do you think the catalogue helped you?", "Do you think it is easy to learn how to use it",  ....)

Then you can measure (and compare) the usability of the two catalogues in term of:

standard precision and recall of the results found for each problem $p_i$. Precision: number of correct solutions among the total number of answers; recall: number of correct solutions found among the total number of correct solutions in $S^i$
time spent for solving each problem $p_i$ (efficiency of the system);
user satisfaction

For what concerns the mapping between a paper catalogue to a system interface, you can "record" what users do during their searches on the paper catalogue, then try to "simulate" the actions of those users that performed better using an expert system (see expert system design).


What would be the over all speed-up achieved? Suppose we are using a dual core processor and we run 2 applications (1 with 80% resource requirements and the other with 20% resource requirements).Now the first program is parallelizable for 40% and the second one not parallelizable.My question is what would be the speed up achieved in this case.By speed-up i mean the ratio between the execution times before and after parallelization.

Hint: Look up Amdahl's Law on your favorite search engine and plug your question into the equation you find.


Algorithm Analysis of Insertion Sort Why is the recurrence formula for insertion sort is T(n-1) + n?

I understand the T(n-1) part but the why does the cost for merging results is n or linear. Do we have to merge in insertion sort?

Here is a recursive version of insertion sort:

Input: array $A_1,\ldots,A_n$

If $n = 1$, output $A_1$. Otherwise, continue.
Recursively sort $A_1,\ldots,A_{n-1}$ into $B_1,\ldots,B_{n-1}$.
Insert $A_n$ into $B$.
Output $B$.

If we denote by $T(n)$ the running time for arrays of length $n$,
then step 2 takes time $T(n-1)$, whereas step 3 takes time $O(n)$. Combined, we get the recurrence $T(n) = T(n-1) + O(n)$, with base case $T(1) = O(1)$, corresponding to step 1.


Are all finitely recursive context free languages parseable with a regexp? Let's say I have a context free language. It can be recognised by a pushdown automaton. Chances are it can't be parsed with a regular expression, as regular expressions are not as powerful as pushdown automata.

Now, let's put an additional constraint on the language: the maximum recursion amount must be finite.

Because the stack size has an upper bound in this case, my understanding is that there are finite number of stack configurations reachable. This means I could number them 0, 1, 2, 3, ..., N. So, I should be able to create a deterministic finite automaton (DFA) with states 0, 1, 2, 3, ..., N that recognises the same language that the pushdown automaton recognises.

Now, if I'm able to create an equivalent DFA, doesn't it mean that there exists a regular expression that can parse the context-free language with maximum recursion amount?

So, my theory is that all context-free languages that have a maximum recursion amount can be parsed with regular expressions. Is this theory correct? Of course, the theory says nothing about the complexity of the regular expression, it just says such a regular expression should exist.

So, in other words: if your stack memory is limited, a regexp can do the job of a HTML/XML parser!

In principle, isn't it true that computers with finite memory are actually DFAs and not Turning machines?

We can take it even further: if we put a limit on the size of the HTML/XML, say 1PB, then there is only a finite number of them, so we can trivially parse them in $O(1)$ using a giant look-up table. However, that doesn't seem to tell us much about the complexity of parsing HTML/XML in practice.

The issue at stake here is modeling. A good model abstracts away the salient points of a real world situation in a way that makes the situation amenable to mathematical inquiry. Modeling HTML/XMLs as instances of arbitrarily recursing language forms a better model in practice than your suggestion or my suggestion.


Covering maximal number of sets using fixed number of elements I've encountered some problem which seems general enough to have already been solved.

There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$.

For every $1 \leq j < k$ we need to find a subset $O' \subset O$ of size $j$ maximizing the number of sets $A_i$ contained in it.

What is the best algorithm to solve this? I've been thinking about reducing it to a problem in graphs or flow networks but still haven't arrived at a solution.

Your problem is essentially Minimum $k$-Union. In this problem (switching from $k$ to $\ell$), you want to find $\ell$ sets out of $A_1,\ldots,A_t$ which together cover the least number of elements. Denoting by $f(\ell)$ the solution of this problem and by $g(j)$ the solution of your problem, we have
$$
f(\ell) \leq j \Longleftrightarrow \ell \leq g(j).
$$
In other words, $g(j)$ is the maximal $\ell$ such that $f(\ell) \leq j$.

Unfortunately, Minimum $k$-Union is NP-hard. You can find some links in this question on StackOverflow.


Unique tilings of squares We want to tile $m\times m$-square using two types of tiles: $1 \times 1$-square tile and $2 \times 2$-square tile such that every underlying square is covered without overlapping. Let us define a function $f(n)$ that gives the size of largest uniquely tillable square using $n$ $1\times 1$-squares and any number of $2 \times 2$-squares.

Is this function computable? What is the algorithm?

EDIT1: Based on Steven's answer, unique tiling means that there is one way to place the $2 \times 2$-squares inside the $m \times m$-square with a unique configuration for the positions of the $n$ $1 \times 1$-squares inside the $m \times  m$-square.

Here's an argument to prove my speculation in comments that no such unique tilings exist for any non-square $n\gt 5$.  Firstly, as noted by Sasho in comments, $n$ must be restricted, because no such tilings exist if $n\equiv2$ or $3\pmod 4$.  If $n$ is a perfect square $n=k^2$ then obviously the $k\times k$ square is uniquely tileable, so $f(n)$ is clearly defined and non-zero in these cases.  To complete the argument, it just remains to show that no tiling involving $1$ or more $2\times 2$ tiles can be unique.

First, consider the case $n\equiv 0\pmod 4$, say $n=4k$.  If we have a tiling of an $m\times m$ square using $n\ 1\times 1$ tiles, obviously $m$ must be even, say $m=2j$; then we can construct tilings by building a $j\times j$ tiling of $2\times2$ tiles and then replacing $k$ of these by 'blocks' of four $1\times 1$ tiles.  It's clear that different replacements can always lead to distinct tilings except in the cases $m=4, n=12$ or $m=4, n=4$ where there's either a single $2\times 2$ tile or a single 'block of four' left over; in these cases, though, there's a different inequivalent tiling, one which puts a $2\times 2$ tile in the middle of an edge rather than in a corner.

Finally, suppose $n\equiv 1\pmod 4$, in particular presume $n=4t+1$ (and with $t\gt 1$ to prevent a slightly trivial case where there's simply 'not enough room' in the square for the following argument to go through).  Then no square of size $(2t+1)^2$ or smaller can be uniquely tileable: consider a tiling with $1\times 1$ tiles across the top of the square and down the right of the square (with any extra $1\times 1$ tiles just tucked onto the right side — they can't affect the argument).  Now the $2\times 3$ 'block' in the top-left of the square (consisting of the two $1\times 1$ tiles on the top and the $2\times 2$ tile beneath them) can be 'flipped' to produce a tiling that will necessarily be different from the tiling we've constructed.  Finally, no square of size larger than $(2t+1)^2$ can be tileable at all: suppose we're trying to tile a square of size $(2s+1)^2$ for $s\gt t$; then by the pigeonhole principle we can't fit any more than $s^2\ 2\times 2$ tiles onto the square, which means that there are $(2s+1)^2-4s^2 = 4s^2+4s+1-4s^2=4s+1$ squares left over - but since $s\gt t$, $4s+1\gt 4t+1=n$, the number of $1\times 1$ tiles we have available.

Thus, the only unique tilings that exist for $n\gt 5$ are those that use no $2\times 2$ tiles at all, and $f(n)$ is only non-zero when $n$ is a square (in which case it equals $\sqrt{n}$).


Start / End-Point in TSP - How to consider in an algorithm I moved my question from Theoretical Computer Science to this site - proposed by one of the users there - and I'm hoping don't be off-topic again.

At my university, I had chosen to write a term paper about Inventory Routing Problem (IRP).
To get comfortable with this topic (I'm a software engineer), I started with some simpler problems like Traveling Salesman Problem (TSP) and afterwards with the Vehicle Routing Problem (VRP) which can be defined as simplified IRP problems.

To solve these kind of problems, I wrote an Ant Colony System algorithm with some adaption to the specific problem.
But one thing I'm pretty unsure is how to deal with the start and end node of a TSP?
Most literature have a strong constraint, that the depot (start/end node) has to be the same and is determined, which makes sense.
But the algorithms (heuristics) just cover finding the shortest path.
A lot of algorithms determines the starting point randomly.
Are there any disadvantages if I define the starting point as fix?
But the bigger question is can I add the last point (starting point) independently of the found route to calculate the total costs?

Let's say the algorithm find the cheapest way with D -> 2 -> 3 -> 1 (-> D) but recalculating these manually results in D -> 2 -> 1 -> 3 -> D because 1 -> 3 -> Dis faster than 3 -> 1 -> D.
But how I have to include a fixed ending point in my algorithm?
I guess it's independent of which specific algorithm.

If you don't understand my question please leave a comment and I try to rewrite it =)

The result of any algorithm for TSP is a tour, that is a cycle in the graph. When translating that answer into practice, you can pick any node as starting point without changing the cost of the tour at all.


Turing machine accepts any word Let M be a Turing-machine with tape alphabet = {0, 1} that does not
  move beyond the first 64 cells of its tape. Is the problem "Does M
  accept any word?" decidable?

I would say it does not accept any word because we can have words longer than 64 characters.
I would say it does because if it accepts any word, we don't care about the length. It always goes into accepting state.

Can someone please explain this to me?

Let $P = \{ w \in \{ 0,1 \} \mid |w| \le 64 \land w \in L(M) \}$. Since $P$ contains only words over an alphabet (i.e., a finite set) and all words in $P$ have bounded length, $P$ is finite. Moreover, any word $w \in \{0,1\}^\ast$ with length $|w| > 64$ is in $L(M)$ if and only if there is a prefix of $w$ which is in $P$. Thus, to decide $L(M)$, we only need to check whether the input has a prefix out of finitely many possibilities (i.e., those in $P$).

Hence, $L(M)$ is not only decidable, it is decidable in constant time.

Note this construction does not require any knowledge of $M$ whatsoever (in particular, there is no need to simulate $M$). We only need to show the existence of a TM which decides $L(M)$, not actually construct one.


NP-Completeness: A question about reduction and hardness I am trying to understand the definition / meaning of reduction.

Is it correct to say that the statement "Problem $A$ reduces to Problem $B$ in $x$-time" is the same as writing $A \leq_{x} B$? For example $\text{SAT} \leq_{polynomial} \text{3-SAT}$.
If we are reducing problem $A$ to $B$ in $x$-time, does it mean that you take an instance in problem $A$, and modify it such that it becomes a valid input for problem $B$, such that the modification is done with $x$ time complexity?

As far as I know, the first point is correct. For the second point you missed the fact that "solve $A$ with the given instance iff solve $B$ with the created instance".


Using the appropriate machine learning algorithm I am not sure if this is the right forum to ask this.

I have some data of the houses, like their size(in square meters), if they use aircondition, how many residents live in, I have their electricity consumption as well.
I want to train any Machine Learning Algorithm to the dataset above, in order to create a model that estimates the houses consumption.

I tried many different algorithms (using weka), but I did not have good results.
I was said that SVMs could solve this problem, with the right preprocessing. However, i did not have good results either.

Can anyone help me, in the way i should approach this problem?

Thanks in advance

There are not an appropiate algorithm for each problem, you must to research and compare results between your algorithms or techniques with an error measure (MSE, etc.).

In general, machine learning algorithms are empiric models (approximated functions). There are arised from the problem itself and a set of suppositions with no revealing the hidden model (many of them, are non-linear problems).

First of all, is necessary to be careful with the variables in the input and output layer, this can be categorical, symbolic or numeric (best case), and you have to model your own representation to preserve some features of interest (topology, etc.)

I will recommend you first of all, try with a multiple linear regression and explore the eventual correlations between variables to find any linear dependence, before do something.

Its a very good practice, normalize the numerical data in the training process, to get a well fitted bias.

Then, for instance, you could try with a multilayer feed forward neural network or SVD o fuzzy inference system.

I understand the machine learning problem as a research with a set of methods to get a good explanation for a given problem, and improvements on that methods.


A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?) I am trying to understand the proof for this theorem (theorem 4.22 of the book 'An introduction to the theory of computation'):
A language is decidable iff it is Turing-recognizable and co-Turing-recognizable.

The first direction is OK. But the other is not, namely:

What I don't understand is why the author assumed that M will halt. We have that A is Turing-recognizable, and thus we are not sure we have a machine that decides it (and thus halts). Same for the complement of A which is also Turing-recognizable.
Thanks in advance

Since both $A$ and $\overline A$ are recognizable, you know that for any input $x$, either

$x \in A$, which means that $T_A$ will halt on input $x$, or
$x \notin A$, which means that $x \in \overline A$ which means that $T_{\overline A}$ will halt on input $x$.

The "trick" here is to run $T_A$ and $T_{\overline A}$ "simultaneously", which means that if any of $T_A$ or $T_{\overline A}$ halts after $k$ steps, then your new machine will halt after $2k$ steps.

If you don't like "simultaneously", you can for each integer $i$ from 0 and up, run $T_A(x)$ for $i$ steps, then run $T_{\overline A}(x)$ for $i$ steps.
The latter is simpler to "program" on a single-taped Turing machine, but the former is quite okay to implement on a two-taped Turing machine.


Machines whose languages are their own encoding Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable?

I tried diagonalization but can only prove that $R = \{\langle M \rangle \mid M \text{ is a Turing Machine and } \langle M \rangle \notin L(M)\}$ is not recognizable, which does not seem to help in this case...

Using the recursion theorem, for any Turing machine $T$ you can construct a Turing machine $M$ such that on input $\langle M \rangle$, $M$ executes $T$ (on the empty tape), and otherwise $M$ immediately rejects. You can use this to show that $S$ is not decidable. Using the same ideas you can explore its recognizability and co-recognizability.


Why are regular tree languages closed under intersection, but deterministic context free languages are not closed under intersection? I am looking for intuition here. Essentially, I understand that the set of parse trees from a context free grammar forms a regular tree language. I also understand that regular tree languages are closed under union, intersection and complement. Now, why are deterministic context free languages not closed under intersection? (the intersection of DCFL need not even be in CFL) but intersection of regular tree languages are closed under intersection? (I get why DCFL union is not in DCFL -- because there is ambiguity).

The intuition is that the strings of a context-free language are formed by the "frontier" (the leaves) of the derivation trees. The trees themselves are no longer directly visible.
Thus, the intersection of two tree languages consists of the trees the structure of which belongs to two tree grammars. We must be able to map productions of both grammars onto the same tree. Moreover, the tree is visible, we do not have to guess it.
For the intersection of two context-free languages we need two trees, one for each grammar and we only need the two frontiers to be the same. Hence we can find languages like $\{a^nb^nc^n \mid n\ge 1\}$ which is the intersection of two context-free grammars. The first one has a tree structure that verifies that the $a$'s and $b$'s are equal, while the second grammar checks the $b$'s and $c$'s with another tree structure. Also we need to 'guess' the two trees as we only 'see' their frontiers.
I do not think that determinism is essential in this discussion.


How can the Operating System run on the same chip it is supposed to be managing? From my readings about Operating Systems (reading the basic material on Wikipedia, tech sites, etc) I've learned that the Operating System is a program that allows programs and applications to interact with the hardware in an efficient and safe way.

However I'm confused about how the Operating System oversees the computer's operation when it itself needs to be operated.

What do I mean? Well, the way I would imagine an Operating System to work, is that on a computer, there would be two CPUs. One that runs the OS all the time, and another that the OS uses to run the computer.
However, it turns out that the OS is running on the same CPU that the other processes are. This is like a manager having to work on the same production line as his employees, and only gets to use the power tools when another employee is done with them. He would not be a very effective manager, since he wouldn't have the ability to issue orders if his employee is even slightly undisciplined.

So how can it be that the OS only runs part of the time on the same CPU that has to be shared between all the other processes? How does this end up working out?

In their most primitive form, operating systems rely on processes being well-behaved and handing control back to the operating system from time-to-time. If a process is not well-behaved, then indeed it can happen that the operating system freezes.

Most CPU's however, have interrupts: an interrupt pauses the current process (preemption) and hands control back to the operating system. You can schedule interrupts to happen at specific intervals, or be triggered externally (for instance pushing the reset button).

Basically, the CPU switches back and forth between running the OS and running processes at a blazingly fast speed. Furthermore, CPU's have "user mode" and "kernel mode". Processes run in user mode and the OS runs in kernel mode. Running in user mode prevents a process from executing restricted commands (such as IO). If a process wants to write to the disk, it has to ask the OS to do so. The OS switches to kernel mode and does the write on behalf of the process (after making sure the process has the required permissions).


error computation in multi layered perceptron I was reading about Multi Layered Perceptron(MLP) and how can we learn pattern using it. Algorithm was stated as

Initiate all weight to small values. Compute activation of each
neuron
using sigmoid function. Compute the error at the output layer using
$\delta_{ok} = (t_{k} - y_{k})y_{k}(1-y_{k})$
compute error in hidden layer(s) using
$\delta_{hj} = a_{j}(1 -a_{j})\sum_{k}w_{jk}\delta_{ok}$
update output layer using using
$w_{jk} := w_{jk} + \eta\delta_{ok}a_{j} ^{hidden}$
and hidden layer weight using
$v_{ij} := v_{ij} + \eta\delta_{hj}x_{i}$

Where $a_{j}$ is activation function, $t_{k}$ is target function,$y_{k}$ is output function and $w_{jk}$ is weight of neuron between $j$ and $k$

My question is that how do we get that $\delta_{ok}$? and from where do we get $\delta_{hj}$? How do we know this is error? where does chain rule from differential calculus plays a role here?

How do we get that $\delta_{ok}$?

You calculate the gradient of the network . Have a look at "Tom Mitchel: Machine Learning" if you want to see it in detail. In short, your weight update rule is

$$w \gets w + \Delta w$$
with the $j$-th component of the weight vector update being
$$\Delta w^{(j)} = - \eta \frac{\partial E}{\partial w^{(j)}}$$
where $\eta \in \mathbb{R}_+$ is the learning rate and $E$ is the error of your network.

$\delta_{ok}$ is just $\frac{\partial E}{\partial w^{(o,k)}}$. So I guess $o$ is an output neuron and $k$ a neuron of the last hidden layer.

Where does the chain rule play a role?

The chain rule is applied to compute the gradient. This is where the "backpropagation" comes from. You first calculate the gradient of the last weights, then the weights before, ... This is done by applying the chain rule to the error of the network.

Note

The weight initialization is not only small, but it has to be different for the different weights of one layer. Typically one chooses (pseudo)random weights.

See: Glorotm, Benigo: Understanding the difficulty of training deep feedforward neural networks


Lower-order term constraints and wrong guess I'm a self-taught and I'm studying from CLRS.
I'm having difficulty with this recurrence relation:
$$T(n)=3T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + n$$

The problem is that I can "prove" that $T(n) = \mathcal{O}(n)$. It's absurd.
My inductive hypothesis about $\mathcal{O}(n)$ is:
$$\exists c \gt 0 \,\,\exists n_0 \gt 0 \,\,\exists b \ge 0 \quad\forall n_0\le k\lt n \quad T(k) \le ck - bn \le ck $$

From here I haven't problem during the "proof":
$$\begin{align}
T(n) &\le 3\left(c\left\lfloor{\frac{n}{2}}\right\rfloor - bn\right) + n
\\ &\le 3\left(c\frac{n}{2} - bn\right) + n
\\ &= \frac{3}{2}cn - 3bn + n
\\ &= \frac{3}{2}cn -n(3b - 1) \qquad\qquad (1st)
\\ &\le cn
\end{align}$$

The latter holds $\forall b \ge \frac{c+2}{6}$ and it comes from:
$$\frac{3}{2}cn - n(3b - 1) \le cn$$

--EDIT--
It's also easy to prove that
$$(1st) \le cn - bn$$
It holds $\forall b \ge \frac{c+2}{4}$
So $$T(n) \le cn - bn$$
--END EDIT--

So I think that the hypotheses are wrong. Probably I misunderstanding subtraction of lower-order term. What are the constraints to apply this technique? Only that $T(k) \gt 0$? In this recurrence the latter seems valid.

Synthesis: https://cs.stackexchange.com/questions/65549/lower-order-term-constraints-and-wrong-guess/65579?noredirect=1#comment139380_65579

First of all, the way you state the induction hypothesis is a bit strange, and it definitely doesn't prove that $T(n) = O(n)$. Assuming that the induction is on $n$, what your induction hypothesis states (more or less) is that for every $n$ there exists $C$ such that $T(k) \leq Ck$ for all $k \leq n$. The function $T(n) = n^2$ satisfies this, with $C = n$.

What you really want to do is to fix the parameters $b,c,n_0$ in advance. In other words, you want to prove
$$
 \exists b,c,n_0 \, \forall n \, \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn.
$$
You first instantiate $b,c,n_0$, and then you prove only the following part by induction:
$$
\forall n \, \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn.
$$
At each step of the induction, you are proving
$$
\forall n_0 \leq k \leq n\colon T(k) \leq ck - bn
$$
for the current value of $n$.

Now for your mistake. Your induction hypothesis states that for all $k \leq n$,
$$ T(k) \leq ck - bn. $$
However, in the inductive step, you only prove
$$ T(k) \leq ck. $$
Also, you only prove it for $k = n$, despite the form of your actual induction hypothesis.

Indeed, it is very strange that your inductive hypothesis gives an upper bound on $T(k)$ which depends on $n$. This is quite unorthodox. Usually the upper bound only depends on $k$. Moreover, you are not really subtracting a lower-order term: $n \neq o(k)$!

Here is what an application of subtracting a lower-order term usually looks like. Suppose that we want to prove that $T(n) = O(n)$. Then you find $b,c,n_0$ and prove the following by induction:

$$ \forall n \geq n_0\colon T(n) \leq bn - c\log n.$$

Note that there is no $k$ here, and that $\log n = o(n)$ is indeed of lower order.


Is occurrence typing (flow-sensitive typing) a form of dependent typing? I take occurrence typing to be typing that "... allows the type system to ascribe more precise types based on whether a [check] succeeds or fails." (adapted from the Racket docs with "predicate check" replaced with "check")
Here's a TypeScript example:
function foo(x: string | number) {
    switch (typeof x) {
        case "string":
            // the type of x is `string` here:
            x.length
            break
         case "number":
            // the type of x is `number` here:
            x * 3
            break
    }
}

playground link
I take "dependent types" to mean "types that depend on terms". reference reference
The type of x (a type) depends on x (a term). So is there dependent typing in the example above? More generally, is occurrence typing a form of dependent typing?
I could see an argument that the answer is "no" if we interpret "dependency" such that it is expressed via binding. So then a "dependent type" would be a type T x where  T is a type and x is a term. But then maybe even on this definition occurrence typing counts as dependent typing, if we allow T to be something fancy like a type-level x -> if x is a string then string else number.

No, I would not consider this a dependent type.  The type of x does not depend on the value of x.
I suppose you could say that the type of the expression x depends on the type of the variable x, but that doesn't make this dependent typing.
You link to Wikipedia, but the Wikipedia article on dependent types say "a dependent type is a type whose definition depends on a value" and says " The return type of a dependent function may depend on the value (not just type) of one of its arguments" and "A dependent pair may have a second value of which the type depends on the first value".  Here the type of x does not depend on values; only on the types of the variables.  Beware that these English sentences describing terms like "dependent types" or "occurrence types" are not to be taken too seriously and you need to look at the precise mathematical formalism if you want to be precise.
I would not consider the feature you describe as dependent typing.  Rather, I would consider it an instance of flow-sensitive typing.


Modification of Hamilton Path Although I know that the Hamilton Path problem is ${\sf NP}$-complete, I think the following variant can be solved in polynomial time:

  Given a planar graph with vertex set $V$, edge set $E$, start node $S$ and target node $F$,
  our task is to find the Hamiltonian path from $S$ to $F$ or write that the path doesn't exist.

  Last condition: In the path, in addition to selecting the directly connected vertices,
  we can also choose those connected to exactly one neighbor.

  Edit: The degree of any vertex is at most four ($\deg(v_i) \le 4$).

Does anyone have any ideas how to prove that this can be solved in polynomial time?

It can be hard to understand, so I will give an example:

In the left example, for $S=1,F=12$, the solution is the path $1, 11, 8, 7, 5, 9, 2, 10, 4, 6, 3, 12$.

In the right example, for $S=1,F=15$, there is no Hamiltonian path.

Perhaps the problem is still NP-complete; this reduction should work: given a planar graph $G$ and two nodes $s$ and $t$ (start and end), expand it to a new graph $G'$ in this way: for every node $u$ of $G$ add two nodes $u_1,u_2$ and two edges: $(u,u_1),(u_1,u_2)$ (informally add a tail made with two new nodes).

There are only two ways to traverse the three node gadget with a valid Hamiltonian path (i.e. cover the three nodes):

a) $out \rightarrow u \rightarrow u_2 \rightarrow u_1 \rightarrow out$ and its reverse

b) $out \rightarrow u_1 \rightarrow u_2 \rightarrow u \rightarrow out$

In both cases the node $u$ must be traversed and cannot be reused in another part of the path.

Now, in order to force one of the two traversals in every node, add two tails to $s$: $(s,s_1), (s_1,s_2)$ and $(s,s_3), (s_3,s_4)$ and pick as starting node of $G'$ the node $s_1$. The only way to traverse and leave $s$ is $s_1 \rightarrow s_2 \rightarrow s \rightarrow s4 \rightarrow s3 \rightarrow out$. This forces traversal (a) on all remaining nodes (gadgets) of $G'$. Pick $t_2$ as the ending node in $G'$.

So the original graph $G$ has an Hamiltonian path from $s$ to $t$ if and only if $G'$ has a "modified" (one node jumps allowed) Hamiltonian path from $s_2$ to $t_2$.

EDIT:

If $deg(v_i) \leq 4$ the above reduction still works because Hamiltonian path is NP-complete even in planar cubic graphs. In a planr cubic graph $deg(v_i) = 3$, so nodes can be extended with the tails as described above. If the starting node has degree 3, just add another node $s'$, an edge $(s,s')$ and add two tails to $s'$.
But, if $deg(v_i) \leq 3$ then the problem falls in $\mathsf{P}$, the following algorithm should work (but I didn't think about it too much):

calculate the shortest path from $s$ to $t$: $s \rightarrow u_1 \rightarrow ... \rightarrow u_m \rightarrow t$, then expand the path using a depth first search from every node; this will lead to a spanning tree having the shortest path as a "backbone". For each $u_i$ of the shortest path there is only one branch $u_i,b_1,b_2,...,b_k$(because the degree of $v_i$ is $\leq 3$) and it can be covered using jumps:

$u_i > b_2 > b_4 > ... > b_k > b_{k-1} > ... > b_3 > b_1 > u_{i+1}$ if $k$ is even
$u_i > b_2 > b_4 > ... > b_{k-1} > b_k > b_{k-2}... > b_3 > b_1 > u_{i+1}$ if $k$ is odd

The only problem is if $s$ and/or $t$ have degree 3. In that case the above procedure must be repeated several times using only one incident edge of $s$ (and eventually only one incident edge of $t$).

In order to formally prove that the algorithm is correct one must prove that every Hamiltonian path (with jumps) from $s$ to $t$ in a $deg(v_i) \leq 3, deg(s)=1, deg(t)=1$ graph can be transformed to an Hamiltonian path (with jumps) of the above form (a spanning tree from the shortest path). It is not immediate but it seems intuitive (but perhaps I'm just wandering :).


Do algorithms always have a return value? I learned that algorithms written in programming languages always return some value, not necessarily an input value.

But, if the return type of the main function is void, then does the algorithm return any value?

Actually, you have asked three different questions:
1) [Does algorithm always have a return value?[sic]"

The algorithm by default is not a function/method (or to say program), but it could be. Sticking to the stringent definition of the algorithm. An algorithm is a set of instruction for accomplishing a task. Every piece of code could be called an algorithm e.g. 1) defining a variable or 2) writing a logic for a loop is also an algorithm. So, addressing to your original question "Does algorithm always have a return value?" answer is 'NO'. In similar situations like 1), and 2) an algorithm does not return a value.

2) "I learned that the algorithm written in programming langauge always have a return value, not necessarily an input value.[sic]"

If you wish to convert/write your pseudo code to a specific program in some programming language e.g. C/C++. Then every program should consist of at least one function. Programming languages like C/C++/JAVA/C# etc., provides default function call Main() in which you can call user defined function(s) (or main itself).

So, reaching the end of a function other than main is equivalent to return;. reaching the end of the main function is equivalent to return 0;. reaching the end of any other value-returning function is undefined behavior, but only if the result of the function is used in an expression.

In certain languages like C/C++ there are features which allows function to defined as 'no-return' function.

#include <stdlib.h>
#include <stdio.h>
#include <stdnoreturn.h>

noreturn void stop_now(int i)
{
    if (i > 0) exit(i);
}
int main(void)
{
     puts("Preparing to stop...");
     stop_now(2);
     puts("This code is never executed.");
}

The 'noreturn' keyword appears in a function declaration and specifies that the function does not return by executing the return statement or by reaching the end of the function body. This type of adventure could be costly and can cause undefined behaviour to your C/C++ program.

P.S. When function/method have return type as 'void' they do not return any value, or anything. Control simply returns. It is also important to learn that void doesn't mean nothing. void is a type to represent nothing. That is a subtle difference : the representation is still required, even though it represents nothing.

3) "But it we use the main function with void return value, does that algorithm have a return value?[sic]"

P.S. If you define return type of main function as 'void' then it does not have any return value. You can actually omite 'return' keyword or simply type 'return' with no expression (or even 0).


Incorporating event handlers In IDE's we can drag a small continuous collection of pixels in a particular configuration to a place on the screen .This collection of pixels are called as controls .

Corresponding to every control, there are various kinds of event handlers,like for a button , some subroutines for events like "double click" , "single click" are available ,for a grid there might be "right click ", "gaining mouse focus" event handlers might be available .

The collection of available event responding subroutines,from what I could conclude , further depend on the framework or library we are using.

Now let us imagine that we have certain hardware with us and only one programming language available and we are accommodating some aliens in this world for whom , nose, is a very important sense organ for communication .Avoiding the concerns of scientific  feasibility of such creatures let us say that to provide input to anything they exhale and inhale air into some device .
And to meet their requirements we might need programs that can manipulate the fragrance that they are smelling , like ,let's say we need a computer program for a messaging app that is to be designed for them to be able to emit the smell of rose at the receiver's end when the sender scratches the screen and many more .

Now given such a situation , if I want to design a GUI for them or may be (OUI,olfactory user Interface ) how can I make my systems compatible with their method of input and output .I mean how can I design event handlers for them like , "One nostril snort event ", "double nostril snort event ","deep inhale event " and many more that we can imagine .

What are the changes that I would require :

Do I need to add some new things in my programming language ?
Do I need to change my hardware (counting out their input device ,namely ,snake :P) ?
Do I need to change my OS ?

P.S :  I asked this question ,because,to put in the most general manner and basically  I wanted to deconstruct and see from the bottom , how can computer programs(including the OS ,which in essence is also a computer program ) control hardware and as such I might get a better idea on how to direct myself in learning about all this.

Those kinds of aliens presumably wouldn't use a GUI.  A GUI is a graphical user interface, i.e., directed at the visual senses.  Your aliens have no sight, and wouldn't use such a user interface.  They'd use something else.

The user interface is programmed as part of the software application.  So, you wouldn't necessarily need to change the programming language or the hardware or the OS -- just the application (and its libraries).  (Of course, you would need additional peripherals to emit smells etc., but you say you're counting that out -- apart from that, there would be no changes to hardware needed.)


Optimization of Church-encoded booleans in System F I can encode booleans in pure lambda calculus like this:

type Bool = forall t. t -> t -> t
true : Bool = \x y -> x
false : Bool = \x y -> y

Is there a procedure to optimize the following "dumb" function

dumb = \(b : Bool) -> b false false

to

dumb = \(b : Bool) -> false

I can imagine this is quite easy in Haskell with an ADT for example.

One way I can think of is counting the inhabitants of the type Bool (2) and then applying the function to both the inhabitants, discovering that the function will have the same result for any argument. This seems quite difficult to do in general though.

Without further assumptions you cannot perform the optimization because it is unsound in general. For example, we could interpret System F in a model that has fixed point operators, in which case there will be elements of Bool that are different from false and true (namely "undefined" ⊥). In such a model, dumb will not be equal to \ b . false because dumb ⊥ = ⊥ but (\b . false) ⊥ = false.

In your question you assumed that we know what it means to "optimize" a function. If we leave aside questions about efficiency, we still have to answer the question what it means for two closed terms in System F to be equal. There are several possibilities:

closed terms $M$ and $N$ are equal if they reduce to the same normal form,
closed terms $M$ and $N$ are equal if they are equal in some preferred model,
closed terms $M$ and $N$ are equal if they are observationally equivalent,
closed terms $M$ and $N$ are equal if they are extensionally equivalent (they give extensionally equivalent results when applied to extensionally equivalent arguments).

Parametricity, which was mentioned in the comments, may be helpful with some of the above. But it's difficult to discuss "optimization" until we know what counts as "equal", or else we cannot tell which optimizations are valid.


Computation equivalence of functional and procedural programming I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural programming (any problem you can solve with one can be solved with another).
I'm curious as to how this conclusion was originally derived, and whether there is a conclusive proof as to this (preferably one that a bit of a newb to lambda calculus like me can understand)
Related:
Why are functional languages Turing complete

One standard way to prove that a language is Turing-complete is to implement a simulator for a Turing machine (or for any other Turing-complete language) in that language.  That is typically straightforward but boring, for most general-purpose languages.
You can find more resources on Turing-completeness in turing-completeness; see especially, e.g., Is there an algorithm for converting Turing machines into equivalent Lambda expressions?.  You might also be interested in Which calculus is based on first-order functions and is Turing complete?, Are there minimum criteria for a programming language being Turing complete?, What does being Turing complete mean?, Are all turing complete languages interchangeable, Clear, complete, proof that a language is Turing Compete?.


The difference between $\beta$-reduction and $let$ These are the reduction rules associated with $\beta$ reduction and $let$:
$$(\lambda x. e_2) e_1 \to_{\beta} e_2 [e_1 / x]$$
$$let \,x = e_1 \textit{ in }e_2 \to e_2 [e_1/x]$$
These reduction rules are very similar.
What is the point of having $let$ as well as $\beta$-reduction?
I can't see why it is of any use.

In the untyped lambda calculus, $\mathsf{let}$ is indeed useless, and most presentations leave it out. But in many typed lambda calculi, $\mathsf{let}$ is useful because it has a more general typing rule.
The best known example is the Hindley-Milner type system, which derives its power from let-polymorphism. In $(\lambda x.e_1) \: e_2$, the expression $e_1$ has one particular type, which is also the type of $x$ when typing $e_1$. But in $\mathsf{let} \: x = e_1 \: \mathsf{in} \: e_2$, $e_1$ can be polymorphic, and the instances of $x$ in $e_1$ can have different specializations of this polymorphic type.


Formal specification; Logical formula * Initial Question *

I'm trying to write a logical formula consists of three Boolean variable C1, C2, C3.

My program takes graph as input and checks properties about them. C1 represents presence of some structural properties of the input graph (graph being strongly connected). If graph have this property, variable C1 is True else its False.

Variable C2 and C3 represent another set of properties involving other program variables.

The property i'm interested is

  If graph have this desired structural property then there is an assignment to program variables that makes C2 & C3 True.

For checking one specific graph i can just say:

SAT (C1 && C2 && C3)

And if there is a satisfying assignment i'm done.

But rather than checking properties of specific graph i'm interested in checking for every graph which have this structural property (represented by C1) also have other properties too (represented by C2,C3).

So I represent graph as arbitrary two dimensional array of size N. So that i can allow my program to iterate over any graph of size N.

Bool Graph[N][N]

I'm using CBMC (C Bounded Model checker) to write and check program.

I want to write this.

  For_all Graph[N][N] s.t C1 $\implies$ There_exists(an assignment) s.t C2 && C3

I'm not sure how to can i write this property? Any help in this regard?

Updated Question : To make question clear as after an answer i thought i was unable to put my point clear.

In my program i'm taking graph as input. based on this graph i'm trying to
make connection that if the graph have some structural property then it
has other properties also.

The structural property is: graph being strongly connected. Other
properties are based on the label of edges and nodes. So to generalize,
other properties depend on program variable x,y,z,.. and Boolean function
f.

I can build this program by using a Boolean variable B1 to inspect whether
graph is strongly connected or not, if its is B1 is True, otherwise False.
and use other Boolean variable B2 and B3 to represent other properties.
Hence both B1 and B2, B3 depend on graph and B2, B3 also depend on other
variables x,y,z,... and Boolean function f.

To check for a single graph i can ask:

SAT (B1 and B2 and B3). if there is an assignment i'm :)

Problem arise when i'm interested not in a particular graph but in every
graph (certain fixed size N). Worst possible try is to generate all graphs
of certain size and check each one by one and make sure that its the case.

The thing i'm trying to achieve is something like this :

For_all graphs G s.t B1 -> There_exist an assignment to (x,y.., f) s.t B2 and B3.

Edited

I want to iterate over all graphs (which i can do making graph arbitrary)

unsigned int Graph[N][N];  // For some specified N

but with that i'm looking to check whether there exists an assignment that makes other property works. If other property were VALID(tautologous) or Contradiction i could have checked easily. But other properties(represented by C2 , C3) are not either a Valid or a contradiction. For example with  SAT (C1 && C2 && C3) and SAT (C1 && !(C2 && C3)) both have a witness.

  I'm interested in iterating and checking that there exists at least one possible assignment for each graph that makes C1 && C2 && C3 true.

If I understand correctly (and I might not), it sounds like maybe the property you are trying to prove is

$$\forall G . C_1(G) \implies (\exists x . C_2(G,x) \land C_3(G,x))$$

where $G$ ranges over all graphs and $x$ ranges over all possible assignments to the program variables.

If that's right, then you can't check this with SAT or with CBMC.  It's a second-order formula, so you need a 2QBF solver to check it.  SAT can help you check properties of the form "$\forall x . F(x)$" and properties of the form "$\exists x . F(x)$", but for properties of the form "$\forall x . \exists y . F(x,y)$" or "$\exists x . \forall y . F(x,y)$", you need 2QBF (or, more generally, QBF).  There do exist 2QBF solvers, but checking 2QBF properties is much harder than checking SAT.

An additional complication is that it sounds like you want to quantify over all graphs of all sizes.

It sounds like you want to verify the following property: for all graphs, if C1 is true, then C2 and C3 are true.

The standard approach is to use assume and assert statements. You first write some assume statements that capture the assumption that the input graph satisfies C1. You then write some assert statements that capture the requirement that the C2 and C3 had better be true. The model checker checks whether there are any inputs that satisfy all the assume statements, and make at least one of the assertions false.

If you were going to use a SAT solver, you would search for a counterexample by writing a boolean formula C1 && not(C2 and C3), then asking the SAT solver to find a satisfying assignment for that formula. If it finds one, that it has found a counterexample to your property. If the formula is unsatisfiable, then your property holds. This all assumes that you are reasoning about graphs of a fixed size.

If the graph is of arbitrary size, then the problem is much harder.  That falls beyond SAT and beyond even QBF, as both SAT and QBF relate to formulas with a fixed (constant) number of boolean variables -- but if you want to reason about arbitrary-sized graphs, there is no encoding of that into a fixed number of boolean variables.  A standard heuristic is to check the property on graphs of size N for a few small values of N (say, for N=1,2,3,4,5,6,... until you run out of patience or the solver starts taking too long).


Context free grammar for $1^k0^{2k}$ I need a hint for writing a context-free grammar for the language $L=\{1^k0^{2k}:k\in \mathbb N\}$. I'm starting to doubt that it can be done for general $k$.

Based on the comments:

$$S \to 1S00 \mid 100$$


Runtime of algorithm to transpose a graph I am working with an algorithm to compute the transpose of a directed graph. Here is a rough overview of the algorithm: For each vertex in the graph, traverse each edge and add an edge from the neighbor to the parent node. The adding of an edge takes constant time, $O(1)$. And I figured, if I am traversing each edge, then the asymptotic run time should be $O(|E|)$. However, the run time of this algorithm is $O(|V| + |E|)$. The only way I can make sense of this is: once it reaches the final level of the tree (the roots), even though the nodes don't have any edges, the for loop will still iterate through those nodes. However, if I am taking this into account, then shouldn't it be $O(|V|)$. Why are we taking both $|V|$ and $|E|$ into account? Can someone can offer some insight to this?

It all depends on how exactly you store the graph. For example:

If you store the graph as an adjacency matrix, the complexity is $\Theta(|V|^2)$.
If you store the graph as a linked list of edges per vertex (i.e., adjacency lists), then the complexity is $\Theta(|V|+|E|)$.
If you store the graph as a linked list of all edges (and don't store the vertices explicitly), then the complexity is $\Theta(|E|)$.

The representations usually used are the first two. I have never heard of the third being used. In most cases, the number of edges exceeds the number of vertices, and so there would be the third method would have no advantage over the second one, but it would have many disadvantages.


Decoding problem and conditional probabilities I'm reading the book by MacKay "Information theory, inference and learning algorithms" and I'm confused by how he introduces the decoding problem for LDPC codes (page 557).

given a channel output $\mathbf{r}$, we wish to find the codeword $\mathbf{t}$ that whose likelihood $P(\mathbf{r}|\mathbf{t})$ is biggest.

I can get on board with that, even if it seems a bit backwards since $\mathbf{r}$ is the evidence we have, so I would be more comfortable if we were trying to find $\mathbf{t}$ that maximizes $P(\mathbf{t}|\mathbf{r})$, and as a matter of fact, he goes on to say

there are two approaches to the decoding problem both of which lead to the generic problem 'find $\mathbf{x}$ that maximizes $$ P^*(\mathbf{x})=P(\mathbf{x})\mathbb{1}[\mathbf{Hx}=\mathbf{z}]$$

he exposes the two points of view in the following page, the first one especially confuses me

the codeword decoding point of view
First, we note the prior distribution over codewords $$ P(\mathbf{t})=\mathbb{1}[\mathbf{Ht}=\mathbf{0}]$$[...]. The posterior distribution over codewords is given by multiplying the prior by the likelihood [...] $$P(\mathbf{t}|\mathbf{r})\propto P(\mathbf{t})P(\mathbf{r}|\mathbf{t}) $$

from the generic decoding problem he gave, it looks like we're actually trying to maximize $P(\mathbf{x})=P(\mathbf{t}|\mathbf{r})$, instead of $P(\mathbf{r}|\mathbf{t})$.
Is it obvious that the two maxima are the same and with the same maximizer? It is not obvious to me since the maximizer $\mathbf{t_0}$ that maximizes $P(\mathbf{r}|\mathbf{t})$ might actually minimize $P(\mathbf{t})$, so the maximizer of $P(\mathbf{t})P(\mathbf{r}|\mathbf{t})$ might be different! I understand that in this case $P(\mathbf{t})$ is uniform, so this shouldn't be a problem, but it seems weird to me that this is simply not stated and I feel like I'm missing something.
Why should we start with the problem of maximizing $P(\mathbf{r}|\mathbf{t})$ and not $P(\mathbf{t}|\mathbf{r})$? Why does he seem to switch after a few sentences? Am I correct in thinking the algorithm presented actually maximizes $P(\mathbf{t}|\mathbf{r})$?
Thank you

Maximizing $P(r|t)$ is known as the Maximum Likelihood (ML) principle, while maximizing $P(t|r)$ is known as the Maximum A Posteriori probability (MAP) principle.

Here are some facts that answer your question:

Optimal decoding (minimizing the probability of error) is achieved by the MAP principle. See p. 152 of the book.
However, using MAP would require a different decoding algorithm for every distribution on $t$. I.e. you would have to adapt decoding to the statistical properties of the source. To avoid this, it is typical to assume a uniform distribution on $t$. In this case, MAP and ML are equivalent because $P(t|r)$ becomes proportional to $P(r|t)$ (see p. 152 again).
I agree with you he should have started with the MAP problem of maximizing $P(t|r)$, since that's the correct goal anyway. But I presume that he is assuming a uniform distribution on $t$, in which case the difference doesn't matter anyway.


Converting a number from N to 0 in binary Trying to solve this problem since 2 days. Still unable to figure out even a basic approach.

Given a number $N$ in binary ($1$ to $10^5$), we need to convert it to $0$ using only 2 operations. Given a binary value of a number with length $M$ ($0$ indexed), we can:

flip the $i$th bit from $0$ to $1$ or $1$ to $0$ only if the $(i+1)$th bit is 1 and all bits at positions from $i+2$ to $M-1$ are NOT $1$, or
flip the rightmost bit unconditionally.

So the problem is to figure out the minimum number of steps to do the conversion.

For example:
if $N=8$,
then its binary representation is $1000$.

So to convert $1000$ to $0000$, the following steps apply:

1 -  1001 (flipping the rightmost bit unconditionally).
2 -  1011 (flipping bit at position 2 as bit at position 3 = 1 and there are no more 1 after it. There are no more characters infact. It is the last character).
3  - 1010 (flipping the rightmost bit unconditionally).
4  - 1110 (flipping the 1st bit as 2nd bit is 1 and no other bits after that are 1)
5  - 1111 (flipping the last bit unconditionally).
6  - 1101 (flipping 2nd bit as 3rd bit is 1 and no other 1 after 3rd bit).
7  - 1100 (flipping the last bit unconditionally).
8  - 0100 (flipping 0th bit as 1st bit is 1 and no other 1 after 1st bit).
9  - 0101 (flipping the last bit unconditionally).
10 - 0111 (flipping 2nd bit as 3rd bit is 1 and no other 1 after 3rd bit).
11 - 0110 (flipping the last bit unconditionally).
12 - 0010 (flipping 1st bit as 2nd bit is 1 and no other 1 after 2nd bit).
13 - 0011 (flipping last bit unconditionally).
14 - 0001 (flipping 2nd but as 3rd bit is 1 and no other bit after 3rd bit).
15 - 0000 (flipping last bit unconditionally).

So the result is $15$ as it took $15$ steps.

Unable to solve this problem. Please help.

I think you can just do a simple breadth-first-search on this. First note that:

There's only one way to do move #1 (you can perform move #1 in one place, if it's at all possible), and doing it multiple times wouldn't result in a loop.
It doesn't make sense to do move #2 twice in a row.

The important thing to do while searching is to note whether the number we've arrived at was by doing move #2 (otherwise we'd get stuck in a loop). So here's a pseudocode:

Put the current number into a queue with flag 0
While the dequeued number is not zero:

If you can do move #1 on the dequeued number then do move #1 and put that in a queue with flag 0
If the dequeued number's flag is 0, then do move #2, and put that in the queue with flag 1


Minimum commands to reach an value Sorry if I am doing it wrong in some way.

Some days ago I have passed trough an technical test in which I had 3 tasks to complete. The tasks were a problem and I have to write an algorithm to solve it.

One of the 3 tasks I could not complete. Really, I have absolutly no idea how to start.

I am not asking for ready algorithm here.

I'll try to reproduce here.

Command 'X': X = ( 2 * X ) - Y
Command 'Y': Y = ( 2 * Y ) - X
Initial values: X = 0, Y = 1;

Given a N number, what's the minimum of commands where X or Y reach N. Each command change it's own value.

If I send the command 'X', the value of X will be '-1', and so on

The exemple was N = -11
Commands: 'X','X','Y','X', this way X will be equal -11.

Command 'X', X = ( 2 * 0 ) - 1 = -1  , Y = 1
Command 'X', X = ( 2 * ( -1) )  - 1 = -3  , Y = 1
Command 'Y', X = -3                  , Y = ( 2 * 1 ) - (-3) = 5
Command 'X', X = ( 2 * -3 ) - 5 = -11, Y =5

Here are some thoughts about the task.

Let us start with reducing all power of 2 from N.
If $N=2^kM$ then we can first apply $$Y=2Y-0$$ $k$ times.

Now you have new task of reaching smaller number $M$ starting with $X=0$ and $Y=1$.

$X\le 0$ and $Y>0$ holds after every transformation. So if $N$ is positive we will reach it with $Y$ and if $N \le 0$ we reach it with $X$.
Replacing $X$ with $X'=-X$ may help thinking.
$$ X' \to 2X'+Y $$
$$ Y \to 2Y+X' $$
looks simpler and is equivalent to the original task.
Applying one operation $k$ times we get
$$ Y \to 2^kY+(2^k-1)X' $$
Another nice representation of the operations:
$$ X' \to X'+(X'+Y)$$
$$Y \to Y + (X'+Y)$$
From 5. after $k$ steps sum of the numbers becomes $2^k$ and we actually add $2^{k-1}$ to one of numbers.
Solution. There is always only one way to reach $N$. Number of operations is $log_2N$. Imagine $N=101110001$ in binary form. Then we go from right to left and change X when there is 0 and Y when there is 1 in binary representation. In this way we finally construct $Y=101110001$ and almost inverted X=010001111. There is only one peculiarity. When we start for the first bit Y is already 1 and we need to apply X transformation instead of Y.


Another way to solve SAT. Was it known? Theorem. If and only if SAT instance $\varphi$ is satisfiable, there is a way to negate variables in $\varphi$ and get $\varphi'$ where all clauses have at least one positive literal.

Also we can change word 'negative' by 'positive'.

For example, let we have an instance $(x\lor y\lor\overline z)\land(\overline y\lor\overline t)\land(x\lor z\lor t)\land(\overline y\lor z\lor\overline t)\land(x\lor\overline t)$

We have monotone clauses $(\overline y\lor\overline t)$ and $(x\lor z\lor t)$.

$(\overline y\lor\overline t)$ is shorter, let's modify it.

Negating $y$ gives us a formula that has no negative clauses. So, $x\overline yzt$ is positive assignment.

Let us take unsatisfiable formula $(x\lor y)\land(x\lor\overline y)\land(\overline x\lor \overline z)\land(z\lor t)\land(z\lor\overline t)$.

There is one negative clause $(\overline x\lor \overline z)$.

Flipping $x$ or $z$ will not reduce the amount of negative clauses. In fact both renamings $xy$ and $zt$ do not allow to get rid of negative or positive clauses.

In fact, this can be seen as generalization for renamable Horn SAT.

We can try to implement an algorithm that will try to reduce the amount of these clauses. Is such way to solve SAT is known?

You haven't really specified an algorithm, but a similar idea is used by random walk algorithms for SAT such as Schöning's algorithm (see for example Giurgiu's Master thesis or one of the many online lecture notes on the topic).

The same approach is also used in the heuristic algorithm WalkSAT which has recently been used to prove an algorithmic version of the Lovász local lemma.


Detect whether one Turing machine invokes another Given two Turing machines $M,M'$, is it possible to check whether $M$ invokes $M'$?

In other words, is the following problem computable/decidable?

Inputs: Turing machines $M,M'$
Question: Does $M$ ever invoke $M'$?

Perhaps we can look whether $M$ includes the code of $M'$ in it?  In a C program we can check whether a function f invokes a function g, right?  Can we do this for Turing machines too?

The notion of "one machine invokes another" is ill-defined. To emphasize the point of @AbdousKamel, let us observe an even trickier example:

function g():
   do_something;

And now:

function f():
   k = 0
   while not "k encodes a proof of Riemann hypothesis":
     k = k + 1
   "simulate the Turing machine encoded by k"

In order to tell whether f "invokes" g, you have to:

Decide whether Riemann hypothesis is provable, and
Calculate whether the smallest k which encodes a proof of Riemann hypothesis also happens to encode a Turing machine whose behavior is equivalent to the behavior of g.

Question: does f invoke g?


Assembly writer vs compiler in VLIW architecture I read this sentence in a book:

  In VLIW architecture, the compiler/and or assembly writer chooses instructions that can be executed in parallel.

What is the difference between assembly writer and compiler? Would an assembly writer also mean the same as assembler?

The "assembly writer" in that book is a human software developer who writes code in assembler language.


Algorithm to match / link complementary pairs I'm working on a problem where I have a large number of pairs

e.g

1 -> 2

4 -> 3

2 -> 8

..

And a "match" would be considered 1 -> 2 and 2 -> 8 to make 1 -> 2 -> 8, as "1 -> 2" ends with 2 and "2 -> 8" starts with 2.

Given a large set of pairs, i'd like to create the longest possible chain. I know I could brute force it, but I'm wondering if there is a better way

Edit - I can give more precise context for the problem (Sorry, i'm a student currently in data structures who has not taken an algorithms course)

The datapoints in the pairs would be song names  which well flow together. There is a subreddit called "/r/ocrableach" which posts pairs of songs where the ending of one song blends well with the beginning of another song.

An item can appear multiple times in the data set, but i will be discarding repeats as i build my chain.

I'd like to pull posts from /r/ocrableach and try to build the longest continuous playlist based on the song pairs.

If I have the pairs

"Okra -> Bleach"
"Bleach -> I THINK"
"On God" -> "Okra"

I'd like to start constructing a linked list like this:

"Okra -> Bleach" and "Bleach -> "I THINK" match
= "Okra -> Bleach -> I THINK"

"Okra -> Bleach -> I THINK" and "On God -> Okra" match
= "On God -> Okra -> Bleach -> I THINK"

I'm essentially checking if the tail of one pair matches with the head of the "chain" to see if it can be added.

Assuming you don't want to repeat a song, this is the problem of finding a longest path in a directed graph.  Here the graph has one vertex per song, and an edge $s \to t$ if the ending of song $s$ blends well with the beginning of song $t$.

Unfortunately, the longest-path problem is NP-hard.  (See, e.g., Is finding the longest path of a graph NP-complete?,  How to prove NP-hardness of a longest-path problem?.)  This means that you should not expect to find an efficient algorithm for your problem that works on all graphs and that is always correct.  Instead,if you want to solve it in practice, your best will be to look for approximation algorithms or heuristics.

Unfortunately, it is also known that there are no approximation algorithms with guaranteed performance, i.e., that are guaranteed to find a path that is close to the longest, for all graphs.  (See
https://en.wikipedia.org/wiki/Longest_path_problem#Approximation.)  So your best bet is to look for heuristics... or hope your graph has some special structure.

If you are willing to allow repeated songs, then the problem becomes tractable in theory, but the resulting algorithms are probably going to provide poor-quality results in practice.  In particular, if you find any cycle in the graph, then it is possible to traverse the cycle an unbounded number of times, achieving an arbitrarily long path.  Unfortunately these algorithms have a decent chance of producing a cycle of short length, which means that your playlist will just repeat the same few songs over and over... which is probably not what you'd hope for.

One simple heuristic might be to pick a starting vertex randomly, do depth-first search starting from that vertex, find the leaf in the tree with largest depth, and use the path from the root to that leaf as your playlist.  You could repeat a few times from a few different random starting points and take the best playlist found.  There are no guarantees for how well this will perform; you'd have to try it out to see.


Reverse cartesian product matching all given rows I´m looking for an efficient algorithm that will find reverse cartesian products.

Mathematically, given $S \subseteq T^n$, I want to express $S$ as a union of sets $A_{i,1} \times A_{i,2} \times \dots \times A_{i,n}$, for $i=1,2,\dots,k$; and I want to minimize the number $k$.  Is there an efficient algorithm to solve this problem?

This may be easier to explain by example.  Calculating the cartesian product (cross product) is trivial, e.g. {1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5} results in:

    1 1 1
    1 1 2
    1 1 3
    .
    .
    .
    5 5 3
    5 5 4
    5 5 5

All 125 (5 x 5 x 5) rows are created.

Now let's say you remove some rows from this result, i.e. you are left with these 14 rows as a starting point:

    1 2 3
    1 2 4
    1 2 5
    5 2 3
    5 2 4
    2 2 5
    3 2 5
    1 3 3
    1 3 4
    1 3 5
    5 3 3
    5 3 4
    2 3 5
    3 3 5

Now, how do I find a cartesian product that if calculated can generate only those 14 rows back? (order of rows is irrelevant). It can no longer be represented by only one cartesian product {1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5} since e.g. 5 5 5 is not in the list.

One way to now represent the rows as cartesian products is this answer:

    {1} x {2,3} x {3,4,5}
    union
    {5} x {2,3} x {3,4}
    union
    {2,3} x {2,3} x {5}

But the above merge of rows is not optimal although it is a valid solution, we can do better and write it in only two cartesian products:

    {1,5} x {2,3} x {3,4}
    union
    {1,2,3} x {2,3} x {5}

This result is better since 2 < 3 and I want to find the smallest possible number of cartesian products that still represents all the rows. There is no way to reduce (merge) this any further given the 14 rows so this is the best answer in this case.

Now if the starting point would have been all the 125 rows (as in example above) the optimal answer would have been one: {1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5}.

Some known facts about the input:

All rows are unique, no duplicates exists in the list.
Row are of same length, fixed with either 3,4,5,6,7,8 in length.
Numbers in a row range from 1 to 20
There could be millions of rows as a starting point but typically around 100k, hence speed is of importance rather than low memory consumption.

One possible idea is that rows can be merged if n-1 numbers (or group of numbers in the slot) are equal, e.g.,

    1 2 4
    1 2 5
    1 2 6
    1 3 4
    1 3 5
    1 3 6

can merge into

    1 2 456
    and
    1 3 456

which further can be merged to:

    1 23 456

and written as:

    {1} x {2,3} x {4,5,6}

My question is similar to https://stackoverflow.com/q/20890802/781723, but that one is limited to triples ($n=3$); I am interested in generalizing, where rows can be longer than 3.  I also found https://stackoverflow.com/q/46084505/781723, but that has no answer.

Unfortunately the problem is NP-hard when the number of columns ($n$) is unlimited.  In particular, consider the case with $n$ columns and where every number in every row is either 0 or 1.  Then your problem is equivalent to: given a truth table for a boolean function, find a minimal DNF formula (with the minimum number of clauses) for that function.  This is NP-hard.

I know you said you'll have at most 8 columns, so this theoretical result doesn't necessarily imply there is no hope for your specific situation, but it does suggest that you shouldn't expect an efficient algorithm that will generalize to a large number of columns.

One approach you could use that might work well enough in your situation is to use a SAT solver.  Encode each of the sets $A_{i,j}$ with a one-hot encoding; i.e., you have variables $x_{i,j,t}$, which is true if $t \in A_{i,j}$ or false otherwise.  Then it is easy to write down a bunch of constraints (clauses) that enforce that these $A_{i,j}$ form a solution to your problem.  For instance, for each row $r$ that isn't in the input (each $r \notin S$), you get a constraint that $r_1 \notin A_{i,1} \lor r_2 \notin A_{i,2} \lor \dots$ for each $i$, i.e., $(\neg x_{i,1,r_1}\lor \neg x_{i,2,r_2} \lor \dots)$.  And so on.  In this way, for any $k$, you can set up a SAT instance that will be satisfiable iff it is possible to express your input using $k$ reverse cartesian products.  Then you can use binary search on $k$ to find the minimal $k$ such that this is possible.

Because SAT is NP-hard, this won't scale to very large inputs, but it's possible it might work well enough on the problem sizes you mention.  The only way to know for sure is to try it and see.


Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH? My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem.

My understanding is that we have to perform a reduction from Hamiltonian Path---> Hamiltonian Circuit (since we have an alg for Hamiltonian Circuit the reduction should be from Ham path---> Ham circuit)

But in contrast, the question says CONVERT the Ham Circuit algorithm to an algorithm to an algorithm of HP. Does this imply that the Ham Circuit problem should be reduced to the Ham Path problem?

Any guidance/feedback greatly appreciated.

The wording of the question is a bit unclear. You're supposed to reduce HamiltonianPath to HamiltonianCircuit: in other words, write an algorithm that solves HamiltonianPath by using a subroutine for HamiltonianCircuit.

I assume you're specifically going for a polytime reduction, so you shouldn't do an exponential amount of work in your new program—but there are a few different types of polytime reductions (Karp vs Cook in particular), and I can't get any more specific without knowing which one you're using. In a Karp reduction, for example, you only get to call the HamiltonianCircuit subroutine once, and have to return its output unmodified—all the transformation has to happen before you make the subroutine call. In a Cook reduction you can call it as many times as you want, and transform the outputs however you like before returning.


Prove that the coding $\pi_k$ is effective I have to prove that the coding $\pi_k$ is effective given that $\pi_k$ is a surjective coding of $\mathbf N^k$ and $\pi_k$ is a recursive function.

What I've got:

A coding by definition is an injective function from a set $X$ to $\mathbf N$.
I know by definition that a coding $\pi_k$ is effective if it is recursive and there exist decoding functions $J_0^k, ..., J_k^k$ for which $J_i^k=x_i$ in $(x_0, ..., x_k)$ and which are also recursive functions.

How can I find such functions or prove they exist?

Since $\pi_k$ is bijective, for every $x∈N$, there exists a unique tuple $(x_1, ..., x_k)∈N^k$ such that $\pi_k(x_1,...,x_n) = x$. So, how can we define $J^k_i$ ? A solution would be to use a coding that is already known to be effective, let $\alpha_k$ be that effective coding and $\beta^k_1,..., \beta^k_k$ the associated decoding functions. Let $x∈N$, we can put : $$J^k_i(x) = \beta_i^k(\mu y(\ \pi_k(\ \beta^k_1(y)\ , ...,\ \beta^k_k(y)) = x))$$

For $\alpha_k$, we can take the cantor tuple function, which is known to be primitive recursive.

Of course, that's not a proper definition, we need mathematical induction to throw away those horrible dots.