What crossover operator should I use for arranging students in classrooms? I am building a genetic algorithm to solve a "classroom map" problem. The goal is to place correctly students depending on several factors (shortsighted students, turbulent students...).
Here, the genomes is the classroom layout, each classroom has a fixed blackboard and tables positions, what varies is the position of the students.
Now, if I want to cross two classrooms genomes, I can't simply mix both together, otherwise, say that on genome A student "Bob" is on table #3, and that on genome B the same student "Bob" is on table #15, and that the "child genome" gets table #3 from genome A and table #15 from genome B, then, "Bob" would be on two tables at the same time... no really great.

How can I solve this issue ?

Thank you.

What you're (probably) doing:

0 = Bob
1 = Mary
2 = John
3 = Susan

parents
[2 | 1 | 0 | 3] => John takes first seat, ..., Susan takes fourth seat.
[3 | 2 | 1 | 0] => Susan takes first seat, ..., Bob takes fourth seat.
       ^
one point crossover
[3 | 2 | 0 | 3]   Where is Susan? (and Mary?)
[2 | 1 | 1 | 0]

What you can do:

allow the generation of an invalid chromosome / individual assigning a
very low fitness value. Such individual will be penalized (ignored) during evolution.

This is very time consuming and not effective
repair an invalid chromosome. It's time consuming but it could work
use ad-hoc operators.

E.g. with Partially Matched Crossover:

(from Genetic Algorithm)

PMX builds an offspring by choosing a subsequence from one parent preserving as many positions as possible from the other parent.

  A subsequence is delimited by two cut points. After this, the segments between the cut points are swapped (the positions in yellow). We have the map: 1↔8, 9↔5, 8↔7 and 6↔3.
  Fill the positions for which there is no conflict. In the example shown, the positions 4 and 2 in both chromosomes (the positions in blue).
  Use the map to fill the remaining positions (the positions in green). Note that using the mapping 1↔8 in the o1 vector a conflict occurs again so one must apply the mapping 8↔7 to obtain a number not repeated.

Other operators are listed in  Crossover for ordered chromosomes but pay attention to the fact that some operators tend to preserve the relative positions more than the absolute positions.
change point of view / representation.

E.g. [2 | 1 | 0 | 3] or [3 | 2 | 1 | 0] are permutations. Standard GA crossover operators produce offspring which aren't permutations. A clever representation of permutations could avoid the problem.

You can represent a permutation as its inversion sequence: for each element i, store in a[i] how many elements larger than i are to the left of i in the permutation.

The only constraint on a[i] is that it cannot be larger than N - i (N is the number of genes).

Now standard crossover of two valid inversion sequences always produces two valid inversion sequences: no need for special handling of repeating elements.

This idea is described in Genetic Algorithm Solution of the TSP
Avoiding Special Crossover and Mutation (Göktürk Üçoluk).


Scheduling Problem Optimisation using LP solvers I am currently working on a scheduling system which schedules individuals based on timeslots that have the following attributes: (1) Day of Week (2) Month (3) Session(AM/PM).

The individuals currently indicate their preference for whether they prefer the AM/PM session for each day of the week in each month eg. (Monday|Jan|AM), this would mean that the person would prefer to do AM session for Mondays of January. Furthermore they are allowed  to indicate that they do not want to be scheduled for certain months of the year, eg. he's able to choose that he does not want to do February time slots and thus my system is required to schedule him accordingly. [Complexity]

As such I currently am required to schedule this large set of data (individuals - 30 people / timeslots - 202). [Large Set]

I have been referred to by some advisors to look into Integer linear programming / linear programming in order to help me schedule these individuals optimally, thus I am currently looking into libraries such as Gurobi to help optimise the solution of this issue. I hope to be enlightened about the following question:

Would solution optimisers such as Gurobi be implementable in my scenario?

Yes, your program can be modelled as an integer linear programming (ILP) instance, and yes, Gurobi is an ILP solver and can be used to solve your problem once you express it as ILP.  I suggest you spend some quality time with a textbook that describes linear programming and integer linear programming.


Knuth's proof of O(1) for linear probing I'm currently reading Knuth's proof about O(1) number of probes in
linear probing. I have a small question on the page 536 (Volume 3, 2nd Edition). Knuth says

  Let $f(M, N)$ be the number of hash sequences such that position 0 of the table will be empty after the keys have been inserted using linear probing.
  The circular symmetry of linear probing implies that position 0 is empty just as often as any other position, so it is empty with probability $1 - \frac{N}{M}$; in other words $f(M, N) = (1 - \frac{N}{M})M^N$.

I explain to myself as follows.
Each hash sequence has $M-N$ empty positions, then the total number of
empty positions is $(M-N)M^N$ and -- due to the symmetry -- each position is empty for $(M-N)M^N / M = (1 - \frac{N}{M})M^N$ hash sequences.
Thus, the probability of zero position to be empty is $(1 - \frac{N}{M})$.

The problem is that Knuth first states that the probability that 0 position is empty is $(1 - \frac{N}{M})$ and after says that $f(M, N) = (1 - \frac{N}{M})M^N$. I'm able to prove this only in other way around.
Could please anybody explain how to prove the probability without showing
that the total amount of empty positions is $(M-N)M^N$.

Thank you.

Let $p_i$ be the probability that position $i$ is empty. A simple coupling (detailed below) shows that $p_i = p_j$ for all $i,j$, and so $Mp_0 = p_0 + \cdots + p_{M-1}$. Now let $X_i$ be the indicator for the event "$i$ is empty". Then $$p_0 + \cdots + p_{M-1} = \mathbb{E}[X_0] + \cdots + \mathbb{E}[X_{M-1}] = \mathbb{E}[X_0 + \cdots + X_{M-1}], $$
using linearity of expectation. But $X_0 + \cdots + X_{M-1} = M-N$, since exactly $N$ positions are full and $M-N$ are empty. Altogether, we get
$$
p_0 = \frac{p_0 + \cdots + p_{M-1}}{M} = \frac{M-N}{M} = 1 - \frac{N}{M}.
$$

Now for the coupling argument. Let $A = a_0,\ldots,a_{N-1} \in \{0,\ldots,M-1\}^N$ be a uniformly random insertion sequence, and let $B = b_0,\ldots,b_{N-1}$, where $b_t = a_t + j-i \pmod{M}$. Denote the final resulting hashtables by $H_A,H_B$. You can prove by induction that $H_A(p) = H_B(p+j-i\bmod{m})$ for every $p \in \{0,\ldots,m-1\}$ (the induction is on the number of insertions), and so $H_B(j) = H_A(i)$. In particular, cell $i$ is empty in $H_A$ iff cell $j$ is empty in $H_B$. Now $H_A$ and $H_B$, when considered individually, are generated by a uniformly random insertion sequence, and so the probability that $H_A(i)$ is empty is $p_i$, and the probability that $H_B(j)$ is empty is $p_j$. This shows that $p_i = p_j$.


Comparisons of functions, their big-oh and their implications I don't understand why the $1^{st}$ is false but I think I see why the $2^{nd}$ is true.

If $f(n) = O(n^2)$ and $g(n) = O(n^2)$,  then $f(n) = O(g(n))$.

If $f(n) = O(g(n))$ and $g(n) = O(n^2)$,  then $f(n) = O(n^2)$.

I understand why the second is true but not the $1^{st}$. For case 1, if

$f(n) < c_1n^2$ for some $n > n_1$ and
$g(n) < c_2n^2$ for some $n > n_2$

by using constants instead of big-O notation , can't we find $c_3$ such that $f(n) < c_3g(n)$ for some $n > n_3$ ?

As a counterexample you can take $f(n)=n$ and $g(n)=\sqrt{n}$. You can think that $f(n)=O(n^2)$ means that an upper bound for $f(n)$ is $n^2$ (of course, without considering multiplicative constant), so the fact that both $f$ and $g$ are bounded by $n^2$ does not implies nothing about the relative behavior of $f$ and $g$.


Power method to calculate eigenvectors I've implemented a program for computing eigenvectors of some random, symmetric, $N$x$N$ matrix using the power method.  I have found difficulty in calculating all $N$ eigenvectors consistently, almost every time the algorithm fails to converge for all $N$.  The Wikipedia page on the power method tells me this algorithm is not guaranteed to converge for all $N$ eigenvectors, can someone suggest a way for me to encourage convergence, at least in a majority of the cases?  Is this possible?  If not, can someone suggest a better algorithm for computing eigenvectors?

Whole books and fields of research are devoted to methods for computing eigenvalues and eigenvectors. Properties of the matrix matter, a lot. The ideal method will depend on whether

the matrices are symmetric or nonsymmetric,
positive definite or indefinite,
sparse or not sparse,
you need all the eigenvalues/vectors or just a few,
you have $O(1)$ access to the elements of the matrix or just the ability to apply it to vectors via a function call
etc...

That said, at the core of most modern methods for finding all the eigenvalues of a generic matrix is the The QR algorithm (the eigenvalue algorithm, not the related orthogonalization algorithm). The methods most used in practice such as the Arnoldi iteration (or Lanczos for symmetric problems) are basically a 2 step process in which the matrix is converted into a nicer form, and then the QR algorithm is used.

Understanding the power method is a good place to start from because it's intuition informs most of the other methods in some way or another.


What is the simplification of AB + BC + (~B)C? AB + C is not the answer.
The correct answer is AB + BC.  HOW?

Imo there is a problem in the proposed options. Indeed,

$AB+BC+(\neg B)C=AB+(B+\neg B)C=AB+C$

You can check that also comparing the truth-tables of
$AB+BC+(\neg B)C$ and $AB+C$.


Finding an Uncomputable Function Let there be 2 sets $X$ and $Y$, both are countable (assume the bijection from $\mathbb{N}$ to the respective sets is computable) and infinite. Let $S$ be the set of all possible functions (NOT necessarily computable, i dont care about computability at this point) from $A$ to $Y$ for all $A \subset X$ (Remember that $A$ is not fixed here and it varies to cover all subsets of $X$. Note that $X$ and $Y$ are fixed in this question).I understand that $S$ is uncountable (as the number of subsets of $X$ will be uncountable) and hence all functions in it cannot be computable because there are countable number of computable functions. My question is that if there are indeed uncomputable functions in $S$, can somebody please give me an example of one such function or example of a subset of $S$ which contains only uncomputable functions ?

Thankyou!

Your definition is a complicated way to say that $S$ is the set of partial functions $X\to Y$ (the sets $A$ you choose are the domains of the partial functions).

Now, if you want to talk about computability, you have to be more precise on $X$ and $Y$: every element of $X$ and $Y$ have to be finitely described, so that they can be manipulated by algorithms.

We can for instance consider that $X=Y=\mathbb{N}$. Since they are countable and infinite, we just have to apply some bijections to get this.

Now, the framework you define is exactly the one of computability theory, you can define turing machines etc, and find out what the uncomputable are. Go here for more details.

For instance the halting function (which is in fact a function $\mathbb N\to \{0,1\}$) is uncomputable.
As for an example of subset of $S$ which contains only uncomputable functions, it is true as soon as the domain of the function is not a recursively enumerable set.
For instance there is no recursive function $NH\to \mathbb N$, where $NH$ is the set of indices of Turing machines that do not halt on input $0$.


How to solve a problem about balancing parentheses with smileys? I'm new to dynamic programming and find a problem about balancing parentheses and smileys ":)" and "(:" at HackerRank, which is impossible to do.
I've been trying to solve it by 3 days now. The main issue with this problem is that the input string size is in range of 10^9 (creating a dynamic programming 2d array of size 10^9*10^9 takes forever) and no matter what I try the execution time out. Someone please help.
Here is the problem about balancing parentheses and smileys ":)" and "(:"

The problem confused me as well until I understood that smileys can be separated into a colon and a parentheses if required (because a colon as the text says is also a valid character.) Now you can write a linear algorithm. By counting how many brackets are open, how many could be opened by smileys and how many could be closed by smileys:
int main() {
    int n; string s;
    getline(cin,s); n = stoi(s); // get value of n
    for(int i = 0; i < n; i++){
        getline(cin,s);          // read line
        ll open = 0, smiopen = 0, smiclose = 0;
        bool colon = false;      // was the last character a colon?
        bool balanced = true;
        for(ll j = 0; j < s.size(); j++){
            if(colon){
                if(s[j] == '(') smiopen++;  //you COULD open an expr.
                if(s[j] == ')' && open > 0) {open--; smiclose++;} // you COULD close an expr.
            }else{
                if(s[j] == '(') open++; // you HAVE TO open an expr.
                if(s[j] == ')') {       // you HAVE TO close an expr.
                    if(open > 0) open--;
                    else if(smiopen > 0) smiopen--;   //open an optional expr. for balance
                    else if(smiclose > 0) smiclose--; //unclose optional close
                    else{ balanced = false; break;}   //not possible to match found ')'
                }
            }
            colon = false;
            if(s[j] == ':') colon = true;
        }
        if(balanced && open == 0) cout << "YES"<<endl;
        else cout << "NO"<<endl;
    }
}

You might notice smiopen and smiclose could be fused into one variable. But I separated them for clarity.


Is determining if there is a prime in an interval known to be in P or NP-complete? I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval.   However, does this mean that the overall decision problem of: (Does there exists a prime in an interval?) is in P. (There were a lot of answers to that post that I did not read so I apologize if this question is a duplicate or unnecessary).

On the one hand, if the interval is large enough (for example $[N,2N]$) then something like Bertrand's Postulate applies and there is definitely a prime in this interval.  However, I also know that there are arbitrarily large gaps between two primes (for example $[N!,N!+ N]$.

Even if the decision problem is in P I don't see how the corresponding search problem is also tractable because, then we may not be able to draw on the same properties regarding the known distribution of primes when performing binary search.

So your problem is as follows:
Input: integers $\ell,u$
Question: does there exist a prime in $[\ell,u]$?
As far as I know, it is not known whether that problem is in P or not.
Here's what I do know:

Primality testing (given a single number, test whether it is prime) is in P, so if the range is small enough, you can exhaustively test each number in the range to see whether it is prime -- but this does not lead to a general algorithm.

If Cramer's conjecture is true, then the problem is in P.  Cramer's conjecture says that the gap between consecutive primes near $n$ is $O((\log n)^2)$, so the following algorithm will be in P: iterate through the numbers $\ell,\ell+1,\ell+2,\ell+3,\dots$, testing each whether it is prime; if you find one that is prime, stop immediately with a yes answer; if you hit $u$, stop with a no answer.  Cramer's conjecture tells us that you'll stop after most $O((\log \ell)^2)$ primality-tests, so that algorithm will run in polynomial time.
Unfortunately, the known results on prime gaps don't seem strong enough to prove unconditionally that the problem is in P.

Here is another simple algorithm: repeatedly pick a random integer $r$ from $[\ell,u]$, and test whether it is prime.  Stop if you find a prime, or if you've tried every integer in $[\ell,u]$ and none were prime.  Heuristically, we should expect this to be efficient in practice.  The prime number theorem tells us that if you randomly choose number in the vicinity of $u$, the probability it is prime will be about $1/\log n$.  Thus, heuristically, we should expect that after about $O(\log u)$ iterations, you'll typically find a prime and stop, if one exists.  On the other hand, due to the coupon collector's problem, if there is no prime in the range $[\ell,u]$, you'll stop after about $O((u-l) \log(u-l))$ iterations.  So, if we had a good upper bound on the size of the longest gap between prime numbers, this would imply that the problem is in BPP.  Even without such an upper bound, it follows that random problem instances are easy.

Probably one can apply sieving methods to improve the running time in practice (e.g., to avoid doing any primality testing on numbers that are divisible by a small prime).  I don't know whether this can be shown to lead to any asymptotic improvement.

Due to these techniques, the problem is probably easy in practice.

Due to the above remarks, I personally doubt that the problem is NP-complete.


Finding similar high dimensional real vectors I have a collection of vectors $v_1,v_2\in [0,1]^n$ and I want to find similar pairs quickly. For similarity, I want to use the Euclidean distance metric $L: [0,1]^n \times [0,1]^n \longrightarrow R$. $n$ will be around $200$.

I've implemented Locality Similar Hashing (LSH) for word based documents, and I'm curious if there's an adaptation of it which will work for real based vectors.

I read here on Computer Science Stackoverflow that universal hashing will work.

If I have the vector $s=(0.55, 0.34, 0.90, 0.99)$ I can break it up into two sub vectors $s_1=(0.55, 0.34)$ and $s_2=(0.90, 0.99)$ and apply a universal hash to each:

$h_n= a\cdot s_n \space mod \space p$

Where $a$ is a random vector and $p$ is prime. I can now define a space of bins, where each $h_n$ defines a bin in this space. Each vector with a subvector in $h_n$ is mapped to the bin $h_n$

The problem is that this method is too precise. The vectors $(0.57, 0.34)$ and $(0.55, 0.34)$ are very similar but will get mapped to different bins.

I'm wondering if it's there's any theoretical and practical issues with either truncating the last digit or rounding up/down such that both vectors are now mapped to a bin representing the vector $(0.5, 0.3)$

This I believe is equivalent to multiplying all the vector elements by 10 and truncating the decimals, leading back to normal LSH.

I'm quite new at all this, so please forgive the slight errors in notation or understanding.

One approach: Quantization

One approach is to quantize the values, then apply an existing LSH that works on discrete values.  In other words, you split up the space $[0,1]$ into several ranges, map each real number to its containing range, and then apply an existing LSH that works with discrete values.  This is essentially equivalent to first truncating each coordinate of the vector, then applying some discrete LSH.

For example, suppose you split the interval $[0,1]$ up into ten ranges, $[0,0.1)$, $[0.1,0.2)$, ..., $[0.8,0.9)$, and $[0.9,1.0]$.  Now you can map any value in $[0,1]$ to its corresponding range -- this is basically just truncating to keep only the first digit in the decimal representation.  Map each interval to a digit from 0 to 9: e..g, $[0,0.1) \mapsto 0$, etc.  In this way, given any vector $v \in [0,1]^n$, you can get a new vector $w \in \{0,1,\dots,9\}^n$.  For instance, the vector $v=(0.55,0.34,0.90,0.99) \in [0,1]^4$ maps to the new vector $w=(5,3,9,9) \in \{0,\dots,9\}^n$.

The new vector $w$ is in a discrete space, rather than in a continuous space.  Now if you have a LSH that works on this discrete space, you can apply it to $w$.  For instance, suppose $h_1:\{0,\dots,9\}^n \to \mathbb{R}$ is a locality-sensitive hash (LSH) on this discrete space.  Let $f:[0,1]^n \to \{0,\dots,9\}^n$ be the mapping that sends each real number to its corresponding range, i.e., $f(v)=(g(v_1),\dots,g(v_n))$ where $g(x)= \lfloor 10x \rfloor$ is the truncation map $g:[0,1] \to \{0,\dots,9\}$.  Define $h_0 : [0,1]^n \to \mathbb{R}$ by
$$h_0(v) = h_1(f(v)).$$
Then $h_0$ is a LSH on continuous values.

If you plan to generate multiple different LSHs, it's probably slightly better to apply the following tweak.  Pick a random $n$-vector number $r \in [0,0.1)^n$.  Now the LSH for $[0,1]^n$ is defined to be $h_0(v) = h_1(f(v+r))$ as above, where $f:[0,1]^n \to \{0,1,\dots,10\}^n$ is the truncation map defined as above and $h_1:\{0,1,\dots,10\}^n\to\mathbb{R}$ is a LSH on discrete values.  This tweak lets you generate multiple independent LSH's for $[0,1]^n$.  If you are only picking a single hash function, you can skip this step.

There's nothing special about base-10.  Instead of using base-10, you can also use base-2 or any other base.  The performance will depend upon the base you use as well as the specific discrete LSH you choose, so you might need to play with the options to see which is best overall.  I suspect you will find that the optimal choice of base is base $b=2$ or $b=3$ (and, if your discrete LSH is based upon hashing a random subset of the coordinates, choosing a subset of size proportional to $\sqrt{n}/b$), but it's not possible to give a hard-and-fast rule: the optimum depends to some extent on the distribution of your data.  That's why I suggest trying a few different parameter choices to see which seems to work best on your data.

This is basically the "truncation" idea in your original post (truncate all real values, then apply a discrete LSH), but now we apply it to the entire vector, rather than trying to split the vector in half.  Of course, the discrete LSH might itself work by picking a few randomly chosen coordinates and hashing only those coordinates (e.g., using a universal hash).

Another approach: Use a LSH designed for continuous values

There are also some LSH's that are designed specifically for continuous real numbers.  I don't know if there are any for the Euclidean distance.

A totally different approach: nearest-neighbor data structures

Finally, it's worth mentioning that there are also other approaches to this problem that don't involve LSH's at all.  There are some data structures that are designed to support nearest-neighbor search (or approximate nearest-neighbor search).  You might look at metric trees, k-d trees, and nearest-neighbor search.

However, beware of the curse of dimensionality.  If the dimension $n$ is large, none of these approaches are likely to work well: high dimensions are just plain hard.  For instance, one rule of thumb I've seen is that k-d trees tend not to work well when $n \ge 30$.  I'm not sure any of these techniques will be terribly effective when $n$ is large: nearest-neighbor search in high dimensions is hard.


Conceptual explanation of negative weights? What conceptually are negative weights on graphs? Why might they have them?

What is the significance of negative weight edges in a graph?

Above link answers your query.

One more example:-
If we want to design some architecture then in the whole circuitry there is flow of current. The whole circuitry can be modeled as graph with device components as vertices and the path between them as edges. In these paths the resistance can be taken as negative weights.


What does does $O$ mean in this context? I understand big O notation in computational complexity theory, but I don't see how it applies in the equation below.

From Pattern Recognition and Machine Learning:

  If we weren't familiar with the rules of ordinary calculus, we could
  evaluate a conventional derivative $dy/dx$ by making a small change
  to the variable $x$ and then expanding in powers of $\epsilon$, so that
  $y(x + \epsilon) = y(x) + \frac {dx}{dy}\epsilon + O(\epsilon^2)$

  and finally taking the limit $\lim\epsilon\to 0$.

It means exactly the same thing.  It means there is a constant $c$ such that the term is $\le c \cdot \epsilon^2$ (where $c$ does not depend on $\epsilon$).  Big-O notation is not unique to computer science; it is also widely used in mathematics.  See https://en.wikipedia.org/wiki/Big_O_notation, which explains some ways it is used in mathematics.


Is this a good approach for first attempt to create my own language and compiler? I want to try to create my own very simple programming language and it's compiler or interpreter.

The programming language I use is Java.

My idea was to create a compiler which will compile source code of my created language to some kind of intermediate code (nothing binary or complex, just plain text), and then have another program (a kind of virtual machine or interpreter) which will execute this intermediate code in Java.

For example, the 'programmer' types: write "hi world". The compiler turns it to some intermediate code like w-hi world. The VM/interpreter program reads this intermediate code and executes System.out.println("hi world");

My question is:

Is this approach common with programmers who want to try to create a simple language for the first time? Is this a good way to start?

I searched this site and came across questions on this subject, but the answers were more complex and technical than what I'm looking for.

That sounds like a fine way to start, and you'll become familiar with the issues involved.

How's it going?

At a certain point, consider learning more about programming language implementation techniques from

a book like Compilers: Principles, Techniques, and Tools (2nd Edition)
open courseware for MIT's Computer Language Engineering course
a MOOC like Udacity's Programming Languages: Building a Web Browser
Stanford's Programming Languages course

It's also worth investigating libraries to use such as parser generators, although some people swear by the recursive descent parsing approach as easier to build, also good at generating helpful error messages.

Another tip: It's easier to implement a programming language in a language like Clojure than Java. (Clojure is a modern Lisp dialect that's hosted on Java.) E.g. your intermediate representation could be a list of Clojure forms. They handle reading & writing as readable text, and you can construct & interpret (eval) them quicker and easier than text.


Give an example of a non-regular language $L$ such that $L^*$ is regular I can't think of an example of a non-regular language $L$ such that $L^*$ is regular. . Any help ?

Define $L=\{a^nb^n|n\in \mathbb N\}\cup \{a,b\}$

It's not hard to see that while $L$ is not regular, $L^*=\Sigma^*$.


Is Kolmogorov-random nonsensical for small numbers? The Wikipedia definition of Kolmogorov-random defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string.

Aren't nearly1 all strings shorter than a certain length2 going to be Kolmogorov-random?

If a random Turing machine is chosen, then programs that output short strings will almost always be longer than the strings. If the programming language used for measurement is optimized for outputting a short string, then only the complexity of a subset of short strings can be made lower than their length. For example, if a Turing complete language defines $0$ as an operation that outputs 0 and halts, the program for outputting 1 and halting is forced to be longer than the length of its output.
The exact length below which this occurs will depend on the programming language chosen. The length is 41 bits using 5 state, 2 symbol Turing machines.

Is Kolmogorov-random nonsensical for small numbers?

Although one could pick a specific description language to make Kolmogorov complexity into

a function from  {0,1}*  to  {0,1,2,3,...} ,  most people don't pick as described  ( 0 , 1 , 2 , 3 ) ,

so basically:

Kolmogorov complexity is only defined up to an additive O(1), so one

needs an infinite set of strings to make sense of Kolmogorov randomness.

In particular, yes, Kolmogorov-randomness is nonsensical for small numbers.


for two languages in $NP$ does one of them karp reducible to another? $\forall A, B \in NP \implies A<_m^{poly}B. \lor B<_m^{poly} A.$

I want to know is there any work around this theorem? or is it correct?

The theorem, as stated, is false: if $A=\emptyset$ and $B=\Sigma$, then we cannot reduce either of them to the other. If take either of $A,B$ to be non-trivial problems in $P$, the claim is true, which is not hard to show (see here). If either of $A,B$ is NP-complete, then the claim also holds by definition of NP-hardness.

So, the only case left is for problems $A,B\in NP-(NPC\cup P)$, the NP-intermediate problems. Note that such problems exist if and only if $P\neq NP$.

It would not be very surprising to me for two NP-intermediate problems to be incomparable, but this would be very hard to prove, as we currently do not have a good idea of what problems even could be NP-intermediate. So, it would seem that the full answer to your question is an open problem, but if I had to guess then I'd guess the answer is no.


How to edge-color a directed acyclic graph so that every path visits none or all edges of each color? Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never encountered along that path, or every edge that is colored $c$ is visited by that path.
Given $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors.  Is there an efficient algorithm for this problem?
I show below an example graph and a sample solution.  The circle on the left is the starting vertex, the filled circle on the right is the end vertex.

You can color a pair of arcs $(a_1,a_2)$ by the same color, if and only if all the paths from the source to the sink, passing through the arc $a_1$, also pass through the arc $a_2$.
Let's consider the set $P$ of all paths from the source to the sink in the graph $G=(V,A)$. Let's denote the subset $P(a) \subset P$ of all paths, passing through the arc $a$. Then we can define an equivalence relation on the set $A$:
$$(a_1 \sim a_2) \equiv (P(a_1) = P(a_2))$$
A minimum number of colors, needed to color all the arcs in the graph $G$ according to your restriction, will be equal to the number of equivalence classes for the relation above.
The algorithm to split all the arcs into such equivalence classes is exact, but may be slow for large graphs. It consists of two steps:
Step 1. For each arc $a \in A$ compute the subset $P(a) \subset P$. This can be done by scanning all the paths in the set $P$, and updating all the subsets $P(a)$ along each such path.
Step 2. Let's assume that we store all the subsets $P(a)$ as binary numbers. Sort the set $A$ by these numbers - this will allow us to group together all the arcs with the same subset of paths. Scan this sorted set of arcs, assigning the same color to arcs in each group.


Red-black tree amortized cost of the rebalancing I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions).
How can it be proven?

If you look at the rules for what happens in a red/black tree insertion, you can see that the fixup rules for maintaining the red/black invariants only propagate upward if the newly-inserted node becomes the child of a red node with a red sibling.

Let's call a "fissionable" group in the red/black tree a black node with two red children. If you do an insertion into a fissionable group, the fissionable group will be recolored and rotated in a way that ends up eliminating that fissionable group, but which propagates the insertion fixup to a higher level in the tree. If you set the potential function of a red/black tree to be the number of fissionable groups in the tree, then the true cost of doing an insertion is 1 + r, where r is the number of groups destroyed, and the number of new fissionable groups created is at most one (you should check this), so the amortized cost of a fixup is O(1) because the potential drop is r.

It's a lot easier to think about this by looking at the isometry between red/black trees and 2-3-4 trees. A fissionable group in a red/black tree corresponds to a 4-node in a 2-3-4 tree, and if you understand 2-3-4 tree insertions it's pretty easy to see why the amortized cost of an insertion into a red/black tree is O(1).


What does it mean for a function $f\colon M → N$ between *any* sets $M, N$ to be computable? In our lecture notes on lamdba calculus, I encountered the sentence:

  Let $M$ be a set and $f\colon ℕ → M$ be computable.

Does this even make sense? Don’t we need aditional structure on $ℕ$ and $M$ to talk about computability and decidability? How can I make sense of this statement?

One convention is as follows. Your sets $\mathbb{N}$ and $M$ come with (injective) encodings as strings. In that way, you can think of $\mathbb{N}$ and $M$ simply as subsets of $\Sigma^*$.

One can think of many other equivalent conventions. For example, you can treat the input as a bona fide natural number, and use the C programming language rather than the string-based Turing machine. All reasonable definitions will result in the same notion of computable function.

In terms of computational complexity, the exact encoding (or other convention) used can be important. For example, graphs can be encoded either using adjacency matrices or as adjacency lists, and this can affect the complexity of algorithms operation on them.


Is it enough to show the number of steps for certain values of $n$ in order to state an algorithm's complexity? If I can easily state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, the number of steps is $n\log n$, is this enough to allow me to state the complexity is amortized $O(n\log n)$?

I have a tree building algorithm - when adding elements a rebalancing operation occurs every so often, with those operations getting progressively more expensive as the tree size grows close to a power of two elements (before becoming cheaper again once we pass such a power). At every power of two elements its easy to state the number of steps done so far but in between it's not so easy.

I'm slightly embarrassed by this question as I currently assume it is OK to state an amortized time of $O(n\log n)$ for this situation but my conclusions, from reading a discussion elsewhere (see next part), seemed to contradict this.

Update: I've move the second part of part of this question, relating to Conc-tree lists and my confusion over how such trees could be built in $O(n)$, into a separate question.

You are asking several questions. I will only answer some of them.

Suppose that the running time of an algorithm as a function of $n$ satisfies $T(2^k) = O(2^k \log 2^k)$. Is it true that $T(n) = O(n \log n)$? Without any more information on the running time, this is patently false. For example, consider the function
$$
T(n) = \begin{cases} n\log n & \text{if $n$ is a power of $2$}, \\ n^2 & \text{otherwise}. \end{cases}
$$
However, in many cases we would expect $T$ to be monotone in $n$. In that case, the deduction does hold. Suppose that $T(n) \leq Cn\log n$ whenever $n$ is a power of $2$. Given arbitrary $n$, we can find $m \leq 2n$ which is a power of $2$, and then
$$
T(n) \leq T(m) \leq Cm\log m \leq 2Cn \log n + O(n) = O(n\log n).
$$

Suppose now that there is a data structure such that the first $n$ operations take time at most $Cn$ whenever $n$ is a power of $2$. If we let $T(n)$ denote the maximal time that $n$ operations take, then $T$ satisfies the conditions stated above (in particular, monotonicity is built-in), and so the amortized time per operation is indeed $O(1)$. Your case is a bit more complicated since different operations have different amortized running times, but the conclusion should be the same.


Armstrong's axioms more precisely 'inference rules': what's the distinction? "more precisely 'inference rules'" is what wikipedia says twice.

Other references I've looked at (the Alice book, Ullman lecture notes cited, Maier textbook) name them as Armstrong's Axioms, use them for inference. talk about axiomatisation and decidability, etc.

Wikipedia's links to axiom vs inference rule isn't helping me. "a rule of inference's action is purely syntactic, and does not need to preserve any semantic property:" Ok I can see that for (for example) modus ponens: it wants a premise like $p \supset q$ and a premise looking like $p$.

Hmm take the Armstrong Axiom of reflexivity

  If $X$ is a set of attributes and $Y$ is a subset of $X$, then $X$ holds $Y$.

    If $Y \subseteq X$ then $X \rightarrow Y$.

How to determine syntactically that $Y \subseteq X$?

So what is wikipedia trying to say? What distinguishes an axiom (which might be of the form $p \supset q$) vs an inference rule?

First, terminologically, "axiom" and "inference rule" are often used as roughly interchangeable as they tend to serve similar purposes. There are technical distinctions, which themselves can vary slightly, but outside the study of formal logic or related systems, these distinctions aren't that important.

In the context of formal logic, an axiom is a formula of the logic that is a theorem by definition. A rule of inference is a way of deducing new theorems from old theorems. Rules are always part of the logic, while axioms are separated into logical axioms, which are viewed as part of the logic, and non-logical axioms, which are viewed as part of the particular theory you are studying within the logic. Many logical axioms can be presented as rules and vice versa. For example, the axiom $P\supset(Q\supset P)$ roughly corresponds to the rule of weakening $\cfrac{\Gamma\vdash P}{\Gamma,Q\vdash P}$.

From a meta-logical perspective, rules of inference can be viewed as (definitional) axioms about the logic being studied (not to be confused with the "formal" axioms within the logic. Philosophically, "believing" in the conclusions of a logical theory requires "believing" the rules of inference just as much as "believing" the axioms.

So are Armstrong's "Axioms" axioms or rules of inference? It depends on how you formalize them. The "axioms" strongly suggest a deductive system, i.e. a system of rules, and that deductive system is quite useful in actually calculating functional dependencies. But, we could just as well take $\to$ and $\subseteq$ as relation symbols in a first-order theory and then the "axioms" really would be non-logical axioms of that theory. This could be viewed as meta-logical axioms about the deductive system, but it can just as reasonably be viewed as axiomatizing what "functional dependency" means without any deductive system in mind.

As for how to determine if $Y\subseteq X$ if we do indeed take a deductive system view of Armstrong's Axioms, in this context $X$ and $Y$ are meta-variables that stand for sets of attributes. They would be instantiated with expressions like $\{\mathsf{name},\mathsf{address}\}$. So for the rule you referenced, you'd simply be able to calculate that $\{\mathsf{name}\}\subseteq\{\mathsf{name},\mathsf{address}\}$ and $\{\mathsf{age}\}\not\subseteq\{\mathsf{name},\mathsf{address}\}$. An algorithm to calculate this could be formalized as a collection of inference rules itself, but there is no reason to do this. We can just assume that it can, in fact, be calculated. Obviously it can be in the intended use-case where the "sets" are explicitly presented, finite sets of elements with decidable equality.

Even for modus ponens, we have $P$ and $Q\supset R$ and we can apply modus ponens if $P=Q$, but checking the (syntactic) equality of two formulas while not hard is not completely trivial. Indeed, weakening is often presented with a rule like $\cfrac{\Gamma\vdash P\qquad \Gamma\subseteq\Delta}{\Delta\vdash P}$ and it is just understood that you can, in fact, calculate whether one set of formulas is a subset of another. It may also be presented as $\cfrac{\Gamma\vdash P}{\Gamma\cup\Delta\vdash P}$ where, again, it is just assumed that you have some way of calculating $\Gamma\cup\Delta$.


GSAT incompleteness example The GSAT (Greedy Satisfiability) algorithm can be used to find a solution to a search problem encoded in CNF. I'm aware that since GSAT is greedy, it is incomplete (which means there would be cases where a solution might exist, but GSAT cannot find it). From the following link, I learned that this can happen when flipping variables greedily traps us in a cycle such as I → I' → I'' → I.

http://www.dis.uniroma1.it/~liberato/ar/incomplete/incomplete.html

I've been trying quite hard to come up with an actual instance that can show this, but have not been able to (and could not find examples elsewhere). Any help would be much appreciated. Thanks :)

P.S. I'm not talking about "hard" k-SAT problems in which the ratio of variables to clauses approaches 4.3. I'm just looking for a simple example, possibly involving the least number of variables and/or clauses required.

The original paper contains such an example (on page 5):
$$
\begin{gather*}
(1 \lor \lnot 2 \lor 3) \land (1 \lor \lnot 3 \lor 4) \land (1 \lor \lnot 4 \lor \lnot 2) \land (1 \lor 5 \lor 2) \land (1 \lor \lnot 5 \lor 2) \land \\
(\lnot 1 \lor \lnot 6 \lor 7) \land (\lnot 1 \lor \lnot 7 \lor 6) \land \dots \land (\lnot 1 \lor \lnot 98 \lor 99) \land (\lnot 1 \lor \lnot 99 \lor 6)
\end{gather*}
$$
The first five clauses force $1$ to hold. Indeed, suppose that $\lnot 1$. Clauses 4 and 5 force $2$, and so clauses 1 and 3 force $3 \land \lnot 4$, contradicting 2. The entire formula is satisfiable, for example by the all-true assignment.

If the starting assignment is not satisfiable or very close to satisfiable, then the authors claim that the large number of clauses of the form $(\lnot 1 \lor \cdot \lor \cdot)$ will ensure that $1$ remains false throughout the algorithm. See if you can substantiate this claim.


Finding non-trivial NFA that accepts all short strings It is well-known that every non-trivial NFA of $k$ states (an NFA that does not accept all strings) rejects a string of length at most $2^k$.

But is this upper bound asymptotically tight ?

I found a rough sub-exponential bound in this strategy.

Let $p_i$ be an $i$-th prime.

On the singleton alphabet, $\Sigma = \{a\}$, the following NFA rejects only

$\{a^n:n>0, p_1\cdots p_k|n\}$. With $p_1+p_2+\cdots+p_k+O(1) = \Theta(k^2\log k)$ states.

Initial state $q$, is an acceptance state and it is branched into $k$ cycles with $\epsilon$ marks.

Every $i$-th cycle has $p_i$ states, and only rejecting state is the state directly linked into initial state $q$. All of its transition are marked by $a$.

It is clear that the complement of accepting language is $\{a^n:n>0, p_1\cdots p_k|n\}$ as given.

But $p_1\cdots p_k=O(e^{\Theta(k\log k)})$. which is sub-exponential with respect to $\Theta(k^2\log k)$.

In this unary and multiplication strategy it seems to be this is optimal because $\text{lcm}\{p_1,p_2,\cdots,p_n\}$ is probably maximized with constraint $p_1+\cdots+p_n=C$ under this prime summation partition.

It seems we should use multi-ary language to improve this bound. Is there any suggestion or results in research?

Your question is very similar to a similar question about regular expressions. My answer there (citing a paper of Jeff Shallit and his students) gives an example in which the minimal word not accepted has length exponential in the number of states (using the fact that a regular expression of length $\ell$ can be converted an NFA of length $O(\ell)$). Moreover, the NFAs are over a fixed alphabet.


Increase-key and decrease-key in a binary min-heap In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally listed for min-heap? I imagine it is possible to do that in O(height) by iteratively swapping the increased element (x) with the minimum of its children, until none of its children is bigger than x.

e.g.

IncreaseKey(int pos, int newValue)
{
   heap[pos] = newValue;
   while(left(pos) < heap.Length)
   {
      int smallest = left(pos);
      if(heap[right(pos)] < heap[left(pos)])
         smallest = right(pos);
      if(heap[pos] < heap[smallest])
      {
         swap(smallest, pos);
         pos= smallest;
      }
      else return;
   }
}

Is the above correct? If not, why? If yes, why isn't increase key listed for min-heap?

The reason that your operation is not listed, is that one is not simply interested in all operations that can be easily implemented using a certain data structure, but rather the other way. Given a set of operations, what is the most efficient way (in terms of space and time) to implement these operations. (But I add more to this later)

Binary heaps implement the abstract data structure priority queue, which asks for operations is_empty, add_element (a key with its priority), find_min, and delete_min. More advanced queues also allow one to decrease the priority of the key (in a min_heap) or even increase it. In fact, you have given an implementation.

Two remarks. Your operation is used in the heapify function, that efficiently constructs a heap from an array. In heapify your operation is repeated (starting from the last key).

Then, most importantly, your code uses the position of the node. For the pure data structure priority queue that is cheating. That data structure asks to perform a certain operation given a key. So in order to decrease or increase the priority of an element, you will first have to locate it. I think that is the main reason it is not listed.


Mathematically determine if two strings are permutations of each other I've come across many coding exercises that require me to determine whether or not two strings are permutations of each other and I've repeatedly wondered if it would be possible to convert each string to char codes and perform mathematical operations on them to determine equivalence.

My idea was to sum up the char values of each and compare. Then multiply the values of each string and compare. If both the sum and product are the same for both strings then the strings are permutations of each other.

Note: this is assuming strings of equal length. instantly reject strings of different length.

example:
A = "abcd" = [1, 2, 3, 4] -> Sum: 10 -- Product: 24
B = "bcda" = [2, 3, 4, 1] -> Sum: 10 -- Product: 24

Sum A = Sum B and Product A = Product B therefore A is a permutation of B

Is there a case where this would not hold true? how would one go about proving this. I want it to be true because it would be more space efficient than https://stackoverflow.com/a/2145221/2001647 which also runs in O(n)

Your algorith isn't correct.

Take $abbc = [1, 2, 2, 3]$ and $acd = [1, 3, 4]$. Their product is $12$ and their sum $8$, yet they aren't permutations of each other; they don't even have the same length.


Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time I am looking for a solution for the following problem:

Find the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time.

Consider the following sequence:
$$
3, 1, 6, 1, 5
$$
The answer here is $3$, with $6, 5, 3$ being in the set found. The value of $N$ is not a given - we're looking for the largest $N$.
So far, I came up with three solutions:

Sort the sequence and go from the top.
Use a modified version of quickselect.
Use a modified version of BST where elements bigger than the current $n$ are inserted, and elements smaller than the new $N$ are removed.

1 and 3 are more or less $n\log n$ (though I'd expect 3 to be faster), 2 is best case $n$, worst case $n^2$.
Our teacher told us it's possible to do it in a reliable $n$ time. What is the algorithm for the linear solution, if there's one?

Let $n$ denote the length of the array. We will find the largest $N$ such that there are at least $N$ elements whose value is at least $N$.
Make a pass through the array, counting the number of elements of value $1,2,\ldots,n$; if any element has value larger than $n$, count it as $n$.
Using this, determine, for each value $m \in \{1,2,\ldots,n\}$, the number of elements whose value is at least $m$.
Now you can easily determine the solution.


prove decidability and recognizability I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is same as $L_1$.

I thought so far that I can describe $L_2$ with a Turing machine. So I can next find the intersection Turing machine of both.

I do not know what to do about the last part of the problem.  Maybe I can say that $L_2$ is decidable (because it is regular) and $L_1 \cap L_2$ is a subset of that. So it is also decidable.

I am not sure whether my approach is correct  or not. Please help me.

The method you propose in your answer is mostly correct. $L_2$ is, indeed, decidable because it's regular. But you can't argue that $L_1\cap L_2$ is decidale because it is a subset of the decidable language $L_2$: every language is a subset of the decidable language $\Sigma^*$ but that doesn't mean that every langauge is decidable.

Hint. You chose the tag closure-properties, which shows you're on the right lines. $L_1$ is either decidable or recognizable; $L_2$ is both. What do you know about the intersection of two decidable/recognizable languages?


Minimize Manhattan distance travel algorithm I am trying to find the name of an algorithm for a game I am making. I am pretty sure it exists, but I have no idea what name it has.

Say I have a matrix like:

$$
\begin{array}{|r|r|r|} \hline
    \hphantom{-}1 &  -1 &  0 \\\hline
    0 &  0 &  1 \\\hline
    0 &  1 & -2 \\\hline
\end{array}
$$

I know that the sum of each element of the matrix is zero.

And an operation $f$ which sums two elements of the matrix together and replaces both of them with this sum. In our example  $f( a_{1,1} a_{1,2} )$ (where $a_{r,c}$ is the element of the matrix at row $r$ and column $c$) would lead to

$$
\begin{array}{|r|r|r|} \hline
    \hphantom{-}0 &  \hphantom{-}0 &  0 \\\hline
    0 &  0 &  1 \\\hline
    0 &  1 & -2 \\\hline
\end{array}
$$

The cost of this operation is the Manhattan distance between the two points, in this case $1$.

Now, I want to find the moves that:

make each element of the matrix go to $0$
minimize the total cost

Is there an algorithm (or a combination of them) that does that? Sorry for the laymen lingo, I am not a programmer myself!

You could always try the A* algorithm.  It might not be optimal but it is something you could try, and depending on how big the matrix is it might be good enough.  You'll need to design an appropriate heuristic (e.g., maybe the number of elements that are non-zero, divided by two?).


Possible to develop a game using assembly language? I am wondering what it takes to develop a game in assembly language. For example, what are the limitations or advantages from using assembly language in game development? Also, are there any programs/softwares to aid the development of games in assembly language?

Yes, most definitely!

Would you want to these days? No, probably not, unless you were doing it for educational purposes.

The first games on computers were coded in Assembly language, because when computers first came out there wasn't anything else to program in. The most recent example of a popular game that I know of which was written in Assembly is RollerCoaster Tycoon: http://en.wikipedia.org/wiki/RollerCoaster_Tycoon

The are a lot of limitations of writing a game in Assembler code.For example, in assembler you are writing individual instructions to the CPU. This takes a lot of thought and a lot of time. Chances are you won't be doing it as efficiently as you could be too! A modern programming language, like C++ for example, would be far easier to code a game in these days. It allows you to think about how you want to program things in at more complex level without having to think about the very basics of how it will actually run on your computer.

Plus, different computers will have their own versions of Assembler code, so writing your game on one computer may mean it won't run on a whole other line of computers! But when you write a game in something like C++, there's a special program you run that will turn it into assembler code, specifically for what ever machine type you run it on!

To sum this up, I'd say there really is no point writing a game in assembler, unless you are doing it to learn assembler. You will get much faster and better results when making a game if you do it in a higher level language. If you want to get up and running quickly I'd say you should go for something like Java, specifically using a special IDE & library called 'Processing', take a look at it and see how easy it is to get up and going, pretty good if this is your first time programming something and want to get a hang of it:

http://www.processing.org/


Provide some help regarding the "Dining Philosophers Problem"? I have an assignment based on operating systems and the question is divided into two sub-questions.

The first is: Prove any seating arrangement of lefties and righties, with at least one of each avoiding deadlock.

The second: Prove any seating arrangement of lefties and righties with at least one of each avoiding starvation.

I understand the concept behind this problem and that I can use semaphores, or monitors etc. but the resources I have found online mainly explain in coding, but I need help understanding which is the best way to answer this question in theory by choosing one of the ways to prevent deadlock and starvation.

Righties: will never try to acquire the left fork before they have the right one.

Lefties: will never try to acquire the right fork before they have the left one.

Deadlock: Assume that you reached deadlock, this means that none of the philosophers can eat (so each philosopher holds at most one fork, and cannot pick up the other one). Sine you have both righties and lefties, there exists two adjacent philosophers with opposite orientation, lets denote them by $p_r,p_l$.
Notice that $p_r,p_l$ cannot pick up any forks, if one of them holds the fork in between, $f_{p_r,p_l}$ , then it means he already got the other fork, since $f_{p_r,p_l}$ lies right to the leftie $p_l$ and left to the rightie $p_r$. So $f_{p_r,p_l}$ is available, and thus if $p_r$ or $p_l$ can pick up the other fork, they can pick up $f_{p_r,p_l}$ and eat, contradicting deadlock. $p_l$ cannot pick up the fork to his left, hence (because the system is in deadlock) the philosopher left to $p_l$ is a rightie, and already picked up the fork to his right (or to $p_l$'s left). Let us denote the $k'th$ neighbor to $p_l$ from the left by $p_l^k$, so we have shown $p_l^1$ is a rightie and owns the fork to his right. $p_l^2$ (left neighbor of $p_l^1$) must also be a rightie and own his right fork, otherwise either he or $p_l^1$ can eat. It is easy to see (by induction) that for all $k$, $p_l^k$ is a rightie owning his right hand fork. however $p_r=p_l^{n-1}$ (where $n$ is the number of philosophers), so $p_r$ is a rightie owning his right fork, contradicting the fact that $p_r,p_l$ do not own any forks.

This is illustrated in the following figure. Red squares are forks, arrow from a philosopher to a fork indicates that he is waiting to use this fork (not ownership). All philosophers left of $p_l$ are righties waiting to use their left fork (already owning their right one). This goes on until you reach $p_r$, who you know is waiting for his right fork and not the left one (which leads to contradiction).

Starvation: Starvation means that there exists a philosopher which is stuck waiting to eat. Suppose that some right hand philosopher $p_r$ is stuck waiting to pick up his right fork (the proof is very similar in case he's waiting for his left). Let us denote by $p_r^k$ the k'th neighbor of $p_r$ to the right. We know that the protocol is deadlock free, so there exists minimal $m$ such that $p_r^m$ is eating. We can see by induction that all $p_r^{j}$  for $j<m$ are lefties holding their left fork. This is clear for $p_r^1$ (otherwise $p_r^1$ would be either eating or leaving the fork right of $p_r$ available, in any case $p_r$ will eventually be able to pick up the fork to his right). Suppose $j,j+1<m$ and $p_r^j$ is a leftie holding his left fork. Since both $p_r^j,p_r^{j+1}$ are not eating (by minimality of $m$), $p_r^{j+1}$ is a leftie holding his left fork. When $p_r^m$ is done eating, $p_r^{m-1}$ will be able to pick his right fork and eat, when he's done $p_r^{m-2}$ will be able to pick his right fork and eat,... Finally, $p_r^1$ will be done eating, allowing $p_r$ to pick his right fork, contradicting the fact that he is stuck.


How is data written to RAM From my understanding(correct me if I am wrong) when I read data from RAM memory it is copied into processor cache and than it is copied into register to be used by the processor. When I create data (like variable) is it first created in register and than copied to cache and from cache to RAM or is it directly created in RAM?

Additional question:Does stack and heap exist only in RAM or do they exist in processor cache as well?

When you read data from a given memory address, the memory manager checks if there is a copy in the cache. If yes (cache hit), the copy is read into the register. If no (cache miss), the cache is first updated with a row of memory from RAM; then the data can be read into the register.

Conversely, when you write to a memory address, the data is just written to the cache, making room if required. Later, when the cache line must be freed or is explicitly flushed, the row of memory is copied to RAM.

If you perform successive reads and writes to the same address, it can very well arise that all changes are made in the cache and the RAM left untouched. From the processor's point of view, the presence of the cache is transparent. It just reads from and writes to memory addresses, and the memory manager optimizes the transfers.

Note that you don't "create" data in memory. When a program is loaded, some RAM space is assigned to it and reserved (possibly also initialized), and the addresses of the variables are "mapped" onto that space. Then the program is allowed to write to or read from these addresses.

In modern, multicore CPUs, cache management is much more complicated because several concurrent reads/writes to the same memory addresses can occur. The MMU must ensure that all caches and RAM remain coherent and "synchronize" their content.

The stack and the heap have a range of memory addresses allocated, and they are handled through the cache like ordinary program space. The stack is an essential resource during program execution and it is extremely frequently accessed. It is important that it be cached as well.


Finding pair of non-adjacent cliques in a dense graph I have a graph consisting of about 5000 vertices, with density around 0.5. I'm trying to find two disjoint 6-cliques, which are not connected by an edge. I have tried bruteforcing this, by firstly looking for any 6-cliques, and then checking pairs for being non-adjacent. However, although it finds a lot of 6-cliques it is too slow to find a non-adjacent pair. Is there a faster way to do this?

Here is one approach:

Find any 6-clique, call it $C$.
Find all vertices that aren't adjacent to any vertex in $C$.  Mark them red.
Find a 6-clique among the red vertices.

How long will this take?  Let's analyze the running time of each step.

You should be able to find a 6-clique by randomly sampling $2^{15}$ possible ways to choose 6 vertices and checking whether it forms a clique; a random collection of 6 vertices has a $1/2^{{6 \choose 2}} = 1/2^{15}$ probability of being a clique, so you're likely to find one in this way after about $2^{15}$ trials.  There are faster ways to find a 6-clique, but this will already be very fast.
This can be done in $6 \times 5000$ operations, i.e., very fast.
Now you have the problem of finding a 6-clique in a smaller graph.  How many red vertices do you expect to have?  If you pick a vertex at random, then it has a $1/2^6$ probability of being red.  Therefore, we expect about $(5000-6)/2^6 \approx 78$ red vertices.  It is very likely that a 6-clique exists among them, as there are ${78 \choose 6} \approx 2^{28}$ possible ways to choose a subset of 6 nodes, and each one has about a $1/2^{15}$ chance of being a 6-clique.  You can find a 6-clique among the red vertices in the same way as before (randomly choosing a collection of 6 red vertices and checking to see if they form a clique).  This takes about $2^{15}$ trials.

So all in all you expect this to be successful, and to take about $2^{16}$ trials, where each trial is very fast.  So this algorithm should be very fast.  There are probably ways to optimize it further, by using standard algorithms for finding a clique more efficiently than brute force, but I'd guess this should already be adequate, and it has the advantage of being easy to implement.


How similar are two DFAs? -not just binary equivalence- Are there any measures to compute similarity (or distance) between two DFAs?

If yes, which are the main references?

I need a measure of similarity, not only a (binary) equivalence test.

"Similarity" is an intuitive concept. There are different ways to formalize it; i'm looking for ready-to-use formalizations with regard to DFAs (not NFAs, weighted automata, or general graphs!).
Furthermore, good solutions may exploit recognized languages.

I found some studies about this problem, which help to clarify the question. They involve two approaches: one from model-testing field aiming at compare languages, a second defined by authors aiming at compare structure of DFAs.

Bogdanov, Kirill, and Neil Walkinshaw. "Computing the structural difference between state-based models." Reverse Engineering, 2009. WCRE'09. 16th Working Conference on. IEEE, 2009.
Walkinshaw, Neil, Kirill Bogdanov, and Ken Johnson. "Evaluation and comparison of inferred regular grammars." Grammatical Inference: Algorithms and Applications. Springer Berlin Heidelberg, 2008. 252-265.
Walkinshaw, Neil, and Kirill Bogdanov. "Automated comparison of state-based software models in terms of their language and structure." ACM Transactions on Software Engineering and Methodology (TOSEM) 22.2 (2013): 13.

They compute exactly what I was looking for, a metrics among DFAs, adopting the techniques developed in the model-testing field.

Does there exist any other approaches, ready-to-use, to compute similarity between DFAs?
(Both in terms of language both of structure).

This problem seems to ask for co-development of a reasonable distance function and an algorithm to compute it for a given pair of languages.

The paper "The Cost of Traveling between Languages" by Michael Benedikt, Gabriele Puppis, and Cristian Riveros defines one such notion, where we are searching for the largest value $d$ such that there exists a word $w$ in the language of the first automaton such that the edit distance of $w$ to any word in the second language is at least $|w| \cdot d$. The paper gives an algorithm to solve this problem, which involves distance automata.

The paper also has an interesting related work section, with a reference to the paper "Edit-distance of weighted automata: general definitions and algorithms" by Mohri, which seems to solve the same problem without the multiplication with the word length.

Both of these definitions are reasonable from a theoretical point of view - you now only have to evaluate whether they make sense for your particular application.

Both of the paper have author-archived versions available without pay-wall on the web which you should easily find with your favorite search engine.


proof non-empty AVL tree The vertex of a binary tree is called an single child if it has a father's vertex but does not have a neighbor.
The root is not considered an single child.
let mark in  numOnly  a number of vertices in T that hold the attribute "single son ", and ‘with n we mark the total number of vertices in the T tree.
i need to prove that every non-empty AVL tree has inequality  $\frac{numOnly}{n}\leq \frac{1}{2}$

If the tree hasn't any single-children the hypothesis trivially holds.
Given a single-child vertex $v$, we can show that the parent of this vertex $v$ cannot be a single-child.
Let $p(v)$ be the parent of $v$.
If $p(v)$ is the root then $p(v)$ isn't a single-child per definition.
If $p(v)$ is not the root: Assume that $p(v)$ is a single-child then $p(p(v))$ has only one child. This implies that the difference in height of the subtrees of $p(p(v))$ must be at least $2$ which conflicts with the AVL-criterium and therefore implies that $p(v)$ is not a single-child.
Using this and the fact that for every single-child there is a unique parent, we can conclude that $2\cdot numOnly \leq n$.


Decidable languages and unrestricted grammars? Turing machines and unrestricted grammars are two different formalisms that define the RE languages.  Some RE languages are decidable, but not all are.

We can define the decidable languages with Turing machines by saying that a language is decidable iff there is a TM for the language that halts and accepts all strings in the language and halts and rejects all strings not in the language.  My question is this: is there an analogous definition of decidable languages based on unrestricted grammars rather than Turing machines?

A language is decidable, iff it is semi-decidable and its complement is semi-decidable. Moreover, a language is recursive-enumerable iff it is semi-decidable and thus you can find an unrestricted Grammar. Therfore:

A language $L$ is decidable iff there is both an unrestricted Grammar $G$ with $L(G) = L$ and an unrestricted Grammar $\bar G$ with $L(\bar G) = \bar L$.


Worked out example of Slepian-Wolf Theorem Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic.

The Slepian-Wolf theorem states that sequences of outputs from two separate random variable sources A and B that have a joint probability distribution defined on them, if encoded with the following rates, can be completely retrieved when decoded together:

$$
R_A \geq H(A|B) \\
R_B \geq H(B|A) \\
R_A + R_B \geq H(A,B)
$$

$R_x$ refers to the bits required for encoding one symbol of $X$, assuming all logarithms are taken to the base 2.

Given this, I wanted to try out an example, especially because I find fractional number of bits per symbol slightly confusing to think about.

Consider two sources $A$ and $B$, that either sprout out 0 or 1 following this probability distribution:

A \ B   0    1
  0    0.5   0
  1    0.25 0.25

We calculate the entropies as follows:
$$
H(A,B) = 3/2  = 15/10\\
H(A|B) = 7/10 \\
H(B|A) = 1/2 = 5/10\\
$$

Now, assume that the a certain sequence of bits that A and B give out are as follows:

 A  B
 0  0
 0  0
 1  0
 1  1
 1  0
 0  0
 0  0
 1  1
 1  0
 0  0

I should be able to find an encoding that allows A to send atleast 7 bits, B atleast 5 and a total of atleast 15, such that they can be decoded completely, right?

Unfortunately I am unable to think of an encoding where they send less than 10 bits each.

For example, B does not have to send anything when A sends 0, however B does not know when A sends 0.

I would also like to know if this is the wrong way to interpret the theorem (perhaps a longer sequence is required), or if there is another way to see its working.

Here's a simpler example. Consider the binary erasure channel which erases its input with probability $1/2$. The channel capacity is $1/2$, so you should be able to send one bit of information by sending two bits on the channel. Or should you?

Shannon's theorem only guarantees that for every $\epsilon > 0$, you can send $(1/2-\epsilon) N$ bits of information by sending $N$ bits across the channel, with failure probability approaching zero as $N\to\infty$. There are two features of this theorem (shared by Slepian–Wolf) that you didn't take into account:

The theorem talks about asymptotic rates.
The theorem allows for some small failure probability.

The article you link to assumes you are already aware of all this. Since you appear not to be, I suggest reading a textbook on information theory, where all the relevant concepts are defined and explained.


Regular set corresponding to regular language I have  just started learning regular expressions and I don't have anybody around me to help me building conceptions. So I rely on online mediums. My question is whether every regular set corresponds a language.
I had a regular expression $(0+10^*)$ and I was trying to find the regular sets. My books suggests that $L=\{0, 1, 10, 100, 1000, 10000,\ldots\}$. But I was thinking why they did not consider the strings starting with $0$ and then only one $1$ and zero or more number of occurrences of $0$, like $010, 0100, 01000$ etc.

Aren't these strings belong to $L$?
Is this $L$ a language? (According to me, it is a language because it is the set of strings over $\{0,1\}$.

A regular language $L$, is a set over the alphabet $\Sigma$ (that is, $L\subseteq \Sigma^*$) that has a regular expression that generates it. Therefore, by definition - any language of a regular expression is a regular language.
Regarding the language in question, $01$ for example is not generated by $(0+10^*)$, since it is not $0$ and also is not generated by $10^*$ (since it doesn't start with $1$). The same goes for any string starting with $0$, and has more than one letter in it.


Making a NFA for accepting a string only if it contains the given substrings First I'll introduce the problem with just two substrings. Say you are asked to construct a NFA which accepts the input string if it has both "bb" and "aba" as substrings.

The solution we came up with in class was that we'll make a NFA with multiple start states (a start state with $\epsilon$-transitions to each of our desired multiple start states). We'll have two cases, one where the substring "aa" occurs before the substring "aba" and one where the substring "aba" occurs before the substring "aa".

Following is the NFA diagram:

But the problem with that solution is that it doesn't generalize well (for example, now if I have to check that the given string contains 10 given strings as substrings, if I have to make a branch for every permutation, I'll have 10! branches).

Is there a simpler solution to this where the complexity of the NFA to be drawn does not increase as factorial of the number of substrings?

Given an alphabet $\Sigma = \{\sigma_1,\ldots,\sigma_n\}$, let us consider the problem of matching all strings which contain all of the letters as substrings, i.e. all the strings $\sigma_1,\ldots,\sigma_n$ as substrings. An NFA with $N$ states accepting this language can be converted to a context-free grammar in Chomsky normal form of size $O(nN)$ (this is the total size of all rules). It is known that any context-free grammar in Chomsky normal form for this language must have exponential size $\tilde{\Omega}((3/2^{2/3})^n)$ (see Theorem 9 here; we gain a quadratic factor since our grammar is in CNF), and so $N = \tilde{\Omega}((3/2^{2/3})^n)$.

Note that this is only an exponential lower bound, whereas the obvious construction has factorial complexity. However, you can improve on this construction. Given $n$ words, the idea is to guess which $n/2$ words will appear first and which $n/2$ words will appear last, and to recurse on each half. We obtain the recurrence
$$ T(n) = \binom{n}{n/2}\cdot 2T(n/2) \leq 2^n T(n/2). $$
Expanding the recurrence and using a trivial base case $T(1) = 1$, we get
$$
T(n) \leq 2^{n+n/2+\cdots} < 4^n,
$$
which is only exponential. In actuality, $T(1)$ is the size of the largest word to be matched, so the bound above should be multiplied by that.


OOP: exampe and references on constructor anomalies I have read the following artice that defines the term "constructor anomaly":

Cohen, Tal, and Joseph Gil. "Better Construction with Factories." journal of object technology 6.6 (2007): 103-123.
http://www.jot.fm/issues/issue_2007_07/article3/

Where can I find examples and references on constructor anomalies? (also in the context of multiplie inheritance)

Are constructor anomalies always due to a method call in the constructor or is it possiple to construct an example without method calls in the constructor?

"Constructor anomaly" is not a bug or anything; it is simply an anomaly on the classification of constructor functions. ie. constructor functions are different from member functions in the following ways.

Anomalous classifications:

While most member functions require an instance and work on an instance, a constructor does not require an instance, but still works on an instance:

  f.bar(); // instance of f, can call bar(). bar() does stuff to/with f.

  new F(); // no instance, yet called F::F(). Yet F::F() does works on an instance.

Most member functions can replace or extend their base-class functions with the same name; that is, a member function can entirely override a base-function (replacement), ...   or ... it can override, and call the base function as well (extension). However, the constructor (in these languages) must extend, that is, call the base-class constructor first. (This is to delegate the base-class's construction to the base-class, first, and then construct the derived class):

struct F{
    F(){/*stuff*/}
    virtual void bar(){/*stuff*/}
    virtual void baz(){/*stuff*/}
};
struct G : public F{
    virtual void bar()
    {
      //Do stuff
      F::bar(); // extend F::bar()
      //Do more stuff
    }
    virtual void baz()
    {
      //Do stuff
      //Do more stuff
      //No call to F::baz(), replaced it
    }
    G::G(){
      //this MUST extend F::F(); in C++ F() is called implicitly in this case.
      //However, if F() takes parameters, it must be called explicitly
    }
};

Most member functions can be dynamically bounded; that is, you never know if a (virtual) function F* f; f->bar() is calling F::bar() or if f is a type that derived from F; and thus a different bar is being called. However, constructors are always static, you must know exactly which class you are creating when you create it:

H* h = get_h();
h->bar(); // this function can be H::bar(), or anything defined in the virtual table; hence it is dynamic; h can be any derivative of H, overriding H::bar().

F* f = new F(); // the call to F::F() MUST be (statically) linked to F(), not a derivative of F


A Turing Machine that exclusively accepts an infinite string While reading some of proofs in Computability Theory, I came up with following conclusion:

We can design a Turing Machine which exclusively accepts finite strings (obvious).

Now while trying the same for infinite string, I came up with the following conclusion :

There exist no Turing Machine which exclusively accepts infinite strings.

Proof : Since acceptance in context to Turing Machine is defined in terms of finite amount of time, therefore every time we say that an infinite string $w$ is accepted by a Turing Machine, we usually talk about searching a "finite pattern" in $w$. So while designing a machine for $w$ there exist a $w'$ which is finite and contains the same "finite pattern" which we try to find in $w$.

Example of "finite pattern" : A string that contains a 0. (Assuming Binary Strings)

So my question is that is my proof right? and if yes, is there a better way to prove this?

In contrast to the commenters, it is perfectly possible to define a Turing machine formalism whose input can be infinite. Let $\Sigma$ be an alphabet, and let $\#$ be a symbol not in $\Sigma$. We say that a Turing machine $T$ accepts a finite word $w \in \Sigma^*$ if it halts in an accepting state when the tape is initialized by $w \#^\omega$ (i.e., $w$ followed by infinitely many copies of $\#$; I assume for simplicity that the tape is only one-way infinite). Similarly, $T$ accepts an infinite word $w \in \Sigma^\omega$ if it halts in an accepting state when the tape is initialized by $w$.

We say that a language $L \subseteq \Sigma^* \cup \Sigma^\omega$ is $\omega$-computable (non-standard terminology) if there exists a Turing machine which halts on all inputs, and accepts exactly the strings in $L$. We say that $L$ is $\omega$-r.e. if there exists a Turing machine that accepts the strings in $L$, and never halts on strings not in $L$.

Under this definition, the language $\Sigma^*$ consisting of all finite words is not $\omega$-computable (as we show below), but is $\omega$-r.e. (exercise). It then follows that $\Sigma^\omega$ is not $\omega$-r.e., and in particular not $\omega$-computable (though we can show the latter directly).

Suppose that $T$ is a machine which halts on all inputs and accepts $\Sigma^*$. In particular, it halts on $\sigma^\omega$, where $\sigma \in \Sigma$ is arbitrary. Suppose that it halts after $N$ steps, at the rejecting state $s$. Then $T$ also halts on $\sigma^N$ (exercise), at the same state $s$, thus rejecting the finite word $\sigma^N$.

The same proof also shows directly that no Turing machine accepts $\sigma^\omega$.


Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T.

This question is a simplification of this dynamic programming question:

  It’s Tushar’s birthday today and he has N friends. Friends are
  numbered [0, 1, 2, …., N-1] and i-th friend have a positive strength
  S(i). Today being his birthday, his friends have planned to give him
  birthday bombs (kicks :P). Tushar’s friends know Tushar’s pain bearing
  limit and would hit accordingly. If Tushar’s resistance is denoted by
  R (>=0) then find the lexicographically smallest order of friends to
  kick Tushar so that the cumulative kick strength (sum of the strengths
  of friends who kicks) doesn’t exceed his resistance capacity and total
  no. of kicks hit are maximum. Also note that each friend can kick
  unlimited number of times (If a friend hits x times, his strength will
  be counted x times)

  Example:

  R = 11, S = [6,8,5,4,7] Ans = [0,2]

Clearly, the maximum number of kicks = R/ min_element(S) = 11/4 = 2

So the question reduces to find the lexicographic smallest order of 2 elements in the Array such that the total of N elements is less than or equal to 11.

I am having a tough time thinking about a solution for this. Any leads/ ideas would be appreciated!

You are on the right track.

It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding and short of performance.)

Let us use the notation in the original question. $R$ is for the resistance capacity. $S$ is for the array of strengths.

Let the index of the first minimum strength be $m$. Then the maximum number of kicks is $n = R/S[m]$. So $O=[m, m, \cdots, m]$, where the number of $m$'s is $n$, is a kick order with maximum number of kicks, with total strength $n*S[m]$.

How can we get a lexicographically smaller order with the same number of kicks? If we can find an index $i$ smaller than $m$ such that we can replace a kick of strength $S[m]$ by a kick of strength $S[i]$ without overpassing the resistance capacity $R$, then we can replace the first element in $O$ by $i$, making the order lexicographically smaller. To make it as lexicographically as small as possible, we would like the index $i$ as small as possible and, then, we would like to use it as many times as possible.

For example, $R = 11, S = [6, 8, 5, 4, 7, 4]$. Then the first minimum strength is the first 4 whose index is 3. So $n=11/4=2$ and $O=[3,3]$ with total strength $4*2=8$. To make it smaller, we will check the strengths before 4 in order. The first one is $6$. Since $8-4+6=10<11$, we find a smaller order $[0,3]$. If we apply 6 again, we would get $10-4+6=12 > 11$. So we go ahead to check the next strength 8, which is too large. So we go ahead to check 5. Since $10-4+5=11\le 11$, we find a smaller order $[0,2]$. Since the room left for replacement, $11-11 =0$, we stop our effort. The final answer is [0,2].

I have verified that my program wrote along the above approach works. Hopefully, I have written enough to encourage you to go ahead. Hopefully, I have not written too much to spoil the fun for you.

This problem is a variation of the unbounded knapsack problem.


Show that a circuit of size $s$ can be converted to a DeMorgan circuit computing the same function of size at most $2s$ I am trying to prove the above statement. A DeMorgan circuit is a circuit that has only $\{ \wedge, \vee, \neg \}$ gates and the negation is applied only to input variables.
So, assuming we have a circuit of size $s$ that computes a function $f: \{0,1\}^n \rightarrow \{0,1\}$. The basis for this circuit is $\{\wedge, \vee, \neg\}$ with fan-in 2 for the OR and AND gates. I am trying to prove we can convert this circuit to a DeMorgan circuit of size at most $2s$.
Intuitively and in small examples this claim makes sense to me but I would like to prove that more formally. I have searched in several papers but this claim is mostly mentioned but not proved. Can someone give me an intuition about the proof?
The above statement was mentioned in the following paper https://eccc.weizmann.ac.il/report/2018/154/ in the second paragraph of the 1st page and continuing on 2nd page.

The idea is to "move backwards" all the not gate. Assume you have some circuit, for example $(\cdot,\cdot)\rightarrow AND\rightarrow NOT\rightarrow OUTPUT$
Can be converted to:
$(\cdot \rightarrow NOT,\cdot \rightarrow NOT)\rightarrow OR\rightarrow OUTPUT$
Doing this without thought can increase the circuit size exponentially. So, when you see two $NOT$ gates one after another - cancel both of them out. I guarantee you this will work, but I wont prove it to you (this is your task)


Calculating speedup of this parallel program I have a sequential program that has a cost of
$(\sum_{n=1}^{N} Ti )$  Where Ti is the load time of the i-th element, so if consider $Tm = max({Ti}) $ i can approximate the sequential cost as $N*Tm$ that has a linear cost.
Let's suppose that i have c cores and i decide to parallelize this program, i can divide the loading of these items among c cores so i have (At most)
$(\sum_{n=1}^{N/C} Ti ) \leq Tm \cdot N/C$
So in brief:
Sequential (approx.) cost: $N*Tm$
Parallel(approx.) cost: $[N/c]*Tm$
How can i calculate the speedup? what about the efficiency?
Thank you.

Kind of application you mention seems to be I/O bound i.e., application execution time is dominated by I/O time (Ti). In this case using multiple threads is not going to be advantageous as there is only one connection between your I/O device (permanent storage) and CPU (having multiple cores). That one connection is the bottleneck. You will not observe much of a speed-up as you increase the number of threads. There may be slight gain as number of threads increase initially, as threads try to saturate and use the maximum bandwidth possible for the I/O connection. Gain will also depend on how much time is spend on I/O and how much on processing of read data. Both of them can run in parallel for two different threads. But your question seems to suggest that I/O time (to get data) >> compute time (to process data). Hence there will be limited gain by increasing the number of threads. Instead, try to optimize the I/O. Keep it sequential and read in larger blocks.


Definiton of a certain symbol in a proof(The right linear languages are exactly the finite state languages) I want to stress that i am not looking for a proof of this question, but rather if someone(that is familiar with the proof and it's context) can explain to me what the symbol 'e' means in the context.

the letter 'e' first appears in line 6:S $\rightarrow $e...

This is crucial for me, because i am not able to deduct from the context what its meaning and write a formal proof

The letter $e$ stands the empty word, which is usually denoted by the symbol $\varepsilon$.
A hint of this is that, according to step 6, if $S \to e$ then the initial state $S$ is also a final state.


Do NPDA work in parallel? Assume my language is
$$
L= ww^{r}\
$$

Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice here. Now each branch will get the current stack contents and start its operation.

So my question is, do these branches operate in parallel or one after another? We have only one stack and each branch will do push/pop according to its requirement and changes the stack. Even if a branch results in dead end, we need to proceed further. How is a single stack able to manage this scenario, as stack contents are changed by each branch?

That's not how non-determinism works, though perhaps it's how you'd simulate it in real life. Here are several ways of thinking about non-determinism.

The genie. Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if the input is not in the language, whatever the genie tells the machine to do, it will always reject.

Hints. The machine computes a bivariate function. The first input is a word $w$, and the second input is a "hint" $x$. Whenever the machine faces a non-deterministic choice, it consults the next hint symbol, and operates accordingly. We are promised the following:

Completeness: if $w \in L$ then there is some hint $x$ which causes the machine to accept.
Soundness: if $w \notin L$ then the machine rejects on all hints.

Accepting computations. An accepting computation is a legal computation (one in which the machine always operates according to one of the choices it is faced with) which ends at an accepting state. A word is in the language iff it has an accepting computation.

We can formalize the notion of accepting computation using snapshots. A snapshot is a triple $(q,z,t)$, where $q$ is the current state, $z$ is the part of the word which remains to be read, and $t$ is the contents of the stack. We can define a relation $(q_1,z_1,t_1) \vdash (q_2,z_2,t_2)$ which expresses that the machine can reach snapshot $(q_2,z_2,t_2)$ from snapshot $(q_1,z_1,t_1)$ in one step. An accepting computation for a word $w$ (for the acceptance condition of emptying the stack) is a sequence $\sigma_0 = (q_0,w,\bot),\sigma_1,\ldots,\sigma_N=(q,\epsilon,\epsilon)$, where $q_0$ is the initial state, $\bot$ is the initial state of the stack, $q$ is an arbitrary state, $\epsilon$ is the empty word/stack, and $\sigma_{i-1} \vdash \sigma_i$ for all $i$.

Another equivalent description is in terms of reachability. Consider a directed graph in which vertices are snapshots and there is an edge from $\sigma$ to $\tau$ if $\sigma \vdash \tau$. An accepting computation is a path from $(q_0,w,\bot)$ to $(q,\epsilon,\epsilon)$, for any state $q$.


Maximizing the sum of adjacent pairs of elements I encountered the following interesting problem on stackoverflow:

  Given numbers $a(1)<\cdots<a(n)$, find a permutation $\pi$ that maximizes $$\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1)).$$

The answers there claim that the answer doesn't depend on the numbers themselves, and is always given by the order $$\ldots,a(n-5),a(n-3),a(n-1),a(n),a(n-2),a(n-4),\ldots$$ However, the proof (given in the comments) isn't convincing.

  Is the answer on stackoverflow correct? Can we prove it?

The following answer is due to Reuven Bar-Yehuda.

Let us call an order maximal if it maximizes the objective function $\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1))$.

Lemma 1. If $\pi$ is maximal then for all $1<i<j<n$,
$$\pi(i-1) < \pi(j+1) \text{ iff } \pi(i) < \pi(j).$$

Proof. Suppose that $\pi(i-1) < \pi(j+1)$ and $\pi(i) > \pi(j)$. Form the permutation $\sigma$ by reversing the order all $\pi(i),\ldots,\pi(j)$. Then
$$
\sum_{k=1}^{n-1} a(\sigma(k)) a(\sigma(k+1)) - \sum_{k=1}^{n-1} a(\pi(k)) a(\pi(k+1)) = \\
a(\sigma(i-1)) a(\sigma(i)) + a(\sigma(j)) a(\sigma(j+1)) - a(\pi(i-1)) a(\pi(i)) - a(\pi(j)) a(\pi(j+1)) = \\
a(\pi(i-1)) a(\pi(j)) + a(\pi(i)) a(\pi(j+1)) - a(\pi(i-1)) a(\pi(i)) - a(\pi(j)) a(\pi(j+1)) = \\
(a(\pi(i-1)) - a(\pi(j+1)) (a(\pi(j)) - a(\pi(i)) > 0. \quad \square
$$

Lemma 2. If $\pi$ is maximal then $\pi(1) < \pi(i)$ for all $i \neq n$ and $\pi(n) < \pi(j)$ for all $j \neq 1$.

Proof. Both claims have a similar proof, so we only prove the first. Suppose that $\pi(1) > \pi(i)$ for some $i \neq n$. Form the permutation $\sigma$ by reversing the order of $\pi(1),\ldots,\pi(i)$. Then
$$
\sum_{k=1}^{n-1} a(\sigma(k)) a(\sigma(k+1)) - \sum_{k=1}^{n-1} a(\pi(k)) a(\pi(k+1)) = \\
a(\sigma(i)) a(\sigma(i+1)) - a(\pi(i)) a(\pi(i+1)) = \\
(a(\pi(1)) - a(\pi(i)) a(\pi(i+1)) > 0. \quad \square
$$

Theorem. If $\pi$ is maximal then $\pi$ is the following permutation or its reverse:
$$ 1,3,5,\ldots,6,4,2. $$
Proof. Lemma 2 shows that $a(\pi(1))$ and $a(\pi(n))$ are both smaller than $a(\pi(2)),\ldots,a(\pi(n-1))$, and so $\{\pi(1),\pi(n)\} = \{1,2\}$. Without loss of generality, assume that $\pi(1) = 1$ and $\pi(n) = 2$.

Lemma 1, applied with $i=2$ and $j=3,\ldots,n-1$, shows that $\pi(2)$ is smaller than $\pi(3),\ldots,\pi(n-1)$, and so $\pi(2) = 3$.

Lemma 1, applied with $j=n-1$ and $i=3,\ldots,n-2$, shows that $\pi(n-1)$ is smaller than $\pi(3),\ldots,\pi(n-2)$, and so $\pi(n-1) = 4$.

Continuing in this way, we recover the rest of $\pi$. $\quad \square$