Turing machine working only with 1's and blanks - how to encode input? Let's say we have a Turing machine which head can only write 1 or blank to the tape (although it can read all symbols from any input alphabet correctly). Can we operate with it on any input?

My approach was that we can rewrite our input tape with unary coding and symbol-codings separated with blanks. If we had, for example, an input

...[][]0123[][]...

we could try to encode 0 as 1[], 1 as 11[] and so on. We would know when we reached the end of our input word when we read two blanks in a row. However, rewriting the example string from above would cause some problems. When we code a single symbol with multiple ones, we overwrite another symbols and need to remember them in state. In the example above, after encoding 0 our tape would be like

...[][]1[]23[][]...

And in our state we'd remember that we need to encode 1 now. Hovever, writing the encoding would overwrite 2, 3 and a blank, so we would need to remember those ones as well in the state. Such an approach leads to creating a lot of states: for n-letter alphabet and unary encoding I proposed it would be $(n+1)^n$ (all possible combinations of symbols on n+1 positions on the tape) "basic states", and for each of those we'd need a few more so that we could write an adequate number of "1" finished by a blank. I am not sure if this is acceptable at all.

Is my approach correct? What other approaches could I take?

In the following, I use "0" to denote a blank cell, and I first assume that 1 is not used in the original alphabet. I will deal with this at the end.

A first solution is possible if you assume that the head can go over a cell and read it without writing on it.

If you assume that you can tell the two ends of your input, the answer
to your question is just that you copy/translate the input to unary form on some
other part of the tape, so that you do not run the risk of erasing a
part of the input that has not been copy/translated yet. If you
copy/translate the input from left to right, you start the copying on
some part of the tape that is on the right of the original input.

For that purpose, you need markers, and you can for example use 010 to
mark the place where you copy the translation of the next symbol. You
can erase original symbols as you copy them, and possibly also mark
the last erased symbol with 010 (wich you then do not use as
translation of an original symbol). Part of the control is teh used to
move bertween the two 010 marks during the translation phase.

But you cannot make the number of states dependent on the length of
the input. The TM uses the same finite state control independently of
input size, which implies not changing th number of states.

If you do not allow reading a cell without overwriting it, things are
more complicated. I further assume that the head is initially on the
left side of the input. In ordr to make a copy translation without
destroying the input, one has to start from the left, and make the
copy further on the left.

Since it is impossible to foresee how much space will be needed, the
trick is to copy/translate the input into a mirror image, so that it
grows on the left, and never risk erasing the original input.

Then you can either decide to compute with a mirror image, or you can
just make a second pass on the copy/translated input, so as to reverse
it again and have it in the right order.

Using 1 in the original input.

I think that it is possible to do the same when 1 is used in the original alphabet. But one must be very careful not to confuse its use in the original input, and in the copy part. This can be done with a specific configuration appearing only a fixed number of times in the created copy, the rightmost one dentifying precisely the beginning of the rest of the original input to be copied.


Efficient traffic allocation Users can be assigned to one experiment on my site. I have an API that developers use to trigger logic for each experiment. They call ExperimentEngine.run() to trigger the code logic for the experiment.

I would like to allocate users to each experiment, at the point where a user might be exposed to the logic for that experiment. I would like to assign users to experiments such that experiments implemented downstream (on pages that are usually seen last) still get users assigned to them.

For example, if user A is runs into the code logic for experiment A at login and then goes to page B and runs into experiment B, the user A could be assigned to either experiment A or B. That means that they will only see one of the experiments and not both (either A or B) or neither. I would like to figure out the right algorithm so that experiment B (which is downstream and shown to the user after they've seen experiment A) gets users assigned to it. I don't to assign all users to experiment A.

So the flow is as follow

User visits page A where experiment A is implemented
We decide whether to assign users to experiment A. If user is assigned to A, user will be able to see experiment A.
User visits page B where experiment B is implemented, we decide whether to assign users to experiment B
Users can only see experiments that they are assigned to.
I want to come up with an algorithm that allows me to assign users to
experiments regardless of where on the site they are implemented so that the traffic distribution is efficient and experiments implemented downstream get enough users.

Can someone please point me in the right direction to an algorithm that allows me to do the above?

Each experiment is given X number of people needed per day to reach stats sig. We could factor that into the algorithm to make sure that we assign users to experiments in a way that experiments reach their sample size in two weeks.

A possible algorithm:

For each experiment, we make a decision of whether to assign based on the experiment's location using coin flip.
If we get heads, a list of experiments that are implemented for that location are selected.
An experiment is chosen from that list based on priority system.
At every location, a % of users are assigned to one of the experiments implemented at that location.
When we decide to assign or not to assign to any experiments at that location, that decision is not made again for the user.

The Question:
How do I assign users to one experiment at a time so that experiments that they might see last get enough users? Only users assigned to experiments can see them.

I suggest you try a simple solution: randomly decide whether to assign users to an experiment when they visit the corresponding page.

Suppose you want to have 100 users to a particular experiment, call it experiment E.  When a user visits the page for experiment E, if that user hasn't been previously assigned to any experiment, flip a biased coin and assign the user to experiment E if that coin comes up heads.  How do you decide what the probability of heads should be?  If historically you see 2000 visitors per two-week period, and you want 100 users, then the heads probability should be about 1/20.  Then after two weeks you should get about the desired number of users.

This assumes you have historical data on the number of visitors to each page, to set the probability appropriately.  If you don't have historical data, there are some alternative strategies you could use.  For instance, if you want 100 users for experiment E, you could randomly pick 100 different times throughout the two-week period; for each selected time, take the next unassigned user who visits that page (the first one who visits the page after that time) and assign them to experiment E.  In this way you are randomly selecting 100 different users.

These techniques treat each experiment independently, which simplifies the assignment process.  This is simple and I suspect it might work well enough for running experiments in practice.  Only consider something more complicated if you have evidence that this won't work.  (How can you tell whether it will work?  You could take your historical data and simulate the strategy on historical data and see if it gets you enough users for each experiment.)


What is wrong in this proof? I stumbled upon this wikipage that has got this proof :

I rechecked sum rule of differentiation.

And i can not understand where is this wrong.

Any Tips ?

I think that the second line

x^2 = x + x +... x times...

being used for differentiation is wrong. but i am not sure .

The proof states that $(\underbrace{x+x+\dots+x}_{x~ times})' = (\underbrace{1+1+\dots+1}_{x~ times})$. Let's give it a try.

$$\lim _{\epsilon \to 0} \frac{\underbrace{x+\epsilon+x+\epsilon+\dots+x+\epsilon}_{x+\epsilon~ times} - \underbrace{x+x+\dots+x}_{x~ times}} {\epsilon} =\\ \lim _{\epsilon \to 0}\frac{ \underbrace{\epsilon+\epsilon+\dots+\epsilon}_{x~ times} + \underbrace{x+\epsilon+x+\epsilon+\dots+x+\epsilon}_{\epsilon~ times}}{\epsilon} = \\ \lim _{\epsilon \to 0}\frac{ \underbrace{\epsilon+\epsilon+\dots+\epsilon}_{x~ times} + \underbrace{x+x++\dots+x}_{\epsilon~ times} + \underbrace{\epsilon+\epsilon+\dots+\epsilon}_{\epsilon~ times}}{\epsilon} =\\
\lim _{\epsilon \to 0}\underbrace{1+1+\dots+1}_{x~ times} + \underbrace{x}_{1 ~time} + \epsilon = 2x$$


How to define the natural numbers as a W-type? I'm having trouble understanding the rules for W-types in type theory as defined here: https://ncatlab.org/nlab/show/W-type#wtypes_in_type_theory

Can someone give an example of how these rules could be used to define a simple W-type such as the natural numbers? What would $A$ and $B$ be in the formation rule for instance?

The formation and introduction rules for W-types, as given on n-cat lab, are:

$$\frac{A:Type\quad x:A⊦B:Type}{(W x:A)B(x):Type}-\text{Formation}$$

$$\frac{a:A\quad t:B(a)\rightarrow W}{sup(a,t):W}-\text{Introduction}$$

You can define the natural numbers by setting $A=Bool$ and $B(a) = \text{if}\; a\; \text{then}\; ⟂\; \text{else}\; Unit$. Where $⟂$ is the empty type and $Unit$ is the unit type.

Zero is then $sup(a,t)$ where $a=true$ and $t: ⟂ \rightarrow Nat = λn. abort(n)$. eg. we use the zero constructor (by choosing $a=true$) and fill in the only possible value of a function from $⟂$ to $Nat$.

The successor of $p$ can be defined as $a=false$, $t:Unit \rightarrow Nat = λx.p$.


How does the hardware of a while loop work? I know get how logical operators for if logic gates work, but I am trying to understand how while loops fit into that picture. I realize that this question is a bit vague. It all started because I was wondering if one could write a while-loop with a series of if statements. Then I realized there had to be something deeper in our programming languages.

Vladislav is right, but there is more that can be said.

A loop means running some code, and then running it again.  An if just conditionally branches to two different bits of code.  If one of those bits of code can jump back to the earlier code, or to the if itself, then you can get a loop.  So you need something that can jump somewhere else.  A goto is one command that does that in some languages.  You have to have a way to naming or identifying where the jump is to, though, even if it's just by a line number.

Another way to implement a loop is with recursion.  To do that, you need to be able to name procedures or functions or targets, and then embed the call to the named code in one of the branches of the if.  (In tail-recursive languages such as Common Lisp and Scheme, this can be as efficient as a loop in some circumstances.)

In both cases, it's crucial that there be a way of referencing earlier code, and jumping into it.  If you don't have that, an if won't be enough.  (But see below.)

You could do without the named code if you knew that your while "loop" didn't need to perform more than $n$ iterations.  Then you just expand the loop explicitly:

run my code
if something is true then stop
else run my code
     if something is true then stop
     else run my code
     if something is ....

However, naming isn't actually required in order to loop without just writing the same code repeatedly.  You can do it with recursion, as noted above, but it's possible to define a recursive function using a Y combinator.  This is probably not very efficient, and if your language evaluates eagerly, as most do, it's kind of a mind-twister at first (it's simpler in with certain kinds of delayed evaluation), but it works, and it's cool.  (My favorite source for the complicated version that most languages need is The Little Schemer by Friedman and Felleisen; you can probably find the simple version in any book on lambda calculus.  That's the version described in the Wikepedia page, so maybe that's enough.)

In answer to the title of the question, in hardware there has to be some jump to a location--probably the same location--that causes the same code to be executed repeatedly--or some way of getting the same code to start running in the CPU, such as rewriting the stack.  Others will be able to say more about this.

(It would be appropriate if the Y combinator function was named after Paul Graham's Y combinator company, since the company is named after the function.  Graham's book on lisp On Lisp discusses recursion without naming, but very briefly, in an endnote on pages 387-388.)


Trying to understand a way to split an AVL tree in O(log n) I'm trying to understand a presentation about AVL trees.
It says that the way to split AVL trees in node x is as follows:
You search for the node x and mark every left son of every node when you turn right.
Later, you merge all the marked subtrees.

Now, i've drawn a complete BST with 15 nodes and tried the algorithm by splitting node 7:

Now, I mark nodes 2 and 5, try to merge them, and the left tree does not have node 6 in it. The description about how to split trees is not complete and I don't know what i'm supposed to do with it.

So, basically, what you are saying, is that you have a bunch of left leaning avls and want to merge them?
That's what I understand from the first graph.
You can merge and rebalance them in O(log(n)) time.

What I did was to make each tree a right child of the previous one, and then you start to rebalance at the root and moving to the right, with the rebalancing being a single or double rotation depending on the balance factors of the node and its children, and then you move to the right children and repeat.

@staticmethod
def ReBalanceRightist(parent, node):
    assert parent is not None
    while node is not None:
        AvlNode.UnlinkNodes(parent, node)
        node = AvlNode.ReBalance(node)
        AvlNode.LinkNodes(parent, node)
        parent = node
        node = node.right

First you unlink them, because you don't know if node will still be the root of that subtree, rebalance, and set the result of that rebalance as the new child.
Then rinse and repeat.

This works with O(log(n)) complexity as each left subtree is already balanced, and you just need one rebalance operation to balance a node (O(1)), then you repeat this along the branch, and the branch length is at most log(n), so you get O(log(n)) complexity.

I had to implement a remove_below(x) and remove_above(x) functions for an Avl, so that all the nodes with keys lesser than x or bigger than x would be removed from the tree, respectively, and the problem in the end is the same, which is, how to merge k right/left leaning trees.

You can look at the code here:

https://github.com/Izikiel/AvlPython


Asymptotics and logarithmic exponents I was tasked to order some functions in respect to the $\mathcal{O}$ notation, and have some problems with the following ones:

$n^{\ln(7)} = \mathcal{O}(n^{3})$: I can't find a more elegant proof for this other than using L'Hôpital's rule and a numerical approximation of $\ln(7)$:

$\lim_{n\to\infty} \frac{n^{\ln(7)}}{n^3} = \lim_{n\to\infty} \frac{n^{ \approx1.94591014906}}{n^3} = \lim_{n\to\infty} \frac{n^{\approx1.94591014906-3}}{3*2*1} = 0 $

(The last equal sign is valid, since the exponent is negative.)
Is there a better way to do this ?

Furthermore I have no idea how to prove $8^{\log_2 n} = \mathcal{O}(5^n)$. I tried to apply the limit rule but to no avail. I think it is intuitively clear, since $\log_2 n$ grows slower than $n$, but I don't know how to argue that rigorously.

Thanks for any answers.

First, notice that $3 > \ln 7$. You can prove this formally using the Taylor expansion of $e^x$:
$$
e^3 = \sum_{n=0}^\infty \frac{3^n}{n!} \geq 1 + 3 + \frac{9}{2} = 8.5 > 7.
$$
Monotonicity of $\ln$ implies that indeed $3 > \ln 7$.

Armed with this knowledge, we deduce that for $n \geq 1$,
$$
n^3 = n^{3 - \ln 7} n^{\ln 7} \geq n^{\ln 7}.
$$
This shows that $n^{\ln 7} = O(n^3)$, using the definition of big O.

For your other question, try using $8^{\log_2 n} = n^3$ and induction. The idea is that as you increase $n$ by 1, the value of $n^3$ hardly increases, whereas $5^n$ increases by a factor of 5.

Finally, let me say that there is absolutely no reason to be so formal. It's enough to go through the formalities once, just to get convinced that they work, and afterwards you can just use well-known facts such as $n^k = o(c^n)$ for all $c > 1$.


Discrete Mathematics Proofs for ∃ and ∀ Premises or Givens:

$∃x(A(x) → B(x))$
$∀x (B(x) → K(x))$

To Prove:

$∃x(A(x) → K(x))$

My Solution:

$A(z) → B(z)$  From premise and  Existential instantiation $x$ for $z$

$B(z) → K(z)$  From premise and  Universal instantiation $x$ for $z$

$A(z) → K(z)$  Transitivity of 1,2

$∃x(A(x) → K(x))$  From Existential generalization (Substitute $z$ for $x$)

OR
I was thinking about assuming $A(z)$ and then using Modus Ponens to get $B(z)$ and then further $K(z)$, then using the deduction theorem on $A(z)$ and $K(z)$, and then using Existential Generalization on that statement by substituting $x$ for $z$.

Can someone suggest which way would be more effective?
Is there any other effective way to solve it?

Your solution is a good one, and that's how I'd prove it also. I don't believe a more straightforward or simpler version is possible.


Computing square vs computing square-root? Time complexity I am working on something that requires checking a very large natural number $x$ to determine if it is the square root of an even larger natural number $y$. So I am wondering what are the fastest algorithms for computing square and square root, and how should I be approaching this i.e.

Computing $\sqrt{y}$ and comparing it with $x$
OR
Computing $x^2$ and comparing it with $y$

So as to write a code that has minimum time complexity.

There is a simple randomized test: pick a random 32-bit prime $p$, and test whether $x^2 \equiv y \pmod p$.  Do this a few times for a few random primes $p$.  (You can even pick a random number $p$ without requiring it be prime.)  If there is any error in your square root, then it is likely that it will be detected by this test.  The chances of failing to detect an error is exponentially small.


Reducing from Hamiltonian Cycle to Subgraph Isomorphism I am reading Subgraph isomorphism problem

I am having trouble understanding how they prove that the subgraph isomorphism problem is NP-Complete using the Hamiltonian cycles problem in the article.

Can someone help me explain what is happening in more laymen terms?

In $\mathrm{Subgraph\,\,Isomorphism}$, you're given two graphs $G$ and $H$, and the question is whether you can delete some vertices and edges from $G$ to get $H$ (i.e. $H$ is a subgraph of $G$). The reduction from $\mathrm{Hamiltonian\,\,Cycle}$ to $\mathrm{Subgraph\,\,Isomorphism}$ is really just rephrasing what it means for a graph to have a Hamiltonian cycle.

A Hamiltonian cycle in a graph is a cycle that includes every vertex, so if we ignore the other edges in the graph, we can think of the Hamiltonian cycle as a subgraph of the original graph with the properties that it contains all the vertices, only some of the edges, and those edges make a cycle. That is, a Hamiltonian cycle in an $n$-vertex is isomorphic to the graph $C_{n}$.

So if we start with $G$ and we can find a subgraph that's isomorphic to $C_{|V(G)|}$, $G$ must be Hamiltonian. This is the same as solving the $\mathrm{Subgraph\,\,Isomorphism}$ problem where $H=C_{|V(G)|}$.


Proof that whether a regular language is finite is decidable I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When you generate all strings from length 0 to n, if the machine accepts any of them then the language is non-empty. We don't have to check words with length > n because of the pumping lemma.
The question claims that you can solve the decision problem for finiteness in a similar way.

I know intuitively that a regular language is finite if its finite, well-formed regular expression does not contain a Kleene star, but I don't know how to convert this notion around. My thought is that we have to know if there are any words in the language whose length is greather than n, but that requires checking all words.

Then I thought:
Have the machine count the number of states n in the FSM. Generate all of the strings of length 0 to n. Then, check every word to see if the only possible way to pump this word xyz is to make y≡λ. If every word pumps only according to this condition, then the language is finite. However, this feels somehow incomplete.

Could someone give me a hint or push me in the right direction? Thanks.

If $L$ is infinite, it contains strings of unbounded length.  Think about the sequence of states visited by the automaton when these strings are accepted. This will give you a condition of the form "$M$ accepts an infinite language implies $X$".  Now check that it's actually "if and only if $X$."


What theorem are these? (from Scott Aaronson's blog) Browsing Scott Anderson's blog, I found this list of theorem. Among them are:

If every second or so your computer’s memory were wiped completely
clean, except for the input data; the clock; a static, unchanging
program; and a counter that could only be set to 1, 2, 3, 4, or 5, it
would still be possible (given enough time) to carry out an
arbitrarily long computation — just as if the memory weren’t being
wiped clean each second. This is almost certainly not true if the
counter could only be set to 1, 2, 3, or 4. The reason 5 is special
here is pretty much the same reason it’s special in Galois’ proof of
the unsolvability of the quintic equation.
It would be great to prove
that RSA is unbreakable by classical computers. But every known
technique for proving that would, if it worked, simultaneously give an
algorithm for breaking RSA! For example, if you proved that RSA with
an n-bit key took n5 steps to break, you would’ve discovered an
algorithm for breaking it in 2n^1/5 steps. If you proved that RSA took
2n^1/3 steps to break, you would’ve discovered an algorithm for
breaking it in n(log n)^2 steps. As you show the problem to be harder,
you simultaneously show it to be easier.

I learnt a bit of computer science in college, but I had never heard of these 2. I am very interested in knowing these. Any know what theorems are these? Thanks.
(since I can't comment...can you be more detailed about how "natural proof" do anything here?)

The first excerpt hints at Barrington's theorem. The second is probably about natural proofs.


Is $A_{PTM}$ a BPP-complete language? The language $A_{PTM}$ is defined as the acceptance problem on a Probabilistic Turing machine.

$A_{PTM}=$ { $<M, x> | M$ on input $x$ accepts with an error probability less than or equal to 1/3}

Basically, given a probabilistic Turing machine $P$ and string $x$, a decider $D$ simulates $P$ on $x$ and outputs accept if $P$ accepts on $x$, and rejects otherwise.

I claim $A_{PTM}$ is BPP-hard because BPP is the class of languages which are accepted a success probability of at least $2/3$. If the PTM for any BPP language is given as an argument to the decider $D$, then it will output accept if the PTM it was passed accepts, and reject otherwise. I know this is far from a formal proof, but I am just trying to understand the idea. Is this correct?

First, $A_{PTM}$ as you defined it is not even decidable (so it isn't in BPP), since your simulation might not halt.

The naive attempt at a BPP complete language is:

$A_{PTM}=\left\{\left(\langle M\rangle,x, 1^t\right) \big| M \text{ accepts $x$ in $\le t$ steps with probability $\ge \frac{2}{3}$} \right\}$.

Note that there is no notion of "error" in the definition of $A_{PTM}$, as there are no right answers, you decide whether or not to include some triplet in your language.

You can show that $A_{PTM}$ is indeed BPP-hard (I leave the reduction details for you). The problem is that we do not know if $A_{PTM}\in \mathsf{BPP}$. Simply simulating $M$ on $x$ for $t$ steps and outputing its answer won't work. Imagine $M$ accepts $x$ after $t$ steps with probability $\frac{1}{2}$, then although $(M,x,t)\notin A_{PTM}$, you accept it with probability $\frac{1}{2}$, while you should be accepting with probability $\le \frac{1}{3}$.

In fact, $A_{PTM}$ is $\mathsf{PP}$ complete, so it is unlikely to lie in $\mathsf{BPP}$. The existence of complete problems for BPP is currently an open question in complexity. You can check this question from cs-theory, which talks about why it is harder to find complete problems for classes like BPP.


Is connected forest a spanning tree? forest : set of disjoint trees.

So a connected forest is a forest, a tree, a spanning forest and a spanning tree.

Is that correct?

Edit: disjoint trees in the forest are connected by single edge, so as to make the forest connected

A connected forest is a tree (as well as a forest).

The terms spanning forest and spanning tree refer to an ambient graph. Given a connected graph $G$, a spanning tree is a subset of the edges of $G$ (spanning all vertices) which forms a tree. Similarly, if $G$ is a graph with $c$ connected components, then a spanning forest is a subset of the edges of $G$ (spanning all vertices) which is a disjoint union of $c$ trees.


Circuits and formulas for Clique Is it correct to say that the Clique Problem is in $P$ iff there exists a family of Boolean circuits $C$ to decide Clique whose sizes are bounded by a polynomial? And based on this question, does that imply that there exists an equivalent set of Boolean formulas $F$ to decide Clique whose sizes are bounded by a polynomial? And if there is such an $F$, would there be correct derivations based on propositional logic axioms from any member of $F$ to the corresponding large naive formula for Clique?

I'm afraid that the answer to all your questions is false:

There are languages decided by constant size circuits which aren't decidable.
It is conjectured that $\mathsf{NC^1} \neq \mathsf{P}$.
It is conjectured that $\mathsf{NP} \neq \mathsf{coNP}$.


Extension of SQL capturing $\mathsf{P}$ According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator): SQL captures safe queries. (In other words, all SQL queries have a complexity in $\mathsf{Q(FO(COUNT))}$, and all problems in $\mathsf{Q(FO(COUNT))}$ can be expressed as an SQL query.)

Based on this result, from theoretical point of view, there are many interesting problems that can be solved efficiently but are not expressible in SQL. Therefore an extension of SQL which is still efficient seems interesting. So here is my question:

  Is there an extension of SQL (implemented and used in the industry) which captures $\mathsf{P}$ (i.e. can express all polynomial-time computable queries and no others)?

I want a database query language which stisfies all three conditions. It is easy to define an extension which would extend SQL and will capture $\mathsf{P}$. But my questions is if such a language makes sense from the practical perspective, so I want a language that is being used in practice. If this is not the case and there is no such language, then I would like to know if there is a reason that makes such a language uninteresting from the practical viewpoint? For example, are the queries that rise in practice usually simple enough that there is no need for such a language?

As for your main question, I recommend this short survey by Martin Grohe.

  Are the queries that are needed in practice usually simple enough that there is no need for a stronger language?

I'd say this holds most of the time, given the fair amount of extensions added to common query languages (transitive closure, arithmetic operators, counting, etc.). This comes from the point of view of somebody who has done some work as a freelance developer of relatively simple web sites and other applications, so I'm not sure about the real uses of SQL in bigger industries/larger databases.

In the rare cases a more powerful language might be needed, my guess is that software developers deal with them by using the language in which they write the application, not the queries (like C++ or java).


Find the cheapest combination of raw foods that fulfill nutritional requirements I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples allowed) with the lowest total price.

Does anyone have any advice as to how to approach this problem? Is there a certain algorithm that exists that takes in a list of possible items, and finds a permutation that minimizes one property of the item(s), in this case the price, and also makes sure that the sum of each property meets a certain range, in this case nutritional properties like carbs and protein? Any advice is greatly appreciated. Thanks!

Use integer linear programming.  Suppose you have $n$ foods.  Let $x_1,\dots,x_n$ be zero-or-one variables, with the intention that $x_i=1$ means you include food $i$ in the combination.  Then the price is a linear function of these $x$'s, so that's your objective function you are minimizing.  If you want the total carbs to be within a range, you can express that as a linear inequality (e.g., $\ell \le c_1 x_1 + \dots + c_n x_n \le u$, where $\ell,u$ are the lower and upper bounds of the range and $c_i$ is the amount of carbs in food $i$).  Feed this to an off-the-shelf ILP solver, and it should give you the optimal answer.


Need help removing ambiguity from grammar $E \rightarrow UV \bracevert EBE \bracevert V \bracevert [E]$

$V \rightarrow a \bracevert b$

$U \rightarrow < \bracevert > $

$B \rightarrow ? \bracevert ! \bracevert @ $

Order of precedence: $?$ < $!$ < $@$, with unary operators ($<, >$) being the highest

$?$, $!$, $@$ are right associative.

My attempt:

$E \rightarrow UV \bracevert EBT \bracevert V \bracevert [E] $

$T \rightarrow E$

$V \rightarrow a \bracevert b$

$U \rightarrow < \bracevert > $

$ B \rightarrow ? \bracevert B_1 $

$ B_1 \rightarrow ! \bracevert B_2 $

$ B_2 \rightarrow @ $

I'm not sure if I left out some corner cases during my conversion. Appreciate if you guys can point some mistakes out and offer some hints.

In your attempt put $T\rightarrow UV \ \bracevert\  V\  \bracevert\  [E]$ instead of $T\rightarrow E$.

The idea is not to just replace symbols arbitrarily, but replace in such a way that it's derivations are a subset of possible derivations (which should be unambiguous).

And you can also use the procedure prescribed in textbooks or in Jonathan's answer in https://stackoverflow.com/questions/3106195/converting-ambiguous-grammar-to-unambiguous to remove ambiguity (unless the language in inherently ambiguous). I like Jonathan Leffler's answers because he gives lot of detail as well as intuition behind answers.


Finding regular expression for a language with more substring of one type than from another Take the alphabet A={0,1} I need to build a regular expression for the language with less or equal substrings 011 than 110.

I tried to figure out what would be the finite automata but I'm not to sure.
I also tried to proof it isn't regular using Myhill-Nerode theorem but the problem is the language "readjusts" itself:

110011  (1 110, 1 011)

011110  (1 110, 1 011)

011011  (2 011, 1 110)

110110  (1 011, 2 110)

Now I'm convinced it should be regular but don't know how to proof it.

Edit:

¿Should be something similar to: $(0^{+}11^{+}+11^{+}0^{+})^{*}110(0^{+}11^{+}+11^{+}0^{+})^{*} + \epsilon$?

Hint: Suppose that as you read a word, you keep a counter which increases by 1 whenever you encounter 011, and decreases by 1 whenever you encounter 110. Show that the counter only gets the values 0,1,-1. In other words, between two occurrences of 011 there is an occurrence of 110, and vice versa. Use this to design your regular expression (you could also start with a DFA).


Solving recursion $T(n)=2T(n/2) +2/\log(n)$ everybody, I'm trying a whole day to compute this recursion. I will be
grateful if someone can try and solve it

$$T(n)=2*T(n/2)+2/\log(n),$$

where $\log n$ is the logarithm to the base 2 - of course! thanks!


Understanding How Double Precision Numbers are Stored in a Computer I am reading Numerical Analysis by Walter Gautschi. I am somewhat confused by the following quote from page $5$:

  To increase the precision, one can use two machine registers to represent a machine number. In effect, one then embeds $\mathbb{R}(t, s) \subset \mathbb{R}(2t, s)$, and calls $x \in \mathbb{R}(2t, s)$ a double-precision number.

(Here $t$ represents the number of allowable binary digits in the mantissa, and $s$ represents the number of binary digits allowable in the exponent.)

Can someone please explain what is going on here with the "machine register"? Some questions that I have are: instead of using two registers, why not just use one of bigger size? Apparently some registers have a different size, because the exponent is also stored in a register, and $r$ may not equal $s$.

Secondly, double-prevision seems to be defined in terms of a "native precision" already intrinsic to the machine. But on the other hand, I thought double precision was a fixed thing determined by IEEE.

My Background I am a math major taking my first Numerical Analysis course. I do not have any prior experience with computers (except day-to-day use of course) or numerical mathematics.

I don't know how old your book is, but some architectures (I know of the early SPARCs, there may be others) only had 32 bit floating point registers. Double precision instructions used pairs of registers for storage. This became much less common on general-purpose hardware when 64-bit integer registers became the norm.

If anything, we have the converse today, thanks to vector/SIMD operations. If you have, say, a 128 bit vector register, you can fit four single-precision or two double-precision numbers in it.


Complexity of keeping track of $K$ smallest integers in a stream I need to analyze the time complexity of an online algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers. The algorithm is

Suppose the $i$th number in the stream is $S_i$.
Keep a max heap of size $K$.
If the heap contains fewer than $K$ elements, add $S_i$ to the heap.
Otherwise: if $S_i$ is smaller than the maximum element in the heap (i.e., the root of the heap), replace the root of the heap with $S_i$ and apply Max-Heapify to the heap; if $S_i$ is greater than or equal to the max element, do nothing.

The problem now is to find the expected number of times the Max Heapify operation will be called, when the stream of integers is of length $R$ and each element of the stream is (iid) uniformly distributed on $[1,N]$.

If the stream were guaranteed to contain only distinct elements, then the answer is easy:

$$E[X] = E[X_1] + E[X_2] + \dots + E[X_R],$$

where $X_i$ is the random indicator variable for occurrence of the Max Heapify operation at the $i$th number in the stream.  Now

$$E[X_i] = \Pr[\text{$S_i$ is ranked $\le K$ among first $i$ elements}] = \min(K/i, 1).$$

Hence,

$$E[X] = K + K/(K+1) + \cdots + K/R.$$

That case is relatively easy.  But how do we handle the case where the elements are iid uniformly distributed?

[This was actually a Google interview question.]

If the value of the $i$-th element is $x$, it causes a heapify, if and only if $j < K$ of the previous $i-1$ elements are smaller than $x$. This gives

$$E[X_i] = \frac{1}{N^i} \sum_{x=1}^N \sum_{j=0}^{K-1} c_{j,x},$$

where $c_{j,x}$ is the number of sequences of $i-1$ elements, of which exactly $j$ are smaller than $x$.

Now, to determine $c_{j,x}$, note that there are $\binom{i-1}{j}$ possibilities for the positions of the smaller elements in the sequence. For each of the smaller elements there are $x-1$ possibilities for its value, while for the larger or equal elements there are $N-x+1$ possibilities. This yields
$c_{j,x} = \binom{i-1}{j} (x-1)^j (N-x+1)^{i-1-j}$, and thus overall (after shifting $i$ and $x$ by $1$)

$$E[X] = \sum_{i=0}^{R-1}\frac{1}{N^{i+1}} \sum_{x=0}^{N-1} \sum_{j=0}^{K-1} \binom{i}{j} x^j (N-x)^{i-j}.$$

Unfortunately, all my attempts at bringing this formula into a simpler/closed form have been unsuccessful.


What should we return when pattern matching on a Path constructor? Context: Cubical Type Theory

Consider a simple HIT, say, an HitInt:

data HitInt : Set where
  pos : (n : ℕ) → HitInt
  neg : (n : ℕ) → HitInt
  posneg : pos 0 ≡ neg 0

Or, if you don't speak Agda we can use cubicaltt:

data int = pos (n : nat)
         | neg (n : nat)
         | zeroP <i> [ (i = 0) -> pos zero
                     , (i = 1) -> neg zero ]

We want to define, for instance, a succ operation for it. As a functional programmer, we want to pattern matching on this HIT. In Agda, it's:

sucHitInt : HitInt → HitInt
sucHitInt (pos n) = pos (suc n)
sucHitInt (neg zero) = pos 1
sucHitInt (neg (suc n)) = neg n
sucHitInt (posneg x) = pos 1

Or in cubicaltt:

sucInt : int -> int = split
  pos n -> pos (suc n)
  neg n -> sucNat n
    where sucNat : nat -> int = split
            zero -> pos one
            suc n -> neg n
  zeroP @ i -> pos one

What I'm interested in is the last case-split of these two pattern matchings. The function is supposed to return the successor of the input integer, but we need to implement something that "finds the successor of the input Path".

My question is, how are we supposed to implement this case-split? In the cubicaltt version (taken from the cubicaltt's GitHub repository, examples/integer.ctt), it matches the Path pos 0 == neg 0 and returns pos 1 -- say, matches a Path, but returns a normal integer. Is this really what we want to do? Why it's not returning a Path like <i> pos 1 (even this is not a member of the higher inductive family)?

What's interesting is that, in Agda it'll fill pos 1 in the case body when I use Agda's proof-search.

it matches the Path pos 0 == neg 0 and returns pos 1 -- say, matches a Path, but returns a normal integer

My understanding is that it matches points of path rather than path itself. This is why the matching is on posneg x (where x : I) rather than posneg itself.

Since paths can be seen as (special) maps from I, we can think of HIT constructors as just a special of regular constructors, i.e.

  posneg : I ↝ HitInt [i0 ↦ pos 0 ; i1 ↦ neg 0]

where if you ignore "special" properties of Interval, it looks like a regular constructor (in cubicaltt notation it already looks similar except that I is always treated specially).

  What's interesting is that, in Agda it'll fill pos 1 in the case body when I use Agda's proof-search.

It's the only way to satisfy constraints imposed by previous definitions (this works for both zero cases). In fact, Agda can correctly solve even two holes (in right order):

sucHitInt : HitInt → HitInt
sucHitInt (pos n) = pos (suc n)
sucHitInt (posneg i) = {!!}
sucHitInt (neg zero) = {!!}
sucHitInt (neg (suc n)) = neg n

  Why it's not returning a Path like  pos 1 (even this is not a member of the higher inductive family)?

Again, since we're matching on points rather than paths; for symmetry it's possible to imagine that case as equal to:

sucHitInt (posneg i) = (λ _ → pos 1) i

reading somewhat like "for all projections from I at i to path posneg we have projections from I at I to constant path (λ _ → pos 1)". This doesn't quite work in Agda (because typecheking lambda application directly isn't very well supported), however the following (with the same meaning) does:

sucHitInt (posneg i) = refl {x = pos 1} i

Finally, abusing notation, we could rewrite that as

(ap sucHitInt posneg) i = (refl {x = pos 1}) i

(where ap (from the HoTT book) corresponds to cong in typical Agda) and, getting rid of i from the both sides, recover path to path mapping.

PS: i'm new to cubical myself, so hopefully someone can correct or extend my answer


When reducing from HALT, can you create a Turing machine that asks whether a simulation stops? Lets say I am doing a reduction from $\mathrm{HALT}_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I create $M'$ in such a way that the next step is depended upon whether or not a simulation stops? Take the following two examples:

$M' = $ "on input $M, w$:

Simulate $M$ on input $w$. If $M$ stops, go to step 2. Else: go to step 3.
....
....."

And

$M'' = $ "on input $M, w$:

...
Run $M$ on input $w$.
accept."

The first one requires the decider for $S$ to solve $\mathrm{HALT}_{\mathrm{TM}}$ more explicitly then the second one. Is the first one wrong?

No, you can't.

First, as a technical point, it never makes sense to say "If this simulation halts", since that would require doing the whole simulation and, if it doesn't halt, you'd never finish simulating it. You can, in certain circumstances, ask whether a particular Turing machine halts on a particular input, but that's something subtly different.

But the main point is that your reduction looks backwards. You're supposed to be using the argument "$S$ must be undecidable because I could use the ability to decide $S$ to let me decide the halting problem, which is impossible." But, by basing decisions on whether some Turing machine halts or not, you're assuming that you can determine this, i.e., assuming that you can already decide the halting problem.


Bipartite Problem is Log-Space Reducible To $s$-$t$ Undirected Connectivity Prove that the problem of determining if graph is bipartite is computationally equivalent under log-space reductions to $s$-$t$ undirected connectivity.

Problem of $s$-$t$ undirected connectivity is the following given an undirected graph $G = (V, E)$ and two designated vertices, $s$ and $t$, determine whether there is a path from $s$ to $t$ in $G$.

I assume the idea is to consider mapping from graph $G$ to bipartite graph $G'$, there should be a correspondence between edges of $G$ and edges of bipartite graph $G'$, and between edges of $G$ and the edges that violates the bipartite property of graph $G'$. The problem is I cannot come up with such correspondence.

I would appreciate any idea.

Here are some ideas on how to reduce checking bipartiteness to undirected non-connectivity:

A graph is bipartite iff it has no odd cycles.
Suppose we guess that vertex $v$ participates in a cycle of length $2k+1$. Using a layered graph, we can check whether it is the case using undirected connectivity.
We can also implement a disjunction ("or") using undirected connectivity.

Here are some ideas for the other direction:

Every graph can be made bipartite by splitting every edge into a path of length $2$.
What happens when we join $s$ and $t$, after splitting the edges?


What is the relation between the formal definition of strictness and its intuitive notion I am currently reading Functional Programming in Scala and have encountered a statement in the book I cannot quite make sense of.

On page 67, we are told the formal definition of strictness:

"If the evaluation of an expression runs forever or throws an error instead of returning a definite value, we say that the expression doesn't terminate, or that it evaluates to bottom. A function f is strict if the expression f(x) evaluates to bottom for all x that evaluate to bottom."

This definition is somewhat puzzling because the discussion of strictness that comes before this definition has discussed strictness in relation to lazy evaluation. To say that an expression is strict is to say that it is completely evaluated, and not lazy. What is not clear is how this notion of strictness and laziness is at all related to the formal definition given.

The intuition: if executing f(x) causes x to be evaluated, and evaluating x doesn't terminate, then this will cause f(x) to fail to terminate (because evaluating x doesn't terminate, so the execution of f(x) never completes).

So, if executing f(x) always causes x to be executed, then f will be strict by the formal definition above.  That's why "f(x) completely evaluates x" implies "f(x) evaluates to bottom for all x that evaluate to bottom".

In contrast, with a lazy function, evaluating f(x) doesn't necessarily trigger evaluation of x, so it doesn't necessarily terminate (even if evaluating x wouldn't terminate).  Thus, for a function that is intuitively lazy, it won't meet the formal definition of strict.


why recursive languages does not come under Chomsky hierarchy? why recursive languages does not come under Chomsky hierarchy ? why Chomsky did not classified
 it? any real life resemblance of recursive language something that i can connect it with like regular language are ones which needs finite memory or context free languages are those which can be parsed using single stack .something like that .

The hierarchy is defined in terms of grammars. It is still an open question whether there is a natural grammar formalism for recursive languages (check out this question), and certainly no such formalism had been known at the time Chomsky wrote his paper.


Show that k-clique lies in L The following exercise is difficult for me:

  Show that for each $k \in \mathbb{N}$ the question of existence of a $k$-clique within a graph lies in $\text{L}$.

  Hint: A $k$-clique denotes $k$ verteces within a graph that are all connected with each other.

  Annotation: if the question also considers $k$ as parameter, then the problem is $\text{NP}$-complete.

So $\text{L}$ is "the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space". Now I'm wondering if this exercise isn't a catchy question, since I've found this paper and it says "We give an algorithm for $k$-clique that runs in (...) $O(n^{\varepsilon})$ space, for all $\varepsilon > 0$, on graphs with $n$ nodes"?

Furthermore, I also don't understand the annotation, because how should it be possible to not consider $k$ for the $k$-clique problem?

If you consider $k$ a constant, then k-clique can be solved be enumerating all $O(n^k)$ sets of vertices and checking that there are edges present in polynomial time (since the exponent is constant).

Enumerating k-Tuples of numbers up to n can be done in $k\log n$ space, you only have to figure out how to check for the presence of an edge between two vertices without using much space. Depending on how much details you have to give this is either obvious or very tedious to write down.


Must a word be binary (and never unary)? I understand that a computer memory sequential word must always include at least two bits so it must be binary and therefore cannot be unary.
Must a word be binary (and never unary)?
That is to ask; can there be a "unary" computer memory sequential word?

This question might relate to my other question - Must a Turing machine tape be binary?

Machine words have fixed length. Denoting the length by $n$ and the base by $b$, each machine word has $b^n$ possible values, and so stores $\log_2 (b^n)$ bits of information.
A base can be binary or decimal and so forth; if $b=1$ then the machine word has a single possible value, and so stores no information. It would be useless.
Unary encoding is only relevant in contexts where the length is not fixed.


Determining whether a CFG is $LL(k)$ for any $k$? In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable.

Is there a similar result showing that it is undecidable whether a given CFG is an $LL(k)$ grammar for some choice of $k$?  Or is this problem known to be decidable?

This is undecidable. It is theorem 11 in Properties of deterministic top down grammars by Rosenkrantz and Stearns. Theorem 12 in the same paper however states that the problem becomes decidable if the grammar is known to be $LR(k')$ for some (possibly different) $k'$.


Is 'double max-$k$ vertex-cover' NP-hard? Consider the following problem, which I have called '$\mathsf{\text{double max $k$-vertex-cover}}$':

  Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices $V'\subseteq V$ of size at most $k$ such that the set $\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$ has a size of at least $t$?

Is this problem NP-hard?

I suspect it is, since the similar problem of max $k$-vertex cover is NP-hard. The same trick for that problem, setting $t=|E|$, does not apply here, as that gives the trivial answer of $|V|-\#\text{zero-degree vertices}$ (in other words, double max vertex-cover is a trivial problem).

Unfortunately, I have been unable to find a reduction. This question seems related, but does not solve this problem for the same reason a reduction from minimum vertex cover fails. (A generalisation of this problem to set covering would look similar to that question)

Background: I encountered this problem in an attempt to show NP-hardness of another problem in this answer, but I think this problem is interesting on its own.

It was easier for me to show that the $k$-clique problem is a special case of this problem.

On an input graph $G$ and an integer $k$, the this special case is defined by  $G$,$k$,$t$, with $t=\binom{k}{2}=k(k-1)/2$.
Observe that some $V'\subseteq V$ of size $k$ is a clique in $G$ if and only if the set $V'$ covers at least $\binom{k}{2}$ edges twice.

Since the NP-hard problem $k$-clique is a special case of 'double max-$k$ vertex-cover', the problem 'double max-$k$ vertex-cover' is NP-hard.


Algorithm for finding cycles in a hypergraph Define a hypergraph as a set $V$ of vertices and a set $E$ of hyperedges, where a hyperedge is a non-empty subset of $V$. (This is a generalisation of an undirected graph, in which edges are allowed to connect any number of nodes, rather than just two.)

Define a cycle in a hypergraph as a cyclic sequence $C$ of vertices $v_0,v_1,\dots,v_n,v_0$, such that

(i) there is no hyperedge that includes all of the members of $C$; and

(ii) for every adjacent pair of vertices in $C$, there is a hyperedge that includes them both.

I'm looking for a simple and straightforward algorithm to detect whether any given hypergraph has a cycle. I feel like it should be obvious but it's not coming to me.

In case it helps: the hypergraphs I'm dealing with are reduced (meaning that no hyperedge is a subset of any other hyperedge), and also have the property that there is at least one hyperedge that contains each vertex.

Yes, there is a simple and efficient algorithm for this.

Given a hypergraph $H=(V,E)$, construct an undirected graph $G$ as follows: add the edge $(u,v)$ to $G$ if there is a hyperedge that contains both $u$ and $v$.  Find the connected components of $G$.

Your condition (ii) is now equivalent to: $v_0,v_1,\dots,v_n$ are all in the same connected component.  Thus, you want to find a subset of vertices that are all in the same connected component, but aren't contained in any hyperedge.

This leads to a simple algorithm.  Iterate over the connected components of $G$.  Let $S$ denote the set of vertices in one connected component of $G$.  Test whether $S$ is contained in any hyperedge of $H$.  If it isn't, then the hypergraph has a cycle (any cycle in $G$ that visits each vertex of $S$ at least once, and doesn't visit any vertex outside $S$, is a cycle in $H$).  If after testing all the connected components of $G$, none of them are a valid cycle, then the hypergraph doesn't have any cycles.

(You don't need to test any of the subsets of $S$.  If $S$ isn't a cycle, then none of the subsets will form a cycle, either.  Why?  If $S$ violates condition (i), then every subset of $S$ will violate condition (i), too.)


How do I model this expression maximization problem as a Knapsack problem? Given two arrays of the same length $n$:

$A = \{a_1,a_2,\dots,a_n\}$,

$B = \{b_1,b_2,\dots,b_n\}$,

I have to maximize the following expression:

$$\frac{a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k}}{b_{i_1} + b_{i_2} + b_{i_3}+ \dots + b_{i_k}}$$

Where $k \lt n$.

Given the constraints:

Firstly, when you select a particular $a_i$ you have select it's corresponding $b_i$, and vice versa.

Secondly, you have to select exactly $k$ elements from the arrays. Where $k \lt n$.

Assumptions:

The assumption is that $A$ and $B$ both contain natural numbers only.

What I have tried:

I have tried sorting the arrays using the ratio $\frac{a_n}{b_n}$ in the non-decreasing order, but this gives an incorrect result since it's trying to optimize $\frac{a_1}{b_1} + \frac{a_2}{b_2} + \dots \frac{a_k}{b_k}$. That is different from my desired objective function.

I have also thought of treating the denominator as a knapsack but this does not make sense because there are no weights involved.

Any suggestion on what I can do to model this problem as a knapsack optimization problem?

One approach (not based on the knapsack problem): suppose you are given a threshold $\tau$ and want to check whether you can find a subset such that

$$\frac{a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k}}{b_{i_1} + b_{i_2} + b_{i_3}+ \dots + b_{i_k}} \ge \tau.$$

Could you solve that problem?  If you could, you could use binary search on $\tau$.

Note that the above condition is equivalent to

$$a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k} \ge \tau \cdot (b_{i_1} + b_{i_2} + b_{i_3}+ \dots + b_{i_k}),$$

or equivalently,

$$a_{i_1} - \tau b_{i_1} + a_{i_2} - \tau b_{i_2} + a_{i_3} - \tau b_{i_3} + \dots + a_{i_k} - \tau b_{i_k} \ge 0.$$

And that enables us to find a simple way to check for the existence of that subset.

See if that gives you any ideas.


Finding an optimal topological ordering I have some jobs, which calculate values. Some of these jobs require the calculated values of other jobs for their own calculation. An execution plan for these jobs can be found with a topological sort on the dependency graph.

However, these calculated values are huge and occupy a large chunk of memory. I want to find a topological order that minimizes memory usage.

To give a simple example, consider the following dependency graph:

There are three possible topological orders: $1\, 2\, 3\, 4$, $1\, 3\, 2\, 4$, and $3\, 1\, 2\, 4$. Let's look at each of them.

In the first case, the values of $1$ and $3$ can be discarded immediately after $2$ and $4$ have finished, respectively, so each of them must be kept in memory for one additional step. The value of $2$ has to be kept for two additional steps until $4$ has finished. So in total we have to keep $4$ results in memory over the whole execution.

In the second case the values of $1$ and $3$ have to be kept for two steps and the value of $2$ for one step. This makes $5$ in total, so this ordering is worse in terms of memory usage.

In the third case the value of $3$ has to be kept for three steps and the values of $1$ and $2$ for one step each. Again we have a total of $5$, so this ordering is also worse than the first one. Thus the first ordering should be chosen.

Is there an efficient algorithm to find an optimal ordering without needing to inspect all possible orderings?

Bonus: is it also possible to give an optimal solution, if the values would need different amounts of memory per job?

This problem is called the Minimum Linear Arrangement of a Directed Graph and it is indeed NP-hard.

See the reduction from the MLA to MLAD on page 11 of this (old) technical report: S. Even and Y. Shiloah, NP-completeness of several arrangement problems, Technical Report no. 43 of the Department of Computer Science, Israel Institute of Technology (Technion), 1975 (PDF).


Prove that every two vertices in graph are connected by a path of some length I'm working on simulating a network architecture. I'm representing every node and their connections as a connected graph with no directional edges. I need some help with my reasoning.

Every node in network is connected to exactly 3 others. Is it possible for me to prove that every two nodes have a path of length O(n/3) between them? I can show people that the way I setup the network guarantees some existence of relatively fast routes. The n is much more than 3

Thank you

$O(n/3)$ doesn't mean what you think it means: in particular, $O(n/3)$ denotes exactly the same class of functions as $O(n)$. However, it's not true that the longest distance between two vertices in a $3$-regular graph is roughly $n/3$. Consider the graph

o---o       o       o             o       o---o
|\ / \     /|\     /|\           /|\     / \ /|
| X   o---o | o---o | o-- ... --o | o---o   X |
|/ \ /     \|/     \|/           \|/     \ / \|
o---o       o       o             o       o---o

(where the Xs denote two crossing edges).  The distance from the top-left vertex to the top-right vertex is approximately $3n/4$.


Calculating DFT of a specific polynomial This seems like a simple problem but I'm getting the impression I'm missing something.

The problem

Given the values $v_1, v_2, \ldots, v_n$ such that $DFT_n(P(x)) = (v_1, v_2, \ldots, v_n) $ for $ P(x) = \sum\limits_{i=0}^k a_ix^i$ , $k < n$ - find $ DFT_{2n}(P(x^2)) $

My attempt:

First expand $P(x^2) $ :
$$P(x^2) = a_0 + a_1x^2 + \ldots + a_k^{2k}$$
Let's denote by $W^j_n$ the j'th root of unity of order n.
We have : $$ W^j_{2n} = e^\frac{2\pi ij}{2n} = e^\frac{\pi i j}{n}$$
Using this information, let's evaluate a term p of $P(x^2)$ on some $W^j_{2n}$ :
$$a_p(x^2)  = a_p(e^\frac{\pi ij}{n})^{2p} = a_p(e^{2\pi i}) ^\frac{jp}{n} = a_p$$ (since $e^{2\pi i} = 1$)
So, when evaluating any term of the compound polynomial on some unity root of order 2n we get $\sum\limits_{i=0} ^k ak$ and therefore the final answer is:
$$(\sum\limits_{i=0} ^k ak, \sum\limits_{i=0} ^k ak,\ldots, \sum\limits_{i=0} ^k ak)$$

This seems wrong, I don't even use the information about $(v_1, \ldots, v_n)$(should the answer be in terms of those?)

Any help would be appreciated.

You haven't explained what you mean by the DFT of a polynomial, so I'm assuming you mean the polynomial evaluated at all $n$th roots of unity, that is,
$$ v_i = P(\omega^i), $$
where $\omega = e^{2\pi i/n}$ is a primitive $n$th root of unity. Let now $Q(x) = P(x^2)$, and let $\varpi = e^{\pi i/n}$ be a primitive $2n$th root of unity, $\varpi^2 = \omega$. Let us examine its DFT $w_1,\ldots,w_{2n}$:
$$
w_k = Q(\varpi^k) = P(\varpi^{2k}) = P(\omega^k) = v_{k \mod{n}}.
$$
We conclude that the DFT of $Q$ is
$$ v_1,\ldots,v_n,v_1,\ldots,v_n. $$


Why Deterministic PDA accepts $\epsilon$ input but DFA not I was going through a deterministic PDA that accepts $wcw^R$ (described in Ullman's textbook), in which the last transition is given as $(q_1,\epsilon, Z_0)\to(q_2,Z_0)$, where $q_2$ is the final state.

In DFAs we don't consider $\epsilon$ transitions, while in PDAs we do include them. Why?

There are definitely definitions of DFA that allow $\varepsilon$-transitions. Arguably, they are not very useful for three reasons.

They don't add computational power.
If you have them, you have to require (for DFA) that every $\varepsilon$-transition is the only transition leaving its source state.
Everything you might want to do with them (say, prove closure of regular languages against concatenation) can be done by using NFA and determinising.

Because they do have use in proofs, they are usually included in the definition of NFA, though. For example, consider translating regular expressions into NFA.

In PDAs, $\varepsilon$-transitions can be used to deal with stack content without consuming any input. Even in DPDA there can be multiple choices in any given state, depending on stack content. So they are useful here for constructing PDA and are thus usually included in the definition.


Semidecidability/Decidability for strings seperated by a non alphabet symbol I am trying to prove the following:

Let $\Sigma $ be an alphabet not containing the symbol "$;$", and suppose that
$L \subseteq \Sigma^*$; $\Sigma^*$ is recursively enumerable. If this is the case language $L' = \{x \in \Sigma^*: x; y \in L \ for \  some \ y \in \Sigma^*\}$ is recursively enumerable.

which left me a little bit confused. Since $";"$ is not in the alphabet $\Sigma$ should I seperate $x$ and $y$ and show that check for $x \in \Sigma^*$ and $y \in \Sigma^*$ is recursively enumerable?

Also, will this statement be the case if we checked for being recursive instead, that is if $L$ was recursive, is $L'$ necessarily recursive as well? And is the proof of this the same with the recursively enumerable case?

Any help will be appreciated.

First, a few things that may or may not help:

Def: A language $L\subseteq \Sigma ^*$ is Recursive (R) if there is some algorithm that, when given $u\in \Sigma^*$, will return $1$ iff $u\in L$ and $0$ iff $u\not\in L$.
Def: A language $L\subseteq \Sigma ^*$ is Recursively enumerable (RE) if there is some algorithm that, when given $u\in \Sigma^*$, will return $1$ iff $u\in L$. (If $u\not\in L$, ir may return $0$ or loop forever)
Prop: A language $L$ is RE iff there is some algorithm that enumerates $L$. One way to formalize "$\mathcal A$ enumerates $L$" would be to say that the algorithm $\mathcal A$ takes an integer $n\in \mathbb N$ and returns some $\mathcal A(n)\in L$ for each $n$, and that for any $u\in L$ there is at least one $n$ so that $\mathcal A(n)=u$ (i.e. if you look at the algorithm as a function $\mathcal A:\mathbb N \to L$, it is surjective).
Remark: Even though the notins of R and RE seem to depend on the alphabet, they do not. If you have an algorithm $\mathcal A$ that takes a word $u\in \Sigma$ as input, you create the one that takes $u\in \Sigma'^*$ by returning $0$ if $u\not\in \Sigma$ (which is decidable) and then running $\mathcal A$. And in the other direction, you can just reuse the same algorithm.

Now, take some alphabet $\Sigma$ so that $;\not\in\Sigma$ and let $\Sigma':=\Sigma\sqcup \{;\}$.

To show that your $L'$ is indeed RE, just take the algorithm $\mathcal A$ that proves that $L$ is RE. When given $x\in \Sigma^*$, you want to know if there is some $y\in \Sigma^*$ so that $x;y\in L$. The problem with simply trying for each $y\in \Sigma^*$ is that your first call to $\mathcal A$ may never terminate and you'll have looped on a possibly positive instance. What you want to do instead is this: for $n$ from $0$ to $+\infty $, for each word $y\in \Sigma^*$ of size $|y|\le n$, run $\mathcal A$ on $y$ for $n$ steps (or seconds) and if it returns $1$, return $1$. So you're trying bigger a bigger $y$ while giving more and more time to $\mathcal A$ to finish. If there is some $y$ so that $x;y\in L$, then you'll eventually try for this $y$ and give $\mathcal A$ enough time to tell you it's the corect $y$. And if it answers yes, then clearly, there is some $y$ so that $x;y\in L$. So we just proved that $L'$ is RE.

Using the property I gave above, there is another simpler proof. You suppose that you can enumerate $L$ and want to enumerate $L'$. Well clearly, you just have to enumerate $L'$ and drop the $;$ and whatever is after it.

If you suppose that $L$ is R then $L'$ may not be R. Recall that the halting problem $HALT=\{\langle M,w\rangle|M\text{ halts on input }w\}$ is undecidable (i.e. $HALT\not\in R$). Let $BHALT:=\{\langle M,w\rangle;n|M\text{ halts on input }w\text{ in at most }n\text{ steps}\}$. Clearly $BHALT\in R$: you can just simulate $M$ on $w$ for $n$ steps and then check if the last state is final. But if you take $L=BHALT\in R$, then $L'=HALT\not \in R$.


How can I make my algorithm more efficient or Is there a better way to solve the problem Problem Statement: You are given an array/sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$ and you need to execute q queries on the array and in each query you will take a positive number as an input and find out all the multiples of the number in the given array and print it.

Input:
2 4 9 15 21 20
q1 = 2
q2 = 3
q3 = 5

Output:
3
3
2

To solve this problem I thought of an algorithm which works as explained below:

Create an array name freq_data[] whose length will be equal to the maximum element of the array, and it stores the count of each and every number occurred in the input array.
For Example:

  array[] = {2, 4, 9, 15, 21, 20}
  max_element = 21
  freq_data[] = {0,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1}

Create an array name multiples[] whose length will also be equal to maximum element encountered in the array. This array will store all the multiples of the numbers between $[1,\text{maximum value}]$. Using multiples[] array, I can answer the query in $O(1)$ time by printing the value at multiples[q - 1].
Initialise the multiples[0] = (size of arr[] - 1) because every number in the array is divisible by 1.
If the query entered is $(\gt \text{maximum value})$ in the array, then the answer will be zero because there will be no element in the array which will be divisible by arr[i] because for the number to be multiple of another, the number should be either equal to or greater than the divisor i.e $(\geq arr[i])$.
Time Complexity: $O(max \times log(max))$
Space Complexity: $O(max)$

Now I was wondering what if I changed the question like instead of taking the queries from the user, I am now interested in finding for each arr[i] how many multiples are present in the left-sub array with respect to arr[i].

Formally: You are given a sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$. Write a program to count the number of multiples in $a_0,a_1,a_2,\cdots,a_{j-1}$ where $0 \leq j \lt i$ for each $a[i]$ where $0 \leq i \lt n$.

For Example:

1. Input:
arr[] = {2 6 3}
Output:
no_of_multiples[] = {0,0,1} // For 2 , 6 there are no multiples present but for 3 there is one multiple present i.e. 6

2. Input:
arr[] = {16,25,63,12,65,45,23,65,78,99,36,12,36,41,36,2,3}
Output:
no_of_multiples[] ={0,0,0,0,0,0,1,0,0,0,2,1,0,2,6,9}

To solve the above problem, the algorithm which I designed is basically based on the previous problem solution but rather than updating the freq_data[] at once I will first check how many multiples of the arr[i] is present in the freq_data[] and after finding all the multiples, I will increment the value at ++freq_data[data[i] - 1] and then I will print the freq_data[i] array after processing the whole arraarr[i].

Time Complexity: $O(n \times log(max))$
Space Complexity: $O(max)$

Solution In C Programming

My question is: Is there any better algorithm to solve the second part i.e Write a program to count the number of multiples in $a_0,a_1,a_2,\cdots,a_{j-1}$ where $0 \leq j \lt i$ for each $a[i]$ where $0 \leq i \lt n$.

Edit-1: With reference to @gnasher729 points, there are constraints on the inputs because if the size of the input gets larger the algorithm will not give the right answer:

$1\leq n \leq 10^5$  Constraint on the length of the sequence
$1 \leq arr[i] \leq 10^6$ Constraint on the values of the sequence

Your attempt runs into a huge problem with the input [1, 2, $2^{63}$].

Either your numbers are so small that it doesn’t matter. Otherwise, you start with a solution, find its speed and why it is slow, and then iteratively improve it. That’s usually a much better method than hoping that someone does the work for you.

For this specific problem, I think that for any algorithm you give someone will be able to come up with input that makes it behave badly. So I would try to find what are typical inputs and design a solution for those.

With the given restrictions, if the numbers are unique, I’d probably turn the number into a bit array, so to find all multiples of k only max / k numbers need checking. If k is tiny, check the elements of the original array. If k = 1 return the number of array elements. And cache the results.

For example to count the multiples of 1,234 you’d check if bits 1,234, 2,468, 3,702 etc are set which would be 800 checks or so. If large numbers are allowed the solution would be awful.


What algorithm paradigm is a recursive solver of Sudoku? I am interested in knowing what algorithmic paradigm are the usual recursive sudoku solvers. Can I consider it a local search? or are they Dynamic programming, greedy, divide and conquer, backtracking?

Let us go over your paradigms one by one:

Local search: In this paradigm, we start with some solution and try to improve it by local changes. Local search can be applied to Sudoku in at least two ways:

Start with a non-legal solution (either not satisfying the Sudoku constraints or not conforming to the filled cells), and try to make local changes (say, one cell at a time) that make it more legal.
Same as before, only we also allow partially filled boards. In this case we might as well start with the board as given, and at each step pick a cell and fill in some legal value. When we get stuck, we can choose a cell and erase it, and so on. This is a stochastic form of local search which in some sense goes against the essence of classical local search, which is completely deterministic and strives to reach an arbitrary locally optimal solution.

Dynamic programming: In this paradigm, we reduce our instance to smaller instances in such a way that the "repertory" of smaller instances is small, and each could be reached in many different ways.  One way you could try to implement this paradigm to Sudoku is as follows. Pick an empty cell and fill it in all possible legal ways. For each such filling, check whether it leads to a solution. Each filling is a smaller problem since it has fewer empty cells. However, the number of possible smaller instances is huge, and each is reached in a unique way, so while this is the same as your recursive solution, it's not really in the spirit of dynamic programming.
Greedy: In this paradigm, you repeatedly make choices that you cannot later change. In the case of Sudoku, this corresponds to identifying unfilled cells which have only one legal filling. This is the approach used by most humans to solve Sudoku, though some puzzles require rather elaborate case analysis to find such safe fillings.
Divide and conquer: In this paradigm you divide your instance into independent instances which you solve separately, and then use their solutions to solve the original instance. One way this could be applied to Sudoku is by finding all possible solutions of 3×3 squares, and then try to combine them together. This is not only a terrible algorithm, but also the recursion is very shallow, whereas in divide and conquer we are aiming at deeper levels of recursion.
Backtracking: The standard recursive approach for Sudoku (pick a cell, enumerate all values, and recurse) is a great example of backtracking, which is the paradigm that best describes this algorithm.


What is an algorithm for what I am trying to do? I have an equation $y=2x^4-20x^2-50x$ within a range of -4 to 6

I already have an algorithim that tell me the y value when I plug in the $x$. It simply uses a loop.

What I am trying to do is determine what will be be the y max value and what $x$ corresponds to it.
Is there some sort of loop or counter I can use. I am program this on SPARC machine but any sort of pseucode loop will be appreciated.

I tried to do the following

I have a counter

You find the local maxima and minima by taking the derivative and setting it to 0.  This leaves you with a non-linear equation $f'(x)=0$ to solve.

The easiest, and most reliable, way to find the zeros of a continuous non-linear equation, $g(x)=0$, is called the Bisection Method.

Find two points $x_-$ and $x_+$ where $g(x_-) < 0$ and $g(x_+) > 0$.  (These are particularly easy to find for odd-degree polynomials, since there will always be at least one real root.)

Now evaluate $g(x_\star)$ where $x_\star = (x_- + x_+)/2$.  If $g(x_\star) > 0$ then let $x_+ = x_\star$ and repeat.  Else if $g(x_\star) < 0$ then let $x_- = x_\star$ and repeat.

Because you are interested in the range [-4,6] you also need to evaluate $f(-4)$ and $f(6)$, because the local maxima may not be inside the range.  (Your function obviously has no finite global maximum. $f(10)$ is about 18000, and grows from there and $f(-10)$ is also about 18000 and grows from there.


Constructing the matrix of a controlled quantum operation How do we construct a matrix that takes into account whether the first qubit is set?

I am trying to construct the controlled-V matrix, but there is no quantum computational paper that describes it so I am looking at CNOT and wondering how the matrix for CNOT determines whether the first bit is set (to apply the NOT part)

Could somebody help?

For any gate $U_n$ on $n$-qubits, you can create a controlled version by taking

$$\text{c-}U_n = \left (\begin{matrix}
I_n & 0 \\ 0 & U_n
\end{matrix}\right)$$

where $I_n$ is the identity matrix (of the same dimension as $U_n$). Note that this gate works on $n+1$ qubits, where the first serves as the control bit.

This should work because the controlled gate is required to satisfy

$\text{c-}U_n |0\rangle|x\rangle = |0\rangle|x\rangle $, and
$\text{c-}U_n |1\rangle|x\rangle = |1\rangle(U_n|x\rangle) $

where $|x\rangle$ is an $n$-qubit state. You should be able to check that the above matrix satisfies exactly this.


Efficient algorithm for 'unsumming' a set of sums Given a multiset of natural numbers X, consider the set of all possible sums:

$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$

For example, $\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}$ while  $\textrm{sums}(\left\{1,1\right\}) = \left\{0, 1, 2\right\}$.

What is the most efficient algorithm for calculating the inverse operation (measured in terms of the size of the input set of sums)? Specifically is it possible to efficiently calculate any of the following:

Whether a given set is a valid set of sums. (For example, $\left\{0,1,2\right\}$ is valid but $\left\{0,1,3\right\}$ is not.)
A multiset that sums to the given set.
The smallest multiset that sums to the given set. (For example, $\left\{1,2\right\}$ and $\left\{1,1,1\right\}$ both sum to $\left\{0,1,2,3\right\}$ but the former is smaller.)

Solution

Solution has two parts. First we discover minimal set, then we prove that it can represent the power sum set. The solution is adjusted for programming implementation.

Minimal set algorithm

Find maximal element $a_{m}$ from the sum (multi)set. $P$, the potential minimal (multi)set is initially empty.
Unless there is only one group, represent $a_{m}$ in all possible ways as a pair of sums that add up to $a_{m}$, $S_{ij}=\{(a_{i},a_{j})|a_{i}+a_{j}=a_{m}\}$
Check that all elements from the set of sums are included.
Find maximal element $a_{s}$ from all $S_{ij}$ (meaning together) with the following property: for each $S_{ij}$, $a_{s}$ is either in $S_{ij}$, or we can find $a_{p}$ from the set of sums so that $a_{p}+a_{s}$ is in $S_{ij}$.
If it is the case that $S_{ij}$ does not contain $a_{s}$, just the sum $a_{s}+a_{p}$, remove $a_{p}+a_{s}$ from $S_{ij}$ (or just set a mark to ignore it) and insert $a_{p}$ and $a_{s}$ in $S_{ij}$ instead.
If an element is present in every $S_{ij}$ remove it from all $S_{ij}$ once (or just set a mark to ignore it and not to touch it any longer) and add it to the list of elements of potential minimal set $P$.
Repeat until all $S_{ij}$ are empty
If some of $S_{ij}$ remains non-empty and we cannot continue, try again with the maximum value from all $S_{ij}$.
Recreate the recursive steps without removals and continue with power set coverage algorithm over $P$. (Before this, you can make a safe-check that $P$ includes all elements that cannot be represented as a sum of two elements so they must be in underlying set for sure. For example, the minimal element must be in $P$.)

(10. Observe that a minimal set solution which is the goal of the algorithm cannot contain more than one repetition of the same number.)

Example:

$$\{2,3,5,7,8,10,12,13,15\}$$

Represent 15 in all possible ways as a sum of two numbers from the set of sums.

$$(13,2),(12,3),(10,5),(8,7)$$

Try to find maximal number that is in all groups or that can be represented as a sum. Obviously we can start searching for it from 8, there is no point going above it.

13 from the first group is 13=8+5 so 13 is fine, but 12 from the second group is not fine since there is no 4 to make 12=8+4 in the set of sums. Next we try with 7. But immediately 13 cannot be covered, there is no 6.

Next we try 5. 13=5+8, 12=5+7, 10=5+5, and for the last either 8=5+3 or 7=5+2 but not both. The groups are now:

$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$

5 is repeating in all groups so we extract it $P=\{5\}$. We extract 5 only once from each group.

$$(8,2),(7,3),(5,5),(3,7)$$

Obviously there is no point going higher than 5 so we try 5 again. 8=5+3, 7=5+2, so all is fine

$$((5,3),2),((5,2),3),(5,5),(3,(5,2))$$

Extract one 5 again from all groups since it is repeating. (This is not common but our case is deliberately created to display what to do in case we have repetitions.) $P=\{5,5\}$

$$(3,2),(2,3),(5),(3,2)$$

Now we try with 3 and have 5=3+2. Add it to the group.

$$(3,2),(2,3),(3,2),(3,2)$$

Now extract 3 and 2 since they are repeating everywhere and we are fine $P=\{5,5,3,2\}$ and the groups are empty.

$$(),(),(),()$$

Now, we need to recreate recursive steps without removals, this simply means doing the above without really removing the elements from $S_{ij}$ just placing them in $P$ and marking not to alter it any longer.

$$(13,2),(12,3),(10,5),(8,7)$$
$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$
$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

Power set coverage

The purpose of this part is to check if the found minimal set is able to cover the power sum set. It is possible that a found solution can cover all given sums, but that they are not power set sums. (Technically, you could simply create a power sum set from the found minimal set and check if each sum, as power set dictates, is in the initial sum set. This is all that just merged with what we already have, so nothing is wasted. You can do this part while rewinding the recursion.)

Encode all elements from the minimal set using successive powers of 2. The order is not important. Encode the same element with a new value as many times as it is repeating. Start from C=1, every next element has C=2C.

$$(2=[1],3=[2],5=[4],5=[8])$$

Replace the elements in the restored recursion list,

$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

with the encoding: 2 with 1, 3 with 2, 5 with 4, and another 5 with 8. Observe that each element has different encoding even though they are repeated.

$$((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))$$

Collect all intermediate sums, at the moment we have (1,2,4,8)

$$((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))$$

Intermediate sums $(1,2,3,4,5,8,9,10)$

$$((14),1),((13),2),((7),8),(15)$$

Intermediate sums $(1,2,3,4,5,8,9,10,13,14,15)$

$$\{(15),(15),(15),(15)\}$$

Check that the result is $2^m-1$, where $m$ is the number of elements in the solution, in the example $m=4$
Collect missing numbers from $1$ to $2^m-1$ in the intermediate sum list

$(6,7,11,12)$

Justify their absence in the following manner: represent each number in binary form

$(6=0110_2)$
$(7=0111_2)$
$(11=1011_2)$
$(12=1010_2)$

$6$ represents the sum of 3+5 since $0110_2$ is covering second and third element from $(2=[1],3=[2],5=[4],5=[8])$. The sum of these elements, 8, is listed in the initial sum list $\{2,3,5,7,8,10,12,13,15\}$, so all is fine.

$7$ represents the sum of 2+3+5 since $0111_2$ is covering first three elements from $(2=[1],3=[2],5=[4],5=[8])$. The sum of these elements, 10, is listed in the initial sum list so all is fine.

$11$ is 2+3+5, and 10 is in the list.
$12$ is 3+5, and 8 is in the list.

If any binary representation corresponds to the sum that cannot be found, report that there is no solution.

So all is fine and $(2,3,5,5)$ is the solution. It is the minimal solution as well.

Discussion

It was necessary to provide the algorithm that is going to check if the sums cover the power set completion, which is what is hidden in the binary expansion. For example if we exclude 8 and 7 from the initial example, the first part would still provide the solution, only the second part would report missing combinations of sums.

First part of discovering the possible minimal set is $mnlog(m)$ which comes to $m\log^2(m)$: we are looking around $m$ elements $n$ times having one $\log(m)$ binary search.

The last part is done in recursion return and it does not require any special effort, we are searching over less than $m$ elements, we need binary form which is $\log{m}$ and we have one addition and search if the sum is in the list, so together it is again about $m\log^2(m)$.

If we assume that the number of elements in the power sum set corresponds to the number of partitions of the largest element in the underlying set then the complexity is around $m\log^3(m)$. Any of the two justifies the initial sorting in order to find the largest element.

Parts of the algorithm assume that we can find the pair of sums in linear time and this requires sorting.

Incorrect start

First part of the algorithm may fail, if we have started it on the wrong foot. For example $2,3,4,5,6,7,8,9,10,11,12,13,15$ has the basic solution $2,3,4,6$ which you get if you start algorithm from 6. However we can start our algorithm from 7, since there is nothing in step 4. that would say not to, and lock ourselves in, the algorithm cannot end properly. The reason is that 7 is 7=4+3 and 4 and 3 are in the solution. So locked algorithm does not always mean that there is no solution, just to try again with lower initial value. In that case, some ideas about the possible values are hidden within remaining $S_{ij}$. That is why we suggested starting from there in case of failure.

Another example, if you miss and start algorithm from 5, you would get $5,4,3,3$ but this one does not include 2.

Notice that this algorithm is not going to give a derived solutions like $2,2,3,4,4$, which we got simply by turning 6 into 4 and 2 in the solution $2,3,4,6$. There are special rules that cover these versions.

The purpose of this algorithm is to provide a solution once we have started it all correctly.

Improvements

Step 4. is the one that could be upgraded in this manner: instead of maximal we could try out every element in descending order that satisfies the given condition. We create a separate branch for each. If some branch does not give a solution, cancel it.

For example for $2,3,4,5,6,7,8,9,10,11,12,13,15$ we could try in the first round $7,6,5,4$ in separate ways since all of them are passing the first test. (There is no reason to use 2 or 3 since we know they have to be in the underlying set.) and simply continue that way all around until we collect all versions that can reach the end. This would create a full-coverage solution which would discover more than one underlying set.

Another thing, since we know that we cannot have more than one repetition if the case is minimal, we can incorporate this in our algorithm.

Overall, the condition in step 4. that a number must repeat in every group or have ability to create a sum is strong enough to get us out of direct exponential waters, which would be an algorithm of simply trying out every combination and creating the power set over each until we find a match.


NP-Completeness of a Graph Coloring Problem Alternative Formulation

I came up with an alternative formulation to the below problem. The alternative formulation is actually a special case of the problem bellow and uses bipartite graphs to describe the problem. However, I believe that the alternative formulation is still NP-hard. The alternative formulation uses a disjoint set of incoming and outgoing nodes that simplifies the problem definition.

Given $n$ outgoing and $n$ incoming nodes (the red and blue nodes in the figure respectively), and a set $w_{ij}$'s of size $n \times n$ of edge weights between the outgoing and incoming vertices. The goal of the problem is to color the thick edges in the figure so that for every incoming node, a condition holds.

  Given a set $\{ O_i \; | \; i=1 \dots n \}$ of output vertices, a set $\{ I_i\; | \; i=1 \dots n \}$ of input vertices, $n \times n$ weights
  $w_{ij} \ge 0$ between $O_i$'s and $I_j$'s for $i,j=1 \dots n$, and a positive
  constant $\beta$, find the minimum number of colors for the edges
  $e_{ii}$ (thick edges in the above figure) such that for all $j=1 \dots n$,

  $$ \frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}} \ge \beta $$

  where $c(i)$ shows the color of the edge $e_{ii}$.

Old Formulation

The following problem looks NP-hard to me, but I couldn't show it. Any proof/comment to show the hardness or easiness of it is appreciated.

  Assume $K_n=\langle V,E \rangle$ is a complete weighted directed graph
  with $n$ nodes and $n(n-1)$ edges. Let $w_{ij} \ge 0$ show the weight
  of the edge $ij$ and $c(ij)$ shows the color of edge $ij$. Given a subset
  of the edges $T \subseteq E$ and a positive constant $\beta$ the goal is:
  find the minimum number of colors such that for each $e_{ij} \in T$:

  $$ \frac{w_{ij}}{1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}} \ge \beta. $$
  and
  $$ c(ij) \neq c(ik) \quad for \quad j \neq k $$

Please note that in the above problem, only the edges in $T$ needs to be colored. That is the problem can be solved in $\mathcal{O}(|T|!)$.

Update:

After Tsuyoshi Ito's comment I updated the problem. The denominator is changed from $1+\sum_{c(kj)=c(ij),k \neq i,e_{kj} \in T} w_{kj}$ to $1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}$. Therefore, the denominator contains the weights outside $T$ as well. That's actually why I mentioned the complete graph in the definition.

I also added an additional constraint $c(ij) \neq c(ik) \quad for \quad j \neq k$. That means, the outgoing edges from a node must be of different colors (but the incoming colors can be the same as long as the inequality holds). This puts an intuitive lower bound on the number of colors, which is the maximum out-degree of the nodes in $T$.

As Tsuyoshi mentioned, $w_{ij}$'s, $T$, and $\beta$ are inputs to the problem and the edge colors are the output.

Update 2:

Problem does not enforce the edges $e_{ij}$ and $e_{ji}$ be of a same color.

It is quite simple to show that the alternative formulation is NP-hard. The reduction is from the vertex coloring problem. Given a graph G with $n$ vertices, we create an instance of the above problem with $n$ output vertices and $n$ input vertices. Weights are set as follows: For all $i$, let $w_{ii}=1$. For $i \neq j$, if there is an edge between vertex $i$ and vertex $j$, let $w_{ij}=w_{ji}=1$, else let $w_{ij}=w_{ji}=0$. In addition, let $\beta=1$.

This is quite obvious but difficult to describe why the reduction is correct.
Let $\mathcal{C}$ show the instance of the graph coloring and $\mathcal{R}$ show the reduced instance of the problem.
To show the above reduction gives a correct solution we need to show that
(1) every valid coloring for $\mathcal{R}$ is valid for $\mathcal{C}$ as well.
(2) the answer given by $\mathcal{R}$ is minimal for $\mathcal{C}$.

If $i$ and $j$ are two adjacent vertices of $\mathcal{C}$,
then they must have different colors in $\mathcal{R}$.
That is because if $i$ and $j$ are adjacent and they have the same color,
the fraction $\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}}$ would result in $\frac{1}{1+X}$,
where $X$ has a positive value.
Therefore, the condition does not hold.
In addition, every valid (but not necessarily minimal) coloring for $\mathcal{C}$,
is a valid coloring for $\mathcal{R}$ as well.
It follows the fact that in a valid coloring of $\mathcal{C}$,
every pair of adjacent nodes have different colors,
so the condition holds for all the colored edges of $\mathcal{R}$ in the solution.
Since every coloring of $\mathcal{C}$ is a valid coloring for $\mathcal{R}$,
the minimal solution to $\mathcal{R}$ must be a minimal solution to $\mathcal{C}$
as well.
Otherwise, it is not a minimal one because the solution to $\mathcal{C}$
gives a solution with a smaller number of colors.


Topological sorting colored tree EDIT: The most general case I need is not a tree but any Directed Acyclic Graph.

I have a directed acyclic graph.

I need to sort it in a list so that in the list every node comes after any node it can walk to in the graph.

So far so good, just use a topological sorting algorithm.

However, I have an additional constraint: Each node in the graph is colored, and I need to find a sorting so that the list is as cohesive as possible. In other words, if you walk the list, you should see a change in colors as few times as possible.

Other thoughts:

I need an efficient algorithm. No iterating through all possible sortings.
The set of colors is typically much smaller than the set of nodes in the graph.
If no efficient exact algorithm is possible, I would be happy with a heuristic one that is likely to produce good results.
There is some information that one could potentially use for the heuristic: The colors are also partially ordered, and this ordering of the colors is correlated to the ordering of the nodes. I.e. a node is likely (but not guaranteed) to have a color that is "smaller than" the color of its parent node.
You can think of the problem this way: I have a set of jobs, and each job can depend on the output of several other jobs (if x depends on y there is an arrow from x to y). There is an overhead associated with setting up the data needed for each job, but this overhead is significantly reduced if the previous job had the same "color". The whole set of jobs is typically executed many thousand times, so if one can find an not too expensive way to improve the order of the jobs, that will pay off.

So far I have come up with this algorithm which works well most times, but not always:

first pass:

Define the order "<=" so that x <= y if y can walk to x in the graph.

find any topological sort of the nodes and put it in the list L
(L is sorted from smallest to largest w.r.t the partial ordering "<=" )

W = []
for x in L:
   find the earliest y in W so that color(x)==color(y) && there is no z in W with z > y and x > z
   if y exists:
       insert x in W after y.
   if y does not exist and there is no z in W with x > z:
       place x at the beginning of W
   else:
       place x at the end of W

second pass:

 for each continuous group G of colors in W:
    for x in G in reverse order:
       find the latest y in W so that color(x)==color(y) && there is no z in W with z > x and z < y
       if y exists:
           move x directly before y in W

The second pass may seem a little puzzling, but it is just my experience that it tends to improve the results. I.e. some times it will be able to move one whole group of colors past another group and join a third group of the same color.

I think the reason that the first pass is not sufficient is that there can be complicated interdependencies between the nodes that are sorted in L after the current x you are looking at, and so you can't know the optimal placement of x in the first pass, you just have to go with something.

Any help would be great!

Suppose you know the list of colors that appear in contiguous parts of an optimal ordering. Then, you can easily find this optimal ordering: simply put as many nodes of the current color in your list as the parent-child order allows and proceed with the next color in your list. This greedy strategy is optimal, because once you have started a color, you will not 'regret' taking a node of the same color later as it adds no cost and only gives more options. If you put all 'free' nodes that already have their parents processed in separate lists, this can be done in $O(n)$, where $n$ is the number of nodes in your forest.

Of course, we do not know this list, so we should figure out how to find it. The number of color lists you would have to check in an uninformed search is $c(c-1)^{k}$, where $c$ is the number of colors you have and $k$ the minimal number of color switches in the final order. If you're lucky, $c$ and $k$ are sufficiently small for a brute-force search and we are done.

However, this will quickly become unfeasible, so I doubt you can afford to spend the $O(c(c-1)^k n)$ time required to do a brute-force search$^1$. Finding an optimal list 'looks hard'. I have no formal proof of e.g. NP-hardness, but it is clear that decisions made early on depend on the structure of the entire forest, so the most natural approach is to try to create subdivisions of by 'cutting' the forest to get subproblems and use e.g. dynamic programming. However, since the nodes can be ordered in many ways, I do not see how to represent these cuts with only polynomially many states. Another hint is that you can see this as a special case of the scheduling problem with partial order requirements.

So, since I think it likely we cannot find an efficient exact solution, you should try an heuristic approach or can perhaps even find an approximation algorithm. I will finish with some observations that may help you in developing such an approach:

If we decide on the last color in list first and build the ordering backwards, observe that we can only choose nodes where all descendants have the same color: if not, there is a node of another color that should be later in the list. Since we would select all children of the same color as a parent if we had chosen a front to back order in an optimal ordering, we should select only subtrees of the same color where the root has no parent of the same color. It is possible that for some colors, there are no such subtrees, which means that we have less options for the final color.
If there is a color for which you can select all remaining nodes, you should select that color. This may occur quite often if the correlation between the color ordering and node ordering is high.
One idea for an heuristic is to select the color that is 'blocking' the most nodes of other colors: you can look at the total number of 'chains' of nodes of the same color that are accessible after removing the color or at the number for a specific color you would like to remove first or the maximum number over all colors.

$^1$: You could be slightly more clever and do recursive backtracking where you can prune some searches, but this has the same worst case running time.


Use Rice's theorem to show that the language of optimisable Turing machines is undecidable I have an assignment to do and I'm quite stuck with the following question :

Use Rice's theorem to show that
$ \qquad L' = \{ \langle M \rangle \mid \; (\exists \text{ TM } M') \; [ L(M') = L(M) \text{ and } M' \text{ has less than 29 states} ] \}$
is undecidable.

I have absolutely no idea how to proceed.
Would someone be kind enough to, at least, give me some clues?
EDIT
First, I wrote the question wrong. It is now '$M'$ has less than 29 states' (not 'steps')."
Here's what I'm thinking after more reading and consulting other students at school.
Rice's theorem :

$L = \{ \langle M \rangle \mid L(M) \text{ has some property } P \}$ where :

$P$ is non-trivial, i.e. there exists at least one machine $M_1$ such that $\langle M_1 \rangle \in L$, and at least one machine $M_2$ such that $\langle M_2 \rangle \not \in L$.

$P$ is indeed a property of the language of TMs, i.e. whenever $L(M_a) = L(M_b)$, we have $\langle M_a \rangle \in L$ if and only if $\langle M_b \rangle \in L$.

Then, $L$ is undecidable.

So here, the property is "$M'$ has less than 29 states".
We can show that this property is non-trivial.
Let's take the language "abcdefghijklmnopqrstuvwxyz0123456789" (only one string is accepted). We can build a TM $M$ this way :
-> Enter in state $q_0$
-> In $q_0$ : if you read "a", proceed to $q_a$, otherwise go to $q_{reject}$ and halt.
-> In $q_a$ : if you read "b", proceed to $q_{ab}$, otherwise go to $q_{reject}$ and halt.
$\vdots$
-> In $q_{abcdefghijklmnopqrstuvwxyz012345678}$ : if you read "9" go to $q_{accept}$, otherwise go to $q_{reject}$ and halt.
So here we got 3 "basic states" : $q_0$, $q_{reject}$ and $q_{accept}$ and we have $|abcdefghijklmnopqrstuvwxyz0123456789| - 1$ states (there is no $q_{abcdefghijklmnopqrstuvwxyz0123456789}$ because when we read "9" at the end, we go to $q_{accept}$). So that's 26 + 10 - 1 = 35 states. We have a total of 35 + 3 = 38 states.
Unless I am wrong, there can't be a TM $M'$ that can test wether a string $w$ belongs to that language without having at least 38 states !
So the property "$M'$ has less than 29 steps" is non-trivial as there is at least one TM that respects it, and at least one that does not.
Now, $P$ is indeed a property of the language of TMs, because any two machines $M_1$ and $M_2$ such that $L(M_1) = L(M_2)$ implies :
$\langle M_1 \rangle  \in L' \Leftrightarrow L(M_1) = L(M_2) \Leftrightarrow \langle M_2 \rangle \in L'$.
(I know there is at least one missing clause in there, but I can't figure how to write it, it's got something to do with that "$M'$ has less than 29 steps")
So, according to Rice's theorem, $L'$ is undecidable.

There is some TM which is not in $L'$, and there is some TM which is in $L'$. So the definition of $L'$ determines a nontrivial property on r.e. languages and so by Rice's theorem it is not decidable.