Can you have simple unit tests for complicated function?

The Turing test would make a very poor unit test because (a) it is difficult (impossible ?) to automate and (b) the evaluation of the test output to produce a pass or fail result is subjective. In fact, it might not even be possible to devise useful unit tests (in the usual sense) for strong AI - how would unit tests distinguish between true AI and a program that simply responded by rote ?

But simple unit tests for other complicated functions are certainly possible. As long as the function produces output that can be objectively evaluated then you can write unit test cases for it. For example, a Travelling Salesman Problem solver could be a very complicated program, but a unit test plan is very simple:

(a) test edge cases - 0 cities, 1 city, 2 cities

(b) test some simple cases with known solutions e.g. 3 cities in scalene triangle, 4 cities at corners of a rectangle, solved examples from TSPLIB


Proof of equivalence of regular expressions (0 + 1)(0 + 1)* and (0 + 1)*(0 + 1)

Let's go with your second approach.

First note that $R^n$, for any nonnegative integer $n$, is in $L(S)$.

If the string $w$ is in the first language, $L(RS)$, then we know that $w$ can be written as the concatenation of some string in $R$ and some string in $S$. This concatenation is denoted $(0 + 1)(0 + 1)^n$ (for some nonnegative integer $n$), which equals $RR^n$ which equals $R^{n+1}$, which equals $R^nR$, which we know is in the language $L(SR)$ (since $S=R^*$).

The reverse direction is more or less the same thing.

Edit:
Another interesting way of proving this is to prove $L(RS) = L(S)$ and $L(SR) = L(S)$.

To prove $L(RS) = L(S)$, take any string in $L(RS)$. It can be written as $RR^n$ for some nonnegative integer $n$. Now this equals $R^{n+1}$, which is of course in $L(S)$. So we have that $L(RS)\subseteq L(S)$.

Now take any string in $L(S)$. It can be written as $R^m$ for some nonnegative integer $m$. This is equivalent to $RR^{m-1}$, which is in $L(RS)$, so we know that $L(S)\subseteq L(RS)$.

Therefore we have $L(S)=L(RS)$.

We can prove $L(S)=L(SR)$ in a very similar way. Therefore $L(RS)=L(SR)$.

The actual difficulty and intuition behind the proof is fairly trivial, but putting the proof into words is harder. The proof amounts to proving some kind of exponent law for the Kleene star. We don't have an actual exponent law for the Kleene star, so the key part of the proof is simply isolating a single arbitrary string in the language, and then we have the finite integer exponents and we can just use the normal exponent laws.


How to calculate the complexity of a TM?

You only have to show that there exists a Turing machine that decides the language, and such that the number of steps taken by it is a polynomial in the size of the input, in this case a polynomial in $|w|$.

An example of such a machine is the following. Scan the tape left to right until you find both an $a$ and a $b$, and replace both of them with a new symbol, let's say $x$. If you fail to find both an $a$ and a $b$, there are two cases: if every nonblank symbol on the tape is $x$, answer $\textsf{YES}$, otherwise answer $\textsf{NO}$.

It should be easy to see that the number of steps is $O(|w|^2)$, and therefore the language is in $\textsf{P}$.

Just a pedantic note: we usually talk about the complexity of languages or problems, not machines. It would be more appropriate to say "number of steps taken" or "amount of space used" rather than "time complexity" or "space complexity" when talking about a specific Turing machine.


Relation between the size of sub-problems and number of sub-problems in a recurrence

A simple, specific example of an algorithm with a type $(iii)$ recurrence is binary search. At each point you decide whether to look in the left or the right half of the current section of the array, so your problem halves, and you only have one subproblem. The recurrence is then $T(n) = T(\frac{n}{2}) + O(1)$.

So you might get a type $(iii)$ any time you "discard" part of the input at each step.

A divide and conquer approach to multiplying large numbers can give you a type $(ii)$ recurrence (obviously there's faster algorithms now though). If you split the numbers in half, you can turn one multiplication of two large numbers in to four multiplications of half-sized numbers, plus some addition. Gauss reduced this to three multiplications of half size numbers (but with more addition and subtraction), so the recurrence for this algorithm is $T(n) = 3T(\frac{n}{2})+O(add)$ (the exact recurrence depends on how you deal with addition/subtraction).


Computability - The language of all strings of even length

$L$ is not recognizable. To avoid confusion, my assumption is that by $\text{HALT}^-$ you mean the language $\{\text{code}(M) \ w \mid M \text{ does not halt on } w\}$. We know that $\text{HALT}^-$ is not recognizable, thus showing $\text{HALT}^- \leq  L$ implies that $L$ is not recognizable.

For showing that $\text{HALT}^- \leq L$, we have to give a computable mapping $\text{code}(M)\ w \mapsto \text{code}(M')$ such that $M$ does not halt on w iff $M'$ halts on all input of even length. For a given $M$ and $w$, define $M'$ to be the TM that behaves as follows: It checks the length $l$ of its input. If $l$ is uneven, it does something arbitrary. If $l$ is even, $M'$ simulates $M$ for $l/2$ steps on $w$. If $M$ halts during this simulation, $M'$ goes into an infinite loop, otherwise $M'$ halts.

You can easily verify that this mapping has the desired properties. It is clearly computable and:

If $M$ does not halt on w, then $M'$ will for any input of even length $l$ simulate $M$ for $l/2$ steps on $w$ without the simulation halting, thus by definition $M'$ will halt afterwards.
If $M$ does halt on $w$ (after $k$ steps), then $M'$ does not halt on all inputs of even length, because for inputs of length $2k$ it will simulate $M$ on $w$ for $2k$ steps, with the simulation halting, thus by definiton of $M'$ it will go into an infinite loop.


Ok, i found what i was searching in a paper "Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity" https://www.faa.gov/aircraft/air_cert/design_approvals/air_software/media/TC-14-49.pdf

in Section 5.7 we can read that: "[...] Based on the results of this study and a literature review, there is no evidence  that  multiple  error  codes  on  the  same  dataword  increase  HD.    However,  adding  more  bits  of  error-detection code does tend to increase the coverage at that HD by creating more bits that  must  be  randomly  matched  to  form  a  valid  codeword. Quantifying  such  a  gain  requires  careful analysis of common-mode undetected error patterns for the multiple error coding schemes used, with a caution that pure mathematical analysis is prone to subtle errors and should always be validated via Monte Carlo simulation."

So the answer to my question is that it's impossible to select the best option unless they have been evaluated through mathematical analysis and subsequent experimental validation :(


Hint. Consider $m=1$ and the question answers itself.


Discrete solution space in NP-complete problems

It could appear to be the case that "discrete problems" are hard while "continuous problems" are easy. In fact, the exact question has already been asked on TCS.SE here. The answers list some continuous problems that area actually hard to solve.

As usual, computational problems come in all colors, shapes, and sizes. It is not a rule that continuous problems are always easy. In this sense, there is no "underlying principle". I think the following comment by Sasho Nikolov puts it well:

  I think the whole discrete vs continuous thing is a red herring. A problem has to have very special structure to be efficiently solvable. I think the real difference here is that in the case of easy continuous problems the special structure tends to be convexity, while in the case of easy discrete problems things look more complicated: sometimes the structure is submodularity or matroid intersection, but often it's not. This probably has more to do with the fact that we don't yet understand discrete math very well.


Maximize $\sum_{i\equiv r \pmod{m}} a_i$ over $m,r$

Denote the numbers by $a_0,\ldots,a_{n-1}$. We want to maximize, over all $m \mid n$ and $0 \leq r < m$, the sum of all $a_i$ such that $i \equiv r \pmod{m}$.
Let $p_1,\ldots,p_k$ be the prime divisors of $n$. Either $m = n$, or $m \mid (n/p_i)$. In the latter case, we can fold $a$ into an array $b^{(n/p_i)}$ of size $n/p_i$, and solve the problem there, recursively. If we use dynamic programming, then each $b^{(m)}$ will explored once, for each $m \mid n$.
What is the running time of this algorithm? The work done at $b^{(m)}$ takes time $O(m\rho(m))$, where $\rho(m) = O(\log m / \log\log m)$ is the number of distinct prime factors of $m$ (the upper bound on $\rho(m)$ follows from $n \geq \rho(m)!$). It follows that the total running time is proportional to
$$
\sum_{m \mid n} m\rho(m) \leq \frac{\log n}{\log\log n} \sum_{m \mid n} m = \frac{\log n}{\log\log n} \sigma(n) = O(n\log n),
$$
since the divisor sum function satisfies $\sigma(n) = O(n\log\log n)$.


Proof NP-Complete for Single machine Job Scheduling Problem specific version

Since this problem is very approachable, you could first try to think about a greedy solution to show this is in the class P, and thus probably not in NP-complete. Once you have done this you could think about a polytime reduction to a problem known to be in NP-complete. Consult Karp's original 21 problems to get a feel for the type of problems you can use to find this reduction. Once you have done this come back with more specific questions :)


Your problem (more accurately, the problem of deciding whether there is any solution) is 3SUM-complete. This can be shown in essentially the same way that the two main variants 3SUM and 3SUM' are shown to be equivalent (check the original paper of Gajentaan and Overmars, for example). Therefore it has an $O(n^2)$ algorithm, but it is conjectured that there is no $O(n^{2-\delta})$ algorithm for any $\delta > 0$.


Can we write a program that can say if any 2 given programs do the same w.r.t input - output pairs

No.  That's undecidable.  Suppose the first program is

return 42

and the second program is

if (f(x) halts)
    return 0
else
    return 42

where x is the input.

Do these two programs yield the same output, for all possible inputs?  That depends whether f always halts on all inputs.  And that is exactly the halting problem, which we know is not decidable.  It's easy to see that, as a consequence, this problem can't be decidable either (if it were, you could decide the halting problem).


Yes.  See the notion of an approximation-preserving reduction.


If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$

We will show the contrapositive: if some NP-complete problem is in coNP, then NP=coNP. Suppose that $L$ is some NP-complete problem which is in coNP. Let $A$ be any problem in NP. Then there is a polytime reduction $f$ from $A$ to $L$ (since $L$ is NP-complete), which means that $x \in A$ iff $f(x) \in L$. Since $L$ is in coNP, this shows that $A$ is in coNP. Hence NP is a subset of coNP.

Now let $B$ be any problem in coNP. Then there is a polytime reduction $f$ such that $x \in B$ iff $f(x) \in \overline{L}$ (since $L$ is NP-complete and $\overline{B}$ is in NP). Since $\overline{L}$ is in NP, this shows that $B$ is in NP, and so coNP is a subset of NP. We conclude that NP=coNP.


Difference between linear bound automata and a Turing machine

Notice that linear bounded automata are precisely all TM's who use $O(n)$ space.
Now, by the space-hierarchy theorem, for any $f$ where $n=o(f)$ (for an extreme example, $f(n)=2^n$) we would have $DSPACE(O(n))\subsetneq DSPACE(O(f))$.
Thus there are languages who require space complexity bigger than $O(n)$, and therefore are not solveable by linear bounded automata but can be solved by a ($O(f)$ space) turing machine.


Proving the equivalence of an LTL and a CTL formula

First, it is important to understand what the statement

$$\forall \big(a \textsf{U} (b \land \forall \square a)\big) \equiv \big(a \textsf{U} (b \land \square a)\big)$$

means. Hear LTL is interpreted over a transition system, and the semantics then is that all paths of the system satisfy the LTL formula. This is tightly connected to the CTL operator $\forall$.

Lets use the equivalence you have shown and prove
$$\forall \big(a \textsf{U} (b \land \forall \square a)\big) \equiv \square a \land \lozenge b$$

To prove the statement, first take a transition system $\mathcal{T}$ that satisfies $\forall \big(a \textsf{U} (b \land \forall \square a)\big)$ and show that it satisfies $\square a \land \lozenge b$.
Take arbitrary path $p$ of $\mathcal{T}$.
By the CTL semantics you know that $p$ satisfies the path formula $\big(a \textsf{U} (b \land \forall \square a)\big)$.
It will have a prefix labeled by $a$ and the state $s$ at the end of this prefix will satisfy the state formula $b \land \square a$. Thus all possible paths starting in $s$ are globally labeled by $a$. In particular, the suffix of the part $p$ we are considering will be labeled by $a$ globally. Also the state $s$ is labeled by $b$. Thus we can conclude that the path $p$ satisfies $\square a \land \lozenge b$.

The other direction is similar. Assume that all paths of $\mathcal{T}$ satisfy $\square a \land \lozenge b$ and show for arbitrary path $p$ of $\mathcal{T}$ that it satisfies $a \textsf{U}(b \land \forall \square a)$. It will be labeled by $b$ at some point, and as all paths of $\mathcal{T}$ are labeled by $a$ globally, in particular all suffixes of $p$ are. So the state on the path $p$ that is labeled by $b$ satisfies the state formula $b \land \forall \square a$.

There is an interesting result connected to your question:
let $\varphi$ be a CTL formula. If the property $\varphi$ is definable by an LTL formula (i.e. there exists an LTL formula $\psi$ such that $\varphi \equiv \psi$), then the LTL formula you get by simply deleting all path quantifiers in $\varphi$ is equivalent to $\psi$.
See the discussion in Equivalence preserving operator from CTL* to LTL.


Is it possible for a hash table's load factor to exceed 100%?

The load factor of a hash table is defined as:

$$\lambda = \frac{n}{k}$$

where $n$ is the number of items stored in the table and $k$ is the number of buckets. So the load factor is greater than 1 if there are more entries than buckets.

Storing more than one entry in a bucket is very common. The most familiar example is separate chaining (e.g. a linked list of entries in the bucket), used for in-memory hash tables.

For disk-based hash tables (as found in database servers or some file systems or file management systems), a "bucket" is typically a page (possibly a disk page or a virtual memory page) in size, so for typical use cases, you can easily fit more than one item into it. A scheme such as extendible hashing is typically used to manage buckets in a way that minimises disk traffic.


Looking for an efficient algorithm quickly find the nearest line (defined by perpendicular distance) to an arbitrary point

All your lines define a planar subdivision, where each polygonal region is bounded by a finite number of line segments or rays. So, at first you need to find a (probably infinite) region, containing a query point, and then you'll be able to select its boundary line with minimum distance from this point.

There are many ways to preprocess a planar subdivision in order to solve the Point location problem with logarithmic time complexity. Some hierarchical data structure is typically devised, which can be traversed for any query point, and it's proved, that the length of the traverse path is limited by $O(log(N))$, where $N$ is the number of regions. As @Pseudonym mentioned in comments, you can also use Binary space partitioning (BSP) to build a BSP tree - it's also a hierarchical data structure (binary tree), which will allow you to efficiently find a region, containing a query point. It looks like your problem suits well for this BSP approach.

Sorry to say, you can get regions with $O(n)$ boundary segments/rays, where $n$ is the number of lines. To overcome this difficulty you can further subdivide each region into Voronoi diagram, generalized for its boundary segments and rays. It's easy to see that the total number of such refined regions will be limited by $O(n^2)$, which still gives you logarithmic time complexity for the nearest line search. However in average case these regions with many boundary segments/rays will make up a small fraction of all regions - so in average you still will be able to quickly select the closest boundary segment/ray just by looping over the region boundary.

If you want to know more about general properties of the geometric structure you're working with - it makes sense to read this Wiki page.


Did Date and Darwen's "Third Manifesto" have a lasting impact?

Hmm, before some moderator closes this q as being a matter of opinion, not substance ...

I think you need to consider whether the first two manifestos (to which TTM was a response) had any impact? I'd say little or no: there were a few OODB ideas that made it into the SQL standard (but were little implemented). There are a few niche commercial products that claim to be OODBMSs. But mostly the industry has stuck with SQL tables; and applications or development tools provide an ORM layer (Object-Relational Mapping).

A comparable question: have 'Codd's 12 Rules' had a significant impact on the DBMS world? I'd say not much, even though most industry practitioners would at least be aware of them.

Hugh Darwen, by the way, is not principally a "DB theory researcher". He was part of the UK development team for an early IBM relational system Business System 12 -- which arguably was more relational than SQL has ever achieved [**]; and he was IBM's representative on the SQL standard committee for many years. He only lately moved into academe. His first draft of TTM was a visceral reaction against the fulminations of the SQL committee, written while he was at one of their plenaries.

Chris Date, IMO, is not much of a researcher either: he's more of an educator and writer of textbooks. I'm unconvinced he's added much to the research rigour of the TTM document.

Apart from that, your q seems to me to show many confusions.

If you read TTM (and the supporting explanations), I see no intent to "harmonise" with OOP. Note that an OODBMS is not aimed purely at OOP's: it's aiming to support notions of encapsulation of data. TTM's claim is that a Truly Relational DBMS already includes sufficient means to encapsulate data -- including under the Liskov/Wing Substitution Principle; and that SQL has bastardised the applicability of the Relational Model. Separation of concerns is principally to be achieved through schema design; we don't need perversion or subsumption of the Relational Model.

What has support for user-defined types got to do with it? Any modern language in any paradigm has those. The usual catchcry is 'types are orthogonal to the model'.

A large part of the TTM Prescriptions and Proscriptions are taken up not with opposing OODBMSs, but opposing SQL. Has TTM had a "significant impact" on SQL? I'd say no: SQL has continued to get worse and worse. Each revision of the standard has retained all the old awfulness (due to the shackle of backwards compatibility); has added new awfulness; and has multiplied up the effective awfulness in trying to support multiple 'features' that are in tension.

There are a few products that have attempted to implement TTM's ideas -- see "Projects" linked from the TTM website. I'd describe them as 'hobby products' developed and supported by individuals -- individuals who are rather cranky, strongly opinionated and difficult to deal with IMO. I would never recommend anybody use these products. (And for that reason, I'm not going to suggest you go ask your question at the TTM forum. You have been warned.)

[**] The more I discover about BS12, the more impressed I am by how much it got right even when the Relational Model was very far from mature. How come it was killed off but SQL continued? IBM internal politics, plus commercial pressure: Larry Ellison stole some significant brainpower from the IBM System/R research team (who arguably never understood what Codd was talking about); they re-implemented at Oracle what had been only a prototype at IBM; then commercial pressure resulted in a race to get 'something' to market, and never mind the quality. Mike Stonebraker/Ingres did originally try harder to follow the model, but eventually had to cave to commercial pressure.


Time complexity of generating the first n primes and their product

Since the input is of length $n^2$, it makes sense that the TM must read it at least once (to learn the value of $n$), and we have a trivial lower bound of $\Omega(n^2)$. It is my understanding that what you actually ask is "can we  complete the task with $O(n^2)$ steps as well"?

You suggest using the Sieve of Eratosthenes to mark primes. This is a clever idea. Indeed, a possible TM can run over the input. Each time it finds a 1, it writes its index on the output tape ($p_i$), and go through the input tape, zeroing any multiply of $p_i$. Then it goes back to index $p_i$ and repeat.

In order to know the index, we can assume the TM maintains a counter on the output tape (which is being "pushed" every time the TM outputs a new prime).

Now let's analyze the running time.

reading the input - $n^2$
For any prime we find (and we have $n$ of those:)

mark the input tape according to the Sieve of Eratosthenes: we need to go through approximately $O(n\log n)$ numbers due to the density of primes  - $O(n\log n)$
push the index and write the output - $O(\log n)$
counting exactly $p^i$ steps between two indexes we zero - $O(n\log^2n)$

Multiplying all primes - $O(n^2\log^{1+\epsilon}n)$

so the naïve solution above takes $O(n^2) + n\times [ O(n\log n) + O(n\log^2 n)]  + O(n^2\log^{1+\epsilon} n)= O(n^2\log^2n)$. In the above I assumed counting takes $O(n\log^2 n)$ since each step we need to subtract 1 from a $\log n$-long number, for every step in the sieve (which we bound to length $O(n\log n)$).

The time complexity of that algorithms is $O(n^2\log^2 n)$.

However, things can get better, as there are other ways of sieving.
Assuming a multitape TM,  the sieve of up to $k$ can be computed using $O(k/\log\log k)$ additions
(thus, with $O(k\log k/\log\log k)$ bit-operations) by [1].
By setting $k=O(n\log n)$, we can compute the sieve with $O(n\log n)$ steps.

However, computing the multiplication of $n$ numbers (of length $\log n$) will take $n \times O(MUL_{\log n})$ where $MUL_k$ is the time to multiply two numbers of length $k$. According wikipedia, $MUL_k \approx O(n\log n )$ [2]. This step alone is $\Omega(n^2\log n)$ and I don't see much hope to get complexity of $O(n^2)$.

 [1]: A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms" (free-access), Mathematics of Computation 73 (2004), pp. 1023–1030.
 [2]: ignoring the practically constant term of $2^{\log^* n}$.


Is there any demonstrably uncomputable concrete problem which does not rely on diagonalization?

there appear to be "no known examples" of undecidable problems that are not proven through "diagonalization" (precisely formalized), or more strongly, apparently diagonalization is the only way of showing uncomputability. in fact diagonalization, formalized, is an even more general property than undecidability, because exactly the same "mechanism" is behind other key mathematical proofs namely Godels theorem and the uncountability of the reals. this is revealed in the Lawvere fixed point formalism/ theorem.[1][2]

maybe inadvertently, your question is also related or nearly equivalent to the Church-Turing thesis in some subtle or direct ways. the thesis is, roughly, that anything computable is computable by a Turing machine. therefore, equivalently, anything that is not computable is not computable by a Turing machine and all uncomputable Turing languages are reducible to the halting problem and vice versa.

the idea that there exist computations not captured by TMs is considered at best speculative and at worst verging on a "generally not credible" idea by the majority of computer scientists; see eg summary/ "debunking" by Fortnow which also cites several published/ peer reviewed counterclaims.[3] a more recent survey on applicability of Turing machine model and "hypercomputation" etc can be found in [4]

[1] Halting problem, uncomputable sets: common mathematical proof? / cstheory.se

[2] Lawvere, F. William. Diagonal Arguments and Cartesian Closed Categories. Lecture Notes in Mathematics, 92 (1969), 134-145

[3] UBIQUITY SYMPOSIUM 'WHAT IS COMPUTATION?'
THE ENDURING LEGACY OF THE TURING MACHINE / Fortnow

[4] Turing's Titanic Machine? / Cooper, communications ACM


Is the open question NP=co-NP the same as P=NP?

No. It is another open problem and certainly related, but different. The complexity class co-$\mathsf{NP}$ is the set of languages whose complements are in $\mathsf{NP}$; that is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier. So for example, the question "Is this SAT formula unsatisfiable?" If the answer is "no", then there is some satisfying assignment of the variables that proves this; that's the certificate for the verifier.

It is possible that $\mathsf{P} \neq \mathsf{NP}$, yet $\mathsf{NP} = $co-$\mathsf{NP}$.

But on the other hand, if $\mathsf{P} = \mathsf{NP}$, then $\mathsf{NP} = $co-$\mathsf{NP}$ for sure. This is because if a language is in $\mathsf{P}$, then its complement is also in $\mathsf{P}$, so if $\mathsf{P} = \mathsf{NP}$, then that goes for every language in $\mathsf{NP}$ as well.


This is an area in which I'm not very familiar, but what you are looking for are so-called expander graphs.
A graph $G$ has edge expansion $$h(G) = \min_{0 \leq |S| \leq \frac n 2} \frac{|\partial S|}{|S|},$$
where $\partial S$ is the boundary of $S$, i.e., the edges with exactly one endpoint in $S$.
This isn't exactly what you ask for, but you can also consider only $S$ of size exactly $\frac n 2$.  There are $d$-regular expander graph classes.  Perhaps that will point you towards something.


Does $P/O(1)$ equal to $P$ if solver needs to consider smaller inputs?

Suppose that $F$ is a problem such that for every $n$, there is a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$.

Let $P_n$ be a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$. Since there are only finitely many programs of length at most $C$, there must be a single program $P$ that occurs infinitely often as $P_n$. This program solves $F$ in polynomial time for all instances.

If we change $O(1)$ to any bound $f(n) = \omega(1)$ computable in $\mathit{poly}(n)$ time, then we can easily construct undecidable problems which are computable in this model. We can assume that $f$ is monotone and has no jumps (otherwise take $g(n) = \min(\max(f(0),\ldots,f(n)),g(n-1)+1)$). For an undecidable $S \subseteq \mathbb{N}$, consider the following language:
$$
L = \{ x \in \{0,1\}^* : f(|x|) \in S \}.
$$
Since $f$ is monotone, if $|x| \leq n$ then $f(|x|) \leq f(n)$. Hence there is a program of length $f(n) + O(1)$ that solves $L$ correctly on inputs of length at most $n$. Conversely, since $f$ has no jumps, for each $m$ we can find a value $n$ such that $f(n) = m$, and this gives a computable reduction from $S$ to $L$, showing that $L$ is uncomputable.


Equivalence between MIN UNCUT and MIN-CSP_XOR

Suppose we are given a set of constraints of the form $b_i \oplus b_j = c$. We construct a graph with one vertex corresponding to each $b_i$. For each constraint of the form $b_i \oplus b_j = 1$, we add an edge $\{i,j\}$. For each constraint of the form $b_i \oplus b_j = 0$, we add a new vertex $x$, and two edges $\{i,x\},\{j,x\}$.

We can think of a cut as a partition of the vertices into two parts. For a constraint of the form $b_i \oplus b_j = 1$, the constraint is unsatisfied iff $i,j$ belong to the same part iff $\{i,j\}$ is uncut. For a constraint of the form $b_i \oplus b_j = 0$, there are two cases:

If the constraint is unsatisfied, then $i,j$ belong to different parts, and so exactly one of the edges $\{i,x\},\{j,x\}$ is uncut.
If the constraint is not unsatisfied, then $i,j$ belong to the same part, and so (depending on the location of $x$) either zero or two of the edges $\{i,x\},\{j,x\}$ are uncut. Since we are aiming to minimize the number of uncut edges, we can assume that zero are uncut.

In total, the number of unsatisfied constraints is the same as the number of uncut edges.


Determining a minimal-state regular language $A$ such that $A \cap B = C$ given regular languages $B$ and $C$

This question is essentially answered here. You are asking for the smallest DFA such that its language contains all words from $C \cap B$ and no words from $C \setminus B$. This called a minimal separating DFA (for $C \cap B$ and $C \setminus B$) in answer number one of the linked other question, where also a link to a paper with an algorithm is given. The other answer in that thread gives a reference to a paper showing that the problem is at least NP-hard. Since the size of the separating automaton is bounded (by the product of the DFA sizes for $B$ and $C$), the (decision version of the) problem is NP-complete.


Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time

Is there a way to make PST in O(N)

The simple is answer is No. It will take a minimum $O(NlogN)$ time to construct the tree.

  Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates.

No, the algorithm you mentioned will fail when you try to maintain the min-heap property based on $x-coordinates$.When you perform the min-heapify operation, the $y-coordinates$ will move from original position and the property of BST (based on $y-coordinates$) will fail. You can't maintain BST property for $y-coordinates$ anymore. So the tree will just reduce to min-heap  based on $x-coordinates$.

Here's a thought to construct priority search tree sorted on $Y$-coordinates:

For a given set of points $S$(sorted on $X$-coordinates), create a priority search tree as follows:

If $S$ is empty, return a NULL pointer and stop.
The point $P$ in $S$ with the greatest $Y$-coordinate becomes the root $R$.
If  $S-P$ is an empty set , then $R$ is a leaf so we return it and stop.
Let $X(P)$ be a value such that half of points in $S-P$ have
$X$-coordinate lower than $X(P)$, and half having higher value. Basically $X(P)$ is median(based on $X$) of your $S-P$
Recursively create a priority search tree on the lower half of $S-P$,
let its root be the left child of $R$.
Recursively create a priority search tree on the upper half of $S-P$,
let its root be the right child of $R$.

Total time complexity will be $O(nlogn)$ as the tree will be height balanced.

Notes:

Since you have sorted points based on $X$coordinates finding median will take $O(1)$.
To find the maximum $Y$, for simplification you could also maintain a max-heap based on $Y$. Finding maximum $Y$ from it and subsequently removing from it during creation of priority search tree will take $O(logn)$.


Is P = NP when solutions length is polynomially bounded by instance length?

You ask

  Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates?

In fact, the number of binary strings of length $n^c$ is $2^{n^c}$, which is exponential in $n$.


If we say L ⊂ {a, b, c}* then is L an infinite language?

$L$ is not necessarily an infinite language. $\{a,b,c\}^*$ is an infinite language, but you've written $L\subset\{a,b,c\}^*$, and infinite sets can (and do) have finite subsets. Consider $L=\{a\}$, then $L\subset\{a,b,c\}^*$ but $\lvert L\rvert=1<\infty$


For arbitrary RR(1) grammar $G$, is there an equivalent LL(1) grammar $G'$?

No. A language $\mathcal{L}$ is $RR(k)$ exactly if its reverse $\mathcal{L}^R$ is $LL(k)$. So if a $RR(k)$ grammar $G$ could be transformed into an $LL(k)$ grammar $G'$, that would mean that both $L(G^R)$ and $L(G') = L(G)$ are $LL(k)$.

But $LL(k)$ is not closed under reversal; there are $LL(k)$ languages whose reverse is no $LL(k)$. The classic demonstration that the set of $LL(1)$ languages is a proper subset of the set of $LR(1)$ languages also serves for this question.

The language $\{a^ib^j\mid 0 \le i\le j\}$ is $LL(1)$:

$$\begin{align}
S &\to A B\\
A &\to \epsilon \\
A &\to a A b\\
B &\to \epsilon \\
B &\to b B
\end{align}$$

However, its reverse $\{b^ja^i\mid 0 \le i \le j\}$ is not $LL(k)$ for any $k$, although the reverse is clearly $RR(1)$, since a n $RR(1)$ grammar for the reverse language can be constructed by simply reversing every production in the original grammar:

$$\begin{align}
S &\to B A\\
A &\to \epsilon \\
A &\to b A a\\
B &\to \epsilon \\
B &\to B b
\end{align}$$

(As it happens, the above grammar is LR(1). The language is an abstraction of the "dangling else" syntax.)


Proving the pigeonhole principle in Cutting Planes

The proof is by induction. Here is the inductive step.

Suppose that we know both of the following inequalities:
$$
x_1 + \cdots + x_m \leq 1 \\
x_2 + \cdots + x_{m+1} \leq 1
$$
Add them to get
$$
x_1 + 2x_2 + \cdots + 2x_m + x_{m+1} \leq 2
$$
Add the axiom $x_1 + x_{m+1} \leq 1$ to get
$$
2x_1 + \cdots + 2x_{m+1} \leq 3
$$
Divide by 2 and round down to get
$$
x_1 + \cdots + x_{m+1} \leq 1
$$
I'll let you fill in the remaining details.


Would a parser for this left-recursive grammar require infinite input?

Your grammar captures the empty language. To see this, you need to use the definition of a language described by a context-free grammar.
A context-free grammar is a tuple $(T,N,S,P)$, where $T$ is the set of terminals (a non-empty finite set), $N$ is the set of nonterminals (a non-empty finite set disjoint from $T$), $S \in N$ is the starting symbol, and $P$ is a collection of productions $A \to \alpha$, where $A \in N$ and $\beta \in (N \cup T)^*$.
In your case, $T = \{a\}$, $N = \{\mathrm{Expr}\}$, $S = \mathrm{Expr}$ (you are not stating this explicitly, but this is the only choice), and $P$ consists of the single rule $\mathrm{Expr} \to \mathrm{Expr} \, a$.
We say that $\beta$ produces $\gamma$ in one step, in symbols $\beta \Rightarrow \gamma$, if there exists a production $A \to \alpha \in P$ and two strings $\lambda,\mu \in (N \cup T)^*$ such that $\beta = \lambda A \mu$ and $\gamma = \lambda \alpha \mu$.
We say that $\beta$ produces $\gamma$, in symbols $\beta \Rightarrow^* \gamma$, if either $\gamma = \beta$, or $\beta \Rightarrow \delta \Rightarrow^* \gamma$ for some $\delta \in (N \cup T)^*$. This is the reflexive-transitive closure of $\Rightarrow$.
Finally, the language produced by the grammar is $\{ w \in T^* : S \Rightarrow^* w \}$.
In your case, a simple induction shows that $\mathrm{Expr} \Rightarrow^* \alpha$ iff $\alpha = \mathrm{Expr} \, a^n$ for some $n \in \mathbb{N}$. Since $\mathrm{Expr} \, a^n \notin T^*$, we conclude that the language produced by your grammar is the empty language.


Is it possible to accurately determine the number of instructions required to multiply or add two integers in a modern processor?

Yes and no.

“Instructions” isn't the right unit of measure: most processors include an ALU and require a single instruction to perform addition or multiplication on a number of a certain size (usually 8, 16, 32 or 64 bits, often with several possible sizes). A more relevant measure is the number of clock cycles required by this instruction. Counting instructions only comes into play when talking about bignums.

The number of clock cycles is determined by the depth of the circuit. A signal can traverse many gates in the same clock cycle, but more gates means a longer path which can be a limiting factor when trying to increase the clock frequency. It doesn't depend on the input values, only on the circuit that is being used (of course the values have to fit within the width of the circuit). For example a 32-bit adder will take the same number of cycles to calculate 1 + 1 and 1,000,042,569 + 1,491.

There are many possible designs for an adder or multiplier circuit. One of the design parameters is using more transistors or more complex connections to achieve faster operations. For example, addition the way we usually perform it requires adding the lowest-order bits, then adding their carry to the bits of order 1, and so on: the carry is propagated linearly, which means that the depth of the circuit is proportional to the word size. There are more sophisticated adders which parallelize the additions to reduce the depth.

The depth of the circuit tells you how many clock cycles the arithmetic operation requires inside the ALU. On a typical complex processor, going from there to the time it takes to perform instructions can be very complex, because you need to consider how the ALU fits in the processor. In order to actually add two values, the CPU must do many things:

Fetch the addition instruction from memory.
Decode the instruction to find that it is an addition, where its inputs are and where its output is.
Fetch the inputs — this can take different number of cycles depending on the width of the operation and whether the inputs are immediates, in registers, in memory, etc.
Make the arithmetic calculation.
Write the result into the output register or memory.

Most processors are very heavily pipelined: all of these steps are performed in parallel for different instructions. For example, at any given clock cycle, there are typically instructions in various stages of being fetched and decoded, different arithmetic operations in various stages of being carried out, etc. Advanced processors often have multiple ALUs so as to be able to make computations in parallel. For these reasons, the time it takes to perform $N$ successive additions is often not $N$ times the time it takes to perform one addition. Though in practice, the biggest variability comes from memory access — accessing an inner cache is dramatically faster than accessing RAM.


A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA.

What happens if only one of the two stacks is linear bounded and the other is unlimited? I optimistically wrote a quick comment that the LBA equivalence holds also in this case ... but ...

It's easy to see/prove that a 2-stack PDA with a linear bound only on one stack can simulate a LBA with one stack; and it is an open problem if a LBA with one stack is more powerful than a standard LBA.

For further details see T.Klimpel's answer to the question Is a LBA with stack more powerful than a LBA without?

This is a sketch of the proof that a PDA + 1 linear bounded stack + 1 unbounded stack (PDA+1B+1U) can simulate a LBA + 1 unbounded stack (LBA+1U)

Given a LBA+1U build a PDA+1B+1U in which the bounded stack is used to store the leftmost tape portion (reversed) and the unbounded stack stores the rightmost portion plus the unbounded content of the LBA stack.

A particular configuration of the LBA+1U:

    # x a y # stack: [b w   ]
        ^head

(where $\#$ are the endmarkers of the linear space, the head is on symbol $a$, the content of the tape is $xay$, the stack contains $bw$, $b$ is the top)

is represented into the PDA in this way:

    stack 1: [ > a x^R #  ]  (bounded stack)
    stack 2: [ y # b w       ]  (unbounded stack)

(where $>$ is a marker for the head position, $x^R$ is the reverso of $x$.

Suppose the LBA pops the b, change $a$ into $c$, moves left and pushes $d$ into the unbounded stack reaching this configuration:

    # x c y # stack: [ d w   ]
      ^head

The PDA can simulate that behavior in this way: it checks and pops the content of the unbounded stack using stack 1 as temporary storage:

    stack 1: [# y^R >a x^R # ]  (bounded stack)
    stack 2: [b w    ]  (unbounded stack)

Then it goes back to the head marker (storing "b" in its internal state)

    stack 1: [>a x^R # ]  (bounded stack)
    stack 2: [y # w    ]  (unbounded stack)

Then it moves left (and push c in the second stack simulating the a->c write operation):

    stack 1: [>x^R # ]  (bounded stack)
    stack 2: [c y # w    ]  (unbounded stack)

"goes" to the stack marker and push d:

    stack 1: [# y^R c >x^R # ]  (bounded stack)
    stack 2: [d w    ]  (unbounded stack)

then "goes back" to the head position:

    stack 1: [>x^R # ]  (bounded stack)
    stack 2: [c y # d w    ]  (unbounded stack)

Addendum

The proof that a PDA+2bounded stacks (PDA+2B) can simulate a LBA is similar.

For the other direction (a LBA can simulate a PDA+2B) the idea is to use two symbols to mark the top of both stacks $b_1, b_2$, and use the linear space to store the two bounded stacks "overlapped" (just use an expanded $\Sigma \times \Gamma \times \Gamma \times \{ b, b_1, b_2 \}$ alphabet).

By further expanding the alphabet you can store in the same (linear) space the original input, the head position of the PDA+2B, and an enumeration of the nodeterministic choices (there are at most $c|x|$ of them, one for each symbol of the initial input. Where $c$ depends only on the size of the transition table).

Then you can scan all the nondeterministic choices and simulate the behaviour of the PDA+2B using the top stack markers.

Note that if you allow epsilon transitions you must run two enumerations in parallel in order to check if the PDA+2B enters the same configuration due to  $\epsilon$ transitions (i.e. detect if it loops forever)


Term for binary search tree using hashes?

To answer the explicitly asked question: There probably is no specific name for this data structure since noone has bothered to use or study it.

Regarding the underlying question: Even using a "good" hash function, you can not expect as well a degree of balanced as you think:

Looking at the node with key $foo$, we see that all keys (in the subtree below $foo$) with a hash smaller than $h(foo)$ will be in the left subtree, while all those with a larger hash will be in the right subtree. So the balancedness of the tree will depend on how far $h(foo)$ is away from the center. This has an expected value of $\frac 12 N$, where $N$ is the number of hash values that belong in the subtree below $foo$. So we can expect an average weight balance of $1:3$ in each node. While this is still enough to give logarithmic expected height, it is already notably worse than the $1:1.6$ balance an AVL tree has in the worst case. Factoring in the additional risk of the hash function being not "good" for the data of a specific run, the idea quickly becomes unattractive.

Additionally, in many practical scenarios you have the option of using a library implementation of AVL trees, while you have to implement the "hash tree" yourself. So your "for free" argument will typically be the other way round.


Longest common sub-sequences with a condition

A two-dimensional $dp[i][j]$ is not fine enough to enable a recurrence relation. We need to track more information to be able to find the solutions to larger problems from the solutions of smaller problems.
Instead of $dp[i][j]$, try filling the following two tables simultaneously

$dp\_good[i][j]$, which means the length of longest common good subsequence of $S[1:i]$ and $T[1:j]$ that ends at $S[i]$ and $T[j]$. This number is $0$ is $S[i]\not=T[j]$.
$dp\_bad[i][j]$, which means the length of longest common bad subsequence of $S[1:i]$ and $T[1:j]$ that ends at $S[i]$ and $T[j]$. Here a bad subsequence just means it is not a good subsequence. Again, this number is $0$ is $S[i]\not=T[j]$.

The answer will be the maximum of all $dp\_good[i][j]$.
The above approach should work when you are looking for a sequence that "contains at least one pair of numbers which are adjacent and equal."
For the original problem, Task: ZAJ
Stutter, we should define a good string as a stutter, i.e., a string that consists of successive pairs of two equal elements. A bad string will be defined as "almost a stutter", that is, a strings which becomes a stutter if we delete its last element.


Moore's law is only indirectly involved here.  NVidia's SIMD registers are 1024 bits wide, have been that wide since at least 2006, and haven't grown.  Intel's slowly grew from 64-bit MMX in 1996, to 128-bit SSE in 1999, to 256-bit AVX in 2008, to the 512-bit AVX-512 in 2015.

My prediction is that neither Intel nor NVidia will grow their SIMD registers any wider from here on out.  The cost would be large, and the benefits decrease with each doubling.

The reason the cost would be large for Intel is that Intel has a whole bunch of inter-related design decisions that would need to be revisited.  Intel processors have used a cache-line width of 512 bits since the Pentium-4.  The cache ports to the cpu pipeline are 512-bits wide.  The BTB designs probably assume 64-byte cache lines.  I assume the coherence busses for multi-socket systems are 512-bits wide.  (I'm in the software division, not the hardware division.)  There is probably quite a bit of legacy code that has now been optimized for 512-bit cache lines.  For example: to avoid false-sharing overhead on cache lines, data structures may be aligned on 64-byte boundaries.  Customers would get annoyed if they spent thousands of dollars for a new server only to discover that their legacy code now runs slower.  I would guess that NVidia faces similar constraints.

The benefits decrease with each doubling because of something similar to Amdahl's law.  The benefit of SIMD is supposed to be that you double your ALU bandwidth, while keeping the area (and power) of the rest of your pipeline constant.  Suppose your processor is 16mm2, of which 1mm2 is your 32-bit ALU and register file, and you are getting 1 GFlOPS.  That's 1/16 GFlOPS/mm2.  Move to 64-bit SIMD, and your performance doubles, but so does the size of your ALUs and register file.  So now you are getting (at best) 2 GFloPS/17mm2, which is almost twice as good.  But when you get up to 512-bit SIMD you have 16 GFlOPS/31mm2.  Now doubling to 1024-bit SIMD gets you to 32 GFlOPS/47mm2, which is only 32% better.


Pumping Lemma on Language with subtracted length

You could argue with a reasonably straight face that L is not well-defined, since it supposedly contains the word $a^0ba^{-1}$, so L wouldn't be a language at all, therefore not a regular language and not an irregular language either.

If you change it slightly to $$ L = \{ w: w = a^k b a^{m-1} \mid k,m \in \mathbb{N} \} $$ then it is definitely regular; there's a very simple FSM with just two states for it.


Are colored graphs and red-black trees related?

No.  They don't have anything to do with each other.


Given a set of numbers (negative or positive), and a maximum weight w, find a subset that is maximal whose sum is less than w

This problem can be solved by a rather simple dynamic programming:

Given a set of numbers $\{a_1,\dots,a_n\}$, let $best(i, w)$ be the best solution using only a subset of the elements $a_i,\dots,a_n$ with a maximum value $w$, then $$best(i,w) = max(a_i + best(i+1,w-a_i), best(i+1,w))$$
With boundaries conditions $best(n + 1,w) = -\infty$ for any $w < 0$,
and $best(n + 1,w) = 0$ otherwise.

Note that this problem is NP-hard because it solves the partition problem, in particular the running complexity of the above program depends on the given numbers, and can be exponential in the size of the input in the worse case.


Assume you have different processes sharing memory. That means you can have different pointers pointing to the same physical memory. If you have two different pointers, pointing to the same physical memory, but pointing to different entries in the cache, then you will be in trouble.

In practice, memory mapping is done page by page. So both pointers will have the same offset into a page, but the page numbers can be different. One pointer can have an even page number, one an odd page number. If your cache is bigger than a page, for example two pages, then two pointers with an even and an odd page numbers would point to different cache entries, exactly what we want to avoid.

Of course an operating system could just not do any memory mapping that creates two pointers to the same memory location pointing an odd number of pages apart, and then the cache could be two pages in size.


Why is it that if we assume the Church-Turing thesis to be true, then human language must be recursive if the brain is finite?

This was a fun little rabbit-hole to jump into!  My understanding is not that dissimilar from what you wrote in your comment:

"Basically IF Church-Turning & Brain finite THEN recursion."

But you forgot to add "and if there is arbitrarily deep layering of semantic meaning".  So, really we would have:

If arbitrarily deep semantic layering AND the Church-Turing Thesis AND a finite brain, THEN recursion.

Now let's see if I can unpack that a little for you.

The authors are arguing that the components of sentences are placed into semantic layers that can group words rather differently than strict word-ordering would suggest, and furthermore, that these layers are effectively unlimited.  Consider this sentence:

Mary and John went to the new movie (which was excellent) with Sam.

Mary, John, and Sam are at one semantic layer, the new movie is at a second, and the fact that the movie was excellent is at yet a third layer.

Mary and John went to the new movie, (which, as you expected, was excellent) with Sam.

We've now added a fourth semantic layer.  And, I hope it is obvious that we could keep going!  The sentence would become convoluted and hard to follow, but we could keep adding semantic layers as many times as we wish.

There is a second idea here as well. It is interesting that Mary, John, and Sam are at the same semantic layer, even though they are far apart in the sentence.  This is evidence that there really is some kind of semantic layering, and not merely word proximity at play.  We read "Mary and John", delve down into a new layer, and eventually return back to this first layer in order to add "with Sam".  I mention this because it is already suggestive of recursion!

I understand your objection about having a finite amount of brain, and it is a very good counter-argument to the idea that we can follow arbitrarily deep semantic layers, but it is not an objection to the idea that human language is structured to be able to create them, which is really what the authors are arguing.

If you accept that language is structured in such a way as to permit this arbitrarily deep layering, then you are doing something very similar to a Turing Machine, which can represent any computable function using a finite number of states.

The Church-Turing thesis involves the notion that all of these representations are, somehow, recursive.  This makes sense if you consider that all three of the systems involved (Godel, Turing, and Church) can do this same trick of going arbitrarily deep using a finite number of rules at the start.  There must be some mechanism that allows arbitrary depth, which means that we must be able to repeat rules or states, which means recursion.

We are very close to having finished here.  If arbitrarily deep semantic layering AND the Church-Turing Thesis AND a finite brain, THEN recursion.

We only are left with the finite brain.  But of course, if the brain were infinite, then we would have no need for recursion.  We could represent every semantic layer in a new region of the brain, and keep doing this forever.


How to convert a recursive function to a non recursive one using stack while keeping memoization?

You can simply maintain a (hash)table, just like in the recursive case. Basically, you need to treat items on the stack like function arguments in recursion. Every time you pop items off the stack for processing, you check whether the particular entry in the table had been filled first. This gives you an equivalent memoized algorithm.
Additionally, you also need to check whether the table already contains the entry when you add an item to the stack; this avoids blowing up the stack with already memoized entries.
maintain a hashtable T of strings.

def num_ways_stack(s: str) -> int:
    stack = deque()
    stack.append(s)

    ways = 0
    while stack:
        cur_s = stack.pop()
        if cur_s is in T, then discard cur_s and continue

        if len(cur_s) > 0 and cur_s[0] == '0':
            continue

        if len(cur_s) <= 1:
            ways += 1
            continue

        if len(cur_s) >= 2 and int(cur_s[:2]) > 26:
            stack.append(cur_s[1:])
            continue

        if cur_s[1:] is not in T:
            stack.append(cur_s[1:])
        if cur_s[2:] is not in T:
        stack.append(cur_s[2:])

    return ways

To answer your second question, which is if there are other methods of converting recursion to iteration, there certainly is. For certain functions that are tail-recursive (and if not, you can try rewriting them into tail-recursive ones using continuous-passing style) you can convert them to equivalent iterative algorithms without keeping a stack but a bunch of variables.
For dynamic programming recurrences, the conventional practice for iterative computation is you identify an order which can be used to correctly fill up the memoization table (e.g. row-major, column-major, or diagonal) and use nested loops to iteratively compute the values in the memoization table. This potentially saves space, as it avoids the need to maintain a stack during the recursion.


Proving that every derivation-tree has at most one leftmost-derivation in a context free grammar

Here is a paraphrase of your proof. Suppose
$$
S \Rightarrow \alpha_1 \Rightarrow \cdots \Rightarrow \alpha_n \Rightarrow w \\
T \Rightarrow \beta_1 \Rightarrow \cdots \Rightarrow \beta_m \Rightarrow w
$$
are two leftmost derivations corresponding to the same derivation tree. Then the first step must be the same. This is the point where you're stuck.

What you want to do now is to say that $\alpha_1 \Rightarrow \cdots \Rightarrow w$ and $\beta_1 \Rightarrow \cdots \Rightarrow w$ are also leftmost derivations corresponding to the same derivation tree (obtained from the original one by taking into account the first step), and so by induction these derivations are the same.

There is a small problem – $\alpha_1$ is now not a single symbol! You therefore have to strengthen your induction hypothesis and prove something more general which involves derivation trees starting from sentential forms (words which can involve both terminals and non-terminals).

Alternatively, if you prefer using frontiers of derivation trees, you should strengthen your induction hypothesis in a different (but equivalent) way. Now you are still given the original derivation tree, but some of the productions are marked as already having been performed. Your induction hypothesis now states that all leftmost derivations from this state are the same.

It's also possible to avoid strengthening the induction hypothesis, at the cost of a more complicated argument during the inductive step. Suppose that the first step is $S \to x_1 A_1 x_2 A_2 \dots x_n A_n x_{n+1}$, where $A_1,\ldots,A_n$ are non-terminals and $x_1,\ldots,x_{n+1}$ are words. Any leftmost derivation must first completely derive $A_1$, then completely derive $A_2$, and so on, until $A_n$ is completely derived. Induction shows that there is only one way to achieve any of these $n$ steps.

More generally, I suppose you focus first on why the result is true; only then focus on how to write the argument formally.


I second Raphael's remark that when shuffling cards, you don't want the deck to be "unsorted", but rather random. However, when analyzing any specific shuffle, there can be measures of randomness that can be used to prove that a small number of shuffles isn't enough to make the deck random enough.

As a simple example, consider the "top card shuffle", in which you repeatedly take the top card and place it at an arbitrary location. If you don't repeat this enough times, then the top $k$ cards will retain their relative order (since you never put the top card somewhere among the top $k$ cards). So a reasonable measure of "sortedness" would be the maximal $k$ such that the top $k$ cards retain their relative order - for a shuffled deck, we expect this to be very small.

There is a similar measure for riffle shuffle, namely the number of ascents, two adjacent cards which retain their relative order. A random permutation has $n/2$ ascents, while an (under-)riffle-shuffled deck will have too many.

All this and more is described in David Aldous and Persi Diaconis, Shuffling cards and stopping times.


Is the certificate for primality testing polynomial in the length of the input?

Before it was proven that primality is in P, it was known that a complete factorisation if n-1 could be used to prove primality of n.  Now this also requires a proof that all factors in the claimed factorisation are actually themselves primes; this leads to a O(n^2) size certificate.

Google for “Pratt certificate”.

(When you use a certificate to solve a problem in NP, you cannot just “trust” the certificate. So if I tell you “here is a complete factorisation if n-1”, you can’t just believe that. You’d have to check that the product of the factors is actually n-1, which is easy. But you’d also have to check that each of the numbers that I claim are prime factors are actually prime, so you need a certificate for primality of these smaller numbers as well)..


Complexity classes that are closed under subtraction

$A \setminus B$ is defined as $\{x | x \in A ~ and ~ not ~ x \in B \}$. If you know the complexity of checking $x \in A$ and $x \in B$, what does that tell you about the complexitty of $x \in A \setminus B$? Can you see the algorithm for checking it?


Given a string, is it possible to determine which hashing algorithm has produced it, if any?

You will first need to define what you mean by a hashing algorithm. For example, my favorite hashing algorithm is simple: check whether the input is "string", and if so, output "b45cffe084dd3d20d928bee85e7b0f21", otherwise output "error".

In the simplest case, you have one algorithm $A$, and string $w$ and you are wondering, is there an input $x$ (and maybe a seed $s$) such that $A(x,s)=w$? You can try brute force, but if you have the source code, is there something more clever that you can do? If not, then your algorithm is a one-way function. Whether one-way functions exist is an open question. We know that if one-way functions exist, then $P\ne NP$, and therefore if $P=NP$, one-way functions do not exist, but that still leaves three possibilities.


Is this language $\{0^n1^m | (n+m) \text{is even}\}$ regular or not?

You seem to have misunderstood the pumping lemma.

Taking the definition from Introduction to the Theory of Computation by Michael Sipser

  If $A$ is a regular language, then there is a number $p$ (the
  pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

  for each $i ≥ 0, xy^i z \in A$,
  $|y| > 0$, and
  $|xy| \le p$.

A few points:

The lemma only says that a pumping length $p$ exists. You do not get to choose the value of $p$. So, you cannot say that let $p=3$.
For every string $s$ in the language with length at least $p$, it may be divided into three pieces, $s=xyz$. Notice that this again talks only of the existence of a way to split $s$ into $xyz$ given that $A$ is regular. So, you do not get to choose how the string splits into $x$, $y$, and $z$ in the general case. Finding a split that does not satisfy the conditions does not show that the language is not regular. You need to find such a string that cannot be split as stipulated by the definition to show that a language is not regular.
Finally, the pumping lemma does not say what happens if $A$ is not regular. So, even a non-regular language may satisfy it, and the pumping lemma cannot be used to show that a language is regular.


it seems that you're asking why bother with reservoir sampling when you're capable of tricking the test that you wrote?

Round robin doesn't return random numbers. It returns numbers deterministically. Well much more deterministic seeming than reservoir/other methods.

Your tests should be better. If you need the result to seem random and not deterministic, make a test which captures that instead of one which is based on empirical probability.

EDIT to add a test example:
another test for randomness (one that round robin would fail) is that you run the same process many times and don't get the same result every time. For uniform random sampling of a stream (the output of reservoir sampling) for a set/list/stream of a fixed size the probability to get one specific subset of size k should be 1/(n choose k) . You can run your method once then another 10000 (or any number of times) and see that you get the first result approximately only 1/(n choose k) times.


Is it more effective to vote for a woman?

Consider the following cases when you are the marginal voter (i.e. you decide the election):

Two men $m_1$ and $m_2$ have $>n$ votes, two other men $m_3$ and $m_4$ have $n$ votes, and one woman $w_1$ has $<n$ votes. If you support $m_3$ and $w_1$ equally and support $m_4$ less, then you should vote for $m_3$, such that both $m_3$ and $w_1$ will be in the top four.
Three men have $>n+1$ votes, one man $m_x$ has $n$ votes and two women $w_1$ and $w_2$ have $k<n$ votes each. If you support $m_3$ and $w_1$ equally, you should vote for $w_1$ regardless of $x$ because $m_x$ will definitely lose, and $w_1$ will only win with certainty with your vote.
Men $m_3$ and $m_4$ have $n$ votes, two women $w_1$ and $w_2$ have $k<n$ votes. What happens in the case of a tie is unclear, and (given one vote) it will end in a tie either way.

Thus, it seems as though there is no advantage to voting for either a woman or a man over the other.


DFA to accept a String containing even number of both A and B, but rejects empty String

I'm going to assume that your DFA has 4 states with the start state also being the singular accepting state.
Add a new (non-accepting) state where the outgoing transitions are a copy from your existing accepting start state. Make that new state the start state.
If my assumption about your existing DFA is correct then this way you should not be able to get into an accepting state with the empty string.


So the paper's

"Numerical infinities and infinitesimals: Methodology, applications, and repercussions on two Hilbert problems", Yaroslav D. Sergeyev (2017),

and it's basically a discussion on the author's "grossone" approach that they've been pushing for quite a while now (at least since 2004).

The tl;dr on it is that they're proposing a slightly abstracted data type, kinda like how complex number data types generalize real number data types, except this one's focused on infinities instead of imaginaries.

The author seems to want CPU's to include support for grossone's in their arithmetic logic units (ALU's), e.g. as specified in their patent.  The author's website and publications seem to focus on applied use in mathematical optimization; they seem to justify their work in terms of theoretical work as an afterthought.

Some of the harshest criticism seems to come from folks who're knocking it as-though the author were trying to report their work as some new theory, arguing that it's weaker and less sophisticated than prior work, e.g. hyperreal numbers.  The weird part about this is that, as far as I can tell, that's what the author wanted to do; they're trying to make an abstract data type to replace floating-point data types for common calculation units, not solve the mysteries of the universe.

In general, I'd expect folks who get the author's intent to receive it with a bit of a yawn.  The arguments for modifying mainstream ALU's don't seem too compelling, and at-current there's likely not much demand for custom CPU's that implement it.

The author appears to have implemented grossone's at a software level, kinda like how computers do complex-number operations.  Since they're using a non-primitive numeric data type, their calculations'll be slower for it; but if they distribute the library and can demonstrate how it's worth the performance hit in some useful applications, some folks might start using it in those cases.

In short, it looks like the controversial proposal's for an abstract data type that includes infinities for use in common calculations.  It looks like applied work rather than theoretical, a misunderstanding which seems to have ruffled some feathers; however, at the end of the day if the authors can show that it's useful in real-life coding scenarios and make it available, then folks might use it.


Preventing oversell, allocation of limited resources with overlapping properties

So the data structure holding pointers for every possible combination of classifiers is huge. Sure, but why build it at all? Don't overengineer this!

Just store the profiles in a database and do one (linear time) filtering sweep for each query, i.e. select/count on demand. For a few millions of records, that should require no further preprocessing.

If the number of requests is large and/or you need really small response times, you can think about caching, or creating equivalence classes along some popular classifiers, or along classifiers with few large classes. Then, the linear sweep has to be done only on small lists.

For example, you can divide your database along gender and age (assuming these are included in most customer queries)

$\qquad \{m, w, o\} \times \{0..5, 10..15, \dots, 95..100\}$

where the values obviously depend on your data. Then, each query will require only few of these small lists, and can even parallelise if you store the individual chunks separately.


For binary variables you could just write $x_1 = 1 - x_2$, but I see that in your case $x_1,x_2 \in \{1,2,3\}$. You can still use the same trick once you force a boolean variable $y_i$ to be 1 if and only if $x_i \ge 1$:
$$
\begin{align*}
3 y_1 &\ge x_1 \\
y_1 &\le x_1 \\[6pt]
3 y_2 &\ge x_2 \\
y_2 &\le x_2 \\[6pt]
y_1 &= 1-y_2 \\[6pt]
y_1, y_2 &\in \{0,1\}
\end{align*}
$$


Why does CLRS refer to the disk parts as pages rather than blocks?

I think you're right to be confused by this.
If their "pages" are sectors (= disk blocks), then they're right to say that pages "appear consecutively within tracks, and each disk read or write is of one or more entire pages", but their size range for pages makes no sense. The overwhelmingly most common sector size in 2009, when this textbook was published, was $2^9$ bytes. Also, I've never heard the term "page" used for a disk sector before.
If their pages are VM pages, then the size range makes more sense. But then they're wrong to suggest that the page size is a property of the disk, and it's not true that a swapped-out VM page will generally appear consecutively in a track. Also, disk reads and writes are only in units of VM pages if they come from the paging subsystem, and you shouldn't expect B-tree nodes to be paged in general (though they can be).
If their pages are clusters (filesystem allocation units), then the size range may be reasonable, but the rest is wrong. Clusters aren't generally read or written as a whole, they are just allocated as a whole. Also, I can't think of any reason to match the B-tree node size to the cluster size unless it's a filesystem B-tree (probably a directory index) and equating them simplifies the design or implementation of the file system.


Why use minhash instead of directly computing Jaccard coefficient?

If you only have two sets $A,B$, then you are right: there is no point computing the minhash.

But now suppose you have sets $A_1,A_2,\dots,A_n$, and you want to know whether there exists any pair $A_i,A_j$ with high Jaccard similarity.  It's more efficient to compute the minhash of each $A_i$ once, and then use that to help you look for a pair that hash high Jaccard similarity.  As a trivial observation, once you've already computed the min-hashes of them all, then estimating the Jaccard similarity of $A_i,A_j$ can be done in $O(k)$ time using the existing minhashes, which can be significantly faster than the naive  $O(|A|+|B|)$-time method.

(In fact, once you have the minhashes of all of the sets, there are even cleverer ways to look for pairs $A_i,A_j$ with large similarity.)

This is even mentioned on the Wikipedia page for Minhash: see the section labelled Time analysis.  However, you do have to read it pretty carefully to get the point.


Relation between Russellian type theory and type systems

``Type theory" in the sense of programming languages and in the sense of Russell are closely related.  In fact, the modern field of dependent type theory aims to provide a constructive foundations for mathematics.  Unlike set theory, most research in type theory based math is done in proof assistants like Coq, NuPRL, or Agda.  As such, proofs done in these systems are not only "formalizable" but actually fully formal and machine checked.  Using tactics and other proof automation techniques we try to make proving with these systems "high level" and thus resemble informal mathematics, but because everything is checked we have much better guarantees on correctness.

See here

Types in ordinary programming languages tend to be more limited, but the meta theory is the same.

Something similar to Russell's paradox is a major issue in dependent type theory.  In particular, having

Type : Type

usually leads to contradiction.  Coq and similar work by nesting universes

Type_0 : Type_1

but in Coq by default these numbers are implicit as they normally don't matter for the programmer.

In some systems (Agda, Idris), the type in type rule is enabled via a compile flag.  It makes the logics inconsistent, but often makes exploratory programming/proving easier.

Even in more mainstream languages, Russell's paradox occasionally shows up.  For example, in Haskell, an encoding of Russell's paradox combining impredicativity and open type case is possible, allowing one to build divergent terms with out recursion even at the type level.  Haskell is ``inconsistent" (when interpret as a logic in the usual way) since it supports both type and value level recursion, not to mention exceptions.  None the less, this result is rather interesting.


Complexity of recursive Fibonacci algorithm

Most of the times, you can represent the recursive algorithms using recursive equations. In this case the recursive equation for this algorithm is $T(n) = T(n-1) + T(n-2) + \Theta(1)$. Then you can find the closed form of the equation using the substitution method or the expansion method (or any other method used to solve recurrences). In this case you get $T(n) = \Theta(\phi^n)$, where $\phi$ is the golden ratio ($\phi = \frac{(1 + \sqrt{5})}{2}$).

If you want to find out more about how to solve recurrences I strongly recommend you to read chapter 4 of Introduction to Algorithms.


Suitability of high-level languages for embedded systems

What is a high level language? What is an embedded system? Once upon a time C was a high level language and a Raspberry Pi would have changed the outcome of major wars, now almost every microcontroller can be programmed with C and we use Pis that run a full-blown desktop OS to turn servo motors. Let's say a high level language is a language that has strong abstraction mechanisms and an embedded system is a system with very limited memory and a processor with few features.

That alone is not enough to say whether this language is suitable for embedded programming or not. The important part is how the programs in the language can be compiled. Many languages (have to) add something called a runtime to the programs. For Haskell for example the runtime added by GHC is about 50k LOC and includes a garbage collector, a scheduler and a bunch of other stuff. That is quite a lot of code for a small chip to handle and might require processor features that aren't present.

Rust is another language that I'd call high-level, but it is possible (in theory at least) to run Rust on many embedded systems. This is because Rust has the possibility to use a much smaller runtime that can be handled by simpler processors and doesn't add as much overhead.

So in summary, the important part is not the features of the language, but how much of those features need support at runtime as opposed to a clever compiler. Garbage collection is typically too difficult for embedded systems, but a surprising amount of abstraction power can be provided without any extra costs at runtime.

Note that in practice you're still limited to C or Assembler in many cases, because you need a compiler that supports your target architecture. Unfortunately it is often the case that the architecture is proprietary and you're limited to using the compiler provided by the manufacturer. That is typically a compiler that supports some flavor of C.


This is an expansion of this presentation.

Because the state graph consists of two disconnected components of equal size.
Without loss of generality we can  assume that the target state is $1\;2\;3\;...\;15\;\Box$.

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  *

Given a state $S$ a permutation inversion is a tile $T_i$ that is placed after $T_j$ but $i < j$; this happens when (a) $T_i$ is in the same row of $T_j$, but on its right, or (b) $T_i$ is in a lower row:

 .  .  .  .      .  .  .  .
 3  .  .  1      .  7  .  .
 .  .  .  .      .  5  .  .
 .  .  .  .      .  .  .  .
    (a)             (b)

We define $N_j$ as the number of tiles $T_i$, $i < j$ that appears after $T_j$.
For example, in the state:

 1  2  3  4
 5 10  7  8
 9  6 11 12
13 14 15  *

we have that after $T_{7}$ there is one tile ($T_6$) that should be before it, so $N_7=1$; after $T_{10}$ there are four tiles ($T_7, T_8, T_9, T_6$) that should be before it, so $N_{10}=4$.

Let $N$ be the sum of all $N_i$ and the row number of the empty tile $T_{\Box}$

$$N = \sum_{i=1}^{15} N_i + row(T_{\Box})$$

In the example above we have: $N = N_7 + N_8 + N_9 + N_{10} + row(T_{\Box}) = 1 + 1 +1 + 4 + 4=11$

We can notice that when the empty tile is moved horizontally $N$ doesn't change; if we move the empty tile vertically $N$ changes by an even quantity.

For example:

 .  .  .  .      .  .  .  .
 .  .  2  3      .  .  *  3
 4  5  *  .      4  5  2  .
 .  .  .  .      .  .  .  .

$N' = N + 3 \mbox{ (2 is placed after 3,4,5)} - 1 \mbox{ (empty tile is moved up)} = N + 2$

 .  .  .  .      .  .  .  .
 .  .  *  4      .  .  3  4
 2  5  3  .      2  5  *  .
 .  .  .  .      .  .  .  .

$N' = N + 1 \mbox{ (2 is placed after 3)} - 2 \mbox{ (4,5 are placed after 3)} + 1 \mbox{ (empty tile is moved down)} = N$

So $N \bmod 2$ is invariant under any legal move of the empty tile.

We can conclude that the state space is split in two disconnected halves, one having $N \bmod = 0$ and the other having $N \mod 2 = 1$.

For example the following two states are not connected:

 1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8
 9 10 11 12     9 10 11 12
13 14 15  *    13 15 14  *
    N = 4         N = 5


Minimum number of clues to fully specify any sudoku?

Since permuting two rows within a single block of a valid, completed sudoku produces another valid, completed sudoku, you can take any completed board (81 clues) and remove the first two rows (81-18=63 clues), which will give you an incomplete sudoku with two solutions. Note that even if you remove all but one of the 18 numbers there, the solution is immediately uniquely determined (since there can be no number repeated in the same column).

Another operation that produces another completed sudoku is applying a permutation of $\{1,\ldots,9\}$. If you take a permutation that is a transposition (permutes two elements, keeping the other fixed), again, as before, you can remove all appearances of those two elements and you have an incomplete sudoku with two possible solutions and 63 clues. Again, if you don't remove all 18 numbers, the solution will be unique.

Of the six elemental operations that produce a completed sudoku (see here), these two are the ones that can involve the least number of elements, so I'd say $C=63$ is an upper bound for what you're looking for. I know this does not exactly answers your question, but the general idea of removing sets of positions which produce two different solutions might be a good starting point.


How to cluster similar objects into fixed size groups?

Just model your problem with graph and use any of the widely known search algorithm to help traverse your graph. After doing that, if you have any problem, let us know.


Simple question on the phrasing on a PBS Infinite Series video

The state of an $n$-qubit system is a superposition of the $2^n$ pure states
$$
\sum_{x \in \{0,1\}^n} \alpha_x \left| x \right\rangle,
$$
where the $\alpha_x$ are complex numbers satisfying $\sum_x |\alpha_x|^2 = 1$. The $2^n$-dimensional (complex) sphere is just
$$
\{ (\alpha_{0\dots0},\ldots,\alpha_{1\dots1}) \in \mathbb{C}^{2^n} : \sum_x |\alpha_x|^2 = 1 \}.
$$
I'm not sure what "finding" $\left|010001\right\rangle$ on the sphere means, though.


An attempt on a partial answer:

Decision problems were already investigated for some time before optimization problems came into view, in the sense as they are treated from the approximation algorithms perspective.

You have to be careful when carrying over the concepts from decision problems. It can be done and a precise notion of NP-completeness for optimization problems can be given. Look at this answer. It is of course different from the NP-completeness for decision problems, but it is based on the sames ideas (reductions).

If you are faced with an optimization problem that doesn’t allow a verification with a feasible solution, then there is not much you can do. That is why one usually assumes that:

We can verify efficiently if the input is actually a valid instance of our optimization problem.
The size of the feasible solutions is bounded polynomially by the size of the inputs.
We can verify efficiently if a solution is a feasible solution of the input.
The value of a solution can be determined efficiently.

Otherwise, there is not much we can hope to achieve.

The complexity class $\mathrm{NP}$ only contains decisions problems per definition. So there aren’t any optimizations problems in it. And the Verifier-based definition of  $\mathrm{NP}$ you mention is specific to $\mathrm{NP}$. I haven’t encountered it with optimization problems.

If you want to verify that a solution is not just feasible, but also optimal, I would say that this is as hard as solving the original optimization problem because, in order to refute a given feasible and possibly optimal solution as non-optimal, you have to give a better solution, which might require you to find the true optimal solution.

But that doesn’t mean that the optimization problem is harder. See this answer, which depends of course on the precise definitions.


Proof of the inclusion-exclusion principle

Let me slightly rephrase the argument. Let $N_r$ be the number of elements contained in exactly $r$ of the sets $A_1,\ldots,A_n$. Then the left-hand side is
$$
|A_1 \cup \cdots \cup A_n| = \sum_{r=1}^n N_r.
$$
The first sum on the right-hand side is
$$
\sum_{1 \leq i \leq n} |A_i| = \sum_{r=1}^n \binom{r}{1} N_r.
$$
The second sum on the right-hand side is
$$
\sum_{1 \leq i < j \leq n} |A_i \cap A_j| = \sum_{r=2}^n \binom{r}{2} N_r.
$$
More generally,  the $m$th sum on the right-hand side is
$$
\sum_{1 \leq i_1 < i_2 < \cdots < i_m \leq n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_m}| = \sum_{r=m}^n \binom{r}{m} N_r.
$$
Therefore the right-hand side is equal to
$$
\sum_{r=1}^n \binom{r}{1} N_r - \sum_{r=2}^n \binom{r}{2} N_r + \sum_{r=3}^n \binom{r}{3} N_r - \cdots + (-1)^{n+1} \sum_{r=n}^n \binom{r}{n} N_r.
$$
Rearranging, the right-hand side is equal to
$$
\left[ \binom{1}{1} \right] N_1 + \left[ \binom{2}{1} - \binom{2}{2} \right] N_2 + \left[ \binom{3}{1} - \binom{3}{2} + \binom{3}{3} \right] N_3 + \cdots + \\
\left[ \binom{n}{1} - \binom{n}{2} + \binom{n}{3} - \cdots + (-1)^{n+1} \binom{n}{n} \right] N_n.
$$
The coefficient of the general term $N_m$ is
$$
\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m+1} \binom{m}{m}.
$$
By the binomial theorem, this equals $1$, and so the right-hand side equals
$$
1 \cdot N_1 + 1 \cdot N_2 + 1 \cdot N_3 + \cdots + 1 \cdot N_n = \sum_{r=1}^n N_r,
$$
which is exactly the same as the left-hand side.


You have to augment each pile with an extra bit which states if it has been passed or not. Then you can compute the Grundy function as usual. For example, here are some values:
$$
\DeclareMathOperator{\mex}{mex}
\newcommand{\yes}{\text{Yes}}
\newcommand{\no}{\text{No}}
G() = \mex(\emptyset) = 0 \\
G(1,\yes) = \mex(G()) = \mex(0) = 1 \\
G(1,\no) = \mex(G(),G(1,\yes)) = \mex(0,1) = 2 \\
G(2,\yes) = \mex(G(),G(1,\yes)) = \mex(0,1) = 2 \\
G(2,\no) = \mex(G(),G(1,\yes),G(2,\yes)) = \mex(0,1,2) = 3
$$
Here Yes means that the pile has been passed, and No that it hasn't been passed.

You mention that a recursive solution won't be efficient enough. In that case, I suggest trying to find a formula for the Grundy function. Here is a hint:

  A pile which has been passed behaves like a normal pile. A pile which has not been passed behaves like a pile which is one item larger.


How to find splitting point in [0,1] to maximize sum of sign function?

WLOG, let $a_i < b_i$. Then $(a_1 - x)(b_i - x) \geq 0$ when $x \leq a_i \vee x \geq b_i$.

Keep a list of intervals $I$. For each $a_i , b_i$ add $(0, a_i]$ and $[b_i, 1)$ to the intervals. Now you just find point $x$ such that it lies within the most intervals in $I$.


Planar Embedding with Some Nodes Constrained

This was meant to be a comment but it was a bit too long, sorry!

There is a well known algorithm to draw a planar graph, namely Tutte's drawing algorithm. The input graph is assumed to be 3-connected and planar. The idea of the algorithm is to fix the position of vertices of a face in convex position and from those coordinates deduce the positions for the rest of the vertices. The resulting drawing being a planar drawing of the input graph. Perhaps you can find more about this at [1].

With respect to grids, there are a couple of well known algorithms for drawing planar 3-connected graphs. One is Schnyder's algorithm (through the a Schnyder wood decomposition of the edges), and the canonical ordering algorithm (through a partition of the vertices of the graph). Both of these algorithms run in $O(n)$ time and produce drawings in an $O(n)\times O(n)$grid, where $n$ is the number of vertices of the input graph. At [2] you may find an overview of these two algorithms for the case of planar triangulations. You could even go to references [4] and [9] cited there for the original papers. It is worth noting that these algorithms have been generalized to work on 3-connected planar graphs as stated above.

Are you thinking about drawings subject to more specific constraints?


The question to be answered in an $LR(k)$ parse is "has the parse reached the end of a production?" (And if so, which production?)

If we are at the end of a production, we choose a reduce action. Otherwise, we shift the next input whatever it is.

So it should be clear that there are grammars which can be parsed without any lookahead; they are grammars in which no right-hand side is a prefix of a different right-hand side.


Confusion related to time complexity of dynamic programming algorithm for knapsack problem

Since computing each cell in the table is $O(1)$, the running time is just the size of the table. The first coordinate ranges from $1$ to $n$, and the second one from $0$ to the maximal value ever encountered (so it's really a dynamic table), which is $V^*$.


Traveling salesman problem - negative distances allowed

Hint: Every TSP tour has the same number of edges. Use this to modify the weights in the graph in a way which affects all TSP tours in the same way.


Line-search does not guarantee convergence so how to use it?

First of all, if we have a descent direction, we can always find a step size $\tau$ that is arbitrary small, such that "the sufficient descent criterion" is satisfied (see the Wikipedia article 'Backtracking line search'). This essentially rules out the infinite loop issue.
For example, consider Armijo condition as "the sufficient descent criterion", which is
$$
f(\bar{x}+\tau d) \leq f(\bar{x})+\gamma \tau\langle\nabla f(\bar{x}), d\rangle
$$
for $\gamma \in (0,1)$ and where $d$ satisfies $\langle\nabla f(\bar{x}), d\rangle < 0$.
If the function is twice differentiable, we can consider its Taylor expansion around the current iterate $x_k$ and show that as $\tau \to 0$, the Armijo condition is satisfied. However the step size could be arbitrarily small, when we consider the backtracking algorithm. To prevent this, we impose additional constraints on the step size, that prevent $\tau$ from being too small, while preserving the guarantee that such a step size still exists. For further details, you can check the Wikipedia article above.


What is the relation between correlation and causation in machine learning?

Not all of AI works on correlation, Bayesian Belief Networks are built around the probability that A causes B.

  I'm working on a system to estimate the performance of students on questions based on their past performances.

I don't think you need causation for this. A past performance does not cause a current performance. Answering on an early question does not cause an answer on a later question.

  But from the point of view of just building a system to pick questions that are likely to be of the appropriate difficulty level - does this distinction have any importance?

No, not for your example. I think correlation (or even simple extrapolation) would solve your problem very well. Assign a difficulty score to each of the questions and then feed questions to the students in increasingly difficult levels (which is how most exams work) and then when the student starts getting them wrong, you can wind back the difficulty. That's a feedback algorithm that is similar to the error minimisation performed on a neuron in a multi-layered perceptron. The non-trivial piece of input spaces like this is deciding what a difficult question is!

A better example of causation in AI would be:

  My car is slowing down. My accelerator is on the floor. There is not much noise. There are lights on the dashboard. What is the probability that I've run out of fuel?

In this case, running out of fuel has caused the car to slow down. This is precisely the sort of problem that Bayesian Belief Networks solve.


Three-address code versus JSON, XML, etc

XML and JSON are formats for representing data. The actual kind of data depends upon how you use them. For instance, they could be used to represent 3-address intermediate code or an abstract syntax tree, or even a symbol table.

3-address intermediate code is best generated only at the very end, as input to the code generator. For all other passes, keep as much information around as possible. This could include a decorated abstract syntax tree (decorated with types and other information) and a symbol table.

In fact, I'd only use the 3-address format if you are generating assembly. For a higher level target language, use a higher-level intermediate format.


From the comment: a quick way is to think that you are working on a two-tapes TM (initially the second tape is empty). You start placing $abc$ on it; then continue scanning it expanding the $a$, $b$ and $c$ substrings ($aabbcc,aaabbbccc,aaaabbbbcccc,...$) until the length of the second string matches the length of the input (or reject if you "overflow" it).
During a scan simply replace the first $b$ with 1 $a$, the first 2 $c$s with 2 $b$s and append 3 $c$s at the end.

   Input: 011010110101101
2nd tape: <empty>
  Scan 1: abc
  Scan 2: aabbcc
  Scan 3: aaabbbccc
  Scan 4: aaaabbbbcccc
  Scan 5: aaaaabbbbbccccc

At this point it should be easy to check if the three subwords are equal ... finally think how to "merge" the second tape into a single one (just add extra symbols to the tape alphabet ...).


Generating symbol matrices that satisfy regular expressions row- and column-wise

Here's one idea that may still take exponential time in $N$ but is polynomial in the (length of) the regular expressions.

Consider strings over the shared alphabet $\Sigma$ of length $N^2$; each such string represents an $N \times N$ matrix stored row-wise. We insert a separation character $\$ \not\in \Sigma$ between rows.

We will now construct a finite automaton the accepts exactly the set of such strings that fulfill your two regular expressions.

Let $r$ resp. $c$ be the row resp. column regular expression

Clearly, $r_N = (r \cap \Sigma^N\$)^{N-1}(r \cap \Sigma^N)$ matches all matrices that match $r$ in every row. Transform $r_N$ into an NFA $A_{r,N}$.
Denote with $A^{(i)}_{c,N}$ the automaton that matches only every $N$-th
input symbol (ignoring $\$$) against $c$, starting with the $i$-th.
I will leave the construction as an exercise; suffice to say that we
need at most $N$ copies of $A_c$.

Now, $A_{c,N} = A^{(1)}_{c,N} \cap \dots A^{(N)}_{c,N}$ accepts the set of all matrices each column of which matches $c$.
The automaton $A_{r,c,N} = A_{r,N} \cap A_{c,N}$ accepts all the matrices
you want.
A simple graph traversal finds an accepting path in $A_{r,c,N}$ finds
a solution matrix, if any.

The blowup in size is mild (i.e. at most a factor $N^2$) for all constructions but the intersections; these multiply sizes, so we may look at a factor $2^N$ for automaton size.

That's still way better than checking all $\Sigma^{N^2}$ possible matrices.


What are the underlying mechanisms allowing us to unsend an email?

The e-mail system has no way of manipulating already sent e-mails, no.

The only services I've seen which allow you to "unsend" an e-mail simply delay the e-mail being sent for a user-determined amount of time and then allow you to cancel the send before it happens.

Alternatively, I've seen some services allow you to "unsend" e-mails if the recipient is using the same e-mail client as the sender, as both sides are controlled by the same service. Although, once again, this is handled by the service provider, not by the e-mail system itself.


What is the difference in time-complexity for sorting these 2-d arrays?

The algorithm you suggest for $B$ is a comparison-based algorithm with complexity $O(n \log h)$, where $h$ is the maximum number of elements in the heap. Since $h = \Theta(1)$, you have that $B$ can be sorted in time $O(n)$.

Regarding $A$, the lower bound of $\Omega(m \log m)$ on any comparison-based algorithm that sorts $m$ elements still applies. Indeed, the first elements on each row (i.e., those of the first column) can be in any order relation with one another.

Any algorithm that sorts $A$, is also an algorithm that sorts the $m = \frac{n}{10} = \Theta(n)$ elements in the first column, and therefore it must have time $\Omega(m \log m) = \Omega(n \log n)$.


An algorithm can have worst-case running time that is both $O(n \lg n)$ and $\Omega(n \lg n)$; those don't contradict each other.  See How does one know which notation of time complexity analysis to use? and https://cs.stackexchange.com/a/201/755 for some background that might help understand why that is so.


Algorithm to detect if word belongs to pushdown automaton

As adrianN notes in their comment, your task is certainly algorithmically possible. There are algorithms that take a PDA $A$ and outputs a context-free grammar $G$ such that $L(A) = L(G)$, and others (such as CYK) that take a context-free grammar $G$ and a word $x$ and determine whether $x \in L(G)$.

There might be shortcuts, but at least this shows that your problem is decidable. In fact, since both algorithms run in polynomial time, the problem belongs to $\mathsf{P}$.

Judging from the literature, it seems that this chain of reductions is the standard way of solving the membership problem for pushdown automata. See for example these notes from Hendrik Jan Hoogeboom and Joost Engelfriet.


Push down automata for $\{a^n b^n c^n | n \ge 0\}$

Your PDA would also accept strings of the form $a^nb^ic^j$ where $i+j=2n$ and $i,j>0$. For example the string "aaabbbbbc" is accepted. There is no way to tell that there are exactly $n$ $a$'s still remaining on the stack once you've finished reading the $b$'s.


Is there constraint on reducibility while defining $\Sigma_i^p$?

In this definition, $M$ is constrained only to be a polytime relation, that is, you can compute $M$ in polynomial time. Note that there is no reduction here. The concept of reduction only comes up when you try to deduce that one problem is in a certain level of the hierarchy (or hard for a certain level of the hierarchy) given that another one is in some level of the hierarchy (hard for a certain level of the hierarchy).

For example, if $A \in \Sigma_i^P$ and $B$ polytime many-one reduces to $A$, then $B \in \Sigma_i^P$. If $A$ is $\Sigma_i^P$-hard and $A$ polytime many-one reduces to $B$ then $B$ is $\Sigma_i^P$-hard. If we consider reduction that are not polytime but are still in the polynomial hierarchy, we still get meaningful results that I encourage you to work out.


The real problem is you're making a mistake with the precedence rules being used. The sentence:
$$
(\lnot D + \lnot C)(\lnot D + B + A)(C + \lnot B + \lnot A)
$$
is ambiguous until we add rules of precedence, or explicitly parenthesise it. Because logical $\mathsf{AND}$ is associative (and commutative), we normally ignore the fact that we have to decide, one way or the other, which of the two $\mathsf{AND}$s applies first.

The normal rules we use (when nothing else gets in the way, go left to right) implicitly parenthesises the sentence as:
$$
[(\lnot D + \lnot C)(\lnot D + B + A)](C + \lnot B + \lnot A)
$$

If we parenthesise in this explicit way, and apply the distributive law, then you get what you expect:
$$
[\lnot D + \lnot C(B + A)](C + \lnot B + \lnot A)
$$

If we changed our rules of precedence to right-to-left and thought about it as
$$
(\lnot D + \lnot C)[(\lnot D + B + A)(C + \lnot B + \lnot A)]
$$
then we can't apply the distributive law at all, we have to apply the associative property first, then we again get what you expect.

In general you have to remember that we often simplify mathematical notation to ease reading, so when you are manipulation expressions, you have to remember that we're leaving things out, or put them back in for clarity.


Usually, concatenation is assumed to bind stronger than alternative, so you have $b \mid (bba)$, not $(b \mid b)ba$.

Then no, you can't drop "$b\ \mid$" since $b^+a \subseteq \mathcal{L}\bigl((b \mid bba)^*a\bigr)$ but $b^+a \cap \mathcal{L}\bigl((bba)^*a\bigr) = \emptyset$.

For what it's worth, $\mathcal{L}(b \mid b) = \{b \} = \mathcal{L}(b)$, so that simplification would be valid. More generally, if $\mathcal{L}(r_1) \subseteq \mathcal{L}(r_2)$, then $\mathcal{L}(r_1 \mid r_2) = \mathcal{L}(r_2)$.


Problems conjectured but not proven to be easy

Two decades ago, one of the plausible answers would be primality testing: there were algorithms that ran in randomized polynomial time, and algorithms that ran in deterministic polynomial time under a plausible number-theoretic conjecture, but no known deterministic polynomial-time algorithms.  In 2002, that changed with a breakthrough result by Agrawal, Kayal, and Saxena that primality testing is in P.  So, we can no longer use that example.

I would put polynomial identity testing as an example of a problem that has a good chance of being in P, but where no one has been able to prove it.  We know of randomized polynomial-time algorithms for polynomial identity testing, but no deterministic algorithms.  However, there are plausible reasons to believe that the randomized algorithms can be derandomized.

For instance, in cryptography it is strongly believed that highly secure pseudorandom generators exist (e.g., AES-CTR is one reasonable candidate).  And if that is true, then polynomial identity testing should be in P.  (For instance, use a fixed seed, apply the pseudorandom generator, and use its output in lieu of random bits; it would take a tremendous conspiracy for this to fail.)  This can be made formal using the random oracle model; if we have hash functions that can be suitably modelled by the random oracle model, then it follows that there is a deterministic polynomial-time algorithm for polynomial identity testing.

For more elaboration of this argument, see also my answer on a related subject and my comments on a related question.


How do we show that the polynomial time reduction of one problem to another has been done in polynomial time?

The reduction described in the mentioned post, from SAT to the halting problem, performs the following mapping:

$$\varphi\mapsto \big(\langle M\rangle,\varphi \big)$$

where $\varphi$ is a CNF formula and $M$ is the Turing machine which given a CNF $\psi$ as input, iterates over all the possible assignments to the variables of $\psi$, and enters a loop iff no satisfying assignment was found.

The machine $M$ does not depend on the input of the reduction, so it has some constant size description independent of the input $\varphi$. This means that you can output $\langle M \rangle$ in polynomial (even constant) time relative to the size of $\varphi$, hence the reduction is computable in polynomial time.

Note that you only need to show that you can generate $\langle M \rangle$ in polynomial time, which does not necessarily mean it has to have a constant size. Suppose e.g. that we want to show that $L=\{\langle M\rangle | \text{M halts on input $\epsilon$}\}$ is NP hard. In that case, the reduction $\varphi\mapsto \langle M_{\varphi}\rangle$ does the trick, where $M_{\varphi}$ is the machine which ignores its input, iterates over all possible assignments for $\varphi$, and enters a loop if no satisfying assignment was found. $M_{\varphi}$ does not have a constant size description, since you have to hardcode $\varphi$ into it. However, you can still generate $\langle M_{\varphi}\rangle$ in polynomial time, which makes the reduction polynomial.