Can someone explain me the Credit-Debit proof method for calculating operations?

I believe you are referring to the accounting method for amortized analysis. With these keywords you should be able to find the explanations you are looking for.


Set the size of the bag to the value you are trying to reach $t$. For each element $x \in S$ add one item to the set having both its weight and value equal to $x$. The claim is the $(S, t)$ is a yes instance of the subset sums problem if and only if the optimal value of the bag is equal to $t$ (why?).


What is the difference between a R-tree and a BVH?

Note that we want to be able to retrieve, for any query range, the points that are inside, or sometimes the points that are closest to that query range. That's why a bounding-volume hierarchy is useful.

However, bounding-volume hierarchy is a very general notion. When designing a bounding-volume hierarchy data structure in practice, it is extremely important to decide what kind of bounding volumes to use. The bounding volume can be any geometric shape: circle, hexagon, square, trangle or rectangle. It is important to keep this bounding volume very simple (we want it to be easy to store, rather than a complicated geometrical shape) and easy to fit other objects in (we don't want to waste a lot of free space in the bounding volume, as it can cause exhaustive search.

Quote from [1],

  Below, I will first explain what a bounding-volume hierarchy is and
  how it is used. After that, I will explain what issues have to be
  addressed when designing a bounding-volume hierarchy. I will then
  focus on a particular class of bounding volume hierarchies, namely
  R-trees, and give an overview of our results on Rtrees.

R-tree is a class of BVH data structures that uses rectangles as bounding-volume. Rectangles are easy to store and they can cover other shapes easily. It is noted that R-tree is not the only class of BVH and there are other BVHs proposed using different shapes. Even among R-trees, there is a variety.

This data structure is important for different communities: computer graphics, computational geometry, database and others. All of them need to deal with situations where they need to query a set of geometrical objects (or vectors).

[1] Herman Johannes Haverkort, Results on geometric networks and data structures, 2004.


Decidable product with an undecidable projection

Let $A$ be set of Turing machines that halt, which is clearly undecidable. Now $B$ needs to be something that helps you decide $A$ (a certificate if you will, in the sense of a certificate for a $NP$ problem). Hint: if a TM halts, it halts in a finite number of steps.


Unusual applications of regular expressions?

I don't know if this question belongs here (the answer could be subjective and depend on your definition of "unusual") but here is my favorite unusual application of regex:

  converting T9 input (2-9) to English text.

For example if the user wants to write hello they presses 42556. Convert the input to [ghi][def][jkl][jkl][mno] and test this regex against the whole vocabulary: the word hello will match.


Prove disprove an existence of mapping reduction between 2 sets

One basic idea is to observe that $B$ looks harder than $A$ since

we need to run a given Turing machine on one given input in order to find whether the pair is in $A$ but
we may need to run a given Turing machine on infinity many inputs in order to find whether it is in $B$.

That observation should motivate us to find a reduction from $A$ to $B$.

Suppose $(p,d)\in A$. Construct a machine that behaves as the following.

Upon an input string $s$, it checks whether $s$ is $d\sigma$, where $\sigma$ stand for a fixed letter in the alphabet.

If yes, it halts.
If no, it checks whether $s$ is $d$.

If no, it loops forever.
If yes, it simulate $p$ on $d$.

It should be routine to verify the construction above is indeed a reduction from $A$ to $B$.


Suppose you have a min heap $H$, and you want to find successor one of the leaf node that its successor is maximum value, so you need to scan all leaves in tree, in addition we know that number of leaves in $H$ is $O(n)$. So you need read $O(n)$ nodes.


Is it possible to "unshift" onto a queue using this theoretical "queue automaton"?

Without any way of creating an unmistakeable marker on the tape, this is not possible. (As far as I recall (cannot check right now), the tape in Manufactoria is actually bounded, which would make a difference, but let us assume this is not the case.)

Let $i$ be any input string, and consider the computation of a given automaton on $i$, i.e. the sequence $(s_0,x_0),\dots,(s_n,x_n)$ with $s_0=sInit$, $x_0=i$, $s_n=sTerm$, and $(s_{j+1},x_{j+1}) = step((s_j,x_j))$. In iteration $j$, we read and remove the first letter $a_j$ of $x_{j-1}$ and append a word $u_j$; these first letters form a word $w=a_1\dots a_n$.

It is not hard to see that any input word which starts with $w$, i.e. $wv$ for some $v$, is indistinguishable from $i$ to our automaton: it reads the same letters as it would on $i$, and as a result goes through the same states and appends the same $u_j$, so that the resulting word at the end is $vu_1\dots u_n$. This will fail to have the required form for any $v$ not starting with $G$ (and many others as well).


The reduction is described in a classic paper of Miller.


Since coNP is confusing, let us construct an NP machine for $\overline{C}$. The input to the machine is a pair $\langle G,S \rangle$, where $S$ is a cover of $G$. The machine guesses another cover $T$, and verifies that $T$ is a cover of $G$ which is smaller than $S$. The cover $T$ is thus a witness to the fact that $S$ is not a cover of minimum size.

If $S$ is not a minimal cover, then there exists some smaller cover $T$, and so the machine accepts the instance $\langle G,S \rangle$ if it guesses $T$. Conversely, if $S$ is a minimal cover, then no smaller cover exists, and so the machine rejects the instance $\langle G,S \rangle$ whatever the guess is. In total, the machine accepts the language $\overline{C}$.

Here is a another way to look at things. We construct a machine that on input $\langle \langle G,S \rangle,T \rangle$, accepts if $S,T$ are covers of $G$, and $T$ is smaller than $S$. Then

  There exists $T$ such that the machine accepts $\langle \langle G,S \rangle,T \rangle$ if and only if $\langle G,S \rangle \in \overline{C}$.

This machine is polytime, and it accepts $\overline{C}$, showing that $\overline{C} \in \mathsf{NP}$, and so $C \in \mathsf{coNP}$.


Common name for a group of commands which break the linear structure of the program

These are control flow statements. There is a quite a large list of them on their Wikipedia page.


Does crossover take the parents or the offsprings? How to select parents with linear ranking?

For example, there are 100 individuals with crossover probability 0.8. Does it mean I take 80 parents (40 couples), or 80 offsprings?

0.8 is the probability that crossover will occur at a particular mating.

The standard algorithm samples the population with replacement (the same parent may be selected more than once):

you pick out 50 couples;
crossover is performed for (about) 40 couples producing 80 new individuals (80% of the new generation is produced via crossover);
(approximately) 10 couples are copied to the new population (here ignoring the mutation operator).

(this is a generational approach).

  I'm using linear ranking as the parent selection because of the fitness values are close to each other. How can I select the parents after I get the values of linear ranking?

Just use the standard roulette wheel selection algorithm  and, rather than weighting each candidate by its fitness score, use its rank.

  If we only take the best 80 individuals as parents, then what is the point of using linear ranking as parent selection?

It's not deterministic. An individual has a probability of getting selected as a parent (the probability is linked to the rank).

With rank selection the best individual is more likely to be chosen than the second one, but both have the same probabilities of being chosen whether the best had ten times the fitness of the second best, or only a slightly greater fitness.


Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference

Assume partially decidable languages are closed under symmetric difference, and let $A$ be a language that is partially decidable but not decidable.  Then, where $U$ is the language that includes everything,

$A \otimes U = (A - U) \cup (U - A) = \overline{A}$.

Then $\overline{A}$ must also be partially decidable, and $A$ is decidable; this is a contradiction.  (This builds on an answer above, which suggested investigating complementation.)


Overlaying Two Matrices So That Sum Of Squared Differences Is Minimized

I try to summarize the results of the discussion in the comments:

Using a heap instead of a list would be better suited for the proposed idea since all operations to be performed on the list are sorting, returning the smallest element and changing an element followed by resorting the list.  These are almost exactly the operations supported by heaps, which will deliver better performance.
The sums $\sum_{k,l} (L_{i+k,j+l}-S_{k,l})^2$ can be expressed as $A_{i,j}+B_{i,j}-2C_{i,j}$ where $A_{i,j}:=\sum_{k,l} L^2_{i+k,j+l}$, $B_{i,j}:=\sum_{k,l} S^2_{k,l}$ and $C_{i,j}:=\sum_{k,l}L_{i+k,j+l}S_{k,l}$.  Here $B_{i,j}$ does not depend on $i,j$ and $A_{i,j}$ can obtained from its predecessor $A_{i',j'}$ by only updating two rows or columns, if the order in which the $i,j$ are perused is chosen wisely.  Most importantly, $C_{i,j}$ describes a convolution, which can be calculated very fast by FFTs, convolution in the frequency domain corresponds to (pointwise) multiplication in the time domain!  But even without implementation of FFT, this algorithm scores better than the naive approach, as it only performs one operation (multiplication) instead of two (subtraction and squaring) in the large (size $HW$) sums.


Find string that minimizes the sum of the edit distances to all other strings in set

The problem is known as "median string problem" and it is NP-complete; some results can be found searching with Google; in particular "2-Approximation Algorithms for Median and Centre String Problems". If $x$ must be one of the points in $S$ then the problem becomes solvable in polynomial time.


Fast polynomial calculation over $\mathbb{Z}_{487}$

You can very efficiently compute $a(x_j)$ for each of those 243 values of $x_j$ by simply evaluating $a(\cdot)$ using Horner's rule.  The running time is 243 evaluations of $a(\cdot)$, and each evaluation requires 243 modular multiplications and 243 modular additions.  That's a total of $243^2 \approx 2^{16}$ modular multiplications.  Consequently, the total running time will be extremely efficient, even without trying to split this into three polynomials $a_0(x),a_1(x),a_2(x)$.

If you want a more efficient method, a better approach is to use a Discrete Fourier Transform.  You can use a DFT over $\mathbb{Z}_{487}$ to evaluate $a(x)$ at 256 different points in running time that's asymptotically $O(n \lg n)$, where here concretely $n = 256$.  [Alternatively, you could use the Number-theoretic transform for $\mathbb{Z}_{487}$ to evaluate $a(x)$ at $486$ points, and do all your calculations in $\mathbb{Z}_{487}$.]


What is the maximum directly adddressable memory capacity?

Start with a simpler example. Suppose you only had 3 address bits, rather than 24. With $3$ bits we could have $2^3=8$ addresses: 000, 001, 010, 011, 100, 101, 110, 111. In this case, we could think of memory as being divided up into 8 chunks, of equal sizes, with one address per chunk:

memory:  chunk 0 | chunk 1 | chunk 2 | chunk 3 | chunk 4 | chunk 5 | chunk 6 | chunk 7
address:   000       001       010       011       100       101       110       111

For example, the contents of chunk 3 would be addressed by the three bits 011. Now how much memory would there be in total? It'll clearly be 8 times the size of a chunk. Stalling is using a memory model where the chunks are bytes, so with 3-bit addresses, we would have a total memory of $2^3=8$ bytes: one byte per address.

A different computer, though, might be built so that each chunk was 4 bytes. On such a machine with 3-bit addresses we would have $8\times 4 = 32$ bytes of memory, 4 bytes per address.

At any rate, with 24-bit addresses, we'd have $2^{24}= 16777216 = 16\text{M}$ possible addresses, hence that many possible chunks. If each chunk was a byte that would mean that the total addressable memory would be 16777216 bytes, or 16MB. Similarly, if each chunk was 4 bytes long, the total addressable memory would be (chunk size $\times$ number of addresses), or $4\text{B}\times 16\text{M} =64\text{MB}$.


Constructing a binary tree with given traversals

You are doing well. From the postorder determine the root, from the inorder determine which letters are in the left and right subtrees.
Once you have done that, you can proceed in the same way for the subtrees.

In the example you start with postorder DCBGFE A
and inorder BDC A FGE.

Using postorder you determine the root as A, and using inorder split the letters into left BDC and FGE.
Thus (1) the left subtree has postorder DCB and inorder BDC
while (2) the right subtree has
postorder GFE and inorder FGE.

Let us look at left subtree (1) which you mention in your question. The root is B, and both DC follow to B in the inorder and thus are right from B.
How to place them. This tiny subtree has postorder DC and inorder DC. Hence its root is C, and D is before C in the inorder, and is in the left subtree of C.


Why $xx^TM$ requires $O(dk)$ operations?

The matrix $xx^T$ has the $(i,j)$th entry $x_i x_j$. Hence
$$
(xx^TM)_{ij} = \sum_k (xx^T)_{ik} M_{kj} = \sum_k x_i x_k M_{kj} = x_i \sum_k x_k M_{kj}.
$$
We can compute $\sum_k x_k M_{kj}$ for each $j$ in linear time. Given that, we can compute the product matrix in linear time using the above formula.


Simple interepretation problem regarding Polynomial Hierarchy?

There is a logical interpretation of the various levels of the polynomial hierarchy, which extends the witness characterization of $\mathsf{NP}$ and $\mathsf{coNP}$.

A language $L$ is in $\Sigma_k^P$ if there is a polytime predicate $f$ and a polynomial $\ell$ such that
$$
x \in L \Leftrightarrow \exists |y_1| \le \ell(|x|) \; \forall |y_2| \le \ell(|x|) \; \cdots Q |y_k| \le \ell(|x|) \; f(x,y_1,\ldots,y_k).
$$
Here:

$\exists |y| \le \ell(|x|)$ means that there exists a number $y$ whose length is at most $\ell(|x|)$ such that ...
$\forall |y| \le \ell(|x|)$ mean that for all $y$ whose length is at most $\ell(|x|)$, the following holds ...
$Q$ is $\exists$ if $k$ is odd and $\forall$ if $k$ is even.

Similarly, $L$ is in $\Pi_k^P$ if it can be written in a similar way, only starting with $\forall$.

As an example, $\mathsf{NP}^{\mathsf{NP}}$ is $\Sigma_2^P$, and consists of all languages such that
$$
x \in L \Leftrightarrow \exists |y_1| \leq \ell(|x|) \; \forall |y_2| \leq \ell(|x|) \; f(x,y_1,\ldots,y_k).
$$
As another example, $\mathsf{coNP}^{\mathsf{NP}}$ is $\Pi_2^P$.

Your third example is $\mathsf{P}^{\mathsf{NP}}$, which is $\Delta_2^P$. I'm not sure what is the logical characterization.


How to connect line segments to form the least number of paths

You could solve this using any algorithm for the traveling salesman problem.  Construct a graph with one vertex per line.  Add an edge of cost 0 from line to another if they share an endpoint (these correspond to extending an existing path).  Add an edge of cost 1 between each other pair of lines (these correspond to starting a new path).  Now find the shortest traveling salesman tour of this graph.  That will correspond to a minimal set of paths that cover all of the lines; the number of lines will be equal to the weight of the traveling salesman tour.  There are standard algorithms and solvers for the TSP.


Asymptotic complexity of function with two Input variables

No, it's not safe to say either.  The intuition: When $n$ is really large, $f(m,n)$ grows faster than $O(m \log n)$.  When $m$ is really large, $f(m,n)$ grows faster than $O(n^2)$.

Instead, what you can say is that $f(m,n)$ is $O(m \log n + n^2 + n \log \log m)$.  Why?

$$\begin{align*}
f(m,n) &= \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000\\
  &=m \log n + 100n\log \log m + 100n\log 5 + 150m + 4n^2 + 1000\\
  &=O(m \log n) + O(n \log \log m) + O(n) + O(m) + O(n^2) + O(1)\\
  &=O(m \log n) + O(n \log \log m) + O(n^2) + O(m \log n) + O(n^2) + O(1)\\
  &=O(m \log n + n \log \log m + n^2).
\end{align*}$$

If $n \log \log m = O(m \log n + n^2)$ (I'm not sure if this is true), then you could simplify this to $O(m \log n + n^2)$.


Linear Programming: algorithm to check if ratios can be combined with n bottles to equal a given ratio

I don't know what class this is for, and how much linear programming you are learning in it, so I don't really know what you need.

One way to do it: assuming $a_i + b_i + c_i = 1, \ \forall i$, use the linear program:

$$ \max x$$

such that

$$\eqalign{
\sum_i  a_i \lambda_i &= a,\\
\sum_i  b_i \lambda_i &= b,\\
\sum_i  c_i \lambda_i &= c, \\
\lambda _i -x &\geq 0 \quad \forall i.
}$$

If there is a solution with $x \geq 0$, then you're done. Why? If $x \geq 0$, then there is a set of positive $\lambda_i$ satisfying the first three equations above: $\sum_i a_i \lambda_i = a$. The $\lambda_i$ give you the proportions with which to mix the bottles.  If one of the $\lambda_i$ were less than $0$, then this would tell you to add a negative amount from that bottle, yielding an unphysical "solution". If there is no solution of the linear program with $x \geq 0$, then no combination will give the proportions $a:b:c$, as that would give a solution to the linear program with $x \geq 0$.


Doubt in definition of closure under concatenation operation in Recursive Enumerative languages

If $L_1,L_2$ are two languages over a common alphabet, then their concatenation is given by
$$ L_1 L_2 = \{ x_1 x_2 : x_1 \in L_1 \text{ and } x_2 \in L_2 \}. $$
If $L_1,L_2$ are r.e. then so is their concatenation. To see this, you can use the following algorithm. Given an input $x$, consider all possible partitions $x = x_1x_2$. For each partition, run a machine for $L_1$ on $x_1$ and a machine for $L_2$ on $x_2$; do this in parallel for all possible partitions. Accept if for some partition $x = x_1x_2$, you find that both $x_1 \in L_1$ and $x_2 \in L_2$.


Are probabilistic search data structures useful?

I don't think there is a polynomial probability for losing 'balance'. After you insert an element in a skip list, you build a tower of copies above it by flipping a coin until it comes up heads.

So you have layers with fewer and fewer elements as you reach the top. Since a tower has height $k$ with probability $2^{-k}$, there is an element at height $k$ with probability (union bound) of less than $n/2^k$. Hence having an element at level $c\log n$ has probalitiy less than $1/n^c$. Towers of height $\omega(\log n)$ have subpolynomial probability. Let $M$ be the maximum level, then we have

$$E[M] = \sum_{k\geq 1} Pr(M\geq k) \leq \log(n) + \sum_{k\le \log(n)} n/2^k = \log(n) + 2.$$

Furthermore, on level $k$ there are $n/2^k$ elements with very high probability, as this is the sum of $n$ independent random variables and you can use Chernov's bound.

Since you can also show that you only do a constant number of steps per level (with very high probability!), search costs are logarithmic.

So you would have to be very unlucky indeed to end up with an unbalanced list. Note that 'luck' here is independent of your data, unlike for example in unbalanced search trees. Coin flips in Skip Lists are always random.

As far as I know, skip lists are of great practical interest, because it is relatively easy to implement them as lock-free search structures, with the obvious benefits. B-trees on the other hand are rather difficult to make performant under concurrent accesses.


Can we remove duplicates faster than we can sort?

It is a classical result that the element distinctness problem requires $\Omega(n\log n)$ comparisons in the comparison model (the one used to analyze sorting algorithms); in fact, it also requires $\Omega(n\log n)$ time in stronger models such as algebraic decision trees, in which we are allowed to compute the sign of arbitrary bounded degree polynomials (rather than just $x_i - x_j$).

The element distinctness problem asks whether all elements in the input are distinct. This is clearly easier than your problem, since you can just compare the sizes of the input and output arrays. Hence in these computation models, you cannot do asymptotically better than $n\log n$.


This appears to be an instance of the assignment problem, where you are trying to match up the $nm$ cells of $M$ with the $nm$ cells of $M'$.  For each place where $M[i,j]$ may get permuted to, you can compute the cost of that: namely, if it is permuted to $M'[i',j']$, then its cost is $(i'-x P[M[i,j]])^2 + (j' - y P[M[i,j]])^2$.  Then you can use standard algorithms for the assignment problem, such as the Hungarian algorithm.  Whether this is practical or not may depend on how large $nm$ is.  If it's not practical, you could instead try a heuristic, such as local search algorithm based on making swaps.


Depending on the programming language, some or all objects might have reference semantics. What this means is that when you assign the object to a variable or pass it to a method, it's still the same object, not a copy. This means the object maintains identity independent of the values it holds.

For example, in C#, classes have reference semantics, while structs do not. This means that for a class C and struct S:

C c1 = new C();
c1.Name = "c1";
C c2 = c1;
c2.Name = "c2";
WriteLine(c1.Name); // writes "c2"
WriteLine(c1.Equals(c2)); // writes "True"

S s1 = new S();
s1.Name = "s1";
S s2 = s1;
s2.Name = "s2";
WriteLine(s1.Name); // writes "s1"
WriteLine(s1.Equals(s2)); // writes "False"

As you can see, changing the class instance through one variable affects the other variable too, showing that both refer to the same object. Also, you can see that the two variables are equal. So, classes in C# maintain object identity.

For the struct, each variable is independent: changing one does not affect the other. This means that structs in C# do not have object identity in C#.

Other languages behave differently. For example, Java does not have structs at all, all user-defined types have reference semantics.

As another example, in C++, you can decide to use reference semantics or not on a case-by-case basis, by choosing to use pointers (or references) or not.

Note: Equals() in C# can be overridden. But since C or S do not override it, the default implementation of Equals() mostly behaves the way we want for both.


The term "point cloud" is normally used to refer to a set of points (locations) in 3D space.  So, a table of temperatures would normally not be called a "point cloud".


Why are different logarithms in the same Θ even thought their difference diverges?

You are missing one thing in your definition of asymptotic notation. In addition to only caring about large values of N, we also ignore constant multiplicative factors.

$f$ is $O(g)$ if there exists a large $N$ and a constant $c$ such that
$f(x) < c g(x)$ for all $x \ge N$

In the $\log_3$ vs $\log_2$ case its true that we have $\log_3 x < \log_2 x$ for all big $x$. However, its also true that

$\begin{equation*}
   \log_2 x
      = \frac{\log_3 x}{\log_2 3}
\end{equation*}$

so we can choose some $c$ larger than $\log_2 3$ to end up with:

$\begin{equation*}
    \log_2 x < c \cdot \log_3 x
\end{equation*}$

and thus $\log_2 x$ is $O(\log_3 x)$.

The same reasoning does not apply to $2^n$ and $3^n$. There is no constant multiplicative factor that will make the $2^n$ catch up to $3^n$ for all big $n$.


You can reduce clique (or independent set) to your problem, so it is NP-hard. Just take the adjacency matrix as your matrix, use the same parameter $k$ (the size of the clique), and declare that there is a clique in the graph if the maximum score is $\binom{k}{2}$.


For each $i$, find minimal $j>i$ such that $A[j]>A[i]$

its next greater element problem
its solvable using stack
u can learn it from here (in method 2)
for more practice of this useful method u can solve these problems:

Largest Rectangle
https://www.hackerrank.com/challenges/largest-rectangle/

And xor Or
https://www.hackerrank.com/challenges/and-xor-or

Poisonous Plants
https://www.hackerrank.com/challenges/poisonous-plants

196A - Codeforces
http://codeforces.com/problemset/problem/196/A

319B - Codeforces
http://codeforces.com/problemset/problem/319/B

Minimum Sum
http://agc005.contest.atcoder.jp/tasks/agc005_b

these are solvable using #next_greater_element


Dynamic Programming Subset Sum Problem with twist

Hint: Arrange the weights in increasing order. You might also need to make other changes, but sorting the weights is a good first step.


In your definition, $x$ must be a terminal symbol. In particular, it cannot be $\epsilon$, which is the empty string. The productions $A \to B$ and $A \to xy$ don't conform to the specifications you give, hence they don't belong in a right linear grammar according to the definition you provide.


What data size is sent to and read from physical RAM?

There is no requirement that a transfer between memory and cache use one line per bit. In fact, DDR3 DRAM uses a burst length of eight, meaning that eight bits are transferred per line in four cycles at double data rate. (DDR3 supports burst chop of only four transfers, but this has the same timing constraints for a read following a read and a write following a write. Burst chop can reduce energy use and other DRAM ranks can use the memory channel during the inactive time.) By requiring burst transfers, memory chips can be made more cheaply while still providing high bandwidth.

The write interface to DRAM is likewise constrained. In addition, the modified nature of portions of cache smaller than a cache block is usually not tracked, so the cache would not know that it actually only needs to writeback part of the cache block. (Such constraints are not inherent in memory systems. Caches could track validity or cleanness at any granularity, at the cost of addition storage and complexity. Interfaces could be defined to support arbitrary sized transfers, including the use of mask bits to tell the memory chips to ignore specific data, but the complexity is generally not considered worthwhile.)

One advantage of a narrower interface is that synchronization of all the lines is easier, making it easier to produce an interface with a fast clock providing higher bandwidth with the same number of lines.

Note also that more than one memory channel can be implemented in a CPU. It is also possible to gang two or more memory channels together to form a single interface.


How to eliminate ambiguity of the follwing CFG?

Basically you have $L = L_1 \cup L_2$ where $L_1 \cap L_2 \ne \emptyset$. So naively writing the two productions:

$$L \to L_1 \\
L \to L_2
$$
will create an ambiguity. What's needed is to create $Ḷ_1' = L_1 - L_2$ in order to use the CFG
$$L \to L_1' \\
L \to L_2
$$
This produces the same language, resolving the ambiguities in favour of $L_2$.

Context-free languages are not closed under set difference, so this is not a general solution. But in this particular case there is no problem.

Suppose we start with the two languages $L_1 = \{ a^ib^jc^kd^i \}$ and $L_2 = \{ a^ib^jc^jd^k \}$, which are not disjoint since $\{a^ib^jc^jd^i\}$ is a subset of both.

So we define
$$Ḷ_1' = L_1 - L_2 = \{ a^ib^jc^kd^i \mid j \ne k\}$$
and are pleased to observe that it is context-free:

$$\begin{align}L_1' &\to E \mid a \; L_1'\; d\\
E &\to B \mid C \mid b \; E \;c\\
B &\to b \mid B b \\
C &\to c \mid C c
\end{align}$$

Meanwhile, $L_2$ is simply

$$\begin{align}L_2 &\to A\; F\; D \\
F &\to \lambda \mid b\;F\;c \\
A &\to \lambda \mid A a \\
D &\to \lambda \mid D d
\end{align}$$


P decision problem that potentially requires at least $\Omega(n \log n)$ in the Turing model?

We know that there exists some problem in $P$ that can't be solved in $O(n \log n)$ time on a Turing machine; this follows from the time hierarchy theorem.  As a result, there definitely exists some problem in $NP$ that can't be solved in $O(n \log n)$ time on a Turing machine.  So your "it is not proven that..." statement is wrong; that is proven.

Model of Computation

When dealing with relatively "small" running times, like $O(n \log n)$, the model of computation can make a big difference.  For instance, there might be problems that are solvable in $O(n \log n)$ time on a multitape Turing machine but not on a single-tape Turing machine.  Also, some researchers have studied problems that can be solved by circuits.

For circuits, the situation is rather depressing.  We cannot identify any computable function $f:\{0,1\}^n \to \{0,1\}$ where we have a lower bound on circuit complexity that is $\omega(n)$.  We know there exist problems that can't be solved by any circuit of size $O(n)$, but we can't identify any specific problem where we can prove this is the case.  See, e.g., https://cstheory.stackexchange.com/q/21400/5038.  This illustrates just how hard it is to prove lower bounds (see, e.g.,
https://cstheory.stackexchange.com/q/17789/5038 and references therein).

Plausible candidates

Nonetheless, there are many plausible candidates where it might not be possible to solve them in $O(n \log n)$ time.  For instance, 3SUM and other similar problems don't appear to have any $O(n \log n)$-time algorithm that we can find, so they might be reasonable candidates.  Other examples include all-pairs shortest paths and linear programming.

For more, see https://cstheory.stackexchange.com/q/1284/5038 and https://cstheory.stackexchange.com/q/17578/5038.

Careful with those Omegas!

You wrote that you wanted to find a problem that can't be solved in $O(n \log n)$ time.  You also wrote that you wanted to find a problem that takes $\Omega(n \log n)$ time to solve.  Beware that those aren't the same thing.  The former is equivalent to looking for a problem that takes $\omega(n \log n)$ time to solve.

It is known that any language (decision problem) that can be solved in $o(n \log n)$ time on a single-tape Turing machine is in fact a regular language.  Thus if you take any language that is not regular but is in $P$, it follows that the running time for a Turing machine to decide it is $\Omega(n \log n)$.  Beware that this might not be what you want: this means the running time might be $\Theta(n \log n)$ or it might be even larger.  I suspect you meant to ask for a problem that cannot be solved in $O(n \log n)$ time, i.e., that requires $\omega(n \log n)$ time.


Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?

The most direct method to solve the problem is to show to build, starting with finite state automata $A_L$ and $A_M$ for the regular languages $L,M$, a new automaton for the new language $K$ which is constructed from $L$ and $M$.

For this you need an idea, a formal construction, and (if you are not convinced) a proof the construction is correct.

The idea can be as follows. If the automaton $A_L$ follows a path on a word, one should be able to decompose this in the form $uvw$ in such a way that the subword $v$ can be accepted by $A_M$. The middle part $v$ should be made invisible in the new automaton for $K$. This idea can be made formal using concepts from finite automata like $\varepsilon$-instructions and direct product construction.

If you have knowledge of other closure properties then the one from this exercise can be deduced. Closure properties you then need are intersection, morphism and inverse morphism.

Enjoy.


is (infinitely often p) ∨ (infinitely often ¬p) valid?

The LTL formula for the given problem could be: $G(F(p)) \lor G(F(\lnot p))$. Consider a $\omega$-word $w = w_1w_2w_3 \ldots$ over $\{\{\}, \{p\}\}$:

Let $w_i = w_iw_{i+1}\ldots$
\begin{align*}
& \; \; \; \; \; \;  \; \; \; w \not\models G(F(p))\\
&\implies \exists i . w_i \not\models F(p)\\
&\implies \exists i. \forall j \geq i . w_j \models \lnot p\\
&\implies \exists i. \forall j \geq i . w_j \models F(\lnot p)\\
&\implies \exists i. w_i \models G(F(\lnot p))\\
&\implies w \models G(F(p)) \lor G(F(\lnot p))
\end{align*}

Therefore, $G(F(p)) \lor G(F(\lnot p))$ is valid.

Note that this doesn't mean that $G(F(p)) \land G(F(\lnot p))$ is not satisfiable. For example, consider the word $w=\{p\}\{\}\{p\}\{\}\{p\}\{\}\ldots$


You can answer your own question by checking whether, for each edge $(u,v)$ of the graph, $u$ appears before $v$ in each of the three candidate topological orders that you listed.


Prove that the complements of pumping-style languages are context-free

The first thing to ask is, why is the claim even true? CFLs, in general, are not closed under compliment, but this language certainly does (yet, it is not regular, so cosure for $\Sigma^*\setminus L$ cannot be used here). So why is the complement a CFL?

The reason is that the language $L$ is actually deterministic context-free, and this class have different closure properties, specifically, it is closed under complementation.

To prove $L$ is a DCFL, we need to build a deterministic PDA for it. There are some technicalities for the case when $v=x$ or $x=y$ or $v=x=y$, but just to give the  idea of the construction, let's assume they are all different, $u\ne v\ne x\ne y\ne z$. Since $x,y,u,v,z$ are fixed, it is easy to construct a Deterministic PDA for $L$: it tries to match the input to $u$ (and rejects if it can't), if it finds $u$ it continues to match the input to $v$ at least once (and count the number of times it succeeds, using the stack), the first time it fails, it assumes the input has gotten into the $x$ part, and from there checking the $xy^iz$ part is obvious.

If you reverse the accept/reject of the DPDA of $L$ you will receive a DPDA for $\overline L$, thus also $\overline L$ is deterministic CFL, and specifically, it is a CFL.


Computing a pre-topological sort using a BFS/a queue

For post-order see: https://en.wikipedia.org/wiki/Tree_traversal#Post-order.

The algorithm just says perform step 2 using BFS traversal rather than DFS traversal, and then let $L$ be vertices of BFS in the postorder. After that perform step 3 to compute SCCs.


You are misinterpreting the statement quoted at point 1. We are unable to prove the existence of a single language in NP that is not in P, but we suspect that there are infinitely many, in fact, we suspect that all NP-complete languages are not in P.


To calculate how many times a certain year repeats itself in the calendar within a given year range

Basically, the "configuration" of a year, if I understand well can be described as a state $Y_i = (D_i, L_i)$ with $D_i$ the weekday of January the $1^{st}$ (0 to 6 for monday to sunday) and $L_i$ which is 1 if $Y_i$ is a leap year and 0 else.

So, comparing the state of 2 years, you can decide wether they have the same configuration.

As a year has 365 days (366 for a leap year) and $365 \mod 7 = 1$ (2 for a leap year), there is a simple relation:

$D_{i+1} = D_i+L_i+1 \mod 7$

As there is one leap year every four years (without 100-exception), it is interesting to also notice there is a 5-step on weekday every 4 years:

$D_{i+4} = D_i+5 \mod 7$

Now, how to not loop on all year ?

Let's consider leap years are all years divisible by 4 without exception. Then, from a starting year $Y_0$, we seek the next year with same configuration $Y_s$. Let's consider all possibles values of $M_0 = Y_0 \mod 4$ :

$M_0 = 0$, then $Y_0$ is a leap year, as $GCD(5, 7) = 1$, 7 of the 5 steps (28 years) are necessary to reach the same configuration: $Y_s = Y_0 + 28$ and $M_s = 0$
$M_0 = 1$, then $Y_s = Y_0 + 6$ and $M_s = 3$
$M_0 = 2$, then $Y_s = Y_0 + 11$ and $M_s = 1$
$M_0 = 3$, then $Y_s = Y_0 + 11$ and $M_s = 2$

Thus, if the considered year is a leap year, you have exactly the same configuration every 28 years, else, you have 3 times the same configuration every 28 years. In the latter case, the $B-A \mod 28$ reamaining years may be simply considered with above rule.

To consider the 100-exception, you may do the same work adding an extra variable modulo 100 (quite more laborious).


The borderless words are also known as unbordered or bifix-free ("A note on bifix-free sequences", PT Nielsen, in a paper as early as 1973).

The language of unbordered words is not even context-free, see the paper "Inverse star, borders, and palstars" by Ramparsad etal, in TCS with a preprint on ArXiv. The technique to obtain this result is Ogden's Lemma, an extension of classical pumping, and discussed elsewhere on this forum.


Question about DFA for exact string matching

Assume that you build an automaton for finding occurrences of $bububa$ in the input string. When the automaton reads the input string $bubububa$, then it after reading $bububu$, it must not just return to state $\epsilon$, as otherwise an occurrence of $bububa$ is not detected. Also, jumping back to state $bu$ is would not do the trick, as then again, the $bububa$ starting in letter 3 of the word would be missed. Rather, after seeing a $u$ in state $bubub$, the automaton must transition to $bubu$ in order to no miss the possibility that only the first two letters are to be ignored.

The last line in the definition of $E$ describes how the back transitions in the automaton are found: in order not to miss any occurrence of $bububa$, the state in the automaton jumps back as little as possible.


Yes... You can also practice with an implementation of your own. I have created such an implementation and a good test is to compile this with different optimization levels in gcc:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node {
    int node_id;
    int data;
    char *name;
    struct node *left;
    struct node *right;
} node;

node *newNode(int data, char *name, int node_id) {
    node *new_node = malloc(sizeof(node));
    new_node->data = data;
    new_node->name = name;
    new_node->node_id = node_id;
    new_node->right = new_node->left = NULL;
    return new_node;
}

node *insert_node(node *root, int data, int node_id, char *name) {
    if (root == NULL)
        return newNode(data, name, node_id);
    else {
        node *cur;
        if (node_id < root->node_id) {
            cur = insert_node(root->left, data, node_id, name);
            root->left = cur;
        } else if (node_id > root->node_id) {
            cur = insert_node(root->right, data, node_id, name);
            root->right = cur;
        }
    }
    return root;
}

node *find_node_data(node *root, int node_id) {
    if (root == NULL)
        return NULL;
    else if (root->node_id == node_id)
        return root;
    else if (root->node_id > node_id)
        return find_node_data(root->left, node_id);
    else
        return find_node_data(root->right, node_id);
}

void print(node *np) {
    if (np) {
        print(np->left);
        printf("(%d, %d, %s)", np->node_id, np->data, np->name);
        print(np->right);
    }
}

int main() {
    int T = 1000; //test case 1000 nodes
    int data, r2, r;
    int node_id = 0;
    //printf("Input number of nodes:");
    //scanf("%d", &T);
    node *root = NULL;
    srand(time(NULL));
    while (T-- > 0) {

        //scanf("%d %d", &data, &node_id);
        r = (2 + T) * rand() % 100; //node id
        r2 = (2 + T) * (rand() % 100); // data
        printf("Input data. %d:\n", r2);
        printf("node id. %d:\n", r);
        root = insert_node(root, r2, r, "foobar");
    }
    print(root);
    // printf("\n");
    // printf("Find data at node:");
    // scanf("%d", &T);
    print(find_node_data(NULL, node_id));
    T = r;
    printf("node data %d %s", find_node_data(root, r)->data, find_node_data(root, r)->name);
    root = NULL;
    // find_node_data(root, T)->data;
    print(root);
    return 0;
}


What are the uses of Markov Chains in CS?

Markov Chain Monte-Carlo is a technique for efficiently sampling from a complicated probability distribution. No matter what your (discrete) probability distribution, you can set up a markov chain so that the steady-state distribution of a random walk is the distribution you wish to sample from. You can then approximate this distribution by simulating the random walk on the markov chain. If the markov-chain happens to have small mixing time, then the empirical distribution of your simulation will quickly converge to the steady state distribution, giving you an efficient algorithm for sampling from it.


Completeness of formal definition of 'hardness on the average'

Hard on average is sometimes defined as in your third (simple) definition: a function $h$ is hard on average if on a uniformly random input, its output cannot be predicted by a ppt with more than a negligible probability. The first definition also captures the situation in which the "correct" input distribution is different. For example, consider the function
$$ h(xy) = \begin{cases} H(x) & y = 0, \\ 0 & y \neq 0, \end{cases} $$
where $|x| = |y|$ and $H$ is some hard-on-average function (under the simple definition). The function $h$ is not hard on average under the simple definition, but it's hard on average under the more complicated definition. I'm not sure why we should be interested in such functions, but there's probably a reason. You'll have to continue reading and reflect when the more complicated definition is needed.

As for your second definition, it is far too strong. Consider for example what happens if $G$ always outputs the zero string. You are still capturing something - the halting function will still be hard - but there's no notion of "average". You have indeed anticipated this in your comment (though it only really applies in the non-uniform setting), but the resulting notion is still probably too strong.

The notion of hard on average came out of an attempt to proof the security of some notion. While it is indeed meant to capture some intuitive sense of hardness on average, the details were determined from some argument who used them, from some construction that obtained them; they're not arbitrary. These notions have been found to be useful, which is why they continue being used. Your suggested notion might be helpful as well, but the onus of proof is on you.


How to get the intersection of two regular languages?

One approach is to convert each regexp to a NFA, then use the product construction to compute the intersection of those two NFA, then convert back to a regexp if necessary.  Whether this is better or not, I can't say, as that depends what you mean by "better".  One advantage of this approach is that it uses only standard techniques that hopefully you've already learned in your automata theory course and doesn't require memorization of specialized algorithms.


If I understand your question correctly, then it simply asks for the TM with the encoding who is ordered first in the lexicographic ordering.

As you surely know, many TMs perform the same task.
Look at all the TMs that accept anything but empty set. Look at the encodings of all of those. Each encoding is simply a string. If you write all those string ordered using the lexicographical ordering (like in the dictionary), which string comes first? That should be your answer.


Since we're using base-$2$ logs, $\log2=1$, so $$n(\log n-\log 2) = n\big((\log n)-1\big)=n\log n -n\,.$$

All of the stages of the calculation are written as equalities, so nothing should be being discarded as too small to matter (and nothing is).


Why does the Count-Min Sketch require pairwise independent hash functions?

You are right: universal hashing suffices. Pairwise independence, while stronger, is the usual method to construct a universal hash family. Also pairwise independence is contrasted in the paper with the 4-wise independence required by previous methods, such as the AMS sketch.


How to define (logically) the complement language?

You aren't exactly correct in your example because of the redundant negation of the $\leq$ sign. In the most general sense, we always have:

$$\neg (x_1 \land x_2\land ...\land x_n)=(\neg x_1) \lor...\lor (\neg x_n)$$

Meaning: NOT (A AND B AND C...) equals (NOT A) OR (NOT B) OR (NOT C)...

In your case, we have two conditions with an AND between them:

M is a Non-Deterministic TM
M has an accepting run on $w$ of length $\leq |w|$

Finding the complement of the language requires negating these conditions, and therefore getting the language where either:

M isn't an NDTM, OR
M is an NDTM , BUT, it doesn't have an accepting run on $w$ of length $\leq |w|$

Notice the difference in the negation of the second condition - we changed it from having a run satisfying a certain property to not having a run satisfying the same original property.

From my experience, usually in these kinds of questions you have a language composed of TMs/Automata/etc' fulfiling a certain condition, and in such cases the negation would be everything which isn't a TM/automaton/etc', PLUS everything which is of the correct "type" but doesn't fulfill the original given condition.


The OR and AND operations are 2-in 1-out.

An Adder is either 3-in 2-out (shown in your diagram) or 2-in 2-out (not shown).  In part, because an Adder has 3 ins and 2 outs, it is composed of more underlying gates than AND and OR.

(But to be clear, it does not require new kinds of gates, the existing AND and XOR, OR, NOT gates, or the negating ones NAND, etc.. suffice.)

If we add two 16-bit numbers (not necessarily on a computer, but speaking mathematically) we get a 17-bit answer.  (That we often send that answer back to 16 bits is to risk errors in our systems; and the potential for these errors require mitigation techniques, but that is off topic to this question.)

Think of base ten.  In the general case, Two one-digit numbers add up to one two-digit number (though the upper digit may be zero).  If we're doing long addition, we carry from one column to the next (going left).  That carry going in means we're now adding 3 digits together, and the result is one digit along with a possible carry for the next column.  That's why adders sometimes take 3 inputs and other times 2 inputs.  The 2-input is for the least-significant-digit, whereas the 3-input is for the rest.

The last column has a carry out that is not used further, but just part of the result.  This is why we get one more digit than have the inputs.

In binary the maximum inputs would be a=1, b=1, and CarryIn=1.  That adds to 3 (decimal) and 3 is represented as 11 in binary.  The first of those one's (from 11 in binary) is the CarryOut and the second pf those one's is the Result in your diagram.


Does the DFS algorithm differentiate between an ancestor and a parent while computing back edges?

The algorithm you describe works on directed graphs. In such a graph, an edge $(u, v)$ does not imply an edge $(v, u)$. Your confusion arises because you are probably trying it for undirected graphs.

For undirected graphs, the algorithm has to be modified slightly. Again, the modification will depend on whether this graph is a simple undirected graph or a multigraph. I will use the same variable names used that you use in your algorithm:

Simple Graph: When checking the colour of the adjacent vertex $a$ of a vertex $v$, if the colour is grey and the vertex $a$ is not a parent of $v$, then it is a back-edge. Ignore if $a$ is the parent.
Multigraph: If the colour of $a$ is grey and it is a parent of $v$, you need to check if $a$ occurs more than once in the adjacency list of $v$. This indicates multiple edges between $a$ and $v$, and one of them can be considered as a tree edge while the rest will be back edges. If there is only one edge between the two, it is a tree edge and has already been considered, so do nothing. Loops (edge from $v$ to $v$, that is, $a$ = $v$) are always back edges.

You are basically finding a spanning tree of the graph, and so try to go by the definitions and see how the algorithm should be modified for various cases. And how a tree-edge or a back edge are informally defined for various types of graphs.


Find shortest path that goes through at least 5 red edges

What about reducing the problem first ?

UPDATED with more details :

Build 2 node subsets:

Vs contains s and the 10 reached nodes of the red edges (called a1, a2, ..., a10 hereafter). This is a 11 nodes set.
Vt contains t and the 10 sources nodes of the red edges (called b1, b2, ..., b10 hereafter). This is another 11 nodes set.

Build a distance matrix M from Vs to Vt (11x11)
Do 11 Dijksta explorations, one starting from any node of Vs to reach all nodes of Vt. So you get 11 shortest distances to report in the matrix M.
The diagonal terms are irrelevant (s->t or ak->bk).
For each row of M, add wi (the weight of the red edge) to all elements (0 for s row). This is the price of crossing the red edge.
Build an new graph G' with 11 nodes. node N0 for s&t and nodes Nk for each red edge (ak & bk). Then create all edges using matrix entry:
w(Ni -> Nj) = M[i][j].
Now your initial problem is equivalent to find a loop of 6 nodes containing N0 in G'.
Use any method to test all combinatoric for instance Apass.Jack one. This step in NP complete.


Why is $NP \subseteq P \implies NP^A \subseteq P^A$ false?

Your statement holds for all oracles $A$ iff $\mathsf{P} \neq \mathsf{NP}$. Indeed, if $\mathsf{P} \neq \mathsf{NP}$ then your statement vacuously holds. Conversely, if $\mathsf{P} = \mathsf{NP}$, then your statement fails for a random oracle $O$, since such an oracle satisfies $\mathsf{P}^O \neq \mathsf{NP}^O$ almost surely.

A similar argument shows that if $A$ is a $\mathsf{PSPACE}$-complete language then your statement holds, since in that case $\mathsf{P}^A = \mathsf{NP}^A$ is known to hold.

The proof that $\mathsf{P} \subseteq \mathsf{NP}$ relativizes, which means that it works even in the presence of an oracle. That is, the proof only uses arguments that keep holding even when the Turing machines are allowed access to an oracle. In all other cases, you cannot conclude from a statement of the form $\mathsf{A} \subseteq \mathsf{B}$ that $\mathsf{A}^O \subseteq \mathsf{B}^O$ for all oracles $O$. The two statements are about two different objects: the first one is about Turing machines without oracle access, and the second one is about Turing machines with oracle access to $O$.

This actually happens in practice, as mentioned in the comments: $\mathsf{IP}=\mathsf{PSPACE}$, but there are oracles $O$ relative to which $\mathsf{IP}^O \neq \mathsf{PSPACE}^O$.


Is there a regular grammar for the language $\{ w : |w|_0 = |w|_1 \}$?

A language can be described by a regular grammar if and only if it is regular. Your language is nor regular, hence it cannot be described as a regular grammar.


Maybe I misunderstood you, but we can definitely find a dynamic programming solution, a very similar one to the one for knapsack itself. Let $T[i, b]$ denote the maximum profit that can be made for the first $1 \leq i \leq n$ items, and $b$ is the remaining weight of the knapsack. Here is the recurrence.

$$T[i, b] = \begin{cases} 0 & \text{if } i =0 \vee b = 0 \\ T[i - 1, b] & \text{if } w(i)  > b \\ \max \{T[i - 1, b], T[i-1, b-V(i)] + V(i)\} & \text{if } w(i) \le b \end{cases}$$

For the base case, the 0th item doesn't exist so we have no profit. Similar for having run out of space.

Next, if $w(i) := W(i) + V(i) > b$, then we obviously cannot add item $i$ to our knapsack, and must continue on.

In the last case, we have two choices, either not include the item, or include it. For the latter, we then have $b - V(i)$ weight remaining, and $V(i)$ extra profit.

This dynamic programming algorithm has a running time of $O(nB)$, which is pseudopolynomial. Returning $T[n, B]$ is your maximum profit for all your items.


How does SARSA handle episode termination

You can think of the terminal state as a loop for every possible action where you receive zero reward. Once you enter the terminal state, not matter what action you choose, you will receive zero reward.


largest bitwise-or subset with a maximum number of on bits?

This problem is NP-hard. It is called "the minimum-k-union problem". Given a universe $U$ and a family of sets $\mathcal{F}$ over this universe. Are there $k$ distinct sets in $F$ such that the union of all these sets has size at most $d$.

Your presentation is the matrix formulation of this problem where each column corresponds to an element in the universe and each row corresponds to a set in the family. We are looking for $k$ rows such that the number of columns having at least one "1" is at most $d$.

The Problem is NP-hard and has approximation algorithms. Here is a link for one of them.


I am by no means an expert on this topic, but just from casually reading Wikipedia:

  it relies on the motion of spherical billiard balls in a friction-free environment made of buffers against which the balls bounce perfectly

... this sounds very realistic.

Nobody has actually figured out how to actually make such gates yet, they're merely of theoretical interest. That might explain why you've never heard of them since engineering usually deals with practice.

The premise of Reversible Computing is that when a bit disappears, some amount of heat is generated. By using reversible gates, no bits ever appear or disappear so supposedly computation could be much more efficient with reversible gates.

The theoretical limit Reversible Computing claims to get around is that erasing 1 bit of information generates at least $kT\ln 2$ energy in heat. For a computer running at a toasty $60\,{}^\circ\mathrm{C}$ with $10^9$ transistors each making bits disappear at a rate of $5\,\mathrm{GHz}$, that corresponds to $16\,\mathrm{mW}$ of heat generation. That only accounts for a tiny proportion ($1/10000$) of a computer's energy usage.

Our current-day computers are not limited by heat generation associated with bits disappearing. They are limited by the inherent inefficiency in moving electrons around on tiny copper traces.


Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?

The deterministic time hierarchy theorem precludes all problems in P being decided in linear time.  If you try to reduce a problem to HORN-SAT that requires more than linear time to decide, you'll find that the reduction itself requires more than linear time.


The Fréchet distance is a similarity measure for trajectories that often works well for curves that we consider visually similar. However, it is not scale or translation invariant, because it compares the distances between the points of the trajectories.

You can try the Direction-Based Fréchet Distance, introduced in this paper by de Berg and Cook. This is a variant of the Fréchet distance that is based on the directions of movement instead of the points directly. This means that it is both scale invariant and translation invariant, but not rotation invariant.

Another possible approach that may be easier to implement if you have a library that can compute Fréchet distance and DTW1 distance between a pair of trajectories, is to first translate the pair of trajectories such that the first points have the same position, and then scale the trajectories such that the distance between the first and last point of the trajectories is the same in both trajectories. If you compute either the Fréchet distance or DTW-distance after these transformations, the total measure will be scale and translation invariant.

1: DTW (Dynamic time warping) is similar to the Fréchet distance, the main difference is that the Fréchet distance is a bottleneck measure, while DTW is not. In other words, only the 'most dissimilar parts' of the trajectories determine the Fréchet distance, while DTW takes the entire trajectory into account.


Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

$\mathsf{3LIN}$ is the following problem:

  Given a set of linear equations of the form $x_i \oplus x_j \oplus x_k = b$, where $1 \leq i,j,k \leq n$ and $b$ is a bit, find an assignment for the bits $x_1,\ldots,x_n$ that satisfies the largest number of equations.

There is a simple 1/2-approximation algorithm, which simply chooses a random assignment. Such an assignment satisfies half of the equations in expectation, and so at least 1/2 of the optimum. Using the method of conditional expectations, it is routine to derandomize this algorithm.

Håstad, in his paper Some optimal inapproximability results, showed that it is NP-hard to approximate 3LIN to within $1/2+\epsilon$ for any $\epsilon > 0$. In other words, the trivial algorithm mentioned above gives the optimal approximation ratio.


Find the Simple Cycles in a Directed Graph

This question appears to be very Googleable. For example, you may be interested in the algorithm presented in this paper:

Finding all the elementary circuits of a directed graph. Donald B. Johnson. SIAM J. COMPUT. Vol. 4, No. 1, March 1975

  Abstract. An algorithm is presented which finds all the elementary circuits-of a directed graph in time bounded by O((n + e)(c + 1)) and space bounded by O(n + e), where there are n vertices, e edges and c elementary circuits in the graph. The algorithm resembles algorithms by Tiernan and Tarjan, but is faster because it considers each edge at most twice between any one circuit and the next in the output sequence.

The paper contains a complete algorithm.


If I understand the paper correctly (and I might not), the solution seems to be described in Section 2.2 of the paper.  It says "we have to compute $D(F_1[i],F_2[j_s,j_t])$..." and then it goes on to describe a strategy for doing so (namely, the Procedure 1, as described in Figure 2).


If there is any sense of an optimal set of instructions in an ISA

The paper you are asking for is:

  Patterson, David A; Ditzel; David R: The case for the Reduced Instruction Set Computer, Computer Architecture News, 8(6):25-33, Oct 1980. (non-paywalled copy).

Beware that it may be the paper you are asking for, but may not be the paper you want.  Almost everything it says is false, or has been debunked.  It is more of a humanities paper than a computer science paper.

There are ways of reducing the number of instruction bits that are fetched from DRAM (using more-or-less traditional compression techniques like Huffman encoding).  (And these kinds of concerns about minimizing instruction bits are evident in most "CISC" designs, as I described in a different question.)
 There are ways of minimizing the decode logic of a state machine (see for example the work of Villa, Kam, Brayton and Sangiovanni-Vincentelli, especially their 1997 book).  There are ways of minimizing the amount of power consumed by an instruction (for example, by increasing the number of different things that the instruction does, thereby better amortizing the power costs of fetching and decoding the instruction).

Finally, when there are ways of better representing instructions internally (for example to reduce decode power) it is trivial to do the translation from the "bad" instruction set to the "good" instruction set and cache the result. (Something x86 processors and many others have been doing since the late '80's (I can't find the academic references for this idea right now)).

What is rarely the case is that minimizing the number of instruction opcodes, or minimizing the number of addressing modes, is correlated with optimizing anything else about a computer design.


Determine when Strassen's algorithm for matrix multiplication is better than regular MM

If you look at the number of operations, it's obvious that you would do a matrix multiplication using the smallest number of operations. For 2x2 the direct method is best. You calculate for 3x3, 4x4, 5x5 etc. how many operations you need using the direct method, and how many you need using the Strassen method, performing (n/2) x (n/2) products using the fastest method.

If you look at execution time, that is dependent on the computer where you run it, so the point where Strassen is better also depends on the implementation. You would do the same thing as above, but instead of calculating the number of calculations, measure the execution time.


Sorting lower bounds for almost sorted array

Suppose that every element is at most $k$ elements away from its true position. In order to sort the array, you maintain a heap. At step $i$, you add $A_i$ to the heap, and pop the minimum element as $A_{i-k}$. You do no popping in the first $k$ steps, and no adding in the last $k$ steps; there are $n+k$ steps in total. Since the heap is always of size $k+1$, this runs in time $O(n\log k)$.

To see that this works, note that the first element in the sorted array must be one of the first $k+1$ elements, and in particular it must be the minimum of these elements. The second element could be any of the remaining elements or the $(k+2)$'th element, and in particular it must be the minimum of these elements. And so on.

For the lower bound, partition $n$ into blocks of length $k$, and consider the set of all permutation which fix each block. The number of such permutations is
$$
k!^{n/k} = [\Omega(k)^k]^{n/k} = \Omega(k)^n.
$$
Hence the number of comparisons is at least $\log [\Omega(k)^n] = \Omega(n\log k)$.


Is it decidable whether a TM reaches some position on the tape?

Any situation which asks whether a Turing Machine is confined to a finite section of the tape (say of length $n$) on a given input is decidable.

The argument works as follows. Consider the Turing Machine, the tape, and the position of the Turing Machine on the tape.  All together these have a finite number of configurations.  To be specific, there are only $t = n|\Gamma|^n|Q|$ possible configurations.  $\Gamma$ is the set of tape symbols and $Q$ is the set of states.  I'll continue to use the word "configuration" to describe the state of the Turing Machine combined with the state of the tape and its position on the tape for the remainder of this answer, but that is not standard vocabulary.

Run the machine, keeping track of all its past configurations. If it ever goes beyond point $n$, return "yes, $M$ passes position $n$".  Otherwise, the machine is somewhere between 0 and $n$.  If the machine ever repeats a configuration--its state, the symbols on the tape, and its position on the tape are identical to what they were before--return "no, $M$ never passes position $n$."

By the pidgeonhole principle, this has to happen in no more than $t+1$ steps.  So all of the above is decidable; after at most $t+1$ simulated steps you get an answer.

A quick note on why this works: when the machine, the tape, and its position on the tape repeat themselves, there must have been a sequence of configurations between these repetitions.  This sequence will happen again, leading to the same configuration one more time--the machine is in an infinite loop.  This is because we're keeping track of every aspect of the Turing Machine; nothing outside of the configuration can have an impact on what happened.  So when a configuration repeats, it will repeat again, with an identical series of configurations in between.

So confining the tape to a finite part of the string is decidable.  Therefore, by iterating over all possible input strings, the problem is in $\text{coRE}$ for all three questions.  You may have already realized this (between your ideas for 1 and 3 and Ran G's answer for 2 it seems solved completely anyway) but I figured it may be worth posting nonetheless.


Shortest path between all pairs with colored nodes

Your answer and reasoning are correct, but the last steps in your algorithm are wrong.

First, discard all edges with no green vertex.  Then:

To find the shortest path between a green and black node, you have to consider all of the black node's green-adjacent edges, and add the shortest path to/from the green.  There are at most 2018 of these, so it's still constant time.

To find the shortest path between two black nodes, you have to consider all combinations of their green-adjacent edges, and add the distance between the greens.  There are at most 20182 of these combinations, so it's still constant time.

So you can certainly do this in O(n2) time, and you can't do any better, because that's also the size of the output.

It may be simpler just to show how you can optimize Floyd-Warshall to take O(n2) time when all edges are known to be green-adjacent.


I am not entirely sure that what you're trying to prove is right.

unique [] = []
unique (x : xs) = if x `in` xs then unique xs else x : unique xs

reverse [] = []
reverse (x : xs) = reverse xs ++ [x]

If we take xs = [a, b, a, c] then:

unique [a, b, a, c]
= { unique.2 }
if a `in` [b, a, c] then unique [b, a, c] else a : unique [b, a, c]
= { ... }
[b, a, c]

reverse [b, a, c] = [c, a, b]

reverse [a, b, a, c] = [c, a, b, a]

unique [c, a, b, a]
= { unique.2 }
c : unique [a, b, a]
= { unique . 2 }
c : [b, a]
= [c, b, a]

Hence, unique (reverse [a, b, a, c]) = [c, b, a] and reverse (unique [a, b, a, c]) = [c, a, b].


Note: The original version of the post included the initial values $T(0) = 0$ and $T(1) = 1$.

If $T(n) = 2T(n-1)$ for all $n > C$ then, as you can prove by induction,
$$ T(n) = 2^{n-C} T(C). $$
In particular, in your case $T(n) = 2^{n-1}$. Note that given your initial values, the recurrence $T(n) = 2T(n-1)$ cannot hold for $n=1$; presumably it holds for all larger $n$.

You are asking for the complexity of the recurrence. Recurrences have no such thing as complexity. A recurrence might describe the running time of an algorithm, and then its solution is the time complexity of the algorithm. But a recurrence can describe any number of things, or even be completely abstract.


Lets begin with defining some terms.

  Semaphore is one form of software implementation for process synchronization. It's an int value that is used by processes for the purpose of signalling. Only three atomic operations: initialize, increment and decrement, can be performed.
  A binary semaphore is restricted type of semaphore which only takes three values, 0 and 1.

  wait(): Process executing wait() is blocked if the value is zero. If the value is one then, the process is allowed in critical section and value is decremented to 0.
  signal(): This checks if any process(es) are blocked (semaphore value equals 0). If yes, then a process is unblocked. If no, then value of semaphore is set to one.

Writer's Code
Writer process code is simple. wait() is used to enforce mutual exclusion. When wait(wrt) is executed wrt is decremented to 0 from 1. So, as long as there is on writer in the critical section, no other writer or reader process has access to the section. After performing it's task, signal() is implemented to allow other blocked process (if any) to execute over the critical section. signal(wrt) increments the value of wrt from 0 to 1.

Reader's Code
'mutex' variable is used for synchronization among different reader processes. No_of_Readers is a shared variable among reader processes. So, if more than one process is updating this variable then it's very likely that we will end up with wrong value. Thus, the first wait(mutex) and signal(mutex) is used to create a block, which only allows one reader to update (increment) the value of Number_of_Readers. When wait(mutex) is called the mutex is decremented to 0 (from 1). This makes sure that no other reader process will try to update the value of Number_of_Readers. After updating the value of Number_of_Readers siganl(mutex) is called. This increments the value of mutex releasing the section to be used by other readers.

  if(Number_of_Readers == 1)

implies that the current reader process is the first reader process to access the main critical section. Thus it is his duty to make sure that the coming writer processes are blocked. Thus wait(wrt) is enforced. Subsequent readers coming don't need to do that, as the first reader has already signalled writers to be blocked.
In the second block of the code, Read operation is being performed by the process(es). After a process has performed it's reading task it will exit the code section. The third block of the code is exit portion. Here also wait(mutex) is implemented as we only want one reader process to update the value of Number_of_Readers. A reader process implementing this will decrement the value of mutex to 0 (from 1), signalling other reader processes not to update the value of the variable. After value is decremented, process checks for

  if(Number_of_Readers == 0)

If this condition is satisfied, then it implies that the current reader process is the last one to exit. Thus, it is the responsibility of this process to signal(wrt). This will increment the value of 'wrt' to 1 allowing writer program to enter is required. Value not satisfying implies that there are still reader process(es) in the critical section and thus signal(wrt) is not executed. After Number_of_Readers is updated singal(mutex), increments the value of mutex (to 1), is called allowing other reader processes to access this value for updating.
Thus wait(wrt) and signal(wrt) are used to synchronize between 'Reader and Writer' processes. While wait(mutex) and singal(mutex) are used for synchronization among different 'Reader' processes. This makes sure that the value of Number_of_Readers value is not updated by many reader processes at the same time.


Given a set of sets, find the magnitude (number of elements) of the smallest set containing at least one element from each set

When we say that hitting set is NP-hard, we mean that the following decision problem is NP-hard: given a set system $S$ and an integer $k$, decide whether there is a hitting set for $S$ of size at most $k$.


On relation between FFT and polynomial multiplication

Suppose you have vectors $u$ and $v$. Imagine a table $M$ of the products of each of their entries.

$$M = |u\rangle\langle v| = \begin{bmatrix}
u_0 v_0 & u_1 v_0 & u_2 v_0 & \dots & u_{n-1} v_0 \\
u_0 v_1 & u_1 v_1 & u_2 v_1 & \dots & u_{n-1} v_1 \\
u_0 v_2 & u_1 v_2 & u_2 v_2 & \dots & u_{n-1} v_2 \\
\vdots &\vdots &\vdots & \ddots & \vdots \\
u_0 v_{n-1} & u_1 v_{n-1} & u_2 v_{n-1} & \dots & u_{n-1} v_{n-1} \\
\end{bmatrix}$$

The convolution $u \ast v$ of the two vectors is a vector of the values you get when summing along each anti-diagonal of this grid. For example:

$$(u \ast v)_2 = \sum \begin{bmatrix}
 &  &  &  &   & & u_{n-3} v_0 & 0 & 0\\
 &  &  &  &   & u_{n-4} v_1 \\
 &  &  &  & \ddots \\
 &  &  & u_2 v_{n-5} &  \\
 &  & u_1 v_{n-4} &  &  \\
u_0 v_{n-3} &  &  &  &  \\
0 &\\
0&
\text{ }
\end{bmatrix}$$

We can also think of the FFT of a vector as summing entries in a grid defined by multiplying two vectors' entries. The second vector is the sequence of roots of unity.

$$M = | u \rangle \langle e^{\tau i k/n} |\begin{bmatrix}
u_0 & u_1 & u_2 & \dots & u_{n-1} \\
u_0 e^{\tau/n} & u_1 e^{\tau/n} & u_2 e^{\tau/n} & \dots & u_{n-1} e^{\tau/n} \\
u_0 e^{2\tau/n} & u_1 e^{2\tau/n} & u_2 e^{2\tau/n} & \dots & u_{n-1} e^{2\tau/n} \\
\vdots &\vdots &\vdots & \ddots & \vdots \\
u_0 e^{-\tau/n} & u_1 e^{-\tau/n} & u_2 e^{-\tau/n} & \dots & u_{n-1} e^{-\tau/n}
\end{bmatrix}$$

The Fourier transform doesn't track along the diagonals, though. Its row-hop is different from its column-hop. For the $k$'th entry of the output we go through each column $c$ and sum up the cell from that column and the $k \cdot c$'th row (wrapping around).

$$FFT(v)_2 = \sum \begin{bmatrix}
u_0 \\
 &&&&u_4e^{\tau/7} \\
 & u_1 e^{2\tau/7} \\
 &&&&&u_5e^{3\tau/7} \\
 & & u_2 e^{4\tau/7} \\
 &&&&&&u_6e^{5\tau/7} \\
 &&& u_3 e^{6\tau/7} \\
\end{bmatrix}$$

So our question becomes: can we somehow re-arrange our vectors so that the each-stride sums $\sum u_i v_{k \cdot i}$ correspond to the each-diagonal sums $\sum u_i v_{k-i}$? Can we turn index-multiplication into index-adding?

We can, as long as we're operating in a context that allows for a logarithm. Suppose our vector size is $n$ and $g$ is a multiplicative generator for the integers modulo $n$. Then we can use the powers of $g$, i.e. the base-$g$ discrete logarithm, to define a permutation of the non-zero elements that does most of what we need. Our transformation goes roughly as follows:

Define permuted vectors $a$ and $b$ so that $a_k = u_{g^k}$ and $b_k = v_{g^{k}}$.
Compute the convolution $c = a \ast b$. So $c_k = \sum_{d=0}^{n-1} a_d b_{k-d} = \sum_{d=0}^{n-1} u_{g^d} v_{g^{-k} \cdot g^d}$.
Now un-permute $c$, and also un-permute the sum over $d$. $x_{g^{-k}} = c_{k}$ and $e=g^d$. So $x_k = c_{\log_g k} = \sum_{e=0}^{n-1} u_{e} v_{k \cdot e}$.

In other words: define a permutation $P$ based on when indices are reached when iteratively multiplying by $g$. Permute the input vector and the vector of $e^{\tau k /n}$ powers by $P$. Convolve. Unpermute by $P$. The result is the Fourier transform.

... Except that I've ignored one important issue. Our permutation doesn't work for $k=0$, because $g^k \mod n$ is never 0. Also, $g^0 = g^{n-1} = 1$. Fixing this hole requires special-casing the edges of the grid. But hopefully I've communicated the core idea of performing an FFT by delegating the heavy-lifting to a convolution and a permutation.

Note that, if you care about bit complexity instead of the number of arithmetic operations, computing the permutation may also be an obstacle. If multiplying by $g \pmod{n}$ costs $\log n$ time, and you don't have the permutation ahead of time, then overall the algorithm will still cost $O(n \log n)$.


When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"

I went and asked Don Knuth about this. He mentioned that he first used the new terminology in his 1972 paper Top-Down Syntax Analysis (link here) to provide a consistency between the terminology in $LL(k)$ and $LR(k)$ parsing.

Hope this helps!


Scott-continuous functions: an alternative definition

The definition of continuity used by your teacher is the nicer one.  It tells you pretty concretely what continuity means.

Suppose $b \in f(x)$.  That means that given all the information of $x$, possibly an infinite set of tokens (atoms), the function produces some element that has the atomic piece of information $b$.  (It could have other information too, but we are not concerned with that at the moment.)  Your teacher's definition says that it is not necessary to look at all the infinite information of $x$ in order to produce the output information $b$.  Some finite subset of $x$ is enough to produce it.

(Melvin Fitting's book "Computability theory, semantics and logic programming", Oxford, 1987, calls this property compactness and defines a continuous function as being monotone and compact.)

This is the essence of continuity.  To get some finite amount of information about the output of a function, you only need a finite amount of information about the input.  The output produced by the function for an infinite input is obtained by piecing together the information it produces for all finite approximations of the infinite input.  In other words, you don't get any magical jump in going from the finite approximations to their infinite union.  Whatever you get at infinity, you should already get at some finite stage.

The standard equation $f(\bigcup_{x \in D} x) = \bigcup_{x \in D} f(x)$ is pretty to look at, but it doesn't tell you all the intuition I have explained above.  However, mathematically, it is equivalent to your teacher's definition.

To show that $\bigcup_{x \in D} f(x) \subseteq f(\bigcup_{x \in D} x)$, it is enough to show that $f(x)$ is included in $f(\bigcup_{x \in D} x)$, for each $x \in D$.  But that follows directly from monotonicity of $f$ because $x \subseteq \bigcup_{x \in D} x$.  So, this is the "easy" direction.

The other direction, proved by your teacher, is the interesting one: $f(\bigcup_{x \in D} x) \subseteq \bigcup_{x \in D} f(x)$.  To see this, use the intuition I have mentioned above.   Any atomic piece of information $b$ in the left hand side comes from some finite approximation of the input: $x_0 \subseteq_{fin} \bigcup_{x \in D} x$.  That is, $b \in f(x_0)$.  Since $x_0$ is finite and it is included in the union of the directed set, there must be something in the directed set that is larger than $x_0$, perhaps $x_0$ itself.  Call that element $z$.  By monotonicity, $f(x_0) \subseteq f(z)$. So, $b \in f(z)$.  Since $z \in D$, $f(z) \subseteq \bigcup_{x \in D} f(x)$.  So, now $b$ is seen to be in the right hand side too.  QED.

As you have noted, showing that your teacher's continuity implies the pretty equation is the easy bit.  The harder bit is to show that the pretty equation, despite looking like it is not saying very much, really does say everything in your teacher's definition.


What language should the following DFA recognise?

Arrive at the answer by following all paths from the start state to the accepting state identifying the 'tail recursion':

  0*1+0+(1+0+1+0+)*
= 0*1*100*(1*100*1*100*)*
= 0*11*00*(11*00*11*00*)*

Intuitively, these are all strings over {0,1}* with an odd number of 10 substrings which is equivalent to the characterization you gave.


Upper-bounding the number of comparisons for Sorting to $\Theta(n)$ using a physically big number like Number of Particles in the Universe

The reasoning is not wrong as such, but applying such constraints tends to make asymptotic analysis meaningless; for example we could simply choose $C' = 10^{100}$, and as all inputs are smaller than this, every algorithm is $O(1)$.

Despite the ability to limit the analysis physically and end up with trivial observations, asymptotic analysis (without imposing those limits) does give practical information about algorithms. When we run them, we can certainly notice the difference between, say, Merge Sort and Bubble Sort - even when we have physically very small instances (even less than 1000).

So by speaking about algorithms in this more general (though not necessarily physically accurate) way, we get genuine information about how we can expect algorithms to perform based on how big the input is. More importantly it allows us to compare them.

From a different perspective, if we accept that all possible instances are smaller than some (really really big) constant, then all algorithms take constant time, what we then need to consider is what that constant is - if it amounts to longer than a few years, we haven't learnt anything useful to humans who only live a few years. If we lived longer than the life of the universe, then perhaps we wouldn't care about anything smaller than the size of the universe.


Basic classical linear error correcting code for bits exercice (from Nielsen & Chuang)

Suppose that $e_1, \ldots, e_k$ are (linearly independent) rows of the generator matrix of $C$. We can find vectors $e_{k+1}, \ldots, e_{n}$ s.t. $\{e_i\}_{i=1}^n$ is a basis in $\mathbb{F}_2^n$ (not necessarily orthogonal).

$\textbf{Claim 1.}$ $\exists i \in [k],$ s.t. $\langle x, e_i \rangle = 1$. Otherwise, for $\forall y \in C$ the inner product $\langle x, y \rangle = \sum_{i=1}^k \beta_i \langle x, e_i \rangle = 0,$ where $y = \sum_{i=1}^k\beta_ie_i$ is the basis decomposition of $y$ (all operations are modulo 2). Hence, the assumption that $x \notin C^{\perp}$ is incorrect.

Without loss of generality, $\langle x, e_1\rangle = \ldots = \langle x, e_s\rangle = 1$, $\langle x, e_{s+1}\rangle = \ldots = \langle x, e_k\rangle = 0$ for some $s \in [k]$.

Then $\langle x, y\rangle = \sum_{i=1}^s\beta_i$. The number of sequences $\{\beta_i\}_{i=1}^s$ of an even weight is the same as the number of odd-weight sequences, and it's equal to $2^{s-1}$, which concludes the proof.


How to prove that a constrained version of 3SAT in which no literal can occur more than once, is solvable in polynomial time?

Without loss of generality, we can assume that each variables appears exactly once positively and exactly once negatively (if a variable only appears once set its value to satisfy the clause and remove the clause). We can also assume that a variable does not appear in a clause more than once (if a variable appears both positively and negatively in a clause, then the clause is satisfied and can be removed). These will not alter the satisfiability.

Now use the resolution rule to eliminate the variables one by one (since each variable appears exactly once positively and once negatively this is a deterministic process).  If at any point we obtain the empty clause the set of clauses is unsatisfiable, otherwise it is satisfiable. This is because:

resolution is a complete propositional proof system (i.e. if a clause is logically implied by the set of clauses then it is derivable from the set of clauses using only the resolution rule),
a set of clauses is unsatisfiable iff it logically implies the empty clause.

This algorithm will take polynomial time since each variable is resolved exactly once.  In particular, each application of resolution will reduce the total number of clauses by one, so the number of clauses does not increase.  For example, applying resolution to $(x \lor B) \land (\overline{x} \lor C) \land \dots)$ yields $(B \lor C) \land \dots$, which has one fewer clause than before resolution.  In contrast, if you applied this to a 3SAT formula with no restriction on the number of appearances of each literal, applying resolution could cause the number of clauses to increase exponentially.


What different lines of reasoning and traditions lead to the conclusion that Software Engineering is or isn't part of Computer Science?

(I did some extensive searching and found material that answers my question. I liked Patrick87's answer, but I found this to be more complete.)

The answer to the question lies in a careful examination of the philosophy of Computer Science. In Computer Science, three intellectual traditions meet (or collide, if you wish) in a single discipline: the theoretical tradition; the empirical tradition; and the engineering tradition.

The theoretical tradition concerns itself with creating hypotheses or theorems, and proving them in a mathematical fashion. Its aim is the construction of coherent axiomatic systems of thought.

The empirical tradition concerns itself with forming hypotheses, models, and predictions, collecting data from experiments, and analysing the results. Its aim is to investigate and explain phenomena.

Finally, the engineering tradition concerns itself with stating requirements and specifications, and with designing, implementing, and testing systems based on these requirements and specifications. Its aim is to construct systems and solve concrete instances of problems.

Each of these traditions comes with a set of assumptions about the aims and means of scientific inquiry.

The traditions are not unique to Computer Science; they are general traditions that can be found to differing degrees in other disciplines. Perhaps the clearest examples are mathematics (theoretical tradition), physics (empirical tradition), and construction engineering (engineering tradition). Computer Science, though, operates in the intersection of all three traditions. However, depending on one's particular focus within Computer Science, and one's familiary with other parts of Computer Science, one might emphasize one of these traditions to the degree that the other two appear alien.

As noted in Patrick87's answer, the educational setting can emphasize a certain intellectual tradition which may lead someone to a certain kind of demarcation of Computer Science which either includes or does not include Software Engineering. Similarly, one may later adopt a view of science that includes or excludes one or more of the three traditions, or parts of them. For example, one may consider only the theoretical and empirical traditions to fulfil one's criteria for "science", and consider engineering non-scientific. One may also consider the three traditions to be on a value continuum, with one tradition being superior to the others (e.g. valuing the theoretical tradition most, the empirical tradition less, and the engineering tradition least).

So the lines of reasoning are rooted in the abovementioned traditions. Based on this, the answer to the question is that considering Software Engineering as part or not as part of Computer Science stems from one's understanding of science in general, and of one's understanding of the philosophy of Computer Science in particular.

The following articles go into considerable depth on this issue and summarise a lot of the viewpoints that have been put forward.

  Tedre, Matti (2011) Computing as a Science: A Survey of Competing Viewpoints. Minds & Machines 21(3):pp.361-387.

  Tedre, Matti (2009) Computing as Engineering. Journal of Universal Computer Science 15(8):pp.1642-1658

  Tedre, Matti (2007) Know Your Discipline: Teaching the Philosophy of Computer Science. Journal of Information Technology Education 6(1):pp.105-122.


Creating an O(n log n) time and O(n) space algorithm for counting pairs in an array

Just evaluate $\binom k2$ with $\frac{k(k-1)}2$, this takes $O(1)$.

Note that if the pairs are to be counted "without replacement", the formula is $\lfloor\frac k2\rfloor$.


Training a model based on polynomial regression and then putting that into a linear regression, vs just using the linear regression

There's no one answer about how you should/shouldn't do it.  There are two perspectives out there:

If it works, go for it. One perspective is: if it gives good results, that's all that matters.  So, if you get more accurate regression, great for you.  Try a bunch of approaches and pick whatever works best (taking care to avoid overfitting).

Model the underlying phenomenom. The other perspective is: choose a model that represents how the underlying physical process works.  So, from this perspective, we can't say what you should do, since you haven't told us how the underlying process works; we have no basis for evaluating whether that's a reasonable way to model reality.

There are many possible models one could imagine that map 4 continuous features $x_1,x_2,x_3,x_4$ to a continuous output $y$.  You could use linear regression:

$$y = a_1 x_1 + a_2 x_2 + a_3 x_3 + a_4 x_4 + b$$

Or you could use polynomial regression:

$$y = p(x_1,x_2,x_3,x_4)$$

where $p(\cdot)$ is some multivariate polynomial in 4 variables with degree at most $d$ (for some $d$ you choose).  Or you could use what you're doing:

$$y = a_1 p_1(x_1) + a_2 p_2(x_2) + a_3 p_3(x_3) + a_4 p_4(x_4) + b$$

where $p_1(\cdot),\dots,p_4(\cdot)$ are univariate polynomials with degree at most $d$.

Or you could fit some other nonlinear function (see nonlinear regression), or  fit a piecewise linear function, or use cubic splines, or use kernel smoothing or LOESS regression (see local regression).  There are so many options.  We can't tell you which to use from the information you've provided.

Advice. Usually, a good rule of thumb is that if you understand the underlying process well, use a model that matches the underlying reality.  If you don't know the underlying process, try multiple approaches and see which works best (using cross-validation to avoid overfitting).


Papers on algorithms:

A RECURSIVE ALGORITHM FOR THE FORCED ALIGNMENT OF VERY LONG AUDIO SEGMENTS
Pedro J. Moreno, Chris Joerg, Jean-Manuel Van Thong and Oren Glickman
Automatic Alignment and Error Correction
of Human Generated Transcripts for Long Speech Recordings
Timothy J. Hazen
SailAlign: Robust long speech-text alignment
Authors Katsamanis, Athanasios
Black, Matthew
Georgiou, Panayiotis
Goldstein, Louis
Narayanan, Shrikanth S.

Implementations:

Sphinx4 long audio aligner
Sail align
Gentle forced aligner


Definition of "properly partial" versus "total" value types

$
\newcommand{\llbracket}{[\![}
\newcommand{\rrbracket}{]\!]}
$First, a proper subset is a subset that is not equal to the whole set. In other words, $A$ is a proper subset of $B$ iff $A \subseteq B$ and $A \ne B$.

If you formulate a denotational semantics for a language, then each type $T$ has an associated set $\llbracket T \rrbracket$ which is called the denotation of $T$. Stepanov and McJones calls this set the abstract species corresponding to the type $T$ (in this particular semantics). For example, it is natural to associate the set of integers $\mathbb{Z}$ to the type $\mathtt{int}$, with value semantics $\llbracket \mathtt{0} \rrbracket = 0$, $\llbracket \mathtt{1} \rrbracket = 1$, $\llbracket \mathtt{-1} \rrbracket = -1$, etc. and the set of truth values $\{\mathsf{T},\mathsf{F}\}$ to the type $\mathtt{bool}$ with value semantics $\llbracket \mathtt{false} \rrbracket = \mathsf{F}$ and  $\llbracket \mathtt{true} \rrbracket = \mathsf{T}$.

A type is total under a denotational semantics iff the set of denotations of values of that type is equal to the denotation of the type. A type is properly partial iff is it not total, that is, iff the set of denotations of values is a proper subset of the denotation of the type. (The denotation of a value must be a member of the denotation of the type, otherwise the semantics is not valid, thus the denotations of values always form subset of the denotation of the type.)

For example, the set of denotations of values of the type $\mathtt{bool}$ under the semantics above is $\{\llbracket \mathtt{false} \rrbracket, \llbracket \mathtt{true} \rrbracket\} = \{\mathsf{F}, \mathsf{T}\} = \llbracket \mathtt{bool} \rrbracket$ so the type $\mathtt{bool}$ is total under this semantics. On the other hand, the set of denotations of values of type $\mathtt{int}$ consists only of values in the range $[-2^{N-1}, 2^{N-1}-1]$, assuming a typical implementation of the type $\mathtt{int}$ with $N$ bits, therefore $\mathtt{int}$ is properly partial under this semantics.

Note that the totality of a type depends on the chosen semantics. For example, under a semantics where the denotation of $\mathtt{int}$ is the integer range $[-2^{N-1}, 2^{N-1}-1]$, the type $\mathtt{int}$ is total.

”Abstract species“ and “properly partial” are not widespread terminology. As far as I know, they were coined by these authors.


Proving that $S_1+S_2 \leq f^{-\omega(1)}$

Let's consider the simpler case in which $f$ only has one input — the general case is the same, given that you use the correct definitions.

Here is what we want to prove:

  Suppose that $\lim_{n\to\infty} f(n) = \infty$.

  If for all $c \geq 0$ there exists $N$ such that for all $n \geq N$, $S_1(n) \leq f(n)^{-c}$ and $S_2(n) \leq f(n)^{-c}$, then for all $c \geq 0$ there exists $N$ such that for all $n \geq N$, $S_1(n) + S_2(n) \leq f(n)^{-c}$.

Let us be given $c \geq 0$. Let $N_1$ be such that $f(n) \geq 2$ for all $n \geq N_1$, and let $N_2$ be such that for all $n \geq N_2$, $S_1(n),S_2(n) \leq f(n)^{-(c+1)}$. Let $N = \max(N_1,N_2)$. Then for $n \geq N$,
$$
S_1(n) + S_2(n) \leq 2f(n)^{-(c+1)} = \frac{2}{f(n)} f(n)^{-c} \leq f(n)^{-c}.
$$


Why does this recurrence give O(n) time?

Your second analysis is correct, and $T(n) \in \Theta(n)$. You can also use the Master Theorem to verify this.

The reason that the first "naive" analysis fails is that you don't have $O(n)$ at each step, you have $O(\frac{n}{2^{i}})$ where $i$ is how far down the recursion you've gone.

Ignoring the constant multipliers for the moment, this gives
$$
\sum_{i=0}^{\log n} \frac{n}{2^{i}} = \frac{\sum_{i=0}^{\log n}n}{\sum_{i=0}^{\log n}2^{i}} = \frac{n\log n}{2^{log n + 1}} = \frac{n\log n}{2 \log n} = \frac{n}{2}
$$

Your second analysis basically does the same thing, just using variable substitution instead.


Is it possible to transfer a point from one camera to another, given n corresponding points?

Is it possible at any number of corresponding points n to derive a transformation relation from one camera view to another so that for an additional point p_01 known only at one image to be able to locate it on the second image p_02?

The answer is no - it is impossible. Each point on the image1 may in general correspond to an entire line on the image2 (see https://en.wikipedia.org/wiki/Epipolar_geometry). The homography matrix is a projection matrix of one plane on another and, therefore,  is useful when you have a plane object ( chessboard, book, painting etc.) pictured on both images.


What you show is that $a$ and $b$ belong to the same equivalence class. Indeed, in this case there are exactly three equivalence classes: $\{\lambda\}$, $\{a,b\}$, and $\{ w : |w| \geq 2 \}$ (that's assuming the alphabet is $\{a,b\}$). I'll leave it as an exercise to prove that.

The Myhill–Nerode equivalence classes are intimately related to the minimal DFA. Indeed, given the minimal DFA, the number of equivalence classes equals the number of states, and each equivalence class consists of all strings which end up at that state. That's the quickest way to find the equivalence classes in simple cases such as $a+b$.


Formally proving properties of fold function

"contents are equal" implies that their lengths are equal, so you don't need double induction.  Instead, try single induction.  A straightforward induction argument on the length of the list should suffice.

I wouldn't suggest trying to remove repeated elements.  That is not necessary, and it is an unnecessary complication that turns a simple induction into something really complicated and messy (as you have discovered).


Why does my code work: bijecting binary trees to Dyck paths

My answer is not a formal proof, but I hope it contains enough information to make you feel confident about your own solution. My strings start at $1$. Sorry, old habit.
Consider a binary tree $T$ with $n$ nodes. Assume $T$ has $n$ nodes, subtrees $T_\ell$ and $T_r$. If the root of $T$ has label $k$ this means that $T_\ell$ has $k-1$ nodes.
A tree with $n$ nodes has a Dyck codes of length $2n$. There are two ways of determining the Dyck code $dyck(T)$ of tree $T$. One is recursively:
$dyck(T) = U \; dyck(T_\ell) \; D \; dyck(T_r)$.
In this string we observe exactly one $D$, which is associated to the tree $T$, other $D$'s are written recursively. The position of this single $D$ is exactly at $2k$. We know this because the length of $dyck(T_\ell)$ equals $2(k-1)$.
Note that the symbols generated by $dyck(T_\ell)$ are shifted by one, because of the $U$ that is written before its code. This is the main observation: it is due to a left branch, and those left branches is what you are counting in your code.
The other way of determining $dyck(T)$ is graphical. Draw the tree and make a traversal around it. Write $D$ for a left child (even when that leads to an empty subtree) and $U$ for a right child. (We visit each node twice: this is both an pre-order and inorder-traversal.) If you try this you will see that each $D$ appears at the number of the node plus the number of times we went left as seen from the root.
The tree below has code (with subscripts that count position in the string and superscript which is the inorder label associated to the root of the corresponding subtree) $U_1^3 U_2^1 D_3^1 U_4^2 D_5^2 D_6^3 U_7^{10} U_8^6 U_9^4 D_{10}^4 U_{11}^5 D_{12}^5 D_{13}^6 U_{14}^8 U_{15}^7 D_{16}^7 D_{17}^8 U_{18}^9 D_{19}^9 D_{20}^{10} U_{21}^{11} D_{22}^{11}$.


Why merge into the larger tree in union by rank

Imagine merging the larger tree into the smaller one. By doing this, you are guarantying that the new tree will have depth one more than the larger tree's depth. But, if you were to merge the smaller tree into the larger one - the increase in depth would occur only in the branches of the small tree, and since it is small it wont impact the depth (unless the smaller tree is the same size as the larger tree).
So to summarize - by doing this you ensure to create the lowest possible depth you can.

Try to run on some examples both cases (merging largest to smallest and merging smallest to largest) and see the differences for yourself


Runtime of good suffix table creation in Boyer-Moore algorithm

The implementation provided in Wikipedia is $O(n^2)$. But these tables can actually be built in $O(n)$ time via Z-algorithm. Since you can find Z-algorithm on internet easily, I just provide a sketch here.

Let $s[i,j]$ denote the substring of $s$ from $i$-th position to $j$-th position. Like what we see in the $O(n^2)$ code, we want to find the largest value $z_i$ satisfying $s[i-z_i+1,i]=s[n-z_i+1,n]$ for each $i$ (the longest matching suffix).

Now compute $z_i$ from back to front. Let $l$ be the smallest number s.t. $s[l,r]=s[n-r+l,n]$ for some $r>i$. If $l\le i$, we have $s[l,i]=s[n-r+l,n-r+i]$, which means we can get some information from $z_{n-r+i}$. If $z_{n-r+i}\le i-l$, $z_i=z_{n-r+i}$. Otherwise $s[l,i]=s[n-i+l,n]$ and $z_i>i-l$. In this case, we should find the real $z_i$ by brute force, but at the same time we get a smaller $l$, which provide more information for future computation. Since $l$ is non-increasing, the algorithm works in $O(n)$.


You mentioned trying induction, to no avail. However, induction does work. Let's prove by induction that for all $n \geq 6$, $$n^4 \leq \frac{81}{4} 2^n.$$
This is true for $n = 6$ (both sides are equal to 1296). Suppose that it holds for some $n \geq 6$. Then
$$
(n+1)^4 = \left(\frac{n+1}{n}\right)^4 n^4 = \left(1 + \frac{1}{n}\right)^4 n^4 \leq \left(1 + \frac{1}{6}\right)^4 n^4.
$$
You can calculate that $(7/6)^4 < 2$ (equivalently, $2401 = 7^4 < 2 \cdot 6^4 = 2592$). Therefore, using the induction hypothesis,
$$
(n+1)^4 < 2n^4 \leq 2 \frac{81}{4} 2^n = \frac{81}{4} 2^{n+1}.
$$
Thus the inequality holds for $n+1$ as well, completing the proof by induction.