How to avoid permutations in the n-Queens problem? EDIT: if you are not familiar with the problem and the solution, it's nicely explained here.

I have solved the n-Queens problem as an exercise using backtracking (recursion), but the problem I have right now is I get multiple permutations of the same solution:

n = 4
(0,1) (1,3) (2,0) (3,2)
(0,1) (1,3) (3,2) (2,0)
(0,1) (2,0) (1,3) (3,2)
(0,1) (2,0) (3,2) (1,3)
(0,1) (3,2) (1,3) (2,0)
...

For n=4 i get a total of 48 solutions. Of course there are rotations and mirroring which are fine and should be included, but as you can see in the example above permutations of the exact same solution appear.

My program works as follows:

solve(queens){
    if (n_queens_are_on_the_board){
        remember_solution();
        return;
    }
    for(x: 0 to n){
        for(y: 0 to n){
            if(current_position_not_attacked){
                add_queen_to_current_potision();
                solve(board);
                remove_prevously_added_queen();
            }
        }
    }
}

Obviously I can just find the permutations and remove them from the final result, but is there a faster way of getting rid of them or ideally completely avoiding them?

Any help is appreciated.

Note that your solution is not optimized - if you really want a speed boost, you should handle rotations / mirroring instead of looping through every possible combination. With a large board, this will be much more significant than looping through the solutions one extra time.

There are a few ways you could handle the permutations. I would handle them as a secondary check under if (n_queens_are_on_the_board), resulting in the following algorithm:

solve(queens){
    if (n_queens_are_on_the_board){
        if (solution_is_sorted) {
            remember_solution();
        }
        return;
    }
    for(x: 0 to n){
        for(y: 0 to n){
            if(current_position_not_attacked){
                add_queen_to_current_potision();
                solve(board);
                remove_prevously_added_queen();
            }
        }
    }
}

All that you have to do now is define a function to tell if the solution is sorted - again, there are a few ways you could do this. The simplest is probably to define the hash of a point to be point[0] * length(points) + point[1] and discard the solution if the hash of position n + 1 is less than the hash of position n. With this algorithm, you will end up with the solution (0,1) (1,3) (2,0) (3,2) from the sample provided.


Existence of Real-Time Multiprocessor Schedule Does an algorithm exist to check for the existence of a Real-Time Multiprocessor Schedule for aperiodic hard tasks(all of which have the same Release time)?

Assumptions:

The processors are Uniform parallel machines
Job preemption is permitted
Job migration is permitted
Job parallelism is forbidden

EDIT: Let there be $n$ jobs $J = \{j_1, j_2,\text{...}, j_n\}$ and $m$ no of processors $P = \{p_1, p_2,\text{...}, p_m\}$. Each job $j_i$ has a task time $t_i$(amount of work it would take to complete it) and due time $d_i$. Each processor has a constant speed $s_i$(amount of work it does per unit time). Each task must be completed before its due time.

I am interested to know about an algorithm with can check feasibility of a schedule in polynomial time.

Y. Cho and S. Sahni, Scheduling Independent tasks with due times on a uniform Processor System, Jr. of the ACM, 1980

Presents an algorithm to preemptively schedule n tasks(with due dates) on m uniform processors whenever a solution exists in $O(n\log{n} + mn)$ time.

Which is a stronger problem than I wanted to solve but still gives a polynomial algorithm, which answers my question.


Converting Boolean circuit to Boolean formula in parallel Let t be a fixed constant. I would like to convert a Boolean circuit C of depth t on n inputs over AND, OR and NOT gates (of fan-in 2, say) to an equivalent Boolean formula F on the same n inputs, in the sense that for each input vector x of length n, we have C(x) = 1 if and only if F(x) = 1. Some restrictions on the problem: the circuit has size m and depth t, and I would like the function mapping C to F to be computable by a PRAM (say) using a number of processors polynomial in m and time polylogarithmic in m. I don't mind that the size of the resulting formula is O(mt), I consider t to be a constant.

The approach I envision is to enumerate each path of length t from the output gate to each input gate and transform that set of paths into a trie. This trie will then be a tree of branching factor m and depth t representing a Boolean formula of size O(mt), observing that this is a polynomial in m if I consider t to be a fixed constant. My problem then reduces to the problem of constructing a trie from a set of at most mt strings, each one a string of length at most t over an alphabet of cardinality m.

Can I construct a trie of strings of length t over an alphabet of size m in parallel time polylogarithmic in m? More generally, can I convert a Boolean circuit of size m and depth t to a Boolean formula in parallel time polylogarithmic in m?

Take a look at the Tseitin transform.  The Tseitin transform can be applied in parallel, working separately on each gate.  Consequently, this can be implemented using one processor per gate, $O(1)$ time per gate, and the resulting formula has size $O(m)$.  Here I'm not counting the time to build the final formula; the final formula is a conjunction of the clauses produced by the processors, with each processor adding $O(1)$ clauses to the final conjunction.


Equivalence of two definitions of mutual information I am learning quantum computing and as a background study, I am currently learning fundamentals of classical information theory.
I thought it best to ask my doubts here.
In Nielsen and Chuang, it is stated that mutual information I(X:Y) of two random variables X and Y is the information they have in common while in some books, it is written that mutual information I(X:Y) is the information one variable(say X) has about the other(say Y). I can't understand it intuitively how the two definitions are equivalent. Also, the symmetric property of mutual information,i.e., I(X:Y)=I(Y:X) is obvious to me from the first definition but not from the second one.

You can define the mutual information as $I(X;Y) = H(X) - H(X|Y)$. This definition is symmetric in $X,Y$ since
$$
H(X)-H(X|Y) = H(X) - \sum_y \Pr[Y=y] H(X|Y=y) = \\
\sum_x \Pr[X=x] \log \frac{1}{\Pr[X=x]} -
\sum_y \Pr[Y=y] \sum_x \Pr[X=x|Y=y] \log \frac{1}{\Pr[X=x|Y=y]} = \\
\sum_{x,y} \Pr[X=x,Y=y] \log \frac{1}{\Pr[X=x]} -
\sum_{x,y} \Pr[X=x,Y=y] \log \frac{\Pr[Y=y]}{\Pr[X=x,Y=y]} = \\
\sum_{x,y} \Pr[X=x,Y=y] \log \frac{\Pr[X=x,Y=y]}{\Pr[X=x]\Pr[Y=y]},
$$
and this expression is symmetric in $X,Y$.

This calculation also shows that if $X,Y$ are independent then $I(X;Y) = 0$, since then $\Pr[X=x,Y=y] = \Pr[X=x] \Pr[Y=y]$.

Moreover, if we write
$$
I(X;Y) = \sum_{x,y} \Pr[X=x] \Pr[Y=y] \frac{\Pr[X=x,Y=y]}{\Pr[X=x] \Pr[Y=y]} \log \frac{\Pr[X=x,Y=y]}{\Pr[X=x] \Pr[Y=y]},
$$
then the convexity of $z\log z$ implies that $I(X;Y) \geq z\log z$, where
$$
z = \sum_{x,y} \Pr[X=x] \Pr[Y=y] \frac{\Pr[X=x,Y=y]}{\Pr[X=x] \Pr[Y=y]} = \sum_{x,y} \Pr[X=x,Y=y] = 1.
$$
Thus $I(X;Y) \geq 0$.


Complexity class of integer factorization Is integer factorization confirmed to be an NP-complete problem? If not, then if one could transform IF into an equivalent problem which is already proved to be NP-complete, would it mean that IF is itself NP-complete as well? Would such a thing have any practical meaning?

Integer factorization (or rather, an appropriate decision version) is not known to be NP-complete. In fact, it is conjectured not to be NP-complete. However, any reasonable decision version of integer factorization is in NP, and so reducible to any NP-complete problem (by definition). There are specialized algorithms for integer factorization which are better than, say, reducing integer factorization to SAT and then using a SAT solver.


Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does? One common way for algorithms to battle adversarial inputs is by acting randomly. One popular example is quicksort and choosing pivots randomly (this sort of notions is explained well in section 5.3 in CLRS 3rd edition page 122 where by acting randomly we manage to impose a distribution on our inputs).

With Simple Uniform Hashing (SUHA) we have that the hash function "evenly distributes" the keys in a random fashion across the hash table. This way the average length of a chain is not too long. Is the randomness that we assume inherently exists in this magic hash function the way we battle worst-case inputs? i.e., is this exactly how we ensure that the expected runtime will be small, since  our hash function is random and no series of keys is bad? (i.e., a worst case input doesn't exist because the hash function will act randomly and hence, make the expected chain lengths small).

I am not sure if this is right or if this is the right way to think about it, but that's how I think of hash tables, that they are random so no chain can get too long (usually) and hence we perform well.

Yes, your understanding is correct.  That's exactly the role the hash function plays.

A pair of keys $x,y$ might collide with one hash function, but not with another.  For any fixed set of keys, the expected number of collisions is small.  Moreover, for any fixed set of keys, the probability of having a large number of collisions is very small.  That's why we can say that the average-case running time is good, and why there's only a tiny probability that the running time is high.

To put it another way: Since the adversary doesn't know what hash function we will be using, he can't craft inputs (a set of keys) that will trigger worst-case behavior.  The randomization ensures we only need to worry about average-case behavior (the adversary has no way to force us into the kind of situation that would trigger worst-case behavior).  And, hash tables have excellent average-case running time.


Can't Understand this Subset Construction Proof This proof is from Introduction to Automata Theory Languages and Computation by Hopcroft & Ullman and is regarding a 'bad case' for subset construction.

The NFA which is being converted is as follows:

The argument for this then goes as follows:

  Consider the NFA N of Fig. 2.15. $L(N)$ is the set of all strings of
  $0's$ and $1's$ such that the nth symbol from the end is $1$.

  Intuitively, a DFA D that accepts this language must remember the last
  $n$ symbols it has read. Since any of $2^n$ subsets of the last $n$
  symbols could have been $1$, if D has fewer than $2^n$ states, then
  there would be some state $q$ such that D can be in state $q$ after
  reading two different sequences of $n$ bits, say $a_1a_2…a_n$ and
  $b_1b_2…b_n$.

  Since the sequences are different, they must differ in some position,
  say $a_i \neq b_i$. Suppose (by symmetry) that $a_i = 1$ and $b_i = 0$.
  If $i = 1$, then q must be both an accepting state and a
  nonaccepting state, since $a_1a_2…a_n$ is accepted (the $n^{th}$
  symbol from the end is 1) and $b_1b_2…b_n$ is not.

  If $i > 1$, then consider the state $p$ that D enters after reading $i - 1$
  $0$'s. Then p must be both accepting and nonaccepting, since $a_ia_{i+1}…a_n00…0$ is accepted and $b_ib_{i+1}…b_n00…0$ is not.

What's confusing me are these two lines,

  Since any of $2^n$ subsets of the last $n$ symbols could have been
  $1$, ...

and

  If $i > 1$, then consider the state $p$ that D enters after reading $i - 1$
  $0$'s. Then p must be both accepting and nonaccepting, since $a_ia_{i+1}…a_n00…0$ is accepted and $b_ib_{i+1}…b_n00…0$ is not.

I understand the case where $i = 1$, but I don't understand how the $i \gt 1$ works, and what they mean by any of the $2^n$ subsets being $1$. How can the subsets be $1$?

Since any of $2^n$ subsets of the last $n$ symbols could have been $1$, ...

This is just referring to the fact that there are $2^n$ possible sequences of length $n$ made up of $0$'s and $1$'s. That is, if you have $n$ symbols, you can think of "a subset of those symbols being $1$" as taking a subset of the indices from 1 to $n$ and making the symbols at those indices be $1$.

  If $i>1$, then consider the state $p$ that D enters after reading $(i−1)$ $0$'s. Then $p$ must be both accepting and nonaccepting, since $a_ia_{i+1}\ldots a_n00 \ldots 0$ is accepted and $b_ib_{i+1}\ldots b_n00 \ldots 0$ is not.

So you have two sequences of characters $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ which end up in the same state. You know that $a_i=1$ and $b_i=0$. Now take both of those strings and append $(i-1)$ $0$'s to each one. This gives you the following two strings $x$ and $y$:

$x= a_1a_2\ldots a_i\underbrace{a_{i+1}\ldots a_n}_{n-i\text{ symbols}}\underbrace{00 \ldots 0}_{i-1\text{ zeros}}$

which we know is a string such that the $n$th symbol from the end is $1$ ($a_i = 1$ and it is the $n$th symbol from the end).

$y= b_1b_2\ldots b_i\underbrace{b_{i+1}\ldots b_n}_{n-i\text{ symbols}}\underbrace{00 \ldots 0}_{i-1\text{ zeros}}$

which we know is a string such that the $n$th symbol from the end is $0$ ($b_i = 0$ and it is the $n$th symbol from the end).

Now think about what happens when you run these two strings through D. It's actually quite similar to the $i=1$ case: since the two strings ended up in the same state $q$ after reading $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$, they also have to end up in the same state $p$ after reading $(i-1)$ more $0$'s. Thus this state $p$ has to be both accepting and nonaccepting since our string $x$ should be accepted but $y$ should not be accepted.


What features should a critical section have to maximize performance? Critical sections limit performance by constraining parallel execution and adding overhead. What features should a critical section have for improving performance?

As noted in the question, the performance impact of critical sections has two components: the limiting of parallelism and the overhead in providing the isolation guarantees.

The limiting of parallelism can be addressed by minimizing the context, frequency, and duration of the critical section. Using finer-grained locking or transactional memory allows independent operations to be executed in parallel by reducing the context in which isolation must be guaranteed.

Reducing coupling of operations can reduce the context and frequency of critical sections. The use of redundant data structures can provide localization of data such that critical sections can be avoided (reducing their frequency) or the potential contention reduced. For example, instead of updating a single accumulator a tree of accumulators could be used.

(While the fastest critical section is the one that does not exist, one must be careful that overheads in avoiding critical sections are not higher than the cost of using a critical section.)

The duration of a critical section can be reduced by keeping work out of the critical section. While this is relatively obvious, moving work before or after the critical section may require that more work be done (at least in some cases) or may interfere with other design considerations. Speculatively performing work before a critical section can shorten a critical section at the cost of detecting and handling incorrect speculation.

One subtle form of work is the handling of cache misses and state updates (primarily acquiring ownership of a cache block). Avoiding false sharing is a well-known technique, but somewhat less commonly mentioned (in part because of tradeoffs of complexity and runtime overheads with the performance benefit) are localization of true sharing and prefetching. Temporal localization of sharing exploits patterns of reading and updating to use warm data. In some cases, it may even be worthwhile to increase the duration of a critical section to reduce the amount of work within critical sections by taking advantage of a warmed-up cache.

Sharing can also be localized within the memory system. Not all communication between threads has equal cost. Physical proximity of communication and read-sharing can exploit sharing of a level of cache to keep warm data in cache (incidentally avoiding replication), to prefetch data (if cross-thread accesses can have temporal locality either naturally or by clever scheduling), or to reduce the bandwidth or latency of communication. NUMA-optimizations can also reduce bandwidth and latency by locating users, especially modifiers, of data near the home of the data. NUMA-optimizations can even apply to last level cache slices when a cache block has a single home partition within the last level cache which can be accessed with less overhead by one or more processing elements.

Using finer-grained locking can also reduce the isolation overhead by avoiding cache line ping-pong. The ultimate in fine-grained locking is lockless updating using atomic operations. Knowing what facilities the targeted hardware provides and the tradeoffs in their use can also be helpful in reducing isolation overhead. For example, if the targeted hardware transactional memory system supports low overhead retry under certain conditions, it may be less important to avoid contention leading to a transient transaction failure than to make sure those conditions are satisfied.

Approximation can also exploited in some cases to reduce overhead. Statistical information such as software performance counters can often tolerate losing some updates, allowing removal from the critical section and the use of less expensive non-atomic operations. Similarly, some information only needs to be conservatively maintained for correctness. For example, a reference counter could afford to lose a decrement if the information is only used for earliest release of a resource (another layer of resource management might handle such leaks).

The basic principle for critical sections is that they should be as small (context and duration) and as infrequent as possible.


Intuition behind straight-line programs Wikipedia defines straight-line programs in the following manner:

  In mathematics, more specifically in computational algebra[disambiguation needed], a straight-line program (SLP) for a finite group G = 〈S〉 is a finite sequence L of elements of G such that every element of L that belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses.

This is a fairly confusing definition to unpack. However, in some meaningful sense, I believe the main idea here is that there are no comparisons allowed. Since there are no comparisons, the "computation tree" ends up being a straight line - hence the name "straight-line program."

In modern terms, is this the correct idea? Or are there even more subtle restrictions than this on what sorts of programs are allowed to be straight-line programs?

A straight-line program is one with no branches, no loops, no conditional statements, no comparisons -- just a sequence of basic operations.

A straight-line program for a finite group $G$ is a straight-line program in a very simple language with an unlimited number of registers $r_1,r_2,r_3,\dots$ and with only two legal operations:

$r_i := \text{inverse}(r_j)$
$r_i := \text{multiply}(r_j,r_k)$

You specify $i,j,k$ for each line of the program; those are constants.  Each register holds a group element.

For instance, the following is a straight-line program that computes the cube of the element in $r_1$ and stores the result in $r_3$:

$r_2 := \text{multiply}(r_1, r_1)$
$r_3 := \text{multiply}(r_1, r_2)$

Here is another program that computes the same thing, but in a different way:

$r_2 := \text{multiply}(r_1, r_1)$
$r_4 := \text{multiply}(r_2, r_2)$
$r_5 := \text{inverse}(r_1)$
$r_3 := \text{multiply}(r_4, r_5)$


Conjectured NP-complete problems Assume P != NP. Then there are many examples of problems in NP that are known not to be NP-complete, like 2-SAT, and many that are conjectured not to be NP-complete, like factorization. However, are there any problems that are widely conjectured but not known to be NP-complete?

There are no natural problems that I am aware of that have that property. There are two problems which are "close", however.

The Minimum Circuit Size Problem is, given a truth table of a boolean function $f$ and an integer $k$, is $f$ computed by a circuit of size at most $k$? Note $MCSP \in NP$, and it is widely expected that $MCSP$ is "hard"; however, it is not known that $MCSP$ is $NP$-complete, and while it is easy to conjecture that it might be, there is also some evidence that it is not.

The Unique Games Conjecture states that approximating the value of a certain combinatoric problem is $NP$-hard. This problem is not strictly in $NP$ because its decision version is a "promise problem". Nevertheless, the UGC is one of the premier open questions of computer science today and there is little consensus on whether it is true or not.


Order of various functions I am to arrange the following 30 functions in terms of increasing order
( all the lg (log) are to the base 2.log* represents iterated logarithm.)

Here's my answer (the functions on the same level are of the same order):
1 ,
lglg*n
lg*n,      lg*(lgn)

 ,
 ,
 ,

,

I am not sure where to insert (logn)!. I know (logn)! = o((logn)^logn) and logn = o((logn)!), isn't it. But where exactly would it fit. Can anyone help me with that. Also I would really appreciate if someone could verify that my arrangement is right or not.
Thank you.
EDIT : I MEANT TO ASK THE POINT OF INSERTION OF (LOGN)! IN THE ABOVE LIST SORTED IN TERMS OF INCREASING ORDER. Simple.

Stirling's formula asserts that
$$
n! = \Theta(\sqrt{n}(n/e)^n).
$$
Thus
$$
(\log n)! = \Theta(\sqrt{\log n}((\log n)/e)^{\log n}).
$$


Why are mapping reductions from incomputable Languages OK? For example, many reductions from $A_{TM}$ will often have the lines:

Simulate M on w:
    if M accepts
       ...
    else

But: a reduction is a computable function, right? So why are we allowed to say "if M accepts"?
Also, I can take the same logic and reduce $A_{TM}$ to a deciable language:
Let L be the empty language. Clearly L is decidable.

Given $(M,w)$:

 Output output:
      If M accepts w
            output = '0'
      else
            output = $\emptyset$

Obviously I'm wrong here. But why?
Thanks in advance.

There are two options:

Either the pseudocode means "run $A_{TM}$ on the pair $M,w$" when it says "Simulate $M$ on $w$";
or it really means to simulate $M$ on $w$, and if it ever stops then do something; there is no "else" clause in that case.


Minimum cost to convert one array to another Given two arrays $A$ and $B$ of integers, both of size $N$, such that for all $0 \le i \le N-1$, $A[i] \ge B[i]$, we have to convert array $A$ to array $B$. For this we can do only one type of operation: choose some $l$ and $r$ ($0 \le l \le r \le N-1$) and set the values of $A[l],A[l+1],\ldots,A[r]$ to $k$, where $k \le A[i]$ for all $l \le i \le r$. Find out minimum operations to convert $A$ to $B$.

I was thinking about dynamic programming solution but could not figure it out.

Let distinct elements of $B$ be $b_1,b_2,\ldots$ where $b_1>b_2>\cdots$. There must be an optimal solution where it first sets a range to $k_1$ then set a range to $k_2$ and so on, such that $k_1\ge k_2\ge\cdots$ (otherwise one can swap related operations to meet the constraint without changing the result), and $k_1,k_2,\ldots\in\{b_1,b_2,\ldots\}$ (otherwise, say $k_i\notin\{b_1,b_2,\ldots\}$, one can delete the $i$th operation without changing the result).

Using the property above, we have the following greedy algorithm.

Let $B[i_1],B[i_2],\ldots$ ($i_1<i_2<\cdots$) be the greatest elements, i.e. $b_1$. The algorithm firstly sets $A[i_1],A[i_2],\ldots$ to $b_1$ using as little operations as possible. More specifically, it checks whether $A[i_1]>b_1$ to see whether an operation is required to set $A[i_1]$ to $b_1$. If so, it then checks whether $A[i_1+1],\ldots,A[i_2-1]\ge b_1$* by range minimum query to see whether this operation can be merged with the operation corresponding to $A[i_2]$. It then goes on with $A[i_2],A[i_3],\ldots$ For example, say

A: 3 3 3 3 2 1 3
B: 2 1 2 1 2 1 2

Now $b_1=2$ and $i_1=0, i_2=2, i_3 = 4, i_4=6$. It requires 2 operations to set $A[i_1],A[i_2],\ldots$ to $b_1$: first setting $A[0], \ldots, A[2]$, then setting $A[6]$.

The algorithm then repeats the above process for $b_2,b_3,\ldots$

This algorithm runs in $O(n\log n)$.

*Note, for example, when dealing with $b_2$ instead of $b_1$, no operation can be performed on a range containing $i_j$ for some $j$, otherwise $A[i_j]$ will be less than $B[i_j]$ and cannot be recovered. Therefore we must also check this constraint here. This can be done by maintaining a sorted index array of all elements greater than $b_m$ when dealing with $b_m$.


Kleene Star regex question, sed behavior? Kleene Star with 'sed' is behaving as expected for me, with exception of a case where the input pattern is "ab" and the regex is "b*".  Does anyone know why this regex is not being matched against the pattern space?

This is the failure case:

$ printf "ab\n" | sed -En 's/b*// p' | od -t c
0000000   a   b  \n
0000003

SOLUTION
'b*' expects 0 or more occurrences of 'b'.  If 0 occurrences of 'b' the empty string $\epsilon$ is expected.  In the string above, 'ab' is preceded by the empty string and it is matched in the beginning of "ab" pattern space as follows:

printf "ab\n" | sed -En 's/b*/x/ p' | od -t c
0000000   x   a   b  \n

where 'x' is substituted for empty string.

In order to match b, I had to use the following form:

Kleene Plus in addition to Kleene Star as follows:

 printf "ab\n" | sed -En 's/(.*)(b+)(.*)/\1/ p' | od -t a
0000000   a  nl

This case, without Kleene Star, behaves as expected:

$ printf "ab\n" | sed -En 's/b// p' | od -t c
0000000   a  \n
0000002

I'm trying to match the 'b' and replace it with nothing.

The pattern space is 'ab', beginning of line is unspecified, so I'm confused why /b*/ would not match a pattern of zero or more 'b's, in this case 'b'.

Oddly, this case works with the '.' prepended to the '*':

# fails to match
$ printf "abb\n" | sed -En 's/b*// p' | od -t c
0000000   a   b   b  \n
0000004
# matches with .* !
$ printf "abb\n" | sed -En 's/b.*// p' | od -t c
0000000   a  \n
0000002

Kleene Star matches zero or more occurrences of the preceding alphabet (in this case a single character).

By definition:

$V^0 = \{\epsilon\}$

$V^1 = V$

$\forall i ( (i \gt 0) \land (V^{i + 1} = \{ wv : w \in V^i \land v \in V )\} $

Therefore $V^0 = \{ \epsilon\}$, $V^1 = \{ \epsilon \cdot b\}$, $V^2 = \{ \epsilon \cdot b \cdot b\}$.

$V^* = \bigcup\limits_{i\ge0} V^i = V^0 \cup V^1 \cup ...$ which I have specified by /b*/.

The following cases agree with my understanding of sed and Kleene Star:

# * : matches 0 or more occurances
# no match
$ printf "a\n" | sed -En 's/b*// p' | od -t c
0000000   a  \n
0000002

# match a
printf "a\n" | sed -En 's/a*// p' | od -t c
0000000  \n
0000001

# match a
printf "ab\n" | sed -En 's/a*// p' | od -t c
0000000   b  \n
0000002

# match aa
printf "aab\n" | sed -En 's/a*// p' | od -t c
0000000   b  \n
0000002

I tested using BSD and GNU sed, both have the same results.

Thanks!

$ printf "ab\n" | sed -En 's/b*// p' | od -t c
0000000   a   b  \n
0000003

This regex expression "$b*$" does match the empty string, which is zero '$b$', at the very front of the input "$ab$". This is in accordance with the definition of Kleene star since $b^*$ stands for the language $\{\epsilon, b, bb, \cdots\}$, where $\epsilon$ stands for the empty string. The matched part, an empty substring is replaced by the empty string. So, the same input string "$ab$" is printed with the newline attached.

Note that sed tries to find a match as early as possible. Although the substring "$b$" of "$ab$" matches "$b*$" more, it is ignored by sed completely since it happens later than the match said above.


Proof that AND-OR graph decision problem is NP-hard Given an directed acyclic AND-OR graph, where each non-terminal nodes are labelled as either AND or OR. The terminal nodes are the nodes which have no outgoing edges. Children of a node are the vertices all the outgoing edges of the node points to.

A solution graph for a node $S$ on an AND-OR graph $G$ is defined as a subgraph $G'$ which satisfies the following

(1) $S\in G'$

(2) If $v\in G'$ and $v$ is an AND node, then all of $v$'s children in $G$ are in $G'$

(3) If $v\in G'$ and $v$ is an OR ndoe, then at least one of $v$'s children in $G$ also belongs to $G'$

I want to show the following decision problem is NP hard:

Instance: An AND-OR graph $G$, a node $S$ in $G$ and a number $k$.

Question: Does there exist a solution graph for $S$ in $G$ which contains $\leq k$ nodes?

I am thinking about reducing some well known NP-hard problem to this problem. However, I am not sure which problem is the most suitable to pick. Please enlighten me! Thank you!

Hint: given an instance of set cover problem, build an AND-OR graph whose terminal nodes represent elements and whose OR nodes represent sets.


Type of a return satement I'm creating a experimental toy language for my own education purposes (an impure typed Lisp based on Clojure - https://github.com/mikera/kiss)

I think I understand the concept of each expression in the language having a return type.

However some expressions may contain flow control statements that mean that the expression will not return normally, e.g.

An early function return
A break within a loop
A continue / recur within a loop
A goto (the horror...)

I'm not sure how to represent these in my type system. Should such things alter the type of the expression? Or should I have a parallel mechanism that enumerates alternative ways the expression may be exited?

There is hardly a good reason to give a return expression a type.

In Benjamin Pierce's book, Types and Programming Languages, he mentions a similar situation: the type of throw expressions. Like return, a throw expression will not produce a value and instead changes the flow of control.

Pierce's comment is that if such expressions is to be given a type at all, a logical choice is ⊥, the "bottom" type. The bottom type is a type, but one which is impossible to instantiate. There are no objects of type ⊥.

This makes perfect sense for expressions that redirect flow in a program. They don't produce a value at all. So to denote this, we say their type is this "uninhabited" ⊥ type. If they did return a value, this would violate the one and only property of ⊥: that there are no values. We would have done the impossible.

If you come from an object oriented background, you might like to think about ⊥ as the "dual" of the Object type. (We sometimes call Object by the name ⊤ in computer science). In a subtype hierarchy, every type is a subtype of ⊤. Dually, ⊥ is a subtype of every other type. This means if I had a value of type ⊥, I can up-cast it


Function that cannot be computed by a Boolean circuit of size $2^n/2n$ Show that, for sufficiently large $n$, there is a function $f\colon\{0,1\}^n \to \{0,1\} $ that cannot be computed by a Boolean circuit with fan-in $2$ with $\frac{2^n}{2n}$ gates. Please give me a hint.

We need counting argument here. First thing is, there are $2^{2^{n}}$ many boolean functions, second thing is to count the number of boolean circuits for $k$ size boolean circuit. There are $2^{k^2} \times 3^{k}$ many  boolean circuits of size $k$ (use adjacency matrix ). In your case value of $k =\frac{ 2^n}{2n}$, now you can easily check that

  $$2^{2^{n}} > 2^{k^2} \times 3^{k} $$

So it means there are more number of functions than the total number of boolean circuits. There has to be at least one function that can not be computed by $k$ size circuit ( pigeonhole principle ). One thing to note here that I have proved the existence of such type of boolean circuit but to come up with such type of boolean circuit is quite hard.


Lambda calculus application I have a function application:

E1 E2

Can someone please show me an example, how to execute function?

If you have at least one abstraction just go on $\beta$-reducing. It just works like taking an input $x$ and computing $f(x)$.

$$ (\lambda x. x + 1)1$$
is an application.

$$ [1/x](x + 1)$$
$$ (1+1) \rightarrow_\beta 2$$


Which word could I use for the Pumping Lemma proof? I have the language

$ A_{1} \triangleq\left\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\{a, b\}^{*} \wedge |\left.w\right|_{a}=l+m\right\} \operatorname{with} \Sigma \triangleq\{a, b, c, d\} $

and I have no idea which word I should use to prevent a case distinction.

My first idea was to set $l = 0$ and $w=b^n$ so I would have the word $p=aa^nd^n$.
The problem with that is, I have no idea how to proof this because this single "a" makes me crazy.
Do you could help me?

If we want to use the usual pumping lemma for regular languages as introduced in most textbooks to prove a given language is not regular, the way to avoid or reduce case distinction in showing a word cannot be pumped
is to

select that word so that its front part is in a very restricted form and at least at long as the pumping length.
combine all cases into very few or only one case conceptually.

Let me take the language in the question as an example.

To show $A_{1} \triangleq\left\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\{a, b\}^{*} \wedge |\left.w\right|_{a}=l+m\right\}$ is not regular, let us suppose our adversary Adriana claims $A$ is regular with pumping length $p$. In order to beat Adriana, we select word $w=aa^pd^p\in A_1$. Adriana claims that $w=xyz$ for some $x,y,z$ such that $|xy|\le p$, $|y|\ge1$ and for all $n\ge0$, $xy^nz\in A$.

It looks like we have to make a case distinction, because Adriana could decompose the word in many ways. For example, Adriana could have any one of the following decompositions.

$ x=\epsilon, y=a^{j}$ and $  z=a^{p+1-j} d^{p}.$
$ x=a, y=a^{j}$ and $  z=d^{p-j} d^{p}.$
$x=aa^i, y=a^{j}$ and $  z=d^{p-i-j} d^{p}.$
$\cdots$.

We have to prove Adriana is wrong in every possible case. There is no way around that, as Adrianna is free to choose any one of them.

However, a little dose of abstraction and intelligence will enable us to treat all cases simultaneously.

Since $|xy|\le p$ and all $p$ letters at the front of $w$ are $a$'s, $y$ must contain $a$ only. Suppose $y=a^i$ for some $i>0$. Then $xz=xy^0z$ contains less number of $a$'s than $w$ but the same number of $c$ and $d$ as $w$. That means $xz\not=A_1$. We beat Adriana as if she has only one case.

Hopefully this strategy answers your question. Indeed, it should be applicable to almost all similar problems in the course of your study where you want to prove a language is not regular.

Here are a few exercises about the languages you have encountered.

Exercise 1. Prove the language $C \triangleq\left\{a^{m} b^{n} c d^{n} d^{m} \mid n, m \in \mathbb{N} \wedge m \leq 3\right\}$ is not regular "without case distinction".

Exercise 2. Prove the language $B \triangleq\left\{w \in \Sigma^{*} \mid |\left.w\right|_{b} \neq|w|_{c} \right\}$ is not regular "without case distinction".

Exercise 3. Prove the language $A \triangleq\left\{(a b)^{n} c^{n} | n \in \mathbb{N}\right\}$ is not regular using two combined cases.


Lower bounds on regret In "regret" styled analysis over $T$ steps of an iterative algorithm $\{x_i \in F \}_{i=1}^T$ (where $F$ is some feasible set) being given the sequence of loss functions $\{ f_i\}_{i=1}^T$ one defines the regret $R_T = \sum_{i=1}^Tf_t(x_i) - \min_{x \in F} \sum_{i=1}^T f_t(x)$ Most typical analyses assume that the $f$s are convex.

Is this notion of "regret" lower bounded?
Or under what conditions is it lower bounded?

I guess "minimizing the regret" does not make sense because one can always have an "Oracle" access to the sequence of points $x^*_i$ such that $x^*_i = \min_{x \in F} f_i(x)$. Then for this sequence for $x^*$ points the regret is only at most $0$.

There are many different models in which regret minimization makes sense. One particular model is Gaussian density estimation. Takimoto and Warmuth, in their paper The minimax strategy for Gaussian density estimation, give a tight analysis which includes both an upper bound achieved by a particular algorithm and an almost matching lower bound proved using the adversary method. There are probably many more such analyses out there.


Modified shortest path problem For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^*(p)=\varSigma(w(v_i,v_{i+1}) -max\{w(v_i,v_{i+1})) | 1\leq i \leq k$}

The complexity needs to be $O(V+E\log V)$.
Obviously i thought about dijkstra, define a new weight function s.t shortest path according to that weight function is the shortest path we looking for, and that just run dijkstra algorithm on the graph using the new weight function, however I cant think about such function, does anyone have an idea?
Thanks in advance.

Notice that if you allow once jumping without paying the weight cost, then the shortest path is exactly what you need.

Create 2 copies of $G: G_1,G_2$. For every edge $e=(v,u)\in G$ also add an edge $(v_1,u_2)$ between the node $v$ of $G_1$ and $u$ of $G_2$. Make those edge's weight to $0$.

Now, find a shortest path between $s_1$ and $t_2$ (using Djikstra)


Words equal to the concatenation of their odd and even position - characters Let $\Sigma = \{0, 1\}$ and $$L = \{ w \in \Sigma^* | w = \mathrm{odd}(w) · \mathrm{even}(w) \},$$ where $\mathrm{odd}(w) = w_1, w_3, w_5 \ldots{}$   and $\mathrm{even}(w) = w_2, w_4, w_6, \ldots{}$ are the words constructed from the characters in all the odd and even positions of the string. I.e. $w = 0110110110 \in L$, because $\mathrm{odd}(w) = 01101, \mathrm{even}(w) = 10110$ and $w = 01101 \cdot{} 10110 = \mathrm{odd}(w) \cdot{} \mathrm{even}(w)$.

  Is $L$ regular?

I've tried using the Pumping Lemma for strings of the sort $0^{2n+1}1$ but I can't fix the value of $v^i$ from $w = uvx$ to have an either even or odd length.

I also tried to construct the DFA but it seems to need an infinite number of states to "track" which characters of $w$ get mapped to $\mathrm{odd}(w) \cdot \mathrm{even}(w)$, so my best bet is it's irregular, which means I need to find a way to prove it with the Pumping-Lemma.

Any ideas how I can find a suitable string for the Pumping Lemma?

It would be more convenient to index word positions starting with zero.
Let us take a look at $L \cap \Sigma^{2^n}$. Any word $w \in L \cap \Sigma^{2^n}$ satisfies
$$
w = w_0 w_2 \ldots w_{2^n-2} w_1 w_3 \ldots w_{2^n-1}.
$$
You can check that for $0 \leq m < 2^{n-1}$ and $b \in \{0,1\}$, this is equivalent to
$$
w_{2^{n-1}b + m} = w_{2m+b}.
$$
In other words, if we think of the index as an $n$-bit string, then this is the same as $w_i = w_{\mathrm{rot}(i)}$, where $\mathrm{rot}(i)$ is obtained by rotating $i$ to the left.

A necklace is an equivalence class of words under rotation. What we have shown above is that $w \in L \cap \Sigma^{2^n}$ iff $w_i$, interpreted as a function $\{0,1\}^n \to \Sigma$, is constant on necklaces. Denoting the number of necklaces of length $n$ by $N_2(n)$, we deduce that
$$
|L \cap \Sigma^{2^n}| = 2^{N_2(n)}.
$$
The explicit formula for $N_2(n)$ shows that $N_2(n) \sim 2^n/n$.

It is known that if $L$ is a regular language then there exists a modulus $m \geq 1$ such that for every $0 \leq i < m$ there exist constants $C,d,\lambda \geq 0$ such that for $N \equiv i \pmod{m}$,
$$
|L \cap \Sigma^N| \sim C N^d \lambda^N.
$$
We can calculate $\lambda$ as $\lim_{N\to\infty} |L \cap \Sigma^N|^{1/N}$ (the limit taken over $N \equiv i \pmod{m}$).

Now suppose that our $L$ were regular. Choose $i$ so that infinitely many values $2^n$ satisfy $2^n \equiv i \pmod{m}$. We have
$$
|L \cap \Sigma^{2^n}|^{1/2^n} = 2^{N_2(n)/2^n} = 2^{O(1/n)} \longrightarrow 1,
$$
and so $\lambda = 1$. However, that implies that $|L \cap \Sigma^{2^n}|$ should have polynomial growth (in $2^n$), whereas it clearly has superpolynomial growth.


Do any decision problems exist outside NP and NP-Hard? This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard.

In order to be in NP, problems have to have a verifier that runs in polynomial time on a deterministic Turing machine. Obviously, all problems in P meet that criteria, but what about the problems with sub-exponential complexity? They do not belong to P and it's not obvious to me that they all have efficient deciders. And they certainly don't qualify for NP-complete.

I'm willing to believe that all decision problems are either NP or NP-hard or both, but nobody has actually said that (that I can find). I'm also willing to believe that such problems do exist, even if they are very contrived. Maybe someone more knowledgeable can put this issue to rest for me. Thanks.

Edit

I abused the term 'subexponential' in my question. In my mind it meant some problem with a complexity between exponential and polynomial like L-notation in this table. See the links in Raphael's answer for more details.

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case.

If, however, $P \neq NP$, then there are languages which are neither in NP nor NP-hard.

For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this language is not computable, it is clearly outside of $NP$. As this language is sparse, $P \neq NP$ together with Mahaney's theorem implies that it is not NP-hard.

If we want a computable counterexample, we can take a language $L$ that is not in EXPSPACE. We number all finite words in increasing order as $(w_n)_{n \in \mathbb{N}}$, and now consider the language $L' = \{1^n \mid w_n \in L\}$. Again, Mahaney's theorem ensures that $L'$ is not NP-hard. If $L'$ were in NP (or even PSPACE), then an EXPSPACE algorithm for $L$ would be available in "Given w_n, compute 1^n and run the PSPACE-algorithm for $L'$ on it."

See here https://math.stackexchange.com/questions/235162/if-an-unary-language-exists-in-npc-then-p-np for a proof of Mahaney's theorem. Note that Yuval speaks about starting with an NP-complete unary language, that assumption is not used - the argument only needs an NP-hard unary language.


Understanding P vs NP I want to make sure my understanding on P vs NP is correct. I know that NP-complete problems cannot be solved in polynomial time, and if P != NP, then all problems in NP cannot be solved in polynomial time. Furthermore, if we consider the church turing thesis, and if P != NP, then no computational formalism can solve NP-complete problems in polynomial time. Would I be fine saying this?

I know that NP-complete problems cannot be solved in polynomial time.

We don't know this. This is exactly the P vs NP question. NP-complete problems can be solved in polynomial time iff P=NP.

If P ≠ NP, then all problems in NP cannot be solved in polynomial time.

P is a subset of NP, so some problems in NP can definitely be solved in polynomial time.

Furthermore, if we consider the Church-Turing thesis, and if P ≠ NP, then no computational formalism (ever) can solve NP-complete problems in polynomial time.

The Church–Turing thesis isn't really relevant here, since it is about computability rather than complexity. It could be that P ≠ NP but NP-complete problems can be solved in polynomial time by randomized algorithms or by quantum algorithms (though both of these are considered unlikely).


3SAT solvable in polynomial time...but with exponential tuning? Suppose there exists an algorithm that solves 3SAT in a polynomial number of steps.  However, this algorithm requires some 'tuning' parameters, and the value of these tuning parameters take an exponential number of steps(given the input) to determine.

Would this place 3SAT in P? (since it can be solved in polynomial time given the appropriate parameters)

Or would 3SAT remain in NP? (since it still takes an exponential number of steps to ultimately solve)

Edit: just to clarify, the question is about whether or not 3SAT would 'move' to P or 'remain' where it currently is...NP.  If 3SAT 'moves' to P it obviously would still be contained in NP.

If the tuning parameters depend on the entire input, then it's not a self-contained algorithm, so it says nothing about whether 3SAT is in P.

After all, I can give you an algorithm that has that property: in my algorithm, the 'tuning parameter' for a 3SAT formula $\varphi$ is 0 or 1, according to whether the formula $\varphi$ is satisfiable or not.  My algorithm ignores the formula on its input and just outputs its tuning parameter.  Sure, it may take exponential time to find the right tuning parameter for any particular formula, but once you've got it, my algorithm can output the right solution in polynomial time -- in fact, in just $O(1)$ time.  Yet this says nothing about whether 3SAT is in P or not.


Problem regarding Turing Machine notation Here I have a Turing Machine (sorry for awful drawing):

So, I have a question regarding the usage of a here. It is treated as a variable here. But since it doesn't alter input tape in any way, shouldn't it be stored in an implicit storage? My question is if this implicit storage (tell me if I am wrong) is in conflict with the fact that a Turing Machine only has a single input tape.

My hunch is that it is syntactic sugar and it can be explicitly defined with less-intuitive notation (another input tape?), but I am not sure.

Unless I'm misunderstanding the diagram, the way to replace it is with a transition for every letter in your tape alphabet.

Say your tape alphabet $\Gamma = \{ 0,1,2,3 \}$, plus the blank symbol. Then you would have a transition from $R$ to $La$ when reading 0, another when reading 1, another when reading 2, another when reading 3, but NOT one when reading a blank.

You are right in your intuition that this is just syntactic sugar. What it is really doing is using one transition to represent several.


What are the implications of Lean not having the type `Set`? In Coq we have an impredicative base type, called Prop, and a predicative base type, called Set, both of type Type 0.

On the other hand, in Lean we only have an impredicative base type. We do not have an equivalent to Set. Instead we use directly Type 0(a synonym of Sort 1).

What are the implications of this design decision?

In Coq Set behaves basically like the smallest possible Type. Unlike Coq however, Lean lets you select the "level" of the type manually, such as Type 9 (or Sort 10), something which is not allowed in Coq - meaning that you do not need Set in Lean, you can just use Type 0 (or just Type, or Sort 1) instead as it is basically the same thing.
I should also note that in Lean Prop is the same as Sort 0 (or Sort) (which does not have large elimination) and Type n (for n : nat) is the same as Sort (n + 1) (which has large elimination).

TL;DR: Type (with no "arguments") is the Set of Lean


Using a binary heap to solve an equation I have to find a solution for this equation:

I have to find the set of solutions a, b, c, d for all possible combinations of values 1 <= x <= n.

$a^5 + b^5 = c^5 + d ^ 5$

I first thought about using a heap, because it is what I am learning, but I can't seem to come up with a pattern.

I was told that my algorithm should run in $O(n^2\log(n))$ so I know I would have to use a heap of size n, with n*2 inserts into its structure.

That's as far as I got, can someone hint me?

You can generate all possible triples $(x^5 + y^5, x, y): x, y \in \{1, \dots, n\}$. There are $n^2$ of them. Next you can sort them by first component using heap sort or any other sorting algorithm(it will take $\mathcal{O}(n^2\cdot\log_2(n))$). Now we have $k$ subsequences in sorted sequence where all triples have equal first component. Let's denote $i$th subsequence as $S_i$ and their first component as $c_i$. Each $S_i$ gives $\frac{|S_i| \cdot (|S_i|-1)}{2}$ solutions such that $a^5 + b^5 = c_i = c^5 + d^5$. Number of solutions is $\mathcal{O}(|S_1|^2) + \cdots + \mathcal{O}(|S_k|^2) = \mathcal{O}(n^2)$ since $|S_1| + \cdots + |S_k| = n$.

You also can just build heap on the sequence of all triples. And consequentially extract triples with minimum first component from it. While triples have equal first component they are part of some subsequence $S_i$.

To build heap of size $n^2$ we need $\mathcal{O}(n^2)$ and to extract $n^2$ times minimum from it we need $\mathcal{O}(n^2\cdot\log_2(n))$.


Nth number in a infinite sequence of numbers This was interview question.

When the input is a infinite sequence of numbers starting from 1, what is the nth digit?

e.g.) 123456789101112131415161718192021.....

here 28th digit is 1.

The idea here is as follows:

The first 9 digits are 123456789.
The next 90 pairs of digits are (10)(11)...(99).
The following 900 triplets of digits are (100)(101)...(999).
And so on.

Given an index $n$, you calculate which group you are (singles, pairs, triplets, ...), then which tuple you belong to and which digit inside the tuple. For example, if $n=28$ then this is digit no. 19 in the second group, which is the first digit of the 10th tuple 19, that is, 1.


Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not? I am having difficulties in understanding why the recurrence

$$T(n)=3T(n/4) + n\log n$$

is solvable with Master Method but

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

isn't?

Despite they both look very similar except the values of coefficient '$a$' and size cutter '$b$'.

I understand that the work function '$f(n)$' must be polynomially larger/smaller than $n^{\log_ba}$. And that in second recurrence $n^{\log_22}=n$ is not polynomially comparable to $f(n)=n\log n$. So Master Method cannot be applied. But why can it be applied to the first recurrence?

I found these examples in CLRS Intro to Algo book, and can't understand them. Can you please explain.

Let us use the master theorem as stated on Wikipedia. Consider a recurrence
$$
T(n) = aT(n/b) + f(n).
$$
There are several cases to consider:

If $f(n) = O(n^c)$ for $c < \log_b a$ then $T(n) = \Theta(n^{\log_b a})$.
If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \geq 0$ then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
If $f(n) = \Omega(n^c)$ for $c > \log_b a$ and $f(n)$ is "reasonable" then $T(n) = \Theta(f(n))$.

In the third case, a function is "reasonable" if there exist $k < 1$ and $N$ such that for $N \geq n$, we have $af(n/b) \leq kf(n)$.

There are also extensions of the second case that handle all values of $k$:

If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k > - 1$ then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k = - 1$ then $T(n) = \Theta(n^{\log_b a} \log\log n)$.
If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k < - 1$ then $T(n) = \Theta(n^{\log_b a})$.

Now back to your recurrences. The values of $a,b$ and $f(n)$ are:

$a=3$, $b=4$, $f(n) = n\log n$.
$a=2$, $b=2$, $f(n) = n\log n$.

In the first recurrence, $f(n) = \Omega(n^1)$, where $1 > \log_4 3$, and so, according to the third case of the master theorem, $f(n) = \Theta(n\log n)$ (you have to check that the function $n\log n$ is reasonable).

In the second recurrence, $f(n) = \Theta(n^1 \log^1 n)$, where $1 = \log_2 2$, and so, according to the second case of the master theorem, $f(n) = \Theta(n\log^2 n)$.


How to generate a context sensitive grammar for www I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages
for example how do i proceed on this kind of question.

  Give a context-sensitive (not just length-increasing) grammar for $\{www : w ∈ \{a, b\}^⋆\}$.

Ideas or approaches on how to deal with this kind of questions is much appreciated.

Intuitively you want to generate three intermediate symbols at a time, and allow the symbols to sort themselves. Let $S$ be the start symbol. The generation rules are:

$$S \rightarrow S A_1 A_2 A_3$$
$$S \rightarrow S B_1 B_2 B_3$$
The sorting rules are as follows: For symbols $X_i,Y_i \in \{A_1,A_2,A_3,B_1,B_2,B_3\}$ such that $j < i$ add the rule:
$$X_i Y_j \rightarrow Y_jX_i$$
In the end we have to turn the intermediate symbols into terminal symbols. Turn the start symbol into another symbol $S_1$ to end the generation phase.
$$S \rightarrow S_1$$
Push $S_1$ through the string converting symbols to terminal symbols on the way and increment the subscript when done with one word $w$.
For all $i \in \{1,2,3\}$ add the rules:
$$S_i A_i \rightarrow a S_i \; | \; a S_{i+1}$$
$$S_i B_i \rightarrow b S_i \; | \; b S_{i+1}$$
The subscript of $S$ ensures that the symbols are converted in the proper order as the subscript can not decrease. In the end remove $S_3$.
$$ S_3 \rightarrow \varepsilon $$


Is there a name for the class of operations containing prefix, suffix, etc? I'm currently doing some research on operations on languages, specifically prefix, suffix, infix and outfix.

For example, for a language $L$, the prefix set of $L$ is:

$pref(L) = \{x \mid xy \in L, y \in \Sigma^* \}$

Infix is

$inf(L) = \{w \mid xwy \in L, x,y \in \Sigma^* \}$

and outfix is:

$outf(L) = \{xy \mid xwy \in L, w \in \Sigma^* \}$

I'm wondering, is there a name for the "class" of operations which contains all of these? I think I might have seen "bitfix" used in a paper somewhere, but it seems to mean something different.

In natural languages, at least, the term is affix.


Algorithm for efficiently sorting large lists based on user preference I’ll preface this question by saying I’m having a difficult time even formulating the problem, so my explanation might be fuzzy and/or I might be missing obvious solutions.

I have a list of 479 books which I would like to sort based on a “Fuzzy” criterion such as “which books would I like to read before the others in this list?”.

I took a stab at solving this by storing a record for each book in a database, and pre-populating a rank column with a unique sequential number from 1 to 479. For any particular rank, I’d like to read the corresponding book more than a book with a higher rank number. If the rank number is closer to 1, the corresponding book is one I wish to read earlier.

I created an interface that presents me with a choice between two books selected randomly from the database. After I click the book I would rather read first, the following happens:

If the rank of the selected book is already lower (more interesting) than the other, I don’t change the rank of either book;
If the selected book has a rank that’s higher (less interesting) than the other, I change the selected book’s rank to be the same as the other book, and add 1 to the rank of all the other books where the rank is more than or equal (including the other book, which would now be ranked directly below the selected book).

Finally, for each book I also store a counter of the times it has been evaluated. After I make a selection between two books, this counter increases for both the books that were presented to me. This allows me to avoid presenting books that have already been evaluated a certain number of times until all other books have been evaluated the same number of times.

I found the algorithm to be utterly ineffective: after going through all 479 of the books once, I looked at the list sorted by rank and noticed the list does not reflect at all my own perception of how I’d prioritize these books.

I’m looking for an algorithm that:

Allows me to organize the list in an order that I would perceive to be accurate based on my personal notion of which books I’d like to read first;
Can prioritize the aforementioned list with as little effort required as possible (i.e. an algorithm that requires the user to compare every book with every other book in the list in order to come to a valid sorting order isn’t ideal).

"Being more interesting" is not a transitive property. I can simultaneously find book A more interesting than B, book B more interesting than C, and book C more interesting than A. (On top of that, whether A is more interesting than B might also depend on when you ask me).

I wouldn't use a yes/no decision but let's say a range from -10 to +10, which allows the user to say that a book is much more interesting or just a tiny little bit more interesting than another boo.

I wouldn't modify ranks after each user comparison of two books, but remember all the rankings, and then each time give all the books a ranking, and find one that minimises the difference between the ranking and the user comparisons.

There's probably a good algorithm to do so. A not very good algorithm: Start ranking all books with an "interestingness" of zero. For each set of rankings we can calculate the error: For each user comparison between books A and B, calculate rating (A vs. B) minus (ranking A - ranking B), sum the squares of these.

Pick a book at random and change its ranking to minimise the error while leaving all other rankings unchanged. Repeat until you can't manage to improve it anymore.


Knapsack problem -- NP-complete despite dynamic programming solution? Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right?

I have read it is actually an NP-complete problem, though, which would mean that solving the problem in polynomial problem is probably impossible.

Where is my mistake?

Knapsack problem is $\sf{NP\text{-}complete}$ when the numbers are given as binary numbers. In this case, the dynamic programming will take exponentially many steps (in the size of the input, i.e. the number of bits in the input) to finish $\dagger$.

On the other hand, if the numbers in the input are given in unary, the dynamic programming will work in polynomial time (in the size of the input).

This kind of problems is called weakly $\sf{NP\text{-}complete}$.

$\dagger$: Another good example to understand the importance of the encoding used to give the input is considering the usual algorithms to see if a number is prime that go from $2$ up to $\sqrt{n}$ and check if any of them divide $n$. This is polynomial in $n$ but not necessarily in the input size. If $n$ is given in binary, the size of input is $\lg n$ and the algorithm runs in time $O(\sqrt{n}) = O(2^{\lg n/2})$ which is exponential in the input size. And the usual computational complexity of a problem is w.r.t. the size of the input.

This kind of algorithm, i.e. polynomial in the largest number that is part of the input, but exponential in the input length is called pseudo-polynomial.


How to schedule events optimally given when the events are available? Suppose I had a dictionary that contains events and the corresponding periods they are occurring. For example:

$$
\begin{align}
\textrm{Event 1} &\rightarrow \textrm{[1, 2, 3]} \\
\textrm{Event 2} &\rightarrow \textrm{[2, 4]} \\
\textrm{Event 3} &\rightarrow \textrm{[4]} \\
\textrm{Event 4} &\rightarrow \textrm{[2, 3]}
\end{align}
$$

How would I go about generating a schedule so that the events are scheduled optimally? For the example above, one possible optimal schedule would be:

$$
\begin{align}
\textrm{Period 1} &\rightarrow \textrm{Event 1} \\
\textrm{Period 2} &\rightarrow \textrm{Event 2} \\
\textrm{Period 3} &\rightarrow \textrm{Event 4} \\
\textrm{Period 4} &\rightarrow \textrm{Event 3} \\
\end{align}
$$

Is there any way to do this in better than checking every permutation? This seems like the reverse of the graph-coloring problem for scheduling, so is there any way to construct a graph to encapsulate this relationship and maybe find a shortest path? Can someone point me in the right direction on how to approach this?

I assume that by "optimally" you mean using the least number of periods. Thirst thing is that you can renumerate the dictionary such that there are no gaps in available periods, so:

$$
\text{Event 1} \rightarrow\ [1, 2, 10]\\
\text{Event 2} \rightarrow\ [3, 5, 11, 12]\\
$$

becomes

$$
\text{Event 1} \rightarrow\ [1, 2, 5]\\
\text{Event 2} \rightarrow\ [3, 4, 6, 7]\\
$$

So now the largest number on the right side is not greater then the sum of sizes of lists on the right side. Assume that, there are $n$ events and sum of sizes of lists on the right side is $m$. Now to check if there is a solution, which uses only first $i$ periods we can reduce the lists to the numbers smaller or equal to $i$, so for $i=4$ this example will change to:
$$
\text{Event 1} \rightarrow\ [1, 2]\\
\text{Event 2} \rightarrow\ [3, 4]\\
$$
Now to check if there is a solution for given $i$ we can create bipartite graph with events on one side, periods on the other side and edges between event $e$ and period $p$ if $e$ is available during $p$. If there is matching of size equal to $n$ in this graph then we can schedule events using only first $i$ periods. If we find smallest $i$ with such property then we have a solution to our original problem. It's easy to see that if there is such matching for $i$ then there is also for $i+1$, so we can use binary search to find smallest $i$. This solution will work in time $O(m\sqrt{n+m}\log{m})$ where $O(m\sqrt{n+m})$ comes from finding matching and $O(\log{m})$ comes from binary search.


Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data Suppose there is an n-element stream with elements from $\{0,1\}^\ell$ which means each element is in set $\{0, \dots , 2^\ell-1\}$. Also may assume $2^\ell >n^2$. How can I with $2p$ passes over the data (for $p \in \{1, \dots , 2^\ell\} $) solve the number of distinct elements problem using only $O(\frac{n}{p}\ell)$ bits of memory? Not looking for probabilistic algorithms.

Try something along the following lines. Preform $p$ iterations where each iteration consists of two passes over the stream. The $i$'th iteration first pass remembers all elements whose index $\bmod p$ equals $i$ , denote this collection by $S_i$. The second pass, for each element of the stream whose index $\bmod p$ is greater than $i$, checks if it appears in $S_i$, and if so deletes it. Denote by $S_i'$ the remaining subset after the second pass, then your algorithm returns $\sum\limits_{i=1}^p |S_i'|$.


validation of a pumping lemma proof for regular languages I have the following regular expression:

Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT
I was just wondering, because $L$ is made up of a union of two expressions, is it valid to split $L$ into
$ L_1=\{a^ib^jc^{2j-1} | i<=j \land i,j>0\}$
$L_2=\{a^ib^jc^{2j-1}| i>=2j-1 \land i,j>0\}$
and show for  each $L_1$ and $L_2$ that the pumping lemma does not work on them (so for $L_1$ I just show that for each $k$, $i$ is not smaller or equal to $j$, and similarly for $L_2$.
By that I show that $L_1$ and $L_2$ are not regular which means that the union of the two will also be not regular. Is this correct?
thank you.

the union of 2 non-regular languages can be regular.
The trivial example is any non-regular language L and its complement. The union of those two is the set of all strings, which is a regular language.
There for the conclusion $L1, L2 \notin Regular \implies L1\cup L2 \notin Regular$ does not follow.


Estimation of average waiting time I'm simulating a procedure that assigns tasks to servers and want to estimate the average waiting time until a task is served (finds a free server).
This procedure runs periodically, thus every task that is rejected in a run can try in the next runs until it finds a free server.
The inter-arrival times of tasks follow an exponential distribution.
Between runs, some tasks may finish.

Is there a way to estimate the average waiting time of tasks?

If tasks arrive faster than they can be dealt with, average waiting time is unbounded.

You can probably adapt the Pollaczek–Khinchine formula to give an analytic answer to your question:

$$L = \rho + \frac{\rho^2 + \lambda^2 \operatorname{Var}(S)}{2(1-\rho)}$$

where

$L$ is the mean queue length;
$\lambda$ is the arrival rate of the Poisson process;
$1/\mu$ is the mean of the service time distribution $S$;
$\rho={\lambda \over \mu}$ is the utilization; and
$Var(S)$ is the variance of the service time distribution $S$.


Are there subexponential-time algorithms for NP-complete problems? Are there NP-complete problems which have proven subexponential-time algorithms?

I am asking for the general case inputs, I am not talking about tractable special cases here.

By sub-exponential, I mean an order of growth above polynomials, but less than exponential, for example $n^{\log n}$.

Depends on what you mean by subexponential. Below I explain a few meanings of "subexponential" and what happens in each case. Each of these classes is contained in the classes below it.

I. $2^{n^{o(1)}}$
If by subexpoential you mean $2^{n^{o(1)}}$, then a conjecture in complexity theory called ETH (Exponential Time Hypothesis) implies that no $\mathsf{NP}$-hard problem can have an algorithm with running-time $2^{n^{o(1)}}$.
Note that this class is closed under composition with polynomials. If we have a subexponential time algorithm for any $\mathsf{NP}$-hard problem, we can combine it with a polynomial-time reduction from SAT to it obtain a subexponential algorithm for 3SAT which would violate ETH.
II. $\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$, i.e. $2^{O(n^\epsilon)}$ for all $0 < \epsilon$
The situation is similar to the previous one.
It is closed under polynomials so no $\mathsf{NP}$-hard problem can be solved in this time without violating ETH.

III. $\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$, i.e. $2^{O(n^\epsilon)}$ for some $\epsilon < 1$
If by subexponential you mean $2^{O(n^\epsilon)}$ for some $\epsilon<1$ then the answer is yes, there are provably such problems.
Take an $\mathsf{NP}$-complete problem like SAT. It has a brute-force algorithm that runs in time $2^{O(n)}$. Now consider the padded version of SAT by adding a string of size $n^k$ to the inputs:
$$SAT' = \{\langle \varphi,w\rangle \mid \varphi\in SAT \text{ and } |w|=|\varphi|^k \}$$
Now this problem is $\mathsf{NP}$-hard and can be solved in time $2^{O(n^\frac{1}{k})}$.
IV. $2^{o(n)}$
This contains the previous class, the answer is similar.
V. $\bigcap_{0 < \epsilon}2^{\epsilon n}$, i.e. $2^{\epsilon n}$ for all $\epsilon>0$
This contains the previous class, the answer is similar.
VI. $\bigcup_{\epsilon < 1}2^{\epsilon n}$, i.e. $2^{\epsilon n}$ for some $\epsilon<1$
This contains the previous class, the answer is similar.

What does subexponential mean?
"Above polynomial" is not an upper-bound but a lower-bound and is referred to as superpolynomial.
Functions like $n^{\lg n}$ are called quasipolynomial, and as the name indicates are almost polynomial and far from being exponential, subexponential is usually used to refer a much larger class of functions with much faster growth rates.
As the name indicates, "subexponential" means slower than exponential. By exponential we usually mean functions in class $2^{\Theta(n)}$, or in the nicer class $2^{n^{\Theta(1)}}$ (which is closed under composition with polynomials).
Subexponetial should be close to these but smaller.
There are different ways to do this and there is not a standard meaning.
We can replace $\Theta$ by $o$ in the two definitions of exponential and obtain I and IV. The nice thing about them is that they are uniformly defined (no quantifier over $\epsilon$). We can replace $\Theta$ with a multiplicative coefficient $\epsilon$ for all $\epsilon>0$, we get II and V. Their are close to I and IV but nonuniformly defined. The last option is to replace $\Theta$ with a multiplicative constant $\epsilon$ for some $\epsilon<1$. This gives II and VI.
Which one should be called subexponential is arguable. Usually people use the one they need in their work and refer to it as subexponential.
I is my personal preference, it is a nice class: it is closed under composition with polynomials and it is uniformly defined. It is similar to $\mathsf{Exp}$ which uses $2^{n^{O(1)}}$.
II is seems to be used in the definition of the complexity class $\mathsf{SubExp}$.
III is used for algorithmic upper-bounds, like those mentioned in Pal's answer.
IV is also common.
V is used to state the ETH conjecture.
Intersections (II and V) are not that useful for algorithmic upper-bounds, their main use seems to be complexity theory.
In practice, you will not see a difference between I and II or between IV and V. IMHO the later three definition (IV, V, VI) are too sensitive, they might be useful for particular problems, but they are not robust which decreases their usefulness as classes. Robustness and nice closure properties are part of the reason why famous complexity classes like $\mathsf{L}$, $\mathsf{P}$, $\mathsf{NP}$, $\mathsf{PSpace}$, and $\mathsf{Exp}$ are interesting.
Summary
IMHO, the main definitions are I and III. We already have subexponential algorithms for $\mathsf{NP}$-hard problems in the sense of III and we cannot have them in the sense of I without violating ETH.


How many segments a process can have in operating system employing Segmentation for memory management Some facts about "Segmented Paging"

1)  Each process has one segment table.
2)  There is one-page table per segment.

Fact about "Paged segmentation"

3)  Contains page table of segment table.

Now consider following problem

  In a paged segmented scheme of memory management, the segment table itself must have a page table because.
  (A)  The segment table is often too large to fit in one page.
  (B)  Each segment is spread over a number of pages.
  (C)  Segment tables point to page tables and not to the physical locations of the segment.
  (D)  The processor’s description base register points to a page table

Given solution is:

Here option (A) is true , as segment table are sometimes too large to keep in one pages. So, segment table divided into pages. Thus page table for each Segment Table pages are created.

My Doubt

I believe a page can contain several hundreds of segment table entries of form

  <segment base, limit>

I only came across code, data, stack and heap segments. I believe a process can have only these  "four" segments. And also, we know each process has a segment table (Fact 1). Then how a segment table can grow so large that it cannot be fitted in a single page?

A process can only access 6 segments simultaneously through CS, SS, DS, ES, FS, and GS registers on an x86 and x86-64 machines.

These registers point to an entry in the segment descriptor table that the operating system manages. If OS uses a multi-segment memory model then that table can have an arbitrary size thus allowing a process to access a theoretically unlimited number of segments. (Intel 64 and IA-32 Architectures
Software Developer’s Manual 3-6 Vol.3)


without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP? In the text book, Introduction to Algorithm, 3rd Edition.

In the chapter, Approximation Algorithms and for the problem Travelling Salesman Problem, the author says:

I am wondering how triangle inequality gives rise to this assertion? It seems that this property is not that important, as I searched through the rest of this section, it does not appear.

Here is what these lecture notes have to say. We can reduce HAMILTONIAN-PATH to MIN-TSP-TOUR in the following way: give the weight $1$ for edges in the original graph, and $B$ (for some $B > 1$ to be chosen later) for edges not in the original graph. If the original graph had a Hamiltonian path, then the new path has a tour of length at most $n$, and otherwise any tour has length at least $n-1+B$. Thus any approximation algorithm with ratio better than $n/(n-1+B)$ would solve HAMILTONIAN-PATH. Choosing $B = 1 + (c-1)n$, we get then any algorithm with ratio better than $1/c$ would solve HAMILTONIAN-PATH. This is true for any $c > 1$, so MIN-TSP-TOUR cannot be approximated to any constant ratio.

Here is where the triangle inequality comes in in Christofides' algorithm. The algorithm is at follows:

Construct a minimum spanning tree $T$.
Find a minimum matching $M$ between the set $O$ of odd-degree vertices in $T$.
Remove edges from $T\cup M$ to obtain a Hamiltonian cycle $H$.

The analysis goes like this. Suppose $H^*$ is a Hamiltonian cycle of weight $w(H)$. Then $w(T) \leq w(H^*)$ and $w(H) \leq w(T \cup M) \leq w(T) + w(M) \leq w(H^*) + w(M)$. So far we haven't used the triangle inequality. Now take $H^*$ and replace paths from adjacent vertices $a,b \in O$ on $H^*$ with direct edges. The triangle inequality implies that the resulting cycle $H^{**}$ satisfies $w(H^{**}) \leq w(H^*)$. We can partition the cycle into two matchings $M_1,M_2$ satisfying $w(M_1) + w(M_2) = w(H^{**})$, and so $w(M) \leq \min(w(M_1),w(M_2)) \leq w(H^{**}) \leq w(H^*)$. We conclude that $w(H) \leq w(H^*) + w(M) \leq 1.5 w(H^*)$.


Let a > 0 be a constant. Find a simplified, asymptotically tight bound for the recurrence T(n) = aT(n-2) + C So I have read the posts on this site involving recurrence relations, however this problem is a little different, because of the constant a involved with the recursive portion. I'm trying to solve this recurrence relation by expanding it out and here is what I have so far:

I'm not sure where to go from here and how to find the asmpytotic bounds.

The first four lines of your argument were correct; all you missed was the proper generalization. In general, we see that
$$
T(n) = c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j)
$$
Now we want to drive $T(n-2j)$ down to a value we know, namely $T(1)=c$. To do this we'll need $n-2j=1$ and so we set $j=(n-1)/2$, giving us
$$\begin{align}
T(n) &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j)\\
     &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{(n-1)/2-1}+\alpha^{(n-1)/2} c\\
     &= c(1+\alpha+\alpha^2+\dotsb+\alpha^{(n-1)/2})
\end{align}$$
and this is just a geometric series, so I'll leave the last steps to you.


How are hardware interrupts handled? I have read that a hardware interrupt is handled asynchronously by the CPU, which means that the interrupt signal may arrive at any point of time with respect to the CPU clock cycle. Now, this means that an interrupt may asynchronously hit the processor when it is in the middle of executing some instruction. So, how does the control pass to the OS in this case? For the case of software interrupts (exceptions), we know that the instruction being executed (trap instruction) itself is the cause of the interrupt. So, it will synchronously finish executing and then the control will transfer to the kernel as per the trap instruction nature. How does all this happen for hardware interrupts?

This is architecture specific so the following might not be true for all architectures.

Normally there is a special hardware in the CPU called interrupt controller that will react to interrupts. You usually program this hardware on boot time by writing a handler for each interrupt (called interrupt service routine) and giving the interrupt controller a table with the location of these handlers (the interrupt vector table https://en.wikipedia.org/wiki/Interrupt_vector_table).

When a hardware interrupt happens, the interrupt controller will automatically lookup the location of the corresponding handler and immediately continue execution there (on the very next assembler instruction). Depending on the architecture, there might now be a second set of registers, another stackpointer etc. that the ISR uses or it has to save the status of the interrupted program to the memory (RAM) perform it's actions and restore the state once it finishes.

The ISR is automatically run in a higher privilege mode on the CPU (if not already in a high privillege mode) and can therefore invoke other OS functionality. How the ISR is now interacting with the OS can't be answered in general. It could for example set some flags which are then checked by the OS threads.

Maybe you will also find this answer interesting: https://cs.stackexchange.com/a/85156/108759


Computing 'score' of string which preserves < relation Is there a way to calculate some kind of numerical 'score' for arbitrary strings which when compared with score of some other string will preserve '<' relation?

I've searched for order preserving compression/hashing but what I've found is either based on precomputing with known set of strings or is a some for of lossless compression.

edit:

To clarify - I don't need it to preserve order exactly. When I need is to have guarantee that if score(A) < score(B) than A < B. If score(A) >= score(B) than it still can be true that A < B. I just would be nice if probability of incorrect relation was 'low'.

Suppose that your alphabet has size $N$ (say, $N=256$). You can think of each word as being over an alphabet of size $N+1$, with the extra element (first in the order) representing "end of word". Take a short prefix of the word (of some fixed constant size) and think of it as the base $N+1$ representation of a natural number.

As an example, suppose that the alphabet is $A<B$ (in this order), and that we take prefixes of length 2. Consider the strings
$$
A < AA < AAA < B.
$$
We think of these as the numbers $1,11,111,2$ in base 3. Taking prefixes of length 2, we get $10,11,11,20$ (here you see how the extra element is used). The encodings are thus
$$
3 < 4 = 4 < 6.
$$


Complexity of dynamic programming algorithm for Knapsack Dynamic programming algorithm for Knapsack is stated to have complexity $\mathcal O (nW)$.

However, I've also seen the complexity stated as $\mathcal O (n^2V)$, where $V=\max v_i$.

(Here $n$ is the number of items and $W$ the weight limit).

I see from the algorithm that the first complexity measure is correct:
http://en.wikipedia.org/wiki/Knapsack_problem

Can someone tell me, why the other complexity measure works ?

The first complexity measure is in terms of the target weight, the second in terms of the heaviest element. Since $W \leq nV$ (or rather, we can assume that $W \leq nV$), the first estimate $O(nW)$ implies the second $O(n^2V)$. So $O(nW)$ is a stronger estimate than $O(n^2V)$.


Suffix trees - "smaller half trick" I have been reading a paper Finding Maximal Pairs with Bounded Gap:

An in there, there is a sentence (page 6 second paragraph):

  The “smaller-half trick” is used in several methods for finding tandem repeats,
  e.g. [2, 5, 26]. It says that the sum over all nodes v in an arbitrary binary tree of size n of terms that are $O(n_{1})$, where $n_{1}\leq n_{2}$ are the numbers of leaves in the subtrees rooted at the two children of v, is $O(n\log n)$

Although it sounds very straightforward, I just cannot see why this is true. Could someone with some experience regarding this trick please explain why this is true?
I read several other papers but just don't see it.

We prove by induction on $n$ that your sum (with $O(n_1)$ replaced with $n_1$, only taken over non-leaves) is at most $n\log_2 n$. We use the convention $0\log_2 0 = 0$. The base case $n$ = 0 trivially holds, since the sum is empty. Now suppose we have a node with subtrees of sizes $n_1 \leq n_2$; this implies that $n = n_1 + n_2 + 1$. The sum is at most
$$ S = n_1\log n_1 + n_2\log n_2 + n_1. $$
Let's concentrate on the first two terms:
$$
\begin{align*}
n_1\log n_1 + n_2\log n_2 &= (n_1 + n_2) \left[ \frac{n_1}{n_1+n_2} \log n_1 + \frac{n_2}{n_1+n2} \log n_2 \right] \\ &=
(n_1 + n_2) \left[ \frac{n_1}{n_1+n_2} \log \frac{n_1}{n_1+n_2} + \frac{n_2}{n_1+n_2} \log \frac{n_2}{n_1+n_2} + \log (n_1+n_2) \right] \\ &= (n_1+n_2) [\log(n_1+n_2) - h(\tfrac{n_1}{n_1+n_2})],
\end{align*}
$$
where $h(p)$ is the binary entropy function. Let $p = n_1/(n_1+n_2) \leq 1/2$. Then we can bound $S$ by
$$ n \log n + (n_1+n_2)(p-h(p)). $$
One checks that $p \leq h(p)$ for $0 \leq p \leq 1/2$, completing the proof. (In fact, $2p \leq h(p)$, so we can get the better bound $\tfrac{1}{2}n\log_2 n$, which is nearly tight for complete binary trees.)


Explanation for indirect addressing While reading about minimal instruction set computer I found out that one needs at least (for example) the ability to increment or decrement the value stored in register, a test for zero and a jump.
A machine with such instruction set would be Turing-complete, correct? Is this called "Counter machine"?
But then I found out about the so-called "Random-access machine" which adds "indirect addressing", meaning I can access a register not just by explicitly specifying memory address or label but I can also fetch an address out of an address, like [Rn]. This should be useful for enabling mechanisms akin to "pointers" in C-like languages, for example.
My question is, why there is the need for "indirect addressing"? Since I presume both machines (without and with indirect addressing) are Turing complete, is it "merely" for convenience? Or are some programs which cannot be expressed without indirection?
PS: I'm a complete noob in this area so please bear with me: if I was to implement memcpy, i.e. to transfer the values of bunch of registers to other bunch of registers, how would I do it without indirection? I mean, I can write copy 1 word from x to y, copy 2 words from x to y, ... but in general, how do I say copy n words from x to y without it?
Edit:
For example, imagine I receive zero-terminated string via network, say 1 2 3 0 which I would like to store to some of my infinitely-many registers. Receiving 0 halts the program. I have an instruction take r which copies one word from the input to register r. No indirection means (?) that r has to be a direct constant number. How do I then move to "n-th" register? In other words, I don't understand how do I move back and forth among the registers, when the only mechanism I have is to read/set register 1, 2, 3, ...?

Here is how you can implement indirect addressing without an atomic operation that does so.

We assume that we can label memory cells (either tape cells or registers, or whatever) in some way. This can be implemented by marked copies of the tape alphabet, or a special encoding of the content.

Idea: Addresses are offsets. If you want the $n$th cell, move a marker $n$ steps from the beginning. For that, you maintain a counter at a fixed location (determined by the programmer/compiler). After that, perform your operation on the first marked cell. Remove the marking when you are done.


How is n-gram different from k-mer? How is n-gram different from k-mer? Both seem to be (n or k) length substrings of a larger string. Are these just terms common with different practitioners? viz. Computer Scientists and Bioinformaticians?

Yes, they mean the same thing.  A n-gram is a sequence of n consecutive things (words, letters, whatever).  A k-mer is a sequence of k consecutive things (DNA basepairs).  The phrase k-mer is more common in computational genomics.

See https://en.wikipedia.org/wiki/N-gram and https://en.wikipedia.org/wiki/K-mer for definitions.


Model paths by regular languages I want use DFA to describe a sequence of movements in a 2D-space (language will be  the path accepted by automaton in a particular case).

That is a typical modeling problem: how can I encode a sequence of 2D movements in a DFA?

Infact, walking through DFA or NFA seems a process analogous to walk through point of a maps.

A naives example could be: State like point in space coordinate (x,y); and  Transitions with an alphabet of "up, down, etc".
That's direct approach is impracticable beacuse "the number of locations is infinite or simply too many". I'm looking for a better and more efficient encoding.

Are there any study about using regular languages for coding path, or movements?

If the number of locations (e.g. points or regions) are finite, naively, you can say that these locations are my states and you can directly use a DFA with an alphabet containing UP, DOWN. But you already said it's impracticable for your case.

Then, let's look into where the number of locations is infinite or simply too many. Basically, in this case, you need to recognize that the sequences UP-DOWN, UP-UP-DOWN-DOWN, UP-UP-UP-DOWN-DOWN-DOWN ... etc. are equivalent because equal number of UP and DOWNs gets you back to the starting point. This is the classical example of non-regular languages. Therefore I suggest you looking into other automata such as counter machines if they are sufficient to capture your intentions.


Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b } I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }.

This is really confusing me, I'm having trouble with making sure that b is always in the middle. Any help?

PDA:

Here is a guideline to solve this problem:

Try to think how to "count the letters until the middle", then "guess" where the middle is, and then "verify that your guess was really the middle, by counting once again"

CFG:

$S\rightarrow b\space | \space xSy$ for every $x,y\in \{a,b\}$

Yea, thats everything in the CFG!


Understanding this explanation about Big O notation I'm trying to learn the Big O Notation...and I got a bit confused by this article:

https://brilliant.org/practice/big-o-notation-2/?chapter=intro-to-algorithms&pane=1838

where it stands that f(x) = 4x and g(x) = 10x, (...), and that one could look at the Big O Notation by dividing f(x) by g(x): 10x/4x

Shouldn't it be 4x/10x instead in this very example? (since f(x) = 4x and g(x) = 10x) Or is just me who got it all wrong?...

Kind regards,

c

The best way to look at big $O$ notation is the following: $f(x)$ and $g(x)$ have the same $O$ complexity if you can find a positive constants $c_1, c_2 \in \mathbb{R}$ such that $f(x) \leq c_1 \cdot g(x)$ and $g(x) \leq c_2 \cdot f(x)$ for all $x$.

So, for example $4x$ and $10x$ are both in the same complexity class because $4x \leq 1 \cdot 10x$ and $10x \leq 3 \cdot 4x$. We name the complexity class they belong to $O(x)$, because $x$ is the simplest of all expressions of the form $c \cdot x$ so we use it as a representative.

Also, one can write equalities with big $O$;
$$O(4x) = O(10x) = O(x) = O(192839182x) \neq O(x^2) $$

Some basic complexity classes are (in order of complexity, from lower to higher):

$O(log n)$
$O(n)$
$O(n log n)$
$O(n^2)$
$\ldots$
$O(n^k)$
$\ldots$
$O(2^n)$
$\ldots$

and every complexity class on this list is not equal to any other.


How to find the pumping length of a context-free language? Please help me understand, and if possible, tips, to determine a pumping length $p$.

Suppose I have the example :

Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,C\}$, set of terminals $\{0,1\}$, start variable $S$, and rules

$S \to ABA \mid SS$
$A \to S0 \mid 1C1$
$B \to S1 \mid  0$
$C \to 0$

Now given the above, how do I find the pumping length $p$?
Please explain how you actually got it from the grammar.

As Raphael says in the comments, any sufficiently large number is suitable as a pumping length, however (also as he points out), the proof of the pumping lemma gives an upper bound for the minimum pumping length.

Similar to the pumping lemma for regular languages, we want to take a length that is sufficiently large that we can guarantee that we have used the same production at least twice. For regular languages this often easy to think of as the number states in a minimal DFA for that language.

For context free languages expressed with a grammar, we can take a similar approach and ask "how many symbols can be in the string before I know that I must have used some production twice?". To figure this out you may want to consider how many symbols any production could insert into the string, and what the parse tree for a sufficiently long string may look like (you can consider each level of the tree to be one production). If you do this correctly you can get a minimal pumping length for that grammar (not exactly a precise concept), then taking the minimum of these minimal lengths over all grammars for the language will give you the minimum for the language.

Further hint:

   If there's a rule with $m$ symbols on the right hand side, and the parse tree is $d$ levels deep, what's the maximum number of symbols in the string?


Number of Hamiltonian cycles on a Sierpiński graph I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other tags would be more appropriate.

I am trying to solve this problem for which I need to compute the number of Hamiltonian cycles $C(n)$ in the $n$th order Sierpinski-graph $S_n$. (Please also see the above link for the definition and pictures of Sierpinski-graphs)

I have found $C(n)$, but I must have messed up something, because my solution does not match the given value $C(5) = 71328803586048$. My argumentation consists of very basic thoughts, and I cannot find the mistake. Any help is greatly appreciated. Even if it seems lengthy, the thoughts become trivial if you look at the graphs while following.

(a) In a given graph $S_n$ call the outer corners $A,B,C$. Then I define the following quantities:

$N(n) := $ the number of Hamiltonian paths from $A$ to $C$.

$\bar{N}(n) := $ the number of paths from $A$ to $C$ which visit each node once except $B$.

I will also call such paths $N$- or $\bar{N}$-type paths in the following.

(b) It is easy to see that $N(n)=\bar{N}(n)$.

The reason is the following: Consider a $N$-type path. Starting at $A$ this path is of the form $(A,...,X_1,B,X_2,...,C)$. By replacing the segment $(X_1,B,X_2)$ by $(X_1,X_2)$ we obtain a $\bar{N}$-type path. This operation uniquely maps all $N$-type paths to $\bar{N}$-type paths.

(c) We derive the recursion $N(n+1)=2N(n)^3$.

Consider an $N$-type path from $A$ to $B$ and denote the subtriangles at the outer corners $A,B,C$ by $T_A,T_B,T_C$, respectively. It is clear that the $N$-type path will visit each subtriangle exactly once starting from $T_A$ over $T_B$ to $T_C$. Now consider the node $Z$ at which the subtriangles $T_A$ and $T_C$ touch. There are two possibilities, when this point is visited by the path, either (i) before leaving $T_A$ or (ii) after entering $T_C$. In these cases the three subpaths inside $T_A,T_B,T_C$ are of the types (i) $N,N,\bar{N}$ or (ii) $\bar{N},N,N$, respectively. With this in mind we can count

$N(n+1)=N(n)N(n)\bar{N}(n)+\bar{N}(n)N(n)N(n)$ and with (b) we arrive at the upper recursion.

(d) We solve the recursion (c) with $N(1)=1$ and obtain $N(n)=2^{3^0+3^1+...+3^{n-2}}$.

(e) Consider a Hamiltonian cycle in the graph $S_n$. As each of three subtriangles is connected to the others via two nodes only, it is clear that the cycle will enter each subtriangle exactly once via one connecting node, then "fill" it, an finally leave it via the other connecting node. Hence the Hamiltonian cycle in $S_n$ consists of three $N$-type subpaths in the subtriangles which all have the structure of $S_{n-1}$. We can conclude for the number of Hamiltonian cycles

$C(n) = N(n-1)^3$.

However it follows for $n=5$

$C(5) = N(4)^3 = 8192^3=549755813888 \neq 71328803586048$

where the latter should be obtained according to the problem page (link above).

Thanks again for any help or comments.

Nice idea! The problem seems to be in step $(b)$. Replacing $(X_1,B,X_2)$ in an $N$-path by $(X_1,X_2)$ gives an $\bar{N}$-path, but not every $\bar{N}$-path will contain $(X_1,X_2)$. So this is not a bijection. This only says $N(n) \leq \bar{N}(n)$.

Or you can in fact show that $\bar{N}(n) = 3N(n)/2$, resulting in $N(n+1) = 3N^3$.


How Data Compression relates to Estimating Distribution? I recently read this paper Mahoney, 1999.
And encountered this line,

optimal compression of a probabilistic language L with unknown distribution (such as English) using an estimated distribution M (an encoding of length −log2 M(x) bits for each string x) is M = L, by the discrete channel capacity theorem.

Can you please explain what this means and what is the relation between data compression and estimation of distribution?

Suppose that we have a random source $X$, and we wish to encode many independent samples $x_1,\ldots,x_n$ taken from $X$. An compression scheme is an algorithm that converts $n$ samples of $X$ to a binary string in a reversible way. Shannon showed that the optimal compression scheme produces binary strings of length roughly $nH(X)$, where $H(X)$ is the entropy of $X$.
In practice, we may have access to $X$ but might not know its distribution exactly. What we can do is to estimate its distribution as $Y$, and then use an optimal compression for $Y$. This will produce binary strings of length roughly $n(H(X) + D(X\|Y))$, where $D(X\|Y)$ is the Kullback–Leibler divergence (called cross-entropy by Mahoney). We have $D(X\|Y) \geq 0$, with equality only when $Y = X$. Thus optimal compression requires knowing the distribution of the source exactly.


Algorithm that finds concise representations of sets of pairs using Cartesian products I feel like there should be a known algorithm to the following problem, but I am short of ideas how to construct or search for it.

Suppose as an input you have a list of two-dimensional data points (xi, yi). Your goal is to "simplify" this data by providing an output that is equivalent to the input, but grouped together using structures like this: ({x1, x2, .., xn}, {y1, y2, .., ym}), which denotes a set of all (xa, yb) where a ∈ {1, 2, .., n} and b ∈ {1, 2, .., m}. A perfect result is to have as few of these structures + remaining data points as possible.

Some points to consider:

The output can be a combination of simple data points and such
structures.
The structures in the output should be mutually
exclusive.
It may as well be that there is no way to simplify a given
input.

Example 1:

Input: (1, 1), (1, 2), (2, 1), (2, 2), (4, 5) Output: ({1, 2}, {1, 2}), (4, 5)

Example 2:

Input: (1, 1), (1, 2), (1, 3), (4, 5) Output: ({1}, {1, 2, 3}), (4, 5)

Example 3:

Input: (1, 2), (2, 2), (3, 2), (2, 1), (2, 3) Output: ({1, 2, 3}, {2}), ({2}, {1, 3})

For a given set $S$ of points, we construct a bipartite graph $B=(X\cup Y,E)$ such that there is an edge $(x,y)\in E$ iff there is a point $(x,y)\in S$.
The biclique decomposition problem asks for the minimum number of bicliques (complete bipartite subgraph) of $B$ whose edges partition the edge set $E$ of $B$. Since a biclique in $B$ corresponds to a structure defined in this problem, an algorithm that solves the biclique composition problem also solves this problem.

Conversely, we can also transform the biclique decomposition problem into this problem as follows. Given a bipartite graph $B=(X\cup Y,E)$, where $X=\{x_1,x_2,\ldots x_p\}$ and $Y=\{y_1,y_2,\ldots y_q\}$, we create a set $S$ of points such that $(x_i,y_j)\in E$ iff there is a point $(i,j)\in S$.
Consequently, the problem is equivalent to the biclique decomposition problem. However, the biclique decomposition problem is NP-hard, and therefore it is unlikely to solve it efficiently on general bipartite graphs.
Note that the problem is equivalent to ``biclique cover'' if the structures are allowed to be overlapped, i.e., a point can be in more than one structure.


Difference between delayed branches and out-of-order execution I have been reading about instruction pipeline and I stumbled upon the term delayed branches. From what I have understood, delayed branches will keep the pipeline busy, by executing instructions, regardless of the outcome of the branch. This will avoid the usages of NOP instructions.

What I do not understand is, how is it it different than Out-of-order execution? In the following example, which I just made up:

1    MOV eax, 5
2    MOV ecx, 6
3    MOV ebx, 2
4    CMP eax, ecx
5    JG label1
6    SUB ecx, ebx
7    CALL someFunc
8 label1:
9    SUB eax, ecx
10    CALL someOtherFunc

if I have understood delayed branches, before the decision is made, whether the jump to label1 will occur, the instructions on line 6 and 7 will be loaded in the pipeline. But isn't this exactly out-of-order execution?

I suppose you could view branch delay slots as a very special sort of out-of-order execution, but this isn't usually what we mean when we talk about out-of-order execution: generally, we're referring to a CPU that has a more general mechanism to detect when instructions can be re-ordered.  In addition, usually out-of-order execution takes care to avoid changing the semantics/behavior of the instructions.  In contrast, a branch delay slot does change the behavior of the instructions (because it affects whether the instruction after the branch is executed or not).


How to use c-gap problems to prove inapproximability? Suppose there is a specific set function with some properties -  $f=2^V\to \mathcal{R}$. It is known that the following problem is NP-Hard: Find $S\subseteq V, |S|\leq k$ such that $f(S)$ is maximized. My goal is to show that designing a constant factor approximation algorithm in polynomial time is NP-Hard.

Correct me if I am wrong: As per these notes on gap reductions, we can design a c-gap problem with $OPT$ being the maximum value of $f$. The problem takes as input $\beta$. The goal is to answer YES if $OPT\geq \beta$. NO if $OPT< c\cdot \beta$. (here $c<1$).

To show the desired inapproximability, it would suffice to show the above c-gap problem is NP-Hard. My question is: Why is it this decision problem is designed for one $\beta$ when the optimimum value for the maximization problem is not known? Is the idea that, suppose you have a solver for the c-gap problem, you can call it with multiple values of $\beta$? If so, how many calls are possible?

Also any additional references on proving inapproximability would be greatly appreciated.

One way to show that there is no polynomial time approximation algorithm with ratio $c$ for a certain problem X (assuming P≠NP) is to give a reduction $f$ from an NP-hard problem Y to X such that:

If $x$ is a Yes instance then the optimal value for X is at least $\beta(x)$, where $\beta(x)$ can be computed from $x$ in polynomial time.
If $x$ is a No instance then the optimal value for $X$ is less than $c\beta(x)$ (for the same $\beta(x)$).

Any approximation algorithm for X whose approximation ratio is $c$ can be used to solve Y via the reduction $f$. Therefore, there cannot be any such efficient approximation algorithm unless P=NP.

I'll let you figure out the proof of these two statements.