Quadratic probing maximum load factor with $c_1 = c_2 = 0.5$ to guarantee successful insertion For quadratic hashing, i.e an open-addressed table with the hash function of the form -

$h(x, i)= (h'(x) + c_1i + c_2i^2) \mod m$

Setting $c_1 = c_2 = 1/2$, and $m$ to some power of 2, leads to a hash function

$h(x, i) = (h'(x) + 1 + 2 + ... +i) \mod m$

I have read that the load-factor of a quadratically probed table should not exceed $0.5$ to guarantee insertion to succeed if an empty cell exists in the table. Wikipedia's article here https://en.wikipedia.org/wiki/Quadratic_probing#Limitations says that

"With the exception of the triangular number case for a power-of-two-sized hash table, there is no guarantee of finding an empty cell once the table gets more than half full, or even before the table gets half full if the table size is not prime. "

So what is the maximum load factor that will guarantee successful insertion for this case?

For the case you describe ($c_1=c_2=1/2$, $m=2^k$), you can reach a load factor of 1. The probe sequence touches all the cells in the table.

As a practical matter, you probably don't want to get really close to a load factor of 1, as the probing can take $O(n)$ time.


Proving NP-Complete problem by reduction of subset-sum My assignment question as "given a multiset of symbols (letters) L from an alphabet Σ (thus, the same letter may appear in L multiple times), and a set of words W ⊆ Σ' , UseAllLetters asks if it is possible to use all letters from L to make words belonging to W. You may form the same word multiple times. Prove that UseAllLetters is NP-complete."

I'm new learning NP problems and still having trouble to understand the intuition behind this. But I'll try my best and sharing my idea here to verify that I'm on the right track.

My suggestion as following:

To prove this question is NP-complete, we can do reduction to subset-sum problem, but we also have to show few things.

1.This problem is in NP. (I'm stuck on this)

2.Any NP-complete problem Y can be reduced to X.

So we choose subset-sum problem, as it defined as:Given a set X of integers and a target number t, find a subset Y ⊆ X such that the member of Y add up to exactly t. Which is similar to our problem, we can find a subset of letters $l$ in our L that make words belonging to W if we are able to find a subset Y ⊆ X such that the member of Y add up to t.

The reduction works in polynomial time.
UseAllLetters problem has solution iff subset-sum has solution. I'm also stuck on this, it seems like I have to argue the correctness of my reduction, and I'm not sure my reduction is the right way to do it, I just do like one-to-one mapping to subset-sum problem.

Any feedback?

To prove a problem is NP-complete you have to prove it is in NP and that it is NP-hard.
NP-hardness proof is usually however, a reduction from one NP-hard problem. To prove that the problem is NP, you can either describe  a non-deterministic polynomial time algorithm for the problem (An NTM that decides the language of the yes-Instances in polynomial time), or you can show that there is a certificate of polynomial size for each yes-instance, such that given the instance with the certificate you can in polynomial time prove that the instance is a yes instance.

Both ways are quite easy here. A polynomial certificate would be an answer of the problem. You can verify if a given set of words as a solution really uses each letter exactly once. Describing an NTM is also straightforward, where the NTM guesses all possible subsets of words and checks for each subset if it covers all letters and each letter exactly once.

To prove NP-hardness, I suggest a reduction from the Exact-Cover problem instead, since it is more related. In the exact cover problem, you are given a Universe of elements $\mathcal{U}$ and a family of sets $\mathcal{F} = \{F_1, \dots F_n\}$ over the universe (A set of subsets of the universe). The output is whether there is a subset of the sets in the family that cover the whole universe and each element is covered exactly once (included in exactly one chosen set). A reduction to your problem would be as follows. We set $\Sigma = W = \mathcal{U}$ (each element in $W$ is repeated exactly once). From each set $F \in \mathcal{F}$ we build a word $s$ that contains exactly the elements in the set (in any order).

If the instance of the exact-cover problem is a yes-instance, then there is a subset of the family $\{F_{i_1}, \dots F_{i_k}\}$ that covers each element in the universe exactly ones. The words $s_{i_1}, \dots s_{i_k}$ we built from these sets cover each element in $W$ exactly once so it is also a yes instance. On the other hand, if the instance of your problem is a yes instance, there is a ste of words $s_{i_1}, \dots s_{i_k}$ that covers each element in $W$ and hence in $\Sigma$ exactly once. The sets $F_{i_1} \dots F_{i_k}$ we build the words from cover each element in the universe exactly once.


Why is this basic language not a regular language? L = {x in {0,1}* | x has an equal number of 0s & 1s}

Based on the recursive definition of regular languages, isn't it possible to form a single regular language set over the binary alphabet {0,1} by doing the following?

concatenating 0's and 1's to form each of the binary strings satisfying the condition, resulting in a regular language consisting of that single string
union all the single-string regular languages together into one single regular language

Every language is the union of regular languages:
$$
L = \bigcup_{x \in L} \{ x \}.
$$
However, the set of regular languages is not closed under infinite unions. It isn't even closed under countably infinite unions, as your example demonstrates.

You can prove that your language is not regular in many ways. For example, if your language were regular, then so would its intersection with $0^*1^*$ be; yet this language is $\{ 0^n 1^n : n \geq 0 \}$, the classical example of a non-regular language. You can also prove non-regularity of your language directly, using either the pumping lemma or Myhill–Nerode theory.


Number of equivalence classes Given language $L$, why is it not necessarily true that the number of equivalence classes of $L$ is equal to the number of equivalence classes of $L^R$?
And for the private case that $L$ is regular, is that true?

Assuming you refer to Myhill-Nerode equivalence classes:
First notice, that for a non-regular language $L$, the number of classes is necessarily infinite. This is one direction of the Myhill-Nerode theorem.
Since regular languages are closed under reversal, it follows that for a non-regular language $L$, both $L$ and $L^R$ have the same ``number'' (namely, infinitely) of equivalence classes.
For the case of regular languages, the Myhill-Nerode relation is very ``right-biased'', since it relates to the existence of a separating suffix. This is why reversing the language may change the number of classes. For example, consider the language
$$L_k=\{w\in \{a,b\}^*: w_k=a\}$$
i.e. the language of words whose $k$-th letter is $a$.
It's easy to show that the number of classes for $L_k$ is roughly $k$ (maybe $\pm 1$).
However, the language $L_k^R$ of words whose $k$-before last letter is $a$, is known not to have a DFA with less than $2^{k-1}$ states (and hence it has $\Omega(2^k)$ classes).
Interestingly, reversal and congruence classes do have an interplay: if you take a DFA, reverse it, determinize it, reverse it again, determinize again, and remove all unreachable states, you will obtain a minimal DFA for the original language, which is exactly what the equivalence classes characterize. This is Brzozowski's algorithm.


Algorithm for approximation with sum or difference of 2 unit fractions Let $U =\{\frac{1}{n}: n\in \mathbb{N}\} \cup \{-\frac{1}{n}: n\in \mathbb{N}\}$ be the set of positive or negative unit fractions.

Given positive integers $m<n \in\mathbb{N}$, how do you find $u_1, u_2 \in U$ such that $|\frac{m}{n} - (u_1+u_2)|$ becomes minimal?

A weaker problem would be the following: Given positive integers $m<n \in\mathbb{N}$ and a positive integer $k\in\mathbb{N}$ devise an algorithm that outputs "Yes" if there exist $u_1, u_2\in U$ such that $|\frac{m}{n} - (u_1+u_2)| < \frac{1}{k}$, and "No" otherwise.

Here's a method that gets close. Do a continued fraction expansion of $\frac{m}{n}$:

$$\frac{m}{n} = \frac{1}{a + \frac{1}{b + \epsilon}} \approx \frac{1}{a + \frac{1}{b}} = \frac{1}{a} - \frac{1}{a(1 + ba)}$$

If $\epsilon$ is small, then this is probably very close to optimal if not optimal in most cases.

The method fails when the truncated continued fraction approximation isn't very good. Take $\frac{15403}{26685}$ (a rational approximation to the Euler-Mascheroni constant) as an example. The continued fraction approximation is:

$$\frac{15403}{26685} = \frac{1}{1 + \frac{1}{1 + \epsilon}}$$

Which suggests:

$$\frac{15403}{26685} \approx \frac{1}{1} - \frac{1}{2}$$

But clearly $\frac{1}{2} + \frac{1}{14}$ is closer.

I would wager that the worst case for any method is the conjugate golden ratio $\phi' = \frac{\sqrt{5} - 1}{2}$. This isn't rational (in fact it's the "most" irrational number in a technical sense; find its continued fraction expansion if you're curious), but you can get arbitrarily close by choosing $m$ and $n$ to be consecutive Fibonacci numbers, e.g. $\frac{4181}{6765}$. The best approximation I could find is $\frac{1}{2} + \frac{1}{9}$.


Leftist Tree initialization in O(n) time In the book Handbook of Data Structures and Applications, section 5.2.5, (copy of the relevant section available here) about leftist queues, the author(s) state the following:

  For the complexity analysis of of the initialization operation, assume, for simplicity, that n is a power of 2. The first n/2 melds involve max HBLTs with one element each, the next n/4 melds involve max HBLTs with two elements each; the next n/8 melds are with trees that have four elements each; and so on. The time needed to meld two leftist trees with 2 i elements each is $\mathcal{O}$(i + 1), and so the total time for the initialization is
  $$\mathcal{O}(n/2 + 2 (n/4) + 3(n/8) + \ldots) = \mathcal{O}(n\sum \frac{i}{2^i}) = \mathcal{O}(n)$$

However, it seems to me that the summation iterates from i = 0 to $\log(n)$: $\sum_{i=0}^{\log(n)}$. This means it varies based on n, which in turn means the algorithm doesn't achieve $\mathcal{O}$(n) time as claimed but instead $\mathcal{O}(n \sum_{i=0}^{\log(n)} \frac{i}{2^i})$ time.

Am I misunderstanding something? I've found other explanations online stating $\mathcal{O}$(n) time for this sort of mass initialization is possible, but this is the only proof I've found so far.

The succession $a_i = 2^{-i}i$ is absolutely convergent.

In more elementary terms:

$$
\frac{n}{2} \le \sum_{i=1}^{\log n} \frac{ni}{2^i} \le n\sum_{i=1}^{\infty} \frac{i}{2^i} = n\sum_{j=1}^{\infty} \left( \frac{1}{2^j}\sum_{i=1}^{\infty}  \frac{1}{2^i} \right) = 2n
$$


VC dimension of set of functions Let $\chi$ be an instance space and $H \in \{0, 1\}^\chi$ a class with finite VC-dimension. For each $x \in X$ we consider $z_x\colon H \rightarrow \{0, 1\}$ s.t. $z_x(h) = h(x), \forall h \in H$.
Let $Z = \{z_x:H\rightarrow\{0,1\}\mid x\in\chi\}$. Is $\mathit{VCdim}(Z)<2^{\mathit{VCdim}(H)+1}$?

The only thing that comes to mind when seeing this is the Sauer lemma, but that's related to the growth function and I don't see how to apply it here. Anyone got any idea on how to approach this?

This is a classical result of Assouad (Densité et dimension) about dual VC dimension.
Let $A$ be a binary matrix. The VC dimension of $A$ is the maximal size of a set $S$ of columns which are shattered, that is, all possible rows appear when we restrict $A$ to the columns in $S$. The dual VC dimension of $A$ is the VC dimension of $A^T$, the transpose of $A$.
Suppose that $A^T$ has VC dimension $2^{d+1}$. Then there is a set $S$ of $2^{d+1}$ rows of $A$ such that when we restrict $A$ to this set of rows, we see all possible columns. If we number the rows using binary numbers of length $d+1$, then in particular we see the following columns: for each $i$, there is a column which contains the $i$'th bit of the row index. For example, if $d=1$ then we see the following columns:
$$
\begin{matrix}
0 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
1 & 1 & 1
\end{matrix}
$$
Therefore the VC dimension of $A$ is at least $d+1$.
If we take $d = \mathrm{VC}(A)$, then we deduce $\mathrm{VC}(A^T) < 2^{\mathrm{VC}(A)+1}$.


What are the k-collections described in ch. 8 of "An Introduction to the Analysis of Algorithms" by Sedgewick In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425.

My confusion is how to identify the k-collections. A k-collection is defined as:
"to be a word that consists of k different letters with the last letter in the word being the only time that letter occurs"

Exercise 8.6 of the book asks to find all the 2-collections and 3-collections in Table 8.1, where that table shows the configurations of 4 balls in 3 urns

If I give it a try, I'd say a 3-collection from Table 8.1 is 2213, where the last letter (number 3) occurring just at the end, but I'm pretty sure I"m wrong.

Can anybody help providing an example of a k-collection (2 or 3-collection) from Table 8.1? Thanks

I cannot figure out why you were "pretty sure" you were wrong, because you have given a correct example, "a 3-collection from Table 8.1 is 2213, where the last letter (number 3) occurring just at the end".

Here are 2-collections.
1112, 1113, 2221, 2223, 3331, 3332.

Here are 3-collections.
1123, 1132, 1213, 1223, 1312, 1332,
2113, 2123, 2213, 2231, 2321, 2331,
3112, 3132, 3221, 3231, 3312, 3321.

There is a natural way for you to check whether your understanding is correct without any extra effort, assuming you are required or scheduled to read that section "coupon collector problem" in the book. What you could have done is to try to understand that section as much as possible, assuming whatever interpretation your could have. If you find some inconsistency, then your interpretation is probably wrong. Otherwise, your interpretation is probably correct.

For example, I also doubted my understanding of that definition of $k$-collection.

However, when I have read "if each box of a product contains one of a set of $M$ coupons, how many boxes must one buy, on the average, before getting all the coupons? This value is equivalent to the expected number of balls thrown until all urns have at least one ball or the expected number of keys added until all the chains in a hash table built by Program 9.1 have at least one key", I am confident that I got it correctly. I can imagine each letter in an $M$-collection is a box containing a coupon, where different letters mean different coupons. A ordered collection of letters is an ordered buying sequence of boxes containing coupons. So an $M$-collection means a buying sequence that gets all $M$ coupons right at its last buy. Ditto for chains in a hash table. The more I read, the more confident I become.


Why does my answer sheet say the set of computable functions is uncountable? I'm trying to understand why I can't find room for the set of computable functions in the hotel of the Hilbert's Hotel Paradox.

I was thinking that, because Gödel numbering, I could consider the set of computable functions as numerable (and with cardinality equal to $\mathrm{card}(\mathbb N)$). However, I have an  answer sheet that says otherwise, and makes a proof of that I'm pretty sure that is wrong. At least I don't trust it:

  Suppose that the computable functions set is enumerable, and $f_n$ is a function of the set. Consider $g(n)=f_n(n)+1$, its not in the set, therefore contradiction. Because that proof then the computable functions aren't countable, so they can't fit in the Hilbert Hotel.

There are countably many computable functions. If $f_n$ is a complete list of all (total) computable functions, then the function $g(n) = f_n(n)+1$ cannot be any of the functions on the list, and so is not computable. This is one way to construct an uncomputable function.


Finding a '1' cell with a '0' to its right in a binary array Given an array of size n that holds ones and zeros I need to find an index of a  1 cell that has 0 to his right (in then next cell) there could be more than one pair in a given array, any one of them is fine. The array is not sorted, but we do know that the first element is 1 and the last element is 0.

The search should be in $O(\log n)$ time. I'm thinking that a binary search variation is the answer but I'm not sure how.

After viewing the original question, it seems that you have an additional piece of information: you know that the first element is 1 and that the last element is 0.
This is crucial!

So indeed you can solve it with binary search: first observe that if the first element is 1 and the last is 0, there must be subsequence of the form $1,0$ in the array.

Denote the array by $A[1,...,n]$. If $A[n/2]=1$, then there is a $1,0$-subsequence in the subarray $A[n/2,...,n]$. If $A[n/2]=0$, then there is a $1,0$-subsequence in the subarray $A[1,...,n/2]$.

So you can use Binary search, which takes $O(\log n)$ time.


Algorithm to output all instances of stable matching So the Gale-Shapley algorithm is just one way to output one stable matching instance. Is there any algorithm that can allow us to output all stable matching solutions ? Thanks

Dan Gusfield gave such an algorithm in his paper Three Fast Algorithms for Four Problems in Stable Marriage. The algorithm uses $O(n^2)$ space, and takes time $O(n^2 + nS)$, where $S$ is the number of stable matchings.


Proof NP-Complete for Single machine Job Scheduling Problem specific version Problem: given a set of n tasks with execution time Ti, due date Di, and a profit Vi (given only if is enden before due date), is there a task schedule that returns a total profit greater or equal than k knowing that tasks must be executed one at a time?

I am asked to proof that this problem is NP-Complete, can anyone help?

Thanks.

Since this problem is very approachable, you could first try to think about a greedy solution to show this is in the class P, and thus probably not in NP-complete. Once you have done this you could think about a polytime reduction to a problem known to be in NP-complete. Consult Karp's original 21 problems to get a feel for the type of problems you can use to find this reduction. Once you have done this come back with more specific questions :)


occur-check, does nominal unification has it? In unification, there is a "occur-check".  Such as $X = a \, X$ fails to find a substitution for $X$ since it appears on right hand side too.
The first-order unification, higher-order unification all have occur-check.

the paper nominal unification described a kind of unification based on nominal concepts. But I did not mention "occur-check" at all.

So, I am thinking why? does it has occur-check?

Yes, it has the occur check. The ~variable transformation rule of nominal unification has a condition which states

   provided X does not occur in t

what it is saying is exactly occur check.


Proof that the set of all universal CFGs is co-RE complete Let $\Sigma^*\text{CFL} = \{G \mid G \text{ is a CFG; } L(G) = \Sigma_G^*\}$.

Enumerate the r.e. sets by $W_n$.

Let $\text{EMPTY}= \{ n \mid W_n=\emptyset\}$.

On page 4 of these lecture notes, to show $\text{EMPTY}\leq\Sigma^*\text{CFL}$ the author constructs a function $g\colon\mathbb{N}\to\{0,1\}^*$ such that

$$n\in\text{EMPTY}\iff L(g(n))\in\Sigma_n^*.$$

I think we actually want $n\in\text{EMPTY}\iff L(g(n))\in\Sigma_{g(n)}^*$. Is this correct?

In the proof we construct grammar $g(n)$ such that it has same alphabet as the Turing machine + symbols for states + separator "#", which is defined to be:

$\Sigma_n = \{0, 1, \triangleright, B, \#, q_0, q_1 . . , q_n \}$

So essentially $\Sigma_n = \Sigma_{g(n)}$. $\Sigma_n$ is a superset of $\{0, 1, \triangleright, B\}$.


How are variables accessed in the correct order from the stack? I'm learning about the stack but one thing I am unable to understand is how variables can be accessed in the correct order.

So if I had a basic program calculating the sum of some user entered values (pseudocode)

Input value1
Input value2
Input value3
Input value4
Input value5
result = value1 + value2 + value3 + value4 + value5

Am I correct in thinking the variables value1 through to 5 would be stored in the stack?
If so this means that value 5 would be the first out for the next section but since my program needs value1 first how does it get this value? (assuming a simplistic computer with minimal registers).

That depends on how your program is written, its language, and how exactly your compiler implements variables. Some languages just don't place variables on any stack (everything is global). This is how FORTRAN and early versions of BASIC used to work. "Normal" languages (like C, Pascal and such) allocate a structure (often called activation record) on the stack, containing space for the local variables, and use architecture-dependent (and compiler-dependent) code to get at the variables. Many scripting languages will have the variables handled by allocating space elsewhere and just linking to the values from an activation record-like place in the stack. Even other languages, particularly LISP-derived ones, don't enforce the last call done -- first call finished rule, and thus can't use a stack for activation records. As @YuvalFilmus comments, there are languages like FORTH around, where it is your responsibility to manage such details.


Steiner tree four points example I have been looking at the wikipedia page for steiner trees, and I don't quite understand their 4-point solution. If the four  vertices are arranged in a rectangle shape wouldn't there be only one steiner vertex required in the middle to create the shortest length graph? The solution shows two vertices S1 and S2, but it seems that it would be shorter if there was only one vertex S instead, in between S1 and S2 and all of the vertices A, B, C, and D connect to S.

You are asking the question for Euclidean Steiner Trees. For Euclidean Steiner Tree problem one can show that "points added to the graph (Steiner points) must have a degree of three, and the three edges incident to such a point must form three 120 degree angles". That's why you need two steiner vertices instead of just one for 4 point solution. If you take just one extra point the degree will be 4 and angles also will not remain 120 degree.

To prove the property of Euclidean Steiner Trees take help of your favorite search engine. A good reference. See section 3.


Why add S0 -> S while converting CFG to Chomsky Normal Form While converting CFG to CNF sometimes it is suggested to add extra step.
Add new start symbol S0 and add new derivation S0 -> S. Book Hopcroft Ullman does not suggest this step but many other articles suggest to add this step.
What is purpose of adding this extra derivation?

This has to do with the fact that grammars in Chomsky normal form cannot generate the empty word. Indeed, if we only allow rules of the form $A \to BC$ and $A \to a$, then it is impossible to generate the empty word.
In order to accommodate languages containing the empty word, we allow the transition $S \to \epsilon$, where $S$ is the starting symbol. For various reasons (for example, the proof of the pumping lemma), we still don't want any other symbol to generate the empty word, so we disallow $S$ on the right-hand side.
The transition $S_0 \to S$ allows us to treat $S$ as a normal symbol, that is, to allow it to appear on the right-hand side, even if the grammar generates the empty word.


Basic action for every data structure O(1) My lecturer for Algorithms said that most of the data structures I will encounter in the algorithms course I am taking have a basic action which is of O(1).

Ex: Binary heap.

Basic action is:

  Compare 2 childen.
  Compare the "winner" with his parent.
  Replace when needed.
  Do 1-3 with the "winner", until and including the root.

How is O(1) even possible?

What was meant is that every data structure is designed to do something really well, e.g:

For an array, lookup by index is O(1)
For a linked list, insertion at the head is O(1)
For a heap, finding the smallest element is O(1)

... and so on. This doesn't mean that the operation that is O(1) for one data structure wouldn't have much worse complexity for some other data structure.


Is intersection used in regular expression? As union is part of regular expression in form of positive closure, similarly intersection is also a part of regular expression? in which form it can be used?

Regular expressions over an alphabet $\Sigma$, and their denotations (denoted by $L[r]$), are defined as follows:

$\emptyset$ is a regular expression, and $L[\emptyset] = \emptyset$ (empty language).
$\epsilon$ is a regular expression, and $L[\epsilon] = \{\epsilon\}$ (the empty word).
For each $\sigma \in \Sigma$, $\sigma$ is a regular expression, and $L[\sigma] = \{\sigma\}$ (single letter).
If $r_1,r_2$ are regular expressions over $\Sigma$ then so is $r_1r_2$, and $L[r_1r_2] = L[r_1]L[r_2]$ (concatenation).
If $r_1,r_2$ are regular expressions over $\Sigma$ then so is $r_1+r_2$, and $L[r_1+r_2] = L[r_1] \cup L[r_2]$ (union).
If $r$ is a regular expression over $\Sigma$ then so is $r^*$, and $L[r^*] = L[r]^*$ (iteration).

The definition of concatenation of languages is
$$
L_1L_2 = \{w_1w_2 : w_1 \in L_1, w_2 \in L_2\}.
$$
The definition of iteration is
$$
L^* = \bigcup_{n=0}^\infty L^n, \text{ where } L^0 = \{\epsilon\} \text{ and } L^{n+1} = L^nL.
$$

As you can see, union is built into regular expressions, whereas intersection isn't. However, the set of regular languages (which is the set of languages of the form $L[r]$) is closed under intersection, and so given any two regular expressions $r_1,r_2$, we can find a regular expression $r$ such that $L[r] = L[r_1] \cap L[r_2]$.

It turns out that sometimes $r$ will be much larger than $r_1,r_2$, see for example
Gelade and Neven, Succinctness of the Complement and Intersection of Regular Expressions, Theorem 17(2). A similar phenomenon is exhibited by complementation, see for example Theorem 12(2) in the aforementioned paper. For this reason, sometimes extended or generalized regular expressions are considered, in which operations such as intersection and complementation are allowed. While this does not increase the expressivity of regular expressions – every language expressible using an extended regular expression can also be expressed as a standard regular expression – it does increase their economy (i.e., length or size).


How can the union of two 'context-free but not regular' languages be regular? I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language:

  If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined over the same alphabet $Σ$ then, the union $L_1∪L_2$ can be a regular language.

I can't find an example to prove that this statement is true because by definition the context-free languages are closed under union operation.

Could someone please provide an example?

Let $L$ be a context-free but not regular language over $\{0,1\}$ such that its complement language $\overline L$ is also context-free. Then $\overline L$ is not regular and $L\cup\overline L=\Sigma^*$ is regular.

In particular, let $L=\{a^nb^n\mid n\in\Bbb N\}$.

The previous example requires you to verify that both $L$ and $\overline L$ are context-free. Here is an example with less burden.

Let $\Sigma=\{a,b,c,d\}$. Let $F_1$ be a context-free but not regular language over $\{a,b\}$. Let $F_2$ be a context-free but not regular language over $\{c,d\}$.
Then both
$F_1\cup\{c,d\}^*$ and $\{a,b\}^*\cup F_2$ are context-free but not regular. The union of them,  $\{a,b\}^*\cup\{c,d\}^*$ is regular.

In particular, Let $F_1=\{a^nb^n\mid n\in\Bbb N\}$ and $F_2=\{c^nd^n\mid n\in\Bbb N\}$.

Exercise 1. If $R$ is a regular language and $F$ is context-free but not regular such that $R\setminus F$ is context-free, then $F\cup (R\setminus F)$ is a desired example. Show that we can take $R=a^*b^*$ and $F=\{a^nb^n\mid n\in\Bbb N\}$.

Exercise 2. If $L_1$ and $L_2$ are 'context-sensitive but not context-free' languages, defined over the same alphabet $Σ$ then, the union $L_1\cup L_2$ can be a context-free language. In fact, the union $L_1\cup L_2$ can be a regular language as well.


Do we need recursion in programming language to solve any problem? My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions?

Assuming we are allowed to use: conditional evaluation of blocks (if/else), cycles(for,while), dynamic allocation of memory.

I know, that we won't be able to implement everything the way we want. However, I'm asking whether we are able to solve everything, just by using different implementation - or by modification of algorithm to be non-recursive.

In short, to answer your questions:

(1) You can convert any recursive algorithm into its non-recursive form.

(2) As stated by the others, you have all the features you need.

Computational Power (Turing-completeness)

You probably know that you cannot solve any problem, for instance, the halting problem is undecidable. And so are many other problems, such as deciding whether an arbitrary formula in first order logic is provable. Thus, with today's knowledge on computability, even the most advanced computer/programming system imaginable won't be able to process every query even if all the data is available.

When assessing the computational power of languages, computer scientists often use the notion of Turing-completeness:
If you can describe (and run) any Turing machine in your programming language, then it is Turing complete and can solve any problem which can be solved by a Turing machine.

To get a feel for Turing machines, I strongly encourage you to use a Simulator and try to solve some simple problems.

In particular, have a look at the syntax of the sample program in the Simulator, which should give you an idea of your minimal language.

Expressive Power and Minimality

When it comes to language design, expressive power is more important to me than the ability to solve any computable problem. Many useful domain-specific languages are not Turing-complete, but address specific problems very well.

However, equally powerful computational models such as the Lambda Calculus (functional programming) or the Pi Calculus (concurrent programming) show that you can have a very small set of elegant, composable language elements to construct larger systems, to be able to reason about their composition while having the computational power of Turing machines at the same time. Beautiful.

So if it is minimality you are looking for, take a closer look at the Lambda Calculus.
Other noteworthy well designed minimal languages are:

LISP
Prolog
Smalltalk and in particular Self

Feel free to add more languages to your personal list (and please let me know ;)


What is the complexity class of solving hash decision problems? With $hash_n$, I mean a standard cryptographic hash like sha256, scaled up to have arbitrary length $n$ of its output with the same underlying principles. What is the time complexity class of the following problem?

  Given an $n \in \mathbb{N}$ and data $d$ with $length(d) = n$, determine whether $\exists p : ((length(p) \le n) \wedge (hash_n(p) = d))$.

I find it really hard to find a class for it because it seems like a hard problem and it's definitely not $\in P$ (except if $P = NP$ or there is a vulnerability of the hash function (assume there isn't one not already known (so sha256 basically just printing the state of a state machine can be used, of course))) but you can't use it to solve any of the classical NP hard problems.

Determining the space complexity is of course trivial: It's only $\mathcal{O}(n)$.

This is of course just one example of a hash decision problem and it's meant to only be an example. I'm more interested in the general classification of hash decision problems.

Edit: You may assume a perfect hash function instead of a commonly used cryptographic hash function. E.g. if you're more comfortable with it, you don't want to exploit properties of cryptographic hash functions which are commonly used in practice, what you want to show is threatened by those properties, etc.

It's in NP.  In particular, it is easy to provide a witness for a yes answer (the witness is such a value $p$) and given a witness, you can verify the yes answer in polynomial time.

As you say, it's not in P if the cryptographic hash function is cryptographically secure.

I don't think it's likely to be NP-complete, but at the moment I can't articulate a specific reason why I think that.

(If you have a one-way permutation, then it's in NP $\cap$ coNP, so unlikely to be NP-complete... but that doesn't apply to your question.)


What order of growth does a ratio of Bigh-Ohs have? Say that $f(n) = \cal O(n^2)$ and $g(n) = \cal O(n)$.

If $h(n)=f(n)/g(n)$,  is it true that $h(n) =\cal O(n)$?

Is it mathematically correct to say that $h(n) = \cal O(n^2)/ O(n) = O(n)$? if not, what would be the correct way to show this?


How to solve this summation of ceiling function in BUILD-MAX-HEAP algorithm I am stuck on solving this problem and cannot understand how is the ceiling function omitted or solved.
Please help.

The equation:

$\sum_{h=0}^{\lfloor\lg n\rfloor} \lceil\frac{n}{2^{h+1}}\rceil O(h) $.

But this transformed to:

$O\left(n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{h}{2^h}\right)$

My question concerns on omitting the ceiling function. I'm not clear on whether it was omitted or solved.

This has been taken from CLRS Section $6.3$ Building a Heap.

Please help me out.
Thank you.

$$
\begin{align*}
\sum_{h=0}^{\lfloor\lg n\rfloor} \left\lceil\frac{n}{2^{h+1}}\right\rceil O(h)
&<
\sum_{h=0}^{\lfloor\lg n\rfloor} \left(1+ \frac{n}{2^{h+1}}\right) O(h)  \\
&<
\sum_{h=0}^{\lfloor\lg n\rfloor} \left(\frac{n}{2^h} + \frac{n}{2^h}\right) O(h)
=
2n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{ O(h) }{2^h}
= O\left(n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{ h }{2^h}\right).
\end{align*}
$$.


Karp hardness of an equidistant vertex set What is the hardness of the following problem?

  Input: An undirected graph $G(V, E)$ and a natural number $k$

  Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO

$\DeclareMathOperator{\dist}{dist}$An equidistant vertex set is a set of vertices $V'\subseteq V$ such that for every two pairs of vertices $u, v\in V'$ and $w, s\in V'$, we have $\dist(u, v) = \dist(w, s)$, where $\dist(u, v)$ is the length of a shortest path between $u$, $v$.

Your problem is NP-hard, by reduction from E3SAT, an NP-hard variant of 3SAT in which every clause involves 3 different variables.

Let $C_1 \lor \cdots \lor C_m$ be an instance of 3SAT; we can assume that $m$ is larger than some constant, since otherwise we can brute force the answer in constant time.
We construct the following graph:

Vertices: There is a vertex $(C_i,\ell)$ for each clause $C_i$ and for each literal $\ell$ appearing in the clause.
Edges: We connect $(C_i,\ell)$ and $(C_j,\ell')$ if $i \neq j$ and $\ell \neq \lnot \ell'$.

Here are a few claims:

The formula is satisfiable iff the graph contains an $m$-clique. Indeed, if the formula is satisfiable, we choose one satisfied literal from each clause, and these are the vertices of the clique. In the other direction, an $m$-clique must identify a literal from each clause. These literals are non-contradictory, and so correspond to a (possibly partial) satisfying truth assignment.
The diameter of the graph is 2. Indeed, given two vertices $(C_i,\ell),(C_j,\ell')$ (where possibly $i=j$), assuming $m \geq 3$ we can find a vertex $(C_k,\ell'')$ such that $k \neq i,j$ and $\ell''$ involves a different variable from $\ell,\ell'$.
If $(C_i,\ell)$ and $(C_j,\ell')$ are at distance exactly 2 then either $i = j$ or $\ell = \lnot \ell'$.
Suppose that $K$ is a "2-clique", that is, a set of vertices in which any two vertices are at distance exactly 2. Pick some $(C_i,\ell) \in K$. If all vertices in $K$ are of the form $(C_i,\cdot)$ then $|K| \leq 3$. Otherwise, let $(C_j, \lnot \ell) \in K$, where $j \neq i$. Every other vertex $(C_k, \ell') \in K$ must satisfy $k \neq i$ or $k \neq j$; suppose, without loss of generality, that $k \neq i$. Then $\ell' = \lnot \ell$. Since $(C_k, \lnot \ell)$ and $(C_j, \lnot \ell)$ are at distance 2, necessarily $j = k$. That is, in this case $|K| \leq 2$.
Therefore if $m \geq 4$, there is an equidistant vertex set of size $m$ iff the formula is satisfiable.


Efficient algorithm for assigning weights to nodes in graph to create steady state flow I'm looking for an efficient algorithm (at least polynomial in the size of the graph, preferably linear) for the following problem:

Definitions:
Given a graph $(V,E)$, with non-negative weights assigned to it's edges $w_E:E \rightarrow \mathbb{R}^+\cup\{0\}$ and non-negative weights assigned to it's vertices $w_V:V \rightarrow \mathbb{R}^+\cup\{0\}$ we define the flow on the edge $e=(v_1,v_2)\in E$ to be the wight of the vertex where the edge starts times the weight of the edge, $f(e=(v_1,v_2)) \equiv w_V(v_1)\cdot w_E(e)$. The inward flow to vertex $v\in V$ is defined by the sum of the flows on all inward edges $f_{in}(v) = \sum_{e\in E\;s.t.\; e=(u,v)}f(e)$ and the outward flow the sum of flows on all the outward edges $f_{out}(v) = \sum_{e\in E\;s.t.\; e=(v,u)}f(e)$.

The Problem
Given a finite directed graph $(V,E)$ and an edge weights assignment $w_E$, find a non-trivial weights assignment to the vertices $w_V$ such that the inward flow and the outward flow are equal for each vertex, $\forall v\in V\; f_{in}(v) = f_{out}(v)$. The trivial solution is $w_V\equiv 0$. Notice that I'm only looking for one non-trivial solution (there could be more than one). If there is no non-trivial solution the algorithm should return some error message.

Any ideas?
Thank you for your help

I will assume, that all weights are rational (since there is a problem with representing irrational numbers on computer).

You can solve this problem by using linear programming in similar manner to finding maximal flow.

$\forall_{v \in V} w_V$ is constant.

$\forall_{e \in E} w_e$ is variable.

Firstly, for each node we want to be sure that inward flow is equal to outward flow:
$$\forall_{v \in V} \sum_{(v_{i}, v)\in E}w_{v_{i}}w_{(v_{i}, v)} = \sum_{(v, v_o)\in E}w_{v}w_{(v, v_o)}$$

Then we want to be sure, that every edge is non negative:
$$\forall_{e \in E} w_e \geq 0$$

You can notice, that if there is any non-trivial solution then there are infinitely many, arbitrary large flows (you can multiply weight of every edge by constant $c$ and it will be still valid). So if there is any non-trivial solution, then there is a solution with sum of weights of edges not smaller then 1:
$$\sum_{e \in E} w_e \geq 1$$

Now what's left is to check if there is a solution for this linear programming instance.


Language Features Not Translatable into Lambda Calculus Haskell is said to be a pure language because the language features are directly translatable into lambda calculus.

My question is: for languages considered to be non-pure functional languages (e.g. Scala, OCaml), which aspects of those languages are not translatable into lambda calculus?

That's not what "pure" means. Pure means, generally, that there is no mutable state, and no way to interact with the outside world (i.e. IO).

Haskell is not "directly translatable" (what translation between language features really means needs to be defined fist, but let's ignore that for now) into either the untyped or simply-typed lambda calculus. There are many features that prevent it from being so, but a good example is polymorphism: there is no polymorphic identity function in the simply-typed lambda calculus.

Instead, Haskell and SML are actually derived from the Hindley-Milner type system, which is an extension of the simply-typed lambda calculus with polymorphism and type-constructors (aka higher-kinded types). Hindley-Milner has the nice property that type inference is decidable without any type annotations.


What's the fastest way to find the Kth smallest value in an unsorted list without sorting? My initial algorithm:

Compare element 0 with every other element, keeping track of how many elements are less than it.
Repeat for each element until an element that is greater than exactly (k-1) elements is found.

I assume this would take $O(n^2)$ in the worst case. Can a faster runtime be achieved without sorting the list?

Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection_algorithm


Simulate the concatenation of two log-space programs in log-space I've got two log-space programs $F$ and $G$.

Program $F$ will get input in array $A[1..n]$ and will create the output array $B[1..n]$.
Program $G$ will get as input $B$ as created by $F$ and create from it the output array $C[1..n]$.

I have to write a proof that there exist a log-space program $H$, which will get input Array $A$ and create from it corresponding array $C$. But I can't find the correct way to write it. How is this done?

A log-space program is a program which uses $O(\log n)$ bits of memory. Here are some conditions you have to keep:

You have to use only variables which have simple integer type (for example int in C++, longint in Pascal).
Allowed range of integer is defined: if $n$ is the size of the input we can save into variables only values which are polymonial sized based on $n$.

For example: we can have variables which can takes on values in $[-n...n]$, $[-3n^5...3n^5]$ or also values $[-4...7]$, but we can't have variables which will take on values in $[ 0...2^n]$.
No other types of variables are allowed, neither are arrays and iterators.
Exceptions from the rules about are input and output. Input will be available in special variables (mostly arrays) which your program can only read from, and the output can only be written to other special variables. So you can't read from output, and you can't increase values of input variables etc.
Your programs can't use recursion.

Example of log-space program written in Pascal (so everyone can understand it) which will find the largest number in the array of integer

    var n: integer;  //input variable the number of elements in A
    A: array [1..n] of integer; //input variable - the array of integers
    m: integer;      // output variable, the position of maximum
    i, j: integer;   //working variables
    begin
      j := 1;
      for i := 2 to n do
        if A[i] > A[j] then j := i;
      m := j;
    end;

The only two variables here are j and i and they evidently take values in $[1...n]$. Therefore all conditions are fulfilled and it really is a log-space program.

The idea here is that we can't compute the output of the first algorithm completely because it can take more than logarithmic space (it can be polynomially large). But we don't need to if we are intelligent. What we can do is simulate the second algorithm and produce the bits it needs from the output of the first algorithm on-line. In other words, we will simulate the second machine, when it wants to read bit $i$ from its input, i.e. the bit $i$ from the output of the first machine, we stop the simulation of the second machine, simulate the first and count (but not store) the bits it outputs until it outputs the $i$th bit at which time we can stop the simulation of the first machine and continue with the simulation of the second machine as we now have the value of what it wanted to read.


Chromatic number of a graph with $10$ vertices each of degree $8$? I have simple graph G on 10 vertices the degree of each vertex is 8. I need to determine the chromatic number of G. I tried drawing and all but it seems there is a trick needs to be used.

Let $G = (V, E)$ be a simple graph like you described (which is unique up to isomorphism and known as the Turán graph $T(10, 5)$, by the way). Note that the maximal degree possible in a graph with $10$ vertices is $9$ and thus, for every vertex $v$ in $G$ there exists a unique vertex $w \ne v$ which is not connected to $v$ and the two vertices share a neighborhood, i.e. $N(v) = N(w)$. Therefore, $v$ and $w$ may be colored using the same color. This however implies that the chromatic number of $G$, denoted by $\chi(G)$, satisfies $\chi(G) \leq 5$ since we can take all such pairs $\{v, w\}$ as described above and assign every such pair a unique color (using 5 colors in total).

To see that $\chi(G)$ cannot be less than $5$ consider the (induced) subgraph $G'$ of $G$ that we get by removing one vertex of every such pair $\{v, w\}$ as described above (that means $vw \notin E$). We find that $G'$ consists of 5 vertices and is complete, therefore implying that $G$ contains a clique of size $5$ and giving us $\chi(G) \geq 5$.

Hence we have shown $\chi(G) = 5$.


How can I determine an algorithm from a table of numbers? I need help with figuring out an algorithm from a generated numbers in a table. I was half way solving this question and I have already got the sequence for N=6, but I'm still stuck at writing the actual algorithm

On input $n$, output
$$
0^2 - n^2, 1^2 - n^2, 2^2 - n^2, \ldots, (3n-1)^2 - n^2.
$$
In pseudocode:

  For integer $k$ from $0$ to $3n-1$, print $k^2-n^2$.


What is meant by problems not in NP but in NP hard? If there is a proof that an NP-Hard problem which is not NP-Complete can be solved in P time, it does say that the verification time is polynomial too.

Why doesn't it then mean that all NP-Hard are NP (i.e. NPC)?

But, if there is something with exponential verification i.e. outside NP and since it can be reduced to an NPC problem in polynomial time which means it is also verifiable in polynomial time (As we assumed above). Isn't it? Which might say that all NP-hard is NP-complete...

I'm unable to grasp what is NP-hard but not NPC here? What is wrong in this reasoning?

Are there any problems which are outside Recursive Enumerable Languages in NP-Hard? Is that even possible?

A language $L$ is NP-hard if you can reduce every language in NP to $L$ in polynomial time. For example, the halting problem is NP-hard: if $A$ is any language in NP, say accepted by a nondeterministic polynomial time Turing machine $T$, there there is a polynomial time reduction which accepts an input $x$ and constructs a Turing machine which simulates all computation paths of $T$ on $x$, and halts if and only if any of these paths accepts.

On the other hand, the halting problem is not in NP, since it is not computable. So the halting problem is an example of an NP-hard problem which is not in NP.
You can think of NP-hard problems as being "at least as hard" as all of NP. They are allowed to be even harder.


Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine? Say I plugged in a hardware true-random number generator (TRNG) to my computer, then wrote programs with output that depends on the TRNG's output. Can it do anything non-trivial that a Turing machine with a psuedo-random number generator can't do? (a trivial thing it can do would be generating truly random numbers)

As long as decision problems (or optimization problems) are concerned, probabilistic Turing machines are equivalent to non-probabilistic Turing machines, since you can just simulate all the possible coin tosses (there are some subtleties here since the probabilistic Turing machine could halt only with probability 1, but let's ignore them).

However, there could be a difference in efficiency. Using truly random coin tosses could allow you to solve a specific problem faster. However, it is conjectured that truly random coin tosses can't bring down the level of difficulty from non-polynomial to polynomial, that is, if you have a probabilistic polynomial time algorithm for a problem, then there exists a deterministic polynomial time algorithm for the problem. This conjecture is known as the P=BPP conjecture. The idea is that you can simulate the truly random coin tosses with a sufficiently sophisticated PRNG. The simulation might be costly in running time, but it incurs only a polynomial overhead, and from this point of view that's a cost we're willing to pay.

Practically speaking, PRNGs are good enough, although in some rare cases you need to be slightly careful and use something beyond the fastest known PRNG. Only in cryptography does it sometimes make sense to use truly random coin tosses, since you can get absolute security guarantees this way (one-time pads), though in practice cryptographic PRNGs are used and they seem secure enough.


Randomly partition an rectangle into N smaller rectangles I'm looking for an algorithm that can partition a rectangle into N smaller rectangles, at random. N will be small (on the order of 5-10 in most cases). It need not be uniformly at random, but at the very least, I'd like to avoid algorithms which completely exclude interesting classes of partitions.

One algorithm I've come across a few times (including a question on Math.SE about the number of ways to do n partitions), is to randomly divide the rectangle in two by drawing an horizontal or vertical line across it, then do the same thing recursively to the resulting smaller rectangles until you get what you want.

The trick here is that although you can get a number of different partitions using this scheme:

There are some ways of dividing a rectangle into smaller rectangles that this method will never produce:

You can easily see that the divide-and-conquer partitioning will never generate the above, because there's no line that could possibly be the first cut, since no single straight line divides the entire square into two smaller rectangles.

So basically I'm looking for an algorithm to randomly divide a rectangle up into N smaller rectangles, where the results meet the following criteria:

Partitioned into exactly N smaller rectangles
Everything must actually be a rectangle (no L shapes, etc)
No empty space left over

The algorithm as a whole should meet the following criteria:

There is no valid partitioning that the algorithm is incapable of producing
Can be biased towards certain types of  configurations, though the less bias the better.
Preferably works with integer indices.
Does not operate by generating all possible partitions and then picking one at random.

I don't care about asymptotic complexity much, because I'll be working with small numbers.

Here's a simple idea that I believe can generate all partitions.  There are two types of subdivisions:

Given a rectangle, randomly generate a horizontal or vertical line to partition it into two subrectangles.  (The usual "split in two" rule.)
Given a rectangle, randomly generate a rectangle that fits inside it.  Consider the 4 corners of this inner contained rectangle: for each of them, flip a coin and draw a line from this corner outwards towards the outer containing rectangle, with the direction of the line (horizontal or vertical) being determined by what the coin says.  Regardless of the directions of the 4 lines, the result will always be 5 rectangles.  (Some partitions that can be generated by rule 1 can also be generated this way -- in fact, only 2 of the 16 possible configurations of lines will produce partitions that could not be produced by rule 1.)

At any point in time you will have a set of rectangles (initially, just the original one).  Randomly choose one to subdivide (or you could, e.g., choose the biggest, etc.), flip a coin to decide which of the two rules to apply to it, and then apply that rule; keep doing this until you have $n$ rectangles.

Disclaimer: I have no idea how to even think about the set of all partitions, let alone whether the above procedure generates them all with equal probability...  Probably not.


Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper Given a list of pairs $(a_1,b_1),\ldots,(a_n,b_n)$, where all $a_i \geq 0$ and all $b_i > 0$, my general problem is when we can use linear subset scan (described below) to solve the optimization problem of finding the optimal combination of pairs,

$$I^* = \hbox{argmax}_I F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$$

where $F,G$ are given increasing positive functions for positive inputs.

I have found a class of functions where there is a fast solution, namely $F(x) = x + A$ and $G(x) = (x + B)^\beta$ where $A,B \geq 0$ and $0 \leq \beta \leq 1$.  In this case, the optimal solution can be found by sorting all pairs $(a_i,b_i)$ in decreasing order according to $a_i/b_i$, and then trying the first $k$ pairs in sorted order for all $k$ and choosing the best solution, and this gives the optimal solution.  (This is an example of linear subset scan optimization.)

Now I want to know, if there a general class of functions $F,G$, ideally defined by abstract properties, where this linear subset scan approach works, where pairs are sorted either according to $a_i/b_i$ or perhaps sorted according to $H(a_i,b_i)$ where $H$ depends on $F,G$?  This could be a question where someone has a new insight and proof, or simply someone has seen something like this in the literature.  At any rate, I feel like the class of $F,G$ I stated where I have a proof is perhaps not the most general possible, and I'm missing some key abstract property that makes the linear subset scan work.

If I wanted to solve this problem, I wouldn't limit myself to the linear subset scan algorithm: I would consider other algorithms as well.

For instance, here is one approach that might be effective in many cases.  If $\theta$ is a non-negative real number, define

$$h(\theta) = \max \left\{\sum_{i \in I} a_i : \sum_{i \in I} b_i \le \theta\right\}.$$

Note that

$$F(I^*)/G(I^*) = \max_\theta F(h(\theta))/G(\theta).$$

So, define $f:\mathbb{R}\to \mathbb{R}$ by

$$f(\theta) = F(h(\theta))/G(\theta).$$

With these definitions, our goal is to find the maximum of $f$.

Also, note that we can compute $h(\theta)$ for any given $\theta$ of our choice, using integer linear programming.  (In principle, there is no guarantee that ILP will run in polynomial time, but in practice, I bet it may often be possible to compute this reasonably efficiently.)  Your linear subset scan algorithm (sort the $a_i,b_i$ by decreasing value of $a_i/b_i$) is a good heuristic for efficiently computing an approximate solution to this ILP (computing a lower bound on $h(\theta)$), but as far as I can see, there is no guarantee that it will actually find the true optimum value.

This means that we can also compute $f(\theta)$ for any given $\theta$ of our choice.

So, we have a function $f$ in one real variable, to which we have black-box access, and we want to maximize it.  Now a reasonable approach is to apply any standard algorithm for black-box mathematical optimization, e.g., grid search followed by hill-climbing, coordinate descent, gradient descent, Newton's method, or other methods.

It is also possible that some suitable criterion on $F,G$ might imply that $f$ has a nice property that makes it easy to maximize (e.g., it is increasing or something), and which might imply that your linear subset scan algorithm is a good approach.  I have not thought about that carefully, but you might look at that direction.


what’s wrong with this quantum key distribution scheme? I’m reading about the BB84 quantum key distribution scheme, and I’m surprised that it’s conceptually more complicated than seems necessary to me. What’s wrong with this conceptually simpler scheme?

Alice chooses two random strings $x,y \in \{ 0,1\}^{2n}$
Alice encodes $x$ into qbits, choosing the basis in which to encode the ith qbit according to whether $y_i$ is 0 or 1.
Alice sends the qbits to Bob (Bob himself doesn’t generate any random strings).
Once Bob confirms to Alice (on an insecure but authenticated channel) that he’s received the qbits, Alice sends $y$ to Bob (on an insecure but authenticated channel).
Bob decodes all the qbits using $y$. He then chooses $n$ bits at random from $x$, and sends these $n$ classical bits to Alice (using the insecure channel), together with an encoding of which bits he picked.
Alice confirms whether the first $n$ qbits are indeed the same as the first $n$ bits in $x$. If they are, then they know that Oscar didn’t observe the qbits, and they use the other $n$ bits as the key. If one of them is not the same, they know that Oscar meddled with the process.

Does this work?

No, not really.  The main problem with this protocol is that it is less practical than BB84.

Less practical

Bob is a benign party.  To measure a q-bit, you need to know what basis to measure it in before you can measure it (e.g., before you can measure a photon, you need to have your measurement apparatus set up in the appropriate basis).  Ordinarily, we'd like to measure it as soon as we receive it.  Your protocol doesn't allow that.

Your protocol requires Bob to receive the q-bit and then decide later what basis to use to measure it.  That means Bob will need some way to store the q-bit for later measurement.  There might be a way to do that (e.g., put the photon into a long delay loop), but it will probably increase complexity and expense.

It's not reasonable to expect legitimate parties to have to do that just to communicate.  And in any case, BB84 doesn't require parties to jump through those hoops.  So your scheme is less practical than BB84.

Side note on security:

With your protocol, it is important that step 4 (including Bob's confirmation) be over an authenticated channel.  Without that, there is a security problem.

BB84 provides the following security property: if the final reconciliation phase is done over an authenticated channel (not necessarily secret; it can be public communication; but it does need to be authenticated), and if the parties don't abort, then the resulting secret will be known only to Alice and Bob.  In particular, no adversary -- not even an active man-in-the-middle attacker -- can arrange to learn the secret.

Your protocol doesn't offer that guarantee, if step 4 happens over an insecure channel.  With your protocol, there's a trivial way that a man-in-the-middle can arrange to learn the secret, with zero chance of being detected.  When Alice sends the q-bits, the adversary Mallet intercepts and stores them.  Mallet then sends a confirmation that the q-bits were received to Alice (pretending that this came from Bob).  When Alice sends $y$, Mallet intercepts and learns $y$.  Now Mallet decodes all the q-bits using $y$, and learns $x$.  In the second phase, Mallet encodes $x$ into new q-bits and sends those q-bits to Bob (pretending they came from Alice).  When Bob responds that he has received them, Mallet sends $y$ to Bob (pretending it came from Alice).  Now Bob will decode his q-bits, obtain the same value $x$, send back some of the bits of $x$ to Alice, everything will match, and both Alice and Bob will think that they have obtained a secure key -- but Mallet actually knows that secret key, since Mallet has learned $x$.  This attack works even if steps 5 and 6 are done over an authenticated channel.

I suspect it suffices to require step 4 to also go over an authenticated channel (I'm not 100% sure; that would require proof; but it looks like it to me).


How could an SMT solver be implemented as simple as possible? I'm trying to figure out how an SMT solver works as simple as possible.
Let's assume we have a simple input program with symbolic values x and y.
E.g.

if (x+y < 20) {
   if (x > 10) {
      if (y > 10) {
        assume(false);
      }
   }
}

Here we have different paths, depending on the conditions. To reach assume(false) each condition has to be true, so our outcoming formula is:

$x+y < 20 \,\,\,\,\,\wedge \,\,\,\,\, x > 10 \,\,\,\,\, \wedge \,\,\,\,\, y > 10$

So far, so good. What happens next, step by step?

I would like to implement, as simple as possible, a solver which gets as input something like the formula above and delivers specific output to reach the end of the path - here assume(false), i.e. x = 2147483647, y = 2147483647 (jfi: x+y would be -2) - for overflow detection or similar.

I know there are a lot of SMT solvers on the internet, but I couldn't find a really simple self-explaining one. Looking forward to a suggestion.

What happens next is that we invoke a SMT solver to try to check whether the formula

$$x+y < 20 \quad \land \quad  x > 10 \quad \land \quad y > 10$$

is satisfiable.  The solver tries to find values for $x,y$ that make this formula true.  If it finds such a value, then it knows the assume(false) statement is reachable. (I am guessing you meant to write assert(false), not assume(false).)  If the formula is not satisfiable, then that statement is not reachable.

So basically you are asking: how do SMT solvers work?  That is too broad for this site, but there are lots of places that explain how SAT solvers and SMT solvers work.  I would suggest doing some research; you will find many explanations.  You could start with the DPLL algorithm for SAT.

There is little point in implementing your own solver.  Your solver will probably perform far worse than existing tools.  There has been a lot of research into building effective solvers, and the techniques required are non-trivial.  Instead, I'd recommend you simply use an existing solver, such as Z3.

If you just want to implement one for fun, the most straightforward approach is probably to bit-blast to SAT: treat each bit of (the binary representation of) $x,y$ as a boolean variable, then write down a boolean formula (on those boolean variables) that expresses the requirement that $x+y<20$.  How can you do that?  Write a boolean circuit that computes $x+y$ and compares the sum to 20, then convert that circuit from CircuitSAT to SAT.  Finally, invoke an off-the-shelf SAT solver to check satisfiability of this boolean formula.  You'll need to do some research to understand each of these steps, but there's a lot written on how to do that.


Upper bound for runtime complexity of LOOP programs Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions.
Furthermore primitve recursive functions can (as far as I understood) compute anything that isn't growing faster than $Ack(n)$.

Is this implying that the upper bound runtime complexity for LOOP programs is $O(Ack(n))$? And are there functions similar to Ackermann's function, which can't be computed by primitive recursive functions, but grow slower than $Ack(n)$?

(sorry for spelling and grammar)

Take Ack(n-1). Grows much slower than Ack(n).


If$A \leq_T B$ is given, can you reduce $\overline{A}$ to $B$ and vice-versa If you are given two languages $A$, $B$ and $$A \leq_T B.$$ Is it possible to $\overline{A} \leq_T B$ or $A \leq_T \overline{B}$?
Here is my shot.
Case 1: $\overline{A} \leq_T B$
This is only possible if $A \leq_m B$ exists and $B=\overline{B}$. As you can transform any many-one reduction to its complement, we can show that if $A \leq_m B$, then $\overline{A} \leq_m \overline{B}=B$. Thus $\overline{A} \leq_m B$.
Case 2: $A \leq_T \overline{B}$
This is the same as above but we need to change the role of $A$ and $B$.

You say:

This is only possible if $A \le_m B$ exists and $B=\overline{B}$

But that condition simplifies to "false" since it can never the case that  $B=\overline{B}$.
Anyway the answer to both cases is "yes".
If $A \le_T B$ then there is a Turing machine $T$ with oracle $B$ that decides $A$.
By complementing $T$'s output we obtain a Turing machine with oracle $B$ that decides $\overline{A}$  showing that $\overline{A} \le_T B$.
Moreover, consider a Turing machine $T'$ with oracle $\overline{B}$ that simulates $T$ except for the following: whenever $T$ invokes its oracle for $B$ on some input $w$, $T'$ invokes its oracle for $\overline{B}$ on $w$ and then complements the result. Clearly $T'$ still decides $A$, thus showing that $A \le_T \overline{B}$.


If I write code in machine language, then I have access to the CPU in both modes (user and kernel), since the OS is bypassed, correct? Codes written in machine language can have access to both CPU modes (Kernel and user), since the OS is bypassed, correct?

No. The Operating System is going to use context switching and virtual memory to hide the fact that there are multiple processes running on the computer. Native code does not mean you have full control to the CPU registers, global physical memory. Your program, if not privileged, is still running in user mode. You need to use syscalls to do lower level tasks. The operating system provided a virtual and abstract environment for the program to make them convince themselves they are running on a dedicated machine.


How to express modalities in lambda calculus - are some extensions required? Lambda calculus can be used for encoding semantics of natural language, e.g. http://yoavartzi.com/tutorial/ contains full details about semantic parsing of natural language: converting natural language texts into lambda expressions - Cornell Semantic Parsing Framework is used https://github.com/cornell-lic/spf.

My question is - how to express modalities in lambda calculus - are some extensions required? E.g. usual classical modal logics can express beliefs/duties-permissions/knowledge and other kind of modalities. Relational (Kripke) semantics is used for modal logics. So - how can we extend of combine lambda calculus to express modalities?

There is idea to express modalities as just another kind of predicates https://www.amazon.co.uk/Toward-Predicate-Approaches-Modality-Trends-ebook/dp/B016XM48V0 but are there some alternatives, more "natrual" ways to introduce modalities in lambda calculus? Full handling of natural language certainly requires this.

Are extensions required? Not really. You can take an axiomatic description of a modal logic and simply provide a "primitive" lambda term for each. The modal operators would become type constructors. Haskell's IO monad can be viewed this way. Coherence conditions like the monad laws would provide some conversions between terms.

A different approach, which does involve extending the lambda calculus, is described in Frank Pfenning's and Rowan Davies' A Judgmental Reconstruction of Modal Logic.  Note, this is for an intuitionistic modal logic. This involves changing the context, or specifically, having multiple contexts to include hypothetically valid propositions. You get rules like:$$
\frac{\Delta;\cdot\vdash M : A}{\Delta;\Gamma\vdash\mathsf{box}\ M:\square A}\qquad\frac{\Delta;\Gamma\vdash M:\square A\quad\Delta,u::A;\Gamma\vdash N:B}{\Delta;\Gamma\vdash\mathsf{let\ box}\ u=M\ \mathsf{in}\ N : B}$$
You should read the $\mathsf{let\ box}\ u = M\ \mathsf{in}\dots$ as pattern matching/a destructuring bind against $M$.

We have:$$
(\lambda m.\mathsf{let\ box}\ u= m\ \mathsf{in}\ u) : \square A \to A \\
(\lambda f.\lambda x.\mathsf{let\ box}\ f'=f\ \mathsf{in\ let\ box}\ x'=x\ \mathsf{in\ box}\ (f'x')) : \square(A\to B)\to\square A\to\square B \\
(\lambda m.\mathsf{let\ box}\ u=m\ \mathsf{in\ box}\ (\mathsf{box}\ u)) : \square A \to \square \square A$$
Handling possibility as opposed to or in addition to necessity requires a bit more cleverness.


How does Grover's Quantum Sorting avoid reading the list? It is well known now that Grover's quantum algorithm can SORT a database of $N$ entries in $O(\sqrt{N})$ time. How can an algorithm work without reading through the list of entries which needs $O(N)$ operation. How does Grover's algorithm avoid reading the list? Is there a special representation that can be used classically as well? I understand any such representation will not help the classical case. However I am curious to understand how Grover avoids reading the list?

The list (or database) is given implicitly by an "oracle" function, which is called $\Theta(\sqrt{N})$ times throughout the algorithm. Suppose for example you're looking for a divisor of some number $N$. Then the function could map $k \leq \sqrt{N}$ to true if $k$ is a non-trivial divisor of $N$, and false otherwise. Grover's algorithm will then find a non-trivial divisor of $N$ in time $\tilde{O}(\sqrt[4]{N})$ instead of the usual $\tilde{O}(\sqrt{N})$ (note that better algorithms are available in this case, even for a classical computer).


single agent vs multiple agent reinforcement learning I am confused about 'single' vs 'multiple' agent reinforcement learning.

Let's say that I have 1 hunter who I am training to hunt 1 static prey, so that only the hunter is moving around. This is definitely single-agent RL.

If there are two hunters and two preys (moving or static), then this becomes multiple agent RL. It would be 'easier' to study two independent hunters, perhaps, but that is a different problem.

My question is this: If there is 1 hunter only, but there are two preys. There is 'some form of interaction' (vaguely defined) between the hunter and prey. Is this still a single-agent RL? or a multiple one?

Is it possible that my agent is the hunter, and all preys be just part of the environment?

A key difference between RL and MARL arises when you consider that other agents are strategic and their behaviour is adaptive. Game theoretical concepts are very important within the scope of MARL and bring in a new range of issues. From a single agent perspective, the environment is non-stationary as every strategic agent is changing their policies to best respond to the each other.

A good discussion on the challenges of MARL can be found here:
http://busoniu.net/files/papers/marl_chapter_springer.pdf

Regarding your question:
Yes, you can use a single agent RL as long as the preys are not learning. If you plan to apply RL to every agent (hunter and preys), you will find new issues such as convergence problems, etc. There is a lot of research going on around this. To start I would suggest you have a look at some basic and classic concepts such as Fictitious Play and WoLF (Win or Learn Fast).


NP $\subsetneq$ EXP? I think I heard in somewhere that it has been proven that $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$, that is $\mathsf{NP} \subsetneq \mathsf{EXP}$. Is this right? Wikipedia and book resources do not seem to bring me an answer..

I just found a post similar to this, but I am not sure whether $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$.

Strictly contained means $\subsetneq$, i.e. it is the definition, it is not a result. So what you are saying is
$$\mathsf{NP} \subsetneq \mathsf{ExpTime} \implies \mathsf{NP} \subsetneq \mathsf{ExpTime}$$
 which is trivially true.

If you are asking if $\mathsf{NP}\subsetneq \mathsf{ExpTime} $ then the answer is: it is unknown.

You may want to check the Wikipedia article about Exponential Time Hypothesis which many experts believe is true.


Generalization of Subgraph Isomorphism I am wondering how to prove that Subgraph Isomorphism is NP Complete.  Wikipedia indicates that the CLIQUE problem can be used to demonstrate this, but I can't figure out how. I also found this link that demonstrates how Subgraph Isomorphism reduces to CLIQUE, but I can't figure out how to reverse it.  Subgraph isomorphism reduction from the Clique problem

Here is a formal example of the problem from DASGUPTA 8.10:
Given as input two undirected graphs G and H, determine whether G is a subgraph of H (that is, whether by deleting certain vertices and edges of H we obtain a graph that is, up to renaming of vertices, identical to G), and if so, return the corresponding mapping of V (G) into V (H).

A subgraph is isomorphic to a clique if, and only if, it is a clique.


Is there any nontrivial problem in the theory of serial algorithms with a nontrivial polynomial lower bound of $\Omega(n^2)$? In  the theory of distributed algorithms, there are problems with lower bounds, as $\Omega(n^2)$, that are "big" (I mean, bigger than $\Omega(n\log n)$), and nontrivial.
I wonder if are there problems with similar bound in the theory of serial algorithm, I mean of order much greater than $\Omega(n\log n)$.

With trivial, I mean "obtained just considering that we must read the whole input" and similarly.

There are such problems by time hierarchy theorem. Just take any problem that is complete for a large complexity class. For example, take a problem that is complete for $\mathsf{ExpTime}$. Such a problem will be $\Omega(n^c)$ for all $c\in\mathbb{N}$.

However also note that for problems in $\mathsf{NP}$, there are not strong time lower-bounds in multiple-tape TM model and existence of linear time algorithms for SAT is consistent with current state of knowledge. (In single-tape TM model it is not difficult to show that many problems like palindromes require $\Omega(n^2)$ time but such lower-bounds depend essentially on the particulars of the single-tape TM model.)


How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in a undirected graph? How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in an undirected graph ?

I've seen it stated that one can apply a maximum flow algorithm to compute a minimum $s$-$t$ cut in an undirected graph. However, trying to adapt the Edmond-Karp algorithm this doesn't make much sense, or does it ?

I know a graph can be viewed as an undirected graph with $(u,v)$ and $(v,u)$ replacing $\{u,v\}$...

You don't need to adapt the algorithm, any maximum flow algorithm for directed graphs works by replacing the edges with a forward and backward arc as you suggested. Denote this directed graph $D=(V,A)$. Take the capacities $C(u,v)=C(v,u)$ of both arcs equal to the original edge. Then, let $F(u,v)$ be the maximum flow returned by your algorithm on the directed graph.

To find the cut you need the (directed) residual graph $G_f$ which can be constructed explicitly from the flow by taking $D$ with capacities $C_f(u,v) = C(u,v) - F(u,v)$. Now find the set $S$ of vertices reachable in $G_f$ from $s$, where you can only cross arcs with positive capacity, and let its complement be $T=V\setminus S$. Then $(S, T)$ gives a minimum $s-t$ cut.

To see why this works, note that the capacities in the residual graph give the additional amount of flow in each direction that can be sent over an edge. That is, given the flow already in place, and if you assume that opposite flows cancel each other out. This means a saturated edge has 0 residual capacity in the direction of the flow and double its original capacity in the reverse direction (as $F(u,v)=-F(v,u)$).

Any vertex reachable from $s$ in $G_f$ can receive more flow. Since $F$ is a maximum flow, $t$ cannot be in $S$. Similarly any edge between $u \in S$ and $v \in T$ must be saturated with flow in that direction, otherwise $v$ would be reachable from $s$. Now suppose the capacity of the cut-set is larger than the $s-t$ flow, then the flow from $S$ to $T$ is larger than the flow from $S$ to $t$, which means there must be flow back from $T$ to $S$ which is a contradiction. Since any $s-t$ cut is at least as large as the maximum $s-t$ flow it follows $(S,T)$ is a minimum $s-t$ cut.


Why are diploid (dominant/recessive) genes not used widely in genetic algorithms? In most implementations of genetic algorithms, the focus is on crossover and mutation. But somehow, most of them leave out diploid (dominant/recessive) nature of genes. As far as my (limited) understanding goes dominant/recessive nature of genes is a very important factor in deciding the actual characteristics of an organism.

So my question is why is the diploid nature of genes left out of genetic algorithms in most implementation?

Is it because:

it doesn't provide much benefit
it adds unnecessary complexity to an otherwise simple algorithm
it's difficult to implement

Or something else entirely?

I don't know the actual reason, but it feels intuitive: let's think about what the diploid nature of genes does in RL. In essence it allows the recessive gene to remain in the gene pool  even if it's currently at disadvantage to exist, and occasionally resurface, giving two things - first, it doesn't go extinct and can re-multiply if it becomes advantageous; and second, it ensures some population variety as you'll continuously have both phenotypes - a part of population that exhibits the gene and part that doesn't.

Both of these things can be achieved in simpler ways by the mutating/crossover engine - you can directly 'fetch' random good-performing items from 100000 generations ago (which nature usually can't); and you can keep multiple varied subpopulations while protecting the non-primary ones from extinction, which nature usualy doesn't do.


Finding the frequency of each unique value of an attribute in a relation (RELATIONAL ALGEBRA) I am trying to figure out how I can use aggregate functions to solve this problem. For example if I had the table

enrolled(student-id, course-id)
123 897
123 645
589 452
009 897

If I wanted to find the number of courses each student is enrolled in, how would I go about doing that? I was thinking of using the count function but I don't know how to separate each student-id


Runtime analysis of prime-set computation I want to find the all primes between 2 and $k-1$. We can come up with an $O(k\log k)$ running time algorithm. I want to compute this set in $O(k)$ running time. For this algorithm is :

we are maintaing a one pointer from node $i$ of the list $L$ to index $i$ of array $N$ and one pointer from index $i$ of $N$ to $i$th node of list $L$. We will use a doubly linked list in such a way that we mark each element of $N$ exacly once.

Pick the smallest unmarked element $i \ge 2$ in $N$ and add $i$ to $Q_{k-1}$.
Starting from the first node, walk up the list $L$ in increasing order until we find the smallest number $r$ in it such that $r\cdot i \ge k-1$.
Walk down the list $L$ (crucially, in decreasing order) from the node $r$, and for each $l$ in $L$, seen, mark the element $N[i\cdot l]$ and delete the node containing $i\cdot l$ from $L$ ( this node in $L$ is accessed through the pointer from the $(i\cdot l)$th location in $N$ ).
If $N$ has any unmarked element $\ge 2$, go back to first step

In the first round all the multiple of 2 will get marked. It is easy to verify that each element in the array will get marked just once.

  Question : How to show that above algorithm has Running time $O(k)$?

After first iteration all multiples of 2 will be marked in the array $N$ and all multiples of 2 will be removed from the list $L$. In the second iteration multiples of 3 and so on.

$$
\begin{align*}
\text{Total time}: &= c_1k + c_2\frac{k}{2} +c_3\frac{k}{2 \times 3} +c_4\frac{k}{2 \times 3 \times 5} + c_5 \frac{k}{2 \times 3 \times 5 \times 7}+\cdots\\
&=k \left(c_1 + c_2\frac{1}{2} +c_3\frac{1}{2 \times 3} +c_4\frac{1}{2 \times 3 \times 5} + c_5 \frac{1}{2 \times 3 \times 5 \times 7}+\cdots \right) \\
&= O(k)
\end{align*}
$$

Reference : link

The key is already shown in your link: each composite number is marked only once in this algorithm.

Consider a composite number $x=p_1^{\alpha_1} p_2^{\alpha_2}\cdots$ where $p_1<p_2<\cdots$ are primes and $\alpha_1,\alpha_2,\ldots$ are positive integers. In the iteration for $p_i$ ($i>1$), note $p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_i^{\alpha_i-1}\cdots$ has been deleted from $L$ in the iteration for $p_1$ because $p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_i^{\alpha_i-1}\cdots$ is a multiple of $p_1$, so $x$ will not be marked in the iteration for $p_i$. As a result, $x$ will be marked only once in the iteration for $p_1$.

In each iteration, traveling the list costs the same asymptotically as the marking process, because each element in the list corresponds to a number to be marked.

Hence the total time is equal to the time for marking asymptotically, which is $O(n)$.


Can we get a better time hierarchy theorem? The time hierarchy theorem states that

$DTIME(f(n)) \neq DTIME(f(n)\log(f(n)))$

(Let me acknowledge that this statement isn't 100 percent accurate because f must be "time constructible" and potentially other things that I'm missing)

If we were to take some function f, we can consider

$DTIME(f(n)) \subset DTIME(f(n)\sqrt{\log(f(n))})\subset DTIME(f(n)\log(f(n)))$

Where we know that at least one of these inclusions is strict. Do we know of examples where one of these inclusions isn't?

In general we might want to prove that
$DTIME(f(n)) \neq DTIME(f(n)g(f(n)))$
for a function $g$ which is as small as possible. Do we have better upper bounds on $g$ (like $g(n) = \log\log n$)? do we have non-trivial lower bounds on $g$ in the form of some (time constructible) $f$ for which $DTIME(f(n) = DTIME(f(n)g(f(n)))$?

IMHO, there cannot be better, stricter Time Hierarchy Theorem everywhere.

To improve this theorem, you need faster Universal Turing Machine. The $log(n)$ overhead of the currently fastest simulation technique seems to be unavoidable, especially for large enough time bounds, since with more time resource the simulated TM can do crazy things that the UTM cannot assume some regular property to do the simulation faster.

With small time bounds, there may be some improvements. But, its consequences are negligible.


How to prove or disprove that f is computable? If $f(x_1,\dots, x_n)$ is a total function that for some constant $K$, $f(x_1,\dots, x_n) \leq K$ for all $x_1,\dots, x_n$ then $f$ is computable.

I want some hints on how to prove/disprove the above claim. This an exercise from the book Computability, Complexity, and Languages. As I didn't find the solutions to the exercises online, I want to see a formal solution of such problems, if possible.

Define the function $f: \mathbb{N} \to \{0,1\}$ as follows.  Let $f(x) = 1$ if turing machine $x$ halts on itself as input and $f(x) = 0$ otherwise.  Then for all $x$, we have that $f(x) \leq 1$.  Yet, if $f$ is computable, then the Halting problem should be decidable.


"Compressing" rationals given error bounds I'm working on implementing some exact real arithmetic operations for fun. I've got the rough outline of how I want to do things as well and have figured out how to write most of the important algorithms (though I have not properly implemented them just yet).

Going against the "pre-mature optimization is bad, m'kay" philosophy I am wondering about a few things. So reducing fractions is one way to reduce the size of rationals, sure, but it isn't perfect. If you knew you only had to be within a certain range you could do better by changing the value. For instance say I need to add $1$ and $\frac{1}{8}$ to with in $\frac{1}{2}$. I don't need to full precision, I can just return 0 in fact. More beneficially say I had something like $\frac{2^{16}+1}{2^{32}}$, if I only need say something like $\frac{1}{2^{15}}$ precision, I can approximate this rational as $\frac{2^{16}}{2^{32}}$ and then reduce that to $\frac{1}{2^{16}}$.

This are some contrived cases but I think there is a generally useful optimization to be done here. Are there algorithms which, given an error bound, can find the smallest (in bits) rational number within the specified bounds of another given rational number?

Most of my algorithms tend to produce rationals with power of two denominators so I am particularly interested in that case.

Continued fractions are an efficient way to enumerate rational numbers that are a good approximation of your number $x$.  In particular, given a real number $x$, you can generate a sequence of truncated continued fractions $a_i/b_i$, where each rational number $a_i/b_i$ is a better approximation to $x$ than any other fraction whose denominator is $\le b_i$.  So, a reasonably good algorithm for your problem is to compute the sequence of truncated continued fractions, and keep the last one whose denominator is smaller than your bound.  This doesn't find the best rational approximation for a given number of bits, but it does give you a best rational approximation for a given upper bound on the size of the denominator.

To compare to KWillets' excellent answer: KWillets' method takes something like $\Theta(a+b)$ steps, but finds the optimal solution (measured by bits).  Continued fractions takes something like $\Theta(\lg b)$ steps, but isn't guaranteed to find the optimal answer (measured by number of bits); it's only guaranteed to find the optimal answer if you measure by the size of the denominator.  KWillets' method seems better if $a,b$ are not too large.  However, if they are very large, then a continued fractions-based method might become more attractive.


How can I argue that $3\mathsf{SAT}\leq_p \mathsf{IndSet}$ is polynomial in time? Given the reduction $3\mathsf{SAT}\leq_p \mathsf{IndSet}$ as follows:

How can I argue that it's in polynomial time? I understand how the reduction works, but even though it appears rather trivial, I can't explain why it's efficient.

  To place $\mathsf{IndSet}$ in $\mathsf{NP}$-Hard, we will show $3\mathsf{SAT}\leq_p \mathsf{IndSet}$:

  Given
  $$\phi=\bigwedge_{m=1}^{n}(x_m\vee y_m\vee z_m)$$
  with $m$ clauses, produce the graph $G_\phi$ that contains a triangle for each clause, with vertices of the triangle labeled by the literals of the clause. Add an edge between any two complementary literals from different triangles. Finally, set $k=m$. In our example, we have triangles on $x,y,\overline{z}$ and on $\overline{x},w,z$ plus the edges $(x,\overline{x})$ and $(\overline{z},z)$.

  We need to prove two directions. First, if $\phi$ is satisfiable, then $G_\phi$ has an independent set of size at least $k$. Secondly, if $G_\phi$ has an independent set of size at least $k$, then $\phi$ is satisfiable. (Note that the latter is the contrapositive of the implication "if $\phi$ is not satisfiable, then $G_\phi$ does not have an independent set of size at least k".)

  For the first direction, consider a satisfying assignment for $\phi$. Take one true literal from every clause, and put the corresponding graph vertex into a set $S$. Observe that $S$ is an independent set of size $k$ (where $k$ is the number of clauses in $\phi$).

  For the other direction, take an independent set $S$ of size $k$ in $G_\phi$. Observe that $S$ contains exactly one vertex from each triangle (clause) , and that $S$ does not contain any conflicting pair of literals (such as $x$ and $\overline{x}$, since any such pair of conflicting literals are connected by an edge in $G_\phi$). Hence, we can assign the value True to all the literals corresponding with the vertices in the set $S$, and thereby satisfy the formula $\phi$.

  This reduction is polynomial in time because $\Huge\dots?$

I've looked at many different examples of how this is done, and everything I find online includes everything in the proof except the argument of why this is polynomial. I presume it's being left out because it's trivial, but that doesn't help me when I'm trying to learn how to explain such things.

You are given a formula, and you will construct a graph. You can argue the reduction is polynomial time by analyzing the time you need to construct the graph. The transformation is an algorithm: write each step down, and analyze them. If every step takes polynomial time, you have shown the reduction runs in polynomial time.

Scan the clauses of the formula in time that is linear in the number of clauses. Scan the 3 literals in every clause. Build 3 vertices, with labels corresponding to the literals in a clause. This you can do in constant time, clearly. Once you have built a triangle, add it to your graph. With reasonable assumptions, you can do this in linear time, but details naturally depend on the way you represent your graph. Nevertheless, the time taken will be polynomial.

Finally, you only need to add edges between any two complementary literals from different triangles. Scan your triangles. For every literal in the triangle, scan through every other triangle, and see if there is a complementary triangle. If so, add an edge. This process takes polynomial time; for every triangle you are scanning every other triangle, so think of something quadratic. After every triangle has been scanned, $G_\phi$ has been built.


Partitioning a graph with specific constraints We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills these constraints:

|V1| - |V2| = 0 or 1 (V1 and V2 have the same amount of nodes or V1 contains one node more that V2)
either

[case A] all nodes in V1 have edges to all nodes in V2
[case B] all nodes in V1 have no edges to any node in V2

We had a few ideas to find those partitions via divide-and-conquer involving the degrees of each node to differentiate between case A and B. If we find any node v with degree(v) < |V2| then there is a partition with case B, otherwise if we find a node v with degree(v) > |V1| then there is a partition that fulfills case A.
However other than that we have been stuck and extendind or other ideas ended in a dead end.

How do we find those partitions? I'd like to not be given the answer but only a pointer to find a easy algorithm for the problem.

It suffices to be able to identify case B, since a graph satisfies case A if, and only if, its complement satisfies B.

A graph satisfies case B if, and only if, it is composed of components of size $n_1, \dots, n_\ell$ and there is some set $S\subset \{1, \dots, \ell\}$ such that $\sum_{i\in S} n_i = \sum_{j\notin S} n_j$.  (If $n_1 + \dots + n_\ell$ is odd, this is impossible, so include a fake component of size $1$.)

This is the set partition problem.  Bad news! It's NP-complete.  Good news!  It's not strongly NP-complete and we're encoding the numbers $n_i$ in unary. This means that the pseudopolynomial algorithms described on the Wikipedia page are actually polynomial-time algorithms in your context.  By checking the algorithms carefully, you can probably avoid the "fake component" trick.