Does NP = coNP imply the collapse of PH to level 1?

No.  $PH=NP$ doesn't imply $P=NP$, because $PH$ is not the same class as $P$.

Roughly speaking, $PH$ includes $P$, $NP$, $coNP$, and more: $PH$ includes $\Sigma_i$ and $\Pi_i$ for all $i$.  Formally, $PH$ is defined as

$$PH = \Sigma_0 \cup \Pi_0 \cup \Sigma_1 \cup \Pi_1 \cup \Sigma_2 \cup \Pi_2 \cup \cdots.$$

If $NP=coNP$, then we have $\Sigma_1=\Pi_1$, and by Proposition 3.10, we have $\Sigma_1=\Sigma_2=\Sigma_3 =\cdots=NP$ and $\Pi_1=\Pi_2=\Pi_3=\cdots=coNP=NP$, so

$$\begin{align*}
PH &= \Sigma_0 \cup \Pi_0 \cup \Sigma_1 \cup \Pi_1 \cup \Sigma_2 \cup \Pi_2 \cup \cdots\\
&= P \cup P \cup NP \cup NP \cup NP \cup NP \cup \cdots\\
&= NP.
\end{align*}$$


If $m > 0$ is even then the two parties communicate $m/2$ times at their first round of communication. If $m > 1$ is odd then they communicate $(m-1)/2$ times at their first round of communication. In particular, the communication complexity is not $O(\log m)$, but at least $\Omega(m)$. In fact, it is also $O(m)$, but you'll have to figure out why yourself.


Run time of recurrence with five uneven calls

I'll offer up a more general claim and a proof, you can apply it to your scenario as needed.

The Uneven Split Theorem

Let $c$ and $k$ be positive constants.

Then let $\{a_1, a_2, \dots a_k\}$ be positive constants such that $\sum_1^k a_i < 1$.

We also must have a recurrence of the form:

$$\begin{align}
T(n) & \leq c & 0 < n < max\{a_1^{-1}, a_2^{-1}, \dots a_k^{-1}\}\\
T(n) & \leq cn + T(a_1 n) + T(a_2 n) + \dots T(a_k n) & n \geq max\{a_1^{-1}, a_2^{-1}, \dots a_k^{-1}\}
\end{align}$$

Claim

Then I claim $T(n) \leq bn$ where:

$$b = \frac{c}{1 - \left(\sum_1^k a_i\right)}$$

Proof by Induction

Basis: $n < max\{a_1^{-1}, a_2^{-1}, \dots a_k^{-1}\} \implies T(n) \leq c < b < bn$

Induction: Assume true for any $n' < n$, we then have

$$\begin{align}
T(n) & \leq cn + T(\lfloor a_1 n \rfloor) + T(\lfloor a_2 n \rfloor) + \dots + T(\lfloor a_k n \rfloor)\\
& \leq cn + b \lfloor a_1 n \rfloor + b \lfloor a_2 n \rfloor + \dots + b \lfloor a_k n \rfloor\\
& \leq cn + b a_1 n + b a_2 n + \dots + b a_k n\\
& = cn + bn \sum_1^k a_i\\[0.5em]
& = \frac{cn - cn \sum_1^k a_i }{1 - \left(\sum_1^k a_i\right)} + \frac{cn \sum_1^k a_i}{1 - \left(\sum_1^k a_i\right)}\\[0.5em]
& = \frac{cn}{1 - \left(\sum_1^k a_i\right)}\\
& = bn & \square
\end{align}$$

Then we have $T(n) < bn \implies T(n) = O(n)$.

We also know $T(n) = \Omega(n)$ by the recurrence definition, therefore $T(n) = \Theta(n)$.

Next apply it to your recurrence of the form:

$$T(n)=cn + T\left(\frac{n}{5}\right) + T\left(\frac{n}{5}\right) +T\left(\frac{n}{10}\right) + T\left(\frac{n}{10}\right) + T\left(\frac{n}{10}\right)$$

I'll leave this for you to figure out the $a_k$'s and $b$.

A pretty quick rule of thumb if the work done per recursion is linear $(cn)$:

If the constants in the recursion calls sum to less than $1$, it's $O(n)$.
If the constants sum to exactly $1$, it's $O(n \log n)$.


If your keys are strings, you can use a prefix tree mapping keys to values. In this way each operation can be implemented in $O(h)$ time, where $h$ is the length of the key, which means it is $O(1)$ to the size of the collection.
To get the minimum key(or maximum) you can traverse the tree, by going through the edge from the lexicographically smallest (or largest if you need max) node on each level.
 I don't think you can get better complexity than $O(h)$ for arbitrary sized keys as you need $O(h)$ time to output the key anyway.


Complexity to generate every combination of every size for a given sequence

Each element in the sequence is part of the combination or not (a binary choice). Since there are $n$ elements, this gives $2^n$ possible combinations.

Using a gray code to iterate over the elements we can make sure that we iterate over every possible combination by only putting in or taking out a single element every time.

Assuming your elements are numbered $1\dots n$ we can use the following algorithm. If our current combination $C_k$ contains an even amount of elements, toggle element $1$ to get $C_{k+1}$. Otherwise, toggle element $\min(C_k)+1$ to get $C_{k+1}$.

Starting from the empty combination $\{\}$ we get:

\begin{matrix}
\{\} & \text{even} & \text{toggle $1$}\\
\{1\} & \text{odd} & \text{toggle $\min(\{1\}) + 1$}\\
\{1, 2\} & \text{even} & \text{toggle $1$}\\
\{2\} & \text{odd} & \text{toggle $\min(\{2\}) + 1$}\\
\{2, 3\}  & \text{even} & \text{toggle $1$}\\
\{1, 2, 3\} & \text{odd} & \text{toggle $\min(\{1, 2, 3\}) + 1$}\\
\{1, 3\}  & \text{even} & \text{toggle $1$}\\
\{3\} & \text{odd} & \text{toggle $\min(\{3\}) + 1$}\\
\cdots & \cdots &\cdots
\end{matrix}

By separately storing whether we are currently even/odd and flipping it, and storing our combination in sorted order we can always get to the next combination in $O(1)$ time. So it simply takes $O(2^n)$ time to generate all combinations.


Algorithm to minimize surface area, given volume

Here is a modified version of a "choose divisor near cube root" algorithm.  It still must brute force many cases, so I'm not sure how much of a real improvement it is speed wise over the enumeration of all cases.  However, I submitted it as a correction to the algorithm on OEIS (that which generated incorrect results) because I believe it should be accurate at least.

Here is the algorithm to find (s1,s2,s3) and surface area of a rectangular prism given its volume n:

Given n, find the cube root.
Set an initial value integer s1 at the ceiling of that cube root.
Test to see if s1 is a divisor of n, and if not, reduce s1 by 1.
If a divisor s1 is found, set an initial s2 to be the ceiling of the square root of (n/s1).
Then test to see if s2 is a divisor of n/s1, and if not, reduce s2 by 1.
When a divisor s2 is found, s3 then is set to n/(s1*s2).
The current surface area is calculated by 2*(s1*s2 + s1*s3 + s2*s3).
The current SA is compared against the current minimum.  If its the first surface area calculated, it is stored as minSA. After the first, we test to see if the current SA is smaller than minSA, and if so, store it in minSA.

This algorithm enumerates some of the triples (s1,s2,s3) but needs only to test the divisors under the cube root. (Since not all three divisors can be above the cube root).  In a similar fashion, s2 needs only to test divisors of n/s1 under the square root of n/s1, since not both divisors can be above the square root)

A note on step 3: if the cube root is a divisor then n is a cube and we can stop there with minimal surface area 6*s1^2 from the box (s1,s1,s1).

Python:

import math
def minSArectprism(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0)))
    minSA=-1
    s1 = s1_0
    while s1>=1:
        while n % s1 > 0:
            s1 = s1 - 1
        s1quot = int(n/s1)
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2>=1:
            while s1quot % s2 > 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))
            SA = 2*(s1*s2 + s1*s3 + s2*s3)
            if minSA==-1:
                minSA=SA
            else:
                if SA<minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1
    return minSA


constructing a DFA and a regular expression for a given regular language

I was able to solve this question using two possible routes.

The 1st route involves constructing the DFA by using the intersection operation on the simpler parts of $D$, i.e.,

$\{$even number of $a$'s$\} \cap\{$odd number of $b$'s$\}\cap\{$does not contain the substring $ab\}$

After that, I was able to reduce the DFA into a RegEx using the State Elimination Method and Arden's Lemma. The regular expression can be achieved by using Arden's Lemma as follows.

$$1\to a2+b4$$

$$2\to a2+b2$$

$$3\to a5+b2+\varepsilon$$

$$4\to a5+b1+\varepsilon$$

$$5\to a3+b2$$

Note that $2\to a2+b2$ will resolve as $2\to \varnothing$ and not $2\to (a+b)^*$.

The 2nd route involves "knowing" that the regular expression is $b(bb)^*(aa)^*$ by analyzing the language $D$. This RegEx can be converted to an ε-NFA. After that, we can convert this ε-NFA to get a DFA which when minimized would give us this.


$\textsf{EvenSat}$ is $\oplus P$-Complete (pronounced "Parity $P$"). The way to see this is (i) that it is the complement of $\textsf{OddSat}$, which is "the" natural $\oplus P$-Complete problem in the same way $\textsf{Sat}$ is "the" natural $\mathcal{NP}$-Complete problem, and (ii) $\oplus P$ is closed under complement.
The Valiant-Vazirani Theorem gives a randomized Cook reduction (i.e., a many-one reduction) with a one-sided error probability of $\mathcal{O}(1/n)$ from $\textsf{Sat}$ to $\textsf{EvenSat}$. That is, $\textsf{EvenSat}$ is $\mathcal{NP}$-Hard under randomized reductions. This is why the Valiani-Vazirani Theorem is usually stated as $\mathcal{NP}\subseteq \mathcal{RP}^{\oplus P}$.
We have $\mathcal{RP}^{\oplus P}\subseteq P^{\#P}$, so VV's Theorem is a bit tighter than what you would get from Toda's Theorem.
It is unlikely that $\textsf{EvenSat}$ is $\mathcal{NP}$-Complete, because then the polynomial hierarchy collapses to the first level, $PH=NP$. It is an open question whether $NP$ and $\oplus P$ are comparable, so far there is only oracle evidence that they are incomparable. (I don't know whether it is generally conjectured that Valiant-Vazirani can be derandomized from $\mathcal{NP}\subseteq\mathcal{RP}^{\oplus P}$ to $\mathcal{NP}\subseteq \mathcal{P}^{\oplus P}$. In that case, since $P^{\oplus P}=\oplus P$, we would have $\mathcal{NP}\subseteq \oplus P$. If I read [1] correctly, then it is not generally conjectured, since it would collapse the polynomial hierarchy)
[1] Dell, Holger, et al. "Is Valiant–Vazirani’s isolation probability improvable?." computational complexity 22.2 (2013): 345-383.


Could AI be used to detect when a human is picking survey response options randomly?

AI is probably not the best tool for this job.  Several classical techniques in survey design include:

Consistency check: ask the same question in several ways, spread out across the survey, and check if they've answered consistently.

Open-ended questions: ask an open-ended question, see if they write nonsense or the bare minimum.

Attention check questions: e.g., "What is your favorite color?  Regardless of your favorite color, please pick the second option."  Beware that these are controversial and have pros and cons.

Recruitment: recruit subjects who are less likely to try to cheat you.  Pay them a reasonable wage for their time.

My experience is that it is easy to be overly worried about respondents answering dishonestly; if you follow basic good practices, the overwhelming majority of respondents will try to be helpful and won't try to cheat you.


Show that for A and B, a language J exists such that A $\leq_T$ J, B $\leq_T$ J

Just define $J$ as $A\oplus B = \{m \mid m =2k \text{ if } k \in A, \text{ and }  m =2k+1 \text{ if } k \in B \}$. Then $k \in A$ is decided by querying $2k \in A\oplus B$, and $k \in B$ is decided by querying $2k+1 \in A\oplus B$. Thus $A \leq_T A\oplus B$, $B \leq_T A\oplus B$.

This result is well known in the theory of computability. It establishes the least upper bound on the lattice of the Turing degrees of $A$ and $B$.


If you want to know what a mathematical object is, you need to read its definition. So, I imagine you've seen the definition of finite automata, and it has something called a "set of final states", and the definition probably doesn't say what that means.

OK, that means that, for now, the author is just giving a name to this set of states. They surely wouldn't bother naming something if it was never going to be used, so we need to keep reading. The very next thing you read is probably a desciption of how an automaton processes its input by moving from state to state as it reads the characters. That doesn't seem to involve the concept of final states, so we keep reading some more. The next thing is probably a definition of what inputs are accepted by the automaton. That definition does involve final states, and it tells you exactly what their role is.

The moral of the tale is that, if you want to know what a mathematical object is, you need to read its definition. If you want to know what it's for, you might have to read a bit more, after its definition. (A good writer will warn you if the point of something isn't going to be revealed for a while.) If you want to know why anyone should care about the object, you might have to do a lot of reading, or find someone (or somewhere! ;-) ) to ask questions.


What's the difference between Adaptive Control and a Kalman Filter?

The Kalman Filter only estimates the current state variables of the system, but doesn't (try to) influence the future state of the system. So a Kalman filter alone is just adaptive observation. I'm not sure whether it makes sense to say that adaptive observation is dual to adaptive control, because adaptive control implies some observation based feedback mechanism, while adaptive observation is just adaptive over time, but doesn't need any control based feedback mechanism, even so it doesn't exclude it.

A mathematically pure Kalman filter only applies to (discrete or continuous) linear system of the form $x_k = F_k x_{k-1} + B_k u_k + w_k$ where $F_k$ and $B_k$ are matrices, $u_k$ in the known control signal, $w_k$ is noise with a Gaussian distribution, and the observed signal is $z_k = H_k x_k + v_k$ with a matrix $H_k$ and noise $v_k$. However, the extended Kalman filter overcomes these restrictions sufficiently well, so that this is no real limitation. However, what stays true is that there should already be a sufficiently accurate model of the system. The noise terms allow to compensate for some model errors, but the overall model still has to be sufficiently predictive, because no adaptive model adjustment is performed, only the current state variables are estimated adaptively.

The video shows strongly nonlinear adaptive neural networks. This is completely different from Kalman filters, because here even the model of the system itself is adaptively adjusted. This resembles more closely what we do ourselves, in case our experiences don't match with out expectations and predictions.


confusion with worst case for direct addressing

When iterating from start to end, you always need to examine $m$ items, which is $O(m)$.
When iterating from end to start, in the worst case you need to examine $m - |S|$ items, then the answer depends on the relationship between $|S|$ and $m$.

If $m - |S|$ is const., it takes $O(1)$ time.
Otherwise since $0 \leq |S| \leq m$, we have $m - |S| \leq m$, the upper bound is also $O(m)$.

Then in either cases, as long as $m - |S|$ is not const., both approaches have $O(m)$.


How to prove SPACE-TMSAT is PSPACE-hard?

Suppose $L$ is accepted by some machine $M$ using up to $p(n)$ space, for some polynomial $p(n)$. We map $w$ to $\langle M, w, 1^{p(|w|)} \rangle$.


Worst Case Scenario for Quicksort algorithm with pivot element n/2

Since you're not guaranteed anything about the order of the input, it's possible that the n/2 position has the smallest/largest element of the input. Then quicksort will proceed and put everything else on one side of the pivot.


The decision tree implements the following algorithm for finding $f$:

What is $f(1)$?
What is $f(2)$?
What is $f(3)$?
What is $f(4)$?

There are six possible answers to the first question, but only three of them lead to a valid function. You split according to these answers in the correct order (you want the result to be in lexicographic order), and then continue to the second question. And so on. If you did everything correct, you'll find $\binom{6}{2} = 15$ different leaves, the last of which is $6543$.


Hint: Show that $$\lim_{n\to\infty} \frac{5^n}{6^n} = 0.$$


The No Free Lunch theorem (NFL) was established to debunk claims of the form:

  My optimisation strategy X is always best.

In particular, such claims arose in the area of genetic/evolutionary algorithms.

The statement is, roughly: every optimisation strategy performs badly on many problems. Therefore, there can be no always-best strategy and your claim about X is wrong.


What if a formal grammar cannot be terminated?

When you are given a grammar $G$, then the language it produces, $L(G)$, is all the (finite) words it can generate. All the other "derivations" that don't yield any legal word, can be ignored.

For instance, for the grammar $G_1$:

  S -> SS | Sa | aS

the language that the grammar produces is $L(G_1)=\emptyset$, as no derivation ever terminates.


How does an NFA use epsilon transitions?

Every time you are in a state which has a $\epsilon$ transition, it means you automatically are in BOTH states, to simplify this to you:

If the string is $\epsilon$ then your automata ends both in $q_0$ and $q_1$

If your string is '0' it'll be again in $q_0$ and $q_1$

If your string is '1', it'll be only in $q_2$, because if you look from the point of $q_0$, you have a '1' transition to $q_2$, but you have also to look at case you're in $q_1$(if you were in $q_0$ you always were in $q_1$ also) then there is no '1' transition, so this alternative path just "dies".

Just by looking at these cases its easy to see that your automata accepts $\epsilon$, $0^*$, and going from $q_0$ to $q_1$, the only way to reach $q_2$ is $0^*11^*1$, so, this resumes your automata to $\epsilon$, $0^*$, $0^*11^*1$

Hope this helped you, if you have any further doubts, just ask!


Why aren't there computers with a base different than 2?

As mentioned in this thread here, this is more due to the electronics of how computers work.  It's a lot easier to create an on-off switch then it is an on-off-middle switch.  If you're really curious about this, I'd recommend reading about how a computer works at the electronic level, as just doing this on-off switch took a lot of time for people to make properly.

That being said, there are computers coming that work with more than one state, mainly in the form of quantum computers.  They can have an on and off state, as well as a "both" state if I'm not mistaken.  There are of course advantages such as potential speed boosts from computers like this (though mostly from the way they work physics wise), but then there are also physical limitations imposed as well, such as the fact that they need to be kept incredibly cold to work properly from what has been experimented with so far.  Quantum computers are the "main focus" of how to solve the issue of Moore's Law currently though.

But long story short, yes, computers that "use a base higher than 2" could be faster and more effecient, and there are computers like that, but they aren't ready for the mass populations of the world to use yet.


As a first approximation, most of the memory will be spent on storing $10^6$ floating point numbers (one per degree of freedom). Assuming double precision numbers are used, each number takes up 8 bytes, for a total of 8MB.


Is "ternary search" an appropriate term for the algorithm that optimizes a unimodal function on a real interval?

The word "bitonic search" can probably refer to this concept. See this book and these lecture notes for instance.


When estimating camera motion from the fundamental matrix, why can translation only be recovered up to scale using epipolar geometry?

This can be seen intuitively as follows:

The fundamental matrix $\mathtt{F}$ can be written in terms of the epipolar matrix $\mathtt{E}$, in which case the epipolar constraint equation becomes:
\begin{align}
\mathbf{x}^{\prime\top} \mathtt{F} \mathbf{x} &= 0\\
\mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} \mathtt{E} \mathtt{K}^{-1} \mathbf{x} &= 0,\\
\end{align}
where $\mathtt{K}, \mathtt{K'}$ are the intrinsic camera matrices of the two images corresponding to the points $\mathbf{x}, \mathbf{x'}$, respectively, and I have used $(\cdot)^{-\top} = (\cdot^\top)^{-1}$.

Now, we also know that the epipolar matrix has the form
\begin{equation}
\mathtt{E} = \mathbf{t}^\times \mathtt{R},
\end{equation}
where $\mathbf{t}, \mathtt{R}$ are the relative translation vector and the relative rotation matrix, respectively, between the two images. The operator $(\cdot)^\times$ turns a $3-$vector into a $3\times 3$ skew-symmetric matrix. Since $\mathtt{E}$ is $3 \times 3$, $\mathbf{x}$ and $\mathbf{x'}$ are $3 \times 1$ vectors represented in what we call homogenous coordinates. These have an equivalence property of $\mathbf{x} = (x_1, x_2, x_3)^\top = (\lambda x_1, \lambda x_2, \lambda x_3)^\top = \lambda \mathbf{x}$ for any $\lambda \neq 0$. If you want to convert a homogeneous point into their more familiar 2D image plane representation, you simply take the first two components and divide them by the third one.

This means that, if we replace all of this in the epipolar constraint and multiply the translation $\mathbf{t}$ by an arbitrary scale factor, we get the following:
\begin{align}
\mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} (\lambda \mathbf{t})^\times \mathtt{R} \mathtt{K}^{-1} \mathbf{x} &= \mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} \mathbf{t}^\times \mathtt{R} \mathtt{K}^{-1} (\lambda \mathbf{x})\\
&= \mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} \mathbf{t}^\times \mathtt{R} \mathtt{K}^{-1} \mathbf{x}\\
&= \mathbf{x}^{\prime\top} \mathtt{F} \mathbf{x} = 0,
\end{align}
which leads to the original constraint. This shows there is an overall scale ambiguity. More precisely, the epipolar matrix (and the fundamental matrix) are homogeneous quantities too. This can be further verified by taking the SVD decomposition of $\mathtt{E}$: if it is a valid essential matrix, two of its singular values are equal, hence $\mathtt{E}$ has 5 degrees of freedom and not 6.


The Knuth-Morris-Pratt algorithm does this in linear time without any error.


Asymptotic analysis for machine learning algorithms

Well, first let's clarify the following. Asymptotic Complexity and real life situations are different. Please take a look at this Question.

Now, machine learning is a very hard topic to explore precisely the asymptotic complexity of your algorithms. If we think machine learning as linear algebra, then the asymptotic complexity is the complexity of multiplying matrices. In the area of machine learning, the most important thing is not so much the complexity, but the efficient use of GPUs and TPUs. Let's say you need to train a model for Natural Language Understanding and you use LSTM, GRU and CNN (CNN ?!). Each algorithm has its own complexity because each one does easier or harder calculations. Unfortunately there is no metric such as Model's Accuracy / # of computations. But we all can agree that two LSTM can vastly vary on their speed depending on how good use of GPUs and TPUs they make.


An algorithm may be infallible. Any physical computer can make an error e.g. if it is hit by a stray cosmic ray, a bolt of lightning or a large axe.


Minimize shipping cost based on weight and price constraints

Since the objective function is piecewise linear, the problem can be formulated as an integer linear program.

Given items with prizes $p_1,\ldots,p_n$ and weights $w_1,\ldots,w_n$, define binary variables $x_i$ for $i\in[n]$ where $x_i=1$ if item $i$ selected. For each of the three segments a binary variable $\delta_k$ selects the active segment, and the convex combination of $(\lambda_1,\lambda_2)$, $(\lambda_2,\lambda_3)$, or $(\lambda_4,\lambda_5)$ defines the point in the first, second, or third segment, respectively. Note that $\lambda_3=1$ and $\lambda_4=1$ are different, since your objective function is not continuous at $80$. Auxiliary variables $w$ and $c$ hold the total weight and cost. Finally $W=\sum_{i\in[n]} w_i$ is an upper bound on the maximum weight.

With this you can
\begin{align}
\text{min.}\quad & c,\\
\text{s.t.}\quad & \delta_1 + \delta_2 + \delta_3 = 1,\\
    & \lambda_1+\lambda_2 = \delta_1,\\
    & \lambda_2+\lambda_3 = \delta_2,\\
    & \lambda_4+\lambda_5 = \delta_3,\\
    & w = 30\lambda_2+80(\lambda_3+\lambda_4)+W\lambda_5,\\
    & c = 7.5\lambda_1+7.5\lambda_2+11.25\lambda_3+10.25\lambda_4+(7.5+0.055(W-30))\lambda_5,\\
    & \sum_{i\in[n]} p_ix_i \leq 15,\\
    & \sum_{i\in[n]} w_ix_i = w,\\
    & x_i\in\{0,1\}, i\in[n],\\
    & \delta_1,\delta_2,\delta_3\in\{0,1\},\\
    & \lambda_1,\lambda_2,\lambda_3,\lambda_4,\lambda_5\geq 0,\\
    & w,c\geq 0.
\end{align}

For, say, about 100 items I guess a standard solver can find the optimal solution in a few minutes.

(From your question it is not clear me if you want to select a subset of the items that can be sent at optimal cost, or minimize the total cost for all packages to send all items. For the latter you can extend the model by using variables $x_{ij}$ that indicate if item $i$ goes to the $j$th package, use similar constraints to define the cost for each package, and then minimize the total cost.)


Use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound

Let's assume that $n$ is a power of 2 (otherwise the recurrence isn't really defined all the way), with a base case at $n=1$. Then
$$
\begin{align*}
T(n) &= n^2 + 4T(n/2) \\ &=
n^2 + 4(n/2)^2 + 16T(n/4) \\ &=
n^2 + 4(n/2)^2 + 16(n/4)^2 + 64T(n/8) \\ &= \cdots
\end{align*}
$$
Note that $n^2 = 4(n/2)^2 = 16(n/4)^2$. If $n = 2^m$ then after $m$ steps we will reach $4^mT(n/2^m) = 4^mT(1)$, with $m$ copies of $n^2$ tagging along. Therefore
$$
T(n) = mn^2 + 4^mT(1) = n^2\log_2 n + n^2 T(1).
$$


How to approach Vertical Sticks challenge

Imagine a different problem: if you had to place $k$ sticks of equal heights in $n$ slots then the expected distance between sticks (and the expected distance between the first stick and a notional slot $0$, and the expected distance between the last stick and a notional slot $n+1$) is $\frac{n+1}{k+1}$ since there are $k+1$ gaps to fit in a length $n+1$.

Returning to this problem, a particular stick is interested in how many sticks (including itself) are as high or higher. If this number is $k$, then the expected gap to its left is also  $\frac{n+1}{k+1}$.

So the algorithm is simply to find this value for each stick and add up the expectation.  For example, starting with heights of $[3,2,5,3,3,4,1,2]$, the number of sticks with a greater or equal height is $[5,7,1,5,5,2,8,7]$ so the expectation is $\frac96+\frac98+\frac92+\frac96+\frac96+\frac93+\frac99+\frac98 = 15.25$.

This is easy to program: for example a single line in R

V <- function(Y){ (length(Y) + 1) * sum( 1 / (rowSums(outer(Y, Y, "<=")) + 1) ) }

gives the values in the sample output in the original problem

> V(c(1,2,3))
[1] 4.333333
> V(c(3,3,3))
[1] 3
> V(c(2,2,3))
[1] 4
> V(c(10,2,4,4))
[1] 6
> V(c(10,10,10,5,10))
[1] 5.8
> V(c(1,2,3,4,5,6))
[1] 11.15


Is Knapsack restricted to integers between 1 and 100 still NP-complete?

Let $V(i, W)$ be the maximum sum of the values of the items among the first $i$ items so that the sum of the weights is less than or equal to $W$, then we have

$$V(i, W)=\max\{V(i-1, W), v_i+V(i-1,W-w_i)\}$$

where $v_i$ and $w_i$ are respectively the value and the weight of the $i$th item. Suppose there are $n$ items and the capacity limit is $W_\max$, then the problem is equivalently to compute $V(n, W_\max)$. We can use the recursion formula above to compute the following values in order: $$V(1,1),\ldots,V(1,W_\max),V(2,1),\ldots,V(2,W_\max),\ldots,V(n,1),\ldots,V(n,W_\max).$$

This is the classical dynamic programming method to solve the Knapsack problem. Since it takes $O(1)$ time to compute each $V(\cdot,\cdot)$ and there are $O(nW_\max)$ such values to compute, the overall running time is $O(nW_\max)$. Since you restrict $W_\max\le 100$, the overall running time becomes $O(100n)=O(n)$, which  is indeed polynomial in $n$.


Is Dijkstras algorithm used in modern route-finding systems?

Google Maps in 2009 used Contraction Hierarchies - see this tech talk.

Since then, some mind-blowing methods have been discovered, capable of doing cross-country routing in fractional milliseconds - the so-called "two-hop labeling distance oracles". See here, or search for "Hub labeling" or "Shortest paths for the masses". I think I heard Bing uses this one. It also has applications like the ability to find the nearest point of interest (e.g. nearest gas station) with a complexity independent on the number of gas stations.


Pushdown automaton accepting $\{a,b\}^*$ with twice as many $a$s as $b$s

When in doubt, one should always consult the definitions.

In this case, this is Definition 7.1 of the book by Peter Linz.

It states that $$\delta : Q \times (\Sigma \cup \{ \lambda \}) \times \Gamma \rightarrow \textrm{finite subsets of } Q \times \Gamma^*$$
Thus, $\delta(q,a,A) = \{[q_1,w_1], \ldots, [q_k,w_k\}$ means that when a pushdown automaton is in state $q$ and sees an $a$ on input (where $a$ may be an input or the empty string $\lambda$), then it can enter any one of the states $q_1$ to $q_k$ and replace $A$ by the corresponding string of stack symbols $w_i$.

Therefore, a pushdown automaton can push a string $w$ to the stack by reading $\lambda$ and replacing it by $w$. Or it can pop the top symbol $b$ by seeing $b$ on the stack and replacing it by $\lambda$.


Minimize the total execution time of jobs executed by 3 processors in sequence

Well since no one else is giving an answer, here goes:

Assume the jobs are represented as $J=\{x_1,\ldots,x_n\}$

Since $P_1$ must process only one job at a time, it doesn't matter which order the jobs are processed, the time taken by $P_1$ is always the same, $\sum_{i=1}^n t_{i,1}$, each job's 3 parts are represented as $(t_{i,1},t_{i,2},t_{i,3})$. So to minimize the total time, we only need to consider the order that affects $P_2$ and $P_3$. Since both of them can execute any number of jobs in parallel, to minimize their time we want the jobs that need longer time to be processed first. So you arrange the jobs in decreasing order of $t_{i,2}+t_{i,3}$. Now to prove that this is optimal.

We need to show that in any optimal solution to the problem, if the ordering of the jobs is not the same as the ordering described above, we can convert it to our ordering without increasing the total time.

Let $C$ be an optimal ordering. Assume $C$ does not have the same ordering as that given by the algorithm. Which means, there exists jobs $x_i$ and $x_j$ such that $t_{i,2}+t_{i,3}<t_{j,2}+t_{j,3}$ and $x_i$ is listed immediately before $x_j$ in $C$, call such a pair of jobs an inversion. Consider the ordering $C'$ obtained from $C$ by swapping the position of $x_i$ and $x_j$. Thus $x_j$ would appear finish earlier here.

We can see that in $C'$, $P_2$ starts on job $x_i$ exactly when $P_2$ starts on job $x_j$ in $C$. This is independent of how long the first parts of $x_i$ and $x_j$ require. Since $t_{i,2}+t_{i,3}<t_{j,2}+t_{j,3}$, it's clear that in $C'$ job $x_i$ finishes sooner than job $x_j$ in $C$. So the total time taken by $C'$ is no larger than the time taken by $C$.

Repeat the above till all inversions are removed from $C$ and we have an ordering which is the same as that of the algorithm. Thus, the ordering returned by the algorithm is optimal.

Running Time: It's clear that the running time is $O(n\log n)$, I don't think I need to elaborate on that.

Hope this helps! Cheers!


I figured out what he means: fetch the instruction and decode it, but do not fetch the next instruction until you've determined whether it's a branch or non-branch instruction.

For the non-branch instructions, it will fetch next instruction after the decode stage. But for the branch instruction, it will require an extra cycle to determine it should stay in the loop or not.

The CPI does add up if I do follow through with what I've mentioned. I've added a picture to give you a better picture of what's happening at each cycle.


How to generate snowflakes of a fixed area as challenges for the FridgeIQ puzzle?

SAT solvers are my favorite "big sledgehammer" to apply to this kind of problem, so let me describe how you could use a SAT solver for this problem.

Let's constrain the shape to fit within a 15x15 grid (say), and express the problem of finding a valid shape as a SAT problem.  It gets a bit messy, so you'll have to be willing to tolerate that, but the approach is powerful.   Introduce boolean variables $x_{i,j,k}$, with the intended meaning that $x_{i,j,k,r}=1$ means that we rotate tile $k$ into orientation $r$ and then put its upper-left corner in the grid cell at coordinates $(i,j)$.  We'll now write down some boolean formulas that characterize what it means for this to be a valid snowflake.

There a bunch of requirements to count as a valid snowflake; I'll sketch how to express each one as a boolean formula:

Each tile must be used exactly once.  In other words, for each $k$, exactly one of the $x_{i,j,k,r}$'s must be true; this is is a one-out-of-n constraint.  See Encoding 1-out-of-n constraint for SAT solvers for some techniques for encoding this as a boolean formula (or if you use Z3, see https://stackoverflow.com/q/43081929/781723).
The shape must be symmetric. To help check this, let's introduce auxiliary boolean variables $y_{i,j}$, with the intended meaning that $y_{i,j}=1$ means that the grid cell at coordinates $(i,j)$ is covered by some tile.  It is easy to express $y_{i,j}$ as a logical-or of a subset of the $x$'s (namely, all the $x_{i',j',k,r}$ such that placing tile $k$ in orientation $r$ at position $(i',j')$ will also cover $(i,j)$; knowing the shape of each tile, you can precompute all such $x$'s; there will be 160 of them).  Moreover, let's require this to have fourfold symmetry around the origin.  That means $y_{i,j} = y_{-i,j} = y_{i,-j} = y_{-i,-j}$ holds for all $i,j$.
No two pieces overlap.  This involves a bunch of constraints of the form $(\neg x_{i,j,k,r}) \lor (\neg x_{i',j',k',r'})$, for all $i,j,k,r,i',j',k,k',r,r'$ such that placing tile $k$ at coordinates $(i,j)$ in orientation $r$ would overlap with placing tile $k'$ at coordinates $(i',j')$ in orientation $r'$.  (This can be easily precomputed based on the shape of tiles $k$ and $k'$.)

This gives you a bunch of boolean formulas.  Write down the conjunction of all of them, and then feed it to an off-the-shelf SAT solver and ask the SAT solver to find a satisfying solution for you.  This will then correspond to a snowflake.

For implementing this stuff, I find Z3 a very convenient API to a SAT solver.

This will find one snowflake.  What if you want multiple of them?  There is a straightforward way to generate multiple solutions: after you have found one solution, you generate what's called a "blocking clause" and add it to the list of constraints (i.e., conjoin it to the formula).  The "blocking clause" just says "not that one I already know of".  For instance, if you already have a satisfying assignment that assigns values $c_{i,j,k,r}$ to each $x_{i,j,k,r}$, then the blocking clause is the formula $\lor_{i,j,k,r} (x_{i,j,k,r} \ne c_{i,j,k,r})$.  You can repeat this to obtain multiple solutions: each time you find another solution, you generate another blocking clause, add it to the formula, and apply the SAT solver again.  Some SAT solvers even have special support for incrementally adding additional constraints that is more efficient than starting the search from scratch, though that might not be necessary.

Well, that's the idea, anyway.  But here I have to confess that I lied.  There is one requirement that I've left out so far: connectivity.  You said you want each snowflake to be connected.  That's messier to implement in a boolean formula, though also possible.  The crude hack is to generate many candidate snowflakes as above, check each for connectivity, and keep only the connected ones.  However, this might not work very well.  So, let me describe how to encode the connectivity constraint in SAT.  Beware; it gets messy, so hold onto your hat.

The shape must be connected. The main idea will be to pick a particular grid cell, require that it be present, and require that every other covered grid cell be connected to it.  Let's say we require that the grid cell at the origin $(0,0)$ be covered.  Then we can introduce auxiliary variables $z_{i,j,s}$, with the intended meaning that $z_{i,j,s}=1$ means that grid cell $(i,j)$ can be reached by starting at the origin and then taking $s$ steps across adjacent covered grid cells.  This constraint can be encoded in SAT by noting

$$z_{i,j,s} = y_{i,j} \land (z_{i-1,j,s-1} \lor z_{i,j-1,s-1} \lor z_{i+1,j,s-1} \lor z_{i,j+1,s-1}).$$

We'll adopt the convention that $z_{i,j,0}=1$, and if $(i,j)$ is outside of the 15x15 bounding box then by convention $y_{i,j,s}=z_{i,j,s}=0$  (we don't introduce extra variables for that, we just replace those terms with "false").

Finally, for each $i,j$, we add the constraint that $y_{i,j} \implies \lor_{s=0}^{39} z_{i,j,s}$.  This ensures that every covered cell is reachable.  (Note that if it is reachable, it is reachable in at most 39 steps, so we only need to go up that high.  In practice, I suspect that 19 or even 9 are probably large enough.)

That ensures connectivity.  However, there's a potential catch: this requires everything to be connected to the origin, so it only generates snowflakes that cover the origin.  We also want snowflakes that have a hole at the origin.  I think you can fix this by iterating over all possibilities for the 'anchor point' (one grid cell that you'll require to be covered and require everything to be connected to), and solving the SAT instance for each possible anchor point.  (To avoid duplicates, if you like you can add additional constraints to ensure disjointness of solutions.  For instance, solve one SAT system where you require $(0,0)$ to be covered and everything to be connected to $(0,0)$; solve another where you require $(0,1)$ to be covered and everything to be connected to $(0,1)$ and you require $(0,0)$ to be uncovered; another where you require $(0,2)$ to be covered and everything to be connected to $(0,2)$ and you require $(0,0)$ and $(0,1)$ to be uncovered; and so on.)

Lastly, in the above I assumed that your shapes are collections of squares, i.e., they either completely cover a grid cell or don't touch it at all.  Of course, this isn't valid for your tiles, due to those diagonal pieces.  So, I suggest that after breaking down the 15x15 region into 225 small squares, you break down each square into four triangles.  Then, instead of using the $y$'s to record which grid squares are covered, you'll need to adjust the definition of the $y$'s and the above formulas to record which triangles are covered.  Everything should go through with some straightforward adjustments.

Phew.  I told you it would get messy.  The basic idea here is that we are taking each of the conditions for a shape to count as a valid snowflake, writing them down in boolean logic, and then letting the SAT solver find solutions that meet all of those requirements.  SAT solvers today are amazing and contain clever and powerful strategies to automatically find solutions that meet your requirements.  Researchers have spent decades coming up with better algorithms and improving the engineering of the tools; you can't hope to duplicate that, so rather than trying, you can build on all of their work and apply it to your specific situation.


Estimating the complexity of an algorithm by looking at code

This question is rather informal, and you may enjoy reading this.
What you are asking about is a topic discussed often in Computer Science and Mathematics (perhaps all subjects, but my perspective is not so broad) - "developing an intuition". Often, students are looking for some sort of cheat code to solving problems quickly without going through all of the steps. The honest answer is that you can only develop such intuition and speed by doing precisely the opposite - practicing slowly and without any sort of shortcut.

Practice calculating time complexity - it really isn't too difficult. A quick google search gave me this page, which is pretty informal and may suit the needs of some practice problems. Once you have gone through the process enough times, you will ascend to a sought-after plane of intuition.

Having very little professional knowledge is not an issue. If the example page I sent is too formal, there are plenty of other pages on the web explaining time complexity. You just have to be willing to sit down and put some hours into it (which no different than what a "professional" does to get the same knowledge, except perhaps they pay more for it?).


Method provided by component may need to be implemented, What does this mean?

I am also not entirely sure what it's saying, but to me, it sounds like this is saying that in inheritance, if e.g. the Dog class already has function bark() { print('woof!')}, then the person writing a GoldenRetriever class which inherits from Dog doesn't need to write a bark method since it's inherited from Dog.

On the other hand, if someone is writing a GoldenRetriever class that contains an instance of Dog inside each instance of GoldenRetriever, you will have to define function bark() { this.dog.bark() }.


First, notice that your topological sort comment isn't quite right, because other nodes can be sinks than the last node in a topological sort.

To your original question: Consider some path in a DAG that is not from a source to a sink. Can you show that this path can be made longer? (This implies that the longest path must be from a source to a sink.)

For example, if the path does not start at a source, then it has at least one incoming edge... (make sure you use the fact that the graph is a DAG).


First of all, this is a math question.

I think you are confused on how brackets are used. They indicate precedence of operations, and can be used anywhere, even in places where such indication is not necessary. For example,
$$3 \times 5 + 8$$
and
$$(3 \times 5) + 8$$
are both legitimate expressions and they mean exactly the same thing.

Your expression
$$(x \cdot 1) + (x \cdot y)$$
is exactly the same as
$$x \cdot 1 + x \cdot y.$$
So we may calculate
$$(x \cdot 1) + (x \cdot y) =
  x \cdot (1 + y) =
  x \cdot 1 = x.$$


Why is the base used to compute hashes in Rabin–Karp always primes?

A quick recap first. We are looking for a pattern $P[1\ldots m]$ in a string $S[1\ldots n]$. The Rabin-Karp algorithm does this by defining a hash function $h$. We compute $h(P)$ (that is, the hash of the pattern), and comparing it to $h(S[1\ldots m])$, $h(S[2\ldots m+1])$ and so on. If we find a matching hash, then it is a potential matching substring.

The efficiency of the algorithm depends on the ability to compute $h(S[r+1\ldots s+1])$ efficiently from $h(S[r\ldots s])$. This is called a "rolling hash". Note that any efficient rolling hash function will do, and it's still Rabin-Karp. The question that you're asking about is one particular choice of hash function, where you use:

$$h(S[r\ldots s]) = \sum_{i=r}^s S[i]\, p^{s-i} \bmod q$$

where $p$ is a prime number with roughly the same order of magnitude as the size of the character set, and $q$ is another prime number which defines the cardinality of the range of the hash function, typically of the same order of magnitude as a machine word divided by the character set size. If I'm reading it correctly, you're asking why $q$ has to be prime.

In fact, this is a more general question. In a lot of the old (and current) literature on hashing, the advice is that the hash function should be taken modulo a prime number (e.g. hash tables should have a prime size).

For a hash function to be as useful as possible, its range needs to be relatively uniform, even when its domain is not. Natural language text (say) doesn't have a uniform frequency distribution, but hash values should be.

If $q$ is a prime number, then a lot of other numbers are relatively prime to it, and in particular, the sum (especially if $p$ is also prime!). This makes the frequency distribution of the hash values more uniform, even though the hash function is relatively weak.

It's important to understand that we do this because the hash function is weak. If the hash function were stronger, taking the remainder when divided by a prime would not be necessary; you could, for example, take the remainder when divided by a power of two, which would be a much cheaper bit mask operation. However, it's hard to design strong rolling hash functions which are cheap enough to be done for every input character in the Rabin-Karp algorithm.

Something that's worth pointing out that this "remainder of a prime" technique used to be common in many hashing applications, but this advice is inadvisable on modern hardware. It advice made sense once upon a time, because while final integer division instruction was always expensive, so were the operations that you used to compute your hash function, such as integer multiplication. On modern CPUs, it is much more expensive to do an integer division even than an integer multiplication.

Modern carry-save adder multipliers are fully pipelined, so you can have several such instructions being executed at once. Modern dividers use the SPH or Goldschmidt algorithms, which are multi-cycle and impossible to pipeline. Goldschmidt dividers also tie up the multiplication unit, making the performance hit even greater.

I've had programs where this division instruction was the bottleneck, and the annoying part was that it was hidden inside the standard library.

On a modern CPU, it is worth using a more sophisticated hash function built out of fully pipelineable operations (e.g. multiplies or even table look-ups) and using hash tables which are powers of two, so the modulo operation is a bit mask. Do anything to avoid that division operation.

Just not for Rabin-Karp.


Why does parallelising slow down this simple problem against looping through all the data?

Parallelism has costs. The processes have to be scheduled, communicate with each other, manage resources, etc. In return you can do multiple things at the same time.

When you have a lot of slow tasks that can be done independently, parallel processing will speed things up a lot.

But when you try to parallelize an easy task it might take longer to handle the overhead than to actually do the work. That seems to be the case here.


Any $P$-complete problem, is unlikely to have an efficient parallel algorithm. Why ?

The existence of $P$-complete problems is the most important clue that $(P ∩ POLYLOGSPACE) ≠ P$.
The question then is, why is this conjecture relevant to parallel computing?
Let's start with the resources used in a computation. For sequential computing: time and space; for parallel computing: time and hardware (number of processors).
Is there a relation? Yes!
Sequential space ↔ parallel time; Sequential time ↔ parallel hardware.
The correspondence between sequential space and parallel time seems to be independent from the parallel computing model adopted; this leads to the following,  so called parallel computation thesis which is unproven.

(Chandra and Stockmeyer) Every computation of a TM with space complexity $S(n)$ can be simulated in a parallel computing model in time $T(n) = O(S(n)^{O(1)})$ and every computation of a parallel computing model with time complexity $T’(n)$ can be simulated by a TM with space complexity $S’(n) = O(T’(n)^{O(1)})$.

The class of problems solvable sequentially in polynomial space is $PSPACE$ and the set of problems solvable in polynomial time is $P$.Since $PSPACE$ is thought to be a much larger class of problems than $P$, the thesis quantifies the effective improvement made possible by parallelism. A consequence of this thesis is that a PRAM can solve $NP$-complete problems in polynomial time…
Unfortunately, no!
The parallel computation thesis implies that we can actually deal with problems belonging to $PSPACE$… but this requires an exponential number of processors!
A time-space trade-off is working: The exponential time on the sequential computing model is transformed into an exponential number of processors on the parallel computing model, whereas the polynomial space on the sequential computing model is transformed into a polynomial time on the parallel computing model.

This trade-off is easier to understand if we try to restrict both parallel time and parallel hardware: if the parallel computing model has a polynomial number of processors, then the class of problems solvable in parallel polynomial time is $P$.
If we restrict the number of processors to a polynomial we can improve the performances of a sequential machine, but no more than a polynomial factor.
Thus we can reduce the degree of the polynomial representing the time complexity, but we are not able using parallelism to reduce exponential costs to polynomial costs.

The problems solved in parallel with polynomial time complexity are those problems belonging to $P$. The polynomial constraint on the number of processors leads to a parallel computing model equivalent to TM.
There are two important practical considerations:
which polynomial number of processors is acceptable/affordable ? In practice, the polynomial number of processors is meant to be linear or close. Which subpolynomial time is achievable ? It turned out that almost all highly parallel feasible problems can achieve polylogarithmic parallel time.
In parallel, a time complexity which is logarithmic in the input length represents an efficient parallel computation.
A parallel algorithm is considered efficient if, given a polynomial number of processors, its time complexity is polylogarithmic.

Given a problem $R \in TIME\_SPACE_{TM}(n^k, (log n)^h)$ where $k$ and $h$ are constants, the parallel computation thesis implies the existence of a parallel algorithm for $R$ with time complexity $O((log n)^{k’})$ where $k’$ is a constant. The comparison between sequential and parallel time allows classifying $R$ as a problem highly parallelizable (from a time perspective).

From the parallel computation thesis, it follows that $POLYLOGSPACE$ is the class of problems highly parallelizable. $POLYLOGSPACE$ does not contain problems complete with regard to log-space reductions; this implies $POLYLOGSPACE \neq P$.
It seems that

$POLYLOGSPACE ⊄ P$
$P ⊄ POLYLOGSPACE$

$P ∩ POLYLOGSPACE$ contains the problems that can be solved in polynomial time using polylogarithmic space. $P$-complete problems probably belongs to $P - (P ∩ POLYLOGSPACE)$.

$NC$ (Nick’s class - so called in honour of Nicholas Pippenger, the first to identify and to characterize it in 1979) is the class of problems that can be solved in polylogarithmic time (i.e., with time complexity $O((log n)^k))$ with a polynomial number of processors (I.e., bounded by $O(f(n))$ for some polynomial function $f$ where $n$ is the problem size)
The parallel computation thesis implies $NC ⊂ (P ∩ POLYLOGSPACE)$.

However, unfortunately by definition $NC$ also includes lots of problems which are not efficiently parallelizable. The most infamous example is parallel binary search.
The trouble is that this problem has polylogarithmic time complexity even for $p$ = 1.
Any sequential algorithm requiring at most logarithmic time in the worst case is in $NC$ regardless of its parallel feasibility!

Now, we can finally explain why $P$-complete problems are the hardest parallelizable problems.
Given a $P$-complete problem $Q$, it is very unlikely the existence of an efficient parallel algorithm: if such a parallel algorithm would exist with time complexity $O((log n)^k)$, then the parallel computation thesis will imply the existence of a sequential algorithm with space complexity $O((log n)^{k’})$ for the same problem.
Since $Q$ is a $P$-complete problem this in turn will imply that every problem in $P$ can be solved in poly-log space: $(P ∩ POLYLOGSPACE) = P$.
As you already know, we instead believe that $(P ∩ POLYLOGSPACE) ⊂ P$, even though we are not yet able to prove this.

One final observation, about the polynomial processor requirement. Well, that is a theoretical statement. In practice: a processor requirement that grows faster than the problem size might not really be useful.


Who was the first to define the RAM model?

According to the chapter notes of Chapter 1 of the book "Computational Complexity: A Conceptual Perspective" by Oded Goldreich,

  The RAM model is attributed to von Neumann's report [234].

where [234] refers to

  J. von Neumann. First Draft of a Report on the EDVAC, 1945. Contract No. W-670-ORD-492, Moore School of Electrical Engineering, Univ. of Pennsylvania. Reprinted (in part) in Origins of Digital Computers: Selected Papers, Springer-Verlag, pages 383--392, 1982.


Write a pseudo code for a Graph algorithm

Yes, you can use the topological sort. Suppose topological sorting of the vertices gives you the sequence: $v_{1}, \dotsc, v_{n}$ such that there is no edge of the form $(v_{j},v_{i})$ for any $i < j$.
Following would be the pseudocode to compute the minimum reachable $f(u)$ value for each vertex $v_{i} \in V$:
fun()
----- int min_val_reachable[n];    // array that stores minimum reachable f(u) value for each vertex

----- for(i = n to 1; i--)
-------- min_val_reachable[i] = f(v_i) // since a vertex v_i is reachable to itself
-------- for each vertex 'u' in adj_list[v_i]
-------------- if (min_val_reachable[i] > min_val_reachable[u])
-------------------min_val_reachable[i] = min_val_reachable[u]
-------------- end
--------- end
----- end
----- return min_val_reachable[];

The time complexity of the topological sort is $O(|V| + |E|)$, and the time complexity of the above procedure is also $O(|V| + |E|)$. Thus, the overall complexity is $O(|V| + |E|)$.

You can prove the correctness of the above procedure using the induction technique as follows:
Hypothesis: After $t$ iterations of the outer "for loop", we get the correct min_value_reachable[] for every vertex from $v_{n}$ to $v_{n-t+1}$
Base Case: For $t = 1$, it is easy to see that min_value_reachable[$v_n$] = $f(v_n)$ since $v_{n}$ does not has any child, and $v_{n}$ is reachable to itself.
The induction case is also simple. Hope you can figure out the details yourself.


How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step

You're asking how to compute the shortest path between two vertices in a graph.  Solution: use an algorithm for computing shortest paths.  In your case, BFS would be a good choice.  There's no need for A*.


Environment detection - How to detect "city" versus "landscape" background environment in computer vision?

Think of what different features the desert has compared to an urban environment. The desert is probably restricted the a limited set of colors/hues. It is limited to mostly smooth textures. It lacks "man-made" geometries such as straight lines from building edges etc.

So you should be able to differentiate between desert and urban environment by looking at the color components (both the number of colors and the variation), textures and the amount of prominent straight lines/edges in the environment.

By googling "image processing classify outdoor environment" I found the paper Automatic Classification of Outdoor Images by Region Matching which can be a good starting point for reading up on environment classification. They seem to base the classification mostly on color and texture features.

These are just general ideas but hopefully they can help you get started. Good luck.


What is the difference between language hierarchy and Grammar hierarchy for LL and LR?

A language is in a class if there exist a grammar of that class which generates the language.  Stating that for languages $LALR(1)=LR(1)$, means that when you have a $LR(1)$ grammar you can build a $LALR(1)$ grammar for the same language.  The grammar may be more complex than the $LR(1)$ grammar (for instance, it may use equivalent but different non-terminals to provide the finer distinction of contexts that $LR(1)$ gives for free).


Using a proof-of-work system to discourage piracy or encourage donations

Hypothesis

Any algorithm or a certain class of algorithms can be converted into a proof-of-work version of that algorithm. That is: A deliberately inefficient and incompressible algorithm.
Such converted proof-of-work algorithms can support proof-of-work shortcuts.
Such converted proof-of-work algorithms can not be converted back to the original algorithm without considerable computational power; if at all.

Surprisingly, this is possible.
Essentially the idea is: you can convert any program into a proof. Add some probabilistic complicated mathematical voodoo, and you can get succinct proof that someone ran a program on his machine, the full program, no cheating. This means you can essentially turn any busy-work algorithm into a POW, or even use useful algorithms as POW, and not have to worry about a shortcut (for example, you can use protein folding as POW, and not have to worry that average-case might not be hard). The proof guarantees that the entire program ran until termination.
For deliberate shortcuts you can simply build in early termination into the program for your deliberate shortcuts. For example:
def P(user_input,hard_coded_n):
  if user_input is not None:
    p,q = user_input
    if p*q = hard_coded_n:
      return True
  protein_fold()
  return True

In this program, you generate and hard-code a semi-prime, $n$, into the program. If you want to provide the user with a shortcut, you give him the p,q that he can use as input for early termination. Then you check his proof that he ran the program, and the proof will guarantee that the output he provides was the output of his program; therefore his POW is to provide "True" as output, and the proof.
This type of system is insanely powerful IMO; you can think of all sorts of things you can do with this; your cheap "DRM" ideas are the least of it :P
Further terminology/keywords:

Succint Non-interactive Argument of Knowledge (SNARKs) are basically succinct proofs that someone ran some computation.
SCIP: Succinct Computational Integrity and Privacy, is a practical system being built upon many years of research/complicated mathematics.

There is a large body of research into this, attempting to make it practical. For an actual project (SCIP) (you asked this question at the right time in history) see this talk: Universal and affordable computational integrity - Bitcoin 2013 Conference by Eli Ben-Sasson (another talk if you found that one interesting); though he applies it to bitcoin (it is a talk given at a bitcoin conference), he generally explains the power of the system, it is a good watch, even if you don't care about bitcoin.
However, the application to bitcoin, distributed trust systems, and systems that rely on proof-of-work are very numerous and abstract. Suffice to say, though the practical applications are hard to come by at first, the intuitive power of such a system suggests that they will be numerous.
Wrt. bitcoin, this system magnifies the potential of a distributed currency by orders of magnitude; read through bitcoin forums/mailing lists/proposals on the wiki, and you can find countless applications of being able to guaranteeing secure computation on someone else's machine.

For example, instead of verifying the entire bitcoin blockchain on your machine, you can have someone else do it, and then simply verify that he ran the verifier!
Of course arbitrary POW is a big possible win for future bitcoin; perhaps one day we'll see a blockchain doing useful work (now doubly useful, not just guaranteeing the integrity of bitcoin, but also computing something useful), or even a secure distributed computing marketplace, where the lottery of minting the next block is won by one of the participants.

For further reading see SNARKs for C :
Verifying Program Executions Succinctly and in Zero Knowledge
(extended version) (PDF): yes, they are making a C compiler. They designed a virtual architecture, called TinyRam from which they generate the proof and the program to be run. They are also considering an LLVM backend. They have created a website for the SCIP project.


You should take the gradient of the function, that is, the vector of partial derivatives with respect to all coordinates of $\mathbf{u}_1$, and equate it to the zero vector. Let us suppose that the individual coordinates of $\mathbf{u}_1$ are $u_1^1,\ldots,u_1^n$, so that (12.4) reads
$$
\sum_{i=1}^n \sum_{j=1}^n S_{ij} u_1^i u_1^j + \lambda_1 \left(1 - \sum_{i=1}^n (u_1^i)^2\right).
$$
The derivative with respect to $u_1^t$ is
$$
\sum_{i=1}^n (S_{it} + S_{ti}) u_1^i - 2\lambda_1 u_1^t = 2 (\mathbf{S} \mathbf{u}_1)_t - 2\lambda_1 u_1^t,
$$
since $S$ is symmetric. The gradient is thus
$$
\nabla (12.4) = 2\mathbf{S} \mathbf{u}_1 - 2\lambda_1\mathbf{u}_1.
$$
Equating it to zero, we obtain the condition $\mathbf{S} \mathbf{u}_1 = \lambda_1 \mathbf{u}_1$, that is, $\mathbf{u}_1$ is an eigenvector of $\mathbf{S}$ corresponding to the eigenvalue $\lambda_1$.


Can a subset of indexes of a partial recursive function be recursively enumerable but not recursive?

I guess the answer is yes, but please check critically. One can easily construct an infinite recursive set of indices of $\phi$ (adding "comments" to a program). From this infinite recursive set one can pick out a non recursively enumerable subset.


Is there a known maximum for how much a string of 0's and 1's can be compressed?

Kolmogorov complexity is one approach for formalizing this mathematically.  Unfortunately, computing the Kolmogorov complexity of a string is an uncomputable problem. See also: Approximating the Kolmogorov complexity.

It's possible to get better results if you analyze the source of the string rather than the string itself.  In other words, often the source can be modelled as a probabilistic process, that randomly chooses a string somehow, according to some distribution.  The entropy of that distribution then tells you the mathematically best possible compression (up to some small additive constant).

On the impossibility of perfect compression, you might also be interested in the following.

No compression algorithm can compress all input messages?
Compression functions are only practical because "The bit strings which occur in practice are far from random"?
Is there any theoretically proven optimal compression algorithm?


It's hard to say without seeing the preceding code. If seq is initially empty the the run time of the outer loop is $O(n2)$ and the first nested loop is $O(k)$ and the second nested loop is $O(n1-k)$. The total running time would be $O(n2)*(O(k)+O(n1-k))$ which is $O(n^2)$.

However if seq has some initial elements, the worst case running time for the algorithm is $O(\infty)$. The problem is with the nested while loop seq[k]>seq2[j]. If any of the first n elements in seq are > seq2[j] the loop will not increment and run endlessly. Also you may run into array index out of range errors.

For example if seq = 2 , 1 , 0 and seq2 = 1 , 2 , 3. Then seq[0] > seq2[0] would be equivalent to 2 > 1 which i s false and k would never increment.
The solution would be to use

n1 = sizeof(seq)/sizeof(seq[0])  # number of elements in seq
int k = 0;
for(; k < n1 ; k++){             # iterate over seq
    if( seq[k] >= seq2[j] )      # until an we find an element in seq >= seq2[j]
        break;


Given a graph, finding if a node has three adjacents from a node subset $N$

To find such triples of edges, partition the adjacency list $L_i$ of each node $p_i$ in $P$ into three sets: $P_i$, the set of neighbors in $P$, $N_i$, the set of neighbors in $N$, and $Q_i$, the set of neighbors in $V \setminus (N \cup P)$. If each vertex is labeled with which set it belongs to, then the partitioning can be accomplished in linear time. Then, for each $p_i$, check if $P_i$ contains at least 3 vertices. If so, then you have an edge subset that meets your requirements.

If you want to generate all possible edge subsets of the outgoing edges in each node, you would be generating the powerset of the neighbors of $p_i$. If a vertex has $n$ neighbors, the size of the powerset will be $2^n$. This strategy is impractical for all but the smallest input graphs.

If you only want to list the edge subsets from each $p_i$ that meet your requirements, the number of subsets for a vertex with $n$ neighbors in $V$ will be ${n \choose 3}$, but the algorithm to enumerate them should not be complicated.


Find the center node on a weighted, non-directed graph

Use the Floyd-Warshall algorithm to compute all-pairs shortest paths (i.e., compute the distance between each pair of nodes).  Then it is easy to find the center of the graph by enumerating all possibilities for the center node.  The running time will be $O(n^3)$.


A helpful way to build intuition: Try working through an example!  Can you find an example of a graph and a flow where property (a) is true?  Then, ask yourself: is property (b) true in that one?  What made the difference?

Spoiler (but it's best to try the above first; it will help you learn more from this exercise):

   The crucial difference is between "for every maximum flow" vs "there exists a maximum flow".  That's the difference between $\forall$ vs $\exists$.  As you probably know, $\forall x . P(x)$ can be false even if $\exists x . P(x)$ is true.


Lower bound on distinct element heapsort

keep in mind, that a heap has a height of $O(\log n)$ and its root contains the minimal element. how long does it take to restore the heap if you remove the root element (the minimum!) and how often you have to do this in order to achieve a sorted list?

after that, think of the time you need for building a heap out of $n$ elements in abitrary order


Does applying Hadamard gate is identical to applying a measurement gate that is perpendicular to the current qubit state?

As Yuval points out, you have already answered your own question. If I have a state $|q\rangle = a|0\rangle + b|1\rangle$ and I apply a Hadamard gate to that state, I end up with a new state: $$H\cdot|q\rangle = \frac{1}{\sqrt{2}}(a+b)|0\rangle + \frac{1}{\sqrt{2}}(a-b)|1\rangle$$

However, if I measure the state $|q\rangle$ in the standard basis, I get either $|0\rangle$ with probability $|a|^2$ or $|1\rangle$ with probability $|b|^2$. Notice that both $|0\rangle$ and $|1\rangle$ are different states than what you would have gotten had you applied the Hadamard transform instead of a measurement. I admit that a Hadamard-transformed state of 50% $0$ and 50% $1$ looks very much like having done a measurement, but this is not true: you haven't done the measurement yet, and the state is still in superposition. This matters if you do other transformations afterward, or if you work in a multi-qubit system. Then when measuring later, it matters whether you did a Hadamard transform or a measurement.

A good thing to do to acquaint yourself with transformations and measurements is to just compute some by hand on one qubit and on two qubits, and to write out in full the intermediate states in Deutsch's algorithm. You'll get the hang of it.


What is the instruction format for an accumulator machine?

Fixed format instruction means that all instructions have the same size of $k$ bits. You ask to learn what $k$ is.

As you say, the opcode takes 7 bits. So $k \ge 7$
In order to support memory operations (such as add mem or load mem etc) we need to be able to give an address (=mem). If the dressing mode is direct, and given there are 24 bits address, we have that $k \ge 7+24$.
But the description of your CPU suggests that there is other addressing modes. Specifically, there is another register, index register that allows accessing the memory of [X+mem] where X is the content of the indexing register and $mem$ is the 24 bits of address we already counted for. Now, do we need to state X in the instruction itself? - No. we just need to be able to mention the addressing mode is different = a different opcode.
what about load immeidate (i.e., loading an immediate value directly into the accumulator)?

I don't know.

Your description doesn't give any information or constraints on this issue and there are many different ways to implement the same action. In particular, one can think of "load-byte" instruction which will update the (LSByte of the) accumulator with some fixed value. The current $k$ is enough for such instruction as long as the immediate value is at most 24bits.  If you wish to have a way to update the entire 32bits of the accumulator using a single instruction you will have to increase $k$ to support this operation as well.

So unless there are other demands or clarifications to the description you gave, we get that $k \ge 31$.


You may be interested in reading about total unimodularity. An ILP is solvable in polynomial time if the associated matrix is totally unimodular (sufficient but not necessary condition). This explains the tractability of assignment and maximum flow problems.

I'm not aware of any "reason" why knapsack is pseudopolynomial time solvable.


Disjoint union of NP-hard problem and P problem is NP-hard

Given an instance $x$ of $A$, reduce it to an instance $y$ of $A \cup B$ as follows:

Check (in polynomial time) if $x \in B$, if the answer is yes, then $x \not\in A$ since $A \cap B = \emptyset$. Pick any $y \in \Sigma^* \setminus (A \cup B)$ (which is non-empty by hypothesis).
If $x \not\in B$, then $x \in A \cup B \iff x \in A$. Pick $y=x$.


Label coloring to maximize number of "balanced" triangles (NP-hardness)

Reduce from 2-Lin(2):

Start with a star that has one edge per variable, and let those initial-labels all be 0.

For each equation    xi + xj  =  b  ,    create an edge from the outer vertex of xi's edge to the outer vertex of xj's edge, and let that edge's initial-weight be (-1)b.

That will produce the output weighted-graph.  Just let k be the number of variables, so the cardinality constraint doesn't matter.

Triangles whose weights are all forced are forced to be good or bad, so their existence affects approximation quality but not which g's are optimal.  Other triangles use at least one variable-edge, and so exactly 2 variable-edges, since being a variable-edge is equivalent to being incident with the central vertex.  Thus no unintended triangles affect which g's are optimal, so those g's are exactly the g's for which composing with log-1 yields an optimal solution to the input 2-Lin(2) instance.

Your problem is obviously in W[P]O, and I have no other clue regarding its parameterized complexity.


Just read the constraint carefully. $m\le n$ tells you that you must have at least as many b's as a's. The other part: $n\le 2m$ tells you that you cannot have more than twice as much a's.

Here is an EBNF description that yon can convert to BNF.

$S\to aSb[b] \mid \epsilon$


Given an array of elements $a[i], 0\le i\le n-1$, we know we can sort it in time $O(n\log n)$. Then do the following to produce an array $b[\;]$:

declare b to be of size n
old = a[0]
b[0] = a[0]
j = 1
for i = 1, ... , n
   if a[i] =/= old    // found a new value
      old = a[i]      // save it
      b[j] = a[i]     // store it in b[j]
      j = j + 1       // and increment the b index

It's clear that, first, this can be done in one pass through the $a$ array, so this part will take time $O(n)$ (along with $O(n)$ time to allocate $b$), and, second, after this part the $b$ array will contain all of the values of the original array, with no duplicate values.

Note. This may or may not be what you want. Starting with an initial array $\langle\,7, 3, 7, 4, 1, 3, 1, 7\,\rangle$, this will result in a $b$ array $\langle\,1, 3, 4, 7\,\rangle$, which has all the values without duplicates, but the original place order of the elements isn't preserved. There are at least two possibilities for the result, depending on whether you want to eliminate all the duplicate values after the first occurrence, (giving you $\langle\,7, 3, 4, 1\,\rangle$) or if you want to eliminate all the duplicate values before the last occurrence, giving you $\langle\,4, 3, 1, 7\,\rangle$.

For the first option, a fairly simple modification is to do a preprocessing step on the $a$ array, changing it to an array of pairs, $(value, index)$, where $index$ is the position of the element with that value. In the example above, this will give you a new array
$$
\langle\,(7, 0), (3, 1), (7, 2), (4, 3), (1, 4), (3, 5), (1, 6), (7, 7)\,\rangle
$$
Now, as we did originally, sort this array by the first element of the pairs, giving
$$
\langle\,(1, 4), (1, 6), (3, 1), (3, 5), (4, 3), (7, 0), (7, 2), (7, 7)\,\rangle
$$
(here we need to use a stable sort, like mergesort, to maintain the original place order). Eliminating duplicates, as above, we will have
$$
\langle\,(1, 4), (3, 1), (4, 3), (7, 0)\,\rangle
$$
and if we sort the result by the second index, we'll have
$$
\langle\,(7, 0), (3, 1), (4, 3), (1, 4)\,\rangle
$$
and looking at the first element, we'll have $\langle\,7, 3, 4, 1\,\rangle$, which is what we wanted.

This algorithm will take $O(n)$ steps to preprocess the array, $O(n\log n)$ steps to sort the result, $O(n)$ steps to eliminate the duplicate values, and $O(n\log n)$ steps to do the final sort, giving us an algorithnm that runs in time $O(n+n\log n+n+n\log n)=O(n\log n)$.


Asymptotic of divide-and-conquer type recurrence with non-constant weight repartition between subproblems and lower order fudge terms

According to the OP, to complete the proof we need to prove that for large enough $n$,
$$
(a_n n + \sqrt{n})^{a_n + 1/\sqrt{n}}((1-a_n)n + \sqrt{n})^{1-a_n + 1/\sqrt{n}} \leq n.
$$
Taking out a factor of $n^{1+2/\sqrt{n}}$, we get
$$
(a_n + 1/\sqrt{n})^{a_n + 1/\sqrt{n}}
(1-a_n + 1/\sqrt{n})^{1-a_n + 1/\sqrt{n}} \leq n^{-2/\sqrt{n}}.
$$
Dividing by $(1+2/\sqrt{n})^{1+2/\sqrt{n}}$, we get
$$
\left( \frac{a_n + 1/\sqrt{n}}{1 + 2/\sqrt{n}} \right)^{a_n + 1/\sqrt{n}}
\left( \frac{1-a_n + 1/\sqrt{n}}{1 + 2/\sqrt{n}} \right)^{1-a_n + 1/\sqrt{n}} \leq
\frac{1}{n^{2/\sqrt{n}} (1+2/\sqrt{n})^{1+2/\sqrt{n}}}.
$$
Raising to the power $1/(1+2/\sqrt{n})$, and defining $p = (a_n + 1/\sqrt{n})/(1 + 2/\sqrt{n})$, we get
$$
p^p (1-p)^{1-p} \leq \frac{1}{n^{(2/\sqrt{n})/(1+2/\sqrt{n})}(1+2/\sqrt{n})}.
$$

The left-hand side is $1/\exp h(p)$, where $h(p)$ is the entropy function. Hence it is maximized when $a_n = 1/4$, at which point $p \approx 1/4$. Since $(1/4)^{1/4} (3/4)^{3/4} < 1$, for large enough $n$ we can bound the left-hand side by some $\theta < 1$.
As for the right-hand side, as $n\to\infty$ it tends to $1$. Indeed, taking logarithm, we get
$$
\frac{2\log n}{\sqrt{n} + 2} + O\left(\frac1{\sqrt{n}}\right) \longrightarrow 0.
$$
In particular, for large enough $n$ it will be larger than $\theta$.


Bounds on the number of rotations in the insertion operation of a Red Black Tree

First of all, as pointed out in the comments, your tree is not a valid Red-Black tree. Here is why:

By definition, every path from the root of the tree to its leaves contains the exact same number of black nodes.
By definition, every red node has a black parent.

So, suppose you have a path with $n$ black nodes. How much longer can another path in this tree be? This other path has exactly $n$ black nodes too, so it can be longer only by having more red nodes. How many more? Well, you can add $n$ red nodes (in the alternating manner) to it (totalling $2n$ nodes) but as soon as you try to add $n + 1$ red nodes you are out of luck: some red node will have a red parent. Finally, this means that for any path in the tree there is no path that is more than twice as long.

Now, suppose you are looking at a subtree of a Red-Black tree. Also suppose that the root of this subtree is black (a formality). Then this subtree is also a Red-Black tree:

The root of the subtree is black (we chose it that way)
Every red node has a black parent (because it is so in the original tree)
Every path from the root of the subtree contains the same number of black nodes

The last statement is true because when we look at a subtree, we actually look at all the paths from the original tree that go through the root of the subtree. So, we essentially subtract the same number of black nodes which are above the root of the subtree.

Since the subtree is also a Red-Black tree, we already know that:

  for any path in the tree there is no path that is more than twice as long

Now look at your drawing, consider the subtree in the intermediate black node. It should be a Red-Black tree, yet it is not. There are at least two reasons:

There is a path (left-left) with one black node and there is a path (left-right-right-left) with two black nodes.
There is a path with $2$ nodes and there is a path with $5$ nodes and since $ 5 > 2 * 2$ which breaks the height property.

Another mistake you are making: you are inserting a red node as a right child of a red node. This is the third insertion case according to wikipedia which triggers color propagation first, not a rotation. A rotation might or might not take place further up the tree.


What is the cardinality of the set of regular grammars?

There is at least one regular grammar per regular language, and all of them are pairwise inequivalent (for any meaningful equivalence relation). Since there is at least a countably infinite number of regular languages¹, that's a lower bound for the number of regular grammars as well.

Without loss of generality², you can write down every regular grammar as finite string over a finite alphabet. Therefore, there are at most as many regular grammars as binary strings, of which there are countably infinitely many.

Combine the bounds to get your answer.

The lower bounds follows from $\{a\}^n$ being regular for every $n \in \mathbb{N}$.
Encode all symbols using binary numbers.


Check a variable within a range with a binary variable

If I understand corectly, you want to formulate a system of linear constraints on a real variable $a$ and a $\{0,1\}$-variable $y$
such that the solutions are given by
$$[0,1]\times\{1\} \bigcup [1,\infty)\times \{0\}.$$

This is impossible.  No linear constraint can put an upper bound on $a$ for some values of $y$ without putting an upper bound on $a$ for all values of $y$.

You can, however, just split the problem into two pieces and solve each one separately.


Why is the inverted index called so and not simply index?

Here is an array:

A[0] = Alice
A[1] = Bob
A[2] = Charlie

Here 0,1,2 are indices.
Now suppose that we want to know which index contains a given word. Then we use a dictionary:

D[Alice] = 0
D[Bob] = 1
D[Charlie] = 2

This is an inverted index (according to your Wikipedia quote).

The word index has different meaning in different contexts:

Technical books often have an index of terms at the end.
The Catholic church held an index of forbidden books.
In economics, there are financial indices.
In computer science, an index is usually an integer used to index into an array.


Constructing hitting sets for randomized algorithms

Suppose that $H$ consists of $m$ seeds chosen uniformly at random (thus $|H|$ could be smaller than $m$). For each $x \notin L$, the probability that $A(x,r) = 1$ for all $r \in H$ is at most $2^{-m}$. Since there are at most $2^n$ inputs of length $n$ not in $L$, we get that the probability that $H$ is not a hitting set is at most $2^n/2^m$. Choosing $m = n+1$, we see that the probability that $H$ is not a hitting set is at most $1/2$, and in particular there must exist a hitting set of size at most $n+1$. If $L \cap \Sigma^n \neq \emptyset$, we can improve this to $m = n$.


Which part of the computer allocates memory in RAM?

It is a combination of the standard C library (usually) and the operating system. No hardware is involved. Check out this answer on stackoverflow for more details.


DFA which accepts all strings starting and ending with 'aa'

One solution could be putting the final state right after the first two states.
From there, if an $a$ is read you stay in the final state, otherwise you move to a state analogous to $q_2$; from there, with two $a$s you return to the final state and with a $b$ you go back to $q_2$.

In short, just picture ($q_1, a$) going to $q_4$ instead of $q_2$. The rest should go unchanged.

This way, the automata should accept strings such as 'aa', 'aaa' and so on. And of course if it reads a 'b' it'll need two more 'a's to return to the final state.


But I can't figure out what the type should be for the denotation for identifiers.

That is because you are implicitly tracing the denotation function $⟦\_⟧$.
It might get easier to see the type if you explicitly trace the denotation
function by tagging them appropriately.
$⟦x + y⟧_{AExp}\sigma = ⟦x⟧_{AExp}\sigma + ⟦y⟧_{AExp}\sigma$.

Similarly, if you have an boolean expression with identifiers, for example:
$$⟦a_1 < a_2⟧_{BExp}\sigma =
\begin{cases}
True &\text{if} ⟦a_1⟧_{AExp}\sigma < ⟦a_2⟧_{AExp}\sigma\\
False  &\text{if} ⟦a_1⟧_{AExp}\sigma \geq ⟦a_2⟧_{AExp}\sigma\\
\bot  &\text{otherwise}
\end{cases}$$

In this case $\sigma : Identifier \rightharpoondown Int$.
The type of $\sigma$ would also be implicitly traced by the denotation function because, the object language construct makes it obvious. You can, if you want to be even more pedantic, carry around a tuple of $\sigma$'s, one for each type of variable lookup.
So, if your language has integer variables and boolean variables, your $\sigma = (\sigma_{Int}, \sigma_{Bool})$ and the correct component would be chosen depending on which $⟦\_⟧$ is being used.

  I guess I am not 100% how the other two are also CPOs...any enlightening comments?

Now, the poset structure is on the co-domain of the denotation function i.e. if you have a denotation $⟦\_⟧_{Stmt}$ the signature of the poset structure will be $(\alpha: State \rightharpoondown State, \preceq, \bot)$ similarly for $⟦\_⟧_{AExp}$ the structure poset structure would be $(\alpha: State \rightharpoondown Int, \preceq, \bot)$, where $\preceq$ allows you to compare the amount of information
contained by the information bearers $\alpha$, as explained on pg 159-160 in the notes you have linked.


Is this concatenation ({a} · {b})^2 ≠ a^2 · b^2?

They are different, because:
$(a \cdot b)^2 = abab$, since you need to concatenate $a$ and $b$ first, them reapeat the concatenation two times.
$a^2 \cdot b^2 = aabb$, since you need to concatenate the repetition of two $a$ with the repetition of two $b$.


The language-theoretic answer:

Convert each regexp to a DFA, then use the product construction to take the intersection of their languages. Check whether the resulting DFA accepts any word (i.e., whether its language is non-empty).  This might take exponential time in the worst case.

The pragmatic answer:

Every pattern has the form $\alpha \texttt{*} \beta \texttt{*} \gamma$, where $\alpha,\gamma$ are (possibly empty) strings of letters (without wildcards), and where $\beta$ is a (possibly empty) pattern (i.e., a string of letters and wildcards).  Let the patterns be $\alpha_i \texttt{*} \beta_i \texttt{*} \gamma_i$ for $i=1,2,\dots,n$.  Find a string $A$ so that each $\alpha_i$ is a prefix of $A$; if no such string exists, output "NO" and terminate.  Find a string $C$ so that each $\gamma_i$ is a prefix of $C$; if no such string exists, output "NO" and terminate.  Find a string $B$ that matches $\texttt{*} \beta_i \texttt{*}$ for each $i$; this can always be done.  Finally, output "YES" and the string $ABC$.

This is your exercise, so I'll let you figure out how to find each of $A$, $B$, and $C$ -- it's not hard.


Intersection of a recognizable language and a decidable language is decidable?

It's false. Let $L_1=\Sigma^*$ be a decidable language and $L_2=L_{HALT}$ be the (recognizable) language of all halting TM-string pairs. Then $L_1\cap L_2=L_2$, which is not decidable.


Strategy
The following linear-time algorithm adopts the strategy of hovering around $0$, by choosing either positive or negative numbers based on the sign of the partial sum. It preprocesses the list of numbers; it computes the permutation of the input on-the-fly, while performing the addition.

Algorithm

Partition $a_1, \ldots, a_n$ into a two lists, the positive elements $P$ and the negative elements $M$. Zeros can be filtered out.
Let $Sum=0$.
While both lists are non-empty
$~~~~~~$If $Sum>0$ { $Sum:=Sum+\text{head}(M)$; $M:=\text{tail}(M)$; }
$~~~~~~$else { $Sum:=Sum+\text{head}(P)$; $P:=\text{tail}(P)$; }
When one of the two lists becomes empty, add the rest of the remaining list to $S$.

Correctness
Correctness can be established using a straightforward inductive argument on the length of the list of numbers.

First, prove that if $a_1, \ldots, a_n$ are all positive (or all negative), and their sum does not cause overflow, then nor do the prefix sums. This is straightforward.

Second, prove that $Sum$ is within bounds is an invariant of the loop of the algorithm. Clearly, this is true upon entry into the loop, as $Sum=0$. Now, if $Sum>0$, adding a negative number that is within bounds to $Sum$ does not cause $Sum$ to go out of bounds. Similarly, when $Sum\le0$ adding a positive number that is within bounds to sum does not cause $Sum$ to go out of bounds. Thus upon exiting the loop, $Sum$ is within bounds.

Now, the first result can be applied, and together these are sufficient to prove that the sum never goes out of bounds.


Is there an isomorphism between (subset of) category theory and relational algebra?

Let me articulate the Curry-Howard-Lambek correspondence with a bit of jargon which I'll explain.  Lambek showed that the simply typed lambda calculus with products was the internal language of a cartesian closed category. I'm not going to spell out what a cartesian closed category is, though it isn't difficult, instead what the above statement says is you don't need to know! (Or that you already know, if you know what the simply typed lambda calculus with products is.)  For some type theory/logic to be the internal language/logic of a category means 1) that we can interpret the language into the structure on the category in a way that preserves the structure of the language (in effect a soundness condition), and 2) and "essentially" all the structure arising from cartesian closure can be talked about in terms of this language (a completeness condition).

The relational algebra is equivalent to the tuple or domain relational calculus which is essentially first order logic.  This statement is roughly Codd's theorem, though a similar theorem was proved decades earlier by Tarski for FOL and cylindrical algebras.  There is a bit of a subtlety though.  We want the queries in the relational calculus to be domain independent, which is to say that expanding the domain of possible values doesn't change the results of a query.  An example of a relational calculus query that is not domain independent is $\{ x\mid x = x\}$.  Every relational algebra expression is logically equivalent to a domain independent query in relational calculus.

Putting that aside, the categories whose internal logic (which is essentially a decategorified or proof-irrelevant form of an internal language) are Heyting categories for intuitionistic FOL and Boolean categories for classical FOL.  (The categorified/proof relevant versions are described by hyperdoctrines.  Also very relevant are pretoposes of various sorts.)  Note, that FOL, the relational calculus, and the relational algebra do not support aggregation.  (They also don't support the recursion necessary to represent a Datalog query.)  One approach to GROUP BY and aggregation is to allow relation-valued columns which leads to higher-order logic (HOL) and the nested relational calculus (NRC).  Once we have relation-valued columns, aggregation can be formalized as just another "scalar" operator.

Your examples point to the fact that a monadic meta-language is a decent language for queries.  The paper Monad Comprehensions: A Versatile Representation of Queries (PDF) spells this out well.  A more comprehensive and modern look is Ryan Wisnesky's PhD thesis, A Functional Query Language with Categorical Types (PDF), which is related to David Spivak's work which itself seems rather relevant to any interpretation of your question.  (If you want to go more historical, there was the Kleisli, A Functional Query System.)  In fact, the monadic meta-language is a decent language for queries in the nested relational calculus.  Wisnesky formulates NRC in terms of an elementary topos whose internal language is the Mitchell–Bénabou language which basically looks like an intuitionistic set theory with bounded quantifiers.  For Wisnesky's purpose, he uses a Boolean topos which will instead have a classical logic.  This language is quite a lot more powerful than (core) SQL or Datalog though.  It is worth noting that the category of finite sets forms a (Boolean) topos.


Prove NP-completeness for union of NP-complete language and language in P

If for any two disjoint languages $X,Y$, we have:

$\textbf{*} \hspace{1mm} X \text{ is NP-complete} \land Y\in P \Rightarrow X\cup Y\text{ is NP complete}$

then $P\neq NP$.

Let $L$ be some NP-complete language. $L\cup\overline{L}=\Sigma^*$ is not NP-complete, thus, using (*) we obtain $\overline{L}\notin P$, but $L\in P\iff \overline{L}\in P$.

In fact your statement is equivalent to $P\neq NP$. You can prove the opposite direction by using the fact that if $P\neq NP$ and $L$ is NP-complete, then $\overline{L}$ is not in $P$. In that case, you can reduce $X$ to $X\cup Y$ by checking if the input is in $Y$, and output some constant word outside of $X\cup Y$ if it is. This can be done since we know now that $Y\subsetneq \overline{X}$.


Since the entry was already populated, is this a conflict? If yes, what kind? Or since the 2 productions are the same we can just ignore it? Also if the second case is the right one, is the grammar LL(1)?

Although the entry was populated, this is not a conflict since the same rule is put into the table entry $M [ S , ( ]$, which can be ignored.

However, the grammar is not LL(1). This can be seen from either of the following.

The string ()() has following two different leftmost derivations.
$$S\rightarrow S'\rightarrow (S)SS'\rightarrow (S')SS'\rightarrow ()SS'\rightarrow()S'S'\\
\rightarrow()(S)SS'S'\rightarrow()(S')SS'S'\rightarrow()()SS'S'\\
\rightarrow()()S'S'S'\rightarrow()()S'S'\rightarrow()()S'\rightarrow()()$$
$$S\rightarrow S'\rightarrow (S)SS'\rightarrow (S')SS'\rightarrow ()SS'\rightarrow()S'S'\\
\rightarrow()S'\rightarrow()(S)SS'\rightarrow()(S')SS'\rightarrow()()SS'\\
\rightarrow()()S'S'\rightarrow()()S'\rightarrow()()$$
When we build the table entry $M[S', (]$, it will have two entries, $S' \rightarrow ( S ) S S'$ and $S' \rightarrow\epsilon$.

Although neither the new grammar nor the original grammar is LL(1), the language generated by either of them is LL(1) since it is generated by following LL(1) grammar.

$$S \rightarrow (S)S \mid \epsilon $$


Linear Programming Problem - what is feasible size for solution on a PC

I would assume a few times n^3 operations for n variables. How many operations per second can you perform? Using vector operations is not too difficult. Using 8 cores for one problem is hard. Depending on your programming effort you will be able to do between 1 and 100 billion operations per second, or 100 to 10,000 trillion operations per day, or very roughly n = 20,000 to 100,000. Buy a lot of RAM as well.


Counting frequencies of Element in an array

Maybe this:

answer = 0
lastVal = -1    //some value not inside [L,R]
count = 0
for i in {l..r}:
  if (array[i] != lastVal)
     count = 1
     lastVal = array[i]
  else
     count++
     if (count == 3)
        count = 0
        answer++

Edit: This code assumes that the set (1,1,1,1) is counted as one triplet not two.
i.e.: (1,1,1) and (1), not (1,1,1) and (1,1,1)


Difference between methods of converting from finite state machine to regular expression

There is a reference question on methods to convert a finite automaton into a regular expression. Personally I am very fond of the "State removal method" which is equivalent to the "Transitive closure method" you seem to be using. The reason is that the administration you do in the state removal seems to be less, and is more easily kept as labels to edges, rather than keeping track of many $R[i,j,k]$ sets.

Nevertheless, basically all methods use the same recursion, and one gets equivalent results. I say equivalent here, because there is no way to uniquely denote regular languages. Even when using the same method, when applying the reductions in a different order one gets a different result. But again, this is always the same language, only written in a different way.


What is the current state of the art in solving the halting problem?

The question as asked is indeed very broad. I give a brief answer here: What are some comparative studies on program termination verification tools?, but that really barely scratches the surface.

I do have several remarks:

In general, once must distinguish between whole program analyses, which are powerful, but do not scale very well for realistic development, and modular analyses which are weaker, but have hope of being integrated in a development environment. Isabelle and Idris both take this approach. As a side note, I'm not sure if this Fuhs et al paper corresponds to the "out of the box" termination check for Isabelle, but it might be enlightening in terms of what the state of the art is.
Termination of higher-order typed programs is difficult, because it involves subtle interactions between the type system features, the inductive types involved, and the "guard condition" required for function definitions. The more complicated the termination check, the less trustworthy the system, since consistency depends on it! These slides by Barras go into some of the nasty details for the Coq system.
Termination for higher-order systems with side effects (references) is particularly nasty. In particular, types are not enough anymore, even in the absence of recursion, see e.g. Landin's knot.


Alternate definitions of enumeration machines

Multitape machines are equivalent to single tape machines. You can simulate several tapes on a single tape. In particular, in order to simulate the "print state" model using the "write-only output tape" model, you simulate an extra output tape, and whenever the print state is reached, you copy the contents of the extra output tape to the write-only output tape. Therefore both models are equivalent.

More generally, all reasonable Turing machine models are equivalent. This is a special case of the Church–Turing hypothesis.


There's not enough information here to answer the question, but I can prove a pretty good guess based on how tokenizers are typically implemented.  Generally the tokenizer will run through the list of patterns, trying each one I sequence.  If one of them matches it takes the longest possible match as a token, then starts over at the top of the list.  I surmise this is the implicit background for the question.

So forinstance if you have abbbaacc and the rules a(b|c)* and b+ in that order then you'd tokenize that as abbb/a/acc.


Computing overlap of intervals in an integer programming framework

By overlap I understand its length (no its coordinates) since you didn't specify how to handle no overlap case.

First you need to know whether $x_1\le y_1$ which is just a comparison.

Next, you create new variables $l_1, l_2, r_1, r_2$ for which you know that $l_1\le r_1, l_2 \ge  l_1, r_2 \ge r_1$

Now the answer is $\min(\max(l_2 - r_1, 0), r_2 - r_1))$

How you build these constraints it is up to you. You can use approaches similar to https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ and https://blog.adamfurmanek.pl/2015/09/19/ilp-part-5/


The CPU tests all caches ways and selects the one that is both valid and have a matching tag address. It may occur concurrently on all ways or be sequential (with a preferred way, depending on the address)

When invalidating cache lines, only the valid bit needs to be cleared, the tag address value do not need to be modified, so it may contain stray values.

(Cache lines may be invalidated by the operating system for coherency with some DMA peripherals, because of self-modifying code, by hardware cache coherency algorithms like MEI/MESI, etc. Depends on the architecture.)

You cannot have several lines that are simultaneously valid and with the same tag address [and different data].

It may occur at power-up, if registers are not automatically reinitialized, and the boot sequence may have to manually clear the cache before enabling it using special accesses and/or instructions.


Looking for a paper comparing NLP methods with Data Mining techniques

there are probably several papers which fit this criteria and this may not be enough info/ criteria to really narrow it down. however some general bkg: google has pioneered research into the use of statistical algorithms for NLP for years and particularly (somewhat more recently) machine auto language translation. in this research one has a large database (aka "big data") of "translated sentence pairs" between language A and language B and the machine learning algorithm attempts to learn the relationship between the two, and its considered something of a relatively recent paradigm shift in the field because previously it was not considered/ thought possible, but google has achieved very good and improving results in the area, and my understanding is that some of this is now used/ incorporated in their live/ production/ public "translate" feature/ "product" built into the main search engine results.

try this nice list of papers: Natural Language Processing listing most NLP papers/research at google by date. there are 8 papers with the word "statistical" in the title. the most recent paper from 2013 may be close to what is being identified or cite the nearby area your speaker was referring to. other papers are from 2012 or older.

One Billion Word Benchmark for Measuring Progress in Statistical Language Modeling / Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, Tony Robinson
ArXiv, Google (2013)