Is there a technique for statically checking that a function is only called at a particular rate? I was reading this article about types, and started wondering how static type checkers could enforce other properties in programs. For example, say I wanted to create a language which would allow checking at compile time that a particular function was only called at most once every 300ms. How would I go about specifying the language to allow that to be enforced? What existing languages try to enforce similar properties?

The property you mention is probably not something that sounds like an ideal fit for enforcement by type systems, so it's not the first example I would suggest looking at, if you want to learn more about how type systems can be used to enforce a variety of properties.  (I'm not saying it is impossible to enforce that property using a type system, but it might not look natural or feel super-useful to an everyday programmer, and the type system might need some hand-holding or help from the programmer.)

However, there are other properties that are a better fit for type systems.  For instance, you might look at dependent type systems, which can be used to enforce many properties.

In my experience, type systems tend to be more useful for enforcing safety properties.  It tends to be harder to reason about time or liveness properties using a type system (I'm not saying it is impossible, but it might be harder or less natural).

You might also enjoy reading about the Curry-Howard correspondence, which shows a correspondence between theorems and types (and between a proof of a particular theorem vs a particular program that can be given a particular type).  Proof-carrying code is one example of a system that relies heavily on this view of proofs-as-programs.  The goal there is to prove non-trivial properties of a program.  The theorem you want to prove gets encoded as a type, and the proof gets encoded as an expression in an abstract language; then checking the validity of the proof becomes as simple as checking that the expression has the claimed type.  This essentially shows how you can reduce "showing that the program satisfies a particular safety property" to type-checking.

In a similar but not identical vein, you might also enjoy looking at languages like Haskell and the QuickCheck tool, which uses the rich type information available from the Haskell type system to synthesize test cases.  Anecdotally, QuickCheck is effective at finding many bugs.  This is not an example of using the type system to enforce absence of a particular kind of bug, so much as using the type system to make random testing more effective and thereby tend to help programmers catch many bugs earlier.


What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm? The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book Elements of Automata Theory ascribes the algorithm to McNaughton and Yamada, who have indeed described it in their paper.

It might appear like a standard situation when one algorithm is ascribed to different authors. However, things seem to be more complicated. In fact, McNaughton and Yamada dealt with a converse problem (constructing a finite automaton to a rational expression) as well and Wikipedia's article on Thompson's construction refers to this algorithm as to the McNaughton-Yamada algorithm.

For this reason, I would like to ask what is the most correct name one can use for the Kleene/McNaughton-Yamada algorithm? In fact, I would also be interested in a correct name for a generalized algorithm, which works over arbitrary, say, complete (or closed, Conway, etc.) semirings. Thank you in advance.

P.S. Sorry for not providing a link to the McNaughton-Yamada paper, but I was not allowed to post more than 2 links.

There is no such thing as a "correct" name. There is the name that is commonly used, which might depend on the community. This is what you would use unless you want to make a point. If you think that the common name doesn't give credit to the right people, you can use a different name, though you should also mention the common name so that others know what theorem you refer to.

Mathematical theorems and concepts are often named not after the first people who proved or defined them (if you're interested, you should be able to find several lists of such theorems and concepts online). Yet once a name has stuck, it is different to change it. That is because the most important goal of a name is not to give credit but rather to give a short name for a common concept. Indeed, sometimes results are not named after anybody, even though many of them were first proved by somebody.


Can two neighbors in a graph be at the same depth in a DFS tree? In an undirected graph, can two nodes at an identical distance n from the root of a DFS tree be neighbors in the original graph? I'm thinking no, but I'm not sure (because of back edges)

I think you are correct:

All neighbors of a node will be of rank one less (the node we got here from) or one more (or two more, etc) because we will rank them before we back out of the node.


Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph I'm learning Dynamic Programming (By myself) and in the textbook there is this question:

Given two undirected graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ over the same set of Vertices $V$ and a weight function $w: E_1 \cup E_2 \rightarrow \mathbb{R}$, let $P = \left\{e_1, e_2, ..., e_n \right\}$ be a path in $(V, E_1 \cup E_2)$.
We sat that P is alternating if for any $1 \leq i < n$ at least one of the following two conditions hold:

$e_i \in E_1, e_{i+1} \in E_2$
$e_i \in E_2, e_{i+1} \in E_1$

Write a DP algorithm that given $G_1, G_2$, returns the weights of the shortest alternating paths between all pairs of vertices in $V$

OK so I sat on this question for a long time but I can't seem to figure out how to do solve it. Since this is a shortest path between all pairs I tried to think of a solution which uses Floyd-Warshall algorithm, but I can't figure out how to factor in the addition of the alternating path.
Every solution I think of fails when inserting special Edge Cases.
Can anyone give a hint as to how to proceed?

May be it helps you to see more easily the way to attack the problem.
The first that you could try  it's find or understand the recursive relation behind Floyd-Warshall Algorithm. As the next function $f$.

$$
f(u,v,k) = \begin{cases}
w_{u,v} & k = 0\\
\min\, (\ f(u,v, k-1),\ f(u,k,k-1) + f(k,v,k-1)) & \text{otherwise}
\end{cases}
$$

$w_{u,v}$ it's the weight of edge from $u$ to $v$ in the direct graph $G$. $\infty$ if that edge doesn't exist.
$f(u,v,k)$ is the weight of a shortest path from $u$ to $v$ if you consider the first $k$ vertices as intermediates.

To adapt the above function form for your problem, I'd sketched the essence of the  problem in the next graph:

$m_i\in E_0$
$l_i\in E_1$
The curly curve is the shortest path considering the first $k-1$ vertices.
You have a alternate path that consider the $k$ node when you see the pattern (normal-$k$-dashed) lines in the path, or with convention above: (dashed-$k$-normal) line or $(m_i, l_j)^*$ , $(l_i, m_j)^*$ pattern in general.

So the next step it's construct the recursive relation looking the connection between subproblems, and for that you could think for a moment that your function solve the problem for a small size of problem, or instances pattern (follow principle of optimality).

$$
f(u,v,k,i) = \begin{cases}
w_{u,v,i} & k = 0\\
\min\, (\ f(u,v, k-1,i),\ f(u,k,k-1,~i) + f(k,v,k-1,i)) & \text{otherwise}
\end{cases}
$$

$w_{u,v,i}$ is the weight for the edge in $E_i$  (Note that I change enumeration of $E$ for convenience). $\infty$ if that edge doesn't exist.
$f(u,v,k,i)$ is the weight of a shortest path that ended up with a edge in $E_i$ that consider  the first $k$ vertices as intermediates like the graph above.
$~i = 0$ if $i = 1$ or $1$ if $i = 0$.

So, the weight of the shortest alternate path from $u$ to $v$ is
$$\min \,(\, f(u, v, |V|, 0),\ f(u, v, |V|, 1) )$$
where $|V|$ is the number of vertices.

Of course, after some work, you could notice that:

It's possible delete parameter $k$
you could implement iterative version or use a memorization technique.
Other details, that I'm forgiving. It's late.

I'd wrote a python code/ and input test file if you can play with that. But, Here, it's not important.


Show $\{1^n0^m |\space n \neq 2^m\}$ not regular using pumping lemma Showing that the language $L$ with  $\{1^n0^m |\space n \neq 2^m\}$ is not regular using Myhill-Nerode is easy: Let $i, j\in \mathbb{N}.i\neq j.$ It follows $1^{2^i}\nsim 1^{2^j}$ because $1^{2^i}0^{i}\notin L$ but $1^{2^j}0^{i}\in L$. Therefore $L$ has an infinite amount of Myhill-Nerode equivalence classes and is not regular.
But how do I show this using the general version of the pumping lemma for regular languages? https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#General_version_of_pumping_lemma_for_regular_languages

Let $p$ be the pumping length, and consider the string $u=1^{2^{p!+p}}$, $w = 0^p$, $v = \epsilon$. Notice $uwv \in L$. According to the pumping lemma, there is a value $q \in \{1,\ldots,p\}$ such that $1^{2^{p!+p}} 0^{p-q+iq} \in L$ for every $i \geq 0$. Choosing $i = 1 + p!/q$, we obtain a contradiction.


Why is Relativization a barrier? When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to a friend, a question came up as to why such techniques are ill-suited for proving the $\mathsf{P} \neq \mathsf{NP}$ problem, and I couldn't give a satisfactory answer.

To put it more concretely, if I have an approach to prove $\mathsf{P} \neq \mathsf{NP}$ and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Any exposition/thoughts on this topic?

To put it more concretely, if I have an approach to prove P≠NP and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Note that the latter “if” is not a condition, because Baker, Gill, and Solovay already constructed such an oracle.  It is just a mathematical truth that (1) there exists an oracle relative to which P=NP, and that (2) there exists an oracle relative to which P≠NP.

This means that if you have an approach to prove P≠NP and the same proof would equally prove a stronger result “PA≠NPA for all oracles A,” then your approach is doomed to fail because it would contradict (1).

In other words, there is some fundamental difference between proving P≠NP and proving e.g. the time hierarchy theorem, because the proof of the latter just uses diagonalization and is equally applicable to any relativized world.

Of course, this does not mean that there is no proof for P≠NP.  Such a proof (if one exists) must fail to prove the stronger result mentioned above.  In other words, some part of the proof must distinguish the nonrelativizing world from arbitrary relativized worlds.


Does the process exiting from critical section will always call signal instruction? I have seen many solutions to critical section problems in process synchronization chapter . Many of them first acquire resources , execute critical section and leave . My Question is a process exiting from the critical section should always call $V(S)$ (or release/signal/ up ) instruction ? Can any process exit from critical solution by calling wait instruction ? If so give an example and explain how it works .

For example , all the problems regarding semaphore are executed in the following manner . Where $P(s) $ and $V(s)$ has usual meaning .( up and down operator )

s=1
P(s)
< Critical Section >
V(S)

I have never seen an solution like this

s=0
V(s)
< Critical Section >
P(S)

Does any critical section problems could be solved like this ? if so please explain me how it would works .

Assuming s is a binary semaphore.

If s=0, a V(s) will be successful operation making s=1

If s=1, a V(s) will be successful operation making s=1

If s=0, a P(s) will be unsuccessful operation by retaining s=0

If s=1, a P(s) will be successful operation by making s=0

  s=0
  V(s)
  < Critical Section >
  P(s)

Let process ${p_1,p_2,p_3,.,p_k,.,p_n}$ are waiting go get a chance to access CS (Critical Section).

For the first time $p_1$ tries V(s), successfully increase s by 1,and get an access to CS.

While $p_1$ still in CS $p_k$ tries V(s), successfully increase s by 1 and get an access to CS and so on.

With V(s) at the entry of the CS, will never guarantee blocking others from getting into CS.

With this implementation all process waiting to access CS will get into CS, thus violation mutual exclusion.

Here talking about exiting operation P(s) is useless as it doesn't help the event by any means.

  s=1
  P(s)
  < Critical Section >
  V(s)

Here, if $p_1$ tries P(s) for the first time, successfully decease s by 1 and get access to CS.

With P(s) at the entry of the CS, will guarantee blocking others from getting into CS.

While $p_1$ still in CS $p_k$ tries to enter CS by executing P(s), but fails as s=0 already and cant decrease anymore.

Thus always guarantee mutual exclusion.

See what happens if we doesn't have signal operation at CS exit:

  s=1
  P(s)
  < Critical Section >
  // remove exit operation V(s)

Without $p_1$ signaling, non of the waiting process ${p_2,p_3,.,p_k,.,p_n}$ can access CS. no one can execute the entry operation P(s),since 's' value is still 0.

All processes waiting for CS will be blocked infinity.

Thus, deadlock kind of event happens here where resource is available but cant be accessed.


space complexity of DFA intersection problem the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper significance in computational complexity theory.[1][2] it is O(n2) time with no better lower bounds known, and tight bounds possibly having major implications on multiple complexity class separations. looking for insight/ refs.

  what is the best known space complexity of determining DFA intersection (emptiness)? how does the best known algorithm work?

[1] Deciding emptiness of intersection of regular languages in subquadratic time / cstheory SE
[2] Two DFA intersection emptiness connections to SETH & L vs P / cstheory SE

Solving intersection Non-Emptiness for 2 DFA's:

It essentially just becomes a reachability problem for the product DFA.

Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ space.
Or, we can solve it non-deterministically with $O(\log(n))$ space.
By Savitch's Theorem, we can also solve it deterministically in $2^{O(\log^2(n))}$ time using $O(\log^2(n))$ space.

To the best of my knowledge, it is not known if we can solve it deterministically in polynomial time using $O(n^{2-\epsilon})$ space.

Feel free to share any thoughts or ideas in the comments.  :)


Application of the four color theorem I was reading up on the four color theorem and am wondering if there is any practical application of it. (I dont think seperating the map into four different colors can be considered an application.)

I tried Googling for applications but couldn't find any.

One of the 4 Color Theorem most notable applications is in mobile phone masts. These masts all cover certain areas with some overlap meaning that they can’t all transmit on the same frequency. A simple method of ensuring that no two masts that overlap have the same frequency is to give them all a different frequency. But, as the government owns all frequencies and charge for each, one wants to use the minimum possible number of frequencies. The areas covered can be drawn as a map and the different frequencies can be represented as colors.


Examples of Analysis of Branch and Bound Method I am solving a graph problem, which can be formulated as an integer programme. Based on computer experiments, it seems that the branch and bound method works well. I would like to analyse the running time, and wonder whether there have been other problems where branch and bound method was used and the theoretical bounds on the running time has been established?

On another note, if anyone knows any examples of problems where the range of possible values that a variable in a linear programme can take, I'd also be interested in.

Branch-and-bound is a heuristic.  In this context, my impression is that typically analysis of the worst-case running time of such heuristics is not enlightening: the worst-case running time is typically exponential.  On some problems in practice branch-and-bound may run significantly faster than that, but my sense is that worst-case running time analysis usually isn't very helpful for predicting when that will happen.


Simplifying the Boolean expression $A + \bar{A}\bar{B}$? So I'm trying to simplify the Boolean expression (1) $A + \bar{A}\bar{B}$.

I noticed that by Karnaugh maps this is equivalent to $A+\bar{B}$, and I also noticed that if I take the complement of (1), I get ~(1)= $\bar{A}(A + B) = \bar{A}A + \bar{A}B = \bar{A}B$, so then taking complements again yields (1) = $A + \bar{B}$.

But this feels very ad hoc to me, and makes me feel like I'm missing some key point about how to simplify this expression more systematically.

Any thoughts appreciated.

Thanks.

There is a Law of Distributivity of Boolean operation $\lor$ (disjunction, which is sometimes denoted by $+$) over Boolean operation $\land$ (conjunction, which is sometimes simply omitted):
$$x \lor (y \land z)= (x \lor y)\land(x \lor z)$$
So, in your case:
$$A \lor (\lnot A \land \lnot B) = (A \lor \lnot A) \land (A \lor \lnot B) = A \lor \lnot B$$
For more information please see: Boolean Algebra.


Runtime analysis of a "find the secret number" algorithm The algorithm task is to find an integer (range is not known). the function guess(num) returns one of three chars: '>','<' or '='.
  Find the secret number with O(logS) guesses, where S is the secret number.  You can use find_secret(N1, N2) which operate with O(log(N2-N1)).. What it does is simply a binary search.

So, the algorithm implemented (with Python) as follows:

def find_secret2():
    low = 1
    high = 2
    answer = guess(high)
    while answer == ">":
        low *= 2
        high *= 2
        answer = guess(high)

    if answer == "=":
        return high
    return find_secret(low, high)

my thoughts about the complexity of this algorithm:

it takes O(logS) to reach the range where low < secret < high.
then, it takes O(log(high-low)) - because we're using find_secret(N1, N2) method.

I'll be glad if you could help me explain why the algorithm's complexity is O(logS) in a mathematical/rigorous way using the O-notation.
Thanks!

You're almost there. It takes $O(\log S)$ time for your while loop to finish (by the way, how would you go about proving that? You can try induction on $\lceil \log_2 S \rceil$ or on $\lfloor \log_2 S \rfloor$, one of them should work). Then $\mathrm{low} \leq S < \mathrm{high}$. Furthermore $\mathrm{low}$ and $\mathrm{high}$ are certain powers of two, and so you can relate $\mathrm{high}-\mathrm{low}$ to $S$. More concretely, you want to bound $\mathrm{high}-\mathrm{low}$ from above in terms of $S$. This is the part you're missing. Perhaps you should try a few concrete examples and then generalize.


Explanation of an explanation of Turing's proof to the halting problem? I am reading the transcription of a lecture from a professor Scott Aaronson, specifically the section titled Turing Machines. In this section he describes Turing's proof of the Halting Problem.

  But can we prove there's no program to solve the halting problem? This
  is what Turing does. His key idea is not even to try to analyze the
  internal dynamics of such a program, supposing it existed. Instead he
  simply says, suppose by way of contradiction that such a program P
  exists. Then we can modify P to produce a new program P' that does the
  following. Given another program Q as input, P'

runs forever if Q halts given its own code as input, or
halts if Q runs forever given its own code as input.

  Now we just feed P' its own code as input. By the conditions above, P'
  will run forever if it halts, or halt if it runs forever. Therefore P'
  -- and by implication P -- can't have existed in the first place.

How would P(x) be defined here, the algorithm which can compute the halting problem?

halts if x halts
otherwise does ...

Is P allowed to "output" something or only halt or not halt? It can write to a tape correct? So it could output 1 if x halts or 0 if it does not and then halt itself?... By attempting to define P am I trying to disprove Turing?..

Would we not need to know the source code of P to modify it to produce P'?

Is the overall idea of the proof that a machine to solve the halting problem would not be able to prove that it itself halts given its own source as input?

P should take two arguments: a TM M and a string x. P accepts if M halts on input x, otherwise rejects. Definition of P:

P(M, x): execute M on x and if it halts, go to the accepting state. If M doesn't halt on x, go to the reject state.

The language of the words accepted by P is Turing recognizable but not decidable. So you can define P, but the machine won't stop for all the inputs, and this is what you're trying to demonstrate.

You don't need to know the code source of P to produce P'. P' can be seen as:

P'(Q):
execute P(Q, 'Q'), where 'Q' is the encoding of the TM Q, and if P accepts then don't halt, else halt.

The point is: if you suppose that a machine P that decides the Halting Problem exists, you're going to get a contraddiction. In fact you can produce a machine P' for the complement (you can do this because we are presuming the Halting Problem is decidable), so that it stops if the machine given in input doesn't and viceversa. If you try to use P' on P', then you get an antinomy.

I'm not sure this answer to your questions..


Range majority queries - most freqent element in range Given N numbers and M range queries (starting and ending points), I need to
compute majority (most frequent element, if it exists) in these ranges.

I'm looking for an algorithm that would answer queries in logarithmic or even constant time.

If the $N$ items are in ascending sorted order and stored into an array, you can determine a majority candidate in $O(1)$ time for a specified range by returning the item whose index is the range median. Therefore, this will require $O(M)$ time in the worst case for $M$ range queries. Note that the item returned in each query is a candidate: you need to verify if the item actually is a majority element in the range. And, verification is linear in the number of items in the range.

EDIT: explained tradeoff between space and time

If the items are not in sorted order, than finding a candidate element requires in the worst case time linear  in the number of items in the range, using the Boyer-Moore algorithm and constant space (one counter). You can not determine a candidate element in time logarithmic in the number of items in the range while using constant space. However, if you trade space for time, you can determine a majority element in $O(1)$ time at the cost of using linear space.


Is $\log(n!)$ in $\Theta(n \log(n))$? I had two questions on my automated test which I don't understand the answer for.

$\log(n!) = \log(n\cdot (n-1)\cdot  \cdots \cdot 2\cdot   1) = \log(n)+\log(n-1)+....+\log(1)$. So it is in $O(n\log(n))$. But is it also in $\Omega(n \log(n))$? I don't think so, but my automated interview test thought so!

$\log(n)+\log(n^2) = \log(n)+2\log(n) = 3\log(n)$. So, it is in $O(\log(n))$, $\Omega(\log(n))$ and $\Theta(\log(n))$. But for some reason my automated interview test thought otherwise.

Is my understanding correct or is the automated test correct?

You mentioned
$$
\log(n!) = \log(n(n-1)\cdots1) = \log(n)+\log(n-1)+ \cdots +\log(1)
$$
From this, we can write (assuming $\log$ is base 2)
$$
\begin{array}{l}
\log(n!) \\
= \log(n)+\log(n-1)+....+\log(1) \\
\geq \log(n)+ \cdots + \log(n/2) \\
\geq \log(n/2)+ \cdots + \log(n/2) \\
= n/2 \cdot \log(n/2) \\
= n/2 \cdot (\log(n) - 1) \\
= n/2 \cdot \log(n) - n/2 \\
\end{array}
$$
since $\lim_{n\rightarrow +\infty} \dfrac{n/2}{n/2 \cdot \log(n)} = 0$, the last expression above is $\Theta(n \log(n))$, hence $\log(n!)$ is $\Omega(n \log(n))$.


Decidability of decision problems Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear because we don't know about given TM anything so it can behave unpredictably, can simply loop on any input), but on another hand in question 2. we don't know much about machine, however I can hardcore all words into my TM as far as given language is finite. Also, for question 1. I'm able to create TM which checks if the output of M is even-length (I would classify this problem as semi-decidable).

What type  of the following decision problems are: decidable, partly decidable, or even undecidable:

Does the language of the given machine M contain only even-length words?
Does the given M machine accept a finite language size of which is less than 2019?
We say that language A is prefixless if no word belonging to A is a prefix of any other word from A. For example, language A = {0, 10, 110, 1110, ...} is prefixless, while language B = {0, 1, 00, 11, 000, 111, ...} does not have this property (for example, because 0 is the prefix 00).
Consider the following language (decision problem): L = {⟨M⟩ | L (M) is prefixless}.
Is the given recursive function a surjection?
Is the given recursive function an injection?
Does the machine M stop at bb?
Does the machine M accept the empty language?

A good rule of thumb is to use Church's thesis: can you personally solve the problem? While this is of course informal, in practice it works very well after you develop a bit of experience with Turing machines. (That said, ultimately the theorem you'll learn and use here is Rice's theorem.)

By way of example, let's first consider the following two sets:

Those Turing machines which halt (on input $0$) in at most $42$ steps.
Those Turing machines which halt (on input $0$) and output $42$.

It should be fairly easy to see that we can informally compute the former: given a Turing machine, just run it on input $0$ for $42$ steps and see what happens. The latter, though, is harder: if I'm presented with a candidate Turing machine, if I know it halts I can run it until it halts and check whether the output is $42$, but in the absence of that information I seem to be stuck since I don't see a way around the infinite search involved in "wait until it halts, if it ever does."

So now let's look at a couple candidates on your list.

(1): in principle, we'd need to check each possible input to be confident that a Turing machine has the desired property: a single counterexample tells is it doesn't, but we don't know where such a counterexample might be and so as we go along checking all possible strings we'll never be fully confident that there isn't a counterexample (= a string of odd length which is accepted) which we just haven't found yet.
(2): Here, there are only finitely many things we need to check, namely all those strings of length $<2019$. However, think about what's involved in checking a single candidate: the only a priori way to tell that a Turing machine doesn't accept a string is to run it forever, and "at the end of forever" you'll know that it in fact doesn't accept that string, but that's clearly bonkers. So there's still an infinite search involved, and this appears undecidable.

Now how do we make further distinctions between the undecidable sets - in particular, between semidecidable (more commonly, computably enumerable) and not-even-semidecidable?

Again, Church's thesis is the key: is it the case that, in order to be certain that something is in our set, we need to see some finite amount of information? If so, then it's computably enumerable. Otherwise, it's not - and in particular, if it's falsified by a counterexample (instead of verified by a witness) its complement is computably enumerable. So our Church's thesis analysis of (1) and (2) says that each is not even computably enumerable.


How to calculate the mergesort time complexity? Recently while reading a book (Skienna) I came across the following statement:

  Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of times we would need to do this would be $\lceil\log_{2}{n}\rceil$ and for each level we perform $O(n)$ work hence total time taken will be $O(n \log n)$

How to understand the above statement? Also, I am always confused about when to take ceil or floor. I am not a math major therefore it seems intimidating to me at first. I don't know about generating functions etc.

Imagine that we have an array $A$ of size $n$. Mergesort splits this array into two equal halves and sorts them individually. So in context of the paragraph you have provided, each node corresponds to some chunk of the original array that we want to sort. We divide a node $A[L,R]$ to two nodes $A[L,M]$ and $A[M+1,R]$ with $M = \frac{L+R}{2}$

The splitting of a node $A[L,R]$ into two nodes takes $R-L+1$ time and then merging the two child nodes $A[L,M]$ and $A[M+1,R]$ again takes $A[R-L+1]$ time. Thus for every node, the number of operations the algorithm performs is equal to twice the size of the array corresponding to that node.

Thus we have that on any particular level if we have an array of size $k$, splitting and merging of the array can be done in $k + 2\times \frac{k}{2} = 2k$ operations.

Now note that we keep splitting the array till we have arrays of size $1$ since we can't split them further.

Draw a binary tree with the root node corresponding to the array $A[1,N]$ and with each node having two children corresponding to its left and right halves and recursively draw  the structure for each child till we have arrays of size $1$. Denote each node by the size of the array that it corresponds to. We will get something that looks like this

(Taken from Khan Academy)

This is the recursion tree for merge sort.

The computation time spent by the algorithm on each of these nodes is simply two times the size of the array the node corresponds to. Therefore the total running time $S$ of mergesort is just the sum of all the sizes of the arrays that each node in the tree corresponds to i.e.
$$S = 2 \sum_{i=0}^k 2^i\frac{n}{2^i}$$

(How did we get this sum? There are $2^i$ nodes of size $\frac{n}{2^i}$ in the tree and it takes $2k$ time to finish computation on an array of size $k$)

Observe that when $i=k$, $\frac{n}{2^k} = 1 \implies n = 2^k \implies k = \lceil{\log n}\rceil$
Thus $S$ reduces to $$2 \sum_{i=0}^{\lceil{\log n}\rceil} n = 2n\lceil{\log n}\rceil = \mathcal{O}(n\log n)$$


Showing the function=? is impossible Here's a lab from a first-year computer science course, taught in Scheme: https://www.student.cs.uwaterloo.ca/~cs135/assns/a07/a07.pdf

At the end of the lab, it basically presents the halting problem, and shows that it is impossible to solve by introducing the function diagonal, which is defined as:

(deﬁne (diagonal x)
  (cond
     [(halting? x x) (eternity 1)]
     [else true]))

Where eternity is a non-terminating program defined as (define (eternity x) (eternity x)). What happens when you feed diagonal its own definition as input ... ?

This is all fairly standard stuff. Then, the lab says:

  For a real challenge, deﬁnitively answer the question posed at the end of Exercise 20.1.3 of the
  text, with the interpretation that function=? consumes two lists representing the code for the two
  functions. This is the situation Church considered in his proof.

So the gist of it is that function=? takes two inputs. Each is a list, which represents the definition of a function, i.e. it is a list of the form (define (id args ...) body ...). We can assume that both functions are syntactically valid and will terminate for all inputs (without runtime errors). function=? returns true if and only if the two functions will always return the same result when given the same inputs. For example,

(function=? '(define (foo x) (* 2 x))
            '(define (bar x) (+ x x))) ; should return #t

(function=? '(define (foo x) (+ x 1))
            '(define (bar x) (+ x 2))) ; should return #f

Now, function=? is obviously impossible to write - the challenge is to prove it is impossible. I thought about this for a while, and the best solution I could come up with is the following:

(define (disprove-function=? x)
  ((lambda (snip)
     (let ((self (list 'define '(disprove-function=? x)
                       (list snip (list 'quote snip)))))
       (if (function=? self '(define (id x) x))
           (list x)
           x)))
   '(lambda (snip)
      (let ((self (list 'define '(disprove-function=? x)
                        (list snip (list 'quote snip)))))
        (if (function=? self '(define (id x) x))
            (list x)
            x)))))

Basically, disprove-function=? uses standard quining techniques to generate its own source code (the variable self), and then asks function=? if it is equivalent to the identity function. If function=? says #f, then disprove-function=? will always behave like the identity function. Contradiction! If function=? says #t, then disprove-function=? will always behave differently from identity; in particular, it will behave like the list function. Contradiction! Thus, function=? can't exist. QED.

My question is: is there a more elegant way to approach this problem? My solution seems ... long and ugly. Not nearly as nice as the diagonal function for proving that the halting problem is unsolvable.

NB: Please give me answers and not hints! Even though this is a homework question, it is not my homework question: I don't go to this university! Further, as you can see from the lab, this question is under the Enhancements category and isn't worth marks, so even if you don't believe me, there is still no problem with just giving me an answer. Finally, I already have a solution, which I am pretty sure is right; I was just wondering if there was a better solution.

Using the halting problem seems like the good solution. Suppose you have a function red that takes the code of a function (or λ-term) (or a untyped function), reduces one step (or β-redex) in it and returns the code of the resulting function. Suppose also that you have a function normal that says if the term is in normal form.

In Turing machines language, red would be the computation of one step and normal would return true when we are in a final state.

Let's simulate the computation of $n$ steps, returning $43$ instead of $1$ if we reach the end of the computation:

(define (run t n)
  (if (= n 0) 1
    (if (normal t) 43
      (run (red t) (n-1)))))

Then we can decide if the execution of a term will terminate or not:

(define (one x) 1)
(define (terminate t) (not (function=? (run t) one)))

From that we can use the usual diagonal argument:

(define (loop x) (loop x))
(define (f x) (if (terminate (code-of-application x (quote x))) (loop 0) 1)
(f code-of-f)

If f terminates on code-of-f then (terminate (code-of-application code-of-f (quote code-of-f)) will return true and then f will loop on code-of-f. So it should loop. Then (terminate ...) should return false and f will terminate on code-of-f, contradiction.

Technicalities: one need to define a base language which is expressive enough to be able to write everything is written above. You then need red and normal which can be tougher than one can imagine. You need also the standard quine techniques: quote which, given the code of a term, returns a term representing the code of the term, code-of-application a b is easy and self-explanatory, and of course you need to write everything above internally to write code-of-f.

The lambda-calculus is surprisingly simple and expressive to both write all this down and to prove its correctness, which is why Church used it to solve Hilbert's tenth problem, but one can do it in a lot of languages, possibly in a simpler way, using language-specific quine tricks.


Does crossover take the parents or the offsprings? How to select parents with linear ranking? I am building genetic algorithm for feature selection. But there are vague things to me.

For example, there are 100 individuals with crossover probability 0.8. Does it mean I take 80 parents (40 couples), or 80 offsprings?
I'm using linear ranking as the parent selection because of the fitness values are close to each other. How can I select the parents after I get the values of linear ranking?
Assume if the answer on number (1) is taking 80 parents. After I get parent's candidates, what will happen to the unused parents if those candidates are more than our requirement? And what will happen if those candidates are less than our requirement?
If we only take the best 80 individuals as parents, then what is the point of using linear ranking as parent selection?

Thanks before.

For example, there are 100 individuals with crossover probability 0.8. Does it mean I take 80 parents (40 couples), or 80 offsprings?

0.8 is the probability that crossover will occur at a particular mating.

The standard algorithm samples the population with replacement (the same parent may be selected more than once):

you pick out 50 couples;
crossover is performed for (about) 40 couples producing 80 new individuals (80% of the new generation is produced via crossover);
(approximately) 10 couples are copied to the new population (here ignoring the mutation operator).

(this is a generational approach).

  I'm using linear ranking as the parent selection because of the fitness values are close to each other. How can I select the parents after I get the values of linear ranking?

Just use the standard roulette wheel selection algorithm  and, rather than weighting each candidate by its fitness score, use its rank.

  If we only take the best 80 individuals as parents, then what is the point of using linear ranking as parent selection?

It's not deterministic. An individual has a probability of getting selected as a parent (the probability is linked to the rank).

With rank selection the best individual is more likely to be chosen than the second one, but both have the same probabilities of being chosen whether the best had ten times the fitness of the second best, or only a slightly greater fitness.


Master Theorem applicable here? Let
$T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\
1 & \text{if }n=1
\end{cases}$

I need to prove that $t(n) \in O(n²)$, thus $t(n) \leq c\cdot n²$

I asked the question here and I got really great help last time, the thing is after I was shown last time that $f(n)=\log(n)\cdot\log(n!)$ is $\Theta(2\cdot\log(n)\cdot n) = \Theta(\log(n)\cdot n)$ I thought I could then use the master theorem

However since $a=\frac{2+\log n}{1+\log n}$ is NOT a constant I can not use the master theorem
but I thought that I could use an upper bound for $a$, since $\frac{2+\log n}{1+\log n} < 2 \quad\forall n$ and then use the master theorem for $a=2$, $b=2$. But am I allowed to use the master theorem after finding an upper bound for the non-constant $a$?

What would other ways be to show that $T(n) = O(n^2)$ ?

Yes, you can define $T'(n) = 2 T'(\frac{n}{2}) + \Theta(n \log n)$, notice that $T(n) \le T'(n)$, and use the master theorem on $T'$ to obtain an upper bound of $O(n \log^2 n)$ to $T$.

Since for $n \ge 2$, $\frac{2+\log n}{1+\log n} \le \frac{3}{2}$ you can get a better upper bound by comparing $T$ to
$$T'' = \begin{cases}\frac{3}{2}T''(\frac{n}{2}) + \Theta(n \log n) & \text{if $n\ge2$} \\ \Theta(1) & \text{otherwise}\end{cases}.$$ Applying the master theorem on $T''$ yields and upper bound of $O(n \log n)$ for $T$.


What future working opportunities do computer science students have? If I am right students learning computer science at universities learn very theoretical kind of knowledge. A knowledge most of which (e.g. algorithm theory) can't be used to create everyday software (e.g. MS Word, IE, etc.).

What opportunities do computer science graduates have if they don't want to do research but rather work at some company where they can make use of what they have studied. (e.g. not writing MS Word)

In case of still not being clear enough, generally speaking, what I would like to know is what can a computer science gradute work?

If I am right students learning computer science at universities learn very theoretical kind of knowledge.

You are largely incorrect. A significant portion of most CS curricula includes hands-on, applied, practical programming, computer systems and software development exposure. The ACM publishes curriculum guidelines for ABET/CAC-accredited CS programs in the US. You should check their list of recommendations to get a more-or-less complete picture of what most CS programs worth the name cover.

  A knowledge most of which (e.g. algorithm theory) can't be used to create everyday software (e.g. MS Word, IE, etc.).

Algorithm theory is absolutely and vitally important for creating everyday software (such as MS Word, IE, etc.), specifically, for differentiating the software sufficiently to compete. To even write a web browser, one needs to understand HTTP, TCP, multithreading, parsing, etc.

  What opportunities do computer science graduates have if they don't want to do research but rather work at some company where they can make use of what they have studied. (e.g. not writing MS Word)

Any company that needs people to write software will need to hire somebody. Having academic credentials is a plus and a computer science degree is more applicable than just about any other option. More applicable, applied, practical options are typically viewed with some skepticism in the US since they're viewed as less rigorous (perhaps rightly so).

  In case of still not being clear enough, generally speaking, what I would like to know is what can a computer science gradute work?

Anywhere most graduates can work. Most of industry bases hiring decisions on individual circumstances; a CS major with experience in mechanical engineering could be hired as a mechanical engineer. A CS major with experience making puff pastry could be hired as a chef. Most CS majors would be well qualified to take jobs writing software since, by virtue of being a CS major, they have some experience writing software.


If P=NP, does this imply that all problems are NP-hard? A problem is said to be NP-hard if every problem in NP is reducible to that problem in polynomial time.
Hence, if P=NP, wouldn't that imply that every problem in NP is reducible to every possible problem, in polynomial time?
However the diagram above seems to imply that if P=NP, there exist problems outside of NP-hard.
Is there anything I am missing?

TL;DR: if $\sf P=NP$ then all languages except $\emptyset$ and $\Sigma^*$ are $\sf NP$-hard. The diagram is perhaps misleading if you consider that it has the implication that there are infinitely many problems outside the $\sf NP$-hard region (which you reasonably could, but I didn't assume that from it).

We assume throughout that $\sf P=NP$.
Recall that "reducible to" means that we need to map a yes-instance to a yes-instance and a no-instance to a no-instance. This rules out $\emptyset$ and $\Sigma^*$ (the set of all strings), as they lack either a yes- and no-instance.
For all other problems $L$ in $\sf NP$, we can choose a yes-instance $y$ and a no-instance $n$. To reduce $M\in \sf NP$ to $L$, we can just compute in polynomial time whether it is a yes- or no-instance and return $y$ or $n$ accordingly. Thus, the problems in $\sf NP\setminus \{\emptyset, \Sigma^*\}$ are $\sf NP$-hard.
Now let's look at the problems which are not in $\sf NP$ (or, equally, $\sf P$). Consider a $\sf EXP$-complete problem. Such a problem is not in $\sf NP(=P)$ because $\sf P\neq EXP$, so it falls outside the inner circle in the diagram. Additionally, it cannot be $\emptyset$ or $\Sigma^*$ because both problems are in $\sf P$, so the problem has a yes-instance $y$ and a no-instance $n$ and thus we can do the same algorithm above to reduce any $\sf NP$ problem to it in polynomial time. So it meets the definition of $\sf NP$-hard.
The diagram on the right is correct that ${\sf NP\neq NP} \text{-hard}$, but there is a technicality that ${\sf P=NP}\not\subseteq{\sf NP} \text{-hard}$ because of $\emptyset$ and $\Sigma^*$. I think the diagram illustrates this by using $\simeq$ rather than $=$ for the text "NP-complete".
I believe your issue was whether it is meant to say that ${\sf NP} \text{-hard} \neq \mathcal P(\Sigma^*)$, the set of all languages, and indeed that is true but only on a technicality: ${\sf NP} \text{-hard} = \mathcal P(\Sigma^*)\setminus \{\emptyset, \Sigma^*\}$. As for whether the diagram implies this or not, that's a matter of interpretation.
The left diagram doesn't have this right diagram's problem because if $\sf P\neq NP$ then $\emptyset$ and $\Sigma^*$ are in $\sf P$, not $\sf NPC$.


What is the average degree of a complete graph and why? Is it correct that the average degree of a complete graph $K_n$, is $(n-1)/n$? or is it only $(n-1)$?

I have the answer of my professor which is $(n-1)$, but I didn't understand why.

In a complete (undirected) graph with $n$ vertices, every vertex is connected to all other $n-1$ vertices, so the degree of every vertex is $n-1$. In particular, the average degree is $n-1$.


Extend binary search There is a way for finding K entries of N given entries using a binary search?

I mean, I have N entries, indexed from 0 to $N-1$ and I have to find $K$ of them that satisfy some constraint.

The naive way is to iterate one after one and check whether it answers the condition or not.
The naive way of Binary Search is using A Binary search until it covers all the tree, this method have a running time $O(K \log n)$.
In this way, I will check whether half of the entries answer the condition or not, if they are I will keep investigating the half of the half and so on.
It's possible to make it more efficient with saving a dictionary from state to its answer.
However, what will be its running time?

Example -
Let's say I have a system and I want to check whether deleting some file corrupt it. The naive way is to delete file after file and to check whether the system behaves normally after each deletion. In Binary search, we can index the files from 0 to N-1 and delete each time half of the files. After each deletion, we can check whether the system behaves normally or not. If it behaves normally, the files we deleted in this step do not affect the system. If not, At least one of the files that were deleted affect the system. I asked, how can I find K files that affect the system?

Thanks.

Your problem is known as group testing. An essentially optimal algorithm for your problem is Generalized binary splitting. There are also pretty good non-adaptive algorithms (such algorithms fix all queries ahead of time).


Is the set of languages recognized by a Turing machine with an oracle countable? I am currently taking a class in complexity theory and I am struggling with this question.

We define a TM with Oracle per. Sipser 6.18 as:

"An oracle for language $B$ is an external device that is capable of reporting whether any string $w$ is a member of $B$. An oracle Turing machine is a modified Turing machine that has the additional capability of querying an oracle. We write $M^b$ to describe an oracle Turing machine that has an oracle for language B."

I think that the answer is potentially false. We know that the set of languages is uncountable and suppose we had a Oracle Turing machine that accepts if the oracle answers YES, reject otherwise. Wouldn't that mean that then the set of languages recognized by TM with an oracle be uncountable?

Every language can be accepted by a Turing machine with an appropriate oracle, for example an oracle for the very language you want to accept. So if you understand "languages recognized by a Turing machine with an oracle" in this way, then certainly their number is uncountable.

Another way to understand this phrase is the you fix the oracle and then ask how many languages are recognized by a Turing machine with access to this specific oracle. In this case the number of languages is countable, since there are countably many ways to specify a Turing machine.


Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph? I've been reading Sedgewick's intro to algorithms book, and he says that the reverse postorder of a digraph's reverse is not the same as the postorder of the digraph, however in both cases it seems that we get the reverse of topological order, so at first I thought that it's the same, but then I looked on his website and he answers "False".

If you think about it, in postorder of a digraph, we first visit every child of the vertex and add it to some queue, hence since the children are visited first, we get the order which is the reverse of topological.

Why does Sedgewick say they're not the same?

I wrote a short example to test the hypothesis and found out that the reverse postorder of a reverse graph is indeed not the same as the postorder of the original graph.
Consider the following graph:

Link to source (archive of image used in original post)

Postorder for the above graph is: 0 1 3 2 4 5.

Postorder for the reverse graph is: 4 5 0 2 3 1.

Reverse Postorder for the reverse graph is: 1 3 2 0 5 4.

You are thinking on the correct lines, but what we should understand is that the postorder of a graph is not necessarily the reverse of the postorder of the reverse graph. This is because of the way we iterate over the vertices when calling the depth-first search. There could be different solutions to the same problem, given the iteration method is different.

And because of this, the reverse postorder of a digraph's reverse is not necessarily the same as the postorder of the digraph.


Find combination of vectors from array that sum up to s I have an array of $n$ $m$-dimensional vectors (in my case, they're 27 dimensional). I also have an $m$-dimensional vector $s$. I want to find all combinations of $k$ vectors from my array whose vector sum is equal to $s$. How to do this efficiently?

The best I could do is just a brute force which is $O(n^k)$ and impossibly slow.

Any help is appreciated.

If $k$ is part of the input, the problem is NP-complete even when $m=1$ (and when we want to know if there's even a single solution). That is, when $m=1$, we essentially have a collection of $n$ values and our task is to decide if there is a subset of those that sum up to a target $s$. This is known as subset sum.

The Wikipedia page lists algorithms that you might be able to adapt to your more general case as well. Also, if $k$ is small enough, you might be able to do something better.


If $B$ is in $SPACE(n^2)$ and $A \leq_p B$ then so $A$ will be in $SPACE(n^2)$? We know that if $B$ is in $P$ and if $A \leq_p B$ then $A$ is in $P$ too.

If $B$ is in $SPACE(n^2)$ and $A \leq_p  B$ then so $A$ will be in $SPACE(n^2)$?

I think that the answer to this question is true, because if $A\in P$ then $A \in PSPACE$, and then $A$ could be in $SPACE(n^2)$. I doubt my answer because of that $(n^2)$.

$A$ may or may not be in $\mathrm{SPACE}(n^2)$.

Any language $A\in\mathrm{P}$ can be reduced be reduced to any nontrivial language $B\in \mathrm{SPACE}(n^2)$ in polynomial time.  Fix your favourite strings $x_\mathrm{yes}\in B$ and $x_{\mathrm{no}}\notin B$ ("nontrivial" means that $B$ is neither $\emptyset$ nor $\Sigma^*$, so both of these strings exist). The reduction is to determine if the input is in $A$; if so, map it to $x_\mathrm{yes}$; if not, map it to $x_\mathrm{no}$.

This is true regardless of whether $A\in\mathrm{P}\cap\mathrm{SPACE}(n^2)$ or $A\in\mathrm{P}\setminus\mathrm{SPACE}(n^2)$.

To get some intuition, it might help to look at it in another way. To show that $A\in\mathrm{SPACE}(n^2)$, you'd want to show that the algorithm "Reduce to $B$, then decide $B$" runs in quadratic space. However, the reduction from $A$ to $B$ might blow up the length of the instance by any polynomial amount.  For example, It could map a instances of length $n$ to ones of length $n^2$. So, now, if you try to decide $A$ by first reducing to $B$, you'll need space $(n^2)^2 = n^4$ to solve  the instance of $B$. Or the reduction itself might take more than $n^2$ space.


Redundancy elimination in the superposition calculus When proving theorems with the superposition calculus, we deal with three kinds of rules:

Generating rules: from pair of clauses A and B, generate new clause C while keeping the original pair, e.g. superposition in the general case.
Rewriting rules: from clause A generate new clause B, e.g. equality reflexivity, equality factoring; superposition with a unit equation can also be regarded as a rewriting rule.
Eliminating rules: delete a clause, e.g. subsumption, tautology elimination.

The question is, regarding the second category, can we perform a strict rewrite, replacing the original clause with the new one, or do we have to keep the original as well as the new one? In the case of equality reflexivity it looks like we can do the former, but for equality factoring and superposition with a unit equation it's not immediately clear whether this would preserve completeness.

Is there a general way of knowing which is the case? Or a list of which needs to be done in each case?

a leading implementation of the superposition calculus theorem prover is E. in its description of their technology it states some basic theory & background under Proof Procedure:

E uses the DISCOUNT [DKS97] variant of the given-clause algorithm. The proof state is represented by two sets of clauses, the set P of processed clauses (initially empty) and the set U of unprocessed clauses. Clauses in U are ranked according to a heuristic evaluation function, and are processed in order. Processing will first simplify the selected clause g with all clauses in P, then simplify P with g (moving all affected clauses from P back into U), and then compute all direct consequences between g and P that can be derived using the generating inference rules (superposition, equality factoring, and equality resolution). The new clauses are simplified with respect to P and added to U, g is added to P.
This proof procedure is different from the given-clause algorithm implemented in Otter (and many provers since), which also uses U for simplification. The variant E uses was first popularized by DISCOUNT, but also is at the core of Waldmeister. Vampire and SPASS implement it in addition to their primary algorithm.

so [iiuc] the word "rewriting" may be somewhat a misnomer in the actual implementations of the theorem proving rules, because the original clauses are never "deleted" & always retained in case they can be affected or combined with later derivations. the rewriting "moves" "rewritten" clauses between $P$ and $U$ in both directions.
ie rewriting is basically like an addition of new derived (true) clauses to a list of known true clauses, and the movement between $P$ and $U$ is a strategy to find new true clauses in an efficient way (basically tracking the "frontier" in a mixed depth/breadth search, ordered by the priority function), and $P \cup U$ is the set of known true clauses.
dont know of a ref for this but think that heres the theory on all this. suppose $A \implies B$ and then $A$ was "deleted". it might still be possible to derive $B \implies A$ by other derivations and clauses. in that case it would have no effect. but if its not derivable by other routes, then in theory it could lead to changing a complete problem into an incomplete problem. dont know of a reference that shows this. it could be a doable exercise for the reader to come up with an example.
fineprint: taking stab at this question due to lack of other responses. am interested in a really authoritative answer to this question also. there is probably a better one than above but this is the best found so far after some research. suspect the question might be better addressed on say math.se, mathoverflow or TCS.se. also found it hard to come by basic descriptions of these concepts & without heavy specialized jargon.


Logic gates from everyday materials Logic gates are an abstract device which can be implemented with electromagnetic relays, vacuum tubes, or transistors.  These implemenations have been successful in computing in part because of various properties of chainability, durability, and size beyond their basic binary stability.  They also work well because electricity is the energy source which can rather easily be shipped around.

I've seen adders built out of wood, marbles, and gravity.  I've seen "lab on a chip" capilary-action-driven prototypes.  I've seen all kinds of specialty mechanical calculators (Curta, slide rule).  I've seen domino trails as single-use logic gates.

I'm interested in other illustrative computing devices that aren't necessarily convenient, durable, or fast, but which exploit properties of everyday materials to perform computation and which are directly visible.  The dominoes trails are close, but are a little too complicated to reset.

Magneto-mechanical arrangements?  Water in pipes/troughs?  More general marble contraptions?

PS.  Here's a new one.  Mechanical CPU Clock

It is possible to build a Turing machine with "Lego" elements without any electric components, only with pneumatic transmission of energy. The guys who did this used some logic gates with pneumatic but this was the very easy part. The underlying automaton was way harder to build. (webpage in French. The other Turing machines in Legos use electronic devices which is very much like cheating)

Moreover I know you can build logic gates using only Lego elements and that may be more relevant.

So mechanics as well as pneumatics are enough to build logic gates.


Can a Turing Machine simulate every possible Turing Machine? Related to my answer on this question, I'm not sure of a detail.

Assume you have a Turing Machine which simulates all possible Turing Machines all at once (meaning it does not "page" its data, i.e. it can't erase data from one "process" to write data from another "process"; it must keep all "processes" "in memory" at the same time).  Then, this Turing Machine must simulate itself, because it is a Turing Machine and the definition of this machine is that it simulates all possible Turing Machines.  It must also simulate the simulation of itself, and the simulation of that, and so on, infinitely recursive.  Therefore, this Turing Machine must have infinite data on its tape.

My question is, can this Turing Machine exist, and why or why not?

Your conclusion "this Turing Machine must have infinite data on its tape" is not accurate.  Everything up to that point is basically fine, but that one statement is not correct.

Turing machines never have an infinite amount of data on the tape at any one time.  At any point in time, they have a finite amount of data on the tape.  However, this amount might increase over time without limit.  That's not the same as saying that at any point the amount is infinite.

An analogy: imagine I start counting out loud 1, 2, 3, 4, 5, 6, etc., without ever stopping.  At any point in time, the number I said aloud is finite.  However, there is no fixed upper bound on these numbers; they increase without limit.

It's the same with such a Turing machine.  Call this machine $M$.  It simulates all Turing machines in parallel, but crucially, each simulation proceeds at a reduced speed.  $M$ itself will be one of the machines being simulated, but at a reduced speed: say, 1000x slower (just to make up a number).  So, $M$ is simulating $M$ running 1000x slower.  That means it is also recursively simulating $M$ running 1000000x slower, and so on.  (And because the simulated $M$ is running slower, it writes to the tape more slowly, so the size of the tape grows slower.)


Reduce $\sqrt{n}$-CLIQUE to CLIQUE Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices. Define CLIQUE as the decision problem

$$\{ \langle G, c \rangle \mid G \text{ has a clique of size } c\}$$

Define the problem $\sqrt{n}$-CLIQUE as follows:

$$\{\langle G \rangle \mid G \text{ has a clique of at least size } \sqrt{n}\}$$

where $n$ is the number of vertices of $G$. It is easy to reduce $\sqrt{n}$-CLIQUE to CLIQUE. How can we go the other way and thereby show that $\sqrt{n}$-CLIQUE is NP-complete?

Idea: If $c \geq \sqrt{n}$, we can add dummy vertices to $G$ until $c = \sqrt{n}$. What do we do if $c < \sqrt{n}$? It seems we need to be able to remove vertices without disturbing the size of the largest clique. My idea in this case to remove a vertex if it has less than $c-1$ edges. Obviously the new graph has a clique of size $c$ if and only if the original graph does. But what happens if we can't remove enough vertices? Can we conclude that if a graph has $n > c^2$ vertices each with degree $\geq c$ then a clique exists?

When $c > \sqrt{n}$, you add an independent set of size $m$ so that $c = \sqrt{n+m}$ (i.e., you need $m = c^2-n$).

When $c < \sqrt{n}$, try doing the same, increasing both $n$ and $c$ at the same time, by adding a complement of an independent set. (You might need to add a few isolated vertices as well.)


Complexity of parity game solving compared to PLS, PPA, and PPAD Since parity game solving is in TFNP ("Total Function Nondeterministic Polynomial") (and the decision version is is NP ∩ coNP), I wonder whether it is contained in PLS ("Polynomial Local Search") or PPA ("Polynomial Parity Argument")? Add PPP ("Polynomial Pigeonhole Principle") if you want, even so this would probably mean that it is already contained in PPAD ("Polynomial Parity Arguments on Directed graphs"), and hence in PPA.

Or is it rather the other way round and parity game solving can be shown to be hard for PLS or PPAD? But that would be surprising, since a recursive algorithm that solves parity games is known (even if it is not efficient in the worst case).

Edit 12 March 2017: I recently learned that parity game solving has been shown to be possible in quasipolynomial time. Here are the quoted references:

  Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.

  A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus Ibsen-Jensen.

  Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić.

An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):

An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space, by John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak

Yes, solving parity games is known to be in PPAD (and thus PPA and PPP too) and PLS, and is thus unlikely to be hard for either (since this would imply containment of one of these classes in the other).

See, e.g.,

Daskalakis, Constantinos, and Christos Papadimitriou. "Continuous local search." Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 2011.

and combine the membership of Simple Stochastic Games (SSGs) in CLS (which is in PPAD and PLS) with the well-known observation that solving parity games can be reduced to solving SSGs in polynomial time.

The reason that these problems are in PPAD is that they admit "optimality equations", rather like Bellman equations, that characterize solutions as fixed points. The reason these problems are in PLS is that they can be solved with local improvement algorithms like strategy improvement (a two-player generalization of policy iteration for MDPs).


NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time.

My question is, if asking for an algorithm that only provides yes/no, or solvable/not solvable, without providing an exact solution of the 3-SAT formula, will this result in another complexity class?

The reason I have in mind of asking this, is a similar situation when looking for prime numbers and factorizations. Where it is known that it's much easier to test if a number is a prime number yes/no, than to find an exact prime factorization of a number.

Short answer: if you can solve the decision (yes/no) problem, calling that tells you if it has no solution; if there is a solution, pick a variable and set it to true, see if the result can be satisfied; if not, it has to be false. This way, with one call to the oracle per variable you get a "solution" (set of values of the variables making the expression true, it here are any). Thus the cost of the search problem isn't "too much more" (multiply by the size of the input --number of variables-- is polynomial).


Can someone explain the logic diagram for the Boolean expression NOT A OR B AND C An IB question requests:
Construct the logic diagram for the Boolean expression NOT A OR B AND C.

The answer

looks to me like not A or (B and C), whereas what I expected only gets partial credit. Can someone explain?

The question is assuming that the operators precedence goes $NOT \rightarrow AND \rightarrow OR$, which is pretty standard for boolean logic.

Hence the proper parathensization would be $\text{((NOT A) OR (B AND C))}$, which correspods to the correct diagram, whereas the partial credits corresponds to $\text{(((NOT A) OR B) AND C)}$, which would just be a left to right evaluation of the operators.


Need for random bits in final PCP theorem statement PCP theorem states that $$PCP(O(\log n),O(1))=NP.$$ Could we not run through $O(\log n)$ bits deterministically?

Does PCP theorem statement mean any set of $O(\log n)$ random bits out of $2^{O(\log n)}$ choices of such bits suffice? If so, why cannot I choose all $0$ bits? If not why not?

The statement of the PCP theorem is essentially equivalent to the following statement:

  For every problem in NP there is a reduction $f$ to $O(1)$-FUNCTION-SAT such that if $x$ is a YES instance then $f(x)$ is satisfiable, whereas if $x$ is a NO instance then at most half of the clauses of $f(x)$ can be satisfied.

Here an instance of $k$-FUNCTION-SAT consists of a collection of "clauses", each an arbitrary function on $k$ inputs.

Where did the parameters $O(\log n),O(1)$ in the PCP theorem disappear? The first parameter is the logarithm of the number of clauses, so there are $2^{O(\log n)}$ clauses; the second parameter is the arity of the clauses. Together, these parameters guarantee that the FUNCTION-SAT instance has polynomial size, and so the reduction runs in polynomial time.

PCPs are not always described this way, but the descriptions are equivalent. Proof of the equivalence left to the reader.

You are enumerating over all choices of $O(\log n)$ when you are constructing the FUNCTION-SAT instance. But it only allows you to construct the instance, not to tell whether it is satisfiable or not; that is an NP task.


Equivalence of PDA and a counting PDA Lets define a counting PDA as equivalent to a PDA except that the transition relation can use the stack size.

Formally, let's define the transition relation as
$\Delta:Q\times (\Sigma \cup \{ \epsilon \}) \times (\Gamma\cup\{\epsilon\})\times \mathbb{N} \to P(Q\times (\Gamma\cup \{ \epsilon \}) )$

Meaning that $(q,\beta) \in \Delta(r,\sigma, \alpha, n)$ means that when the automaton is in state r reading the symbol $\sigma$, the head of the stack contains $\alpha$ and we have n items in the stack, then we can remove $\alpha$ and insert $\beta$ and transition to q.

My question is whether the family of automata created by this definition of a counting PDA is equivalent to family of PDAs.

Nope.  A counting PDA is more powerful than a PDA... even more powerful than a Turing machine.  It can recognize undecidable languages.

Proof: Let $L \subseteq \{1\}^*$ be an undecidable unary language.  It's easy to build a PDA that pushes one symbol on its stack per symbol on the input tape.  Then the height of the stack fully encodes the input word.  Thus its final transition can in one step decide whether the input word is in $L$, by "encoding" $L$ fully into the transition relation $\Delta$.

In retrospect, this is perhaps not too surprising.  A counting PDA is not physically realizable.  A PDA has a finite description.  A Turing machine has a finite description.  A counting PDA does not.  Thus, it's not too surprising that it might be more powerful.

Or, to put it another way, because they have a finite description, there are only countably many PDA's and only countably many Turing machines; but there are uncountably many counting PDA's.  As a result, it's not surprising that there exists a language accepted by a counting PDA that isn't accepted by any PDA (or any Turing machine) -- for this not to be the case, there would have to be some enormous equivalence among counting PDAs that map the uncountably many counting PDAs to only countably many languages.

How do we know there exists an undecidable unary language?  Well, let $L_2 \subset \{0,1\}^*$ be any ordinary undecidable language in binary.  Now map each word $x \in L_2$ to its unary encoding; this gives you a unary language $L_1$.  Then $L_1$ must be undecidable too (because the mapping is computable).  For instance, the binary word $110$ maps to the unary word $1^6$, since $110$ is the binary representation of 6.  (Strictly speaking, we must adjust the encoding slightly, to make sure that $110$ and $0110$ don't map to the same thing, but that's easy to fix up.)


Runtime of Divide and Conquer Flavored Bogo Sort Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively.

https://en.wikipedia.org/wiki/Bogosort.
Input: An unsorted array A[1...n].
Output: A sorted array.

Let's remind ourselves of why normal Bogo Sort's runtime is O(n!).

Let's say we were to randomly guess the smallest element of an array. What are our odds of guessing right? Our odds would be 1/n of course. Let's say we guessed right! Now let's try to randomly guess the second smallest element of an array, after guessing the first right. What are our odds of guessing right? Our odds would be 1/(n-1) of course.

$$\frac{1}{n}*\frac{1}{n-1}*\frac{1}{n-2}\; * \;... \;*\; \frac{1}{n-n+1}$$
Expectation is n!

Let's use a Divide and Conquer strategy on Bogo Sort to improve the runtime. We will use a modified Merge Sort to achieve this. We recall that merge sort merges two sorted arrays recursively. Can Bogo Sort take advantage of the fact that we are merging two already sorted arrays? Let's say we were to randomly guess the smallest element of two sorted arrays. We know that the smallest element of both can only ever be the first element of one of these two arrays. If we randomly guess from just the first two smallest elements in each array, what are our odds of guessing right? Our odds would be 1/2. This sounds better than 1/n, but let's look at an example recurrence tree.

Example Recurrence Tree:
n = 4               brackets [ ] represent a merge being performed.

$$[\frac{1}{2}*\frac{1}{2}*\frac{1}{2}*\frac{1}{2}]$$
$$[\frac{1}{2}*\frac{1}{2}]\;+\;[\frac{1}{2}*\frac{1}{2}]$$
$$[\frac{1}{2}]+[\frac{1}{2}]+[\frac{1}{2}]+[\frac{1}{2}]$$

[Depth 0] Expectation is 16
[Depth 1] Expectation is 4 + 4 = 8
[Depth 2] Expectation is 1 + 1 + 1 + 1 = 4

Note, that in our base case we only need sort two values, guess between two values, a total of n times.
From the above, we see the expected runtime of D&Q Bogo Sort:

Runtime: $$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$
Recurrence: $$T(n) = 2T(n/2) + O(2^{\frac{n}{2^i}} * 2^i)$$ i++ each recurrence

  I need help confirming the runtime. My assumption originally was that
  the runtime is simply O(2^n). However, I believe I need a log( ) in
  there somewhere. I am unsure how to apply the Master Theorem to O(2^n) in my
  hypothesized recurrence:

$$2T(\frac{n}{2}) + O(2^n)$$

We have successfully reduced Bogo Sort from factorial runtime to exponential runtime using divide and conquer. Let me know how I can improve my analysis.

The solution to the recurrence $T(n) = 2T(n/2) + O(2^n)$ is $T(n) = O(2^n)$.


Is there a concept for an algorithm computing a function by first finding another algorithm? If I understand it correctly, an algorithm that computes the value of a real function $f$ has computational complexity $O(g(n))$ if the following holds:
When we compute $f$ to precision $\delta$ requires on the order of $g(n)$ steps.

However, what if we have an algorithm that first "finds a more efficient algorithm to compute $f$", and then computes $f$?

  In other words, what if we have an algorithm $A$ that does the
  following:

  Find an efficient algorithm $B$ for computing $f$.
  use $B$ to compute $f$.

In that case, we can no longer speak of the computational time it would take to compute $f(5)$ for example,  because it fully depends on whether Algorithm $A$ has already found algorithm $B$. In other words, the computing time required to compute $f(5)$ if $5$ is the first comoputed number is far greater than the computational time required to compute $f(5)$ after $f(3)$ is already computed.

My question is, is there a concept/theory about this kind of algorithm that first finds another algorithm before computing a function? Specifically I am wondering about analysis of the computational complexity of such algorithms.

There is a well-known algorithm, Levin's universal search algorithm, whose mode of operation is identical. Consider for example the problem of finding a satisfying assignment for a formula which is guaranteed to be satisfiable. Levin's universal search runs all potential algorithms in parallel, and if any algorithm outputs a satisfying assignment, stops and outputs this assignment. If the optimal algorithm for the problem runs in time $f(n)$, then Levin's algorithm runs in time $O(f(n))$ (with a possibly huge constant) if implemented correctly.

While Levin's algorithm is impractical (due to the huge constants involved), it is very interesting theoretically. See the Scholarpedia article for more on universal search.


Overlaying Two Matrices So That Sum Of Squared Differences Is Minimized I have a question about my solution to a problem from Hackerrank.  The problem is, given $R,C,H,W$ with

$1\le R,C\le 100$,
$1\le H\le R$,
$1\le W\le C$,

an $R\times C$-matrix $L$ and an $H\times W$-matrix $S$, to find $i,j$ with $0\le i\le R-H$ and $0\le j\le C-W$ which minimize the sum $$\sum_{0\le k< H,0\le l< W}(L_{i+k,j+l}-S_{k,l})^2$$ (where I use 0-based indexing).

My first attempt, which performed best, was to try out all $i,j$, store the best result so far in a variable, and stop calculating each sum as soon as it exceeds the best result from the previous runs.

Then I thought of something else (which unfortunately didn't perform that well): I want to run all the sums in parallel and advance those first which look most promising for returning a small result.  So I make a list containing $[i,j,c,m,p]$ for all $i,j$, where $c$ stores how many indices I already calculated of the sum, $m$ stores the intermediate value of the sum and $p$ stores the interpolated value of the finished sum (scaled by $HW$), which I set as $m/c$ for $c>0$ and some arbitrary $x$ else.  So in the beginning all elements will look like $[i,j,0,0,x]$.  I will then advance the first element of the list, which means I increment $c$ by one, $m$ by a new square and then recalculate $p$.  Afterwards I move the first element upwards so that the list is always sorted by $p$.  I also keep track of the best finished sum so far together with its $i,j$-indices.  If the new first element is a finished sum ($c=HW$) then I throw it away (and possibly update the best result).  After the list is empty, the indices of the best result get returned.

I guess the resorting process takes too much time for this to perform well.  I also tried using for $p$ a different function $f(m,c)$ which puts more emphasis on $c$ so that less resorting takes place.  If $f(m,c)=1/c$ and $x>1$, this gives roughly the first algorithm I described, with the good performance.

My question: Is this idea any reasonable?  If yes, what values for $f(m,c)$ (and possibly $x$) could yield better performance than $1/c$?

I try to summarize the results of the discussion in the comments:

Using a heap instead of a list would be better suited for the proposed idea since all operations to be performed on the list are sorting, returning the smallest element and changing an element followed by resorting the list.  These are almost exactly the operations supported by heaps, which will deliver better performance.
The sums $\sum_{k,l} (L_{i+k,j+l}-S_{k,l})^2$ can be expressed as $A_{i,j}+B_{i,j}-2C_{i,j}$ where $A_{i,j}:=\sum_{k,l} L^2_{i+k,j+l}$, $B_{i,j}:=\sum_{k,l} S^2_{k,l}$ and $C_{i,j}:=\sum_{k,l}L_{i+k,j+l}S_{k,l}$.  Here $B_{i,j}$ does not depend on $i,j$ and $A_{i,j}$ can obtained from its predecessor $A_{i',j'}$ by only updating two rows or columns, if the order in which the $i,j$ are perused is chosen wisely.  Most importantly, $C_{i,j}$ describes a convolution, which can be calculated very fast by FFTs, convolution in the frequency domain corresponds to (pointwise) multiplication in the time domain!  But even without implementation of FFT, this algorithm scores better than the naive approach, as it only performs one operation (multiplication) instead of two (subtraction and squaring) in the large (size $HW$) sums.


How is code executed in the computer I started to learn about compilers and interpreters. But I still can't understand how program execution happens under the hood.
This is what I have understood so far.
Compiler
The Compiler does not run a code, instead, just converts the code into another (low-level) code. This part is clear to me.
Interpreter
First I thought the interpreter converts some high-level code or byte code into machine language and then executes it.
But then I realized that interpreters not convert code into machine code, instead, that instruction becomes an input to the interpreter application and it activate some particular function of the interpreter, which has been already converted into the machine code.
Refer to this pseudo code. Imagine I create a programming language that is interpreted by an interpreter created by python.
add 5 + 3
sub 5 - 3

Interpreter
def add(a, b):
    print(a+b)

def sub(a,b)
    print(a-b)

# Parsing
code = [] #list of instructinos

for instruction in code:
    if instruction.command == "add":
        add(instruction.a, instruction.b)
    elif instruction.command == "sub":
        sub(instruction.a, instruction.b)
    else:
        print("incorrect instruction)

I am not sure whether my understanding of the interpreter is correct. If it is not, I want to know how the interpreter works internally. I mean how the interpreter executes a code without translating it into machine code.

I mean how the interpreter executes a code without translating it into machine code

TL;DR It's the interpreter's (machine) code that executes your program's code.
To explain it better, consider these lines taken from your example:
def sub(a,b)
    print(a-b)

I think you got this point wrong: when you write x-y in an interpreted programming language it's because you want to know the result (for example to save it into a variable) rather than to be printed. Also, the variables of the interpreter are not mixed with the ones of the interpreted programs: for example the variables x and y could have some meaning for the interpreter and another meaning for the final program. Usually the interpreter does not make any assumption on the program's variable, it just stores them into a "memory" which is just a set of pairs <variable_name, value>.
So, when there is an instruction like z = x-y in your program, the interpreter does the following:

look into the memory, retrieve the current value for x
look into the memory, retrieve the current value for y
compute x-y (call the result R).
set the value for z to be R in the memory.

Point 3. in the list above is crucial. If this was a real interpreter, it would not be a Python program but a compiled one, thus the implementation of point 3. would be a bunch of machine code that eventually contains a sub machine instruction, or some other sequence of machine instructions that together implement the subtraction.
So every instruction of every language is executed as machine code eventually:

in the compiled languages the higher level instructions are translated into machine code;
in the interpreted languages it's the interpreter's machine code to be executed.

Read the last paragraph again.
Actually you could write an interpreter using Python, but in this case it's the Python interpreter's machine code to be executed. Or it could have been any chain of pairs <interpreted language $L_i$, interpreter for $L_i$>, the point is that the last interpreter must be compiled, and thus at the very last it's just machine code to be executed because that is the only languages that the processor understands


Is there a function $t$ fulfilling $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$? $f:\mathbb{N} \to \mathbb{N}$ is in $\mathcal{O}(0)$ only if $f(n) \neq 0$ for a finite number of values of $n$. Therefore, $\mathcal{O}(0) \subset \mathcal{O}(1)$ strictly. Is there something in between, i.e. a function $t:\mathbb{N} \to \mathbb{N}$ with $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$?

Yes, for example: $f(n)=\cases {0&$n\in\mathbb{N}_{even}$\\1&$n\in\mathbb{N}_{odd}$}$
This function is not in $O(0)$, since it has infinitely many $1$'s, but also $1$ is not $O(f)$ since it has infinitely many $0$'s.
To see more clearly why $1$ is not $O(f)$, consider any constant $c>0$ and any constant $n_0\in \mathbb{N}$. Then, if $1 \le c\cdot f(n)$ for any $n>n_0$, we will have that for any $n_0<n\in \mathbb{N}_{even}$, $1 \le c\cdot f(n) = c\cdot 0 = 0$ which is a contradiction. Hecne $1\notin O(f)$.
Therefore $O(0)\subsetneq O(f)\subsetneq O(1)$.
However, for computer science usages, as Pal GD said, we consider only monotonically increasing functions - in which case there is no such $f$.


How to correctly contract an edge in a network? Assuming an adjacency list as data structure of a directed Graph, it is not completely clear to me how "contraction of an edge" is defined.

Let me cite the definition I do have at hand:

Source: JAMES B. ORLIN - A FASTER STRONGLY POLYNOMIAL MINIMUM COST
FLOW ALGORITHM, Section 4.1. Contraction

  [...] any edge, say $(k, \ell)$, can be contracted into a single node $p$. The contraction operation consists of: letting $b(p) = b(k) + b(\ell)$ and $e(p) = e(k) + e(\ell)$; replacing each
  edge $(i, k)$ or $(i, \ell)$ by the edge $(i, p)$; replacing each edge $(k, i)$ or $(\ell, i)$ by the edge $(p, i)$; and letting the cost of an edge in the contracted network equal that of the edge it replaces.[...]

$b$ and $p$ are functions defining values for certain properties of a node; their meaning is unimportant for understanding contraction.

Consider the following graph described in "adjacency speak", where e.g. node 0 has an edge to the nodes 1, 2 and 5; node 5 has no outgoing edges; node 3 has an edge to node 4 and so on...

0 -> 1, 2, 5
1 -> 2, 3
2 -> 1
3 -> 4
4 -> 5
5

Now I want to contract the edge $(1,2)$. Note that there is an edge $(2,1)$, too. Should the application of the contraction operation yield the following directed graph, where the newly introduced node $p$ has the id $6$?

0 -> 6, 5
3 -> 4
4 -> 5
5
6 -> 3, 3, 5, 6 # Note that we got two edges from node 6 to node 3.
                # Note that we also have an edge from 6 to 6, i.e. a loop.

Thanks a lot!

The very next sentence (!) of Orlin's paper says

  We point out that the contraction operation may lead to the creation of multiple arcs, i.e., several arcs with the same head and tale nodes.

In some contexts, you might want to replace multiple arcs between the same two nodes with a single arc whose weight (or capacity or whatever it's being called) is the sum of the weights of the original arcs; in other contexts, it might make more sense to keep them separate.  Orlin is keeping them separate.

For example, if the arcs represent trading relationships between companies, it makes sense to merge the arcs: if companies $A$ and $B$ both sell to $C$ and $A$ and $B$ merge, it makes more sense to say that $C$ is a customer of the new company once, with a single arc, than to say that it's a customer twice, by having two arcs. On the other hand, if arcs represent roads between towns and two towns merge, it makes sense to keep the arcs separate: if there's a road from each of $A$ and $B$ to $C$ and $A$ and $B$ merge, there are still two roads from the merged town to $C$.

So, contracting the arc $(1,2)$ into a new node $6$ has the following effects:

it converts the arc $(1,2)$ into the loop $(6,6)$;
it converts the arc $(2,1)$ into a second copy of the loop $(6,6)$;
replaces the arcs $(0,1)$ and $(0.2)$ with two copies of $(0,6)$;


Is the class of Turing-recognizable languages closed under Homomorphism? Would this proof work?

Given a language $L$ that is Turing recognizable and a TM M that recognizes it and a homomorphism $f$, we build a NTM M' that recognizes $f(L)$,

M' looks like this:

On input $w$ :

-Non-deterministicly feed words from $\Sigma^{*}$ to $f$ until you obtain w.

-run M on $f^{-1}(w)$, if M accepts accept, otherwise reject.

Your proof has a flaw.

Assume $L=\{b\}$, and $f(a)=f(b)=w$ for some word $w$. We have $f(L)=\{w\}$.

TM $M'$ on $w$ finds the preimage $a$, then checks $a\not\in L$, and rejects. This is wrong, since $w$ should be accepted.

The point is, we should not reject $w$ just because we found a preimage of $w$ which is not in $L$. We should continue checking all such preimages.

Above, doing that we would consider $b$ as well, and cause $w$ to be accepted.


Trying to tag parts of a word and keep track of any changes that happen to those parts I'm a researcher working with a language that has gone through phonological changes through time.  I would like to tag parts of a word (i.e. prefix, stem, suffix) and then apply those phonological changes and then see what is left or different about the stuff that I tagged.

I'm currently using Python with some regex stuff to apply the changes so if I can do this using its NPL toolkit that would be perfect.  I've start to mess around with it but I haven't found anything that will work just yet.  I'm also not sure if this toolkit would be the best for this.

For example, I apply the following transformation to tag re, peat and ed in repeated:
$$
\begin{align}
  \mathtt{repeated}
  & \xrightarrow{\mathtt{rep} \mapsto \mathtt{rp}} \mathtt{rpeated} \\
  & \xrightarrow{\mathtt{ea} \mapsto \mathtt{e}} \mathtt{rpeted} \\
  & \xrightarrow{\mathtt{d}\$ \mapsto \epsilon} \mathtt{rpete} \\
\end{align}
$$

I would like to be able to find out what is left of the stuff I tagged.  So I'd like to see that r is all that is left of the prefix, pe is all that is left of the stem, etc.  Any help or direction is greatly appreciated!

You can use sequence alignments with a suitable score. You then get something like this:

$\qquad\displaystyle
\begin{array}{cccccc}
  r & e & p & e & a & t & e & d \\
  r & - & p & e & - & t & e & -
\end{array}$

Now, if you have marked the original word, you can read off that -- according to your alignment score -- only "r" is left from the prefix, "pet" from the stem and "e" from the suffix.

The score makes a difference when parts may be assigned to e.g. prefix or stem. Levenstein/edit distance and Damerau-Levenstein distance may be good starting points. Play around with the penalties a bit; note that you can assign costs depending on whether you match against prefix, stem or suffix (if you have marked the original words) and use things like affine gap costs.


Conversion from assembly program to low-level machine language While studying COMPILER-DESIGN through an online book from Google Books, referenced as Compiler Design by A.A.Puntambekar, I got stuck across a line. Actually, I am more curious to know the inner-detail.

  The assembler converts the assembly-program to low-level machine
  language using two passes. A pass means one complete scan of the input
  program. The end of the second pass is the relocatable machine code.

Why the 2 passes for conversion and what are the phases involved like lexical analysis,syntax analysis,etc while conversion from assembly to machine-code??? I have very less/no idea about it.

If someone over here would like to describe those two-passes or link out to some good resources, I'd be thankful to him/her.

The first pass can't resolve any forward jumps.  For example:

    cmp r1, 0
    bne label
    add r2, r3, r4

label:
    add r3, r4, r5

On the first pass, when the assembler gets to the bne label instruction, it doesn't know how far the branch needs to jump because it hasn't seen label yet.  On the second pass, it knows where all the branch targets are located and therefore it can go ahead and generate the proper branch/jump instructions at that time.


Question about the CLRS Linear Programming chapter I'm currently reading the CLRS Linear Programming chapter and there is something i don't understand.
The goal is to prove that given a basic set of variables, the associated slack form is unique
They first prove a lemma :

And then they prove the result :

My concern is that to prove the second lemma, they apply the first lemma. However equations (29.79) -> (29.82) only holds for feasable solutions, which is not for any x, so why can they apply the first lemma ?

Lemma 29.4 mentions an LP, because that is what they need it for, but it is really a statement in linear algebra about the system of equations $Ax=b$ and a linear form $\phi(x)=c\cdot x$, which in the LP is the objective function.

Lemma 29.4:
If the variables $x_i,i\in B$ are basic variables, i.e. if the corresponding columns of $A$ are a maximal set of linearly independent columns, then you can solve for those variables in terms of the rest of the variables $x_i,i\in N$ and the polynomials obtained are unique. In addition, if you write $\phi(x)=\psi(x_i,i\in N)$, the polynomial $\psi$ is also unique.

(Well, this version of the lemma includes the assertion that one can solve for those variables. This is due to Gaussian elimination.)
Now, for the uniqueness, as they did, you assume that you have two expressions of the basic variables in terms of the non-basic ones
$(x_i)_{i\in B}=(b_i)_{i\in B}+S(x_j)_{j\in N}$ for some matrix $S$ and $(x_i)_{i\in B}=(b_i')_{i\in B}+S'(x_j)_{j\in N}$.
So the polynomials $(b_i)_{i\in B}+S(x_j)_{j\in N}$ and $(b_i')_{i\in B}+S'(x_j)_{j\in N}$ are the same.
By definition $(b_i)_{i\in B}=(b_i')_{i\in B}$ and $S=S'$.
There is no real need to talk about values of the variables, since all the statements are purely algebraic, in the ring of polynomials in the variables $x_i$. So, there is no need for Lemma 29.3. Of course, the equations written have to be thought as equations between polynomials and not as equations between values of functions that are satisfied for all values of the variables. Ignore this paragraph if it causes confusion.


Is there a difference between "marking", "configuration" and "state" in Petri nets? When finding sources for certain definitions related to Petri nets, I found that there seem to be three ways of referring to "which tokens are located in each place":

Configuration (e.g. in Sequential Configuration Graph, also referred to as a reachability graph)
Marking (e.g. initial marking)
State (e.g. in State Space analysis).

Is there a subtle difference between these terms, or can they all be used for every type of Petri net?

For standard Petri nets, configuration, state and marking are the same thing.
The term marking is standard. State is probably best avoided, as novices may confuse it with place.

For extended Petri nets (e.g. timed Petri nets), a configuration may contain more information than just a marking.


If both the concatenation of two languages and the second "half" are regular, is the first too? Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular.

I need some help on getting started on proving this is the case.

My intuition is that if $L_1 \cdot L_2$ is regular there exists a DFA for it, in which case you can just remove the states that correspond to the $L_2$ part of the DFA and you are left with a DFA that recognizes $L_1$.

Suppose that $L_2 = \Sigma^*$ and $L_1$ includes the empty string. Then $L_1 \cdot L_2 = \Sigma^*$, yet $L_1$ doesn't even have to be computable.


Balanced weighting of edges in cactus graph Given a cactus, we want to weight its edges in such a way that

For each vertex, the sum of the weights of edges incident to the vertex is no more than 1.
The sum of all edge weights is maximized.

Clearly the answer is no more than $\frac{n}{2}$ for $n$ vertices ($\sum d_i = 2D$ where $d_i$ is the sum for one vertex and $D$ is the sum over every edge). This bound is achievable for cycle graphs by weighting each edge 1/2.

I found a greedy algorithm for trees. Just assign 1 to edges incident to leaves and remove them and their neighbors from the graph in repeated passes. This prunes the cactus down to a bunch of interconnected cycles. At this point I assumed the remaining cycles were not interconnected and weighted each edge 1/2. This got 9/10 test cases but is, of course, incomplete.

So, how might we solve this problem for cacti in general? I would prefer hints to full solutions, but either is fine.

This question involves a problem from an InterviewStreet CompanySprint. I already competed but I'd like some thoughts on a problem (solutions aren't released, and I've been banging my head against the wall over this problem).

So this question has been bothering me: why a cactus, if there's already a linear-time algorithm for a more general class?

The primal problem is known as the fractional matching problem, and, unsurprisingly, it has been studied as well. Balinski (whose result was made known to me via Schrijver's book Combinatorial Optimization) characterized the extreme points of the fractional matching polytope as consisting of an integer matching plus half of a collection of odd cycles. Given the relatively low input limits, I suspect that the intended solution of the problem poser was to modify Edmonds's blossom algorithm in a way that, for now, I will leave for you to discover. The structure of the cycles in a cactus makes this algorithm simple enough to be appropriate for a contest.

As sxu points out, this problem is amenable to linear programming. If you need just the objective value, the dual LP has the same objective value and is the fractional vertex cover problem. The nice thing about vertex cover is that it has a half-integral optimum; in linear time, you can use depth-first search to compute a tree decomposition of the cactus of width O(1) and solve the dual LP with a dynamic program that tries variable values in {0, 1/2, 1}.

If you actually need a solution for the primal, then complementary slackness might help, but I can't help but suspect that the restriction to cacti is supposed to allow a more elementary solution.


Can the turing machine accept these type of languages in O(n)? or better? $L = \{a^n b^n c^n ... d^n | n > 0\}$ $L = \{a^n b^n c^n ... d^n | n>0 \}$

so for example $L = \{a^n b^n | n>0 \}$ , $L = \{a^n b^n c^n| n>0 \}$ and such

can the turing machine accept these in O(n)? if yes then what about a better time complexity like O(logn) or O(1)?

my take on this is: yes because we can use n number of tapes and we go through all of them word by word altogether, but a book i was reading said the best time is $O(n^2)$ so i got confused, maybe it was referring to standard turing machine but idk

so my question is this :

can a turing machine do this in O(n) ?
if yes, then is there a better time complexity?

Yes a TM with multiple head for example can easily do this. for $a^nb^n$ you can have two heads one at the first occurence of A's and other at the first occurence of B. Then at each iteration you can cross each off. If both see blank accept. If A head does not see A or B head does not see a B reject. Else cross both off with some special character.

Clearly this takes one linear pass in time O(N). Now for the lower bound. It is not possible to do with less than O(N). If you use N number of tapes by definition then it is $\Omega{(N)}$. If you use K number of tapes then it is $K \times (N/K)$ which is still O(N). The reason for this lower bound is that you have check each character since any one character can break the rule of this language. Thus we get a linear lower bound.