Algorithm to find the two closest elements in a BST

In most common models of computation, it cannot be ensured to find the two closest elements in a binary search tree (BST) in $O(\log n)$ time or, in fact, in $o(n)$ time. Here $n$ is the number of elements in BST and $o(n)$ is the little $o$-notation.

The idea is simple. There must be enough running time for an algorithm to access at least about half of the elements.

Here is an detailed explanation. It is not rigorous;  to make it rigorous we will need an explicit adversary argument as well as a more detailed formal specification of the model of computation.

Let us fix some model of computation $M$ in which at most $c$ elements can be accessed in a unit time of computation for some constant $c$. In fact, $c$ is usually 1 or 2.

For the sake of contradiction, suppose algorithm $Alg$ can find the two closest elements in a BST of $n$ element in $o(n)$ time. So for constant $\dfrac1{3c}$, there exists a constant $n_0>0$ such that $A$ can find the two closest element in no more than $\dfrac1{3c}n$ time for all $n>n_0$.

Now let $n_1>\max(n_0, 6)$. Let $Alg$ runs on a BST with $n_1$ nodes for some time that is no more than $\dfrac1{3c}n_1$. Then $A$ has accessed at most $\dfrac{1}{3c}n_1\cdot c=\dfrac {n_1}3$ elements.
Let $a_1, a_2, \cdots, a_{n_1}$ be the elements in the BST in nondecreasing order. There must be at least 2 adjacent elements in that nondecreasing list of all elements none of which have been accessed by the algorithm. Those two elements mights be closer to each other than any pair of elements among the elements that have been accessed by $Alg$. That means, $Alg$ may not have found the two closest elements. This is a contradiction.

Exercise. Find the two closest elements in a binary search tree with left-child pointers, right-child pointers and parent pointers in $O(1)$ working space.


Count arrays with size n, sum k and largest element m

You actually don't need the largest element l in your recursive function. It doesn't make such sense to use it, since the largest number in an array has no influence on the other numbers.

In most (all?) dynamic programming problems you have to think about the last step / the last part. For f(i, j) you have an array with i numbers. You can imagine, that in the last step you added the last number to the array. So before you added the last number, the array only consists of i-1 numbers.

Now, if the added number was 1, then there are f(i-1, j-1) many arrays. If the added number was 2, then there are f(i-1, j-2) many arrays. And so on...

Add all those possibilities up, and you end up with f(i, j).


How to write suitable three address code for switch-case statements?

Some more things to look at:

First, mixed table/branch approach. Say you have cases 1, 2, 3, 4, 5, 6 and 999,999,999. You might check for 999,999,999 first, then use a table for the rest. And remember for the table approach that you need to check if the case is within the table. So take a table for 0-5, compare if case ≥ 6, if not you use the table, if yes, you handle the remaining case.

Second, probably most important: Binary search. Say you have cases 1-20. First you compare against 10. Branch to a second compare block if the case is >10. That alone halves the average number of comparisons needed.

Third, take advantage of one comparison usually giving multiple results. If you know that x = 1, 2 or 3, then you need only one comparison with 2 and two conditional branches.


Math behind Multi-class linear discriminate analysis (LDA)

Given normalized top $k$ eigenvectors $v_1,\ldots,v_k$, you send a point $x$ to the tuple $(\langle x,v_1 \rangle, \ldots, \langle x,v_k \rangle)$.

Alternatively, you put the eigenvectors as rows in a matrix $M$, and you map the column vector $x$ to $Mx$ (this is exactly the same thing as above).

Multiplying vectors is an operation that doesn't have much semantic sense here. (How would you multiply them anyway, and why?)

There are reasons why we apply this particular operation, and they have to do with the goal of LDA. If you want to know more, I suggest picking up a decent textbook that explains LDA not only via formulas and algorithms, but also as the solution to an optimization problem.


Are typical sets larger, when information is messier?

Recall that
$$
A_\epsilon^{(n)}(P) = \left\{ (x_1,\ldots,x_n) \in \{0,1\}^n : 2^{-n(h(p)+\epsilon)} \leq p^{\sum_{i=1}^n x_i} (1-p)^{\sum_{i=1}^n (1-x_i)} \leq 2^{-n(h(p)-\epsilon)} \right\}.
$$
We can rephrase the condition as follows. First, it is equivalent to
$$
2^{-n(h(p)+\epsilon+\log(1-p))} \leq \left(\frac{p}{1-p}\right)^{\sum_{i=1}^n x_i} \leq 2^{-n(h(p)-\epsilon+\log(1-p))}.
$$
Taking the logarithm, we obtain
$$
-n(h(p)+\epsilon+\log(1-p)) \leq \log_2 \frac{p}{1-p} \sum_{i=1}^n x_i \leq -n(h(p)-\epsilon+\log(1-p)).
$$
This means that
$$
|A_\epsilon^{(n)}(P)| = 2^n \Pr\left[\frac{n(h(p)-\epsilon+\log(1-p))}{\log \frac{1-p}{p}} \leq \mathrm{Bin}(n,1/2) \leq \frac{n(h(p)+\epsilon+\log(1-p))}{\log \frac{1-p}{p}}\right]
$$
In order to estimate the probability on the right, we need to use binomial tail bounds. The Chernoff bounds is a well-known upper bound, and there are almost matching lower bounds, see for example (1) and (3) in Pelekis, A lower bound on binomial tails: an approach via tail
conditional expectations. Plugging these bounds, we would get a rather accurate estimate for $|A_\epsilon^{(n)}(P)|$, which we could then compare with $|A_\epsilon^{(n)}(Q)|$, estimated using the same method.

Unfortunately, this calculational method seems like a lot of work, better done with the aid of a computer algebra system, and I am not motivated enough to actually carry it through. However, it seems likely (if not certain) that this method will be able to settle the conjecture.


When are invariants true inside of a loop?

Are invariants true at most part of the loop and can be untrue at some part?

Invariants hold prior and after each execution of the loop body; there are no requirements for what happens in between its statements. Not only that, I would even say it is quite the norm that invariants are broken during the loop. Fixing them is actually a sort of programming paradigm; it gives you a way of determining what the values for variable assignments in a loop should be. In fact, this is a quite natural concept if your design approach is based on invariants (e.g., if you are writing programs which are annotated with JML as in design by contract and similar ideas based on formal proof systems).

For instance, consider the following toy example in which we want to sum over the elements in an array $A$ and save the result in the variable $s$:

$$\begin{align*}
&s \gets 0  \\
&i \gets |A| \\
&\textbf{while } i > 0 \textbf{ do} \\
&\quad i \gets i - 1 \\
&\quad s \gets s + A[i] \\
&\textbf{done}
\end{align*}$$

The invariant is $s = \sum_{j=i}^{|A|-1} A[j]$, and it holds prior and after each execution of the loop body. However, after $i \gets i - 1$ is executed, the invariant no longer holds, that is, we then have $s = \sum_{j=i+1}^{|A| -1} A[j]$. Hence, the next instruction updates $s$ so that the invariant holds again.


How to define a context free grammar from a regular language?

Your statement is correct. However your cases do not cover the full width of context-free grammars. All your examples are linear grammars.

In general one also allows right-hand sides that contain more than one non-terminal, like A->BC.


Algorithm for determining whether 2 entities of some feature are the same?

I am not able to clearly understand your use case, but from what I infer I believe if you are trying to de-dupe data on other features, the approach would be to use LSH(Locality Sensitive Hashing) you can see the following links to get an overview. hope this helps.

https://stackoverflow.com/questions/12952729/how-to-understand-locality-sensitive-hashing

https://www.cs.utah.edu/~jeffp/teaching/cs5955/L6-LSH.pdf

https://en.wikipedia.org/wiki/Locality-sensitive_hashing


How to solve a problem about balancing parentheses with smileys?

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

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


Disruption in the context of Genetic Algorithms

According to my professor, my intuitive description of disruption is correct, however one does not measure the "degree of disruption". It is a binary measure. Either you have disruption or you do not.

Still can't find an official source for this, so edits to this answer and other answers are welcome.


How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?

Let $S(n) = T(n) - 2n - 2$. You can check that $S(n) = S(n-1) + S(n/2)$ (ignoring the fact that $n/2$ need not be an integer). This shows that the additive $n$ term doesn't make a big difference.

For large $n$, we have roughly $S(n) - S(n-1) \approx S'(n)$, and so we are led to solve the differential equation
$$
S'(n) = S(n/2).
$$
Consider $f(n) = \exp (\tfrac{1}{2}\log_2^2 n)$. Then
$$
f'(n) = \exp (\tfrac{1}{2}\log_2^2 n) \cdot \frac{\ln n}{(\ln 4)n},
$$
whereas
$$
f(n/2) = \exp(\tfrac{1}{2} (\log_2 n - 1)^2) \approx \exp(\tfrac{1}{2}\log^2 n) \exp(-\log n) = \exp(\tfrac{1}{2} \log^2 n) \cdot \frac{1}{n}.
$$
This suggests that, at the very least, $\ln S(n) = \Theta(\log^2 n)$.

Where does this come from? You can think of $S(n)$ (with an appropriate base case!) as the number of ways to go from $n$ to zero by applying two operations: subtract 1 and divide by 2. A "typical" such sequence will contain roughly $\log_2n$ many operations of the second type, out of $\Theta(n)$ operations in total, leading to the very rough estimate $\binom{\Theta(n)}{\log_2 n}$, which is also of the form $\exp \Theta(\log^2 n)$.

Consider for concreteness the following precise definition of $S(n)$: the base case is $S(0) = 1$, and for $n > 0$,
$$
S(n) = S(n-1) + S(\lfloor n/2 \rfloor).
$$
This is sequence A000123. Knuth, An almost linear recurrence, showed that
$$
\log_4 S(n) \sim \log_4^2 n,
$$
that is, the ratio of the two terms tends to 1 as $n \to \infty$. The OEIS entry contains even more precise asymptotics.


How to come up with a language that is recognizable but not co-recognizable?

Remember that there are three things a Turing machine can do, given an input. It can:

Accept
Reject
Diverge (infinite-loop)

"Recognizable" means "we can accept on strings in our language, and reject-or-diverge on anything else". "Co-recognizable" means "we can reject-or-diverge on strings in our language, and accept on anything else". Or, equivalently, "we can accept-or-diverge on strings in our language, and reject on anything else".

So the key is, intuitively, to find a language so that a TM always diverges on (some) strings not in the language.

A classic example is the Halting Problem. (To be more specific, the set of encoded Turing machines that halt on empty input, for a given encoding.) You can recognize this language by simulating the machine, then accepting. But you can't recognize its opposite.

(Formally, you have to do a bit more work. You have to prove that the language is undecidable: that no Turing machine can always say "no" correctly, even if it can always say "yes" correctly. Usually this means reduction to the Halting Problem or Rice's Theorem.)


With all due reserve.
DRAM chips today are placed on DIMMs which look like

The black chips seen on the DIMM are the DRAM chips. DRAM chips inside look like

Each big gray square is called a bank. One bit of DRAM looks like

You see that between the output of the DRAM chip and the bit stored in the capacitor there is a sense amplifier. That is used to amplify the voltage of the stored energy. You need this because the energy stored in one capacitor is not strong enough to just be sent over to the bus. The sense amplifier is detailed at http://pnrsolution.org/Datacenter/Vol3/Issue2/119.pdf.

Sense amplifier is not only an amplifier but a positive feedback device that quickly pushes the readout voltage to 1 or 0. The gates of the DRAM cells are  tied to the row decoder and the bit-line pairs are connected to the sense amplifier.

A detailed explanation of the hardware interface of DRAM chips is found at https://compas.cs.stonybrook.edu/~nhonarmand/courses/sp15/cse502/res/dramop.pdf. This pdf is very detailed. For the read operation it says:

To read the data from a memory cell, the cell must be selected by its row and column coordinates, the charge on the cell must be sensed, amplified, and sent to the support circuitry, and the data must be sent to the data output. In terms of timing, the following steps must occur:

The row address must be applied to the address input pins on the memory device for the prescribed amount of time before RAS goes low(tASR) and held (tRAH) after RAS goes low.

RAS must go from high to low and remain low (tRAS).

A column address must be applied to the address input pins on the memory device for the prescribed amount of time (tASC) and held (tCAH) after CAS goes low.

WE must be set high for a read operation to occur prior (tRCS) to the transition ofCAS, and remain high (tRCH) after the transition of CAS.

CAS must switch from high to low and remain low (tCAS).

OE goes low within the prescribed window of time. Cycling OE is optional; it may be tied low, if desired.

Data appears at the data output pins of the memory device. The time at which the data appears depends on when RAS (tRAC),CAS (tCAC), and OE (tOEA) went low, and when the address is supplied (tAA).

Before the read cycle can be considered complete,CAS and RAS must return to their inactive states (tCRP, tRP).

To be clear, this is how DRAM chips work with their own pins. This is not how the DIMM itself works. The DIMM is a bit different. You can look at JEDEC specifications on DDR RAM to see how DRAM work a bit better. For example, the JESD79-4 standard is about the DDR4 SDRAM (Synchronous DRAM) (http://www.softnology.biz/pdf/JESD79-4B.pdf). In this document is stated how bank groups and banks are selected. The address pins are multiplexed meaning that depending on if RAS or CAS is set then address pins will either select a column or a row. Page 5 is especially interesting because it describes the actual pins of the DDR4 DRAM chip.
To determine how actual DIMMs work, one can look at other JEDEC specifications (https://www.jedec.org/standards-documents/docs/module4_20_26_annexa). This website presents the actual document that you must be registered to download. This documents specifies the pin description of DDR4 DIMMs. The DDR4 DIMM is 288 pins (144 on each sides). The pins that are important for your question are the DQ pins. There are 64 DQ pins which is not for no reason. It is because DDR4 supports 64 bits machines. The DQ pins are probably connected to the data bus of the computer.
For actual interface between memory and Intel CPUs you can look at the External Memory Interface Handbook Volumes 1, 2 and 3 from Intel. These volumes are available on internet and are pretty lengthy. They are pretty hard to understand. The document at https://www.intel.com.br/content/dam/doc/datasheet/core-i5-600-i3-500-pentium-6000-datasheet-vol-1.pdf is a description for the core i5 processor which is pretty good. It has a pin description at the end of the document for the processor. There are 64 bidirectional SA_DQ pins and 64 SB_DQ pins. These pins are used for I/O to and from RAM.

The Integrated Memory Controller (IMC) supports DDR3 protocols with two independent, 64-bit wide channels each accessing one or two DIMMs.

Based on the above statements, there are several interfaces between the data bus and the actual bit line of the memory cell. A path will have to eventually be opened between the processor SA_DQ pins and the DQ pins of the DIMM using the data bus. The DQ pins of the DIMM are themselves connected to the output data buffers of the banks of the DRAM chips.


Do non-computable functions grow asymptotically larger?

If you take any noncomputable set of natural numbers, the characteristic function of the set takes only the values $\{0,1\}$ and is noncomputable. So it is not the case that every noncomputable function grows very quickly, they can even be bounded.

The Busy Beaver function grows more quickly than every computable function because it is constructed to do so. The proof that it is noncomputable proceeds by first proving that it grows faster than any computable function.

More generally, say that a set  $A \subseteq \mathbb{N}$ has "hyperimmune-free degree" if every function computable from $A$ is bounded by a computable function. Certainly every computable set has hyperimmune-free degree. It is known that there are also many noncomputable sets that have hyperimmune-free degree. So it is not the case that everything noncomputable will have to compute some fast-growing function.

However, it is also the case that an r.e. set that is noncomputable will not have hyperimmune-free degree. If $B$ is r.e., and enumerated by index $e$, the function $f$ such that $f(n) = k$ if $e$ enumerates $n$ in $k$ steps, and $f(n) = 0$ if $e$ does not enumerate $n$, is computable from $B$ but this function is bounded by a computable function if and only if $B$ is computable.


Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n))

Yes. Clearly NSPACE($2^{O(n)}$) $\subseteq $  NSPACE($n^2 \cdot 2^{O(n)}$).
To show that NSPACE($2^{O(n)}$) $\supseteq $  NSPACE($n^2 \cdot 2^{O(n)}$) it suffices to notice that $n^2  \cdot 2^{O(n)} = 2^{O(n) + 2\log n}$ and $O(n)+2\log n =O(n)$.


Why is there only a polynomial number of provers in multi-prover interactive protocols?

Yes. We could have defined MIP to allow an exponential number of provers but that is basically  the PCP model which is equivalent to MIP with a polynomial (or just two) provers.


On an array of sets, Data structure to handle Interval insert, Interval erase, Interval sum of size query

I am assuming that inserting a value $x$ to a set already containing it does nothing, which is how sets usually work. Then this can be solved in amortised $\mathcal{O}(\log n \log q)$ time per query, with $\mathcal{O}(n + q \log n)$ memory usage.

Assume you have $n = 2^{h}$ sets (this is not limiting, add some unused sets if you need to). We will build a segment tree on the sets: build a perfect binary tree of size $2n-1$, and index the nodes such that node $1$ is the root, the children of node $i$, $1 \leq i < n$ are nodes $2i$ and $2i+1$, and nodes $n, \dots, 2n-1$ are the leaves. Each vertex represents some interval of the sets, with leaf $i+n$, $0 \leq i < n$ representing the $i$th original set (0-indexed), and each vertex representing the union of the intervals its children represent.

We will store in every node two sets: one containing every value occurring in every set of its interval, but not in every set of its parent's interval, called $all[i]$, and one containing every value occurring in some, but not all of the sets in its interval, called $some[i]$. We also store an integer $sum[i]$, which is $|all[i]|$ times the size of the node's interval, plus the sums of its children.

First note that this data is sufficient to answer queries of type 3 in $\mathcal{O}(\log n)$ time. Say we want to count the total size of the sets in interval $[a, b]$. DFS down from the root, and at every node,

If that node's interval is disjoint of $[a, b]$, return 0
If that node's interval is contained in $[a, b]$, return $sum[i]$.
Otherwise, return $|all[i]|$ times the size of the intersection of $[a, b]$ and this node's interval, plus the return values of recursive calls to this node's children.

Clearly storing the data this way requires at most $\mathcal{O}(n + q \log n)$ memory:

We initially need $\mathcal{O}(n)$ memory.
In a query of type 1, we at worst add $x$ to $\mathcal{O}(\log n)$ sets in our tree, since in segment trees, for any interval $[a, b]$ there are at most $\mathcal{O}(\log n)$ nodes, such that their interval is contained in $[a, b]$, but the interval of their parent isn't.
In a query of type $2$, say we delete $x$ from interval $[a, b]$. If $x$ doesn't occur in $a-1$ and doesn't occur in $b+1$, this operation in fact frees memory. Thus it always uses at most as much memory as two insertions, as we can extend the interval to be deleted until $x$ doesn't occur in $a-1$ and $b+1$, and then re-insert $x$ to the sides.
Queries of type $3$ are read-only, and use no memory.

How to perform operations 1 and 2? First note that we do everything in DFS-order, so updating the stored value is trivial: it's just the sum of the stored values of this node's children, plus the size of this node's interval times the size of this node's first set. So we only need to consider how to update the sets.

For this time complexity, we need amortised analysis. We will use a potential function with value

\begin{equation*}
f = \sum_{i = 1}^{2n-1} |some[i]| \log q
\end{equation*}

With this potential function, it costs no time to delete $x$ from interval $[a, b]$, if $[a, b]$ is the interval of some node $i$, and $x \in some[i]$, and we do not care about updating ancestors of $i$ for now. Deleting $x$ from $some[i]$ takes $\mathcal{O}(\log q)$ time, but the potential decreases by $\log q$. Then recurse to the children of $i$. If $x \not \in some[j]$ for either child $j$, then if $x \in all[j]$, delete $x$ from $all[j]$, otherwise return. This wastes $\log q$ time, but with large enough constants, the potential decrease covers that.

In operation 1, say we want to insert $x$ to interval $[a, b]$. We DFS down from the root, and at every node,

If that node's interval is disjoint of $[a, b]$, return.
If that node's interval is contained in $[a, b]$, first delete $x$ from the interval for either free if $x \in some[i]$, or at the cost of $\mathcal{O}(\log q)$ otherwise, then add $x$ to $all[i]$ in $\mathcal{O}(\log q)$.
Otherwise, first recurse to the node's children. Then, update whether $x$ appears in $all[i]$ and $some[i]$ in $\mathcal{O}(\log q)$ time. If $x \in all[j]$ for both children $j$, you have to remove it from $all[j]$ for both children, but this is again just $\mathcal{O}(\log q)$ time.

Thus insertion takes $\mathcal{O}(\log n \log q)$ amortised time, since cases 2 and 3 occur at most $\mathcal{O}(\log n)$ times. For deletion, very similarly, we again DFS and at every node,

If that node's interval is disjoint of $[a, b]$, return.
If that node's interval is contained in $[a, b]$, delete $x$ from the interval for either free if $x \in some[i]$, or at the cost of $\mathcal{O}(\log q)$ otherwise.
Otherwise, first recurse to the node's children. Then, update whether $x$ appears in $all[i]$ and $some[i]$ in $\mathcal{O}(\log q)$ time.

Here's a C++ implementation:

#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;

class SegTree {
    private:
        vector<set<int>> all, some;
        vector<ll> sum;
        int h = 1;

        // returns 2 if x in all[i], 1 if x in some[i] and otherwise 0
        int val(int i, int x) {
            return all[i].count(x) ? 2 : some[i].count(x);
        }
        void update(int i, int x, int len) {
            int va = val(2*i, x), vb = val(2*i+1, x);
            if (va == 2 && vb == 2) {
                some[i].erase(x);
                all[i].insert(x);
                for (int c : {2*i, 2*i+1}) {
                    all[c].erase(x);
                    sum[c] -= len / 2;
                }
            } else {
                all[i].erase(x);
                if (va || vb) some[i].insert(x);
                else some[i].erase(x);
            }
            sum[i] = (ll)all[i].size() * len + sum[2*i] + sum[2*i+1];
        }

        // [a, b) is query interval, [ia, ib) is the node's interval
        ll recGet(int a, int b, int i, int ia, int ib) {
            if (b <= ia || ib <= a) return 0; // intervals are disjoint
            if (a <= ia && ib <= b) return sum[i]; // contained in query interval
            int mid = (ia + ib) >> 1;
            ll res = (ll)all[i].size() * (min(ib, b) - max(ia, a));
            res += recGet(a, b, 2*i, ia, mid);
            res += recGet(a, b, 2*i+1, mid, ib);
            return res;
        }

        void recErase(int a, int b, int x, int i, int ia, int ib) {
            int v = val(i, x);
            if (b <= ia || ib <= a || v == 0) return;
            if (v == 2) {
                all[i].erase(x);
                sum[i] -= ib - ia;
                if (ia < a) recInsert(ia, a, x, i, ia, ib);
                if (b < ib) recInsert(b, ib, x, i, ia, ib);
            } else {
                int mid = (ia + ib) >> 1;
                recErase(a, b, x, 2*i, ia, mid);
                recErase(a, b, x, 2*i+1, mid, ib);
                update(i, x, ib-ia);
            }
        }

        void recInsert(int a, int b, int x, int i, int ia, int ib) {
            if (b <= ia || ib <= a || all[i].count(x)) return;
            if (a <= ia && ib <= b) {
                if (some[i].count(x)) recErase(a, b, x, i, ia, ib);
                all[i].insert(x);
                sum[i] += ib - ia;
            } else {
                int mid = (ia + ib) >> 1;
                recInsert(a, b, x, 2*i, ia, mid);
                recInsert(a, b, x, 2*i+1, mid, ib);
                update(i, x, ib-ia);
            }
        }
    public:
        SegTree(int n) {
            while(h < n) h <<= 1;
            all.resize(2*h);
            some.resize(2*h);
            sum.resize(2*h, 0);
        }

        ll query(int a, int b) { return recGet(a, b+1, 1, 0, h); }
        void erase(int a, int b, int x) { recErase(a, b+1, x, 1, 0, h); }
        void insert(int a, int b, int x) { recInsert(a, b+1, x, 1, 0, h); }
};

int main() {
    int n, q;
    cin >> n >> q;

    SegTree seg(n);
    for (int i = 0; i < q; ++i) {
        int t, a, b;
        cin >> t >> a >> b;
        --a; --b;

        if (t == 3) {
            cout << seg.query(a, b) << '\n';
        } else {
            int x;
            cin >> x;
            if (t == 1) seg.insert(a, b, x);
            else seg.erase(a, b, x);
        }
    }
}
```


how to solve NFA acceptance problem in polynomial time

Hint (expanding on David Richerby's hint): As the NFA reads $w$, keep track of the set of states it could be in at any given time.


Counting Number of arrays where sum of ith row is greater or equal to (i-1)th row

The case where $N=2$ is fairly easy. For $M\ge N$ we'll have an array
$$\begin{array}{ccccc}
a_{1,1} & a_{1,2} & a_{1,3} &\dotsm & a_{1,M}\\
a_{2,1} & a_{2,2} & a_{2,3} &\dotsm & a_{2,M}\\
a_{3,1} & a_{3,2} & a_{3,3} &\dotsm & a_{3,M}\\
        &\dotsm   &         &       &        \\
a_{N,1} & a_{N,2} & a_{N,3} &\dotsm & a_{N,M}\\
\end{array}$$
Define $t(k,M)$ to be the number of integer solutions of $x_1+x_2+\dotsm+x_m=k$ with all $x_i\ge 0$. The stars and bars theorem tells us that
$$
t(k,M)=\binom{M-1+k}{M-1}
$$
Then if we let $C(N,M)$ denote the number of solutions to the original problem, it's not hard to see that for $N=2$,
$$\begin{align}
C(2,M) &= \sum_{i=0}^M\left[t(i,M)\sum_{j=0}^it(j,M)\right]\\
&= \sum_{i=0}^M\binom{M-1+i}{M-1}\sum_{j=0}^i\binom{M-1+j}{M-1}\\
&= \sum_{i=0}^M\binom{M-1+i}{M-1}\left[\binom{M-1}{M-1}+\binom{M}{M-1}+\dotsm+\binom{M-1+i}{M-1}\right]\\
&= \sum_{i=0}^M\binom{M-1+i}{M-1}\binom{M+i}{M}
\end{align}$$
The last step above uses a fairly well-known result on the sum of a column of Pascal's triangle. So finally we'll have
$$
C(2,M) =\binom{M-1}{M-1}\binom{M}{M}+\binom{M}{M-1}\binom{M+1}{M}+\dotsm+\binom{2M-1}{M-1}\binom{2M}{M}
$$
For $N=M=2$ we have $C(2,2)=1+6+18=25$, which agrees with your example.

Added yet again. For a (not particularly useful) general form, it's not hard to see that
$$
C(N,M)=\sum_{0\le i_1\le i_2\le\dotsm i_N\le M} t(i_1,M)t(i_2,M)\dotsm t(i_N,M)
$$
In this expression, each of the $i_k$ represents the possible sum of the $k$-th row.

I asked on Math.SE whether the expression for $C(2,M)$ had a closed form and the consensus was that it didn't (although it can be expressed as a hypergeometric series, for what that's worth).


Counting the number of squares in a graph

There is a simple $O(n^4)$-time algorithm which I will let you discover yourself. A better algorithm follows from the following formula for the number of squares:
$$
\operatorname{Tr} (A^4) - \sum_i d_i^2,
$$
where $A$ is the adjacency matrix and $d_i$ is the degree of the $i$th vertex. Using this formula you can compute the number of squares in $O(n^\omega)$, where $\omega < 2.373$ is the matrix multiplication constant.


Grammatical characterization of deterministic context-free languages

Wikipedia actually gives you the model and points to [1] for reference: LR grammars are equivalent to DPDA.

On the Translation of Languages from Left to Right by Donald Knuth (1965) [free download]


Hint: If $f(n) \notin \overset{\infty}{\Omega}(g(n))$ and $g(n)$ is asymptotically non-negative, then for all positive constants $c$, $f(n) \leq c \cdot g(n)$ for large enough $n$. This follows by ignoring the condition $c \cdot g(n) \geq 0$ and negating the definition of $f(n) \in \overset{\infty}{\Omega}(g(n))$. In fact, this way you get the stronger result that either $f(n) \in \overset{\infty}{\Omega}(g(n))$ or $f(n) \in o(g(n))$ (but not both).

Further hint: You can start by showing that the negation of "$P(n)$ for infinitely many $n$" is "$\lnot P(n)$ for large enough $n$".


Identical register input operands in assembly

R1 <- R0 + R0 works in every processor that permits three register operands.  Nothing special needs to be done to deal with the same register driving multiple read ports.

Each register-file read port is just a multiplexer.  If you have $N$ registers driving the $N$ inputs of one $N$-to-$1$ multiplexer and the same $N$ registers driving the $N$ inputs of a different $N$-to-$1$ multiplexer, there's no constraint that says that both multiplexer selects can't be set to the same register.


How to find the language of a CFG from Production rules

The idiom "$X \to YX \mid \epsilon$" (or "$X \to XY \mid \epsilon$") means that $X$ generates $Y^*$ (assuming there are no other productions for $X$). This means that your grammar generates $A^*$. You know what $A$ generates. Putting everything together, you should be able to find a very concise description of the language generated by your grammar.


Divide self-intersecting polygon into simple polygons

A self-intersecting polygon induces a plane partition, which should be represented by some data structure. This structure should include at least three types of objects - vertices, edges and faces. The faces are what you are trying to construct.

This data structure is called DCEL and it usually represents both planar graphs - the original graph with vertices and edges (where intersection points are added as new vertices, and some edges are split), and a dual graph with polygonal faces as vertices. Each vertex in the original graph should refer to a list of adjacent edges (sorted by angle, yes) and each vertex in the dual graph should refer to a list of adjacent edges, forming its boundary. Edges are usually represented by two arcs with orientations, opposite to one another. In this case each arc is adjacent to exactly one face (including the exterior face), which normally lies "to the left" of it.

Having this data structure implemented you'll be able to calculate all the faces by finding proper cycles in the set of all arcs.


How to go about working the average case run time of this trivial algorithm (and other algorithms)?

Here's an elaboration of The Unfun Cat's answer. For convenience, let the numbers be $v_1,\ldots,v_n$. Whatever the value of $v_1$ is, for $i>1$ we have $\Pr[v_i = 10-v_1] = 1/9$. Therefore, the number of iterations of the second loop is roughly distributed geometrically $G(1/9)$, so we expect it to run about $9$ times. A complication is that $n$ is not infinite, but this doesn't have a great effect on the running time.

Given $n$, the probability that the outer loop doesn't terminate on the first iteration is $(8/9)^{n-1}$. If it does, then the expected number of (inner-loop) iterations is less than $9$. Otherwise, it is at most $\binom{n}{2}$. Therefore the running time is $O(9 + \binom{n}{2}(8/9)^{n-1}) = O(1)$, using $n^2 = O((9/8)^n)$.


Parallelization of priority queue-based algorithms

Two old, but, I think, still very useful resources:

M.T.Goodrich, M.R.Ghouse, and J.Bright. Sweep Methods for Parallel Computational Geometry. Algorithmica (1996), 15:126-153. - closely related to what you are asking about, download for free: link.
S.G.Akl, K.A.Lyons. Parallel Computational Geometry. Prentice-Hall, 1993 - monograph about first ten years of research in parallel computational geometry. In the Chapter Four they say: "The plane sweep technique appears to be inherently sequential", but nevertheless refer to a number of parallel sweeping algorithms. Please see: link.


Why Finite Automata are restricted in reading the input?

Yes, there are things you could do to finite automata to make them more powerful. However, "with great power(er) comes great(er) responsibility."

Finite automata aren't very powerful but the languages they express – the regular languages – form a natural and important class.  Furthermore, for a fixed automaton, you can decide in linear time (with respect to the input) and constant working space whether it accepts or rejects any particular string. This is true even if the automaton is nondeterministic.

OK, but lots of important languages can't be decided by finite automata.  Important examples include anything that involves bracket matching, including the syntax of any sane programming language. How might you try to make automata more powerful and what would the cost be?

Suppose we allow the machine to scan both left and right along its input. This gives a two-way automaton.  Well, it turns out that two-way automata (deterministic or nondeterministic) still only accept regular languages – the same as ordinary automata. The two-way automaton might require fewer states and you can still determine whether it accepts a given input in linear time.  But now there's the possibility that the automaton can loop forever, so you need to check for that, which requires a logarithmic amount of working space, instead of constant.  (Since the number of steps before termination is bounded by some linear function of the length of the input, you can detect looping by counting steps and halting if the computation runs too long.  The counter needs a logarithmic number of bits.)
Suppose you allow the automaton to move backwards and forwards as well as overwrite its input, but not to use any more space than the input takes up.  This does make the machine more powerful (for example, you can now detect well-matched bracketings by "crossing out" the brackets one by one) but it makes it even harder to determine whether the machine accepts its input and to check for infinite loops.  Now, halting might take exponentially many steps, so you need a polynomial-length counter (linear is probably enough).
Suppose you allow the automaton to move backwards and forward, overwrite its input and use as much additional space as it wants.  Now your automaton has become a Turing machine.  It can do (we think) anything that any reasonable computer can do but there's no way of determining whether it accepts its input except for running the machine and hoping it eventually stops. This could take arbitrarily long and use arbitrarily much working space.

There are plenty of other possible additions to automata (for example, stacks) but they don't fit as neatly into the discussion above.

So, yes, you might want to make automata more powerful.  But doing so brings risk and expense that you might not be prepared to tolerate, if you don't need it.


What exactly would stop me from registering a domain from my own nameserver?

Nothing stops you from setting up such a nameserver.  However, this wouldn't be of any use to you, because no one is going to contact your nameserver to ask whether domainexample.com exists: they're only going to contact the official name server for .com.

It'd be like saying "can't I lie about the location of the White House if anyone asks me?" -- well, yes, I can, but if no one ever asks me that, then this isn't achieving much.

What prevents you from lying about .com?  People aren't going to ask you; they are going to contact the root nameserver and ask that question.  How do people know who the root nameservers are?  The root nameservers are publicly known (specified in a RFC) and hardcoded in everyone's DNS software.  So ultimately the recursion bottoms out.

That's why setting up your own nameserver won't help you: no one is ever going to ask your nameserver anything or have any trust in it, so its lies won't affect anyone.


malloc is a library function that makes use the sbrk system call. The manual page of malloc on Linux says:

  Normally,  malloc() allocates memory from the heap, and adjusts the size of the heap as required, using sbrk(2).

If we now look at sbrk manual page:

   brk() and sbrk() change the location of the  program  break,
   which  defines  the end of the process's data segment (i.e.,
   the program break is the first location after the end of the
   uninitialized  data  segment).  Increasing the program break
   has the effect of allocating memory to the process; decreas
   ing the break deallocates memory.


Calculate the complexity of an algorithm

The number of times that the if is executed is
$$
\sum_{i=1}^{n-1} (i^2-1) = \Theta(n^3).
$$
The number of times that sum is incremented is
$$
\sum_{i=1}^{n-1} \sum_{\substack{1 \leq j < i^2 \\ i \mid j}} j =
\sum_{i=1}^{n-1} \sum_{k=1}^{i-1} ki = \sum_{i=1}^{n-1} i \binom{i}{2} = \Theta(n^4).
$$
Altogether, we get a running time of $\Theta(n^4)$.


probablistic procedure to permutate array

I'm not exactly certain what you mean by probabilistic procedure as pertains to array permutation, and I'm going to assume you're looking for a random permutation of the array. I'm basing this off the formulation of the problem being very similar to an algorithm for that purpose.

So lets say as a person I'd like to do this task: Well, I'd probably just write down all the possible numbers, and then pick a random one. Then I'd cross of the one I'd picked and continue until I'd crossed them all off.

Spoiler as to the name of the algorithm which I mentioned:

   See Fisher-Yates Shuffle algorithm or Knuth Shuffle.


Construct a PDA for the complement of $a^nb^nc^n$

No, this is context-free. To accept $a^nb^nc^n$, you need to make sure that three numbers are equal. To accept $a^*b^*c^* \setminus a^nb^nc^n$, you just need to make sure that you're in one of the following three cases:

The number of $a$s is different from the number of $b$s; or
The number of $a$s is different from the number of $c$s; or
The number of $b$s is different from the number of $c$s.

Write a PDA for each of these cases, then combine them by jumping nondeterministically to each one from the start state.


Without using the Time Hierarchy Theorem, is there any other way to prove P /= EXP

There is a way, actually! Kind of.

Consider two cases:

$P \not= NP$. This case is easy: then $P \not= EXP$, because $NP \subset EXP$.
$P = NP$. It is known that $P = NP$ implies that there is a language from $EXP$ that has circuit complexity of at least $\frac{2^n}{10n}$, so $EXP$ is not a subset of $P/\mathrm{poly}$ in this case, let alone $P$. I will recall the proof here with more details if it is necessary, but that question has already been answered, for example, here: https://mathoverflow.net/questions/57828/p-np-exp-has-circuit-size-o2n-n (the answer is pretty sketchy, though, so feel free to ask for more details).


NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}

We can assume without loss of generality that the vertex set is $1,\ldots,n$.
Let us say that a vertex is minimal if it has the minimal value in its connected component. You can check that a vertex in minimal in NL by checking that it is not connected to any smaller vertex.

A graph has at least $k$ connected components iff there is a list $v_1 < v_2 < \cdots < v_k$ of minimal vertices. This shows that CONN is in NL. Since NL=coNL, it follows that E-CONN is also in NL.

Morale: if you want to make sure that you guessed $k$ distinct vertices, guess them in increasing order.

Since undirected connectivity is in L, we can actually count the number of connected components in L, by just going over all vertices, and counting how many of them are minimal.


Covering grid with constrained rectangles

I suggest you use a constraint solver, like Minion.  The following paper shows that they are effective for a related problem:

Almost Square Packing, Helmut Simonis and Barry O’Sullivan.

My thanks to András Salamon for pointing to this information.

You could also try using a SAT solver.


Quantum computers, parallel computing and exponential time

Why can't a quantum computer solve exponential problems in sub-exponential time? Factoring is believed (by some) to take classical time $2^{n^\epsilon}$ for some $\epsilon > 0$, while Shor's algorithm takes time $O(n^3)$. Does that count?

Is it at least theoretically possible to imagine a computer able to solve EXPTIME-complete problems in constant time? Sure, consider a Turing machine with oracle access to all EXPTIME problems (i.e. the oracle accepts the code of an EXPTIME machine and an input, and returns the output). This doesn't lead to any contradictions. Is this realizable in practice? Probably not.

Can quantum computers do parallel computing? It is known that BQP$\subseteq$PP$\subseteq$EXPTIME, and most people expect these inclusions to be proper. Under this conjecture, there are problems solvable in classical exponential time but not quantum polynomial time. In particular, EXPTIME-complete problems shouldn't be in BQP.


reduction from the problem "accepts-empty string" to "language of empty string"

Call $L_1=\{\langle M \rangle\mid M\text{ accepts }\lambda\}$ and $L_2=\{\langle M \rangle\mid M\text{ accepts only }\lambda\}$, where $\langle M\rangle$ denotes the description of the TM $M$. We wish to establish a mapping reduction $L_1 \le_\text{M} L_2$.

To do this, we want a mapping, $f$, from TM descriptions to TM descriptions such that
$$
\langle M\rangle\in L_1 \Longleftrightarrow f(\langle M\rangle)\in L_2
$$
For a TM description $\langle M\rangle$, we'll define $f(\langle M\rangle)=\langle N\rangle$ where

N(x) =
   if x = lambda
      run M on input lambda
      if M accepts
         accept

Now what happens with this mapping?

If $M(\lambda)$ accepts (so $\langle m\rangle\in L_1)$, $N$ will accept $\lambda$ and no other string, so $\langle N\rangle\in L_2$.
If $M(\lambda)$ doesn't accept (so $\langle M\rangle\notin L_1)$, $N$ will accept no input string, so $L(N)=\varnothing$ and thus $\langle N\rangle\notin L_2$.

That's exactly what we need to establish the reduction $L_1 \le_\text{M} L_2$.


The meaning and relevance of the locution ''no terminating implementation'' in type theory

You can always inhabit a type by a free variable: the type $\tau$ is inhabited by the free variable $x_\tau$. When people speak about "implementation" of a type they mean a closed term, i.e., one without free variables. The examples you gave contain free variables, namely $b_a$.
In pure simply-typed $\lambda$-calculus all terms are "terminating" in the sense that the calculus is strongly normalizing, so whatever reductions you take they will always lead to the (unique) normal form.
In $\lambda$-calculus extended with recursive definitions (such as Haskell) we can inhabit every type $\tau$ with a closed term, for instance in Haskell the type t is inhabited by a defined as
a :: t
a = a

Once we have recursive definitions, it is easy to write closed terms that do not terminate (or do not have a normal form).


Relaxation of the null production restriction in Regular and Context Free Grammars

True.

For CFG we can remove in fact all epsilon rules and obtain the same family of languages, except for the empty word. That can be added by adding the $S\to\varepsilon$ production. It is a so-called normal form.

Like Raphael says: it all depends on what you want to express in the formalism, and what makes proofs convenient.

The definition on type-3 grammars is a matter of taste. I would prefer $A\to\varepsilon$, $A\to aB$ as these two types of productions correspond to final states and transitions in finite state automata.


The discrete version of your problem has a close resemblance with the classical Clustering problem. In Clustering given a finite set of points you have to divide the set such that points belong to a partition (cluster) iff they have similar properties.

We consider the continuous version, i.e, your problem. Let $2\epsilon < 1$ is error bound. And, we have a bounding box of size $n*n$ which we would like to partition based on functional values.

We divide the bounding box into $n/\epsilon*n/\epsilon$ grid cells, each cell has $\epsilon$ length side. Here we apply bottom up approach where the consecutive cells having same functional values are merged together. The partitioning algorithm is as follows.

i) For each grid cell $c$, compute function values in its four corner points. Let $x$ be the function value occurring most frequently among those four values (in case of tie choose one arbitrarily). Assign $x$ as a label to $c$.

ii) Start with the left and topmost grid cell. Iterate over cells from top to bottom and in a single row from left to right. In each cell $c$ if the cell on left and above (if exists) have same labels add $c$ to the cluster (partition) correspond to those cells (merging). Else if one of the left or above cell has same label add $c$ to the cluster (partition) of that cell. Otherwise start a new cluster with $c$.

You can see that the error may occur in boundary regions (between two partitions) of the partitioning and the merging procedure will give correct partitions. But, as the boundary consists of $\epsilon$ side length boxes the error is within tolerance limit.

Time complexity is $O((\frac{n}{\epsilon})^2)$.


Genetic algorithm neural networks converges, but suddenly stops

Well, I'm not an expert at genetic algorithms, but here's what I would check, coming from a neural networks perspective:

1) Learning rate (in your case, I think this is your mutation rate? Please correct me if I'm wrong). When a neural network exhibits this type of 'convergence', often you need to decay the learning rate either as a step function after a fixed number of iterations, or smoothly through exponential decay. Is that an option for you?

2) Initialization. Have you tried initializing your algorithm from different points and seeing if the convergence behaviour changes?

3) Adding noise. Sometimes you can get stuck in a poor local minimum, or at a saddle point. Small neural networks are more likely to get stuck in local minima. Saddle points proliferate in high-dimensional space. When learning stalls like this, adding some jitter to your parameter values and trying to learn from that new location can sometimes move you from a saddle point or local min to a better location in error space, and learning can continue from there.

4) Hyperparameter selection. How do you know your network is the correct size? Have you done some cross-validation to determine the number of hidden units you need, for example? Have you tried any kind of regularization?

Hopefully that provides some inspiration, or at least a starting point. Best of luck!


This is $\mathrm{NP}$-complete. Reduce from Independent Set instance $(G, k)$. Add a new universal vertex $v$ to $G$. Connect $v$ with a very long path (only to $v$ not to any original vertex of $G$). And set $k' = k + 1 + \mathrm{length\:of\:the\:long\:path}$, where length of the long path is the number of vertices in it.

Clearly, if the induced tree does not touch $v$ then it either only stucks in the long path or being confined to $V$. So, in order to have $k'$ vertices, it must include $v$ and the long path. Since $v$ is connected to all $V$, the set of vertices in $V$ that are included the induced tree must form an independent set.


Measuring and maintaining the diversity of individuals in Genetic Algorithm

How to rank the individuals of a population based on both diversity and fitness?

You can combine diversity and fitness into a single score: $$score(i) = fitness(i) + k \cdot diversity(i)$$

It's a standard approach and doesn't require significant changes to the algorithm. Unfortunately $k$ is problem-specific.

Alternatively change the standard GA to a multi-objective evolutionary  algorithm (MOEA).

This needs a lot of changes (e.g. the algorithm now needs to maintain a set of Pareto optimal individuals).

MOEA is probably a overkill for what you're doing. Indeed it's very interesting and a good training.

  Computing the diversity this way is expensive... What is a relatively optimal way for measuring the diversity of a population?

The genotypic / structural approach to diversity isn't the only workable one.

Instead of measuring how differently the individuals look like, measure how  differently those individuals behave (phenotypic diversity).

A great advantage is the ease of computation: often an acceptable approximation is the simple fitness value.

Schemes like Fitness Uniform Selection / Fitness Uniform Optimization generate selection pressure toward sparsely populated fitness regions, not necessarily toward higher fitness:

Evolution of the population under FUSS versus standard selection schemes (STD): STD may get stuck in a local optimum if all unfit individuals were eliminated too quickly. In FUSS, all fitness levels remain occupied
with “free” drift within and in-between fitness levels, from which new mutants are steadily created, occasionally leading to further evolution in a more promising direction (from "Fitness Uniform Optimization" - Marcus Hutter & Shane Legg).


Why each function may be computed with circuit with 2^n gates?

The meaning of the statement is that each function can be computed with at most $2^n$ gates; it doesn't anything about the minimal number of gates needed to compute any function.

That said, you can always add dummy gates to increase the number of gates in your circuit without changing the function it computes. For example, you can replace one of the inputs $x_i$ to $x_i \lor x_i$ to increase the number of gates by 1.


Assuming NP $\neq$ P, are there NPI languages only P languages reduce to?

I don't think such a language $L$ can exist, because it suffices to slightly modify it to get a language $L'\in L_c$ and not in $P$.
For instance let $u$ be a word of minimal length which is not in $L$, and take $L'=L\cup\{u\}$. It is clear that $L'$ polynomially reduces to $L$: check if the input word is $u$, and if it's not use your oracle for $L$. Since $u$ is of constant size, this algorithm runs in polynomial time. So $L'\in L_c$.
But you also have the inverse reduction: $L$ polynomially reduces to $L'$. This implies that $L'\notin P$, because otherwise $L$ would also be in $P$.


Both of your languages are context-free and not regular. The first one can be generated using the following grammar:
$$
S \to a S \mid a S b \mid aab
$$
The second one can be generated using the following grammar:
$$
S \to aaSbbb \mid aabbb
$$

You can show that these languages are not regular using the pumping lemma or using Myhill–Nerode theory. Let me briefly indicate how to do so using the pumping lemma.

For the first language, suppose it were regular. Let $p$ be the constant promised by the pumping lemma. Then the word $a^{p+1} b^p$ is in your language. According to the lemma, it can be written as $xyz$, where $|xy| \leq p$ consists solely of $a$'s, and $y \neq \epsilon$. But then $xy^0z$ is not in your language.

The second language is even simpler, and left to you.


How hash-table and hash-map are different?

If you ask me, you're correct and Wikipedia is wrong, as the complaints on the article's talk page (some 11 years ago!) clearly explain, but it was never fixed (or it was fixed and reverted).

A hash table stores items; these items can be keys (in which case it implements a set), or key-value pairs (in which case it implements a map, i.e. a hash map), or perhaps something else, e.g. triples; the Wikipedia article describes only the key-value case, while I was only taught the key-only case in class.

Some people do use hash table to mean hash map, so Wikipedia successfully describes a particular usage of the term; it should also describe the other cases. (It does describe how a hash map can be used to implement a set and other data structures, but that's not the same thing.)

In IT, most terms mean different things to different people, and most people using the term in one sense aren't aware that other people use it in another sense; hash table is no exception.


Non-deterministic TM and problems in class P

The class $P$ is a subset of $NP$. For an $NP$ algorithm to simulate $P$ in polynomial time, it does not even need to use nondeterminism, since a single branch can solve the $P$ problem.

It could be a bit confusing though when textbooks say that an $NP$ algorithm works in 'polynomial time'. But this refers to the amount of time it takes for a single branch to compute. But taken as a whole, $NP= \cup NTIME(n^k)$, while $P= \cup DTIME(n^k)$.


Does Multitape reduction to a one tape machine preserve space complexity?

You can take $C(k)=1$.

Simulate the $(k+2)$-tape machine (input, output, $k$ work tapes) by storing the $i$th character of all the simulated tapes in the $i$th character of the single tape. This is a standard construction, which also requires you to store the head positions using the characters on the tape. Now, you can do the whole computation without using any extra space.

In a little more detail, suppose you're simulating a Turing machine with tape alphabet $\Sigma$. Let $\Sigma'$ be the alphabet containing a character $a'$ for each character $a\in\Sigma$. We'll simulate using alphabet $(\Sigma\cup\Sigma')^{k+2}$, so each character on the simulating tape is a tuple $(c_1, \dots, c_{k+2})$. If $c_j\in\Sigma$, that means that the corresponding cell on the $j$th tape of the simulated machine contains that character; if $c_j=a'\in\Sigma'$, that means the cell contains character $a$ and that tape's head is in this position.

Note that it only makes to talk about space $\Omega(n)$ on single-tape Turing machines, since you now have to count the space used by the input.


Dijkstra shortest path yields unintuitive results

In the wikipedia article you linked, the final distance is only computed when the node is visited (step 6). The tentative distance is (re)calculated each time to visit a parent of a node, and overwritten if it's smaller (step 3).

So in your example,

We visit node 0.  We set tentative(1) = 0.2, tentative(3) = 0.5
We visit node 1, since it has the smallest tentative distance. We set tentative(2) = 1000.2
We visit node 3.  Since 0.6 < 1000.2, we set tentative(2) = 0.6
We visit node 2.  Its final distance is tentative(2), which is currently 0.6


Prove that {0^{n^3} | n≥0} is not context free

Gilles suggests a sophisticated method for solving this exercise, which is also the "proper" method; we will say more about it below. But let's start with applying the pumping lemma. The pumping lemma states that if $L$ is context-free then there exists some integer $n$ such that all words $w \in L$ of length at least $n$ can be written in the form $w = uvxyz$ with $|vxy| \leq n$ and $|vy| > 0$ (i.e. not both $v,y$ are empty), such that $uv^ixy^iz \in L$ for all $i \geq 0$.

Let's see what this means in your case. Suppose $L$ were context-free, and let $n$ be the integer given by the pumping lemma. Take some $m$ satisfying $m^3 \geq n$. Since $0^{m^3} \in L$ and the word has length at least $n$, we can write $0^{m^3} = uvxyz$ such that $|vy| > 0$ and $|vxy| \leq n$, and furthermore $uv^ixy^iz \in L$ for all $i \geq 0$. So $vy = 0^t$ for some $1 \leq t \leq n$, and for all $i \geq 0$, $0^{m^3-t+it} \in L$, that is, for all $i \geq 0$, $m^3 + (i-1) t$ is a cube. Your mission is to somehow reach a contradiction from this data.

Now for Gilles' proof. We can consider the language $L$ over the unary alphabet $\Sigma = \{0\}$. Parikh's theorem states that $L$ is context-free iff it is regular. The proof is not difficult: if $L$ is regular then it is context-free, and in the other direction you take a grammar for $L$ and massage it into an equivalent right-regular grammar; the idea is that $xy = yx$ if $x,y \in 0^*$.

The next step is to find a criterion for when a language $L_A = \{ 0^n : n \in A \}$ is regular. By considering a DFA for $L_A$, it is not hard to show that $L_A$ is regular iff $A$ is eventually periodic, that is, for some $a \geq 0$ and $b \geq 1$ it is the case that $x \in A$ iff $x + b \in A$ for $x \geq a$. This is not the case for the set of cubes, since the gap between adjacent cubes tends to infinity. We conclude that $L$ isn't regular nor context-free.


What does "post-image analysis" mean in the context of formal program analysis?

When working with transition systems,  $\text{post}(s)$ is the set of states that are reachable in a single step from the state $s$; if $S$ is a set of states,

$$\text{post}(S) = \bigcup_{s \in S} \text{post}(S).$$

Also, $\text{post}^*(s)$ is the set of states that are reachable from $s$, i.e., $\text{post}^*$ is the transitive closure of $\text{post}$.


How should we define the behavior of a Turing machine where the head tries to move left from the leftmost tape position?

There is no single accepted model of Turing machines. Different choices would lead to very similar models, which simulate each other with very small overhead. That's why we usually don't care so much about the exact model.

Here are some possibilities:

If the Turing machine attempts to move to the left of the origin, then the head stays put. The Turing machine might or might not be notified.
The Turing machine has a mechanism to detect that it has reached the origin, and cannot move to the left of it (the specs don't allow it).
Same, but not the machine can move to the left, and crashes if it attempts to do so (you decide how to interpret a crash – acceptance, rejection, infinite loop).
If a Turing machine attempts to move to the left of the origin, then instead it moves right. This makes sense if the Turing machine is guaranteed to always move at every step.

You can probably think of several other alternatives.


Is Post's Correspondence Problem decidable with fixed word size?

For all $m \geq 3$, the problem is undecidable.

Proof by reduction from the word problem of unrestricted grammars:

Take an arbitrary formal grammar. W.l.o.g. all left and right sides of rules have length at most $3$.

This can be seen by translating any grammar into an equivalent TM and then converting back.
Map the resulting grammar to PCP instances; no tile is longer than the longest left or right side of a rule.

That is, with step 1, all tiles have length $\geq 3$.


Binary Integer Programming question - what graph problem is represented

This answer assumes that $c_{ij} \geq 0$.

The first two sets of equations guarantees that $x_{ij}$ is a permutation matrix. It defines a permutation $\pi$ on $\{0,\ldots,n-1\}$ in the following way: $\pi(j) = i$ if $x_{ij} = 1$.

The set of inequalities is a logical implication: if $x_{ik}=x_{j(k+1)}=1$ then $z_{ijk} = 1$. That is, if $\pi(k) = i$ and $\pi(k+1) = j$ then $z_{ijk}=1$.

Since $c_{ij} \geq 0$ and the objective is to minimize $\sum_{ijk} z_{ijk} c_{ij}$, we want to have $z_{ijk} = 0$ unless we are forced to take $z_{ijk} = 1$. Therefore $z={ijk} = x_{ik} \land x_{j(k+1)}$. This means that the objective function is
$$
\min_\pi \sum_{k=0}^{n-1} c_{\pi(k)\pi(k+1)}.
$$
This is the problem known as minimum directed Hamiltonian circuit.


There are plenty of solutions online and in books. However, I’m
  curious to know about the fundamentals of this problem.

Basically, this problem is trying to reveal your ability to solve problems using recursive algorithms/divide&conquer for generating all possible permutations (brute-force). There are some filtering techniques that can be used in practice, but the worst-case running time is exponential.

  Is this problem essential asking for the Cartesian product of multiple
  sets? If so, what are some efficient algorithms to compute this?

Yes, one way to look at the problem is 'Cartesian product of multiple sets'. Given a string S, you can consider two sets a[i] and b[i], where a[i] is the set of character strings that can be made by substring S[1:i], and b[i] is the set of character strings that can be made by substring S[i+1,end]; then output the Cartesian product of a[i] and b[i] for every possible i.
However, this algorithm is not the best one.

  Some solutions reference DFS and BFS. How are DFS and BFS related to
  this problem (are they possibly referring to the type of recursion being
  used to solve the problem) ?

These algorithms use DFS for its recursive nature. Probably, it uses BFS to avoid stackoverflow.


Theta Manipulation to show $N = \Theta(n/\log N)=\Theta(n/\log n)$

There is not any strange thing here. As:

$$\frac{n}{\log(n)} = \frac{n}{\log(N\log(N))} = \frac{n}{\log(N)+\log(\log(N))} = \Theta\left(\frac{n}{\log(N)}\right) = O\left(\frac{n}{\log(N)}\right)$$

Therefore, all of them are true.


Minimizing a multivariate polynomial over the hyper-cube is NP-Hard

Hint: Modify your polynomial slightly so that (a) it is always negative, (b) its only zeroes are solutions to SAT.


Why in Declarative Programming variables are not reassigned?

This isn't as exotic as it sounds, and you can do it in a procedural language fairly easily.  The basic idea is just that instead of changing a value you just have a function return a new value.  For instance, instead of something like

string read()
{
  string s = '';

  while((string c = getchar()) != '\n')
  {
    s += c;
  }

  return s;
}

you could write something like

string read()
{
  string c = getchar();

  if(c == '\n')
  {
    return '';
  }
  else
  {
    return c + read();
  }
}

See how no variable ever gets reassigned here?

There are some subtleties here that I'm not going into, but I just wanted to illustrate that the idea is not that farfetched.


Breadth First Search actually require specifically Queue instead of any other type of Collection?

It doesn't literally have to be a queue. Anything that ensures that one level is completely explored before moving to the next one would suffice. However, the most natural way to do this is with a queue and any other implementation is going to be harder to describe and/or harder to implement than just "use a queue."

As evidence that it's harder to describe, note that your claim in the question that it suffices to ensure that the collection is empty before moving onto the next level is incorrect.  Consider the following tree.

    1
   / \
  2   3
  .   .
  .   .
  .   .

We start searching at node 1. We place its children 2 and 3 in the collection. So the collection isn't empty but it's definitely time to move on to the next level.

OK, how do we fix this? Well, we could have two collections: one for the current level and one for the nodes that need to be expanded at the next level. Each time we process a node at the current level, we add its children to the "next level" collection. When the current level is all done, the "next level" collection becomes the "current level" collection, and we start a new, empty, "next level". OK, that works, but it's harder to describe than using a queue. On the other hand, if you want to claim that it's easier to prove that the two-collection version is correct, you'd have a point. Really, everything is a trade-off.


Your statement "Integer x;" is syntactically "identifier identifier;" which is a perfectly fine variable declaration. Semantically, the first identifier must be defined as a type, and the second identifier must not be defined as a variable in the same scope. The first condition fails, therefore ...
And you might download a copy of the C Standard to check if "int main()" is acceptable, or whether it must be "int main(void)", which is preferable and might be required.


If I understand correctly (and I might not), it sounds like maybe the property you are trying to prove is

$$\forall G . C_1(G) \implies (\exists x . C_2(G,x) \land C_3(G,x))$$

where $G$ ranges over all graphs and $x$ ranges over all possible assignments to the program variables.

If that's right, then you can't check this with SAT or with CBMC.  It's a second-order formula, so you need a 2QBF solver to check it.  SAT can help you check properties of the form "$\forall x . F(x)$" and properties of the form "$\exists x . F(x)$", but for properties of the form "$\forall x . \exists y . F(x,y)$" or "$\exists x . \forall y . F(x,y)$", you need 2QBF (or, more generally, QBF).  There do exist 2QBF solvers, but checking 2QBF properties is much harder than checking SAT.

An additional complication is that it sounds like you want to quantify over all graphs of all sizes.

It sounds like you want to verify the following property: for all graphs, if C1 is true, then C2 and C3 are true.

The standard approach is to use assume and assert statements. You first write some assume statements that capture the assumption that the input graph satisfies C1. You then write some assert statements that capture the requirement that the C2 and C3 had better be true. The model checker checks whether there are any inputs that satisfy all the assume statements, and make at least one of the assertions false.

If you were going to use a SAT solver, you would search for a counterexample by writing a boolean formula C1 && not(C2 and C3), then asking the SAT solver to find a satisfying assignment for that formula. If it finds one, that it has found a counterexample to your property. If the formula is unsatisfiable, then your property holds. This all assumes that you are reasoning about graphs of a fixed size.

If the graph is of arbitrary size, then the problem is much harder.  That falls beyond SAT and beyond even QBF, as both SAT and QBF relate to formulas with a fixed (constant) number of boolean variables -- but if you want to reason about arbitrary-sized graphs, there is no encoding of that into a fixed number of boolean variables.  A standard heuristic is to check the property on graphs of size N for a few small values of N (say, for N=1,2,3,4,5,6,... until you run out of patience or the solver starts taking too long).


Finding stabbing numbers for lines for a set of segments in the plane

Are you familiar with

  H. Edelsbrunner, H. A. Maurer, F. P. Preparata, A. L. Rosenberg, E. Welzl, D. Wood.
  "Stabbing line segments."
  BIT Numerical Mathematics.
  1982, Volume 22, Issue 3, pp 274-281.
  (Springer link.)

Google Scholar finds more than 100 papers that cite it.

One can use a segment tree data structure, or an interval tree.
Segment trees offer $O(\log n + k)$ query time, where $k$ is the number of segments intersected. Space complexity is $O(n \log n)$.


In graph coloring you are looking for a partitioning of the vertex set into independent sets. Now, there are many arguably well-known similarly behaving (i.e., easy for $k=2$, hard for $k \geq 3$) problems where instead you want to find a partition into $k$ sets which could be (i) independent dominating, (ii) dominating, (iii) total nearly perfect, (iv) weakly perfect dominating, or (v) total perfect dominating, to name a few. Many of these problems also appear under different shorter names like "domatic number", "total domatic number", and so on. For more details, see e.g., the work of Heggernes and Telle [1, Table 1] (there's quite a bit of follow-up work as well).

Also, graph coloring is naturally linked to the classical and heavily-studied chromatic index (i.e., edge coloring) via the line graph. Further, deciding if a $k$-regular graph can be edge $k$-colored properly is NPC for every $k \geq 3$.

[1] Heggernes, Pinar, and Jan Arne Telle. "Partitioning graphs into generalized dominating sets." Nord. J. Comput. 5.2 (1998): 128-142.


Removing common background in image processing phase for classification

Try using clustering on the histogram of pixel color values.  I would suggest using $K$-means using $K=2$ as a starting point, but you could use any clustering algorithm.

You might want to convert to HSV color space, build a histogram of the hues, and apply clustering on those values.  You could also try other color space models, like CIELAB, but HSV is probably good enough for your purposes.  Working in HSV space tends to yield techniques that are more robust to variation in lighting/illumination.

In your examples, the majority class (the cluster containing the majority of pixel values) is the background.  You could use heuristics, such as that the cluster that contains the majority of pixels along the boundary of the image is more likely to be the background.

The watershed algorithm or other methods of image segmentation could be an alternative approach that might work well.

If your images are as clean as shown in the example, almost anything should work well.


How to prove that the erosion of a convex set by a convex set will result in a convex set?

(Convexity is closed under intersection) Given a family of convex set $C_i$, where $i\in I$ for some index set $I$, then $\cap_{i\in I}C_i$ is convex.

In other words, the intersection of convex sets are convex.

Proof. Suppose two points $p$ and $q$ are in $\cap_{i\in I}C_i$. That is, for each $i\in I$, $p\in C_i$ and $q\in C_i$. Consider $L$, the line segment between $p$ and $q$. By the definition of convexity, $L\subseteq C_i$. That is $L\subseteq \cap_{i\in I}C_i$. By the definition of convexity again, $\cap_{i\in I}C_i$$ is convex.

(Convexity is closed under translation) If $C$ is a convex set, then $C_t=\{x+t\mid x\in C\}$ is also convex.

In other words, if you translate a convex set, you will get a convex set.

Proof is skipped.

(Convexity is closed under erosion) Suppose $A$ is a convex set. Let $B$ be another set. Then the erosion of $A$ by $B$ is convex.

Proof. I will let you figure out given the above two lemmas. Another hint is given in the statement itself, which is, you do not need $B$ to be convex at all.

Is the erosion of $A$ by $B$ always empty?

Imagine both $A$ and $B$ are disks centered at the origin. $A$ is a huge while $B$ is a very small. Then the "erosion" by $B$ can only remove a small stripe along the circumference of $A$. The inner part of $A$ will not be "eroded". So the erosion of $A$ by $B$ will keep a significant part of $A$.

You can also check an example on Wikipedia.


Average number of slots needed in slotted-Aloha

The protocol you are describing is most probably CSMA or slotted ALOHA.

As @wece mentioned, you need also to specify what you do in case of conflict (this is also the main difference between the above mentioned protocols). I would assume that a station sends regardless of the link-status and that a station will retransmit in the next slot with same probability $p_{i}$ in case of collision. This is basically what happens in slotted ALOHA, just that you have individual transmission probabilities for you stations.

You would not refer to the specified protocol as TDM (time division multiplexing), because the channel access is non-deterministic and non-repetitive, although you do have fixed time slots.

To your calculative questions:

1) Station 1 has 2 packets to send:
The probability that 1 successfully transmits to 2 is:

$$P(transmit_{1,2})=P(send_{1})*(1-P(send_{2}))$$

Since we have no packets at station 2, $P(send_{2})$ is zero. This is repeated over potentially many slots, always with probability $p_{1}=0.5$ that 1 will send in a slot. Note that this is the same problem as a simple coin toss. The expected number of sends in n tries (if we had infinite packets at 1) is $E=n*p$. Let's look at only one packet: We only want to know how many tries it takes on average. We can therefore write: $n=E/p$. This yields 2 tries on average for station 1. We can thereafter reason exactly the same way for the second package, because there is no statistical dependence between the events. We thereby obtain #tries = 4. (The same problem for station two would yield 4 + 4 tries.)

2) Now two stations want to send. We therefore have ($\neg$ means not):

$$ P(send_{1}\&send_{2}) = \frac{1}{2}*\frac{1}{4}=\frac{1}{8} $$
$$ P(send_{1}\&\neg send_{2}) = \frac{1}{2}*\frac{3}{4}=\frac{3}{8} $$
$$ P(\neg send_{1}\&send_{2}) = \frac{1}{2}*\frac{1}{4}=\frac{1}{8} $$
$$ P(\neg send_{1}\&\neg send_{2}) = \frac{1}{2}*\frac{3}{4}=\frac{3}{8} $$

Only the middle two give a first correct transmission. As in the previously calculation we see that we need 2 tries (or time slots) on average for this to happen. Once this happened, we are back to the first problem, sending one packet with the other station being quiet.

However, at this point it could have been the first or the second station which sent the first packet. We therefore need to account for it: We have 3/4 cases where it was station 1 and 1/4 cases where it was station 2 which transmitted correctly in the first step. This means we can simply add up the number of tries as:
$$\#tries_{first-packet} + \#tries_{second-packet-from-1}*p_{second-packet-at-1} + \#tries_{second-packet-from-2}*p_{second-packet-at-2}$$
$$= 2 + 2 * \frac{1}{4} + 4 * \frac{3}{4} = 5.5$$


Data structure to hold and retrieve points in a plane

Solution outline:

We will maintain two AVL trees.

Tree_X: will hold points sorted by their X coordinate.
Tree_Y: will hold points sorted by their Y coordinate.

Each node within both trees will hold the following additional data:

Number of leaves in left sub-tree.
Number of leaves in right sub-tree.

For a point $(x,y)$ we will define regions $A$ ,$B$, $C$, $D$:

Point $(x',y')$ is in $A$ if $x' < x$ and $y' > y$.
Point $(x',y')$ is in $B$ if $x' > x$ and $y' > y$.
Point $(x',y')$ is in $C$ if $x' < x$ and $y' < y$.
Point $(x',y')$ is in $D$ if $x' > x$ and $y' < y$.

Now it is clear that Score(x,y) = |C|-|B|.
However $|A|+|C|$, $|B|+|D|$, $|A|+|B|$, $|C|+|D|$ could be easily retrieved from our two AVL trees, as we will soon see.
And notice that $\frac {(|A| + |C| + |C| + |D|) - (|A| + |B| + |B| + |D|)}{2} = |C|-|B|$

Implementation of required operations:

Add(x,y) - We will add point (x,y) to both of our AVL trees. Since the additional data we are storing is affected only on the insertion path and since the insertion occurs in (logn), the total cost of Add(x,y) is O(logn).
Remove(x,y) - We will remove point (x,y) from both of our AVL trees. Since the additional data we are storing is affected only on the removal path and since the removal occurs in (logn), the total cost of Remove(x,y) is O(logn).
Score(x,y) - I will show how to calculate $|B|+|D|$ as others done in similar way and same complexity costs. It is clear that $|B|+|D|$ is the number of points which satisfy $x' > x$. To calculate this number we will:

Find x in AVL_X. Complexity O(logn).
Go upwards in Tree_X until the root and on each turn right we will sum the number of elements in left sub-tree of the son. Complexity O(logn).

Total cost of Remove(x,y) is O(logn).


Converting context-free grammar to Chomsky/Greibach Normal Form

You can convert a context-free grammar into Chomsky normal form or Greibach normal form in whatever way you wish (converting a grammar to a normal form means finding a grammar in the normal form which generates the same language as the original grammar). A given algorithm might require you first to remove lambda productions, or first to convert to Chomsky normal form. If using a specific algorithm, you have to follow whatever the algorithm prescribes.


What could you learn from studying player movement and behaviour on online FPS games?

File each given vector function with the win/loss of the game and the team each vector was on.
Applications of this data: To gauge map balance and provide the least advantage to any one particular team.

Determine how particular elements of the map effect balance.

Make bots more effective by determining common strategies employed against bots, and the manner in which players address situations (going with the counter strike example: We're down players lets group up on the objective).

It would be interesting to see which would provide better balance or more effective bots, conventional testing or this in-depth vector analysis.


How to prove intersection between languages L1 (belongs to NP) and L2 (belongs to P) actually belongs to NP?

You can prove something more, intersection of two NP languages is also in NP.

Suppose you have polynomial time non-deterministic turing machines $M_1$ for $L_1$ and $M_2$ for $L_2$. We can modify $M_1$ as follows: Whenever any non-deterministic thread of $M_1$ accepts input string, say $w$, we run $M_2$ on $w$, if $M_2$ then accepts $w$, accept the input, otherwise reject.

The resulting machine is polynomial time non-deterministic.


Can not understand idea of the KMP algorithm

Sedgewick continues: "These are
pattern characters that we know, so we can ﬁgure out ahead of
time, for each possible mismatch position, the state where we
need to restart the DFA."

What I understand is that this quote tries to explain that if you encounter a mismatch at letter at position $j$ of the pattern you have to shift the patterns by one position against the text and see where that leads us. The point there is that we do not need to know the actual text at that moment, because we know that so far the patterns has matched the text and we can match the pattern to itself (shifted).


Why isn't P and P/poly trivially the same?

The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C_0, C_1, C_2, \dots$ such that the circuit $C_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $C_i$ and $C_{i+1}$: they could be completely different. In particular, for any set $S\subseteq\mathbb{N}$, you could set declare $C_i=\mathrm{true}$ if $i\in S$ and $C_i=\mathrm{false}$ for $i\notin S$. Even if $S$ is undecidable!

In contrast, a language is in $\mathrm{P}$ if there is a single Turing machine that tells you whether every possible input of every possible length is in the language. Now, you can't play any funny games about inputs of different lengths.

You're correct that we can evaluate any fixed circuit in $\mathrm{P}$. But that's not necessarily enough to decide a language in $\mathrm{P/poly}$. To do that, we would first need to compute the length of the input, then use that to determine which circuit $C_i$ we need to evaluate, and then evaluate the circuit. As the example above shows, the "determine which circuit" part might not even be computable, let alone computable in polynomial time.


Solving a recurrence relation with T(n) = 2 * T(n/3) + 5n


swapping between sorting algorithms for small input size left over

People don't usually program their own sorting routines, and I would advise against it, unless you're implementing a non-comparison-based sort such as counting sort. Library sorting routines are optimized beyond what the casual programmer can achieve.

If you're interested in the best practices of the field, you'll have to look at library sorting routines. For example, python uses Timsort, which switches to insertion sort for small arrays. The GNU implementation of Quicksort also switches to insertion sort for small arrays. So it seems switching to insertion sort for small arrays is indeed advisable.


What is the regular expression for the following language?

I claim that $L$ is equal to the set of all strings of the form $a\gamma b\gamma$, where $a,b \in \{0,1\}^+$ and $\gamma \in \{0,1\}$. Indeed, a string of this form clearly belongs to $L$. Conversely, if $acbc \in L$ and $c=d\gamma$, then $acbc = ad\gamma bd\gamma$ belongs to the new set. The new set is clearly described by the regular expression
$$ (0+1)^+0(0+1)^+0 + (0+1)^+1(0+1)^+1. $$


Recognizing strongly connected digraphs in NL

Because nondeterministic space classes are closed under complementation by the Immerman–Szelepcsényi theorem. So, you can't literally just invert the answer from $\text{PATH}(a,b)$ but the fact that there is an $\mathrm{NL}$ algorithm for $\text{PATH}(a,b)$ implies that there is also an $\mathrm{NL}$ algorithm for $\text{NOT-PATH}(a,b)$, and you use that.


minimize sum of primes with a lower bound on product

I'll suggest a very simple and very fast algorithm that I believe produces the correct result unless n is very large.

Step 1: If n = 1 the solution is {}. If n = 2 or n = 3 the solution is { n }. Otherwise, find the smallest prime p such that the product of the primes from 2 to p is ≥ n. Let S = the set of primes from 2 to p, let P = the product of the primes from 2 to p. If p < 2n then the result is S.

Otherwise, let r be the largest prime such that P / r ≥ n. Also, let q be the smallest prime > p, and let r' be the largest prime such that (P * q / p) / r' ≥ n. If r' - r > q - p then the result is S + { q } - { r', p }, otherwise the result is S - { r }.

The first n where this doesn't give the optimal solution is n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1 ≈ $2.622·10^{36}$.

Reasoning: We would want to use the smallest primes possible, because the ratio P / log p grows as p grows (with the exception of the primes 2 and 3). The exception is when we have a product that is quite a bit larger than n, and may get a product closer to n with a smaller sum.

If P < 2n, then we might replace p with a larger prime q and remove the prime 2 from the product. But q ≥ p + 2, so the sum of primes will not get smaller.

If P ≥ 2n, then removing the largest possible prime from the product will obviously make the product smaller. This does not give the optimal solution if for example P / 7 ≥ n but P / 11 < n, the next prime after p is q = p + 2, and replacing p with q in the product means that (P * q / p) / 11 ≥ n. In this case we increased the sum by 2 replacing q with p, and decreased it by 4 replace r with r'. But the algorithm will find this case.

This does not detect the case where replacing p with the next prime after q would improve the sum. Let q be the smallest prime > p, and q' the smallest prime > q. We know that q' ≥ p + 6 because p, p+2 and p+4 cannot all three be prime. So we might not find the optimal solution if the prime after r is r+8.

This is the case for the first time when r = 89 and the next prime is 97 = p + 8. If p = 101, then q = 103 and q' = 107 = p + 6. So take n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1: We need all the primes up to p = 101 to have a product P ≥ n. We can leave out r = 89 from that product, but not 97 because the remaining product is much smaller than n. If we exchange 103 for 101, we still cannot remove 97 because the product would be n-1. But we can exchange 107 for 101 and remove 97 instead of 89 from the product, getting a sum that is smaller by 2. So the optimal solution here is { 2, 3, ..., 83, 89, 107 } where the algorithm will return { 2, 3, ..., 83, 97, 101 }.


Polytime and polyspace algorithm for determining the leading intersection of n discrete monotonic functions

Determining whether two monotone functions given as programs intersect is non-computable. Similarly, determining the first intersection under the promise that it exists is "arbitrarily hard" (definitely not polytime).

Given a program $P$, define a function $f_P$ which, for input $n$, is $1$ if $P$ stops after $n$ steps or less. The first intersection of $f_P$ and the constant function $1$ is the running time of $P$, if $P$ halts. So no program can decide whether $f_P$ and $1$ intersect.

Similarly, the time hierarchy theorem shows that for no recursive time bound $T$, the first intersection point can be found in time $T$, even under the promise that it exists. Using the space hierarchy theorem, you can get the same for space.


It looks like you have 3 symbols in your language: a, b, and \lambda.  But your transition table only has the symbols a and b.  You need to add \lambda to your transition table and integrate that into your diagram.  That should help some.


Brzozowski's algebraic method is safe as long as you don't have epsilon transitions. It even works if your transitions are labelled by languages not containing the empty word. It may also work if some transitions contain the empty word, as long as you can eliminate them, as in the example below:

the system can be written as
\begin{align*}
 X_1 &= (a^*b + a)X_2 + b^*X_3 \\
 X_2 &= (a+b)X_1 + bX_3 + 1 \\
 X_3 &= aX_1 + aX_2 + 1
\end{align*}
Replacing $X_3$ by $aX_1 + aX_2 + 1$, and observing that $a + b^*a =
b^*a$, we obtain the equivalent system
\begin{align*}
 X_1 &= (a^*b + a)X_2 + b^*(aX_1 + aX_2 + 1) = b^*aX_1 + (a^*b + b^*a)X_2 + b^* \\
 X_2 &= (a+b)X_1 + b(aX_1 + aX_2 + 1) + 1 = (a + b + ba)X_1 + baX_2 + b + 1\\
 X_3 &= aX_1 + aX_2 + 1
\end{align*}
We deduce from the second equation
$$
 X_2 = (ba)^*((a + b + ba)X_1 + b + 1)
$$
and replacing $X_2$ by its value in the first equation, we obtain
\begin{align*}
 X_1 &= b^*aX_1 + (a^*b + b^*a)(ba)^*((a + b + ba)X_1 + b + 1) + b^*\\
   &= (b^*a + (a^*b + b^*a)(ba)^*(a + b + ba))X_1 + (a^*b +
   b^*a)(ba)^*(b + 1) + b^*
\end{align*}
Finally, the language recognised by the automaton is
$$
 X_1 = \bigl(b^*a + (a^*b + b^*a)(ba)^*(a + b + ba)\bigr)^*[(a^*b +
 b^*a)(ba)^*(b + 1) + b^*]
$$
since $1$ is the unique initial state.

Now, if you want to implement this algorithm, you may end up with more complicated regular expressions. For instance, the sentence "observing that $a + b^*a = b^*a$" might be difficult to implement. Other useful simplifications
like $a^* + 1 = a^*$ or even $K + K = K$ or $K + L = L + K$, where $K$ and $L$ are regular expressions, are also not easy to implement and require more sophisticated rewriting systems.


What are the possible sets of word lengths in a regular language?

First, an observation which is not crucial but convenient: the set $\mathscr{S}$ of sets of integers that are $LS(L)$ for some regular language $L$ on a non-empty alphabet $\mathscr{A}$ does not depend on the choice of alphabet. To see that, consider a finite automaton that recognizes $L$; the lengths of the words that are in $L$ are the lengths of the paths on the automaton seen as an unlabeled graph from the start state to any accept state. In particular, you can relabel every arrow to $a$ and get a regular language with the same length set over the alphabet $\{a\}$. Conversely, if $L$ is a regular language over a one-element alphabet, it can be trivially injected into a larger alphabet, and the result is still a regular language.

Therefore we are looking for the possible length sets for words over a singleton alphabet. On a singleton alphabet, the language is the length set written out in unary: $\mathrm{LS}(L) = \{n\in\mathbb{N} \mid a^n \in L\}$. Such languages are called unary languages.

Let $L$ be a regular language, and consider a deterministic finite automaton (DFA) that recognizes $L$. The set of lengths of words of $L$ is the set of lengths of paths in the DFA seen as a directed graph that start on the start state and end in one of the accept states. A DFA on a one-element alphabet is pretty tame (NFAs would be wilder): it's either a finite list or a circular list. If the list is finite, number the states from $0$ to $h$ following the list order; if it's circular, number the states from $0$ to $h$ following the head of the list, and $h$ to $h+r$ along the loop.

Let $F$ be the set of indices of accept states up to $h$, and $G$ be the set of indices of accept states from $h$ to $h+r$. Then

$$\mathrm{LS}(L) = F \cup \{ k \, r + x \mid x \in G, k\in\mathbb{N} \}$$

Conversely, let $h$ and $r$ be two integers and $F$ and $G$ be two finite sets of integers such that $\forall x \in F, x \le h$ and $\forall x \in G, h \le x \le h+r$. Then the set $L_{F,G,r} = \{ a^{k\,r+x} \mid x\in G, k\in\mathbb{N} \}$ is a regular language: it is the language recognized by the DFA described above. A regular expression that describes this language is $a^F \mid a^{G} (a^r)^*$.

To summarize in English, the length sets of regular languages are the sets of integers that are periodic¹ above a certain value.

¹
To hang on to a well-established notion, periodic means the characteristic function of the set (which is a function $\mathbb{N}\to\{\mathtt{false},\mathtt{true}\}$ which we lift to a function $\mathbb{Z}\to\{\mathtt{false},\mathtt{true}\}$) is periodic. Periodic above a certain value means that the function restricted to $[h,+\infty[$ can be prolonged into a periodic function.


Why does arithmetic left shift of negative number leads to positive number?

$01100 \Rightarrow +12$, not $+24$.

And it is $+12$ because $32-20=12$. With $5$ bits and $2$s complement you can only represent numbers in the range $-16$ to $+15$. You have overflowed this range and, in effect, "run around" to the other end and into the positive number range.


Prove correctness of recursive Fibonacci algorithm, using proof by induction

(Seems like it may be a duplicate, but the "Related" questions don't seem to be too close, with the possible exception of "this one)

The proof is by induction on $n$. Consider the cases $n = 0$ and $n = 1$. In these cases, the algorithm presented returns $0$ and $1$, which may as well be the 0th and 1st Fibonacci numbers (assuming a reasonable definition of Fibonacci numbers for which these values are correct).

Now, assume that the algorithm returns the correct Fibonacci number for all $n$ (i.e., the nth Fibonacci number) for all $n \leq k$ where $k \geq 1$.

We must show that the algorithm returns the correct value for $k+1$, i.e., the (k+1)th Fibonacci number. By the induction hypothesis, $k \geq 1$, so we are in the else case. We return Fibonacci(k) + Fibonacci(k-1) in this case. By the induction hypothesis, we know that Fibonacci(k) will evaluate to the kth Fibonacci number, and Fibonacci(k-1) will evaluate to the (k-1)th Fibonacci number. By definition, the (k+1)th Fibonacci number equals the sum of the kth and (k-1)th Fibonacci numbers, so we have that the algorithm returns the (k+1)th Fibonacci number on input $k+1$.

The proof of the claim follows by induction on $n$.


Using saved registers at the main function with no other function calls [RISC-V]

Calling conventions may be called "convention", but they are rules. The reason they are called "convention" is because each compiler uses a different one, once a convention was chosen - it acts as rules.
Regarding the particular case of "main", it's being called by the operating system, so convention must be obyed.


A document is modeled as a set $d$ of words.  Since we're maximizing $f(w,d)$ over all $w\in d$, this means that $w$ ranges over all possible words contained in $d$.

In the future, please check a textbook before asking.  We expect you to do some research on your own before asking, and this is a standard topic that's well-covered in standard explanations of tf-idf.


You could use MindNode or OmniGraffle (though OmniGraffle is more expensive), although these are more oriented towards mind-mapping than for flowcharting.

If you were looking for a free, web-based software, I've heard draw.io works pretty well. There really isn't much choice for macOS unfortunately, after all.


Efficient way to get integral points of segment from two points in grid

For a line segment defined by two integral lattice points $(x_0,y_0), (x_1,y_1)$ there will be $gcd(y_1-y_0,x_1-x_0)-1$ additional integral points along the line segment.
To find them move along line by largest value in the reduced slope.


Shortest-Path for Weighted Directed Bipartite Graphs

Merge every zone into one vertex. You now have a linear path, with one or multiple edges between each vertex. Since this graph does not branch, you can simply choose the cheapest edge between every vertex directly.

A small illustration I made:


First of all, it is not necessarily true that on average half a block is wasted. The main reason why this is false is that for small files it might be the case the more than half a block is wasted on average. Moreover, this is your main worry regarding this wastage, since is you waste half a block per large file, the fraction of blocks wasted is actually quite small. So you have to worry mainly about small files, whose size is at most a handful of blocks, and most of all for files whose size is much smaller than one block.

Second, you're asking how the index block structure can be modified to reduce this wastage. Here it's your time to be creative. One idea is to have special blocks for storing small files. I'll let you flesh this idea out. Another idea is to allow the first block of a file to start at the middle, so that two files can share one block. Of course this becomes somewhat problematic when files are updated.


Detecting spoken words in audio stream or file?

Its a huge field.  Basics are to convert the audio into a spectragraph (a Fourier transform).  That highlights what frequencies are present in the signal and at what intensities.  From this you break up windows (wavelets in some models) and learn to identify the phonemes from these.  Phonemes are the names for the types of sounds you can make with your mouth.  There is a lot biology in this, how air leave your mouth, if your tounge is against the roof of your mouth, behind your teeth etc.  This all affects what frequencies result and subsequently you see those in the spectrograph.  With experience you can read phonemes right off from these graphs.

Phonemes are not letters in a written alphabet, they are an alphabet all their own.  But the work of linguist have decoded what phonemes emerge from pronouncing words.  It is tricky business because unlike written words, when we speak one words phonemes can blend with the start of another.  So detecting single words is actually involved.  You instead start to score the likelihood of a sequence of phonemes and work back to the most probable sequence.  This can be done with hidden Markov models, but the rise of neural nets might be changing what's the best approach here.  But certainly this is the place that becomes language specific.

A final common component is domain and grammar.  Producing text from speech works best if there is an expectation that the words come from a limited domain, such as ordering your pizza or sending text messages.  Again the linguist have to help by providing language models that map spoken language (often quite different from rules of written language) to likely sequences of words.  Pauses and intonation have to provide clues for punctuation.  So there is a lot of training and retraining to do within a domain to get it work.

Of the list of things here about the only one that springs to mind as "go do it yourself" would be to read in an audio stream and produce the spectragraph.  That much is classical signal processing and calculus.  As for phonemes, linguistic, random models, and machine learning... those seem to me to be specialist material.

Well at least this is how it was done in broad strokes years ago when I was peripherally involved.  I'm sure it has advanced but hope this gives some help.