Get all factors of a word in linear time or constant time I have the following problem :

I have an algorithm which takes a word $w$ as entry. The problem is that my algorithm is doing a lot of things on the factors of $w$ and I am representing $w$ as an array of char. So if I want to get the factor $w_i...w_j$ of $w$ I need to do a loop that begin at $i$ all the way to up $j$., so it basically takes$O(j-i)$ times. Yet I am doing this operation on a lot of couples $(i,j)$ so at the end it becomes heavy in time complexity.

So one idea is to first calculate all factors of $w$ and put them in a double array of size $\mid w  \mid^2$, I guess it takes $O(\mid w \mid^2)$ to fill this array.

Now I am wondering if we can improve this complexity ? Like for example get all factors of $w$ in linear time ? Maybe it's possible to use at first a different data structures to stack $w$ (so not array) that will allowed me to get any factors of $w$ in constant time ?

Thank you !

No, there's no faster way to calculate all the "factors" (substrings) of $w$.  It takes $\Theta(|w|^2)$ space even to write down the list of all factors.  Any algorithm has to spend at least 1 unit of time per character of output.  So, any algorithm will have to take $\Omega(|w|^2)$ time; you can't do better than $O(|w|^2)$ time.

If you want to look for a faster algorithm, you'll need to look for a way to do it that doesn't involve calculating and storing all possible factors.  You might want to think about what operations you need to perform on these factors, and whether there's any data structure that can help you perform those operations faster (maybe a Merkle hash tree?  maybe a rolling hash?  hard to know, without knowing what you're trying to do with the factors).


How to prove that n&(n-1) and n&(-n) respectively returns and removes the least significant bit? In a code, I saw someone use:
n&(n-1) to get the least significant bit of n ⇒ 101000 will return 1000
n&(-n) to remove the lsb from n ⇒  101000 will return 100000.
This sounds magical to me. Is there any proof for these?
Thanks a lot!

For $n=0b101000$ we have $n-1=0b100111$, so $n \& (n-1)=0b100000$.
As to the second, then knowing $-n=\sim n+1$ we have $-n= 0b10111 +1 = 0b11000$ so $n \& (-n)= 0b101000 \& 0b11000= 0b1000$.
Addition for general proof.

Let's take $n \in \mathbb{N}$. Suppose $k$ is first one in its binary expansion i.e. $n=2^m a_m+ \cdots + 2^k a_k$, where $m \geqslant k$.Then
$$n \& (-n) = 2^k$$
proof: as we know $-n=\sim n+1$. So, first step, $\sim n$, gives inversion for each bit. Hence in bits lower then $k$ we will have ones and in bit $k$ we will have zero. Now adding $1$ gives all zeros in bits lower then $k$ and in bit $k$ we again have one, but all upper bits are reversed. So $-n$ have in all  bits more then $k$ reversed values with respect to $n$, which gives result.

Again let's take $n \in \mathbb{N}$. Suppose $k$ is first one in its binary expansion i.e. $n=2^m a_m+ \cdots + 2^k a_k$, where $m \geqslant k$. If we consider $n-1$, then we get zero in $k$-th bit. So $n$ and $n-1$ have different coefficient only for bit $k$. This gives, that in
$n \& (n-1)$ we have all coefficients same as in $n$ besides $k$-th bit is zero.


DFA for language of all strings avoiding 'aa' I'm trying to draw a dfa for this description

The set of strings over {a, b, c} that do not contain the substring aa,

current issue i'm facing is how many states to start with, any help how to approach this problem?

For an alphabet of $\{a, b, c\}$ constructing a DFA that accepts all strings not containing the substring 'aa' tells you several things about the number of states you need. Firstly, and this is true for any DFA, you need at least one accepting state. Since your DFA is meant to filter out some strings, it requires a 'trap' or 'dead' state, a state that may never reach an accepting state once reached. Now clearly the strings 'a', 'b', 'c', and '' (empty string) do not contain the substring 'aa', therefore we know our initial state must also be an accepting state, which eliminates the next obvious choice for a new state.

So you know you need at least two states in your DFA, one trap state and one accepting state (which is also your initial state). Now you may also know that to construct a DFA that accepts the string 'aa' would require two states at least, so this gives a good guess that one additional state is required before transitioning to the trap state. So now there are three states to work with, if more are required they should come up as you construct your DFA from there.


Proving correctness of inefficient algorithm - Path between two vertices Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity and compare it with the other path between two vertices algorithms (Dijsktra, Bellman-Ford Algorithm, etc.) and explain why this algorithm is inefficient.

ALGORITHM Reachable(G, s, t)
     RETURN A(G,s,t,|V(G)|)
END Reachable

FUNCTION A(G,s,t,d)
     IF d=1 THEN
        IF s == t OR there is a directed edge (s,t) in G THEN
              RETURN TRUE
        ELSE
              RETURN FALSE
     ELSE
          FOR each vertex v in G DO
              IF A(G,s,v,d/2) AND A(G,v,t,d/2) THEN
                   RETURN TRUE
              ENDIF
          ENDFOR
          return FALSE
END A

I tried to prove correctness using invariants, but I'm not sure if that's the best way to prove it. Could you help me, please?

And I tried to obtain time complexity considering the for-loop, but also I have doubts.

Thanks a lot for your help!

If we interpret d/2 as real number division, then A(G,s,t,3) will run forever. If we interpret d/2 as integer division such as 3/2=1, then the algorithm will fail for a graph which is just a path of 6 vertices and 5 edges. If we interpret d/2 rather unnaturally as integer division of d+1 by 2, the algorithm becomes correct but the semantic of A(G,s,t,d) is not very natural either.

Hence, we will change the following part of the algorithm

              IF A(G,s,v,d/2) AND A(G,v,t,d/2) THEN
                   RETURN TRUE
              ENDIF

to

              IF A(G,s,v,d/2) AND A(G,v,t,(d+1)/2) THEN
                   RETURN TRUE
              ENDIF

together with the conventional interpretation of d/2 and (d+1)/2, the integer division.
We will see this change makes the most sense as shown by the simple proposition below that characterizes the semantic of function A(G,s, t,d).

We have the following proposition.

Reachable(d): A(G,s,t,d) returns TRUE if and only the distance from s to t is less than or equal to d.

Let us prove the above proposition by induction on d.

The base case when d = 1 is trivial.

Suppose reachable(d) is true for all d <= n, where n>=1. Let check the case when d=n+1.  There are two cases.

n+1 is even. Suppose n+1 = 2k. Checking the definition of function A, we can see that A(G,s,t, n+1) returns TRUE if and only if there is a vertex v such that both A(G,s,v, k) and A(G,v,t,k) return true, i.e., both the distance from s to v and the distance from v to t are less than or equal to k, thanks to the induction hypothesis since k <=n. That means the distance from s to t is less than or equal to 2k = n+1.
n+1 is odd. I will leave this case for you to check.

Proof is done.

The correctness of the algorithm is the correctness of reachable(|V(G)|), since there is path from s and t if and only if the distance from s to t is less than or equal to |V(G)|-1 (or |V(G)|, which is equivalent).

To verify that this algorithm can be very inefficient, we should find an example where it runs very slowly.  We would like to choose a graph for which A(G,s,t,d) computes as much as possible and return as late as possible. How about graphs with no edges? Let D be a graph of 2^n vertices without an edge.

Claim: A(D,s,t,2^k) will call A(D,*,*,2^(k-1)) 2^(n+1) times.

Claim: A(D,s,t,2^n) will call A(D,*,*,1) (2^(n+1))^n=(2^n)^(n+1)=|V(D)|^(log |V(D)| +1) times.

I will let you contemplate why this algorithm is so inefficient.


Modify DFA/NFA that accepts Language Subset with only Palindromes (with Size Limit)? Given a DFA (D1) with P1 states, that accepts a language L1.

Modify (D1) to create another DFA (D2), such that it will accept the language L2 that is defined as: All strings in L1 that are also a palindrome (of maximum length P1).

How many states would the minimized D2 have (worst case)? And time complexity?

Similarly, NFA (N1) with Q1 states that accepts a Language L3. How many states would minimized (N2) have (worst case)? Along with its time complexity?

The generic Palindrome Language is non-Regular hence a DFA/NFA for it is impossible but I am unaware of the limited Palindrome case in DFA/NFA?

For DFAs, the size of $D_2$ is always at most $O(P_1|\Sigma|^{P_1/2})$, and this bound is tight up to the $P_1$ factor. For the lower bound, take a DFA for $\Sigma^*$ having $P_1$ states (you haven't specified that $D_1$ is minimal). The DFA $D_2$ accepts all palindromes of length $P_1$, and so Nerode's theorem shows that for even $P_1$, the optimal DFA $D_2$ contains $\Theta(|\Sigma|^{P_1/2})$ states. The upper bound now follows by using the product construction.

The exact same reasoning works for NFAs as well, although you need to replace Nerode's theorem with a suitable "exchange lemma" in order to show that any NFA for the language of all palindromes of length $P_1$ requires $\Omega(|\Sigma|^{P_1/2})$ states (for even $P_1$).

If you insist on $D_1$ being minimal as well, then instead of a DFA for $\Sigma^*$ take a DFA for $(\Sigma^{P_1})^*$, to get the exact same results. This construction works also for NFAs.


Minimum space needed to sort a stream of integers This question has gotten a lot of attention on SO:
Sorting 1 million 8-digit numbers in 1MB of RAM

The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\mathord{,}999\mathord{,}999]$) using only 1 MB of memory ($2^{20}$ bytes = $2^{23}$ bits) and no external storage. The program must read values from an input stream and write the sorted result to an output stream.

Obviously the entire input can't fit into memory, but clearly the result can be represented in under 1 MB since $2^{23} \geq \log_2 \binom{10^8}{10^6} \approx 8079302$ (it's a tight fit).

So, what is the minimum amount of space needed to sort n integers with duplicates in this streaming manner, and is there an algorithm to accomplish the specified task?

Ok, it's way past my bedtime, but this won't let me go, so here's a second try (deleted my first)...

Before going into the specifics of how to sort the numbers, I will start by representing them not as a sequence of integers $i_1, i_2, \dots , i_n$, but as a sequence of their differences, i.e. $\delta_k = i_k - i_{k-1}$ where, by convention, $i_0 = 0$.

Then, in order to represent these values, I will first group them into buckets depending on the number of bits needed for their representation, with the assumption that I need one bit to represent 0. Since the numbers are between 0 and 99'999'999, I will need 27 buckets.

For each bucket, I will choose a prefix from the set 1, 01, 001, 0001, etc... Up to 000000000000000000000000001. Obviously, I will choose the shortest prefix for the largest bucket, the second-shortest for the second largest, etc...

The sequence of $\delta_k$ can then be written as pairs of prefixes and values, whereby for the values $>1$, the leading bit can be omitted.

For any random set of numbers, then, how many bits do I need to represent the sequence of $\delta_k$?

For a constant sequence, e.g. $0, 0, 0, 0, \dots , 0$, I only have to store one million representations of the number $0$, or with the above encoding, 10, hence 2 million bits. For any other constant, it would be 2 million bits plus the number of bits of that value for the initial $\delta_1$.

The same computation goes for an increasing sequence, e.g. $0, 1, 2, 3, \dots , n$, where $\delta_k=1$ and the sequence is represented as a million copies of 11.

Now what is the worst-case, i.e. what sequence of $\delta_k$ will give the longest sequence of bits? The worst we can do is make sure that each bucket has one entry less than the previous one, choosing the smallest $\delta_k$ possible, thus assigning the largest prefix to the longest sequences. For simplicity, I'll assume that $K$ buckets have the same amount of entries, with the shortest prefix assigned to the shortest sequence. This means that we have $n$ ones, $n$ twos, $n$ fours, etc... To represent the $j$th bucket, we need $2j-1$ bits, except for the first bucket, that needs $2$ bits.

So if we put $m$ $\delta_k$s into each of the $K$ buckets, we need $m\left(2 + \sum_{j=2}^{K}2j-1\right) = m(K^2 + 1)$ bits. However, the sum of all the $\delta_k$ must not exceed 99'999'999. This sum, assuming we've kept the $\delta_k$ as small as possible, is $m\sum_{j=2}^{K}2^{j-1} = m(2^K-2)$.

So here's the question: is there a combination of $K$ and $m$ such that

$m(2^K-2) < 100'000'000$, e.g. the largest value is $<100\,000\,000$,
$Km < 1'000'000$, e.g. there are at most a million values, and
$m(K^2+1) > 8'000'000$, e.g. we use more than $8\,000\,000$ bits?

Unfortunately, this does happen. Here's a plot of the number of bits as computed in Maple with plot( min( 100000000/(2^K-2) , 1000000/K ) * (K^2 + 1) , K=2..27 ):

So we can represent any sequence of up to one million numbers in $[0,99\,999\,999]$ using roughly 10 million bits. This is, unfortunately, still above the specification.

But how can we sort numbers like this? Well, remember that the numbers come in one by one, so as each number comes in, we update its bucket count ($\mathcal O(1)$) and compute the new optimal prefixes for each bucket ($\mathcal O(\log\log(i_\mathsf{max}))$ if the buckets are indexed in a heap). We then run through our encoded $\delta_k$, reading each entry, computing the respective $i_k$ from the cumulative sum, and comparing it to the new value. If the computed $i_k$ exceeds the new value, we encode the new value and write it back, along with the adjusted $\delta_k$, using the new encoding. Otherwise, we just write back the $\delta_k$ with the new encoding.

But write-back where? Well, if we treat our eight million bits as one large ring buffer, we can append the new, re-coded sequence of $\delta_k$ to the old sequence, re-writing the old values as we go along. We've got almost 1 million extra bits from the worse-case scenario, and I don't think the re-coding can cause that amount of stretching to make this not work.

All in all, this leaves us with a $\mathcal O(n)$ cost for inserting the $n$th number, which gives us an average-case cost of $\mathcal O(N^2)$ for a total of $N$ elements. This isn't really good, but speed did not seem to be a criteria.


How can I calculate tree sizes to "stretch up" a finger tree? I've been working on implementing an efficient Cartesian product operation (actually the <*> operation, but it amounts to about the same thing) for sequences based on Hinze and Paterson's "Finger trees: a simple general-purpose data structure". It seems that a natural way to calculate $xs \times ys$ when $xs$ and $ys$ each has at least two elements is to (conceptually) replace each leaf $x$ in $xs$ with a 2-3 tree representing $\{(x,y)\mid y \in ys\}$, and then "stretch" the first and last element of the resulting tree upwards/outwards to bring the tree to the proper depth. But for efficiency and other reasons, this actually needs to be done in the opposite direction—I'd need to pull off the first and last element of $xs$, and then work my way down, calculating at each level how much of $ys$ to leave behind there, and also to check whether it's possible to represent $ys$ by a 2-3 tree of the appropriate size for that level. I'm not really sure how to get a grip on the necessary math.

As it turns out, the best way to calculate the necessary tree sizes is not to. While crushing down one copy of the $ys$ finger tree (in a process reminiscent of "zipping" a Huet zipper), I can simultaneously crush down just one side of each of two additional copies, while pulling digits off the other sides to use directly (no calculation!). When I get near the bottom, I finish off the complete 2-3 tree, and then attach the two crushed half-trees to the $xs$ finger tree (once I've replaced its leaves using the complete 2-3 tree).
Edit (March, 2015)
The code (recently simplified and cleaned up) can be found in the GitHub repository. Both the <*> and *> implementations now use this technique; the latter takes advantage of Louis Wasserman's applicativeTree function to obtain asymptotic reductions in time and allocation.


Why does $2^{O(\log n)} = n^{O(1)}$ hold? I was recently looking at the article on the P complexity class on Wikipedia. In the section on relationships to other classes, it mentions that P is known to be at least as large as L, giving this explanation:

  A decider using $O(\log n)$ space cannot use more than $2^{O(\log n)} = n^{O(1)}$ time.

The article sadly fails to explain how that last equality holds. How exactly does one go about showing that $2^{O(\log n)} = n^{O(1)}$?

This is simple math. An expression of the type $O(\log n)$ is at most $C\log n$ for some $C > 0$ and large enough $n$. So for large enough $n$, the entire expression $2^{O(\log n)}$ is at most
$$
2^{C\log n} = n^C = n^{O(1)}.
$$
The first equation follows from the definition of the logarithm $2^{\log n} = n$, which in this case I conveniently assumed is taken to the base 2 (though it makes no difference in this case – can you see why?).


Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed? Wikipedia here https://en.m.wikipedia.org/wiki/Selection_algorithm shows an algorithm using sort of quicksort.. in order to find Kth largest or smallest element taking O(n) time only on average. The point which is unclear is whether K is required to be constant or at least independent of size of N.

I saw this issue being discussed on this site here : https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on
But people there in the comments seem to claim that K is fixed.

The point which I don't understand is, if k is indeed needed to be fixed.. then what's the point of this algorithm of select and quicksort?

Why can't we just perform like bubble sort K times if K is fixed it wouldn't be more than K*N  which is O(n) . So what's the problem of achiving it in O(n) if k is fixed.

There is no requirement that $k$ be constant, and those StackOverflow comments are misleading or simply incorrect.

Obviously $k \le n$ and so $k$ is $O(n)$. Your partial bubblesort algorithm is $O(kn)$ which is $O(n^2)$ unless $k$ is somehow restricted.

But the Quickselect algorithm is stochastic $O(n)$ and can be made worst-case $O(n)$ by using the median-of-medians algorithm to select the pivot. (Median-of-medians is too slow for practical use, but it proves that $O(n)$ is possible.) Quickselect does not require $k$ to be fixed.


If inorder traversal of a tree is in ascending order will the tree definitely be a BST? For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?

Yes.

The proof is straightforward. Assume you have a tree with a sorted in-order traversal, and assume the tree is not a BST. This means there must exist at least one node which breaks the BST assumption; let's call this node $v$.

Now, there are two ways $v$ could break the BST assumption. One way is if there's a node in $v$'s left subtree with label greater than $v$. The other way is if there's a node in $v$'s right subtree with label less than $v$.

But everything in $v$'s left subtree must come before it in the in-order traversal, and everything in its right subtree must come after it. And we assumed that the in-order traversal is sorted.

Thus, there's a contradiction, and such a tree cannot exist.

(EDIT: As RemcoGerlich points out, this is only true if your tree is known to be binary. But if it's not binary, an in-order traversal isn't defined, afaik.)


Different boolean degrees polynomially related? Let $f$ be a Boolean function.

Let $p$ be the minimum degree real polynomial that represents $f$ with degree $d_f$.

Let $p_\epsilon$ be the minimum degree real polynomial with degree $d_{f,\epsilon}$ such that $$|p_\epsilon(x)-f(x)|\leq\epsilon.$$

Let $p_{0,\epsilon}$ be the minimum degree real polynomial with degree $d_{0,f,\epsilon}$ such that $$f(x)=0\implies p_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p_{1,\epsilon}$ be the minimum degree real polynomial with degree $d_{1,f,\epsilon}$ such that $$f(x)=1\implies p_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Are $d_f,d_{f,\epsilon},d_{0,f,\epsilon}$ and $d_{1,f,\epsilon}$ all polynomially related?
It is clear $$d_{f,\epsilon}\leq d_{0,f,\epsilon},d_{1,f,\epsilon}\leq d_f.$$

Does $$d_{f}\leq (d_{0,f,\epsilon})^a,(d_{1,f,\epsilon})^b\leq (d_{f,\epsilon})^c$$ hold for some $a,b,c\in\Bbb N$?

What is a good reference to understand relations among these four degrees?

It is known that
$$ d_f = O_\epsilon(d_{f,\epsilon}^6), $$
for all $\epsilon < 1/2$. This is described in many lecture notes, for example these quantum lecture notes by Montanaro (Theorem 3). It is suspected that the best exponent is $2$. It is known that the exact value of $\epsilon$ only affects the constant.

Since $d_{f,\epsilon} \leq d_{0,f,\epsilon},d_{1,f,\epsilon} \leq d_f$, the other measures are also polynomially related.


Is it possible to solve the coin denomination problem using a 1-D array? In an algorithm book it said that to solve the coin denomination problem via Dynamic Programming approach a 2-D array is needed:

Exercises 8.4 #9

Is it not possible to do this using a 1-D array.

I was thinking that maybe you could set the $C$ values in a 1-D array as:
$C[0]=0$, $C[n]=1$ if $n$ is one of the denomination values and $C[n]= \infty$ if $n$ is less that the least denomination.

Otherwise set $C[n] = \min_{1 <= i <= \frac{n}{2}}{(C[i]+C[n-i])}$

What is wrong with my solution other than I won't be able to generate the actual solution because my goal is only to find the optimal number of coins for that $n$ value?

It is perfectly possible to solve the problem using a 1D array. Actually, you can even reconstruct the solution using just that 1D array. There are often multiple ways to solve a given problem, and in this case there's a neat time-memory tradeoff: in the 1D example you need $O(m)$ time to compute the value of one array slot, in the 2D example you only need $O(1)$ time but there are $O(nm)$ slots rather than just $O(n)$.


How to show that a $\log_2(x)$ is a recursive function? I have a problem for the comprehension of how to prove that a function $ \log_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as:
$$\log_2 (x)= \begin{cases}
y  & \text{if $x=2^y$} \newline
\bot & \text{otherwise}
\end{cases}$$
is recursive.
I think that I need to use minimization operator but I don't know how to do that.

Once you have proved that $|x-2^y|=0$ is a decidable predicate, the function
$$\log_2(x) \equiv \mu y(|x-2^y| = 0)$$
should match the description of the function given and proves that it is recursive.

Edit:
To show that $|x-2^y|=0$ is decidable, show that $\overline{\text{sg}}(|x-2^y|)$ is recursive, which requires you to show that $|x-z|$, $2^y$, and $1 - \text{sg}(z)$ are recursive, then use substitution.

$|x-z|$ can be defined as $(x-z) + (z-x)$ where cut-off substraction is used in the latter and you can use $x^y$ is a primitive recursive function to show that $2^y$ is recursive. $\text{sg}(z)$ is computable by noting that $\text{sg}(0)=0$ and $\text{sg}(z+1) = 1$.


Infinite regular language Let $M$ be a DFA.

I would like to prove that $L(M)$ is infinite if and only if there exists a string $w \in L$ such that $|Q| \leq |w| \leq 2 \cdot |Q| $.

My idea was to use the fact that the shortest string in $L(M)$ is of size at most $|Q|$, but I am not sure precisely how I should use this. Or is there a different approach?

Thanks!

The proof makes use of the pigeonhole principle.

First suppose $L(M)$ is infinite. This means that for every $k \geq 0$ there exists a $w \in L(M)$ with $|w| \geq k$. Therefore there must in particular exist a $w$ with $|w| \geq |Q|$. Take the shortest such $w$ and let $w = a_1 a_2 \ldots a_k$. When reading $w$, $M$ will visit $k+1$ states $q_0, q_1, \ldots, q_k$ where $q_0$ is the initial state and $q_k$ is an accepting state. Since $k+1 \geq |Q|$, some state must occur at least twice in this sequence: Now consider the first such repeated pair, $q_i$ and $q_j$. We have that the substring $a_i...a_j$ has length at most $|Q|$. The string $a_1 \ldots a_i \ldots a_j a_i \ldots a_j \ldots a_k$ will be accepted, and its length is at most $2|Q|$.

Next suppose there is a string $w \in L(M)$ where $|Q| \leq |w| \leq 2 |Q|$. Again consider the states that $M$ will visit when reading $w$ and let $w = a_1 a_2 \ldots a_k$. As in the proof of the converse implication above, we notice that when reading $w$, $M$ will visit $k+1$ states $q_0, q_1, \ldots, q_k$ where $q_0$ is the initial state and $q_k$ is an accepting state. Since $k+1 \geq |Q|$, some state must occur at least twice in this sequence. Again, consider the first such repeated pair, $q_i$ and $q_j$. We have that for every $m \geq 0$ that the  string $a_1 \ldots (a_i \ldots a_j)^m a_{j+1} \ldots a_k$ will be accepted, and this proves that $L(M)$ is infinite.


If there is any sense of an optimal set of instructions in an ISA So there are One Instruction Set Computers, having only one (complicated) instruction like addleq, "add and branch if less than or equal to zero". And then there are extremely complicated Instruction Set Architectures (ISAs) with 100's of instructions like x86.

Most computers today I think use the x86 architecture, though ARM architectures seem like they are gaining some attention. I think x86 is popular (for one reason or another) because they have created these many instructions to handle specific use-cases, and so can be performance-optimized for specific common instruction scenarios.

However, I am interested in the fact that all logic can be boiled down to AND + NOT or OR + NOT. I'm not sure if this means you can implement a computer with just these two instructions, or if it's not possible to model things like ALUs using them. But it's interesting.

What I'm wondering though is if there is any notion of "optimal" in the architecture of an ISA. For example, it's a lot easier to represent things you can do in a computer with the let's say 20 or 30 or so regular operators like + and >= and =, etc. LLVM also shows you can have a pretty small instruction set, not taking into account the instructions with multiple different variations based on the datatype (int32 vs. int64, etc.). But either way, from a practical perspective I suspect most people don't use the 100's of x86 instructions, and instead use a standard small subset. Compiler architects probably do because they have the time and resources to do all the micro optimizations perhaps.

But then there are the optimizations in terms of processor speed. Implementing custom instructions like x86 does probably allows you to take advantage of hardware accelerations. So there is a balance.

My question is if there are any resources/papers/topics on "optimal" and "minimal" ISAs. Maybe they have like 10 or 20 instructions or something like that. Some minimal but not too minimal as in OISCs.

The paper you are asking for is:

  Patterson, David A; Ditzel; David R: The case for the Reduced Instruction Set Computer, Computer Architecture News, 8(6):25-33, Oct 1980. (non-paywalled copy).

Beware that it may be the paper you are asking for, but may not be the paper you want.  Almost everything it says is false, or has been debunked.  It is more of a humanities paper than a computer science paper.

There are ways of reducing the number of instruction bits that are fetched from DRAM (using more-or-less traditional compression techniques like Huffman encoding).  (And these kinds of concerns about minimizing instruction bits are evident in most "CISC" designs, as I described in a different question.)
 There are ways of minimizing the decode logic of a state machine (see for example the work of Villa, Kam, Brayton and Sangiovanni-Vincentelli, especially their 1997 book).  There are ways of minimizing the amount of power consumed by an instruction (for example, by increasing the number of different things that the instruction does, thereby better amortizing the power costs of fetching and decoding the instruction).

Finally, when there are ways of better representing instructions internally (for example to reduce decode power) it is trivial to do the translation from the "bad" instruction set to the "good" instruction set and cache the result. (Something x86 processors and many others have been doing since the late '80's (I can't find the academic references for this idea right now)).

What is rarely the case is that minimizing the number of instruction opcodes, or minimizing the number of addressing modes, is correlated with optimizing anything else about a computer design.


Help understanding ip address classes microsoft.com has the ip address 23.96.52.53

Since the first number is $23$, this is class A.
Does this mean microsoft owns all the addresses from 23.0.0.0 to 23.255.255.255 ?

The original division and allocation of IP addresses used a system called classful IP addressing. This is the division to which you are referring, in which a class A network would receive all addresses X.0.0.0-X.255.255.255 and have over 16.5 million host addresses. As designated below, the network bits in classful addressing are divided in 8-bit groupings.

The modern internet utilizes an alternative subnetting system called classless inter-domain routing (CIDR) to more efficiently allocate and distribute IPv4 addresses. This technique is based on variable length subnet masking (VLSM) which allows one to set arbitrary-length prefixes and accordingly allow address space to be allocated on bit lengths other than the previous 8 bit boundaries. This allows one to specify the most significant (i.e. network) bits with CIDR notation by notating the prefix by the number of bits designating the network, yielding the host bits by omission. We'll use your example for specific demonstration.

Utilizing ARIN to search the address number, we can see that the IP block in question is not, in fact 23.0.0.0 - 23.255.255.255, but 23.96.0.0 - 23.103.255.255 with a CIDR notation of 23.96.0.0/13. "/13" indicates that the first 13 bits of the IP address are used to specify the network address space and accordingly the remaining 19 bits specify the host space.

We'll convert the Dotted Decimal Notation (DDN) to binary to show how the math works. Keep in mind, binary is base-2, meaning that each bit is an exponentially higher value of 2:

27  26  25  24  23  22  21  20

-or-

128  64  32  16  8  4  2  1

Each octet has 8 bits, with 1 signifying that bit in use, 0 signifying it not in use. Any value 00000000 - 11111111 inclusive is valid with 00000000 representing 0 and 11111111 representing 255.

00010111.01100000.00000000.00000000           (23.96.0.0 in DDN)
00000000.00000111.11111111.11111111 +      (19 least significant or host bits)
00010111.01100111.11111111.11111111 =      (23.103.255.255 in DDN)


Regular Grammar and Regular Language From Wikipedia, Regular Language

All finite languages are regular.

and Also Regular Grammar, is a way to describe the Regular Language

Right regular grammar (also called right linear grammar).
Left regular grammar (also called left linear grammar).

From Wikipedia its Example :  a* b c* can be described as Regular Grammar..
but it generate infinite number of 'a's and infinite number of 'c's.
Recall Regular Language can be described by Regular Expression and Also Finite Language ..

This might be a language issue. In (mathematical) English, the statement all finite languages are regular means: if $L$ is a finite language then $L$ is regular. No implication in the other direction ("if a language is regular then it is finite") is implied.


SAT solver optimizations of DPLL for unsatisfiable formulas I am implementing a SAT solver based on DPLL algorithm, and it works fine on small formulas and larger satisfiable problems. My case split is based on a tree like structure, where every branch is tried one by one until solution for the problem is found or until every branch is tried.

So my problem now is that the above described approach does not terminate when trying to find a solution on large UN-SAT problems (so there shouldn't be a solution), therefore my program tries every possibility $2^n$, giving it a run time of years to solve UN-SAT problem with $50$+ variables (it would eventually terminate in years as I am not having any memory issues etc.).

My question is: what topics/implementations would I want to look at to speed up the tree processing or this case split process on unsatisfiable problems. Thanks.

Conflict analysis and clause learning and non-chronological backtracking should help a lot, for both satisfiable and unsatisfiable instances.  They discover large portions of the search space where no solution can reside and prune the search to avoid traversing those.

You could also try two-watched-literals unit propagation, but I'd try the others first, as I expect they'll make a bigger difference.


Is this grammar LR(1)? A bit confused about whether this grammar is ambiguous or not

C' -> C
C -> d C u C
C -> d C
C -> ε

I tried building the DFA for this but I get this in one of the states:

C -> d C DOT u C, $
    C -> d C DOT, $

Isn't this a shift-reduce conflict, so surely it means the grammar is not LR(1)? Or does it reduce regardless since $ and u are both in the follow set of C? Is this not a reduce-reduce conflict since it goes to C regardless?

This grammar (which isn't ambiguous) isn't LR(k) due to the right-recursion, thus it isn't LR(1).


Finding number of edges with weight less than k on the path between two nodes in a tree You are given a tree with $n$ nodes and $n-1$ edges. Each edge has a weight. There are $m$ queries. In each query you have to answer the following question:

How many edges are there in the path between node $a$ and node $b$ with weight less than $k$?

$a$, $b$, and $k$ vary in each query.  You're allowed to preprocess the tree to make it easy to answer each query.

Consider the tree with edges

          1
 weight=4/ \weight=5
        2   3
weight=4|
        4
weight=4|
        5

Between nodes 3 and 5, the total number of edges with weight less than 5 is 3, i.e. {1-2, 2-4, 4-5}.

I was trying to solve by brute force method by checking each path.

I want to know if there is a better way of solving this.

You can answer each query in time $O(\log^3 n)$, plus whatever time is needed to answer a lowest-common-ancestor query (a tricky $O(1)$-time solution exists, but you might as well go with the easier $O(\log n)$-time solution, since it doesn't hurt the final time complexity), after doing $O(n\log^3 n)$ preprocessing.

We only need counts from each vertex to the root

Let's call the number of edges of weight less than $k$ on the path from a vertex $v$ to the root $f(v, k)$.  We can calculate the desired final answer -- the number of edges of weight less than $k$ on the path from $a$ to $b$ -- using $f(a, k) + f(b, k) - 2f(lca(a, b), k)$, where $lca(u, v)$ is a the lowest common ancestor of $u$ and $v$.

From now on we will focus on answering the simpler question of computing $f(v, k)$.

Heavy-light decomposition

The heavy-light decomposition decomposes the tree into disjoint paths in such a way that at most $O(\log n)$ such "heavy paths" are visited on the path from any vertex to the root.  This can be accomplished with a DFS in $O(n)$ time.  The idea here is that, since the heavy paths are disjoint, if we have a way to quickly compute the number of edges of weight less than any given $k$ for each one, then we can nearly compute $f(v, k)$ for any $v$ and $k$ just by summing these counts over all heavy paths that we visit on the way from $v$ to the root.  And we do have a way to do this counting: Simply by sorting the edges within each heavy path by weight in a preprocessing step, we can later binary-search for any $k$ to count the number of edges of weight less than $k$ in this particular heavy path in $O(\log n)$ time.

But why only "nearly"?  Because we have so far ignored the possibility that $v$ might not begin exactly at the bottom of a heavy path -- it could begin part-way up.  We could try to "patch things up" by walking down to the bottom of the heavy path containing $v$, subtracting 1 from the count for each edge of weight less than $k$ that we see -- but this won't be worst-case efficient, since an individual heavy path can be as long as $n-1$ edges.  We need a way to handle this bottommost heavy path efficiently.

As noted by commenter xskxzr, the issue of beginning part-way up a heavy path is not only confined to the bottommost vertex $v$ in a path to the root -- it can also happen in the middle of such a path, such as in the path from 11 to 0 in the figure on the linked page.  Fortunately, the same trick, described next, works for both cases.

Fenwick trees of sorted lists

The subproblem we are now focussed on is: Given the ordered list of edge weights $x_1, \dots, x_m$ encountered while traversing down a particular heavy path, we want to preprocess this list to enable us to be able to later efficiently answer queries of the form "How many of the first $r$ elements are less than $k$?", with both $r$ and $k$ part of the query.  One way is to use a Fenwick tree which has as its elements not individual integers, but sorted lists of integers.

A "regular" Fenwick tree with single-integer elements takes $O(n)$ space.  Since each $x_i$ belongs to at most $O(\log n)$ buckets, increasing the size of the Fenwick tree's elements from single integers to sorted lists of integers fortunately only increases space usage by a $\log n$ factor.  The associative operation in a "regular" Fenwick tree is usually addition; in our Fenwick tree it's "set union".  For efficiency, all lists should be populated in a first pass, and then only sorted once, in a second pass.  This can be done in $O(n\log^2 n)$ time for a single heavy path, so $O(n\log^3 n)$ overall.

To process an $(r, k)$-query for a particular heavy path, a subquery in that heavy path's Fenwick tree is performed on each of the sequence of buckets found by stripping least-significant 1-bits from $r$, and the counts from these subqueries are summed.  That much is standard for Fenwick trees, but the individual subqueries are more complicated: Instead of just reading out the integer value from each bucket, we must binary-search the sorted list in that bucket for $k$; the leftmost position where $k$ appears (or would appear) tells us the number of edges of weight less than $k$ in that bucket.

An example might help: Suppose $r = 43$.  In binary, 43 is 101011 (32 + 8 + 2 + 1).  To answer a query for $r = 43$ (and some $k$ value), we would binary-search for $k$ in the following 4 buckets: 101011, 101010, 101000, 100000.  Each bucket is found by stripping the least-significant 1-bit from the previous bucket, so there cannot be more than $\log n$ subqueries.  Each subquery is a binary search, so cannot take longer than $O(\log n)$ time.  Finally, there are at most $O(\log n)$ heavy paths encountered on the path from any vertex to the root, so the worst-case time to compute $f(v, k)$ is $O(\log^3 n)$.


What algorithm to use, least waste when sawing wood planks Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 30cm 50cm and 20cm. Is there an algorithm for calculating the least waste? When using brute force it quickly escalates in time :(

Formally we have $N$ wooden planks each $L_1, \dots, L_N$ cm long. And we want to have $M$ pieces, $l_1, l_2, \dots, l_M$ cm long. How to minimize the waste?

This problem can be reduced to the binpacking problem (which is a special instance of the cutting stock problem, see @fade2black's answer)
The bins can represent the fixed size wood pieces, which are 100cm long in your example.
The items to be binned can be the list of needed wood lengths.
Minimizing for the minimal number of bins equates minimizing waste;

Let $L_M$ be the size of a bin, $L_{all} = \sum_{i=1}^N L_i$
Suppose there is a distribution of $L_i$ over $M_{min}$ bins, but it is not the minimum amount of waste.

Then there is a distribution of $L_i$ over $M_{minwaste}$ bins where $M_{min} < M_{minwaste} $
And then the waste can be expressed as $[M_{minwaste} * L_M - L_{all}] < [M_{min}*L_M - L_{all}] $
which simplifies to: $M_{minwaste} < M_{min} $
This contradicts our premise and its derivative of $M_{min} < M_{minwaste}$ .

Hence, $M_{minwaste}$ cannot be greater than $M_{min}$ and have less waste.

Python example using the binpacking module, note that binpacking is indeed NP-hard, as such the binpacking module is most likely using heuristiscs which will most likely result in approximation answers.
import binpacking
needed = [60, 30, 50, 20]
print(binpacking.to_constant_volume(needed, 100))

Outputs the following:
[[60, 30], [50, 20]]


Turing Machine DTime(log(n)) An Exercise from a Textbook:

  L3 := {ε,01,0011}

  is L3 ∈ DTime(log(n))

The answer says yes it is, it is even in DTime(1).

How is this possible? I would say it takes at least n steps to check the word. How is it possible to do it in less than n steps?

Your Turing machine just needs to read the first four symbols one the input tape that will be sufficient to to solve the problem $L3$.


Solving $T(n) = 2T(n/2) + T(n-1)/\log n$ I am interesting in the asymptotic rate of growth of the following recursion:

$$ T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n}, $$
with base case $T(1) = 1$.

I'm having trouble of solving this recurrence problem, it seems much more tricky than I initially thought, and I'm totally stuck after doing some unrolling. What is a good way to approach this question?

By comparison to the recurrence $T(n) = 2T(n/2)$, we see that $T(n) = \Omega(n)$. By comparison to the recurrence $T(n) = 2T(n/2) + n$, we see that actually $T(n) = \Omega(n\log n)$.

Now let us prove by induction that the other direction holds as well. I will interpret $T(n/2)$ as $T(\lfloor n/2 \rfloor)$. Suppose that $T(m) \leq Cm\log m$ for all $m < n$. Then
$$
T(n) \leq 2C\frac{n}{2}\log \frac{n}{2} + \frac{n\log n}{\log n} = Cn\log n + (1-C)n.
$$
For $C \geq 1$, it follows that $T(n) \leq Cn\log n$.

It seems that we have proved that $T(n) = O(n\log n)$, but actually the base case of the induction doesn't hold. However, this shouldn't be too hard to fix (left to the reader).


Why do we use big O rather than $\Omega$ when discussing best case runtime? When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ of an algorithm, we also attempt to bound $T(n)$ above and use $O$ notation.

Why don't we instead attempt to bound the best case runtime from below? Wouldn't it make more sense to put an upper bound on the worst case runtime and a lower bound on the best case runtime, as this will then give us upper and lower bounds on all cases?

I understand that both $O$ and $\Omega$ notations can be useful for discussing best/worst/average case runtime., and that we can put upper and lower bounds on the worst or best case runtimes, respectively. My question is about the convention in the field to list an upper bound rather than a lower bound for the best case runtime (for example, see here and here).

The symbols $O$, $\Omega$ and $\Theta$ mean at most, at least and exactly, respectively. What these bounds are about, is an entirely separate issue. They can be about best-case or worst-case performance, but you can use these symbols throughout mathematics. To describe a function, one of the things you can do is to give $O$ and $\Omega$ upper and lower bounds, independent of whether your function is related to computer science.

For example, to describe an complicated algorithm (or language) for which you don't have precise bounds yet, but for which you do have rough preliminary bounds, you can say: the best-case of this algorithm runs in $\Omega(n^2)$ and $O(n^3)$ (meaning no better than $n^2$ but no worse than $n^3$) and the worst-case runs in $\Omega(2^{\sqrt{n}})$ and $O(2^{n^{2}})$. This means: I don't know what the worst-case running time is exactly, but my analysis thus far puts it between $2^{\sqrt{n}}$ and $2^{n^{2}}$. Later, it may turn out that the worst-case running time was in fact $\Theta(2^{n})$, and then your $O(2^{n^{2}})$ upper bound, while correct, was not strict.


Basic question about branches and pipelines In which stage ( on an ideal 5-stage pipeline ) are branches and hazards handled? How much is the branch penalty for a branch hazard or data hazard. Is there different stages to find data hazards or branch hazards ( meaning for example branch hazards occurs on the 2th stage in the pipeline) or are all hazards detected at a specific stage?

The classic RISC pipeline resolves branches in the decode stage, which means the branch resolution recurrence is two cycles long. More information can be found in the Wikipedia article on the Classic RISC pipeline.


Proof of Demorgan's law how can i prove Demorgan's law (X+Y)'=X'. Y'?I already tried studying book but doesn't understand the first step so plz answer in detail.(beginner here)

In order to prove $A = B$, It is sufficient to prove that $A'B = 0$ and $A' + B = 1$. Try to think of why this should be the case intuitively. In case you are unable to understand, then think of $A$ and $B$ as sets, Boolean $+$ operation as set union operation and Boolean $.$ operation as set intersection operation.

Therefore, take $A = (X+Y)'$ and $B = X'Y'$.

So, $A'B = (X+Y)X'Y' = XX'Y' + YX'Y' = 0$.

Also, $A' + B = X + Y + X'Y' = 1$.

(Use the property $A + BC = (A + B )(A + C)$ for simplifying above expression.


"Not in big theta but in big O" Can somebody please help me understand ways I can attempt to find two functions f(x) and g(x) in which f(x) is in big O of g(x) but not big theta of g(x). I get that this is asking me to prove that f(x) isn't in big omega of g(x) but I really don't know where to start with this one. I tried to look for scenerios where there wouldn't be any positive constants. However, I had trouble doing that.

One of the answers to your question: $f(n) = n$, and $g(n) = n^2$.

Then $f(n) = O(g(n))$ but not $\Theta(g(n))$. This is because $n^2$ is an upper bound on $n$ , for all $n \geq 0$,  but it is not tight (actually we only need the inequality to be true for $n > N$ for some $N$, by the definition of $O()$).

By saying that the bound is not tight, what we mean is that we do not have  $cn^2 \leq n \leq c'n^2$, for large enough $n$'s (it should hold for all $n > N'$ for some $N'$ by the definition of $\Theta()$ if $n$ were $\Theta(n^2)$). Also $c$ and $c'$ are positive here and the following discussion.

Since $n^2$ is upper bound on $n$ it is easy to get $n \leq c'n^2$ part. But we can never get to the $cn^2  \leq n$ part. Even if we take $c$ very small,say 0.01 in the picture, at $n > 100$ it will not remain smaller. So we can never have $n$ between $cn^2$ and $c'n^2$ for all values $n>N'$. This is because we will always find some big number where $c'n^2$ will be above $n$.

$O()$ is just an upper bound, where as $\Theta()$ is a tight bound.  Also if we have $f(n) = o(g(n))$ then the bound in not tight yet it is an upper bound. Then $g(n)$ is a loose upper bound. If $f(n) = o(g(n))$ then any such pair of $f(n)$ and $g(n)$ will satisfy the condition of your question.


When does the function mapping a string to its prefix-free Kolmogorov complexity halt? In Algorithmic Randomness and Complexity from Downey and Hirschfeldt, it is stated on page 129 that

$\qquad \displaystyle \sum_{K(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$,

where $K(\sigma)\downarrow$ means that $K$ halts on $\sigma$, $\sigma$ being a binary string. $K$ denotes the prefix-free Kolmogorov complexity.

When does $K$ halt? I think it only halts on a finite number of inputs, since the classical proof on non-computability of the Kolmogorov complexity gives an upper bound on the domain of $K$. But then, the finite set of inputs on which $K$ halts can be chosen arbitrary (one just needs to store the finite number of complexities in the source code).

So is this sum well-defined? In other words, is the domain of $K$ well defined?

I think you are right; $K$ is a specific function which can not be computed. The author likely means to use some (arbitrary) approximative implementation; so no, this does not seem to be well-defined, if you are pedantic. You can also call it abuse of notation.

Consider this instead:

$\qquad \displaystyle \forall {M \in \mathcal{M}_K}.\ \sum_{M(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$

with $\mathcal{M}_K = \{M\ \mathrm{TM} \mid M(\sigma)\!\downarrow\ \implies\ M(\sigma)=K(\sigma) \}$ the set of all Turing machines that compute subfunctions of $K$.

In essence, this means: the bound holds no matter for which strings your implementation can compute the Kolmogorov complexity.

As Carl notes in the comments, it is plausible that the notation has nothing to do with halting or computing, as $K$ is not computable. Read $\sum_{K(\sigma)\!\downarrow}$ as sum ranging over the domain of $K$.


Design Hashing function from known distribution of bits to be set How to design Hashing function when the distribution for the bits that will be set are known before hand? Given that the number of bits to be set is constant. The intention is to minimize the hash collisions and resizing of the hash table.

Mentioned query is more of an open-ended question. What I am interested is in the known existing approach for such scenarios?

More description: Design a hashing function where the keys are formed from 64 bits. The number of bits $(l)$ that will be set is fixed which is $3 \leq l \leq 15$ of the 64 bits in the key. Further clarification, any $l$ bits in of the given 64 bit will be set.

Approximate distribution for the respective bit to be set is also known beforehand. The approximate probability of the $k^{th}$ bit will be set in the keys that will be inserted is known. In other words, for most keys that will be inserted in the hash table $k^{th}$ bit will not be set.

Implementation is to be done in C++ if this information helps in anyway.

I have tried with bit mixing from link which has the following function:

UInt64 MurmurHash3Mixer( UInt64 key )
  {
  key ^= (key >> 33);
  key *= 0xff51afd7ed558ccd;
  key ^= (key >> 33);
  key *= 0xc4ceb9fe1a85ec53;
  key ^= (key >> 33);

  return key;
  }

But the number of key collisions wasn't much affected. Also, the execution time worsened in comparison to hashing scheme that comes with std::ordered_map.

For my case, most of the keys have the property that last certain will never be set and the probability of initial bits will be set is lower than the bits in the middle section.

std::ordered_map - I believe uses the initial bits to map to a memory location. Since, many of keys share the property more time is spent in re-hashing.

There are 224,723,513,575,448 possible 64-bit bit-strings which satisfy the constraint that there are between 3 and 15 one-bits (inclusive). That number is approximately 247.675, so it could be represented in 48 bits. This compression is not particularly difficult, but it is much slower than the Murmur3 mixing algorithm you cite, whose speed seems to be a concern.

In any event, the compression won't really help you much (if at all). A good hash function will produced unbiased distribution of hash values for any subset of possible inputs; such hash functions are theoretically possible and, with appropriate caveats, practically achievable. (Tabulation hashing is a simple and effective technique, which is provably independent provided you have an appropriate source of randomness. But unless you have special requirements, you are probably better off using an existing hash library which has been tested and found to be unbiased.)

In practice, the C++ standard does not prescribe any particular hashing algorithm nor does it prescribe any particular mapping from hash values to buckets for unordered associative containers (there is no such thing as a std::ordered_map; there are std::map, which is ordered and therefore not a hash table, and std::unordered_map, which is a hash table). The implementations of the C++ standard library I know of use the identity function for hashes of all integer types. (Hash values are of type size_t, which means that values larger than the capacity of a size_t will be reduced modulo the size of a size_t; that will be the case for a 64-bit key on most 32-bit architectures.) Since that is likely to produce biased results in your case regardless of how the hash values are mapped to buckets, you probably are well-advised to use a specialized hash function, at least if you expect the hash tables to be large.


What are the applications of Rose trees? I recently found out about the Rose tree data structure, but just going off of a Haskell data definition and the tiny Wikipedia description of it, I've got some trouble understanding what applications a Rose tree might have.

For reference, the Haskell data definition:

data RoseTree a = RoseTree a [RoseTree a]

For those unfamiliar with Haskell -- it's a recursive data type definition with an arbitrary type a, where the type constructor is provided with a literal of type a followed by an optionally empty list of type RoseTree on the same type a.

The way I see it:

This data structure is unordered by default (although I assume most practical applications do implement some form of ordering for searching)
The data structure doesn't enforce a fixed number of nodes per layer at any point, except the global root, which must have a single node

Given that minimal amount of information, I'm having trouble figuring out when one might use this type of tree.

In addition to the question in the title, if search is indeed implemented in most applications of a Rose tree, how is this done?

You seem to have an overly "data structures and algorithms" mindset.  Not every tree is some kind of search tree.  Data structures are often designed to correspond to or capture aspects of a domain model.

S-expressions are almost exactly rose trees. (Or rather, I would say how they are typically thought of is as rose trees.  Wikipedia is correct in saying they are more like binary trees, but what you might call "proper" S-expressions are only slightly different from rose trees.)  At any rate, you can use them as a generic representation for an abstract syntax tree.  The benefit of doing this is that you can easily write generic operations, e.g. "find all variables" or "swap parameters" or "rename this symbol".  It's also extensible in that adding a new type of node to your abstract syntax often doesn't require really changing anything.  The downsides are there aren't really any constraints, so it doesn't a priori prevent you from writing nonsense.  This can be mitigated for users by standard abstract data type techniques, but the implementer of transforms and such must deal with the unstructured representation even though they "know" that the input is structured via a data type invariant.  Of course, when that certainty is misplaced (possibly because things have changed), the errors tend to be unpredictable and hard to debug.

In practice, while the Data.Tree module in the standard libraries provides a rose tree, almost no one uses it in the Haskell community.  Defining custom data types that explicitly capture the constraints is so easy that there is little reason to use a generic library type.  Further, there has been an enormous amount of research and practice around performing generic operations over custom types which eliminates many of the benefits of using a generic representation.  Finally, Haskellers tend to be very much in favor of explicit, enforced constraints and are willing to pay to get it.

To answer your last question, oftentimes searching an AST is unimportant and/or the ASTs are generally assumed to be small enough that just walking the whole thing is acceptable.  Admittedly, it's not uncommon to collect definitions in a separate data structure with references into the AST which could be viewed as a sort of index.  Similarly, some optimization passes will (usually locally and temporarily) build up indexes to simplify and speed up their operation.  The structure of the AST corresponds to the input and so it can't be "rebalanced" or anything like that.  As such, it's uncommon for the AST itself to contain indexing information or information to help "searching".


NP-hardness of maximum set cover with even/odd coverage requirement Given universal set $U=X \cup Y = \{x_1, \ldots, x_{n_1} \} \cup \{y_1, \ldots, y_{n_2}\}$ where $X \cap Y = \emptyset$
and sets $\mathcal{S}=\{s_1, \ldots, s_m\}$ such that $s_i \subseteq U$ for all $i=1,\ldots,m$ and integer $k \in \mathbb{Z}^{+}$.

Find $\mathcal{C} \subseteq \mathcal{S}$ (denote $Z = \cup_{s \in \mathcal{C}} s$) that maximizes

$|\{ z \in Z \mid (z \in X \text{ and is covered even times by } \mathcal{C}) \text{ or } (z \in Y \text{ and is covered odd times by } \mathcal{C} )\}|$

s.t

$|\mathcal{C}| = k$

In other words, we consider an element to be covered if it satisfies the odd/even coverage requirement according to its membership ($X$ or $Y$).

This problem differs from the standard maximum set cover in the definition of "covering an element".

Is this problem NP-hard? Is so, how to prove it?

One can rephrase your question as follows:

  Given a matrix $A$ and a vector $b$ over $GF(2)$, find a vector $x$ of weight $k$ such that $|Ax-b|$ is as small as possible.

A very similar problem was shown to be NP-complete by Stadnicki on cstheory:

  Given a matrix $A$ and a vector $b$ over $GF(2)$, does there exist a vector $x$ of weight at most $k$ such that $Ax = b$?

This implies that your problem is intractable as well.


Equivalent regular grammar with minimum number of nonterminals Given a set of terminal symbols $\Sigma=\{a,b\}$ and a set of nonterminal symbols $N=\{S,A,B\}$ with start symbol $S$, then the two following sets of production rules are equivalent:

$S\to aA$
$A\to aA$
$A\to bB$
$B\to aA$
$B\to bB$
$B\to \epsilon$

and

$S\to aA$
$A\to aA$
$A\to bA$
$A\to b$

They both match any string starting with $a$ and ending with $b$, but the second set of rules has only two nonterminals instead of three.
Is there a standard way to convert an arbitrary (regular) grammar to the equivalent grammar with the smallest number of non terminals?
I don't think this can be achieved by the rules for Chomsky normal form.

A regular grammar corresponds directly to a finite automaton, mapping each non-terminal to a state. So this question is equivalent to asking how to minimize the number states in a finite automaton. Unfortunately, minimizing NFAs is hard. See, for example, Gregor Gamlich, 2007.


Finding largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$ I need to find largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$ where $N$ can be as large as $10^{18}$.

I tried this approach , but is too slow.
Finding the just smallest prime number to $N$, as its $\frac{\phi(i)}{i}$ value is $\frac{i-1}{i}$, which is maximum in the range. (See Maximum of ϕ(i)i\frac{\phi(i)}i)

So, I was wondering if there is any other faster way to find the maximum value. More precisely I need the value of i where $\frac{\phi(i)}{i}$ is maximum.

Since you know that the maxium value is achieved when $i$ is the largest prime smaller than $N$, your problem is equivalent to finding the largest prime smaller than $N$.

There are many ways to test for primality, so presumably you could just take your favorite primality test and run a for loop from $N-1$ downwards, to find the first number which is prime.

Perhaps I do not understand what you are asking for.


Closure of regular Language - Transition Function : Sipser Proof I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser.

I have doubts regarding how he wrote the transition function.

When $Q \in F_1$ and $a=\epsilon$ he wrote $\delta_1(q,a) \cup \{q_2\}$. I couldn't understand why its so. When the input is epsilon, the state moves to $q_2$ and what is the need for writing that $\delta_1(q,a)$

Also if that is so, the $A^*$ example he wrote for the transition function $\{q_1\}$ only  when $q=q_0$ and $a=\epsilon$

The idea is that whenever $A_1$ reaches an accepting state, it "guesses" that this is a good place to split the word, and run the second part in $A_2$. But maybe this guess is wrong? There are many ways to split a word, and you only need one such splitting to work.

As an example, consider the languages $L_1=(a+b)^*a$ and $L_2=b(a+b)^*$. Now consider what would happen in your suggestion with the word $aab$.
After reading the first $a$, $A_1$ will be in an accepting state, so it will move to the initial state of $A_2$, and upon reading the second $a$, will move to a rejecting sink.

However, as Sipser suggests, $A_1$ may continue using $\delta_1$ for the second $a$ as well, and only then move to $A_2$.

Same goes for the construction for Kleene star.


Martin-Löf randomness characterization In his 1973 paper On the notion of a random sequence, Levin states (without proving) a characterization of Martin-Löf randomness by writing

  Theorem 3. A sequence $\alpha$ is random w.r.t. the distribution $P$ in the Martin-Löf sense if and only if the probability ratio $P(\alpha_n)/ R(\alpha_n)$ is bounded below

where $R$ is the universal semicomputable (semi)measure.

I feel a bit confused how this ratio could not be bounded below, being the ratio of two positive quantities it should always be bounded below by $0$.

The ratio should be bounded below by a positive constant. Equivalently, its infimum should be positive.


pseudocode to split number value to array of numbers How to write a pseudocode to split a number value to array of numbers? Let's say the number value is 12345. I need to convert it into [1,2,3,4,5].

num_to_arr(num):
   length_of_arr = log(num)+1 //log(num) base 10
   arr[length_of_arr]
   digit = 0

   while num > 0:
      digit = num % 10
      arr[length_of_arr - 1] = digit
      length_of_arr = length_of_arr - 1
      num = num / 10

return arr

This should do the job.


SSTF disk scheduling algorithm? What if lowest seek times are equal in either direction? Using the Shortest-Seek-Time-First (SSTF) disk scheduling algorithm (where we select a request with a minimum seek time from the current head position), what happens if the requests in both directions from the current head position are equal?

For example, if the head position is at 25, and the nearest positions are 5 and 45, how do we determine which one to select?

Thanks

Short answer: Depends on implementation.

Long answer: Ties could be broken randomly, or some fixed direction might be preferred. A popular strategy is to select that position first which does not require the head to change direction (since changing direction could take more time). So suppose that the head has moved from 20 to 25, it might prefer 45 next instead of 5 (since it was going towards the higher side). It could also depend on what the further instructions are going to be. Basically, the answer depends on what tie-breaking policy is selected in the implementation, and how complicated the implementation can be.


Solve the online unweighted 0-1 knapsack problem efficiently I have $n$ items and a bin of size $B$ units. Each item $j$ consumes $w_j$ units of $B$ when placed into the knapsack. The item appears one-by-one in an online fashion. Once item $i$ appears, we must either place it into the bin (irrevocably) or ignore it. The objective is to maximize the number of items placed into the bin. (All inputs are positive integers.)

The offline algorithm is easy: place the items in the order $w_1\leq w_2\leq\cdots\leq w_n$ until the bin is full.

How can I solve this problem in an online fashion? My approach is to randomize the choices: once item $j$ appears, place it into the bin with probability $p_j$ and ignore it otherwise.

Well as you already noticed, or at least didn't mention, it is easy to see that there is no deterministic competitive Algorithm for your problem. (Counterexamples only need two items, and you can use the fact that the algorithm is deterministic.)
Your approach taking randomization actually isn't enough as some difficulties cannot be overcome by randomization. But there are a few relaxation models of your problem.
Some of those, and a few details to my answer can be found in the paper by Susanne Albers, Arindam Khan and Leon Ladewig named "Improved Online Algorithms for Knapsack and GAP in the Random Order Mode" (see section 1.1).


Does MMU contain and manage CPU caches? I read about Virtual Memory in various CS references, however I'm still not sure whether CPU caches such as TLB, L1 and L2 are integrated within MMU. Also I don't know if the hit/miss operations are managed by hardware (i.e MMU) or by software (i.e OS).

Does anyone have any idea?

First the term MMU refers to many different thing (more on later below). For now let's defined MMU as "virtual to physical address translation".

The caches L1 and L2 are always managed in hardware, however note that for proper operation the OS still has to interact with the cache on some occasions (notably when using DMA). An important point to be aware of is that depending on whether the caches are virtually or physically indexed, they have a different relationship with the MMU. Indeed a virtually indexed cache (typically L1) will usually be accessed by the CPU without going through the MMU and it will not only contain the data but also the security bits associated with the MMU (privilege bit, read/write, cacheability, etc). On the other hand, a physically indexed cache must come after the address translation and does not care about the MMU at all. This also applies to higher levels (L3 and L4) which are always physically tagged (and sometimes outside the CPU die).

Thus a typical CPU will have the core with a memory bus connected to the L1 (which is typically split between data and instruction, but this is not important here). On cache miss, the L1 will issue read/write on a bus that goes through the MMU then L2, L3, L4 and finally DRAM.

The MMU itself may consist of different things. The simplest forms of MMU are just segmentation and PMU (protection memory unit). More advanced forms of MMU include a TLB so as to support paging. The TLB itself is always a hardware component (essentially just another cache). However there are two very different ways of managing the TLB:

in hardware: the MMU has a "page table walker" that can issue read to the memory to load TLB entries on a miss (this includes x86, ARM, etc)
in software: the MMU triggers a CPU exception on a TLB miss, and then the OS does the page table walk in software, fills the TLB with the entry and return from the exception (this includes MIPS)


How can I translate this quantified logical expression into english I was reading chapter-1 The Foundations: Logic and Proofs from this book.

The chapter gives example of translating English sentence : "There is a woman who has taken a flight on every airline in the world." as follows:

Introducing variables : w for women, f for flight, a for airline
Let P(w,f) : “w has taken f”
Let Q(f,a) : “f is a flight on a.”
Translation : ∃w∀a∃f (P(w,f ) ∧ Q(f,a))

I did understood above. Next it gives example of translating negation of above sentence : "There does not exist a woman who has taken a flight on every airline in the world.", which it solved as follows:

¬∃w∀a∃f (P(w,f ) ∧ Q(f,a)) ≡ ∀w¬∀a∃f (P(w, f ) ∧ Q(f, a))

                            ≡ ∀w∃a¬∃f (P(w, f ) ∧ Q(f, a))

                            ≡ ∀w∃a∀f¬(P (w, f ) ∧ Q(f, a))

                            ≡ ∀w∃a∀f (¬P(w, f )∨¬Q(f, a))

I thought their can be straight approach for this translation instead of going through negation. Anyways though my problem is I am unable to interpret the final translation ∀w∃a∀f (¬P(w, f )∨¬Q(f, a)) in plain English.

"Every woman has either not taken all flights or out of all the flight she has taken are not there on some airline." Is this correct? But if yess, it still does not make me much sense. Anyone?

The negation is that every woman has an airline that she has never flown with. This is equivalent to saying that, for every woman there's an airline with the following property:

for every flight in the whole world, either the woman was not on that flight (regardless of what airline operated it) or the flight was not operated by that airline (regardless of whether the woman was on it or not).

That is, there was no flight by the airline in question that the woman was on.

This is not quite the same as what you have.


Special case of subset sum in $O(n)$ A sorted array $A[1..n]$ is given. Each element of $A[i]\in \mathbb{N}$, and for each $A[i],A[j]$ we have $A[i]+A[j]\leq n$. Find two elements $A[i], A[j]$ such that $(A[i]-i)+(A[j]-j)=0$. Give a deterministic $O(n)$ time algorithm for this problem.
I tackle with this problem as follow :
Calculate each $A[i]-i$ , and insert it into hash table $T$ that take $O(n)$ , then one time traverse $A$ such that to find and element that $A[i]-i=T[i]$. Each search take $O(1)$ in expected, but we must give a deterministic in $O(n)$.

The assumptions $A[i] \in \mathbb N$ and $A[i] + A[j] \leq n$ together imply that $0 \leq A[i] \leq n$, and so $-n \leq A[i]-i \leq n$. This suggests maintaining an array $B[-n],\ldots,B[n]$, initialized with zeroes. We go over the elements of $A$ one by one. We put $B[A[i]-i] = i$, and then check whether $B[i-A[i]]$ is non-zero, say equal to $j$. If so, then $i-A[i] = A[j] - j$, and so $A[i] - i + A[j] - j = 0$. (This allows $i = j$; if you want to disallow it, reverse the order of these two steps.)


Why is 2s complement of 000 equal to 111, but 9s complement of 000 is not 888? I'm pretty confused so I hope I don't mix up the different terms here.

The two's complement representation of decimal 0 is simply 000

The two's complement of 000 is 111

I imagine that complementing a number is equivalent to flipping bits in binary

The nine's complement of 000 is 999

This is what confuses me. Are two's complement and nine's complement similar (except for the base change obviously)?
If they are, then I'd expect the nine's complement of 000 to be 888 because 8 is the biggest digit in radix 9 and therefore the complement operation would assign the highest digit (8) to the lowest value input (0) [I imagine a folding from the center]

Obviously this is totally wrong but I'm not sure which part I've misunderstood.

You are very confused due what is simply poor terminology, to be honest. Both your statements 2 and 3 are false due to the same misunderstanding.
For each base $b$ there are two mainstream variants of the 'complement', the radix complement and the diminished radix complement.
The two most common bases in computer science are base $2$ and base $10$. Confusingly, the definitions usually used are:

one's complement: the diminished radix complement of base $2$
two's complement: the radix complement of base $2$
nine's complement: the diminished radix complement of base $10$ (not $9$!)
ten's complement: the radix complement of base $10$.


Encoding a "not-k-out-of-n" constraint for SAT solvers I'm finding myself needing to encode a "not-k-out-of-n" constraint in a SAT solver.

The "at-most-k-out-of-n" constraint for SAT solvers is something I can find research about -- this paper by Frisch and Giannaros, for example.

Given an "at-most-k-out-of-n" tool, I can get an "at-least-k-out-of-n" tool by inverting all the terms.  With both tools, I can get a "k-out-of-n" tool by having both the "at-most-k" and "at-least-k" constraints.

But I don't see how I can encode a "not-k-out-of-n" constraint.  If I use "at-most-(k-1)" and "at-least-(k+1)", then obviously I'm going to get no solutions.

Is there a simple transformation here that I'm missing?

Assuming you work in CNF, construct  "at least $k+1$-out-of-$n$" and add "or $p$" to each disjunction. Do the same for "at most $k-1$-out-of-$n$" and add "or $q$" to each disjunction.

Then add one extra term to your main conjunction, $\neg p \vee \neg q$.


How to evaluate all possible groups of adjacent tiles in 2D array? I'm working on a tile based game idea in Javascript. It's a math puzzle game where players move around tiles with numbers on them, and the goal is to connect groups of tiles that have a sum of certain goal number, for example 5 or 7 or 9.

However, I'm stuck on the algorithm to detect these sum groups. I know how to do a flood fill algorithm using recursion to detect a group of adjacent tiles, like in the same game. But I don't know how to iterate through all the possible permutations of possible groups, and what is the best way to approach this?

Because the problem is that adjacent tiles form a group, but within that group of tiles there are many possibilities for sub groups. See tiles example below

Tile letters     Contains numbers    Represented as graph
+---+---+---+    +---+---+---+
| A | B | C |    | 1 | 5 | 2 |       1---5---2
+---+---+---+    +---+---+---+       |   |
| D | E | . |    | 2 | 1 | . |       2---1
+---+---+---+    +---+---+---+       |
| F | . | . |    | 4 | . | . |       4
+---+---+---+    +---+---+---+

So the group is all the tiles A though F, and a subgroup could be A, B and E (1+5+1) but also A, D and F (1+2+4). But A, C and F is not a possible group because those tiles are not adjacent. I suspect it could maybe be approached like it's a graph problem. But then I still don't know how to handle the many possible circular nodes.

So my question is; How to systematically go through and evaluate all possible permutations? Is there an algorithm for something like this? Or can someone explain how to approach this problem?

EDIT:
I've put my code in the jsfiddle in the link below. It uses flood fill from a starting tile, in the example tile with nr 2. Then for each cell it counts to 15 and uses the bits of that counter to flood-fill to the 4 adjacent tiles (up,down,left,right). However it doesn't work properly because it doesn't consider branching paths. For example, in the jsfiddle example the combination 3-2-4 is never evaluated.
https://jsfiddle.net/wu6p49r2/

I know how to do it by hand, see examples below. But what would the algorithm look like, to systematically gather these possible adjacent combinations starting at A?

Tiles ex.1    Tiles ex.2        Tiles ex.3
+---+---+     +---+---+---+     +---+---+---+
| A | B |     | A | B | C |     | A | B | C |
+---+---+     +---+---+---+     +---+---+---+
| D |         | D | E |         | D | E |
+---+         +---+---+         +---+---+
                                | F |
                                +---+
All possible adjacent combinations,
starting at A:

A             A                 A
A-B           A-B               A-B
A-D           A-B-C             A-B-C
A-B-D         A-B-E             A-B-E
              A-B-C-E           A-B-C-E
              A-B-E-D           A-B-E-D
              A-B-C-E-D         A-B-C-E-D
              A-D               A-B-E-D-F
              A-D-E             A-B-C-E-D-F
                                A-D
                                A-D-E
                                A-D-F
                                A-D-E-F

I suggest you use a search algorithm on the following statespace: the state is a set of adjacent tiles whose numbers sum to 7 or less; it is possible to transition from state $s$ to $s'$ if $s'$ is obtained by adding to $s$ one tile that is adjacent to some tile in $s$.  The initial state has the empty set $\emptyset$, and it can transition to any state containing a single tile.

Then, use a search algorithm, such a depth-first search or breadth-first search, to explore all states reachable from the initial state.  You can store the reachable states in a hashtable.  Whenever you discover a new reachable state, check if the numbers on its tiles sum to 7.  If they do, you have found a valid solution.

As an optimization, you can use flood-fill to find all of the groups (connected components), then apply the above algorithm separately to each group.


strange choice of constant when showing $an + b = O(n^2)$ ("Introduction to Algorithms" book) In the third edition of Introduction to Algorithms, the authors state:

  ... when $a$ > 0, any linear function $an+b$ is $O(n^2)$, which is
  easily verified by taking $c = a + |b|$ and $n_0 = max(1, -b/a).$

[In the above, $c$ and $n_0$ come from the standard definition of big-oh:

$f(n)$ is in $O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le cg(n)$ for all $n \ge n_0$.]

I have no trouble accepting that $an+b \in O(n^2)$, but I'm questioning the motivation/origin of the weird choice of $n_0$.

If we assume that $ n \ge 1$, then, since $a > 0$, we have $an^2 \ge an$ and since $n^2 \ge 1$ we have $|b|n^2 \ge |b| \ge b$, implying that $(a+|b|)n^2 \ge an+b$. So it seems that $n_0$ could simply have been taken as $1$. Or am I messing up somewhere?

Because of the requirement $an+b>0$. The definition requires $0 \leq f(n)$.


Term for shifting work to idle machines I am looking for a term here. A while ago, i was told about a network in which all the computers are connected in parallel, and when a computer is idle, the central server sends heavy cpu usage tasks to that idle computer.

This is often used in pharmaceutical companies working on protein structure configurations, or as the CS community more commonly knows, the bit mining community.

Any who, i know this is often called grid computing, however there was another name for it. Scapegoating? or something like that. Not quite sure. The term has really been bugging me. Can you guys help me out?


The fastest algorithm for intersection of two sorted lists? Say that there are two sorted lists: A and B.

The number of entries in A and B can vary. (They can be very small/huge. They can be similar to each other/significantly different).

What is the known to be the fastest algorithm for this functionality?

Can any one give me an idea or reference?

Hwang and Lin's Algorithm (A simple algorithm for merging two disjoint linearly-ordered sets (1972) by F. K. Hwang , S. Lin) is the reference on how to merge (or intersect) ordered lists of unequal sizes with (possibly) fewer comparisons.  It works by calculating a stride from the ratio m/n and doing the comparison against that element in the larger list; for instance if m/n = 4 it will compare the fourth element of the larger list against the first of the other, and either eliminate all 4 elements or do a binary search within them for the correct insertion/intersection point.

It neatly covers the continuum from merging equal-sized lists with the usual algorithm to merging a list of one element into a list of n with a single binary search.


How to prove that a problem is undecidable by using the Halting problem? I cannot understand how to reduce the halting problem to a property to show that is undecidable.

For example, I have this property of a Turing Machine and I have to prove if it's recursive or not:

"M eventually enters the fifth state in its rule list when executed on an empty tape"

How can I do it? Do I have to reduce it to a halting problem or vice-versa?

Thanks in advance.

When you reduce problem A to problem B, you show that B is at least as hard as A. (It's sort of like a proof by contradiction: if B were any easier, then A would become just as easy.) And undecidability is about as hard as you can get, in computer science.

So what you want to do here is:

Assume you have an oracle for the "fifth state problem"
Show that you can solve the Halting Problem with this oracle

It doesn't matter how long it takes or how many times you call the oracle, for this problem (since all you care about is decidability)

The Halting Problem is undecidable
Therefore, the "fifth state problem" is also undecidable

Here are a few hints to get you started:

You can reorder the states in a Turing machine without really changing anything important
If a TM has less than five states, you can add new "dummy" states that are never used, without really changing anything important
A TM never needs more than one halting state
The question "does this TM halt on empty input?" is a variant of the Halting Problem that is also undecidable


On satisfiability for 2-variable FOL being NEXPTIME-complete Let $\mathbf{FO^2}$ be the fragment of first-order logic consisting of sentences with at most two variables and no function symbols. It is well known that satisfiability for $\mathbf{FO}^2$ is decidable (see [1], for instance). Furthermore, in that same paper, it is argued that $\mathbf{FO^2}$ satisfiability is $\mathbf{NEXPTIME}$-complete, and that this result follows from these two lemmas:

Satisfiability for $\mathbf{FO^2}$ is in $\mathbf{NTIME}(2^{O(n)})$.
Satisfiability for $\mathbf{FO^2}$ has a lower complexity bound of the form $\mathbf{NTIME}(2^{cn/\log{n}})$ for some positive constant $c$.

I don't have a lot of background in complexity theory, so this has left me with two questions:

Is it easy to see that these two lemmas imply $\mathbf{NEXPTIME}$-completeness?
Is this result not contradictory? By definition, $\mathbf{NEXPTIME} = \bigcup_{k \in \mathbb{N}}\mathbf{NTIME}(2^{n^k})$, and by the non-deterministic time hierarchy theorem we have for any $i, j \in \mathbb{N}$ that $\mathbf{NTIME}(2^{n^i}) \subsetneq \mathbf{NTIME}(2^{n^j})$ if $i < j$. So I'm wondering how a problem complete for the class can lie at the "lowest rung" of the ladder - is this because Karp-reductions can blow-up the size of an input polynomially?

REFERENCES

[1] On the Decision Problem for Two-Variable First-Order Logic - Grädel, Kolaitis and Vardi

Regarding your first question: I haven't read the paper, but I guess that the proof of the second lemma is by a polynomial time reduction from a generic $\mathbf{NEXPTIME}$-hard problem. This establishes $\mathbf{NEXPTIME}$-hardness. Membership in $\mathbf{NEXPTIME}$ is by the first lemma. Regarding the second question, your guess is correct.


Calculating the number of non-intersecting routes in an Euclidean graph I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.  I found a geometric proof that every optimal TSP solution contains no intersections.

How many non-intersecting routes could be there? Or in other words: what is the probability to guess an optimal solution to a TSP problem if we just enumerate or sample non-intersecting routes?

Edit: I want to ignore the case that D.W. mentioned. For every path that you can swap between two neighbors vertices(If we represent the path as an array of vertices so neighbors will be two vertices with consecutive indexes) without changing its non-intersecting quality, all of those paths will be considered as one.

Edit I found that this kind of removing crossings from the graph also know as 2-OPT

There are exponentially many such routes.

Think of a sequence of $n$ diamonds.  At each diamond, you can go either left or right, independently of what you do at all other diamonds.  This leads to $2^n$ paths, each of which is non-intersecting.  Now the complete graph on those vertices contains all of these paths, plus some more, so this is a lower-bound on the number of non-intersecting paths.

Therefore, you can't hope to find the optimal one in polynomial time by guessing or enumerating non-intersecting routes.

You probably could have guessed or suspected this, from the fact that Euclidean TSP is NP-complete....


Encoding (binary) trees using lambda calculus I'm new to lambda calculus, and I read all kinds of interesting stuff about encoding data types as functions. Church booleans, numbers and lists.
https://en.wikipedia.org/wiki/Church_encoding

Is there a way to encode (binary) trees?

I'll choose to encode binary trees with data in the internal nodes.
Intuitively, a tree is either empty leaf, or a triple (data,left subtree,right subtree).

The corresponding Church encoding is:

$$
\begin{array}{l}
{\sf Empty} = \lambda e b. e
\\
{\sf Branch}\ x\ l\ r = \lambda e b. b x (l e b) (r e b)
\end{array}
$$

For instance, ${\sf Branch}\ 1\ {\sf Empty}\ ({\sf Branch}\ 2\ {\sf Empty}\ {\sf Empty})$ is an encoded tree. You can easily reduce it to a normal form, if wanted, resulting in $\lambda e b. b \ 1\ e\ (b\ 2\ e\ e)$.

Indeed, the normal form of a tree obtained from the above "constructors" will always start with $\lambda e b.$ and then proceed with the tree where the variable $b$ denotes a "branch" and variable $e$ denotes the empty tree.

To use an encoded tree, you can simply apply it as in $t\ E\ B$, providing two suitable terms $E,B$. This will compute a so-called "fold" of the tree, using constant $E$ and ternary function $B$ over the tree $t$.

For instance, $t\ 0\ (\lambda x l r. x+l+r)$ will result in the sum of all the numbers in the tree $t$, assuming $t$ only contains numbers as data.

It takes a while to convince oneself that this encoding indeed lets us do "whatever we want" with the tree, i.e. run any algorithm over a tree. For primitive recursive algorithms, we can use the encoding itself, directly. For more general algorithms, we can use a fixed point combinator on top of that.

This encoding can be generalized to all the algebraic data types defined through (positive) recursion. Moreover, the encoding can be typed in System F.
It is really general.

If you are familiar with some typed functional languages (such as Ocaml or Haskell), I'd recommend you try to implement a "fold" function on trees (with data in the nodes, or in the leaves), or on other algebraic data types. It's a nice exercise which I believe can help a lot in understanding the encoding in its generality.


Are all integers kept in 2's complement form in all microprocessors? Are all integers kept in 2's complement form in all microprocessors or do microprocessors use 1's complement form and unsigned integer form too?

If there was the keyword "almost" attached to the question then answering it could have been much more easy. As people have mentioned in the comments that nothing can be said with certainty about "all" the processors but yes majority of them do.

2s compliment is definitely preferable over the 1s compliment as it provides you a better range for instance if you have 8 bits the you can represent numbers in the range -2^7 to 2^7-1 with it (1 bit being for the signed bit). its interpretation also is easy and quick for the processors.

However for floating point numbers most processors use a different strategy to save them efficiently. This post would fall short if I needed to explain about them but matter of fact they don't use 2s compliment they rather have the concept of exponential, mantissa and signed bit. And there are 2 commonly used variant of these known as the single precision and double precision floating point representation which are technically same and vary only by the range they can represent. If you want to read further about this you can visit https://steve.hollasch.net/cgindex/coding/ieeefloat.html (not my website, but the website explains the whole thing fabulously).

Let me know if I could help you further in this regard.


Dynamic loading vs. dynamic linking? What is the difference between dynamic loading and dynamic linking?

Both systems seem to allow shared libraries, but I am struggling to differentiate between them.

Dynamic linking is performed at the time of program loading only and uses compile-time established names.  Dynamic loading can be done at any point in program execution.

From wikipedia:

  Unlike static linking and loadtime linking, this mechanism allows a computer program to startup in the absence of these libraries, to discover available libraries, and to potentially gain additional functionality.


Algorithmic intuition for logarithmic complexity I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$.

In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of the list.
$\Theta(n)$ is where I'd walk the entire list once, and $\Theta(n^2)$ is walking the list once for each element in the list.

Is there a similarly intuitive way to grasp $\Theta(\log n)$ other than just knowing it lies somewhere between $\mathcal{O}(1)$ and $\Theta(n)$?

The $\Theta(\log n)$ complexity is usually connected with subdivision. When using lists as an example, imagine a list whose elements are sorted. You can search in this list in $\mathcal{O}(\log n)$ time - you do not actually need to look at each element because of the sorted nature of the list.

If you look at the element in the middle of the list and compare it to the element you search for, you can immediately say whether it lies in the left or right half of the array. Then you can just take this one half and repeat the procedure until you find it or reach a list with 1 item which you trivially compare.

You can see that the list effectively halves each step. That means if you get a list of length $32$, the maximum steps you need to reach one-item list is $5$. If you have a list of $128 = 2^7$ items, you need only $7$ steps, for a list of $1024 = 2^{10}$ you need only $10$ steps etc.

As you can see, the exponent $n$ in $2^n$ always shows the number of steps necessary. Logarithm is used to "extract" exactly this exponent number, for example $\log_2 2^{10} = 10$. It also generalizes to list lengths that are not powers of two long.


Set Similarity - Calculate Jaccard index without quadratic complexity I have a group of n sets for which I need to calculate a sort of "uniqueness" or "similarity" value.  I've settled on the Jaccard index as a suitable metric.  Unfortunately, the Jaccard index only operates on two sets at a time.  In order to calculate the similarity between all $n$ sets, it will require in the order of $n^2$ Jaccard calculations.

(If it helps, $n$ is usually between 10 and 10000, and each set contains on average 500 elements.  Also, in the end, I don't care how similar any two specific sets are - rather, I only care what the internal similarity of the whole group of sets is. (In other words, the mean (or at least a sufficiently accurate approximation of the mean) of all Jaccard indexes in the group))

Two questions:

Is there a way to still use the Jaccard index without the $n^2$ complexity?
Is there a better way to calculate set similarity/uniqueness across a group of sets than the way I've suggested above?

An option would be to use the Signature Scheme of [1], size-based filtering: a scheme which uses size information to reduce the number of set pairs that need to be considered.

They also experiment with a weighted form; where weights are IDF-based.

[1] Arasu, Arvind, Venkatesh Ganti, and Raghav Kaushik. “Efficient Exact Set-similarity Joins.” In Proceedings of the 32nd International Conference on Very Large Data Bases, 918–929. VLDB  ’06. VLDB Endowment, 2006


Does an enumerator print the first occurrence of a word in finite time? For a proof I need to use the fact that every word in the language of an enumerator occur on the output paper in finite time. Is it true?
For example, the language of the natural numbers in decimal representation. Can the enumerator print the odd numbers first and then the even numbers? (if yes, I am wrong)

$1, 3, 5, 7, ..., 2, 4, 6 ,8, ...$

As I know, we get to the even numbers but not in finite time (maybe transfinite induction based on this)

Your interpretation is correct, and the easiest way to look at it is to know both definitions of recursively enumerable sets:

There is an algorithm (potentially running forever) that enumerates the members of $S$.
There is an algorithm for which the algorithm halts only on elements of $S$.

These two definitions are equivalent, and if you use the second one then you can easily answer your own question.

However, do note an important caveat. Although for any given word $w \in S$ there is some time $T_w$ such that after $T_w$ steps, $w$ will have been enumerated. However, there is no way to bound $T_w$ from above as a function of $w$. It can grow faster than any computable function.


Randomize List with guaranteed Index Change I usually post on Stackoverflow, but I got stuck with a problem which I think fits better here and I hope someone can help me. The task ist pretty simple:
Shuffle/Randomize an array/list
conditions:

each Index has to change; an Item which was at index 0 before the shuffle has to be at an index != 0 after the shuffle
all possible resulting permutations which satisfy the first condition should be distributed equally

I am unable to find a satisfying solution. Brute force (shuffling the array with Fisher-Yates until first condition is met) obviously works but is not a solution I am looking for. Brute Force with an array with four elements resulted in following number of permutations (which is roughly distributed equally) for one million tries: [111467, 111172, 111497, 111047, 111114, 111053, 110699, 110655, 111296]
Another thing I tried was something like this:

iterate through the array object by object and randomly choose a new index for the object
the randomly chosen index must not have been chosen before and must not be same as the original index
if the last element would fall on its original index, swap the last element with a random other element

Using this approach, the distribution looks really bad: [74166, 110734, 83581, 129486, 83210, 101904, 111305, 111235, 194379].
In theory, there must be a better solution than brute force but unfortunately everybody I asked so far (including google) didn't have a solution, or just had another non uniform solution comparable to my second approach.
Can anyone help me please? I would appreciate it a lot.

NOTE: updated (before it had low=i+1 always, this missed some valid results, and missed the extra check needed for the last index)
**NOTE: update 2 - randomize order to ensure uniformity **
Consider the following approach:
loopIndex[0..n-1] = permute([0..n-1])
index[0..n-1] = [0..n-1] // track indices
for i=0..n-2
   idx = loopIndex[i]
   if index[idx] == idx
      low = i+1
   else low = i
   swapIdx = random(low,n) // random(start,end) --> start <= i < end
   swapElement(index, idx, loopIndex[swapIdx])
   swapElement(array, idx, loopIndex[swapIdx])
finalIdx = loopIndex[n-1]
if index[finalIdx] == finalIdx
   finalSwapIdx = random(0,n-1)
   swapElement(index, finalSwapIdx, finalIdx)
   swapElement(array, finalSwapIdx, finalIdx)

PROOF NOT YET UPDATED
Note the following:

loopIndex is used to give a random ordering on which we process the elements. This ensures that any non-uniformity is "smoothed out".
If an index $j$ is selected as swapIdx then that element is swapped to a place where it's not processed again in the loop.
If an index $j < n-1$ is never selected as swapIdx then when $i==j$ the element will be swapped out from $j$ and never can return to $j$.
The final check handles the case where the final element was never selected. In this case, we swap between $n-1$ and some other random element.

Proof of uniformity by induction on the index -
Let $p(j,k)$ be the probability that after completing $i=j$, the element at index $j$ is the element that originally had index $k \neq j$ (clearly $p(j,j)=0$).
Then $p(0,k)=\frac{1}{n-1}$ clearly.
Assume then that the statement holds for all $j \leq t$ and we now prove for $j=t+1$.
$p(t+1,k)$ is the probability the element with original index $k$ is not in the first $t$ elements at step $i=t+1$, times the probability that $k$ is swapIdx now. By the assumption, this is then:
$$
\left(\frac{n-2}{n-1}\right)\left(\frac{n-3}{n-2}\right)\dots\left(\frac{n-t-1}{n-t}\right)\left(\frac{1}{n-t-1}\right) = \frac{1}{n-1}
$$
(Note that there is a minor difference between $k \leq t$ and $k > t+1$. For the former, it must not have been selected as a swapIdx for $j \neq k \leq t$, and it must not have selected $t+1$ as its swapIdx. For the latter, it must not have been selected as a swapIdx. The result though is the same in terms of the math).


Is reference counting GC vs. tracing GC a language property or an implementation property? We sometimes hear "Swift doesn't do classic (tracing) GC, it uses ARC."

But I'm not sure if there is anything in the Swift semantics that requires reference counting. It seems that one could build one's own Swift compiler and runtime to use tracing GC.

So what exactly is "reference-counted" about Swift? Apple's implementation or the language itself? Are there parts of the language or the library that so strongly support ARC that we can use that label for the language itself?

Swift guarantees that once the last reference to an object is dropped the object is deinitialized, and the deinit code is immediately run.

Obtaining this kind of guarantee through GC is not possible - at least, not without sacrifying performance. Standard GC mechanisms only ensure the deinit code is eventually run, e.g. at the next GC cycle. For precise semantics, you need a reference count somewhere.