Are all prefix codes uniquely decodable? I can't think of any counterexample but I can't find any such statement on the internet or my textbook either. I know that for each uniquely decodable code, there exists a prefix code with the same average length.

You can prove by induction on the length of the encoding that any string is uniquely decodable.

Let $s=s_1...s_n$ be some string encoded with a prefix free code. Since our code is prefix free, there exists a unique prefix of $s$, $s_1...s_j$ which is a code word. $s_{j+1}...s_n$ is also a valid encoding (we removed a single codeword from a concatenation of codewords), so by our inductive hypothesis, $s_{j+1}...s_n$ is uniquely decodable, which completes the proof.


Random conditional association I have a really specific problem to solve and i'm looking for an existing algorithm to help me (i hope i'm in the right section of stackExchange).

I would have to make "random" association between items but all association need to have to answer to specific conditions.

Below, an simple exemple in javascript.

INPUT

var items = [12, 32, 25, 11, 8, 2, 4, 3, 8, 9];
CONDITION

All couples sum need to be between "20"(include) and "27"(include).

OUTPUT

result = [[12,9], [11,9], [25,2], ...];

This is a really "simple" exemple. I need to implement this with at least 3 or 4 items by couples but the conditions is almost the same.

Is it an algorithm that existing to easly do this kind of stuff ? Or did i need to iterate all couples possibilities to pick up randomly after ? Even a way to iterate less for the generation of all couples would be nice.

Thank you a lot for your help.

There is a similar problem, where you're looking for pairs with a given sum $S$.

For that problem, you initialize an empty set and then iterate once through your numbers. For each number $x$ you do:

Check, if the number $S-x$ is in the set. If it is, you can form the pair $(x,S-x)$.
Add $x$ to the set.

If its allowed to use a number twice, you would only have to switch step (1) and (2).

To check for ranges instead of exact sums you would have to adapt your data structure. You would exchange the set with a range tree and do the following:

Query your range tree for the range $(low-x,high-x)$ (where low and high are 20 and 27 in your example). This query will return a set $P$ of numbers and you can form a pair  $(x,p) \forall p \in P$.
Add $x$ to the range tree.

Obviously, this approach only works for pairs. If you want to get all tuples with 4 elements you could first generate all distinct pairs and then try to combine them with the approach I've outlined above. This would result in an $\mathcal O (n^2 \log n)^*$ algorithm (same for tuples with 3 elements, though you would add the pair-sums to the DS and query with the elements from your initial array and not with other pair-sums).

*: This runtime is only correct if the size of tuples in a range is bounded with $\mathcal O(1)$. The worst case without this assumption is of course $\mathcal (N^4)$, when e.g. you have $N$ positive numbers and your allowed range is from $0$ to $\infty$ (result = all possible 4-tuples, without constraints).

PS: I think it's highly likely, that there cannot be a better algorithm, as this problem is an adaptation of 3SUM.


What's the right way to think about a CFG symbol with an infinite null derivation? I'm curious about the right way to characterize symbol $A$ in a CFG like this one:

$$
\begin{align*}
A &\to A B\\
A &\to x\\
B &\to y\\
B &\to \varepsilon
\end{align*}
$$

$B$ is certainly nullable. However, should $A$ be considered nullable? It feels like the answer is probably "no" (and most first-follow implementations I've seen either agree or crash on this). However, you can derive an infinitely large parse tree for the null symbol sequence like $A \to A(A(A(...) B()) B()$.

The infinitely large parse tree you propose does not represent the parse of any sentence, because its leaves are not all terminals.

A more precise statement would be that $A$ cannot derive the empty sentence. You can produce an arbitrarily long derivation of $A$ by repeatedly using the rules $A \to A B$ and $B \to \epsilon$ but none of those derivations is empty. Since the precise definition of "nullable" is "a non-terminal which can derive the empty sentence", $A$ is not nullable.

If a FIRST/FOLLOW implementation crashes on that input, then the implementation is buggy. The correct computations are:

$$\begin{align}
FIRST(A) &= \{x\} \\
FIRST(B) &= \{y, \epsilon\} \\
FOLLOW(A) &= \{y, \epsilon\} \\
FOLLOW(B) &= \{y, \epsilon\}
\end{align}$$


Solution to a Np-hard problem and its relevance to a dual LP From The design of APX algorithms book by David P. Williamson and David B. Shmoys, at the bottom of page 21 I saw the following statement (it is about the set cover LP and its dual):

  Let $y^*$ be an optimal solution to the following dual LP $$max \sum_{i=1}^n{y_i}$$$$subject \sum_{i:e_i\in{S_j}}{y_i \leq w_j}, y_i \geq0; j=1,...,m;i=1,...,n$$
  and consider the solution in which we choose all subsets for which the corresponding dual inequality is
  tight; that is, the inequality is met with equality for subset $S_j$, and $\sum_{i:e_i \in{S_j}}{y^* = w_j}$. Let $I^{'}$
  denote the indices of the subsets in this solution. We will prove that this algorithm also is an $f$-approximation algorithm for the set cover problem

I would like to know what does the writer mean by corresponding dual inequality? Is there any correspondence between a solution of the Set Cover problem and a dual LP solution?

I can't understand what does the paragraph mean.

Thanks in advance.

Any linear program has a dual linear program, whose constraints are in one-to-one correspondence with the variables of the primal program. Under mild conditions, the optimal value of the dual program coincides with the optimal value of the primal program, and certain conditions known as complementary slackness are satisfied by any pair of optimal solutions.

In this case, however, we are already looking at the dual linear program; the constraints here correspond to subsets. In detail, the constraint $\sum_{i\colon e_i \in S_j} y_i \leq w_j$ corresponds to the subset $S_j$.

What is the relation to Set Cover? There is a natural linear program which is a relaxation of a natural integer programming formulation of Set Cover. If you compute its dual, you get the linear program that you quote. (If you're not sure which primal linear program was used to generate this dual linear program, you can always compute the dual of the dual linear program to get back the primal linear program.)


Can a 1-tape turing machine simulate a stack? Is it possible to simulate a stack-based machine using a 1-tape turing machine? I cannot wrap my head around it as turing machines do not provide mechanisms such as pointers.

I failed to find any examples or explanations. If it is possible, how?

Machines that have only a stack are called pushdown automata. They are less powerful than Turing machine, so yes: TMs can simulate stacks.

Turing machines are a fairly simplistic model of computation, which can make programming in them hard. Try to start with simple things; for instance, implement a counter. If you feel ambitious, try implementing the basic building blocks of (Turing-complete) imperative programming as Turing machines. This should convince you, then, that TMs are as powerful as any other¹ model.

As for your question, you don't need pointers for a stack. TM tapes have a direction, and you can easily label cells by introducing special alphabet symbols; the TM can then move over the tape and look for these labels. It's all a matter of encoding.

Ignoring hyper-computation.


Can we split a vector into positive and negative parts in LP? Say you have a vector $v$ with $n$ length $v=\begin{bmatrix}v_1&\dots&v_{n}\end{bmatrix}$ can we write as $v=v_+-v_-$ where $v_+$ agrees with $v$ on non-negative components and is $0$ otherwise and $v_-$ agrees with $v$ on non-positive component and is $0$ otherwise.

Eg: $v=[-1,-3,4,5,0,0,1,2,-3,-4]$ then $v_+=[0,0,4,5,0,0,1,2,0,0]$ and $v_-=[-1,-3,0,0,0,0,0,0,-3,-4]$ holds.

I tried using $\max(0,v_i)\leq v_+(i)$ and $v_-(i)\leq\min(0,v_i)$ operations. I am unable to write this correctly without convex optimization.

$v$ is not a constant for me and is a variable. So is there a way to do this with only feasibility Linear Programming with only perhaps $O(1)$ integer variables?

Unfortunately, in the general case, no.

Consider if we had a single variable $x$, one can then write out $x = x_+ - x_i$, and have that $x_+, x_- \geq 0$.

The problem is that one can increase both $x_+$ and $x_-$ by any value $\Delta$ and the value for $x$ stays the same. There isn't any convex way to enforce that one of the values is 0. $\min\{x_+, x_-\} = 0$ is non-convex. One can understand that trying to enforce this is non-convex, by considering two axes, one for $x_+$ and the other for $x_-$. Requiring that one of them be 0, is equivalent to enforcing that the solution must lie on an axis - any penalty incurred where they are both non-zero (e.g. $\min\{x_+, x_i\}$, or $x_+ x_-$), then implies non-convexity.

One may be able to deal with this in an acceptable way by applying an $\ell_1$ penalty of $c(x_+ + x_-)$ for some small constant $c$ which doesn't cause too much distortion to the objective.

Of course, if the number of variables for which one wants to apply this is small enough, one can always consider solving all the different options explicitly (i.e., $x_+ \geq 0, x_- = 0$, $x_- \geq 0, x_+ = 0$), but this will only work for a very small number of variables.

Otherwise, one needs to resort to non-convex optimization techniques, which of course aren't guaranteed to find a global minimum.


Build max heap in which all the nodes at certain level are less than all the nodes at the level before them Max-heap is called a "strong" max-heap if all the nodes at certain level are less than all the nodes at the level before them. What is the most efficient way to build such a heap from a given array?

I was thinking about something similar to the regular build heap algorithm: scanning the array from right to left, compare every node to all of the nodes at the level below her, replace her with the max node and continuing until it reaches to the right position. However, I'm not sure How to make it more efficient.
Thanks

Here's a simple way to approach it. Let's assume the array has $n = 2^k - 1$ distinct elements for convenience.

Find the median in $O(n)$ using quickselect.
Partition into two halves (greater and lesser-equal).
Insert the lesser-equal half all as leaf nodes (deepest empty nodes).
Repeat 1-3 on the greater half until you only have 1 value left which will be the max value.

Time complexity is: $$T(n) = T\left(\frac{n}{2}\right) + \Theta(n)$$
Which overall is linear $O(n)$ time complexity.


is there a (FLAC like) loseless compression coding format for EEG data? EEG and Audio data are very similar, both

are numerical samples in continuous sequence

have a sample rate

need and can have multiple channels

channels for multi-channel audio
channels for each electrode

have predictable characteristics that are exploitable for compression.

FLAC is specifically designed for efficient packing of audio data, unlike general-purpose lossless algorithms such as DEFLATE, which is used in ZIP and gzip. While ZIP may reduce the size of a CD-quality audio file by 10–20%, FLAC is able to reduce the size of audio data by 40–50% by taking advantage of the characteristics of audio.

is there a standard loseless compression coding format for EEG data, that takes advantage of the characteristics of EEG, like FLAC takes advantage of the characteristics of audio?

For single channel with raw signal, the best option is Elias gamma, for single channel frequency signal, the best option is to use Range encoder. For multiple channels, this is still viable option to compress each channel and then compress them together interleaving signal (one sample from all electrodes, then another sample from all electrodes).

If you have multiple channels, there are inter-channel correlations, which should be used for compresion, standard method is to use DPCM or use DCT-IV for decorrelation (this is the very same transform like in JPEG) and then use arithmetic codding of any kind. For online setting - compress signal as it goes - this is very good idea.

Another standart approach is Karhunen-Loeve transform. Do not use autoregressive methods, use Elias gamma in the pipeline instead.
Another approach is to use DCT transform to remove redundancy of interchannels (decorrelation) and compress in minimal frequency form.

If you need to store volumes of EEG data, my advice is to clear it from noises and store bands you are interested in, otherwise you store mainly hard to compress noise.


What threads share in general? Well this is general question. And if anyone want to make it implementation specific then I will prefer Unix related stuff. But first need to know following problems in generality:

I read single process can have multiple threads. Multiple threads of same process does share things among them. I want to know what they share and what not.
Considering process is comprised of address space, stack, heap, global variables, code, data, OS resources, what among them is shared by threads? I have following guessings:

Global variables - I have read thread shares global variable. Also while programming in Java and C#, I have made threads to share class level variables. So I am believing that the threads share global variables (though not sure whether the concepts in high level programming languages translates as is to low operating system level facts).
Heap - Since global variable is stored in the heap, heap is shared among threads.
Stack - Since each thread can have its own execution sequence/code, it must have its own stack on which it might push/pop its program counter contents (when say function calls and returns happen). So threads of same process do not share stack.

Now I am unsure about the sharing of following things

Address space - Not sure what exactly counts under address space. But I guess address space is generally used in the context of processes, not threads. And since all threads of same process reside in the same address space as the parent process, it is said that threads share address space. (But then they maintain different stack inside same address space?)
OS resources - I guess this can be very implementation specific. For example, parent process can selective give handle of same file to some of its threads and not to all. Or I am mistaking and OS resources means something other than files?
Code - Threads can have different code, so sharing code is not always the case.
Data - Unsure about what to consider under data. But sure that global variables are shared among threads. And sure that local variables are not similarly shared.

Overall I am considerably confused due to vague terms, super-generalizations done in the Operating Systems books and extra-implementation specific details provided online. So I am trying to find some answer that can satisfy me.

In general each thread has its own registers (including its own program counter), its own stack pointer, and its own stack.  Everything else is shared between the threads sharing a process.

In particular a process is generally considered to consist of a set of threads sharing an address space, heap, static data, and code segments, and file descriptors*.

An address space is simply the mapping of logical addresses to specific pieces of physical memory. So when we say that all the threads in a process share the same address space we mean that when accessing a variable foo in global scope all the threads will see the same variable.  Similarly, the threads may all be running a different point in the code at any particular time, but they are all permitted to call the global function bar(), which will correspond to the same function for every thread in the process.

Most modern operating systems have added a notion of thread local storage, which are variables of global scope that are not shared.  The usual example of the use of this is for the variable errno.  That's a single variable of global scope, but in most modern operating systems each thread is given its own local copy, so that an error in a library call on one thread won't impact the behavior of other threads.

* There is some additional process state shared by all the threads in a process, things like the process id, the signal handling, and file locks.  For a complete list of process state shared by threads you need to look at the documentation for the specific threading implementation.  For example, the pthreads man page.


What is a fixed point in the context of Roger's fixed-point theorem? In the Wikipedia article on Rogers' theorem, it is stated that all total computable functions have a fixed point.  The notation is a little hard for me to understand; a symbol is used that is used to denote "semantic equivalence."  I do not know what semantic equivalence is; I would appreciate it if someone could shed some light on what a fixed point is in this context, and on what semantic equivalence is in this context.

The notation is explained in the Wikipedia entry (though regrettably after its first use): for partial functions $f,g$, we say that $f\simeq g$ if for all inputs $x$, $f$ halts on $x$ iff $g$ halts on $x$, and if both halt on an input $x$, then $f(x) = g(x)$. In other words, $f$ and $g$ compute the same partial function, and so they are semantically equivalent: they result in the same outcome.

The idea behind semantic equivalence is that two programs might be different but could be equivalent in the sense that they compute the same function. For example, if there are two statements $x \gets 0; y \gets 1$ and we switch their order to $y \gets 1; x \gets 0$ then the resulting programs are different syntactically but equivalent semantically.

Roger's theorem shows that for every total computable function $P$, which we think of as a transformation rule for programs, there is some program $e$ that is equivalent to $P(e)$. The rest of the Wikipedia entry explains why this is useful.


Is there a proof that "undetectable" malware cannot be written? In Fred Cohen's paper "Computer Viruses - Theory and Experiments", he proves that for the general case, classifying malware is an undecidable problem. I was wondering whether there might be a similarly well-known proof that an undetectable malware can or cannot be written.

For every malware, there exists some detector that will detect it.  (For instance, given a specific malware $M$, consider the detector that just checks whether its input is $M$ or not, and if it is, outputs "malicious".)

Conversely, Cohen's result shows that for every detector that classifies all benign samples correctly, there exists some malware that it won't detect.

So, there is an unavoidable arms race, if you want to try to detect malware statically.


Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes I want to compute the median in an array of size $m$ which consists of distinct integers from $\{0, 1, ..., n-1\}$, I have $m<n$. By median I mean the middle element (rounding up/down if the array size is even) in the sorted version of the array.

Ideally, the expected number of passes over the array should be $\mathcal{O}(\log{}n)$, the used memory should be $\mathcal{O}(\log{}n)$ bits and the solution should be exact. I'm flexible with the time complexity as long as it's feasible.

Since finding the median in an unsorted array is such a common problem I expected to quickly find some solution which suits my needs but after some research I'm wondering if this is even possible. Does anyone know a solution or where I could expect to find one?

The natural algorithm determines the $\log n$ bits of the median, MSB to LSB. Suppose that we have determined the $k$ MSBs of the median, $b_{m-1},\ldots,b_{m-k}$. Determine the number of integers in the array whose $k+1$ MSBs are $b_{m-1},\ldots,b_{m-k},1$, and use this to find the $(k+1)$th MSB of the median.

This algorithm uses $O(\log n)$ passes and $O(\log m + \log n) = O(\log n)$ space.


How to design a finite state machine to detect 0110 in the input? My task is to design a FSM whose output goes high for a single cycle whenever the pattern 0110 is detected on its input. The patterns may overlap, so an input 0110110 of would cause the output to go high twice- once for the first pattern (0110110), and once for the second pattern (0110110). a is used for the input and f is used for the output.

I am assuming I will need five state bubbles like this.

Is this correct or am I missing some cases based on the pattern going high twice if the pattern overlaps?

It looks like you're missing the overlap case, if I understand your diagram correctly.  This does the trick:

A    // goto B if read 0 else stay
B    // goto C if read 1 else stay
C    // goto D if read 1 else goto B
D    // goto E if read 0 else goto A
E    // emit rising edge, goto B

assuming that you have a falling edge after every read.


Disadvantages to using simple step functions for activation in neural networks? From what I have read, the main advantage to using tanh(x) or sigmoid(x) as an activation function for neural networks is that it is very easily differentiable.

I am trying to implement a neural network that uses a genetic algorithm for optimisation rather than backpropogation, and therefore it doesnt matter if my activation function is differentiable or not

When running my algorithm on matlab/octave, it seems like there is a massive bottleneck in the computation when it is trying to calculate sigmoid of the input to the neuron, so I was wondering if there would be any disadvantage to using a simple step function instead of the more complex sigmoid or tanh functions to activate the neuron?

The disadvantage would be that your fitness landscape would look less smooth (a small change in your weights may result in a big change in the output or no change at all). This may affect the convergence speed of your GA, since small changes in the chromossomes may not produce differences in fitness, rendering it blind to some benefical changes.
If your problem is performance, I'd suggest to try the hard ReLU activation function instead of a sigmoid one.


Since physical memory is the RAM where is logical memory stored on the computer? Since logical memory maps to the RAM (physical memory) it has be stored somewhere right and it will obviously take large bunch of memory of itself. Where is it stored?

I'm not sure what you mean by "logical memory"...

Memory is usually composed of physical memory and virtual memory. Physical memory is usually RAM, hard drives, solid-state drives, etc. It's the actual chips and stuff you plug into your computer (hence "physical").

However, it would be impractical if a larger scale OS is trying to run various applications at once and we only use this memory in a sequential manner, right? That's where virtual memory and virtual mapping comes into play. It's a matter of optimization used by the OS to improve performance.

"It" isn't exactly "stored" anywhere.


Bidirectional Encryption I would like a way to hide a piece of information from Alice and Bob. Let's say this piece of information lets Alice and Bob vote me off the island. If Alice had this information she could vote me off even if Bob did not want that. Likewise if Bob had this information he could vote me off the island even if Alice did not want that. However I'd like Alice and Bob to be able to vote me off the island if they both agree that its in their interest. So I'd like to give Alice and Bob a piece of information such that they can combine that information to vote me off the island.

One very simple method I thought of was to encrypt the information. Give the encrypted information to them. And give them each half the key that I encrypted that infomation with. I wasn't however sure how secure this was or what problems there might be with it. Additionally this is (deliberately) just like some of the naively proposed methods by which back doors might be added to encryption. I'm trying to consider what is wrong with this from a mathematical stand point. So does this method have some known theoretical issue (not issues in practice)? Is there an efficient algorithm that attacks it? If this method is a bad method then is there a good method? If not then is it possible for there to be a good method?

That is called secret sharing.

The usual method for the 2-shares case is the method you thought of with the one-time pad.

Note that usual secret-sharing schemes provide no protection against fake shares.


Language Recognition Devices and Language Generators I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses just like the text books I have.

My question is about language recognizers verses generators.

I get the overriding principle of a recognizer. That it analyses a language and is able to determine nay or yay if a String belongs to a language.  This is at least what I have picked up from the books and notes. However, it's much more complex than that is it not? A tokeniser and syntax analyzer  (which I assume to be recognizers) do not just say yes or no, they also say where and somtimes what don't they...?

However, regarding language generators,I cannot find a very clear explination about what they are. The typical description I get is,  for example in Sebasta's Concepts of programming languages says 'A language generator is a device that can be used to generate the sentences of a language. We can think of a generator as a push button that produces a sentence of a language every time it is pressed.'  Seriously? That's it?? Your kidding right....

I read that Regex is an example of a Generator, then why when people talk of generators to they not talk of the inputs. For example Regex has a target String, and the Regex with defines both the accepted alphabet and it's grammar rules.

Can someone provide for me a clearer distinction of what a recogniser is?

For a language $L$, a recognizer of $L$ is an algorithm that computes

$\qquad \chi_L(w) = \begin{cases} 1, & w \in L \\ 0 , &w \not\in L\end{cases}$.

Note that in computability and complexity theory, these are sometimes called deciders and algorithms that compute

$\qquad \tilde\chi_L(w) = \begin{cases} 1, & w \in L \\ \uparrow , &w \not\in L\end{cases}$

are called acceptors.

A generator or enumerator can be modelled as an algorithm computing

$\qquad e_L(i) = w_i$

where $L = \{ w_i \mid i \in \mathbb{N} \}$. As it turns out, $e_L$ and $\tilde\chi_L$ are equal in power (cf. the set of recursively enumerable languages) but $\chi_L$ is stronger (cf. the set of recursive/decidable languages).

You typically want compilers to be deciders; interpreters are arguably recognisers.

A regular expression (or, for that matter, a grammar) does not fit in this terminology per se. I'd say they give a descriptive representation of their languages while above notions are algorithms representatios. Grammars have a slighly more enumerative feel (since translating them into a top-down generator of words is intuitive) while regular expressions feel more like deciders (via their NFA), but it's also easy to build acceptors from grammars.


Using pumping lemma to prove that $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ is irregular Given the following language:
$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
I am trying to prove that it is not regular. On the one hand my intuition tells me that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{j's}$.
However, when I try to prove that it is irregular using the pumping lemma I have trouble finding which word I should use to arrive at a contradiction.
Any suggestions?

You can use the word $a^pb^p$, where $p$ is the constant promised by the pumping lemma.


Search on Conformant Problem: solution for subset of a belief state I am having trouble understanding the following statement.

I have understood why in a sensorless/conformant problem, if there exists a solution (a sequence of actions) for a belief state $b$, then it is also a solution for any $b'$ that is a subset $b$.

Next claim is what is confusing me.

Then in a standard graph search, we can save time by pruning some branches from the search tree.

Example from the Sensorless Vacuum World problem in Russel Norvig.

When we have a successor $\{1,3,5,7\}$ generated during graph search, we do not add it to the frontier if we have already expanded the belief state $\{5, 7\}$ which is a subset.

I thought those cases are totally unrelated since each belief state may encode a different path from the start state. If $\{5, 7\}$ does give us a solution, we have no guarantee it will work for $\{1, 3, 5, 7\}$. It's also possible $\{1, 3, 5, 7\}$ can lead to a solution through a different path.

I must be missing something.. can someone please explain?

'different path from the start state': The sensorless vacuum world is by definition a 'single-state problem', that is, all variables in the world are incorporated into a single state variable. In that case, history doesn't matter. If we are in state 5 by one path, the world is exactly as it would be if we had got there by another path.

For an example of something else represented as a single-state problem, consider chess: you might say history matters because whether you can castle, depends on whether the king has moved, not just the current board position. Okay so if we represent chess as a single-state problem, then the state would encode not only the current board position but also other relevant variables like whether the king has moved.

Subsets: if we know how to get to {5,7}, we don't need to be interested in {1,3,5,7}. Getting to {5,7} gives us all the same information plus more besides.


How to remove null production from context free grammar? How to remove null production and simply the grammar?
$$
S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A
$$
Can the simplification result in this CFG?
$$
S \to a \mid aBa \\ A \to b \\ B \to b
$$

Your simplification is wrong. The language of the first grammar includes $b$, but the one of the second grammar does not.
If you replace the definition of $A$ in the productions of $B$ you obtain $B \to b \mid \epsilon$. Then if you replace $A$ and $B$ with their definition in $S$ you have.
$$
S \to a \mid bb \mid b \mid aba \mid aa
$$


Is $L:=\{a^k \mid k \text{ is prime}\}$ regular? For this exercise the pumping lemma should be used. My instructor gave me a tip it should start with $w:= a^{prime(n)}$ where prime is a while program returning the nth prime number. This does make sense to me since a while program always returns an element of the integers. How can I use code in my proof?

You don’t need any code. If S is any set of integers such that the difference between neighbouring elements becomes arbitrary large, then $\{a^k: k \in S\}$ is non-regular.


Period of a pseudo-random sequence generated using an LFSR I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR).
I have read from many sources that the length of the pseudo random sequence generated from the LFSR would be maximum if and only if the corresponding feedback polynomial is primitive.

I have tried to generate the pseudo random sequence for the primitive polynomial (4,1,0) (corresponding to polynomial $x^4 + x + 1$) by tapping at bits 4 and 1, and it has resulted in a sequence with a period of $2^4$ - 1 = 15. Similarly I have tried primitive polynomial given by (3, 1, 0) (corresponding to polynomial $x^3 + x + 1$) by tapping at bits 3 and 1 and it has resulted in a sequence of period $2^3$ - 1 = 7.

When I tried to apply this same logic to the primitive polynomial (5, 2, 0) (corresponding to polynomial $x^5 + x^2 + 1$) it yields a sequence with period 15. While it should have yielded a sequence with period 2^5 -1 = 31. Following is the circuit diagram for (5, 2, 0)

1) What is the exact procedure to convert the given polynomial into a maximal length LFSR?

2) How do I determine the correct tap bits for a given polynomial?

The LFSR that you give is really of length $4$ rather than $5$, since $b_1$ never gets used. The correct way to implement a "Fibonacci" LFSR is explained in the Wikipedia article: $b_1$ should be the leftmost bit rather than the rightmost bit.

There is also an alternative kind of LFSR knows as a "Galois" LFSR, also described in Wikipedia, which is dual to a Fibonacci LFSR: at each point, the contents of the register is shifted, and if the bit which is shifted out is 1, then a mask is XORed to the contents. In both types of LFSR, the resulting sequence has maximum period iff the feedback polynomial is primitive.

The polynomials that you give as examples are known as trinomials, polynomials with three non-zero monomials. Not all trinomials are primitive. There are algorithms for deciding whether a trinomial, or any other polynomial, is primitive. As far as I know, there is no explicit construction of primitive polynomials.

How do we test whether a given polynomial $P$ of degree $n$ is primitive? The first step is verifying that it is irreducible. The second step verifies that $x^{(2^n-1)/p} \not\equiv 1 \pmod{P}$ for every prime divisor $p$ of $2^n-1$ – this step requires factoring $2^n-1$. A list of primitive polynomials can be found on Wikipedia.


Finding nd - m dimensional neighbors for a given node within a balanced hyperoctree I'm writing a balanced $n_d$-Hyperoctree data structure in which the only fundamental operations I provide are edge traversals between parent and child nodes. I'm storing the nodes using a Morton z-curve.

Using only this information:

The level of a node can be computed by traversing to the root of the tree.
Neighbor searches are performed by traversing the tree up until a common parent is found, and then traversing the tree back down again.

I can compute the following constants depending on the number of spatial dimensions $n_d$:

the #of children of a node: $2^{n_d}$,
the #of $n_d - m$ dimensional neighbors for each node (in 3D, $n_d - 1$ neighbors are faces, $n_d - 2$ neighbors are edges, $n_d - 3$ neighbors are corners):

$2^{n_d} \begin{pmatrix} n_d \\ m \end{pmatrix}$

The neighbors sharing a $n_d - 1$-dimensional face with each Hypercube form the set $\mathcal{N}_{n_d - 1}$. They are numerated within this set as follows. The neighbor at the negative side from the node center comes first, then it comes the neighbor at the positive side. That is, for $n_d = 1$ I just have $\mathcal{N}_{n_d - 1} = \lbrace 0, 1 \rbrace = \lbrace \mathrm{Left}, \mathrm{Right} \rbrace$.

In $n_d = 2$, $\mathcal{N}_{n_d - 1} = \lbrace 0, 1, 2, 3 \rbrace = \lbrace \mathrm{L}, \mathrm{R}, \mathrm{Top}, \mathrm{Bottom} \rbrace$.
In $n_d = 3$ it is $\mathcal{N}_{n_d - 1} = \lbrace 0, 1, 2, 3, 4, 5 \rbrace = \lbrace \mathrm{L}, \mathrm{R}, \mathrm{T}, \mathrm{B}, \mathrm{Front}, \mathrm{Back} \rbrace$

and so on.

I haven't been able yet to generalize the algorithm for finding the $n_d - 1$ neighbor located at a given position to arbitrary dimensions. My current algorithm traverses the tree up until a common parent node is found. During the up traversal it stores the child positions w.r.t. their parents of the nodes traversed. Then it traverses the tree back down using the reversed path of the up traversal. The child positions are found by finding the siblings of the child positions during the up traversal in the inverted neighbor direction, which can be computed as:

$\mathrm{inverted\_neighbor\_position}_{n_d - 1}(p) = (p + 1) * (p \% 2 = 0) + (p - 1) * (p \% 2 \neq 0)$

However, to know if a common parent has been found, it checks if a parent node has a childe at a given relative position of another child which expressed as a neighbor position, i.e., it checks if a node has a sibling in a given neighbor direction within its parent. I have only a hand-coded stencil for this check and haven't been able to generalized.

Can this check for a "common parent" be generalized to arbitrary dimensions? How?
Example up to 3D: for a child and a neighbor position, returns the child position of the sibling:

// i means, there is no sibling for that child in that direction
//0  1  2  3  4  5     << nghbr position
{ i, 1, i, 2, i, 4},  // child 0
{ 0, i, i, 3, i, 5},  // child 1
{ i, 3, 0, i, i, 6},  // child 2
{ 2, i, 1, i, i, 7},  // child 3
{ i, 5, i, 6, 0, i},  // child 4
{ 4, i, i, 7, 1, i},  // child 5
{ i, 7, 4, i, 2, i},  // child 6
{ 6, i, 5, i, 3, i}   // child 7

Assuming that the $n_d - 1$ dimensional neighbors can be found:

How can I find $n_d - m$ dimensional neighbors?

Right now, I hand-coded traversals that perform $m$ times searches for $(n_d - 1)$ neighbors. Is there a general way to generate these traversals for $n_d$ dimensions and the $n_d - m$ neighbors?

What is a suitable order for $n_d - m$ dimensional neighbors where $m > 1$ ?

Most of the research I've found in the literature uses hand coded stencils for, 1,2,3 and 4 dimensions, but no general ways of generating these stencils. So if anyone can point me to relevant literature I would appreciate it.

You are asking two different questions:

What are the $2^{n_d} \binom{n_d}{m}$-many codimension $m$ neighbors of a given node?
Given a description of a neighbor, how to locate it?

Regarding the first question, a neighbor of codimension $m$ is given by (1) a subset $S$ of the coordinates of size $m$, (2) for each $x \in S$, a direction $d_x \in \{-1,+1\}$. The address of a neighbor is obtined by adding $d_x$ to coordinate $x$.

Regarding the second question, the simplest algorithm would consist of the following steps:

Find the address of the node by traversing the tree up.
Find the address of the neighbor. This part is described above.
Find the neighbor by traversing the tree down.

These steps are straightforward generalizations of the algorithm described in the link.


Semantic readings of the Lambek sequent calculus I am reading Categorial Grammar: Logical Syntax, Semantics, and Processing by Glyn Morrill and I am stuck with the Fig. 3.9:

Can someone explain this set of formulas and |.| function specifically?

This figure displays the definition of the |.| function that maps some proof (of some formula) in Lambek calculus (as fragement of intuitionistic logic) into lambda-term (by Curry-Howard correspondence there is correspondence between proof in some logic and terms in lambda calculus). I understand Lambek calculus and lambda calculus but I can not understand this picture? It is said in this book, tht |.| function is applied to proof, but this picture say something different - this function is applied to proof rules, that is completely different structure. What does small indices mu(ni, psi) and so on mean?

This was very good book up to this chapter, I am completely lost.

What constitutes a proof in a system like this is a derivation which is a tree of rule applications. The above translation function is defined by (structural) recursion over that tree. Note, this is why it labels the premises in the rules with $\delta$. This is intended to be mnemonic for "derivation".

I'm guessing but $\mu$ and $\nu$ appear to need to be sequences of lambda terms, while $\phi$ is a specific lambda term (or, equivalently, a single element sequence of lambda terms). $\Gamma$ is a sequence of formulas, and $\mu$ has a lambda term for each element of that sequence. Constructs like $x,\mu$ correspond to sequence extension, extending the sequence $\mu$ with the (particular) lambda term $x$ on the left, symmetrically for $\mu,x$. The parenthesis notation, e.g. $\Gamma(C)$ and $\mu(\dots)$ correspond to (consistently) operating on an element at an arbitrary location in the sequence.

So, for example, an instance of the $\bullet R$ case would look like:
$$\left|\cfrac{\cfrac{\delta}{X,A,B,Y,Z\Rightarrow W}}{{X,A\bullet B,Y,Z\Rightarrow W}}\right|_{t_X,t_{AB},t_Y,t_Z} = \left|\cfrac{\delta}{X,A,B,Y,Z\Rightarrow W}\right|_{t_X,\pi_1(t_{AB}),\pi_2(t_{AB}),t_Y,t_Z}$$

A translation of a complete derivation would look like: $$\begin{align}
\left|\cfrac{\cfrac{A\Rightarrow A \qquad B \Rightarrow B}{A,B\Rightarrow A\bullet B}}{\cfrac{A\Rightarrow (A\bullet B)/B}{\Rightarrow ((A\bullet B)/B)/A}}\right|
& = \lambda a\left|\cfrac{\cfrac{A\Rightarrow A \qquad B \Rightarrow B}{A,B\Rightarrow A\bullet B}}{A\Rightarrow (A\bullet B)/B}\right|_a \\
& = \lambda a\lambda b\left|\cfrac{A\Rightarrow A \qquad B \Rightarrow B}{A,B\Rightarrow A\bullet B}\right|_{a,b} \\
& = \lambda a\lambda b(\left|A\Rightarrow A\right|_a, \left|B \Rightarrow B\right|_b) \\
& = \lambda a\lambda b(a, b)
\end{align}$$


Universal binary rewriting system What is the simplest example of a rewriting system from binary strings to binary strings

$$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$

that can perform universal computation? Binary string rewriting systems in general can compute any computable function, but I have trouble finding particular instances that can by themselves compute any computable function given an appropriate input.  I've seen statements that a class of rewriting systems (e.g., the set of cyclic tag systems) is Turing-complete, but I'm looking for a single rewriting system that is universal.

I was thinking a self-modifying bitwise cyclic tag system might be a candidate, but I'm not sure how to interpret the output of such a system.

Rule 110 is a binary rewriting system that can perform universal computation, i.e., it has been proven to be universal.  It can be implemented by a finite-state transducer: it needs only finite state.

However, Rule 110 is not a tag system or a cyclic tag system, so this does not provide an instance of a specific binary tag system that is known to be universal.  It might be that examining the proof of universality of Rule 110 could yield such a system, as apparently the proof involves a reduction that goes by way of cyclic tag systems -- though personally I've never read the proof, so this is only speculation.

A side note: From Rule 110, you can construct a particular queue automaton that is universal: the queue alphabet is $\{0,1,\$\}$ and contains the state of the cellular automaton (a binary string representing the contents of each cell, followed by $\$$).  I don't know whether it'd be possible to use this to construct a specific tag system that is universal (e.g., if you can find a way to use a tag system to emulate a queue automaton).


Does the Hack computer from "The Elements of Computing Systems" use Von Neumann architecture? I'm reading "The Elements of Computing Systems" (subtitled "Building a Modern Computer from First Principles - Nand to Tetris Companion) by Noam Nisan and Shimon Schocken.

Chapter 4 is about machine language, and more specifically the machine language used on their computer platform called Hack. Section 4.2.1 says this about Hack:

  The Hack computer is a von Neumann platform. It is a 16-bit machine, consisting of a CPU, two separate memory modules serving as instruction memory and data memory, and two memory-mapped I/O devices: a screen and a keyboard.
  …
  The Hack programmer is aware of two distinct address spaces: an instruction memory and a data memory. … The CPU can only execute programs that reside in the instruction memory. The instruction memory is a read-only device, and programs are loaded into it using some exogenous means.

With that distinction between instruction memory and data memory, is it really a von Neumann architecture? According to my understanding of the difference between von Neumann and Harvard, that description sounds much more like a Harvard architecture.

I had the same suspicion going through the Nand to Tetris course.
Indeed, if you look at John K. Bennett's annotated version of "The Elements of Computing Systems", specifically Chapter 5, he calls this out:

The Hack architecture would more properly be called a “Harvard Architecture,” since the data and instruction memories are separate.

We can also do some digging for ourselves.
If we consult Wikipedia, it states that the Harvard architecture is distinguished by:

The term "von Neumann architecture" has evolved to mean any stored-program computer in which an instruction fetch and a data operation cannot occur at the same time because they share a common bus.
The design of a von Neumann architecture machine is simpler than a Harvard architecture machine—which is also a stored-program system but has one dedicated set of address and data buses for reading and writing to memory, and another set of address and data buses to fetch instructions.

The latter is indeed the architecture of the Hack machine, which has two separate memories and can do an instruction lookup, data lookup, and computation all in one step* of the CPU. You can see this in the book's diagram:

Last, this is also explicitly stated at the end of Chapter 5 of the original book:

Unlike Hack, most general-purpose computers use a single address space for storing both data and instructions. In such architectures, the instruction address as well as the optional data address specified by the instruction must be fed into the same destination: the single address input of the shared address space. Clearly, this cannot be done at the same time.... In contrast, the Hack architecture is unique in that it partitions the address space into two separate parts, allowing a single-cycle fetch-execute logic.

*Note: In the Hack machine language, it actually takes two steps (e.g. @dataaddr then D = M + 1) to do an operation on data in memory. However, during the second instruction, both the instruction and the data in memory can be read by the CPU simultaneously.


I need to prove Prove that the language L = {w | number of 11s in w is more than the number of 010s} is context free How would you go about proving that this Language is Context free.  I'm having issues with drawing the PDA for this.

I need to prove Prove that the language L = {w | number of 11s in w is more than the number of 010s} is context free.

I so far assume that when a string of 11s occur add x to the stack and when 010s add y to the stack, but I'm having issues drawing that part out the part were you check to see if the number of x's in the stack is greater then the number of y's.

Update based on GoodDeeds answer, just need to clearify something
Basic PDA Input, Pop -> Push

"Whenever a 11 is encountered, and the top of the stack is not a y, push an x. Else, pop a y."

So in this case whenever a 11 is encountered do I draw out the transition like example A or B?

Sketch of an answer:

As you suggested, use the states of the PDA to check when a $11$ or a $010$ has been found. Then, instead of keeping track of the number of $11$s and $010$s separately, keep track of the difference in their numbers.

You could have some symbol in the stack initially, say, $\$$, to mark that the stack is empty. Then, use a symbol $x$ to denote $+1$ in the difference, and $y$ to denote $-1$ in the difference.

Whenever a $11$ is encountered, and the top of the stack is not a $y$, push an $x$. Else, pop a $y$.

When a $010$ is encountered, if the top of the stack is not an $x$, push a $y$. Else, pop an $x$.

Thus, at any given point, the stack consists entirely of $x$s or entirely of $y$s, or only the $\$$. The number of $x$s denotes how many more $11$s have been encountered as compared to the number of $010$s, and vice-versa.

At the end of the input, accept if the top symbol is an $x$, as this would mean that the number of $11$s were more than the number of $010$s.


Efficient formulation for binary integer linear programming Problem:

There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either:

nothing, or
1 S, or
1 B, or
2 S, or
2 B, or
1 B and 2 S

We are given the weight (float not integer) of each ball (in array $w$). There are some constraints on the weights of the boxes and balls:

The total weight of a box $ \leq T$
In configurations 4 and 6 above, the difference of S should be $ \leq D$
In configuration 6 above, the weight of 2 S should be $\geq$ weight of 1 B

Now I want to minimise the number of boxes used.

My approach

I have modelled this as a linear programming problem with binary variables.

Let there be $M$ boxes, $N_S$ small balls and $N_B$ big balls.

Decision variables:

$b1_j$ is a binary variable which is $1$ if box $j$ is in configuration $1$, else $0$. Similarly for $b2_j, b3_j, b4_j, b5_j, b6_j$ for each box $j$.
$x_{ij}$ is a binary variable which is $1$ if ith big ball is in box $j$, else $0$.
$y_{ij}$ is a binary variable which is $1$ if ith small ball is in box $j$, else $0$.

Constraints:

Total weight of any box $\leq T$
$$\sum_{i}x_{ij}w_i + \sum_{i}y_{ij}w_i \leq T \qquad \forall \, j$$
Weight difference constraint:
$$y_{ij}w_i-y_{kj} w_k \leq D \qquad \forall \, i,j,k$$
Each ball used exactly once:
$$\sum_{j}x_{ij}=1 \qquad \forall \, i$$
$$\sum_{j}y_{ij}=1\qquad \forall \, i$$
Each box is exactly one configuration:
$$b1_j+b2_j+b3_j+b4_j+b5_j+b6_j=1$$
Similarly for other constraints. I hope you get the way I am trying to solve this.

Now the problem is this approach is taking a lot of time to solve using PuLP. For just 15 balls and 10 boxes it took minutes and time is increasing exponentially as the balls increase. I want to solve this for at least 100 balls.

Any help would be appreciated.

Integer linear programming

Let me suggest another way of formulating this with ILP that might be worth trying.  Define combination to mean a list of all of the balls in a single box.  For instance, the combination might be (7,15) meaning that the box contains ball 7 and ball 15.  Of course, we can enumerate all legal values for the combination, i.e., for the contents of a single box.  There will be at most $1+N_S+N_B+N_S(N_S-1)/2+N_B(N_B-1)/2+N_B N_S(N_S-1)/2$ different combinations (fewer in practice due to the constraints on the difference of weights and the total weight of a box).

Now introduce a binary variable $x_{ij}$ that is 1 if the $i$th box contains combination $j$.  Here $j$ is an index that ranges over all possible legal choices for the combination, i.e., for the contents of a single box.  (Don't include any illegal combinations.)

We get some linear inequalities from this:

For each box, we must select one combination for it to contain: $\sum_j x_{ij} \le 1$.
Each ball must be used exactly once: $\sum_i \sum_{j \in B_k} x_{ij}=1$, where $B_k$ is the set of legal combinations that include ball $k$.

Now you can test feasibility, i.e., test whether it is possible to pack all of the balls into some given number of boxes.

For example, suppose we have 5 big balls and 10 little balls and 10 boxes.  Then there will be at most about 300 legal combinations (probably fewer), so there will be about 3000 binary variables.  I don't know whether PuLP will be effective, but you could give it a try.

Exact cover

Even better yet, one can note that your problem is an instance of the exact cover problem.  The universe is the set of balls; each combination is a subset of the universe; and we want to find a way to cover the universe by a disjoint union of the combinations.

There are dedicated algorithms for the exact cover problem that might be faster than expressing this as an integer linear program and applying an ILP solver.


Why did Google not use an NP problem for their quantum supremacy experiment? Reading discussions of the recent quantum supremacy experiment by Google I noticed that a lot of time and effort (in the experiment itself, but also in the excellent blog posts by Scott Aaronson and others explaining the results) is spent on verifying that the quantum computer did indeed compute the thing we believe it to have computed.

From a naive point of view this is completely understandable: the essence of any quantum supremacy experiment is that you have the quantum computer perform a task that is hard for a classical computer to achieve, so surely it would also be hard for the classical computer to verify that the quantum computer did complete the task we gave it, right?

Well, no. About the first thing you learn when starting to read blogs or talk to people about computational complexity is that, counter-intuitive as it may seem, there exist problems that are hard to solve, but for which it is easy to verify the validity of a given solution: the so called NP problems.

Thus it seems that Google could have saved themselves and others a lot of time by using one of these problems for their quantum supremacy experiment rather than the one they did. So my question is why didn't they?

An answer for the special case of the NP problem factoring is given in this very nice answer to a different question: https://cs.stackexchange.com/a/116360/26301. Paraphrasing: the regime where the quantum algorithm starts to out perform the best known classical algorithm starts at a point that requires more than the 53 qubits currently available.

So my follow-up question is: does this answer for the special case extend to all NP-problems where quantum speedups are expected or is it specific to factoring? And in the first case: is there a fundamental reason related to the nature of NP that quantum-supremacy 'kicks in later' for NP problems than for sampling problems or is it just that for NP problems better classical algorithms are available due to their being more famous?

there exist problems that are hard to solve, but for which it is easy to verify the validity of a given solution: the so called NP problems.

This statement is wrong. There are many NP problems which are easy to solve. "NP" simply means "easy to verify". It does not mean hard to solve.

What you are probably thinking of is NP-complete problems which is a subset of the NP problems for which we have very, very good evidence to think they are hard. However, quantum computers are not expected to be able to solve NP-complete problems significantly more "easily" than regular computers.

Factoring is also thought to be hard, but the evidence for this is only "very good" and not "very, very good" (in other words: factoring is likely not NP-complete). Factoring is one of very few natural problems which falls in between not being NP-complete and not being easy.

The list of problems that we know that are easy to verify, easy to solve on a quantum computer but hard classicly, is even shorter. In fact, I do not know of any problem other than factoring (and the very closely related discrete logarithm problem) with this property.

Moreover, any easy to verify problem would likely have the same issue as factoring: $53$ qubits is not that many, and $2^{53}$ is huge, but just within reach of classical computing. $2^{53}$ less than $10^{16}$, and most classical computers can execute on the order of $10^9$ operations per second. We could run through all possibilities in about $1/3$rd of a year on a single classical desktop computer.

Quantum computers have very few applications which they're known to be good at, and are essentially useless for most hard NP problems.


Expressing pseudo-polynomial runtime solely in terms of the input size In case we have an algorithm which is pseudo-polynomial and runs in  $O(n^2C)$ for some $C$ that is encoded in binary. Is it correct to say that if $C=2^n$  then $O(n^2C)=O(n^22^n)$
and because $n=\log C$ we can write that $O((\log C)^22^n)=O(2^n)$ because $2^n$ grows more rapidly than $\log C$?

You are correct that the running time is $O(n^2 2^n)$, but according to the definition of big O, it is not the case that $n^2 2^n = O(2^n)$, since $n^2 2^n$ grows faster than $2^n$. What is true is that for every $\epsilon > 0$, $n^2 2^n = O((2+\epsilon)^n)$.

Often it is convenient to hide such "small" factors, and write $O(n^2 2^n) = \tilde{O}(2^n)$. The usual definition of $\tilde{O}(\cdot)$ is this: $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log g(n))^k)$. In practice this is almost always used when $g(n)$ is either a polynomial or an exponential. When $g(n)$ is a polynomial, $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log n)^k)$, and we say that $\tilde{O}$ hides polylogarithmic factors. When $g(n)$ is exponential (that is, $g(n) = e^{An^B}$ for some $A,B>0$), $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n) n^k)$, and we say that $\tilde{O}$ hides polynomial factors.


Chernoff-Hoeffding bounds for the number of nonzeros in a submatrix Consider a $n \times n$ matrix $A$ with $k$ nonzero entries. Assume every row and every column of $A$ has at most $\sqrt{k}$ nonzeros. Permute uniformly at random the rows and the columns of $A$. Divide $A$ in $k$ submatrices of size $n/\sqrt{k} \times n/\sqrt{k}$ (i.e. $\sqrt{k}$ meta-rows and meta-columns). Enumerate the $k$ nonzeros and define the following indicator random variable:

\begin{equation}
X_{\ell,z} =
\begin{cases}
1 & \text{if the $z$-th nonzero entry is in $A^\ell$} \\
0 & \text{otherwise}
\end{cases}
\end{equation}

The expected number of nonzero entries in a generic submatrix $A^\ell$ is one. Is it possible to prove Chernoff-Hoeffding bounds on the sum $X_\ell = \sum_{z=1}^k X_{\ell,z}$?

My first guess was to prove negative association, following Dubhashi and Panconesi analysis. Unfortunately, $X_{\ell,z}$ and $X_{\ell,z^\prime}$ are not negatively associated (following the book's notation, if $z$ and $z^\prime$ are in the same row/column then $\mathbf{E}[f(X_{\ell,z})g(X_{\ell,z^\prime})] > \mathbf{E}[f(X_{\ell,z})] \mathbf{E}[g(X_{\ell,z^\prime})]$).

Okay, here is a full answer.

We will use the fact, that any bipartite graph of maximum degree $d$ can be broken into (at most) $d$ matchings.

In our case, this means that we can split $A$ into (at most) $\sqrt{k}$ disjoint sets of elements $S_i\subseteq\{(i,j)\in[n]\times[n] \mid A_{i,j}=1\}$ of size at most $n$ such that any every element in each set has a unique row and column.
(This uses that a $1$ in $A$ can be seen as an edge in the $n\times n$ bipartite graph that is the matrix.)

Now let $X$ be the total number of $1$s in your $n/\sqrt k\times n/\sqrt k$ matrix, $A^\ell$, and let $X_i$ be the number of elements coming from $S_i$.
Then $X\ge t\implies \exists_i\, X_i\ge t/\sqrt k$ and so
$$\Pr[X\ge t]\le \sqrt k \Pr[X_1 \ge t/\sqrt k]$$
by the union bound.
Now, because elements in $S_1$ don't share any rows/columns, it is easy to analyze using your original approach.

In particular, reorder the rows and columns using the matching, so that the first element in $S_1$ is $(1,1)$ the next is $(2,2)$ and so on.
Let $r_i$ be the random variable that is 1 if row $i$ is chosen and $c_i$ likewise. Then we want to upper bound $\Pr[\sum_i r_ic_i \ge t]$.
Notice $E[r_ic_ir_jc_j] = E[r_ir_j]E[c_ic_j] \le E[r_i]^2E[c_i]^2$ by Maclaurin’s Inequality, so
$$\exp(t\sum_i r_ic_i) = \sum_k t^k/k!\,E\left(\sum_i r_ic_i\right)^k \le \sum_k t^k/k!\,E\left(\sum_i b_i\right)^k = \exp(t\sum_i b_i)$$
where $b_i$ is a normal binomial variable with $p=(n/\sqrt{k}/n)^2=1/k$.

Finally, we then get

$$\Pr[X\ge t]\le \sqrt k \Pr[X_1 \ge t/\sqrt k] \le \sqrt k \exp\left(-2\left(\frac{t-p n \sqrt{k}}{n\sqrt k}\right)^2 n\right)$$

or more simply

$$\Pr[X\ge \lambda\sqrt{nk}+n/\sqrt k]\le \sqrt k \exp(-2\lambda^2)$$

or if we use the Hoeffding bound for small values of $p$ (large $k$):

$$\Pr[X\ge \lambda\sqrt{nk}+n/\sqrt k]\le \sqrt k \exp\left(\frac{-\lambda^2}{2/k+\lambda/\sqrt n}\right)$$

Note that if we had simply assumed all elements were independent, we would have gotten the bound $\Pr[X\ge \lambda\sqrt{n\sqrt{k}}+n/\sqrt k]\le \exp(-2\lambda^2)$. Equal to ours except for a factor $k^{1/4}$ in the exponent.


Relational calculus to SQL I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a formula in relational calculus to an SQL query whose run on a database produces rows that make the original formula satisfiable. However, I cannot find any rules for such conversion and I would expect them to exist.

Is my understanding wrong? Where can I find these "conversion" rules? I am specifically interested in how to systematically (automatically) convert predicates involving existential quantifiers.

I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a formula in relational calculus to an SQL query ...

Why do people persist in this confusion? The semantics of SQL is different to Codd's Relational Model. Therefore no 'conversion' makes sense. Specifically:

Relations are sets vs SQL tables are multisets.
In Tuple Relational Calculus and Domain Relational Calculus, attributes are named, and that is the only way to access attributes vs SQL columns of an SQL table might or might not have names, might or might not have a unique name; can also be accessed by column position (under older SQL standards), and have an obtuse and incomplete algorithm for column positioning of query results.
For Relational Algebra, it gets messier: some versions (including in Codd 1972) access columns only positionally; some only by name.

The only formal conversion between any of these is given in Codd 1972 'Relational Completeness', where he uses conversion from TRC to Relational Algebra (not v.v.) to show the expressive completeness of (that version of) RA. (And actually, it's from his 'Alpha', which is an 'implementation' of TRC that was never implemented.)

  However, I cannot find any rules for such conversion and I would expect them to exist.

Please give some reference claiming they exist. The usual form of words is that SQL is "based upon" RA or TRC. That's not a claim of convertability, in either direction.

  I am specifically interested in how to systematically (automatically) convert predicates involving existential quantifiers.

Given some relation schema

S(SNO, SNAME, CITY, STATUS) with predicate 'Supplier identified by SNO is named SNAME, is located in CITY and has status STATUS',
a derived predicate 'exists STATUS s.t. Supplier identified by SNO is named SNAME, is located in CITY and has status STATUS'
is given by RA: pi(SNO, SNAME, CITY)(S).
That is, existentially quantifying an attribute is equivalent to projecting it away. "Projecting away" is also known as REMOVE or project ALL BUT.


Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() Why? I just found out by luck that

 Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min()

For example,
Consider a sorted array, {1 43 65 97 98 99 101}

Abs(1-43-55-97-98-99-101)= 101-1

Does anyone know why?

Thanks in Advance.

If you picture these as distances along a road, it should be very intuitive.

If (for example) you start at kilometer #7, then proceed through kilometers #45, #81, and #97, then the distances you travel are 45−7, then 81−45, then 97−81; and the total distance you travel is 97−7. Since the total distance is the sum of the individual distances, 97−7 = (45−7) + (81−45) + (97−81).

This only works for a sorted set, because otherwise you have backtracking, where you cover a certain distance and then "un-cover".


How 'Avalanche Effect' got its name? I wonder how or why Avalanche Effect got its name.

Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (for example, flipping a single bit), the output changes significantly (e.g., half the output bits flip).
(source: Wikipedia)

But I feel like this definition has nothing to do with its name. If I asked what is avalanche/snowball effect, I would probably think of something which starts small but exponentially grow out of control.

The term first described by Horst Feistel (1973)

As the input moves through successive layers the pattern of 1's generated is amplified and results in an unpredictable avalanche.

It is rather very good naming. Consider a bit flip in the AES's input; It enters the first Sbox, then according to the design of the Sboxes of AES the output is different since they are invertible (actually they are also designed to have avalanche effect). Now say we have at least two different output bits, then the Sub-Bytes and MixColums will distribute the changes. Therefore in the first round, you will have 2 changes, in the next round you will have 4,.. and so on. As you can see the minimum change becomes larger and larger in each round. That is how an avalanche is working.
Note that we have $2^{10}$ changes in the last round for AES-128. Contradictory, no, since some changes will cancel each other and that part together with the key's action is unpredictable for our computing capabilities!
The blow picture was drawn by Feistel, which should tell the idea; One small change at the beginning and it is a big effect on the output.


Is there a set of NP-hard problems that are most commonly used for proving NP-hardness? Are there any NP-hard problems that are considered kind of the standard for reductions? There's so many but it feels like some come up more often than others (for example Vertex Cover, Independent Set, 3-SAT, etc.). I'm sure people just pick whatever is most convenient, but where's the boundary between "more useful" and "too obscure" when choosing a problem to reduce from?

Most textbooks will have a set of 'core' NP-Complete problems from which all their examples and exercises would reduce from, which are probably the ones you list (3SAT, Vertex Cover, Independent Set, Clique, k-Coloring, Set Cover, Dominating Set, Hitting Set, Subset Sum, Knapsack.)

A bigger set of 'standard' problems would be Garey & Johnson's book. Beyond that, people look at hard restrictions of the standard problems (i.e. k-coloring for k=3, Exact Cover version of set cover, not-all-equal 3SAT, etc).

Beyond that, it gets fairly domain specific.


Calculating gradient in a neural net using batches I am a CS student learning about neural nets. Currently I am confused about how to train a neural net in batches. If I calculate error in a batch, I will get a vector of errors e.g. real1 - predicted1, real2 - predicted2, etc... How do I then calculate a single gradient value to adjust the weights with?

This is known as stochastic gradient descent.  I suggest you read some background material on stochastic gradient descent; then I think you will understand.  There is lots written on that subject in many standard places.

Compare:

In standard gradient descent, we let $E(w)$ denote the total error across all training samples (as a function of the weights $w$), compute the gradient of $E(w)$ (with respect to $w$), and use that gradient to update the weights.
In stochastic gradient descent (in its simplest form), we pick a single training sample at random, let $E_1(w)$ compute the error on just that training sample (as a function of the weights $w$), compute the gradient of $E_1$ (with respect to $w$), and use that to update the weights.  We repeat this many times.  In each iteration, we pick a different randomly chosen training sample.

$E_1(w)$ can be thought of as a noisy approximation to $E(w) $, so the gradient of $E_1(w)$ can be thought of as an approximation to the gradient of $E(w)$.  Thus, in each iteration of stochastic gradient descent, we are moving in a direction that is roughly correlated with the direction standard gradient descent will take, but with some noise; over enough iterations, hopefully this noise will average out.  A crude intuition might be that $kn$ iterations of stochastic gradient descent are roughly comparable to $k$ iterations of standard gradient descent, if $n$ is the number of samples in the training set.
Stochastic gradient descent with batches is a more sophisticated form of stochastic gradient descent, where we randomly choose a batch of training samples (more than one sample, but less than all of them), sum the total error across the batch, compute the gradient, and use that to update the weights.


Comparing the big-$O$ of these four functions Sometimes you can substitute values for $n_0$ and $c$ in the big-$O$ equation and compare two functions. Or take limits and compare two functions.
But for the following functions, for example, taking the limit in infinity for
$f_3$ over $f_2$ requires using l'Hôpital's rule which doesn't simplify anything. $f_3$ is technically the product of a polynomial and an exponential function. And I don't know how to go with comparing functions like that with others.
Firstly, I know that $f_4$ is the most efficient because it is $O(n^2)$. ($f_4(n) = n + \frac{n(n + 1)}{2}$) and the rest are exponential.
But for the rest, I really don't know what to besides using my intuition which could be really far from the correct answer anyway. Please help me compare these rigorously.
$f_1(n) = n^{\sqrt{n}}$
$f_2(n) = 2^n$
$f_3(n) = n^{100}2^{\frac{n}{2}}$
$f_4(n) = \Sigma_{i=1}^{n}i + 1$

One useful technique for comparing functions asymptotically is to take their logs since doing that turns exponentials into polynomials. So, if you are comfortable with comparing polynomials, then taking logs is always something you should be thinking about.
There is one thing that you have to be careful of when you do that, however. After taking logs, you can not throw away constant factors anymore.
If you take the logs of your functions, you get $\log(f_1(n))=\sqrt{n}\log(n)$, $\log(f_2(n))=n\log(2)$ and $\log(f_3(n))= 100\log(n)+\frac{n}{2}\log(2)$. So, $f_2$ is asymptotically larger than $f_3$ which, in turn is asymptotically larger than $f_1$. You already know where $f_4$ goes.


General resolution in first order logic Assuming you have a formula in first order logic like

    $$(\forall_x p(x) \land \forall_x q(x)) \rightarrow \forall_x(p(x) \land q(x))$$
    (which seems valid?)

Converting the formula to CNF:

  $$(\neg p(x) \vee \neg q(y) \vee p(z)) \land (\neg p(x) \vee \neg q(y) \vee q(z)) $$

I don't see how I can apply general resolution to get the empty clause in this case which puzzles me since I believe the formula is valid.

As you correctly point out, the original formula is valid (in every model either there is some element for which p or q doesn't hold, or p and q hold for all elements).

To prove that your formula is valid, you cannot use resolution directly. Recall that with resolution, you can derive the empty clause from a clause set iff the clause set is unsatisfiable. Your formula is valid iff its negation is unsatisfiable. So to prove your formula is valid, you have to derive the empty clause from the clause set corresponding to the negation of your formula.

Let $\varphi$ be your original formula. $$\lnot \varphi \equiv \forall_x \forall_y \exists_z (px \land qy \land (\lnot pz \lor \lnot qz))$$
Skolemization replaces $z$ by a function symbol $f(x,y)$:
$$\lnot \varphi \equiv_{SAT} \forall_x \forall_y (px \land qy \land (\lnot pfxy \lor \lnot qfxy))$$
The corresponding clause set:
$$\{\{px\},\{qy\},\{\lnot pfxy, \lnot qfxy\}\}$$
From there it should be straight-forward to derive the empty clause:

Apply renaming $\nu_1 = \{x/x_1\}$ to $\{px\}$, yielding $\{px_1\}$, then
resolve $\{p x_1 \}$ with $\{ \lnot pfxy, \lnot qfxy\}$ by $\sigma_1 = \{ x_1 / fxy\}$, yielding $\{\lnot q fxy\}$
Apply renaming $\nu_2 = \{y / y_1\}$ to $\{qy\}$, yielding $\{qy_1\}$, then resolve $\{qy_1\}$ with $\{ \lnot qfxy \}$ by $\sigma_2 = \{y_1/fxy\}$, yielding the empty clause $\Box$

In conclusion, we have shown by resolution that $\lnot \varphi$ is unsatisfiable. Therefore $\varphi$ is valid.


Shannon's entropy for an image Shannon's entropy [plog(1/p)] for an image is a probabilistic method for comparing two pixels or a group of pixels.Suppose an image with a  matrix of 3x3 has pixel intensity values

1 1 2
2 3 3
4 4 5

and another image with 3x3 matrix has group of pixels having intensity values

5 5 6
6 7 7
8 8 9

Then shannon's entropy for the images would be the same.So in this case the entropy values would point out that the images are same though in actual they are different.So image matching using this technique doesn't help.On basis of supervised classification where I classify an image based on trained databases of shannon's entropy ,we use the concept of entropy to find similarity between two images.Is there any method or research paper where this entropy can be used or modified for image matching for the above case..?

Shannon's entropy works as a hashing or fingerprinting function here; they are not injective which means we have to be careful not to interpret too much into relations of values.

If $H(I_1) \neq H(I_2)$, then images $I_1$ and $I_2$ are certainly not the same.

If $H(I_1) = H(I_2)$ (or even $H(I_1) \approx H(I_2)$), however, we know nothing. The images might be similar, but the values can also be close because of non-injectivity.

We would like to have some smoothness, that is that two images are more different if $|H(I_1) - H(I_2)|$ is larger. Whether this is the case is certainly a quality criterion of such fingerprinting functions. Given your example, it does not seem as if entropy was a good fingerprint in this sense.

It would be confusing if any kind of entropy would be. Any rectangle of one color holds no information (entropy zero), yet two rectangles of different colors are as different as two images get.


An algorithm to find the maximum profitable assignment Given a set of workers $w_1,...,w_m$ and and a set of tasks $t_1,...,t_n$, and a  $m\times n$ matrix $P$ s.t. $P(i,j)$ is the profit of assigning worker $i$ to task $j$. One worker can only be assigned to one task, and one task can only have one worker. We want to find the maximum profit of all possible assignments.

Does anyone knows an algorithm or approach that can efficiently solve this problem and help provide a name or reference? Thank you.

Your problem is known as the assignment problem.


Prove that any algorithm that has sublinear time have a constant time complexity? This exercise is taken from Goldreich's textbook of "Computational Complexity - A Conceptual Perspective", first ed., p.140.

Exercise 4.3: Referring to any reasonable model of computation and assuming that the input length is not given explicitly, prove that any algorithm that has sub-linear time complexity actually has constant time complexity?

Here is the note given by Oded:

Guideline: Consider the question of whether or not there exists an infinite set of strings S such that invoked on any input $x \in S$ the algorithm reads all of x. Note that if S is infinite then the algorithm cannot have sub-linear time complexity, and prove that if S is finite then the algorithm has constant time complexity.

For definition of sublinear time, see here.
This is how I show it: Since we strictly read less than the size of the input |x|, then it is necessarily that we read some of the input, let's say 1, 2, ..., k where k < |x|. Since k is not part of the input, therefore time complexity of this algorithm is O(1). Is my conclusion right? If not, then why?
As you notice, I didn't use the hint since I didn't know how to show if S is finite, then the algorithm has a constant time.

I think to make this work we need to work in a model of computation where the input string is read sequentially. That is, in order to read the $i$'th character of the input string $S$, we first need to read characters number $1,2,\ldots,i-1$. In what follows I also assume that every substring of a valid input is a valid input (this in particular implies the fact that the length of the string cannot be explicitely encoded in, say, the first $O(\log n)$ bits of the input).
Let $S$ be the set of strings such that invoked on any input $x\in S$ the algorithm $A$ reads all of $x$. As the guideline suggests $S$ must be finite, as otherwise $A$ cannot be sublinear.
Now, let $k$ be the length of the longest string in $S$. I claim that $A$ never reads more than $k$ characters of its input. Indeed, suppose there is some input $x$ such that $A$ reads $k'>k$ characters when invoked on $x$. Let $y$ be the string consisting of the first $k'$ characters in $x$ (this is where I use the assumption that every substring of a valid input is a valid input). Because $A$ reads only the first $k'$ characters when invoked on $x$ it cannot distinguish between $x$ and $y$. In particular, it also reads all $k'$ characters when invoked on $y$. Thus, $y\in S$ and $y$ is of size $k'>k$, which contradicts the definition of $k$. We conclude that our assumption was wrong, and $A$ never reads more than $k$ characters of its input.
Because $A$ never reads more than $k$ characters of the input, it has a finite (constant) number of distinct possible executions. Thus, its worst-case time-complexity is also constant.
(I implicitly assumed a deterministic model of computation here, but it isn't hard to make the argument work under the presence of randomness, both for worst-case and expected time-complexity)


Problem class of assigning N persons to N tasks, zero costs with prefs I am looking for the general problem class / computational complexity / algorithms for the following problem:

N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice versa. There is a binary preferences matrix whose (i,j) entry is 0 if person i can not do task j, and 1 if it can.

There are no costs involved, no weights and the number of tasks equals the number of people.

I was searching for it but all I could find was the Assignment Problem which has costs/weights associated with each assignment.

As a last resort, perhaps I can transform my preferences matrix to a cost matrix if person can not do job then cost is infinite else cost is zero?

This problem is known as maximum matching of a bipartite graph.
Basically let vertex $p_i$ (resp., $q_i$) represent the $i$th person (resp., task).
And we connect $p_i$ and $q_j$ with an undirected edge iff person $i$ can do task $j$.
The answer of the original problem is exactly the maximum matching of the new graph.

For algorithms, the classical Hungarian algorithm, of complexity $O(n^3)$, is a nice choice. Certainly you can reduce this problem to network flow, and then apply any max-flow algorithm.
If you are looking for some "advanced" choices, refer to Wikipedia.


Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem? I read a theorem which states that:
If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant performance ratio r, then NP = P.

But I never understood the reasoning behind this!!

In fact, something stronger is true: if you can approximate maximum clique within $n^{1-\epsilon}$ for some $\epsilon > 0$ then P=NP. This is because for every $\epsilon > 0$ there is a polytime reduction $f_\epsilon$ that takes an instance $\varphi$ of SAT and returns an instance $(G,cn)$ of maximum clique such that:

If $\varphi$ is satisfiable then $G$ has a $cn$-clique.
If $\varphi$ is not satisfiable then $G$ has no $cn^{1-\epsilon}$-clique.

If you could approximate maximum clique within $n^{1-\epsilon}$ you would be able to distinguish the two cases (exercise), and so to decide whether $\varphi$ is satisfiable or not.

The reduction uses the PCP theorem as a first ingredient. Given the PCP theorem it is not hard to give a similar reduction with a constant gap, and with some effort to give a reduction with a gap of $n^\epsilon$ for some $\epsilon > 0$. The reduction claimed above, which has a gap of $n^{1-\epsilon}$ for every $\epsilon>0$, is much harder. See lecture notes of Guruswami and O'Donnell for the constant gap, and lecture notes of Scheideler for the $n^\epsilon$ gap.


Evaluating Grover's algorithm on 3-SAT I recently asked this very similar question on how Grovers algorithm must be modified in order to solve 3-SAT and learned that it actually needs no modification at all.

However, what I still don't get is how to determine whether a satisfying variable assignment was found after having applied Grover's algorithm. The final step (as described in wikipedia) is to measure $λ_ω$ which in the case of solving 3-SAT would give me an assignment for the variables of my formula. Do I need to check manually whether this assignment is indeed a satisfying assignment? Or is there any better way to find out whether there exists at least one match?

"Measuring", in quantum computation, is the act reading the quantum state along some basis. This will cause the the quantum state to collapse. The quantum state after grovers algorithm is such that it collapses with very high probability to the desired result (in this case an assignment). Perhaps you should check the result because it might just be a bad case, that is just unlikely, but you don't have to check the result to get the output of grovers algorithm. You just have to measure it. To determine with high probability weather or not the formula was SAT you should check the assignment that it gave out.


If a CSP (over a finite domain) has only linear inequalities as constraints, is it solvable in linear time? I have an optimization problem in fuzzy logic that I want to model and solve as a CSP. If I could use only linear inequalities in my encoding, is the resulting CSP solvable in linear time?

Problem statement: Given a set of formulas in CNF in Łukasiewicz logic, I want to find an assignment for the variables in some truth set T_k, for some k, such that the assignment maximizes the number of satisfied formulas. I wanted to model this problem into CSP or SAT, hence my question. The SAT problem for CNF Łukasiewicz logic formulas is solvable in linear time. So, maybe we can take advantage of that.

Probably not, since clauses can be encoded using only linear inequalities.
http://web.stanford.edu/~rrwill/cnf-sat-feasible.pdf


Ambiguous Grammar demostration exercise Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows:

$$S \rightarrow aT | bR$$
$$R \rightarrow a | aS | bRR$$
$$T \rightarrow b | bS | aTT$$

Thanks!

An example is the word $aabbab$.

We can either create it like this
$$S \rightarrow aT \rightarrow aaTT \rightarrow
 aabST \rightarrow aabbRT \rightarrow aabbaT \rightarrow aabbab.$$
Or like this
$$S \rightarrow aT \rightarrow aaTT \rightarrow
aabT \rightarrow aabbS \rightarrow aabbaT \rightarrow aabbab.$$


The meaning of 'Pool' in Computer Science While reading about SIMD on Wikipedia, I noticed the use of the technical term Pool in the figure below:

I didn't know what it means; so after searching for it, I found only this article. Yet the definition wasn't very clear to me:

  In computer science, a pool is a set of resources that are kept ready
  to use, rather than acquired on use and released afterwards. In this
  context, resources can refer to system resources such as file handles,
  which are external to a process, or internal resources such as objects

This is not the first time since I have seen the term - I found it on other CS-related materials in the past as well.

Does anyone have any idea about the meaning of 'Pool' in CS? or can provide any reference?

A pool is basically some grouping.  It's kinda vague.
In that figure, the "data pool" is just some set of data while the "instruction pool" is just some set of instructions.  The figure means to show that a single instruction and multiple data go into the vector unit at a time, and then that single instruction is applied to each of the multiple data independently.

On the "pooling" design strategy
I clicked the link to "Pool (computer science)", Wikipedia.  That article's worded a bit confusingly because it's talking about a design strategy called "pooling" rather than discussing the term "pool" itself.
Pooling is when a resource is collected up into a pool for some reason.  Because it's such a vague term, it can apply in a lot of different situations, so it's hard to give a more specific description without overstating it.
But to give a common example, there's thread pooling in which a bunch of threads are kept alive-and-waiting to do jobs.  This pattern's often useful when you might have a bunch of little jobs that you want to run on different CPU cores.  Then, whenever you want to run a job, you pick an available thread from the thread pool and have it run the job.
In principle, you don't actually need a thread pool; you could instead create a new thread each time you want to run a new job.  The problem's that threads can be expensive to create and dismiss, so if you're running a bunch of little jobs, it's often highly inefficient to keep creating/releasing threads.
That said, "pooling" is unrelated to what the SIMD diagram was referring to as a "data pool" and "instruction pool".  In that diagram, they just meant that they had a bunch of things data and instructions to use on them, which they vaguely referred to as existing in pools.


Assignment problem with no cost I have a problem that I was able to conceptualize as following:
Problem
We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination of these people, I want to check if it is a diverse group.
A diverse group is a group that satisfies several requirements, each requirement is of the form "at least $k_i$ persons in the group belong to subset $S_i$". Here is the tricky part, one person can only be used to satisfy one requirement. As in, you can't use him/her for multiple requirements.
Example:
Given:
At least two people from Hispanic= {a,b,c}
At least two people from African={a,d,e}
Is the group {a,c,d} a diverse group?
The group {a,c,d} is not diverse because you cant count a as Hispanic and African. But, the group {a,c,d,e} is diverse because we have two Hispanics a and c and two African d and e.
Attempt:
I think this is an instance of the Assignment problem. The jobs are the ethnicity and we can put as many ethnicity as the requirement dictate. For example, if we need two Hispanic, then we put two Hispanic jobs. However there only some people are able to do a particular job. Is there a name for such a problem? any algorithms somewhere in the internet? If not how would the implementation look like?
This is my attempt so far:
I will construct a bipartite graph with the set of people $P$ on one hand and the set of ethnicity on the other $S$. We will put an edge between a person $p_i$ and an ethnicity $S_i$ if he/she belongs to the ethnicity.
Now, we will modify the graph, for every ethnicity $S_i$ duplicate it $k_i$ times ($S_{i,1}, S_{i,2}, ... , S_{i,k_i}$). And add new edges accordingly. Find the maximum matching M of this graph.
Now, merge the $S_{i,j}$s into one $S_i$ and there you have a diverse group. However, a maximum matching is only a possible solution to to the problem. And my problem is a decision problem, I want to check if a given group is a solution or not.

Let $P$ be the set of people and $\mathcal{S}$ be the modified multi-set of subsets. By checking if an $\mathcal{S}$-saturated matching into $P$ exists (i.e. Hall's condition) you are indeed finding a diverse group. If you are checking that some group $P$ is a putative solution the procedure is the exactly the same.

This can be done quickly via the Hopcraft-Karp algorithm (as you don't have weights over edges) or by implementing this as a Max-flow LP and using a solver. I'm willing to bet the solvers will work much faster in practice.


Maximizing length of subsequence Given a sequence $(a)$ of lenght $n$, such $a_1 = a_n = 1$ and $a_i \in \left \{ -1, 1 \right\}$.

We want to find a subsequence $(b) \subset (a)$ which statisfies the following conditions:

The length of $(b)$, (let's call it $k$) is the largest possible
$b_k = b_1 = 1$
Each prefix sum $b_1$, $b_1+b_2$,  $b_1+b_2 + b_3,\ \ldots\ , b_1 + b_2 + \ldots + b_k$ is $\geq 0$.
Each suffix sum $b_k$, $b_{k} + b_{k-1}, b_{k} + b_{k-1} + b_{k-2}, \ \ldots\ , b_k + b_{k-1} + \ldots + b_1$ is $\geq 0$.
Sum of $(b)$ is the biggest possible.

Is it possible to construct linear algorithm to solve it?

Yes.

Let $c_0 = 0$ and $c_i = \sum_{j=1}^i a_i$, (which can be done in linear time).  Now the problem becomes -- find $0\le i < k\le n$ such that for all $i\le j<k$ we have $c_i\le c_j \le c_k$ that maximizes $k-i$.  This can be found in a single sweep. (I'll let you work out the details.)

For the problem actually asked:  We want the longest subsequence that begins and ends with 1 and each of the prefix and suffix sums is nonnegative.  First note that all $a_i=1$ are included as including it will only increase the prefix and suffix sums.  In particular $b_1=a_1$ and $b_k=a_n$.  We can construct $(b)$ in two passes.  First pass from $i=1$ to $n$ selecting every $a_i$ such that either $a_i = 1$ or $a_i=-1$ and the prefix condition is not violated in our subsequence (we are greedily selecting everything subject to the prefix condition).  Now pass backwards through the subsequence discarding elements that violate the suffix condition.

Note that since all of the $a_i=1$ are in $(b)$ the sum of $(b)$ is just the count of $a_i=b_j=1$ minus the count of the $b_j=-1$ and so is twice the count of $a_i=1$ minus the length of $(b)$, a function of the length.  So any other subsequence satisfying the conditions having the same length will have the same sum.


Can a RAM calculate its own Gödel number? You can get the Gödel number of a RAM by making it a list of commands and making this list an integer.

So, what I thought is something like "The RAM that would return its own Gödel number (say, $x$) would have to have the information $x$ in it, so the integer would be greater than $x$, so it would not return its own Gödel number."

But then I noticed that for specific numbers you could do compressing, such as calculating $10^{9999}$ instead of writing 100000...000 in the code of the RAM. Probably the Gödel number would not be $10^{9999}$ though, but at least it could be.

Question: Is there a RAM that calculates its own Gödel number? Can there be such?

Consider the computable function $Q\colon \mathbb{N}\times\mathbb{N}\to\mathbb{N}$ given by $Q(x,y) = x$.  By Kleene's second recursion theorem, there is some $p$ such that the program with Gödel number $p$ computes the function $f(y) = Q(p,y)=p$, i.e., a program which outputs $p$ for every input. This is exactly the program you're looking for: for any input, it outputs its own Gödel number.

Such a program is known as a quine, and they exist in any Turing-powerful model of computation.


Example of tree with > 6 vertices, tree would have depth = n after splay() deepest vertex How to build tree with more than 6 vertices, that after operation splay() would have depth = number of vertices? Is it possible?

UPD:
Example for n = 4:

insert 60
insert 10
insert 20
insert 50
splay(10)

You can use splay tree visualization

This is a good question whose answer can help us understand how splay tree tends to keep away from being imbalanced.

No, it is impossible for any rooted tree with more than 5 vertices to become a linear tree after operation splay() one of the deepest vertices, i.e. its depth is one less than the number of vertices.

Why?

For the sake of contradiction, let there be a rooted tree with more than 5 vertices which becomes a linear tree after splaying $x$, one of its deepest vertices. Consider the point of time just before the last splay step that moves $x$ to the root. There are three cases.

That last step is a zig-step (the following graph) or its mirroring zag-step.  Since the resulted tree is linear, part $A$ and $B$ are empty. That means, the left subtree of the root before that step contains node $x$ only. Since $x$ is the deepest node, the whole tree has at most 3 nodes, which is not true.

That last step is zig-zig step (the following graph) or its mirroring zag-zag.  Since the resulted tree is linear, part $A$, $B$ and $C$ are empty. That means, the left subtree of the root before that step contains node $P$ and $x$ only. Part $D$ can have at most two nodes; otherwise, either $x$ was not the deepest node or the resulted tree is not linear. So the whole tree has at most 5 nodes, which is not true.

That last step is a zig-zag step (the following graph) or its mirroring zag-zig. However, after that step, the root will alway has two children, which is not ture.

Exercise. Draw a tree with 5 vertices that becomes a linear tree after splaying one of its deepest vertices.


Finding all edges on any shortest path between two nodes Given a directed weighted graph with non-negative weights, how can I find all edges that are a part of any of the shortest paths from vertex X to Y?

In the example below the yellow edges are the solution for finding the shortest path between A and D (note that other examples may have more than one path).

I know how to find all nodes that are a part of a shortest path so I thought that all edges that sit between two nodes which are both on a shortest path means that the edge between them is also a part of the shortest path, but that is not true.

Any ideas would be appreciated.

Off the top of my head, you could do this. (Let's say you want to find all edges on a shortest path from $s$ to $t$.)

Run an All-Points Shortest Path (APSP) algorithm to store the shortest-path distances from every node to every other node
For every edge $a \rightarrow b$ in the graph:

Add up the distance from the $s$ to $a$, and the weight of the edge, and the distance from $b$ to $t$
Compare this sum to the distance from $s$ to $t$
If it's the same, this edge is part of a shortest path

This runs in $\Theta(E)$ plus the time for the APSP, which is $\Theta(V^3)$ using Floyd-Warshall. The space complexity is $\Theta(E)$ for the final results plus $\Theta(V^2)$ for the APSP.

EDIT: D.W. has pointed out an even more efficient algorithm. Instead of using APSP, use SSSP and SDSP (Single Source/Destination Shortest Path) once each, since you only need the distance from $s$ to everything, and from everything to $t$. This reduces the additional space to $\Theta(V)$, and the time to $\Theta(E+V \log V)$ using Dijkstra (assuming there are no cycles of negative weight).


How many different strongly connected graphs can be created given n nodes? Given some fixed number of nodes $n$, which we will number 1 to $n$ in order to tell them apart, how many different strongly connected graphs can be created? Multiple edges with the same starting and ending nodes should be considered redundant and not contribute to the total.

For example, if $n$ is 2, we can create only one strongly connected graph, (the 2-cycle.) But if $n$ is 3 then we can create 18 different graphs: 2 with 3 edges, 9 with 4 edges, all 6 with 5 edges and the complete 3-graph.

Is there a known general formula for computing this number for a given $n$?

This is A003030. Everything known about this sequence is listed there.


Reducing time complexity for finding all possible triplets in an array? So I have an array sized N. It is sure that array has all distinct elements.

I need to find sum of all possible triplets in that array and for that i need to find all possible triplets.

What i did: looping through array with three nested $for$ loops but that gives O(n^3).

I want to optimise the algorithm as n is very large(upto 10000)

Eg: Array==> {1,2,3,4,5}

Possible triplets: {1,2,3} {1,2,4} {1,2,5} {1,3,4} {1,3,5} {1,4,5} {2,3,4} {2,3,5} {2,4,5} {3,4,5}

Finding all the triplets is in fact useless. Let $|A| = n$. Observe that each $a \in A$ appears in exactly $\binom{n-1}{2}$ triplets.

Therefore, the requested sum is just:

$$
\sum_{a \in A} \binom{n-1}{2}a = \binom{n-1}{2} \sum_{a \in A} a
$$


Proof that $\{0^i1^{i^2}:i\in\mathbb{N}\}$ is not context free I am to prove that $L :=\{0^i1^{i^2}:i\in\mathbb{N}\}$ is not context-free. I presume that I can do this with the Pumping Lemma and the word $0^p1^{p^2}$, where we assume for a contradiction that $L$ has a Pumping Length of $p$, and here's my attempt:

Let $0^p1^{p^2}=uxyzv$ such that $xz$ is non-empty, $xyz$ is of length $\le p$ and $ux^iyz^iv\in L$.

Case 1: if $xyz$ is entirely within $0^p$ then $ux^2yz^2v = 0^p0^k1^{p^2}$ for some $k>0$ and hence $ux^2yz^2v \notin L$.
Case 2: if $xyz$ is entirely within $1^{p^2}$ then we get the same contradiction (with $0^p1^{p^2}1^k$).
Case 3: suppose that $x = 0^i$, $z = 1^j$. Then $ux^0yz^0v=0^{p-i}1^{p^2-j}$.

Then I want to show that $(p-i)^2 \ne p^2-j$, but I'm not sure how to do this.

The simplest way to show that your language is not context-free is by reduction to unary alphabet. Suppose that your language were context-free. Then the language obtained by applying a homomorphism which deletes all $0$'s would also be context-free. This language is the unary language $L' = \{ 1^{i^2} : i \notin \mathbb{N} \}$. It is known that a unary language is context-free iff it is regular. You can prove that $L'$ isn't regular in any number of ways (for example, it is finite but its limiting density is zero).

If you are hell-bent on using the pumping lemma, then the following argument works. As you mention, the only interesting case is Case 3, in which $x = 0^i$ and $z = 1^j$. According to the pumping lemma, for every $t$ the word $ux^{1+t}yz^{1+t}v = 0^{p+ti} 1^{p^2+tj}$ must belong to $L$, that is, $p^2+tj = (p+ti)^2$. But $(p+ti)^2 = \Theta(t^2)$ whereas $p^2+tj = \Theta(t)$, so for large $t$ the two cannot be equal.