NP-hardness proof, what is wrong with it? My question is the following: If we have a problem divided into two versions, weighted and unweighted. Can we prove that the unweighted problem is NP-hard from the fact that the weighted problem is NP-hard ?

For example let say I have the knapsack problem (the weighted version):

$$\max \sum_{i}^n w_i x_i$$
$$\text{s.t.} \sum_{i=1}^n p_i x_i\leqslant W,\quad(WP)$$
$$x_i\in\{0,1\}.$$

This problem is know to be NP-hard problem. However, the unweighted version of this problem is given by:
$$\max \sum_{i}^nx_i$$
$$\text{s.t.} \sum_{i=1}^n p_i x_i\leqslant W,\quad(P)$$
$$x_i\in\{0,1\}.$$
is not NP-hard since the optimal solution is to sort the items in the ascending order with respect to $p_i$ and start filling the bag until the capacity $W$ is reached.

The problem is the following: I used the unweighted version of this problem as a special case of the weighted version and I showed that unweighted is an NP-hard problem. What is my mistake?
Here is my steps: I will reduce $(WP)$ to $(P)$ in polynomial time. So, an instance of $(P)$ is constructed easily by taking $w_i=1$. And I am done and hence $(P)$ is NP-hard which is obviously wrong.

Thank you to correct me and give me if possible some good references that deal with such weighted and unweighted problems?

No, you cannot prove that the unweighted problem is NP-hard in this way.  The error is that you cannot reduce WP to P in polynomial time (without proving P=NP).

Remember what the input to each problem is. For WP, you are given a list of $w_i$ and $p_i$ and must choose a setting of the $x_i$. So once I am given a fixed list of $w_i$ and $p_i$, I would need to come up with an instance of P (which is just a list of $p'_i$) so that the solution tells me the solution to WP.

The key point is that you seem to say that we can just take all $w_i = 1$ to reduce WP to P, but we can't change the $w_i$: They are given as part of the input. It is true that P is the special case of WP where all $w_i = 1$, but the issue is, when we are given an instance with $w_i \neq 1$, we have to solve this instance and we can't change the $w_i$ we are given.


Why is the Turing machine rather than the finite automaton the main model for computation if computers have finite memory? Any physical computational device clearly has finite memory. On the other hand the input can be external and could therefore potentially be infinite. This idea is perfectly captured by the deterministic finite automata (DFA), so why do we use the Turing machines instead?
Let's consider a popular example. The language
$$L = \{a^nb^n, n\in \mathbb{N} \} $$
is recognizable by a Turing machine, but not by a DFA. Suppose that you are getting a string from a server, and you need to determine whether it belongs to $L$ or not. I'd say you can't do it, because you might, in fact, run out of memory.

First, I want to clear a misconception:

On the other hand the input can be external and could therefore potentially be infinite.

Usually unless specified otherwise for some purpose, we do not consider TM inputs to be infinite, only unbounded in length (similar to DFA input strings, as a normal DFA cannot accept or reject a string that never ends). This distinction might be hard to grasp, but it will be useful. If you're curious, you can read up on $\omega$-automata, a class of automatons specifically modeling problems with infinite-length inputs.
It is true that an individual computer is, strictly speaking, more akin to an extremely big DFA than a TM. However, by modeling algorithms as TMs, we are trying to make a more general statement about computability, one that transcends individual computers. The theory of computation seldom concerns itself with the need to establish that a particular student laptop, ancient server or supercomputer can perform a particular computation.
Rather, by modeling a problem as a TM and comparing it to a real computer, we're establishing that the computation is possible in the sense that while a given machine might not be able to actually finish it, the only obstacles are the impractical logistics of acquiring a machine with enough RAM/paper/tape/you-name-it and possibly waiting impractically long, too. Alternatively, we're establishing that a given computer or model (eg. a programming language) can be used to simulate a Turing Machine and therefore compute anything computable under the same logistic constraints. And since the inputs are finite, the amount of memory you need to scrounge up (for a working, terminating algorithm) is finite too.
So yes, the TM does conveniently ignore that a given computer has a bounded memory, but since it doesn't need to represent a "given" computer but any computer, this slip is easy to forgive and doesn't prevent the comparison from serving its purpose. If you need to make formal proofs about a single computational device with bounded memory where the finite amount of states is likely to present an interesting issue, a DFA-equivalent model might indeed be better.


Dynamic Programming vs Memoization I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization.

Am I understanding correctly? Or is DP something else?

Summary: the memoization technique is a routine trick applied in dynamic programming (DP). In contrast, DP is mostly about finding the optimal substructure in overlapping subproblems and establishing recurrence relations.
Warning: a little dose of personal experience is included in this answer.
Reading suggestion: If this answer looks too long to you, just read the text in boldface.
Background and Definitions
Memoization means the optimization technique where you memorize previously computed results, which will be used whenever the same result will be needed.
Memoization comes from the word "memoize" or "memorize".
Dynamic programming (DP) means solving problems recursively by combining the solutions to similar smaller overlapping subproblems, usually using some kind of recurrence relations. (Some people may object to the usage of "overlapping" here. My definition is roughly taken from Wikipedia and Introduction to Algorithm by CLRS.) I will only talk about its usage in writing computer algorithms. Note that an actual implementation of DP might use iterative procedure.
Why is DP called DP? The word "dynamic" was chosen by its creator, Richard Bellman to capture the time-varying aspect of the problems, and because it sounded impressive. For the full story, check how Bellman named dynamic programming?.
Nowadays I would interpret "dynamic" as meaning "moving from smaller subproblems to bigger subproblems". (The word "programming" refers to the use of the method to find an optimal program, as in "linear programming". People like me treat it as in software programming sometimes.)
Explanations
Why do some people consider they are the same?
It is understandable that Dynamic Programming (DP) is seen as "just another name of memoization or any tricks utilizing memoization". When the examples and the problems presented initially have rather obvious subproblems and recurrence relations, the most advantage and important part of DP seems to be the impressive speedup by the memoization technique.
In fact, for some time, I had been inclined to equating DP to mostly memoization technique applied to recursive algorithms such as computation of Fibonacci sequence or the computation of how many ways one can go from the left bottom corner to the top right corner of a rectangle grid.
How are DP and memoization different?
The memoization technique is an auxiliary routine trick that improves the performance of DP (when it appears in DP). It appears so often and so effective that some people even claim
that DP is memoization
Let me use a classic simple example of DP, the maximum subarray problem solved by kadane's algorithm, to make the distinction between DP and memoization clear.
Since I was a kid, I had been wondering how I could find the maximum sum of a the contiguous subarray of a given array. First thought was grouping adjacent positive numbers together and adjacent negative numbers together, which could simplify the input. Then I tried combine neighbouring numbers together if their sum is positive or, hm, negative. Then the uncertainty seemed attacking my approach from everywhere. Many years later, when I stumbled upon the Kadane's algorithm, I was awe-struck. It is such a beautiful simple algorithm, thanks to the simple but critical observation made by Kadane: any solution (i.e., any member of the set of solutions) will always have a last element. Trust me, only if you can appreciate the power of such a simple observation in the construction of DP can you fully appreciate the crux of DP.
Please note there is not any (significant) usage of memoization in Kadane's algorithm.
Just in case you might brush off Kadane's algorithm as being trivial, let me present two similar problems.

Can you find efficiently the maximum sum of two disjoint contiguous subarray of a given array of numbers?
Can you find efficiently two disjoint increasing subsequence of a given sequence of numbers the sum of whose lengths is the maximum? (This problem is created by me.)

If you can find the solution to these two problems, you will, I believe, be able to appreciate the importance of recognizing the subproblems and recurrence relations more. That might just be the start of a long journey, if you are like me.
By Wikepedia entry on Dynamic programming, the two key attributes that a problem must have in order for DP to be applicable are the optimal substructure and overlapping sub-problems. In other words, the crux of dynamic programming is to find the optimal substructure in overlapping subproblems, where it is relatively easier to solve a larger subproblem given the solutions of smaller subproblem.
In summary, here are the difference between DP and memoization.

DP is a solution strategy which asks you to find similar smaller subproblems so as to solve big subproblems. It usually includes recurrence relations and memoization.
Memoization is a technique to avoid repeated computation on the same problems. It is special form of caching that caches the values of a function based on its parameters.

More advanced dynamic programming
Here I would like to single out "more advanced" dynamic programming. More advanced is a pure subjective term. What I would like to emphasize is that the harder the problems become, the more difference you will appreciate between dynamic programming and memoization.
Even as the problem becomes harder and varied to solve, there is not much variation to the memoization. The memoization technique are present and helpful most of the time. However, it becomes routine. After all, all you need to do is just to record all result of subproblems that will be used to reach the result of final problem.
However, as I have been solving more and harder problems using DP, the task of identifying the subproblems and construction of the recurrence relations becoming more and more challenging and interesting. There are many variations and techniques in how you can recognize or define the subproblems and how to deduce or apply the recurrence relations. Many of the harder problems look like having a distinct personality to me. Here are some classical ones that I have used.

Knuth's optimization that reduces the dimension of computation almost by one.
the Golden Rule of harder DP problems (named by me for the lack of a name): when you cannot move from smaller subproblems to a larger subproblem because of a missing condition, add another parameter to represent that condition.
Convex hull trick
Dynamic programming on graphs with bounded treewidth

The following is a nice article.

Dynamic programming from novice to advanced


Minimum spanning tree with two minimum edge weights Given an undirected weighted graph $G$ with two edges of minimum weight and all other edges are distinct. Does G have a unique minimum spanning tree?

I know the proof for if all edge weights are distinct (it does give a unique MST) and I am thinking that if two edges of minimum weight are in $G$ then I should be able to show a counter example. But so far I have not been able to produce one.

So my question is does it give a unique MST if the graph $G$ contains two minimum weight edges?

Yes $G$ has a unique MST (assuming it is not a multigraph). Take a look at Kruskal's algorithm: the edges are ordered ascending by weight and then added to the MST unless there is a cycle. After adding the two minimum edges, you can't have a cycle, therefore both are in the MST.

Edit: As Paresh pointed out, this is not a complete proof, since there may be MSTs which cannot be produced by Kruskal's after permutating equally weighted edges in the sorted list. But Kruskal's is in fact able to produce any MST. Proof.


Alternate proof of the Caro-Wei theorem for lower bounding the independence number Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ that are pairwise non-adjacent. So Caro-Wei says that $\alpha(G) \geq \sum_{d_i \in V(G)}{\frac{1}{1+d_i}}$. The standard probabilistic proof goes as follow, here we let $V(G)=\{1,2,...,n\}$:

Consider the set $S_n$ of permutations of the vertices in $G$ and $\sigma \in S_n$ be a permutation in $S_n$. Let $A_i$ be the event that $\sigma(i)<\sigma(j), \forall j \in N(i)$ namely all neighbours $j$ of the vertex $i$ gets maps to by $\sigma$ to some number greater than $\sigma(i)$. There are $\binom{n}{1+d_i}$ places that $\sigma$ can map the vertex $i$ and its neighbors to. Futhermore, $\sigma(i)$ is the smallest, so there are $d_i!$ ways for the neighbours of  $i$ to be map to and $(n-d_i-1)!$ ways for the remaining number to be permuted. So $P(A_i)=\frac{\binom{n}{d_i+1} d_i!(n-d_i-1)!}{n!}=\frac{1}{1+d_i}$. Now consider the subset of the vertex set of $G$, $U=\{i \mid A_i = \text{true}\}$. Notice that two vertices in $U$ does not share an edge. The expected value $E[|U|]=\sum_{i\in \{1,...,n\}}{\frac{1}{1+d_i}}$. So done.

But I'm wondering if there is a proof not involving probabilistic method.

An algorithmic proof is given by Murphy [1, Section 1], where he attributes the algorithm to Erdös [2].

As a side remark, I don't know what the original proof of Caro or Wei is, but I believe the proof you mention is due to Alon and Spencer [3].

[1] Murphy, Owen. "Lower bounds on the stability number of graphs computed in terms of degrees." Discrete Mathematics 90.2 (1991): 207-211.

[2] Erdös, Paul. "On the graph theorem of Turán." Mat. Lapok 21. (1970): 249-251.

[3] Alon, Noga, and Joel H. Spencer. The Probabilistic Method. John Wiley & Sons, 2004.


Difficulty in understanding the proof of "Every context-sensitive language L is recursive" as given in the Peter Linz text I was going through the automata text by Peter Linz. There I came across the proof the theorem below. I could not quite get the portion of the proof in bolds.

Every context-sensitive language L is recursive.
Proof: Consider the context-sensitive language $L$ with an associated context- sensitive grammar $G$, and look at a derivation of $w$
$$S \Rightarrow x_1 \Rightarrow x_2 ... \Rightarrow x_n \Rightarrow w$$.
We can assume without any loss of generality that all sentential forms in a single derivation are different; that is, $x_i \neq x_j$ for all $i\neq j$ . The crux of our argument is that the number of steps in any derivation is a bounded function of $|w|$. We know that
$$|x_j| \leq|x_{j + 1}|,$$
because $G$ is noncontracting. The only thing we need to add is that there exist some $m$, depending only on $G$ and $w$, such that
$$|x_j| \lt|x_{j + m}|,$$
for all $j$, with $m = m(|w|)$ a bounded function of $|V\cup T|$ and $|w|$. This follows because the finiteness of $|V \cup T|$ implies that there are only a finite number of strings of a given length. Therefore, the length of a derivation of $w \in L$ is at most $|w| m (|w|)$.
This observation gives us immediately a membership algorithm for L. We check all derivations of length up to $|w|m(|w|)$. Since the set of productions of $G$ is finite, there are only a finite number of these. If any of them give $w$, then $w \in L$, otherwise it is not. ■

What I could reason on my own is that, since context sensitive grammars are non contracting, we can apply the productions in steps, and if we get more $|w|$ symbols in the right sentential form, it then when we stop. So we shall be ultimately above to check where $w$ is generated by a context sensitive grammar or not.

What he wants to show here is that for any sentence of some given length, there is a (very large but finite) number $m$ which is the maximum number of steps in a derivation of the sentence.
If that is true (which it is), then we can figure out whether or not a sentence is generated by the grammar by enumerating all possible derivations with at most $m$ steps. If we encounter the sentence in one of these derivations, then we have derived it. Otherwise no derivation exists.
There are a finite number of such derivations, so this process will eventually finish. That makes it recursive, since it eventually finishes both on success and on failure). (It won't finish during the lifetime of the universe but mathematicians are allowed to ignore inconvenient aspects of reality).
Type 0 grammars (not context-sensitive) are not non-contracting, so we can't limit the number of possible derivation steps. We can still enumerate all possible derivations in order by derivation length (in steps), but we have no guarantee that the process will ever terminate on failure. (More accurately, there is no point on the enumeration at which we can say that a derivation for the sentence will never appear.) So Type 0 grammars are recursively enumerable, but not recursive.


Transform calculation to memory Theoretically, is it possible to convert the processing power of the CPU into several tens of bits of memory?

My question is unusual, but it's very interesting. I'm looking for a way to create a small (64 bit) memory department that the user could not access.

There's a line of research that studies how to store sensitive data in the CPU's registers instead of RAM.  Here's a seminal paper:

TRESOR Runs Encryption Securely Outside RAM.  Tilo Müller, Felix C. Freiling, Andreas Dewald.  Usenix Security 2011.

There's also work in storing sensitive data in the cache.  Here are two of the seminal papers:

CARMA: A hardware tamper-resistant isolated execution environment on commodity x86 platforms.  Amit Vasudevan, Jonathan McCune, James Newsome, Adrian Perrig, Leendert van Doorn.  ASIACCS 2012.
Copker: Computing with Private Keys without RAM.  Le Guan, Jingqiang Lin, Bo Luo, Jiwu Jing.  NDSS 2014.

There's lots more work on these subjects, but this will get you started.  You can find follow-up papers in the standard ways (Google Scholar, etc.).

You might also be interested in Intel SGX, TrustZone, TPMs, or related schemes for hardware support for secure computation.


Pick elements that don't exhaust any set The following is an NP-Complete problem:

Suppose you have a collection $\mathcal{C}$ of sets, so that $A_i\in \mathcal{C}$ and $A_i$ is some set--we can suppose the elements of $A_i$ are integers.  We want some $k$ integers, say $X \subseteq \bigcup_{A_i\in \mathcal{C}}A_i$ where $X$ has $k$ elements, and subject to the constraint that $A_i \not\subseteq X$ for any $A_i \in \mathcal{C}$.

I primarily am curious whether this is a named problem and if so, what is it's name?  I've already figured out how to show that it's NP-Complete by reduction to the Independent Set problem.  However I am curious to get some more context to this problem, so I wanted to research it a bit.  But I can't find it referenced anywhere.

This is the hitting set problem in disguise.
Let $U=\cup_{A_i \in \mathcal{C}} A_i$ be the universe and $\overline{X} = U \setminus X$.  Then your problem can be equivalently stated as follows: given $\mathcal{C}$ and $k$, find $\overline{X}$ that has $|U|-k$ elements, and such that $A_i \cap \overline{X} \ne \emptyset$ for each $A_i \in \mathcal{C}$.  That is exactly the hitting set problem.


Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, but I'm not sure how to write it formally.

Here is what I have:

Let $x_1$ and $x_2$ be two letters in the encoding where $x_1$ is before $x_2$.

It is given that $\text{freq}(x_1) < \text{freq}(x_2)$.

Suppose the contradiction, $\text{code_length}(x_1) < \text{code_length}(x_2)$.

The cost would be $$B(A) = \text{freq}(x_1)\times\text{code_length}(x_1) + \text{freq}(x_2)\times\text{code_length}(x_2)+r$$ where $r$ is the remaining cost of the other letters in the code.

If we were to swap the code lengths of $x_1$ and $x_2$, the cost would become $$B(A) = \text{freq}(x_1)\times\text{code_length}(x_2) + \text{freq}(x_2)\times\text{code_length}(x_1)+r$$

The cost would decrease, meaning the code where they are not swapped is not an optimal encoding.

The problem is I'm not sure how to prove that the cost would decrease. Is that provable? Also, is there a better approach?

I have come up with a solution.

To show that the old $B(A)$ is larger than the new $B(A)$, it is necessary to show that

$$\text{f}(x_1)\times\text{c_len}(x_1) + \text{f}(x_2)\times\text{c_len}(x_2) > \text{f}(x_1)\times\text{c_len}(x_2) + \text{f}(x_2)\times\text{c_len}(x_1)$$

($\text{f}(x)$ = frequency of $x$, $\text{c_len}(x)$ = length of $x$'s encoding.)

By moving terms over and using distributive law:

$$\text{f}(x_1)(\text{c_len}(x_1) - \text{c_len}(x_2)) > \text{f}(x_2)(\text{c_len}(x_1) - \text{c_len}(x_2))$$

Since $\text{c_len}(x_1) < \text{c_len}(x_2)$,
$$\text{c_len}(x_1) - \text{c_len}(x_2) < 0$$

Therefore dividing both sides by $\text{c_len}(x_1) - \text{c_len}(x_2)$ leaves:

$$\text{f}(x_1) < \text{f}(x_2)$$

Which is true as it is a premise.

Correct me if I have made a mistake.


Problems that feel exponential but are P I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ultimately solves them. Examples of what I mean:

Linear Programming (The simplex algorithm is exponential time; it took a long time to find a polynomial time solution!)
More generally, Semidefinite Programming
Primality testing
2-SAT and HORNSAT
Computing determinants (if this doesn't sound difficult, consider the permanent)
Finding perfect matchings
A variety of hard group theoretic problems that can be accomplished using the Classification of Finite Simple Groups
A variety of hard graph problems that can be accomplished using complicated Forbidden Minor characterizations (embeddability on an arbitrary surface; bounding of treewidth and branchwidth; Delta-Wye reducible graphs)
Computing exponentials in a bounded group (i.e. computing $a^b \mod k$ in $\log b$ steps, as accomplished by repeated squaring)
Computations relying on the LLL algorithm. (As a special case: Euclidean algorithm. As a more general case: PSLQ or HJLS algorithms.)
Constraint problems without Taylor terms (?). I admit I don't fully understand this, but it sounds like it probably subsumes the 2-SAT / HORNSAT cases above, and any linear algebra over finite fields. See here for a longer post
Problems computable via holographic reductions.

As a honorable mention, I would also mention Graph Isomorphism, because it's still awfully easy ($n^{\log^2 n}$), and equivalent to so many other isomorphism problems:

Digraphs/multigraphs/hypergraphs (a sort of 'harder' problem)
Finite automata/CFGs

Obviously there's a range of difficulty in these, but all leave at least some people with some sense of 'surprise' in the sense that the problem can sound difficult but turn out tractable. LP might sound relatively straightforward, but took people quite a while to build an actual solution to. Repeated squaring or solving 2-SAT is something an undergraduate could possibly come up with on their own, but if you had only learned about NP-Complete problems without having seen HORNSAT, it might sound like a natural candidate for NP-Completeness. Solving the CFSG or having a polynomial way to check for Delta-Wye reducability are no mean feats.

I hope this makes sense; there are obviously lots of subjective attributes here, but I'm curious to hear what other people find to be efficient solutions to "obviously hard" problems.

For me one of the most efficient algorithms is the Blossom V algorithm that find maximum weight perfect matching in a general graph:

https://en.m.wikipedia.org/wiki/Blossom_algorithm


Universal hashing - insert / search / delete I don't understand the highlighted text below in CLRS 3rd Ed.:

I'm not sure I even understand what the sentence is trying to say. For example:

What do they mean by "... operations containing $\mathcal{O}(m)$ INSERT operations"?  Which operations contain which?
If the (total) expected time is $\Theta(n)$ how can any of these operations contain other $\mathcal{O}(m)$ operations?

Let me try to explain this with an example. Let us say if m=10 and n=1000.
If I have m number of insertions in a table with m slots, it is going to be O(m). Right?
But if we have 1000 insertions in a table containing 10 slots, it is not the same math anymore. Since you will have to deal with collisions at a greater frequency. It no more remains linear math. Thus if the n stays small enough that it is in order of O(m), you can have expected Theta n for n inserts. If inserts increase at a number much greater than m, the collisions doesn't let it be linear.


Is it possible to build DFA for odd-length words with 1 in the middle? $L := \{w \in \{0,1\}^* | $the length of $w$ is odd $ \wedge $ 1 is in the middle of $w\}$

So the alphabet is $\{0,1\}^*$. My problem is that I can't keep track of the equality of chars before and after $1$. A limited DFA for the length less than 6:

How can I expand it so that it would accept any length words? Is it possible?

I tried putting cycles in it, but as I already said, then I just cant keep track of the number of chars after $1$ to be equal to that before. In other words 1 to be always in the middle.

No, you can not. Proof by Pumping Lemma: Assume $L$ is regular and $n$ be the pumping length consider the word $w=0^n10^n$. Thus there are $x,y,z \in \{0,1\}^*$ with $|xy|<n$ and $|y| > 0$ such $xyz=w$. Then $\forall i\in \mathbb{N}_0: xy^iz \in L$.

But due to its length constraint $x$ and $y$ consist of $0$ only and all are before the $1$. Thus $xy^2z = 0^{n+|y|}10^n \notin L$.

Thus, $L$ is not regular and can not be expressed by any DFA.


Prove that every thin AVL tree may be converted to red-black tree Let's define thin AVL tree as AVL tree $t'$ such that contains minimal possible number of nodes among all AVL tree $t$ such that $height(t)=height(t')$.

I am trying to prove that every thin AVL tree may be colored to be red-black tree. I would like to use induction. I tried to do induction by height - but as you could see Every AVL tree may be red black tree I didn't managed to (I have very similar problem).

Could you give me a hint ?

I can see following thing:
thin avl tree of height $h$ has exactly one vertex on height $h$ - contrary avl tree wouldn't be thin.   Moreover this node must be red (property of black height).
Example:

Just a remark.

Your "thin" trees are sometimes know as Fibonacci trees. A Fibonacci tree $T_h$ of height $h$ is recursively defined as root with two subtrees $T_{h-1}$ and $T_{h-2}$. Hence the name.

As the number of black nodes along each path from root to leaf must be equal, this means that the subtrees $T_{h-1}$ and $T_{h-2}$ must have the same black height  in $T_h$, although they differ in height.


How to tell if a language is recognizable, co-recognizable or decidable? If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable?

Basically any hints or tricks that can be used to tell. Or maybe the common patterns to search for to tell which kind it is?

L is recognizable

A language $L$ is recognizable if and only if there exists a verifier for $L$, where a verifier is a Turing machine that halts on all inputs and for all $w \in \Sigma^*$, $w \in L \leftrightarrow \exists c \in \Sigma^*. V\text{ accepts }\langle w, c\rangle$. Commonly, $c$ is thought of as a "certificate" or "proof" that $w$ is in $L$ and the verifier $V$ checks whether $c$ is a valid proof of $w$ being in $L$. (Note that this definition is equivalent to the recognizer definition because we can construct a recognizer for a language from a verifier for that language). Now to determine whether or not a language is in RE we can ask the following question:

  Given a string $w \in L$, could you prove that $w \in L$?

For example, consider $HALT = \{\langle M, w\rangle\ |\ M\text{ is a TM that halts on }w\}$. $HALT$ is recognizable because to prove to you that $M$ halts on $w$, I can just tell you the number of steps you should run $M$ for and if $M$ does halt after that many steps, you would be convinced that $\langle M, w\rangle \in HALT $.

L is co-recognizable

Similarly, a language $L$ is co-recognizable if and only if its complement is recognizable, or in other words if there exists a verifier for $\overline{L}$. Thus to see if a language is in co-RE, we can ask:

  Given a string $w \not\in L$, could you prove that $w \not\in L$?

Taking again the example of $HALT$, we can use this intuition to show that $HALT$ is not co-recognizable. This is because if I told you that some machine $M$ does not halt on input $w$, there isn't really anything I can tell you to convince you of that fact. I could run $M$ on $w$ but even if we've been watching $M$ run and haven't seen it halt yet, we don't know that it won't go and halt sometime in the future.

L is decidable

Finally, a language $L$ is decidable if both $L$ and $\overline{L}$ are recognizable. So if the answer to both of the above two questions is yes, then the language is decidable.

As an example, consider $L = \{a^nb^n\ |\ n \in \mathbb{N}\}$. Given a string $w \in L$, could I prove to you that $w \in L$? Sure, I could count up the number of $a$s and the number of $b$s and show that they're equal, so $L$ is recognizable. What about if $w \not\in L$? I could prove that a string is not in $L$ by showing that it's either not of the form $a^nb^m$ or that there's a mismatch in the number of $a$s and $b$s. Thus, $L$ is co-recognizable. Since it's both recognizable and co-recognizable, $L$ is also decidable.

Reference: I'm a TA for an intro computability/complexity theory class at my university and my professor made this really helpful animated guide for reasoning about regular, decidable, and recognizable languages.


What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms:

When the same heuristic information is given to all the algorithms.

This is a nice question! Indeed, A* is known to be asymptotically optimal in the number of expansions. This is usually understood by saying that any algorithm solving the same problem should expand the same set of nodes at least. A unique property of A* with regard to its asymptotical behaviour is that, in addition, it never re-expands any nodes ---in contraposition with other algorithms such as IDA* and RBFS.

But first things first. Before addressing why A* is asymptotically optimal let me note in passing that A* is a suitable algorithm not only for the shortest path problem but those problems that actually verify the suboptimal structure, this is, that all the subpaths in the solution are solutions also between their respective start and end nodes. Additionally, A* is asymptotically optimal not only with regard to evaluation functions $f()$ which are scalar values but, in general, with any that verify the so called cost algebras.

In the following I address the question by mentioning the two contributions of A* that address its asymptotically optimal behaviour and also the role played by the heuristic function $h(n)$.

From the preceding paragraph, the first condition is that $f()$ should be non decreasing, i.e., $f(n) \leq f(n')$ where $n'$ is a descendant of $n$. This property is exploited by Raphael, Hart and Nilsson (the authors of A*) to create a CLOSED list that stores all nodes that have been previously expanded: if a node which is about to be expanded is found in CLOSED, then it is not expanded again even if its $f$-value is larger. The reason is simple: If that node was already expanded, a shortest path cannot go through a more expansive subpath (hope you see here how the principle of suboptimal structure applies). The second contribution of A* is that all newly generated nodes are inserted in an OPEN list and they are sorted in increasing order of their $f$-value. This guarantees that no node with a $f$-value strictly larger than the cost of the optimal solution is ever expanded.

In general, both conditions are also satisfied by Dijkstra's algorithm and, from here, by any of the so called Best-first search algorithms. A* is different from those however in the design of the $f$ evaluation function which is defined as $f(n)=g(n)+h(n)$. Now, if $h(n)$ is admissible, i.e., it never overestimates the effort to reach the goal then it is non-decreasing and, from here, optimality of the solutions found can be guaranteed.

Note, however, that some nodes with a $f$-value equal to the optimal cost might be expanded by A* whereas they are not needed at all. Some works, such as EPEA tried to address this issue with the design of specific operator tables.

Hope this helps,


Interview Questions for Minimum Cost of Tasks I got this problem as an interview questions and I was blank all the way, I thought it was pressure but as I try to do it now I am still blank, anyway to solve this problem, I am blank so a solution would be more helpful than just explaining it as I am just trying to move on from this problem and do something else, more of like a review question that i can look at for the next interview prep. Thanks in advance.

Assume that you have a list of n home maintenance/repair tasks (numbered from 1 to n) that
must be done in list order on your house. You can either do each task i yourself at a positive cost
(that includes your time and effort) of c[i]. Alternatively, you could hire a handyman who will do the
next 4 tasks on your list for the fixed cost h (regardless of how much time and effort those 4 tasks
would cost you). You are to create a dynamic programming algorithm that finds a minimum cost way
of completing the tasks. The inputs to the problem are h and the array of costs c[1], . . . , c[n].

Here is an example. [1,3,5,6,7,2,1,3,1000] is the cost array by yourself. The handyman cost is 11. For any sequence greater than or equal to 4 tasks we would add handyman to do the tasks. In this case we would add handyman for 1...4, and 5....8, hence the total cost here is 23, and it is the minimum. Note that the handyman can not do less than 4 consecutive tasks.

Here are the subproblems I was given to solve:

find and justify a recurrence (with boundary conditions) giving the optimal cost for completing the tasks
O(n)-time recursive algorithm with memoization for calculating the value of the
recurrence and a bottom up algorithm

Equivalence to another question
Here is how we can find the problem in the question is basically the same as the problem in another question. Hence the answer over there can be adapted easily to this problem.
     the problem here <---> the problem over there
           home tasks <---> weekly shipments
cost c[i] by yourself <---> cost s_i * r by company A
         next 4 tasks <---> next 4 weeks
   cost h by handyman <---> cost 4c by company B
         minimum cost <---> minimum cost

For example, for cost array [1,3,5,6,7,2,1,3,1000] and handyman cost  11 here, we have the corresponding problem of $r=1$, frights by pounds[1,3,5,6,7,2,1,3,1000] and $c=11/4=3.75$.
You might want to ask why or how I can connect these two problems together. A simple reason is that I wrote the answer to the other question. Another reason is that I have been solving, modifying and creating problems about algorithms constantly. I would encourage you to try that kind of exercises from time to time.
Exercises
Exercise 1. Imagine a different backdrop of this problem.

Exercise 2. (A slight generalization) Let us have the same problem as in the question, the same list of $n$ consecutive tasks and a handyman with the following change. Besides 4 consecutive tasks of the fixed cost $h$, the handyman can also do the next 3 consecutive tasks on your list for the fixed cost of $g$, regardless of how much time and effort those 3 tasks would cost you. Find an $O(n)$-time recursive algorithm that calculates the lowest cost for completing the tasks. (This problem degenerates to the original problem if we let $g$ be sufficiently large.)
Here is the idea to solve exercise 2.
Let $dp[i]$ be the lowest cost to do tasks 1 to $i$ inclusive. The base cases and the recurrence relation for $dp[i]$ is given by the following description.

When $1 \leq i \leq 2$, you have to do all the tasks by yourself.
When $i=3$, either you do all the tasks or let the handyman does all 3 tasks.
When $i\geq 4$, the arrangement of lowest cost to complete all tasks must be one of the following ways.

You will do the last task by yourself. Complete the other $i-1$ tasks with the lowest cost.
Let the handyman do the last three tasks with cost $g$. Complete the other $i-3$ tasks with the lowest cost.
Let the handyman do the last four tasks with cost $h$. Complete the other $i-4$ tasks with the lowest cost.


Trying to break the proof of undecidability of the halting problem Posted this question on cstheory.SE where they said to go here:

  I read the demonstration of the Halting problem, it is done by
  reductio ad absurdum where the push to get to the absurd is to use the
  halting function "H(A,b)" (where A=another function, b=the A
  parameter) as its own parameter. This proofs that can't exist a
  function which takes every function including its own as parameter and
  says if it is an infinite loop or not, but doesn't proof that a
  function Z(A,b) where {A,b!=Z} (1*) can't exist.

While I deleted that question I had this answer by dkuper:

  It is easy to circumvent this problem, by giving to the functions the
  code of a different machine which computes the same function.

  Say you succeeded in building your machine computing Z(a,b) which
  works as you said. Then you still get the reductio ad absurdum, by
  feeding to this machine the code of another machine which is
  equivalent. This is always possible because for every machine M, there
  are infinitely machines M′ which behaves the same as M (i.e. halt on
  exactly the same instances). So checking that the input is not
  precisely the machine M is not enough to avoid the paradox. And
  checking that the input does not behave the same as M is impossible.

So, now, this doesn't work if we assume that the function passed as parameter has a flag (applied by the constructor) that indicates if it is the halt function.

Let's do this step by step.

"Z(A,b) where {A,b!=Z}"
I understand this to mean "just forbid input Z for algorithm Z". You can not do that. A machine that is supposed to solve the halting problem has to work on all machines, by definition of the problem. In other words, you make the assumption "Let Z be a machine that does not solve the Halting problem" -- that does not lead anywhere.

dkuper's argument is correct: you can derive the contradiction by feeding any of the infinitely many indices of the (assumed) solver of the halting problem, arriving at the same contradiction. Since this set of indices is not recursive, you can not program your machine to detect every alias.

Then the machine does not solve the halting problem anymore (see 1). Even if we had some leeway there, just assume the function that solves the halting problem for all functions but the one which solves the halting problem, and do the same proof.
And when you try to fix this in the same way, I'll get another function. And another one. There are enough of them.

In other words, your strategy of fixing one (or finitely many) special cases won't lead you anywhere. The halting problem is far too undecidable for that -- as the proof shows.


Problem Set Solutions/Interrupts & Exceptions/Problem 1 Using Tomasulo’s algorithm, for each instruction in the listed sequence determine when (in which cycle, counting from the start) it issues, begins execution, and writes its result to the CDB. Assume that the result of an instruction can be written in the last cycle of its execution, and that a dependent instruction can (if selected) begin its execution in the cycle after that. The execution time of all instructions is two cycles, except for multiplication (which takes 4 cycles) and division (which takes 8 cycles). The processor has one multiply/divide unit and one add/subtract unit. The multiply/divide unit has two reservation stations and the add/subtract unit has four reservation stations. None of the execution units is pipelined – each can only be executing one instruction at a time. If a conflict for the use of an execution unit occurs when selecting which instruction should start to execute, the older instruction (the one that appears earlier in program order) has priority. If a conflict for use of the CBD occurs, the result of the add/subtract unit has priority over the result of the multiply/divide unit. Assume that at start all instructions are already in the instruction queue, but none has yet been issued to any reservation stations. The processor can issue only one instruction per cycle, and there is only one CDB for writing results.

Can someone explain why for Instruction 1 the write happens in cycle 5 ?
It is given in the question that MUL takes 4 cycles to execute. So write  for I1 should have happened in cycle 6 ?

The question I have met in class before. I cannot add comment so I write here. Notice the note 'Assume that the result of an instruction can be written in the last cycle of its execution, and that a dependent instruction can (if selected) begin its execution in the cycle after that.' which means instead of WR in the 1st cycle after the completion of EXE, it WR in the last cycle of EXE.

E.g. The I1 starts its EXE in 2nd cycle and end in 5th cycle (2, 3, 4, 5). So I1's WR happens in the last cycle of EXE which is 5th cycle.

For the rest of the table you should fill them based on the given notes, kind of the manual of a specific processor. This is not the general case which you will encounter in other scheduler problems. Wish it helps you.


Can computation models be categorized in terms of efficiency? It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other computing systems.

Not much is said about the efficiency of such systems. Intuitively speaking, it makes sense to think that some systems are less efficient than others. Is it possible to meaningfully categorizing such systems in term of efficiency?

If your model contains a notion of "step" (which is reasonable), and consequently defines the running time as the number of computational steps, then you can define the class $P$ for your model. If you think about polynomial time as efficient (which is what we normally do, see for example the question here), then you have a definition for what is efficiently solvable in your new model. You can now ask about the differences between the classes $P_M$ (set of languages decidable in polynomial time in the new model $M$), and the regular $P$ (which relates to Turing - machines).

Now, a reasonable definition for "the model $M$ is more efficient than $M'$" would be $P_{M'}\subsetneq P_M$.

Although $P$ has the advantage that it can be defined relative to any reasonable computational model, sometimes our notion of efficiency changes depending on the context.

For example, in quantum computation (for a formal definition of the model you can look up quantum circuits or quantum Turing machines) our notion of efficiency is captured by the class $BQP$ (since we involve error probabilities, it makes sense to allow our polynomial algorithm to be wrong with small probability). Same goes for the probabilistic Turing machine (Turing machines with the additional ability to toss coins). Our notion of "efficiently computable" with respect to probabilistic Turing machines is captured by the class $BPP$.

The question whether these models are "more efficient" than the classical Turing machine, translates to whether $P\subsetneq BQP$, and whether $P\subsetneq BPP$.

Since we know factoring integers is in $BQP$ (Shor's algorithm), and we suspect that it is not in $P$, we suspect that indeed $P\subsetneq BQP$, meaning that quantum computers can decide more problems efficiently (although it has the same computational power as the classical Turing-machine).


When testing n items, how to cover all t-subsets by as few s-subsets as possible? This problem arose from software testing. The problem is a bit difficult to explain. I will first give an example, then try to generalize the problem.

There are 10 items to be tested, say A to J, and a testing tool that can test 3 items at the same time. Order of items in the testing tool does not matter. Of course, for exhaustive testing, we need $^{10}C_{3}$ combinations of items.

The problem is more complex. There is an additional condition that once a pair of items has been tested together, than the same pair does not need to be tested again.

For example, once we executed the following three tests:

A B C

A D E

B D F

we do not have to execute:

A B D

because the pair A,B was covered by the first test case, A,D was covered by the second, and B,D was covered by the third.

So the problem is, what is the minimum number of test cases that we need to ensure that all pairs are tested?

To generalize, if we have n items, s can be tested at the same time, and we need to ensure that all possible t tuples are tested (such that s > t), what is the minimum number of test cases that we need in terms of n, s and t?

And finally, what would be a good algorithm to generate the required test cases?

The block designs you want (for testing 3 things at a time, and covering all pairs) are called Steiner triple systems. There exists a Steiner triple system with $\frac{1}{3} {n \choose 2}$ triples whenever $n \equiv 1 \mathrm{\ or\ } 3$ mod $6$, and algorithms are known to construct these. See, for example, this MathOverflow question (with a link to working Sage code!). For other $n$, you could round up to the next $n' \equiv 1 \mathrm{\ or\ } 3$ mod $6$, and use a modification of this triple system for $n'$ to cover all pairs for $n$.

If you want the best construction for other $n$, the number of triples required is the covering number $C(n,3,2)$, and is given by this entry in the on-line encyclopedia of integer sequences. This links to the La Jolla Covering Repository which has a repository of good coverings. The online encyclopedia of integer sequences gives a conjectured formula for $C(n,3,2)$; if this formula holds, intuitively that means there should probably be good algorithmic ways of constructing these coverings, but since the formula is conjectured, it is clear that nobody currently knows them.

For high covering numbers, good coverings are harder to find than for $C(n,3,2)$, and the repository will give better solutions than any known efficient algorithms.


Basic second-order logic example contains a mistake? I'm reading the following course on second-order logic, by Péter Mekis :
http://phil.elte.hu/mekis/sol.pdf .
The course seems excellent, but I'm stuck on one of his first examples for showing the power of second-order logic w.r.t first-order logic.

In this example, he works on the following statement : "Santa Claus has all characteristic properties of a pedophile."
This is translated into the second-order logic sentence : ∀X ( R(X,P)→P(a) ),
where a is santa, P is the property of being a pedophile, X is a property and R tells us whether a property is characteristic of another property.
I understand this as : for all properties, if a property is characteristic of being a pedophile, then santa is a pedophile. This is obviously not what the statement says, so am I misunderstanding or should the second-order logic sentence instead be : ∀X ( R(X,P)→X(a) ), effectively meaning : for all properties, if the property is characteristic of being a pedophile, then santa has this property.

Yes, the example contains a mistake. The statement $\forall X (\mathcal{R}(X,P)\rightarrow P(a))$ is in fact equivalent to $P(a)$, under the assumption that $\mathcal{R}(X,P)$ is true for at least one $X$.

So indeed, the example should be $\forall X (\mathcal{R}(X,P)\rightarrow X(a))$, as you state. Perhaps the author would not have made this mistake if they had chosen a class of people that would be described by another letter than $P$.


Process address space separation in L1 cache of Intel hyperthreaded CPUs Since a processing core with hyperthreading enabled is presented as two or more cores to the operating system, it can run completely different processes with different, isolated virtual memory spaces. There must be a mechanism that guarantees process address space isolation. How is it done in Intel hyperthreaded CPUs with regards to L1 cache? I can think of three possibilities:

1) virtual-physical address mapping is done before L1 (could add delay to L1);

2) each virtual core has its own L1 cache (costs space on the die);

3) only different threads of the same process are allowed to be hyperthreaded (must be implemented in the OS kernel)

Or is it something completely different?

In modern Intel processors, the virtual-physical mapping is done in parallel with the lookup into the L1 cache.  There is a trick that gets the effect of doing lookups on virtual addresses, without actually having to complete the virtual-physical mapping before the cache lookup (and thus avoiding the delay you are worried about).  See https://stackoverflow.com/q/19039280/781723 and https://software.intel.com/en-us/articles/how-memory-is-accessedfor details of how they make this work.

There is only one L1 cache per physical core.  The two virtual cores on the same physical core share the same L1 cache.  See, e.g., https://stackoverflow.com/q/27797424/781723 and https://stackoverflow.com/q/32979067/781723.

Different processes can be hyperthreaded on the same physical core.

In general, you can often find answers to these questions by reading the Intel reference manuals.


Struggling to understand the symbolism around the big oh formal definition I'm struggling to understand what exactly T(n), and f(n) is in the above text:

  When we compute the time complexity T(n) of an algorithm we rarely get
  an exact result, just an estimate. That’s fine, in computer science we
  are typically only interested in how fast T(n) is growing as a
  function of the input size n.

  For example, if an algorithm increments each number in a list of
  length n, we might say: “This algorithm runs in O(n) time and performs
  O(1) work for each element”.

  Here is the formal mathematical definition of Big O:

  Let T(n) and f(n) be two positive functions. We write T(n) ∊ O(f(n)),
  and say that T(n) has order of f(n), if there are positive constants M
  and n₀ such that T(n) ≤ M·f(n) for all n ≥ n₀.

  image

  This graph shows a situation where all of the conditions in the
  definition are met.

I'm taking Tim Coughgarden course and reading his books. I'm still in the beginning and I can understand the explanations, but sometimes I struggle to understand the mathematical meaning of things... there are some implicitly about what is T(n) or f(n) (in this case) that is not explained at all.

T(n) is a function that has been conceived in a effort to describe the behavior of a program. There are many other possibilities, but that should be the case, in the context of computer science.

That doesn't mean we will actually write T(n) down, because i) it can be too complicated, and ii) it is probably not essential to do so.

Then comes f(n), which is another function. It indicates a set of functions, to which T(n) belongs, denoted by O(f(n)). Now, that doesn't say much about f(n), but we can use this construct to divide the universe of functions in categories, each one corresponding to a different f(n), chosen from a list of "archetypal" functions.

The definition of O(f(n)) may seem tricky, but it is consistent, and general, which is important if you're going treat the subject scientifically.

This division has immense practical benefits, since it gives us a language to talk about the behavior of programs in a way that is both precise and meaningful. Each of these function categories has functions that have something important in common, in the way that they grow.

The notation has limits, of course. It's not the only tool in our belt.


Reccurrence for the game of pile of stones I am trying to solve this question from Project Euler for past few days: Divisor game.
The problem is as follows:

  Two players are playing a game. There are $k$ piles of stones. When it is his turn a player has to choose a pile and replace it by two piles of stones under the following two conditions:
  1.Both new piles must have a number of stones more than $1$ and less than the number of stones of the original pile.
  2.The number of stones of each of the new piles must be a divisor of the number of stones of the original pile.
  The first player unable to make a valid move loses.
  Let $f(n,k)$ be the number of winning positions/configurations for the first player, assuming perfect/optimal  play, when the game is played with $k$ piles each having between $2$ and $n$ stones (inclusively). Then find $f(10^7,10^{12}).$

What I tried

The first thought upon seeing the number of piles to be $10^{12}$, is that somehow matrix exponentiation is involved, with a linear recurrence being obtained on the number of piles $k$ for some fixed $n$.
The second thing which can be observed is that if I have $k-1$ piles of stones with each pile having stones between $2$ and $n$. And this  configuration is denoted by $S_{k-1}$, then if I have two numbers $a=q_1^{r_1}q_2^{r_2}...p_x^{r_x}$ and $b=s_1^{t_1}s_2^{t_2}...s_y^{t_y}$ ( where I have written the prime factorization of $a$ and $b$ ) such that $r_1+r_2..+r_x=t_1+t_2..+t_y$ then either both the configurations $S_{k-1}a$ and $S_{k-1}b$ are loosing configurations or both are winning configurations ( where $S_{k-1}a$ means I have added a pile with $a$ stones to the configuration $S_{k-1}$ ).
Based on the the above two points I tried the following approach. Let $L_{k-1}$ and $W_{k-1}$ be the number of loosing and winning configurations respectively, where each configuration has $k$ piles, with each pile having between $2$ and $n$ stones ( inclusive ). Also let $P$ and $C$ represent a prime and a composite number respectively, between $2$ and $n$ ( inclusive ).
Then it is easy to note the following:
$L_{k-1}P$ is a losing configuration with $k$ piles, last pile having $P$ stones.
$W_{k-1}P$ is a winning configuration with $k$ piles, last pile having $P$ stones.
$L_{k-1}C$ is a winning configuration . The reason is: as $C$ is a composite number it has a prime divisor $p$. The first player chooses the last pile ( $k$th pile ) having $C$ stones and replaces it with two piles each having $p$ stones. Now its the second players chance and he is left with configuration $L_{k-1}$ which is loosing configuration ( the second player can't choose the two newly form piles as they cannot be broken down further as they have prime number of stones ).
The problem comes here as $W_{k-1}C$ can be a winning or a loosing configuration. For example let $k=2$ and $n=10$ then it can be seen that a single pile having $4$ stones is a winning configuration. And also it is easy to see that $\{4,4\}$ is a loosing configuration whereas $\{4,8\}$ is a winning configuration ( where $\{4,8\}$ means two piles, first having $4$ stones and second having $8$ stones). So I am unable to move forward in this case.

I still suspect it is a matrix exponentiation question. But I guess it cannot be done just keeping variables $W_{k-1}$ and $L_{k-1}$. How do I proceed ?

PS: As this problem is from project Euler I would appreciate only hints.

AS I asked for hints only, apart from the hints I have provided one can solve the question with grundy numbers.


Finding MST for connected graph with $|E|=|V|+87$ Given $G=(V,E)$ undirected, connected graph and weights given by $w:E \to \mathbb R$. We also know that $|E|=|V|+87$.

Find Minimum spanning tree of $G$.

Obviously we can use Prim in $O(|V| \cdot \log |V|)$.

But can we do better by using the fact that the graph is connected, and use the sets sizes? Like removing the lightest edge from each cycle and keeping the connectivity of the graph?

The "Cycle Property" helps (If you don't know it before, try to prove it first):

  Let $C$ be any cycle in $G$ and $e$ a heaviest (not necessarily unique) edge in $C$. Then there exists some MST which does not contain $e$.

You are encouraged to answer the following questions:

How to identify a cycle and then a heaviest edge $e$ in it?
What to do with the edge $e$?
How many times should you apply the cycle property?
When to stop?

Then analyze the time complexity.


How to minimize the average distance between pumps and cities? There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k cities. The cities are all in a straight line.

How do I need to install these so that the average distance between the cities and the nearest pumps is minimized?

What I am thinking is that dividing is this:

Suppose there are 6 cities [C1, C2, C3, C4, C5, C6]  and 3 pumps [P1, P2, P3].

I divide the array of cities equally -> [C1, C2] , [C2, C3] .. and then each block gets one pump.

Then again break that [C1,C2] and let C2 have the pump. Same way C4 and C6.

So basically recursively calling and assigning the city a pump. Is this the right way to approach this problem?

Minimizing the average distance is equivalent to minimizing the sum of the distances, so let me work with that formulation of the problem.

Hint #1: When $k = 1$, the pump should be located at the median of the positions of the cities.

Hint #2: When $k > 1$, you can use a dynamic programming approach.
Let $f(i, j)$ be the optimal cost of serving cities $1,...,i$ with $j$ pumps. Your goal is to compute $f(n, k)$. Now observe that $$ f(n,k) = \min_{i=1,...,n} \left( \sum_{i': i < i' \le n} d(\text{city}_{i'}, \text{pump}_k) + f(i,k-1) \right), $$
because if the rightmost pump (pump number $k$) serves cities $i+1$ through $n$, then the total cost is the sum of distances of those cities to pump $k$, plus the optimal cost of serving cities $1$ through $i$ with $k-1$ pumps. Here $\text{pump}_k$ is the position at the median of cities $i+1,...,n$.


Classifying objects by set proximity The project I'm working on has a number of objects arranged in overlapping sets. I need to classify them by whether they have a trait or not, using pre-classified objects that they are connected to (through shared set membership). I.e., the objects within the same set are likely to share whether they have that trait. The training data only consists of whether some objects have the trait or not.

To illustrate by example:

Green and red circles represent pre-classified objects (with having and not having the trait respectively). White circles are unclassified.
Objects A, C, D and E are likely to have the trait, and thus should have a positive score, because they are in common sets with other objects which are known to.
A should have a better score than C because there is more certainty (C's unclassified neighbor might or might not have the trait).
Similarly, D should have a higher score than A.
E is likely to have the trait because all of its neighbors are.
F and G should have a neutral score, because we don't know anything about F, and G has equally conflicting information.

I'm looking to sort all unclassified objects by score (likelihood to have the trait), which in this example would roughly be D, A, E, C, F, G, B, or at least get the top N objects with the highest score.

My set size is about 50 million objects across 10 million sets. The training size set (number of pre-classified objects) can vary from 1 to a few thousand. The objects are pretty well connected - the biggest "connected subgraph" contains 90% of all objects.

One powerful and general approach is to write a probabilistic model that describes how colors are chosen, then apply maximum-likelihood estimation.  The probabilistic model provides an expression for $p(x)$, where $x=(x_1,\dots,x_n)$ and $x_i$ is a random variable that describes the color of the $i$th object.  You are given an observation for some of the $x_i$'s, namely, the color of the pre-classified objects, and want to infer the color of the rest.  This can be done by finding a vector $x$ that maximizes the value of $p(x)$, subject to the requirement that it be consistent with the observed colors.  You then apply some mathematical optimization routine to find $x$ that maximizes $p(x)$, subject to the constraint that $x$ is consistent with the observations.

This requires that you supply a model for how colors are generated.  Only you can provide that, since that depends on the specifics of your application domain and the random process underlying your observations.

One possible approach is to model this as a Markov random field.   Build an undirected graph where the vertices are the objects; add an edge $(u,v)$ between two objects $u$ and $v$ if $u,v$ are in the same cluster.  Then the Markov random field assumption says that $p(x)$ is proportional to

$$\prod_{(u,v) \in E} q(x_u,x_v),$$

where $q(\cdot,\cdot)$ is some function $q:\{\text{red},\text{green}\}^2 \to [0,1]$.  For instance, you might take $q(c,d) = 0.99$ if $c=d$ and $q(c,d)=0.01$ if $c\ne d$.  That defines a Markov random field.  There are algorithms for maximum-likelihood inference for Markov random fields.  (In particular, as a starting optimization, you can decompose the graph into connected components and solve the problem separately for each connected component.)

Another possible model would be a hierarchical model, where we first pick a color at random for each cluster, then randomly pick a color for each object based on the color(s) of the cluster(s) it is contained in.  Suppose there are $m$ clusters, and let $w=(w_1,\dots,w_n)$ where $w_i$ is a random variable describing the color of the $i$th cluster.  We might imagine that the $w_i$ are independently uniformly distributed.  Then, we might imagine that we pick a color $x_j$ for object $j$ based on the values of $w_i$ for each cluster $i$ that contains object $j$.  In particular, we might imagine that the conditional probability distribution $p(x|w)$ is proportional to

$$\prod_{j=1}^n \prod_{i \text{ s.t. } j \in i} p(x_j|w_i),$$

where we define $p(x_j|w_i) = 0.99$ for $x_j=w_i$ and $p(x_j|w_i)=0.01$ if $x_j \ne w_i$ (say).  Using the fact that $p(x,w)=p(x|w) \cdot p(w)$ and that $w$ is iid uniform, we obtain that $p(x,w)$ is proportional to

$$2^{-m} \prod_{j=1}^n \prod_{i \text{ s.t. } j \in i} p(x_j|w_i).$$

We can then try to find $x,w$ that maximizes $p(x,w)$, subject to the constraint that $x$ be compatible with the observations (the pre-classified objects).  This could be done by mathematical optimization.  Again, as an optimization, you can decompose the problem into independent subproblems through a connected component decomposition (consider two objects in the same component if they are members of the same cluster).

It is also possible to obtain confidence scores through "marginalization": if you can compute $p(x_i|y)$ where $y$ denotes the observed colors of the pre-classified objects, then this serves as a confidence score for the inferred color of object $i$.

There are other models that might be appropriate.  We can't tell you which one is most suitable for your application domain, but once you choose one, you can work out how to apply the maximum-likelihood maximization principle to it.


showing that the pair of Finite Automata are equivalent Here I am trying to show that the pair of Finite Automata are equivalent. I have tried something but I am not sure if I am in the right direction. This is what I have.

These are pairs of FA's. Set theory formula in here is (L1' + L2)' + (L2' + L2)'

Conclusion:

  Both machines (FA1'+FA2)' and (FA2+FA1)' has no final states.
  (FA1'+FA2)' to have a final state, the machine (FA1'+FA2)' must have
  no final state. The exact same thing half of the formula. Clearly, if
  we added these machines together we would get a machine with nine
  state and no final state. Because there is no final state, it accepts
  no words and two languages L1 and L2 ar equivalent.

  So the two regular expressions defame the same language and
  equivalent.

Am I in the right direction ?

Your approach works. You are effectively showing that the symmetric difference $L(FA_1) \Delta L(FA_2)$ is empty, hence $L(FA_1) = L(FA_2)$.

A more direct, automaton-level approach would be to build the following product automaton $A = (Q, \Sigma, \delta, q_0, F)$:

$Q = Q_1 \times Q_2$
$\delta((q_1, q_2), a) = (\delta(q_1, a), \delta(q_2, a)) \ \forall (q_1, q_2) \in Q, a \in \Sigma$
$q_0 = (q_{0,1}, q_{0,2})$
$F = \{(q_1, q_2) \in Q \mid q_1 \in F_1 \Leftrightarrow q_2 \in F_2\}$

Intuitively, you keep in mind the current state in both $FA_1$ and $FA_2$. Initially, the current states are the respective initial states $q_{0,1}$ and $q_{0,2}$. Then, for each input symbol $a$, you move to the respective successor in each automaton, and note the successor state (the combination of the two successor states as a pair). Of course you only draw the state for each combination only once. You can proceed either breadth-first (considering all input symbols for one product state before moving on to a newly introduced state) or depth-first (always continue with the newly introduced state and backtracking if all product successor already existed).

Note that this way you might not have to construct the full product set $Q_1 \times Q_2$, as you automatically prune unreachable states (you don't ever introduce them). However, the product automaton in your example will have no more than 6 states anyway, so it is rather small.


Is there a Data Structure like Binary Decision Diagrams for Non-Binary Functions Binary Decision Diagrams (BDD) take a set of binary variables $x_1, x_2,..., x_n$ as input.
Is there a data structure similar to BDDs where each variable takes more than two values? Each variable's values should be independent of every other variable. For example, $x_i$ could be assigned the three values $\{0,1,2\}$ and $x_j$ could be assigned the four values $\{0,1,2,3\}$, where $i \ne j$.

Yup.  A BDD is just an acyclic finite-state automaton (DFA) that accepts a language $L \subseteq \{0,1\}^n$.  It represents the function $f(x)= 1$ if $x \in L$ or $f(x)=0$ if $x \notin L$.

You can generalize this to allow an acyclic finite-state automaton over a language over a different alphabet, or indeed, a language $L \subseteq \Sigma_1 \times \cdots \times \Sigma_n$ where $\Sigma_i$ is the set of valid values for $x_i$.  Everything carries over.


Enumeration of winning coalitions Taken from Wikipedeia:

A simple voting game, taken from Game Theory and Strategy by Phillip D. Straffin:
[6; 4, 3, 2, 1]
The numbers in the brackets mean a measure requires 6 votes to pass, and voter A can cast four votes, B three votes, C two, and D one. The winning groups, with bolded swing voters, are as follows:
AB, AC, ABC, ABD, ACD, BCD, ABCD

Using a non-trivial structure, we know that ABCD will always be a member of the set of winning groups. Also, we know that if AB is a winning group, then ABC and ABD are also winning groups. In other words, the set of winning groups AB, ABCD is invalid. Thus, any member of the set, besides ABCD, can be constructed by removing a single element from another set in the group. (Edit: While this is true, it gives the wrong impression.)
In the beginning, the goal was to generate the set of possible winning groups for a given number of players. Using three players as an example, the set of winning groups is:
{1, 2, 3}

{1, 2, 3}, {1, 2}
{1, 2, 3}, {1, 2}, {1}
{1, 2, 3}, {1, 2}, {2}
{1, 2, 3}, {1, 2}, {1}, {2}

{1, 2, 3}, {1, 3}
{1, 2, 3}, {1, 3}, {1}
{1, 2, 3}, {1, 3}, {3}
{1, 2, 3}, {1, 3}, {1}, {3}

{1, 2, 3}, {2, 3}
{1, 2, 3}, {2, 3}, {2}
{1, 2, 3}, {2, 3}, {3}
{1, 2, 3}, {2, 3}, {2}, {3}

{1, 2, 3}, {1, 2}, {1, 3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}
{1, 2, 3}, {1, 2}, {1, 3}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {2}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}, {3}

# and so on...

This is doable through a relatively simple algorithm as thankfully offered here.
(Edit: That algorithm does what was requested, but, per my oversight, generates false positives, e.g. {{1, 2}, {1, 3}, {1, 2, 3}, {1, 2, 3, 4}}.)
However, I want to only generate one set per "isomorphic group." For example, the sets {1, 2, 3}, {1, 2} and {1, 2, 3}, {1, 3} are the same if we swap the labels of 2 and 3. This is the primary goal.
The secondary goal is to only generate the sets of winning groups that could be realized through a voting structure. Using a four player system and a maximum of 20 votes per person, I found sets of winning groups that satisfied the above criteria, but could not be realized. (Edit: See previously mentioned false positives and the answer below.)

You are asking two questions:

How to count "winning groups" up to isomorphism?
Which winning groups are realizable as winning coalitions?

From the point of view of winning groups, we can assume that each voter always casts all her votes, and the resulting games is known as a weighted voting game.

Counting winning groups

Your concept of "winning group" is a same as a monotone Boolean function or an upset. The number of monotone Boolean functions up to permutation is enumerated in the sequence A003182, and grows pretty quickly. For $n=7$ the number is already pretty large: 490,013,148. It's probably not too helpful to list all of them. It is even non-trivial just to calculate the number, see this paper.

You can find all the 16351 non-constant monotone Boolean functions for $n=6$ listed here as sets of minterms, which are (in your parlance) minimal winning coalitions. The minterms form what is known as an antichain, a collection of sets none of which is a subset of another.

Which winning groups are achievable?

Let $S_1,S_2$ be two sets of voters. A swap consists of taking some $x \in S_1 \setminus S_2$ and some $y \in S_2 \setminus S_1$, and forming the new sets $S_1 - x + y, S_2 - y + x$ (that is, we exchange two voters, taking care not to have the same voter twice in any of the sets). Given several sets $S_1,\ldots,S_k$ of voters, a trade is the result of applying arbitrarily many swaps, resulting in a new $k$-tuple $T_1,\ldots,T_k$.

(Alternatively, $T_1,\ldots,T_k$ is a trade of $S_1,\ldots,S_k$ if the multisets $S_1 \cup \cdots \cup S_k$ and $T_1 \cup \cdots \cup T_k$ are the same.)

Let $W$ be a set of "winning coalitions". We say that $W$ is trade robust if whenever $S_1,\ldots,S_k \in W$, in any trade $T_1,\ldots,T_k$ obtained from $S_1,\ldots,S_k$ at least one of the $T_i$ is in $W$. It is easy to see that every set of winning coalitions arising from weighted voting games is trade robust (exercise). Amazingly, Taylor and Zwicker showed that the converse holds as well.


Find a $\log_2(|V|)$ long cycle where each node is of different color Here's a question from an algorithms exam by Prof. Noga Alon that I just can't wrap my head around.

Let $G=(V,E)$ be a directed graph where $|V|=n$. Let $k=\lfloor \log_2(n)\rfloor$. Each node in the graph is in one of $k$ colors. Give an efficient algorithm to determine if there exists a simple cycle of length $k$ in the graph where each node has a different color.

I really don't know where to start with this. I thought about breaking the graph into subsets of nodes of each color and having multiple copies of each subsets in order to force a color change with every edge we traverse but I couldn't get this to work. Any hint is appreciated!

The idea is to use dynamic programming. For every pair of vertices $x,y$ and subset $S$ of colors, you determine whether there is a path from $x$ to $y$ of length $|S|$ (measured in vertices) which uses all colors in $S$, each of them exactly once.

What is this good for? Usually our graphs are not colored. The idea of color coding is that finding cycles (and other structures) is much easier if vertices or edges are colored: instead of having to remember all vertices visited in the cycle being constructed, it suffices to remember the colors encountered. Therefore we need to introduce the colors into our graph. How do we do that? In the simplest possible way: randomly.

Suppose that we want to find a directed cycle of length $k = \ln n$ in a directed graph. We color the vertices of the graph randomly with $k$ colors. If there is a directed cycle of length $k$, then the probability that all of its vertices are colored with different colors is $k!/k^k \approx e^{-k} = 1/n$. Therefore if we try (say) $n\log n$ different random colorings, then it is highly likely that one of these colorings would color the vertices of the cycle with different colors. When that happens, the dynamic programming algorithm outlined above will find the cycle. Conversely, if there is no directed cycle of length $k$, then no coloring would confuse us.

All in all, we obtain a randomized algorithm, running in polynomial time, that finds a cycle of length $k$, if one exists, with high probability.


Running time analysis of a segment tree Can someone provide an analysis of the update and query operations of a segment tree?

I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and right sub-trees. If we could prove that one of these calls terminates fairly quickly, the time complexity would be logarithmically bounded. But how do we prove this?

Those are my lecture slides, so I figured I'd chime in. :-)

The idea is to split apart the recursive calls being made into two different classes: recursive calls where the range being searched is the entire range of a node and recursive calls where the range being searched corresponds to just a part of the range. One of the observations you can make is that if you do a range search on a segment tree, after the initial split made in the recursive call, every recursive call made either spans the entire range given by a node or corresponds to a subrange that's flush up against one of the sides of the range given by a node.

As an optimization in a segment tree, any recursive call that's made for a range that completely spans a node doesn't do any further recursion; it just returns the cached value and stops. Therefore, the only recursive calls that fire off more recursive calls are ones where the range searched is flush against the side of the range spanned by a node. If you look at what happens in that case, you'll see that every recursive call made from that point either is over a full range (in which case it doesn't really count as a recursive call; we can charge that work back to the initial recursive call) or is to a flush against the side range. This means that while the recursion does indeed branch, one of those branches always immediately ends. Therefore, the work done obeys the recurrence

  T(n) = T(n / 2) + O(1)

where that O(1) term counts both the work for the recursive call and the (up to) one recursive call made on a full range, which terminates immediately. That solves to O(log n), as required.

Hope this helps!


Church numerals without functions This is really a second part to my first question, but I felt that this was different enough from the first part that it merited its own question.

So, using Church numerals, we define

$3 = {\lambda} f. {\lambda}x.f(f(f(x)))$,

and

$4 = {\lambda} f. {\lambda}x.f(f(f(f(x))))$.

We can then add with an expression like

$3\ g\ (4\ g\ z)$

And this reduces to:

$(g (g (g (g (g (g (g\ z)))))))$.

But, of course, this is not how we would define $7$ in the scheme above.  $7$ would be

${\lambda}g.{\lambda}z.(g (g (g (g (g (g (g\ z)))))))$.

Why is it still legitimate to call the application $3\ g\ (4\ g\ z)$ "7" when we can no longer perform functions with it?

This is just a shorthand, leaving off some things that aren't really needed to understand the concepts. If you want your $7$ to be written as a function again, all you need are a couple more implicit lambdas. Here's how I'd write the Church addition with those lambdas in place:

$$3 + 4 = \lambda g . \lambda z . 3 g (4 g z) = \lambda g . \lambda z . 7 g z$$

But we also know that:

$$\lambda k . f k = f$$

Therefore:

$$\lambda g . \lambda z . 7 g z = 7$$


Is the language of palindromes context-free? Is the language $\{ w=w^R \mid w \in \{0,1\}^* \}$ a context-free language?

I am confused in deciding whether the language is context-free or not, that is one of my problems, I do a pumping lemma proof and what I get is that it is not a context-free language, but I want to make sure again.

The language of palindromes is one of the standard examples of a non-regular context-free language. It is generated by the context-free grammar
$$
S \to 0S0 \mid 1S1 \mid 0 \mid 1 \mid \epsilon
$$


Simple algorithm for listing all 6-cycles in a directed graph What's an easy-to-program way of listing all 6-cycles in a directed graph? I've done some reading on the general case of even cycles, but it's rather complicated. I found a really neat approach for 4-cycles, in this post, and I was wondering if there's something similar for 6-cycles.

My graph isn't that big (maybe a few hundred nodes) so I'm not too worried about computation time.

The easiest-to-program method will probably be a straightforward for-loop.  In particular, for each combination of six vertices $v_1,v_2,\dots,v_6 \in V$, check whether the following conditions all hold:

the $v_1,v_2,\dots,v_6$ are all distinct
$(v_1,v_2) \in E$ and $(v_2,v_3) \in E$ and ... and $(v_5,v_6) \in E$ and $(v_6,v_1) \in E$.

If all the conditions hold, then you've found a cycle.  Output it.  Repeat for each possible combination of vertices.

The running time of this method is $\Theta(|V|^6)$.  It is easy to see that in the worst case there can be $\Theta(|V|^6)$ different cycles (consider a complete graph), so any algorithm will have to take at least this long on some graphs.

You can also get a very easy-to-program algorithm with running time $\Theta(|E|^3)$.  Enumerate all triples of edges $(v_1,v_2), (v_3,v_4), (v_5,v_6) \in E$, and then check the following conditions:

the $v_1,v_2,\dots,v_6$ are all distinct
$(v_2,v_3) \in E$ and $(v_4,v_5) \in E$ and $(v_6,v_1) \in E$.

If all the conditions hold, you've found a cycle; output it

This algorithm has $\Theta(|E|^3)$ running time.  Again, it's easy to see that there exist graphs where there are $\Theta(|E|^3)$ cycles and thus any algorithm will need to take at least $\Theta(|E|^3)$ time.

Both of those algorithms are easy to program.  That doesn't mean they are necessarily optimal in running time.  One could hope for an output-sensitive algorithm whose running time is a function of the number of 6-cycles as well as of $|V|,|E|$.  I suspect there are more complex algorithms that might have better asymptotic running time, for some graphs, when considering all three of those parameters.  However, they will be much more complex to program.  Therefore, by your stated goal of "easiest-to-program", I recommend one of the two algorithms listed above.


Are all foldable data structures also recursive? I was checking what Wikipedia has to say on reduce. It says:

  In functional programming, fold (also termed reduce, accumulate,
  aggregate, compress, or inject) refers to a family of higher-order
  functions that analyze a recursive data structure and through use of a
  given combining operation, recombine the results of recursively
  processing its constituent parts, building up a return value.

This raises the question: Are foldable data structures always recursive (or can be seen as such)?
This is obvious for things such as lists and trees (in Haskell):

data List a = Nil | Cons a (List a)

data Tree a = Empty | Node (a, Forest a)

data Forest a = Nil | Cons (Tree a) (Forest a)

In other words, are all iterable data structures also recursive?*
How would one go about proving this?

*I'm assuming that being iterable is sufficient to be foldable.

No, not all foldable data structures are recursive, although the in the non-recursive case what we have is really a degenerate version of a fold.

For example, we can view the function if : Bool -> a -> a -> a as a fold over the type Bool.

In general, when dealing with recursive or non-recursive types, the fold are called eliminators, since they are how we consume values of a given datatype. Eliminators are particularly interesting for dependent types and indexed type families, where the eliminator corresponds to an induction principle for that data type. See this paper for more info on this.

Eliminators always terminate, which means that if you have only eliminators (in place of general recursion) you will not be Turing Complete. You can even encode a data structure as its eliminator, using something called Church Encodings. Using this, you can write lists and other data types in a language that only has functions, like System F.


Is this algorithm for Exact Three Cover sub-exponential, because I find $length(s)/3$ combinations for $C$? Given an input $S$ (set of elements) find an exact three cover for a list of 3-element sets named $C$.
$S$ = 1,2,3,4,5,6
$C$ = [1,2,3],[4,5,6],[3,1,2]
Algorithm
1.Sort list and delete occurrences of sets that repeat in $C$.

(eg. $[1,2,3]$ repeats because of $[3,1,2]$. Of course leave one of
the sets.)

2.Remove sets that have elements that do not exist in $S$.

(eg $[1,2,9]$... $9$ does not exist in $S$)

3.Remove sets with repeating elements.

(eg. $[1,2,2]$ is deleted from $C$)

4.Remove repeating sets

(eg. $[1,2,3]$ and $[1,2,3]$ but leave $[1,2,3]$)
After $C$ has been sorted; the worst-case length of $C$ will be
$\frac{lenght(s)!}{\left(3!\left(length(s)-3\right)!\right)}$

5.Use $length(s)$/$3$ for $K$ combinations of $C$.

(eg. there will be $2$ sets required for an Exact Three Cover of
$S$ $[1,2,3]$,$[4,5,6]$)

It seems the number of combinations will be < $2$^$\frac{lenght(s)!}{\left(3!\left(length(s)-3\right)!\right)}$ at least most of the time.
Question
Is this algorithm sub-exponential at least on average?

No. Exponential time is sometimes used to mean running times in $2^{\Theta(n)}$, and other times it is used to mean running times in $2^{\Theta(n^k)}$ for some constant $k>0$.

Your algorithm is exponential w.r.t. the second definition and superexponential w.r.t. the first.
In fact your algorithm takes time $2^{\Theta(n^3)}$, where $n = |S|$ (notice that $\frac{n!}{3! \cdot (n-3)!} = \frac{n(n-1)(n-2)}{6} =\Theta(n^3)$).


Given a graph, finding if a node has three adjacents from a node subset $N$ Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \{n_1, n_2 ...\} \subset V$ and $P = \{p_1, p_2, ...\} \subset V$ such that $N \bigcup P \neq V$.

I want to find if there exists an edge subset such that $\{<n_i,p_l>, <n_j,p_l>, <n_k, p_l>\}$ i.e. three nodes from $N$ and one node frpm $P$.

Should I first list the triplets of $N$ and search if they have a common adjacent in $P$ or for each $p \in P$, check if $p$ has three adjacents in $N$?

Which method would be more efficient? Or does it depend on the sizes of the sets?

Edit:
What if I want to list all the edge subsets for all $p_l$?

To find such triples of edges, partition the adjacency list $L_i$ of each node $p_i$ in $P$ into three sets: $P_i$, the set of neighbors in $P$, $N_i$, the set of neighbors in $N$, and $Q_i$, the set of neighbors in $V \setminus (N \cup P)$. If each vertex is labeled with which set it belongs to, then the partitioning can be accomplished in linear time. Then, for each $p_i$, check if $P_i$ contains at least 3 vertices. If so, then you have an edge subset that meets your requirements.

If you want to generate all possible edge subsets of the outgoing edges in each node, you would be generating the powerset of the neighbors of $p_i$. If a vertex has $n$ neighbors, the size of the powerset will be $2^n$. This strategy is impractical for all but the smallest input graphs.

If you only want to list the edge subsets from each $p_i$ that meet your requirements, the number of subsets for a vertex with $n$ neighbors in $V$ will be ${n \choose 3}$, but the algorithm to enumerate them should not be complicated.


Radix, merge, counting sort and when to use Okay can't figure this out. I want to make sure I understand it.
There are n random keys each being float numbers with p decimal places.
So, for example,
123.456,

343.645,

234.543,

863.238,

956.043,

etc.

For which values of p should you use counting sort, radix sort, and merge sort to make it the fastest.
I know counting sort runs O(n+k), radix runs O(d(n+k)), and merge is O(n) in its best case.
Also, I *think when sorting with decimals you first multiply each by 1000 (in this case) to make them whole numbers, correct? Or is that wrong?
Any and all help would be appreciated.

The idea seems wrong at its core. The missing parts are: what is the distribution and range of the data. How many items do you have? (You may not know this in advance, but it renders some algorithms useless).

The counting sort works well when the range is compact, it gives good memory requirements and the mere array traversal is not computationally expensive. In the case of floating-point numbers, when you multiply decimal part to make full integers the range may be huge, in that case $n$ may be small but $k$ is huge.
Instead of multiplying them out the better idea is to round them and store only decimal part. This idea would not blow up the range and after counting you are left with small bins to sort. To give more or less answer to $p$ parameter, it really depends on scarcity of data and number, but say, if you really want to multiply them by $10^p$ in many cases for $p \ge 3$ it seems like bad idea.

The radix sort depends on $d$ which is the number of digits, here it doesn't matter where is the decimal point, but with bigger $p$ the $d$ is bigger, which kills the performance (unless bigger radix is used for decimal part only).

Merge sort, the natural variant, is $\mathcal O(n)$ but this property is not that important to choose, it effectively says that the algorithm terminates sorting early when it gets sorted data. The best case for sorting (when applicable by algorithm properties) must be $\Omega(n)$ to at least read the input and check whether consecutive numbers obey order.
Merge sort runtime does not depend on $p$, as far it is some built-in type, unless the float is stored as the string, but this on its own may be problematic and performance killer. The access to decimal digits in case of some floating-point number requires conversion, which takes time or additional memory.

To choose sorting algorithm the first step is to match inherent properties with data, use (or add if you have to) properties like stability of sorting, understand what asymptotic notation mean, look at average case and test with your real data.

Why $n$ is important here? Because if it is small (10-20) Bubble sort is faster on average than other algorithms (short of counting sort with extremely tight range), because it has small hidden constant and for non-artificial data it does rarely encounter bad case. The situation gets more complicated when actual data is bigger, but in the case of smallish data, say 1000 – 20000 items, the hidden constant still matters.

For data in your format (3 digit decimals with $p$ decimal places) if you know distribution, it may be beneficial to use distribution sort or counting sort, rounding numbers beforehand. Back to your question, the decision to select one of given algorithms doesn't solely depend on $p$.


Reference asking: phase transition in SAT This is not a technical question, I hope this community has a room for such questions, but I will delete it in case this is inappropriate.

It has been experimentally observed (e.g. here) that when choosing a $3$-SAT formula by the following process:

On input $(n, \alpha n)$: choose $\alpha n$ clauses uniformly at random from the set of all clauses of $3$ literals over $x_1, \ldots, x_n$, and return the conjunction of these clauses.

The probability that the outputted formula is satisfiable depends on $\alpha$: if $\alpha \ll c$ the probability is very close to $1$, and if $\alpha \gg c$ the probability is very close to $0$ (it has been observed for a general $k$-SAT instances).

My question is what is the theoretical understanding of this problem? To the best of my knowledge, for other  problems it is possible to prove similar claims quite easily (e.g. the probability that a random graph $G(n,p)$ has a clique of size $4$ is almost $1$ when $p(n) = \omega(n^{-2/3})$ and is almost $0$ when $p(n) = o(n^{-2/3})$, and it can be proven by a basic use of second moments).

However, for SAT I couldn’t find proofs. Do you know of any progress in this problem?

The two most relevant rigorous results are:

Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-SAT problem. This paper (with an appendix by Jean Bourgain) shows that $k$-SAT exhibits a sharp threshold. However, a priori this threshold could depend on $n$ (i.e., this method cannot show that $\alpha$ is constant).
Jian Ding, Allan Sly, Nike Sun, Proof of the satisfiability conjecture for large $k$. The authors determine the exact value of $\alpha$ for $k \geq k_0$. This value of $\alpha$ had been calculated by physicists using the cavity method, but their arguments are not rigorous.

Related work discusses the geometry of the solution space of $k$-SAT around various thresholds. See for example Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi, On the solution‐space geometry of random constraint satisfaction problems.


Can the set of all $2^{24}$ colors be expressed as a ternary linear code? Consider the usual RGB color palette, for which each color (red, green, blue) has $256$ distinct intensities. Can the set of all $2^{24}$ colors be expressed as a ternary linear code? If so, give a basis. If not, explain why not.

I'm confused on how to solve this because I've only worked with binary linear codes. Can somebody please walk me through it?

Hint: The number of codewords in a ternary linear code is a power of 3.

That's my best guess for the answer that the setter expects. However, the truth is you can certainly use a ternary linear code to represent all colors, you will just have a little redundancy.


Difference between Tail-Recursion and structural recursion Is there any difference between structural-recursion and Tail-recursion or they both are same? I see that in both of these recursions , the recursive function is called on the subset of the orignal items.

Structural recursion: recursive calls are made on structurally smaller arguments.
Tail recursion: the recursive call is the last thing that happens.

There is no requirement that the tail recursion should be called on a smaller argument. In fact, quite often tail recursive functions are designed to loop forever. For example, here's a trivial tail recursion (not very useful, but it is tail recursion):

def f(x):
   return f(x+1)

We actually have to be a bit more careful. There may be several recursive calls in a function, and not all of them need to be tail recursive:

def g(x):
  if x < 0:
    return 42             # no recursive call
  elif x < 20:
     return 2 + g(x - 2)  # not tail recursive (must add 2 after the call)
  else:
     return g(x - 3)     # tail recursive

One speaks of tail recursive calls. A function whose recursive calls are all tail-recursive is then called a tail-recursive function.


Is it possible to implement dependent types by any object oriented language supporting inheritance and classes? When I was reading Agda tutorial, I noticed resemblance between dependent type declarations and class definitions which I've been primarily used to work with. I'm not totally sure how much sense this questions makes, but what is the real practical difference between types and classes? Could we very well use object oriented approach to define types, and thus construct proofing system similar to Agda by any language supporting class and object construction?

So, things like this are possible, but the usefulness varies depending on your system.

First, you can absolutely model object oriented programming in a functional, formal setting. System F-sub is the classic example of this, but Scala Dependent Object Types are another model.

Secondly, let's talk about the difference between types and classes, without dependent types. A class is essentially just a type, combined with a bunch of methods that operate on that type. Classes can be modeled with recursive record types in some languages. The algebraic data types you see in languages like Haskell and Agda are kind of like regrouped classes. An interface groups functions together, and the type specific implementation of those functions for specific classes are spread out. Conversely, algebraic data types group all the variants of a type together, but the different functions are spread out, with each function specifying how it is implemented for each type.

Finally, how do dependent types play into all this? Well, Agda and other Dependent Type languages have a particular feature, namely that types can be indexed by values, and that types are themselves values. Computation can happen not just in expressions, but in types.

Java, Haskell, and every other mainstream language are weaker than this, since their types can't be indexed by arbitrary values. This is what the dependent in dependent types means, and it's what makes them useful for proving things.

To have dependent object oriented types, you need to overcome a few hurdles. One is, do you have mutation, and how does it affect dependent types? Can types refer to mutable variables, or alter state? How is that possible, when type computation happens at compile time, not runtime?

And then you need to decide whether you want to prove actual theorems in your language. Most OO languages are Turing Complete, meaning that the would be inconsistent if interpreted as a logic. This doesn't mean that Dependent types are useless, you can still enforce sophisticated program invariants using them. But Agda and the others feature termination checkers that make them Turing Incomplete.


Careful 5COLOR NP hardness Given the following definition of Careful 5COLORING:

  A 5-coloring is careful if the colors assigned to adjacent vertices
  are not only distinct, but differ by more than 1(mod 5)

how would a reasonable reduction to prove NP hardness work? Suggestion is to reduce from standard 5COLOR, but I am not able to find a correct one.

I have tried reducing from an instance $G$ of the standard 5COLOR as suggested creating one extra vertex between every edge in $G$. That is, let $\{u,v\}$ be an edge in $G$, create a new vertex $w$ and add edges $\{u,w\}$ and $\{w,v\}$. Fix the color of every new vertex to the same color, for example 3. This results in a new graph $H$.

When proving "$G$ is 5COLORABLE iff $H$ is carefully 5COLORABLE", I can prove the first $G$ is 5COLORABLE $\rightarrow$ $H$ is carefully 5COLORABLE since $H$ actually requires only 3 colors (if every new vertex is colored as 3, I only need colors 1 and 5 for the original vertexes in $G$).

On the other hand, the proof doesn't work since there are instances where $G$ isn't 5COLORABLE but $H$ is carefully 5COLORABLE. This has led me to believe my reduction is wrong.

There is a dichotomy theorem that covers this. For a graph $H$, let $P_H$ be the following problem: On input of graph $G$, decide whether there is a homomorphism from $G$ to $H$. A homomorphism is a function that maps vertices of $G$ to vertices of $H$ in such a way that edges of $G$ are mapped to edges of $H$.

Observe how $5$-colouring is $P_{K_5}$, where $K_5$ is the complete graph with $5$ vertices: The only constraint for a homomorphism to $K_5$ is that the endpoints of edges are mapped to different vertices. Furthermore, careful $5$-colouring is $P_{C_5}$, where $C_5$ is a cycle of length $5$. (To see how that works out, let the vertices of said cycle be in the order $0,2,4,1,3$.)

Now the theorem states that:

If $H$ is bipartite, then $P_H$ is in PTIME.
If $H$ is not bipartite, then $P_H$ is NP-complete.

If you still want a reduction from $5$-colouring, I suggest to look for a suitable gadget. The gadget should be a graph $I$ with two special vertices $v$ and $w$, such that

There is no careful $5$-colouring of $I$ that assigns the same colour to $v$ and $w$.
For all colours $c$ and $d$ such that $c\not=d$, there is a careful $5$-colouring of $I$ that assigns $c$ to $v$ and $d$ to $w$.

Then, for a reduction you would replace every edge with a copy of $I$.

[EDIT]

Wikipedia has the following reference for the dichotomy theorem:

Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110