Convert a decimal floating-point number into a binary floating-point number

I am not an expert in this area, but the following is what I know about this problem. This problem was solved in the following paper:

William D. Clinger. How to read floating point numbers accurately, ACM SIGPLAN Notices, 25(6) [Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation], pages 92–101, June 1990 (A PDF, you'll find other versions online)

This is also the reference cited by Knuth in TAOCP Volume 2, Exercise 17 in 4.4 (Radix Conversion).

In a retrospective published in 2004, the author looks back and cites the following additional references:

David Gay. Correctly rounded binary-decimal and decimal-binary conversions. Technical Report 90-10, AT&T Bell Laboratories, November 1990. At http://www.ampl.com/REFS/ (Direct link)

In particular, see function strtod in David Gay's dtoa.c available at http://www.netlib.org/fp/

The reverse problem (printing floating point numbers) is harder. It should probably be a separate question, but here are some references:

Steele and White, How to Print Floating-Point Numbers Accurately (also 1990, at the same conference)
Their retrospective
Burger and Dybvig, Printing Floating-Point Numbers Quickly and Accurately (1996)
Florian Loitsch, Printing Floating-Point Numbers Quickly and Accurately with
Integers
Printing Floating-Point Numbers: A Faster, Always Correct Method from POPL’16. Revised to Printing Floating-Point Numbers: An Always Correct Method (see github) (2016)

Popular expositions and other implementations:

Bryan Sullivan, Here be dragons: advances in problems you didn’t even know you had (2011)
Russ Cox, Floating Point to Decimal Conversion is Easy (2011)
Ryan Juckett(?), Printing Floating-Point Numbers (2014)
python-nicefloat
Aubrey Jaffer, Easy Accurate Reading and Writing of Floating-Point Numbers (2013)

Aside/Example: Even though this is a problem solved since 1990 (albeit with developments even last year), even Python until 2.6 had suboptimal printing of floating-point numbers, e.g. it would print float('2.2') as '2.2000000000000002'. It was fixed only in Python 2.7. See https://docs.python.org/2/whatsnew/2.7.html#python-3-1-features and https://docs.python.org/3/whatsnew/2.7.html#other-language-changes (specifically https://bugs.python.org/issue7117 and discussion at https://mail.python.org/pipermail/python-dev/2009-October/092958.html).


Detecting rotational symmetries of spatial structures

Here is one approach  to identify all rotational symmetries of the graph:

Pick any three vertices, $v_1,\dots,v_3$.  Loop over all possible combinations of three vertices $w_1,\dots,w_3$.  For each such combination, find the unique rotation that maps $v_1 \mapsto w_1,\dots,v_3 \mapsto w_3$, then check whether this is a rotational symmetry of the entire graph (by mapping the entire graph and seeing whether the mapped graph coincides with the original graph).

The worst-case running time will be something like $O(n^4)$, where $n$ is the number of vertices in the graph.  In practice I expect it to be typically more like $O(n^3)$, as most candidate rotations can be immediately rejected by testing a few vertices.

To identify the unique rotation that maps $v_1 \mapsto w_1,\dots,v_3 \mapsto w_3$, given $v_1,\dots,v_3,w_1,\dots,w_3$, see https://math.stackexchange.com/q/3341635/14578.


Transform grammar for repeating characters into LL(1)

Let's construct an LL(1) grammar for the language $\mathscr{L}(a^+)$.

Firstly, observe that all the production rules in this case must have one of two forms:
$$A \to a\Gamma$$
or
$$A \to \epsilon,$$
where $\Gamma$ is a (possibly empty) sequence of non-terminals and the terminal 'a'.

The first step would be adding the rule $S \to aS'$, since it's clear that $S \to aS \mid a$ doesn't give us an LL(1) grammar.
Obviously $S'$ must have a production rule with the empty string as its body $S' \to \epsilon$, which will be used when we get the end of string symbol $\$$ during parsing. We also need a "looping construct" to finish our construction, resulting in the following LL(1) grammar:

$$\begin{align}
S  &\to aS' \\
S' &\to \epsilon \mid aS'
\end{align}$$

From wikipedia:

  A nonterminal is left-recursive if the leftmost symbol in one of its productions is itself (...) or can be made itself by some sequence of substitutions (...).

Since neither $S'$ nor $S$'s left-most non-terminal symbol cannot be 'made itself' by any sequence of substitutions (there are simply no left-most non-terminal symbols there), the resulting grammar is not left-recursive.


Size of intersection of two acyclic DFAs A and B is O(|A|+|B|)?

Lemma 4 and Lemma 8 in your paper show that even for a fixed size alphabet, there are infinitely many finite languages with minimal DFAs $A,B$ of sizes tending to infinity such that the minimal DFAs for the intersection and union languages has $\Omega(\min(|A|,|B|)^2)$ states.


How to produce nonzero absolute differences between neighboring numbers on a circle as long as possible?

I am a bit cautious just in case you might be taking part of some kind of open competition or exam.

Before I could reasonably believe that you are raising this question in good faith, I will just say I can reach 51 iterations without going to all zeros using less than 18 digits for each number.

As an evidence that I do have an answer, here are the last 5 digits of my numbers. This will not help anybody to get a better answer, except when you are super good at math, in which situation you probably do not need this too tenuous a hint anyway. However, it can be used to prove beyond any doubt in the future that I did know an answer.
$$(***00000, ***22634, ***22881, ***60047)$$

Per request of the questioner, I will explain the simple "secret" of how to get an answer briefly. A full update may or may be followed later.

What you want is to let $a_1, b_1,c_1,d_1$ look like $a_0, b_0,c_0,d_0$ exactly. Since they look like exactly, the $a_2, b_2, c_2, d_2$ will look like $a_1, b_1, c_1, d_1$ exactly. You see you can actually go on forever. It will break down only when we cannot express the number accurately enough in its numerical representation, which is enforced since the geocacher owner does not accept values like $\sqrt 2$ (just for an example; there may or may not be a $\sqrt 2$ in my answer).

What does it mean by exactly alike? Well, for example, if the two circles of numbers are the same except by a factor and a rotation.


I would do it the following way:

First remove the Z production:

X-> Yc | dY | Y

and leave the others intact. Now you still have the First/First conflict, but you don't need to descent to the epsilon.

Next step, introduce a new symbol Y' for deciding wether to read a c or not.

 X-> YY' | dY
 Y' -> c | epsilon
 Y -> ab|cX

now you have a first/follow conflict. How to solve that:

Let's take a look at the produced language(Assuming X is the Start symbol) and transform the grammar:

L(G) = abc or c^n ab d ab..

X-> cX| ab |abY |dX

this should be LL(1).


What Does The Notation of Union Over K represent?

Authors often leave out the domain of the union if it is clear within the context. Here, $k$ is a natural number, i.e. $P = \bigcup\limits_{k \in \mathbb{N}} TIME(n^k) $. This is what it means for a complexity function to be bounded by a polynomial: there is a constant $k$ such that the function is in $\mathcal{O}(n^k)$.


Why aren't primality tests easily linear in time complexity?

It seems that the main sticking point of the question here is: Why express runtime in terms of the size of the input, rather than the numeric value that the input represents? And indeed in some cases it doesn't make much difference which way you choose to express it. For instance, we could say that the time to read all values in an $N\times N$ matrix is quadratic in the number of columns, or we could say it is linear in the number of cells, and the meaning of these is the same, just with different conventions.
So let's look at some reasons why it is conventional to express operations on numbers in terms of the length of the number rather than its numeric value:

It is more easily comparable to operations on other kinds of data, since every possible form of input has a length but not all forms of input have a numeric value. By consistently using the length of the input as our reference point across a variety of problem types, we also get some nice properties like "the runtime of an algorithm that reads the entire input can never be better than linear."

It provides more useful time complexities in context. For instance, a common use for primality testing is for cryptography. When we're doing cryptography, we might use say a 512-bit number as a key. We would like to have algorithms that scale proportional to the length of the number (512), rather than its numeric value (about $2^{512}$), since $2^{512}$ is such an astronomically large number that even a "linear" time algorithm would never realistically finish.

It relates better to the actual operations performed by the computer. Many people are accustomed to implicitly treating all numbers as capped at some fairly large constant like $2^{64}$, and thus all arithmetic operations are constant-time and the actual internal representation of the number is irrelevant. But when we are analyzing the big-O performance of operations on the number itself we cannot assume that numbers are always small enough to ignore their internal representation. Ultimately, these operations are performed on bits so the number of bits is a good reference point to use for describing the performance.
As a thought experiment, try analyzing the performance of the addition operation. You may have always considered it a constant-time operation, but what happens if the numbers in question get arbitrarily large? Ultimately, you'll need to sum each digit one-by-one, carrying as necessary. It makes sense to describe this as a linear-time operation based on the length of the input, rather than logarithmic time based on the numeric value of the input.


$\mathbf{NC}$ is closed under logspace reductions

Given any language $L$ in NL decided by some machine $T$, you can decide whether $x \in L$ by considering the configuration graph of $T$ when run on $x$. This is why PATH is NL-complete. Given any length $n$ of the input, the configuration graph is a fixed polynomial-size graph which doesn't depend on $x$. Only the starting vertex depends on $x$. We can arrange that the starting configuration corresponding to an input $x$ is configuration (vertex) number $x$. This implies that $L$ is in NC.

If we are careful we can do better and show that $L$ is in fact in uniform NC (under various definitions of uniform). The idea now is that given two configurations $\sigma_1,\sigma_2$, it is easy to decide whether $\sigma_1$ can reach $\sigma_2$ in one step. According to the complexity zoo, this way we can show that PATH is NL-complete under first order reductions (uniform AC0 reductions). Since uniform NC is closed under first order reductions, this implies that NL is in uniform NC.


The expressive completeness of the typed combinators compared to the simply typed lambda calculus has been demonstrated. For each untyped combinator, one needs a whole family of typed combinators. For example, one has

$\mathbf{I}_{\alpha\to\alpha}$
$\mathbf{K}_{\alpha\to(\beta\to\alpha)}$
$\mathbf{S}_{\alpha\to(\beta\to\gamma)\to(\alpha\to\beta\to(\alpha\to\gamma))}$

for all combinations of simple types $\alpha,\beta$ and $\gamma$.

Alternatively, just think of the types as type schemes (or polymorphic types) and enter them into Haskell and voila: combinators.


Conditions for applying Case 3 of Master theorem

Yes, your sharp observation is completely correct.

To be compatible with the highly strict style shown at section 4.6, Proof of the master theorem of Introduction to Algorithms, here is the complete proposition and a slightly more rigorous proof. It seems that the proof in the question ignores the requirement that $f$ is defined only on exact powers of $b$.
(Regularity implies lower-bounded by a greater-exponent polynomial.) Let $a\geq1$, $b>1$ and $f$ be a nonnegative function defined on exact powers of $b$. Suppose $af(\frac nb)\leq cf(n)$ for some fixed $c<1$ and for all sufficiently large $n$. Furthermore, $0 < f(n)$ for all sufficiently large $n$. Then $f(n) = \Omega(n^{log_ba +\epsilon})$ for some fixed $\epsilon>0$.
Proof. There exists some $n_0>0$ such that $af(\frac nb)\leq cf(n)$ and $0 < f(n)$ for all $n\ge n_0$. We can assume $n_0$ is an exact power of $b$ since, otherwise, we can replace $n_0$ by $b^{\lceil\log_b{n_0}\rceil}$.
Let $n\ge n_0$ be an exact power of $b$. So $n = n_0b^m$, where $m=\log_b\frac n{n_0}$ is an integer since both $n$ and $n_0$ are exact powers of $b$.
Applying $af(k/b)\leq cf(k)$ multiple times, we get
$$f(n) \ge \frac acf(\frac nb) \ge (\frac ac)^2f(\frac n{b^2})\ge \cdots \ge (\frac ac)^mf(\frac n{b^m})=(\frac ac)^mf(n_0)$$
Since
$$(\frac ac)^m=(\frac ac)^{\log_b\frac n{n_0}} =(\frac n{n_0})^{\log_b\frac ac}=(\frac n{n_0})^{\log_ba-\log_bc}=c_0n^{log_ba+\epsilon}$$
where $\epsilon=-\log_bc > 0$ and $c_0=(\frac1{n_0})^{log_ba +\epsilon}$ are two constants, we have
$$f(n) \ge c_0f(n_0)n^{log_ba +\epsilon}.$$
So,
$$f(n)=\Omega(n^{log_ba +\epsilon}).\quad \checkmark$$

What happens if $n$ is not necessarily an exact power of b?  The same result will hold if we replace $\frac nb$ by $\lfloor \frac nb\rfloor$ or $\lceil \frac nb\rceil$.  The following is a version when $\lfloor \frac nb\rfloor$ is used.
Let $a\ge1$, $b>1$ and $f$ be a nonnegative function defined on positive integers. Suppose $af(\lfloor \frac nb\rfloor)\leq cf(n)$ for some fixed $c<1$ and for all sufficiently large $n$. Furthermore, $0 < f(n)$ for all sufficiently large $n$. Then $f(n) = \Omega(n^{log_ba +\epsilon})$ for some fixed $\epsilon>0$.


What is the differences and similarities between refinement type and liquid types?

They are, to a first approximation, the same thing. "Liquid types" come from LiquidHaskell (1, 2), which is a programming language and verification framework based on refinement types. The Scala repository that you link to is an implementation of refinement types for Scala.

In terms of programming language theory, refinement types is the technically correct and more general term. LiquidHaskell and the Scala repository are examples of implementations of refinement types.


Proof that the Blank Tape Halting Problem is undecideable

You need to explain how to construct $R$. In your case this can be done formally, by constructing a machine which works as follows:

Write $w$ on the input tape.
Move the head back to its initial position.
Transfer control to $T$.

It is not too hard to construct $R$ explicitly from $T$.

In order for your argument to go through, you need to show that this reduction is computable. Usually we describe such reductions informally and just claim (without proof) that it is computable, since actually proving such things formally is extremely technical and longwinded.


Block sizes (aka Cache line lenghts) can be different on different levels of caches. L1 caches should be optimised for the type of access the CPU does while L3 caches should be optimised for the burst lenght and data width of the attached DRAM memory.

It is possible to fill/spill only one block of the L1 with a larger block sized L2 (in your example 4 words). On write back, either the whole L2 block is marked as modified, or use sub-blocking (effectively reducing block size without raising associativity).

One advantage with using the same size is probably with exclusive caches (AMD did that many times) : As soon as a block is in L1, copied from L2, the L2 block can be made available for new data.

Edit

Many examples there : http://www.7-cpu.com/
Using different block sizes across different cache levels seems very rare : Several recent x86 use 64Bytes, ARMs 32Bytes, PowerPCs 128Bytes, but they keep the same size on all levels. Note also the bus width : Internal busses can be extremely large, able to transfer 16 or 32 bytes in one cycle.


Odd cycle transversal and linear programming

No, $v$ does not have to belong to any minimum odd cycle transversal.
Consider the following undirected graph. The vertices are split into eight groups: $C_i$ for $i \in [0, 3]$, each of them containing $4$ vertices and $F_i$ for $i \in [0, 3]$, each containing $3$ vertices. The following edges (and only them) are present in the graph:

All edges between $C_i$ and $C_{(i + 1) \bmod 4}$ for every $i \in [0, 3]$
All edges between $C_i$ and $F_i$ for every $i \in [0, 3]$
All edges between $F_0$ and $F_2$, all edges between $F_1$ and $F_3$

Let's prove the following statements:

Any OCT that contains a vertex from one of the $C_i$'s has size at least $7$, but there are OCT's of size $6$ (for example, $F_0 \cup F_1$).
In any optimal solution to the LP relaxation, the variables corresponding to vertices from $F_i$'s are set to zero. Moreover, there is only one optimal solution to the LP relaxation: set all variables corresponding to vertices of $C_i$ to $1/3$.

If both are true, then, for every nonzero variable in the optimal solution to the LP, there is no minimal OCT that passes through the corresponding vertex. Because the graph is small enough, you can verify both these statements on a computer.
But I will give a short "human" proof to both.
For the minimum OCT part, it is clear that we should either delete each of the vertex group either fully, or not touch it at all (because just a single vertex from the group is "good enough representative" for the whole group). Moreover, we can see that deleting one $C_i$ group is not enough. If we delete, say, the group $C_0$, there is still an odd cyle $F_1 \to C_1 \to C_2 \to C_3 \to F_3 \to F_1$. Hence, we still have to delete at least one other group, for $7$ vertices in total. On the other hand, $F_0 \cup F_1$ is an OCT with size $6$.
Now let's deal with LP part.
It can be seen that all odd cycles in the graph pass through at least $3$ vertices from $C_i$. Hence, assigning weight $1/3$ to each vertex of each $C_i$ yields a solution with total cost $16/3$. On the other hand, consider all cycles of length $5$ in our graph. It can be proven that all vertices from $C_i$'s lie on exactly $3/16$ fraction of them, but all vertices from $F_i$'s lie on exactly $1/6$ fraction of them (the proof is a bit tedious to write down, so I will add it only by request). Then, by averaging the inequalities $x_a + x_b + \ldots + x_\ell \geqslant 1$ over all these cycles, we get $\frac{1}{6} \sum\limits_{v \in \bigcup F_i} x_v + \frac{3}{16} \sum\limits_{v \in \bigcup C_i} x_v \geqslant 1$, implying $\sum\limits_{v \in V} x_v \geqslant \frac{16}{18} \sum\limits_{v \in \bigcup F_i} x_v + \sum\limits_{v \in \bigcup C_i} x_v = \frac{16}{3} \left(\frac{1}{6} \sum\limits_{v \in \bigcup F_i} x_v + \frac{3}{16} \sum\limits_{v \in \bigcup C_i} x_v \right) \geqslant \frac{16}{3}$. Moreover, the inequality is strict if some $x_v$ with $v \in F_i$ is not zero. Hence, in each optimal LP solution, non-zero weights are assigned only to vertices from $C_i$'s. Moreover, it is possible to prove that there is only one optimal solution, with all weights of $C_i$'s set $1/3$. It is not too important, though, because we already proved that all optimal LP solutions are pairwise disjoint from all optimal OCT's.


A matrix $A$ is positive semidefinite if and only if there exists a matrix $V$ such that $$A = V^\top V.$$
So, you can use the entries of $V$ as your unknowns, and express each entry of $A$ as a quadratic function of the unknowns.  Whenever you want to use $A$, instead rewrite that equation in terms of the entries of $V$.


I think you're making a good point. It's just that since an $\epsilon$-transition from a state to itself must always be there in some sense (we can read nothing from the input stream and stay in the same state) it's more economical to make the convention that we don't consider such "transitions" to be transitions.


What is this type of consistency called in DataRetrieval?

I would call it expected consistency.

Unless you are just defining the $=$ operator.

When you get into transactions can have uncommitted or dirty value. By default $=$ will only match committed values but you can search on the uncommitted value. Look up ACID around data consistency.

Also careful with any as with an AND condition it needs to satisfy both so you may not get $R^1$ for $F_2 = V_2$ if another AND condition is not satisfied.


What is the set of operations of a Turing machine?

The set of operations is what makes the machine work, i.e. read input
somewhere, write output somewhere, and change its internal state
(which includes anything it may change in its memory which can be a
tape or some other device).

In the case of a TM, that is done by the transition function $\delta$.

Now, as you wish, you may see the transition function (actually a
relation, when non-deterministic)) as the unique operation applied
repeatedly. Alternatively you may consider that each instance of the
(arguments, effect) pairs defined by the function, usually defined on
a finite number of possible arguments pairs (state, tape content),
each associated with a finite number of effect triples (state,tape
output,move), are as many separate instructions, the transition
relation being then the instruction set.

It is not a fundamental issue to decide whether you see it globally or
case by case.


What would NP-complete solution in O(2^N/B) mean?

It says nothing about the P vs NP question because no such algorithm can exist.  If there is an algorithm that takes as its input a formula $\phi$ and an integer $B$ and determines whether $\phi$ is satisfiable in time $O(2^{N/B})$, where $N$ is the length of $\phi$, then we can decide SAT in constant time by calling the algorithm with $B=N$.

But we know that SAT cannot be solved in constant time because, in $k$ steps of the computation, you can only read the first $k$ characters of the input. That means that you have no way of distinguishing between the formulas $X\land X\land\dots \land X$ and $X\land X\land\dots \land X\land\neg X$, where $X$ is repeated, say, $k$ times. One of these formulas is satisfiable and the other isn't, but an algorithm running in $k$ steps would have to return "satisfiable" or "unsatisfiable" before seeing the $\neg X$ (or lack of it) at the end.


Relation Between Priority Queue, Heap, Tree

Arrays and linked lists are indeed simple data structures, but they are not more "fundamental" than other data structures. Everything in software is built out of contiguous memory to which the CPU has random access by address. All data structures are just abstractions built on top of that foundation.

A tree data structure is not composed of arrays and linked lists in any meaningful sense. You can implement a tree data structure using contiguous memory and pointers, just as you can implement a linked list using contiguous memory and pointers. If anything, a linked list is a special case of a tree in which each node has at most one child.

Saying that a tree is built from linked lists is like saying that a dinosaur is built from birds.

It is confusing a special case as a composition. A dinosaur is not composed of birds; a bird is a special case of dinosaur. A tree is not composed of linked lists; a linked list is a special case of tree.
However, the special case is itself only in a technical sense. If someone casually mentions the word dinosaur, they probably aren't thinking of birds. If someone casually mentions the word tree, they probably aren't thinking of linked lists.

You are also confusing the definition of abstract data type. An abstract data type is one where the operations are specified but the implementation is unspecified. A priority queue is an abstract data type, for which many concrete implementations are possible. Possible implementations of a priority queue include ones based on heaps stored in tree data structures; heaps stored in implicit trees in resizable array data structures; binary search trees; and many others. A linked list is an example of a concrete data structure which can be used to implement (among other things) a list abstract data type with operations for insertion, removal, indexing, etc.


PDA for all non-palindromic strings of even length

The solution is very much similar to PDA for palindromes of even length, except at atleast one place you have mismatched symbols.


How to check if my language is context-free can't seem to solve it using pumping lemma

One can proof that a language is CF by constructing a CFG or a PDA for it. I will give an example CFG for this language.

Let the start symbol be $S$.

In the definition we see that we can add arbitrarily many $m$'s, and for each $m$ there have to be two $t$'s.
$$M \rightarrow mMtt|\epsilon$$

The same for the $e$'s, but now with one $t$ fot each $e$.
$$E \rightarrow tEe|\epsilon$$

Then finally, there has to be an extra $t$. This gives following CFG:

$$S \rightarrow MtE$$
$$M \rightarrow mMtt|\epsilon$$
$$E \rightarrow tEe|\epsilon$$


Code and time complexity of multiplication à la française

In the function $T(n)$, the parameter $n$ represents the length of the input in bits. The recursive call reduces $y$ to $\lfloor y/2 \rfloor$, which reduces the length of the input by a single bit. Hence the recurrence is really $T(n) = T(n-1) + O(n)$, whose solution is indeed $T(n) = O(n^2)$.


Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?

You can prove precise equality for your recurrence. I'm going to assume the base case:

$$T(n) = \begin{cases}
  8 & n = 2\\
  8T\left(\tfrac{n}{2}\right) + n^3 & n > 2\\
\end{cases}$$

Claim: $T(n) = n^3 \log_2 n$

Base Case ($n = 2$): $T(2) = 8 = 2^3 \log_2 2 = 8$

Inductive Case ($n > 2$):

$$\begin{align*}
T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\
     & = 8\left(\tfrac{n^3}{8} \log_2 \tfrac{n}{2}\right) + n^3\\
     & = n^3 \log_2 \tfrac{n}{2} + n^3\\
     & = n^3 \log_2 n - n^3 \log_2 2 + n^3\\
     & = n^3 \log_2 n - n^3 + n^3\\
     & = n^3 \log_2 n & \square
\end{align*}$$

Thus $T(n) = n^3 \log_2 n \implies T(n) = O(n^3 \log n)$. No need to mess with lower or upper bounds.

However, in general this equality might not be the correct solution. Sometimes you will need to add lower order terms to get the equality or inequality to hold. A general approach to determine the lower order terms is as follows:

If we have:

$$T(n) = \begin{cases}
f(b) & n = b\\
aT(n/b) + f(n) & n > b
\end{cases}$$

We first assume $n = b^k$ for some $k$. Next we can turn this into a summation:

$$\begin{align*}
T(n) & = aT(n/b) + f(n)\\
     & = a(aT(n/b^2) + f(n/b)) + f(n)\\
     & = a^2T(n/b^2) + af(n/b) + f(n)\\
     & \vdots\\
     & = \sum_{i = 0}^{\log_b n - 1} a^{i} f\left( \frac{n}{b^i}\right)
\end{align*}$$

Then if you can find a closed form for this sum, we can easily prove equality by induction (e.g. substitution method) with proper constants. Here is your example again:

$$\begin{align*}
T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\
     & = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \left( \frac{n}{2^i}\right)^3\\
     & = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \frac{n^3}{2^{3i}}\\
     & = \sum_{i = 0}^{\log_2 n - 1} n^3\\
     & = n^3 \log_2 n\\
\end{align*}$$

Now you can go ahead and use this in your substitution method and you should not have any issues.

Feel free to try the same method with a trickier example:

$$T(n) = \begin{cases}
  12 & n = 3\\
  5T\left(\tfrac{n}{3}\right) + n^2 + n & n > 3\\
\end{cases}$$


Bin packing with given bin sizes, not necessarily same

Yes, it's still NP-hard, because the input could specify that the bins actually are the same size, which is the standard NP-hard version.

A general rule of thumb is that allowing the input to be more general can't make the problem any easier, as long as the new setting includes the original hard case as a special case.


How to prove that $\{0^n 1^{5n} \mid n \ge 10000 \}$ is not a regular language?

The condition $n>10\,000$ makes no real difference. If the pumping length is greater than $10\,000$, your existing proof works. If the pumping length is $10\,000$ or less, then pumping the string $0^{10\,000}1^{50\,000}$ gives you a string that isn't in the language because it has too many zeroes.


A big thing that is studied in higher type computability is infinite streams. Others have talked about hyper computation but this isn't quite the same. For starters the objects and functions studied in higher type computability are all things you can do in Haskell or some other such real programing language. These functions DO terminate in finite time thanks to laziness.

Exact real arithmetic is arithmetic that is performed on infinite binary streams or other kinds of infinite streams (dyadic digits and more commonly having both negative and positive digits). Addition of such streams terminates in finite time but produces another object which is infinite. The trick here is that the infinite streams are definable by computable functions that have finite construction. It turns out that classically there exist certain infinite streams that we can't define. For instance a computable real on the range $[0, 1]$ can be defined by a function $f : Nat \to Bool$. If we have an undecidable set $S$ then if we consider $f(x) = 1$ if and only if $x \in S$ then $f$ defines a real number but NOT a computable real number. It seems to turn out that there are no natural examples of such numbers coming up in practice however.

For more information take a look at one of my favorite blog posts: seemingly impossible functional programs


This seems like a dupe, but I couldn't find one in a cursory search. Given that, we can solve your problem as follows:

Generate NFAs $N_1$ and $N_2$ for the regular expressions $r_1$ and $r_2$;
Generate DFAs $M_1$ and $M_2$ for the NFAs $N_1$ and $N_2$;
Generate DFAs $D_1$ and $D_2$ such that $L(D_1) = L(M_1) \setminus L(M_2)$ and $L(D_2) = L(M_2) \setminus L(M_1)$;
Determine whether $L(D_1) = L(D_2) = \emptyset$; if so, $L(r_1) = L(r_2)$; else, $L(r_1) \neq L(r_2)$.

You can do (1) by using Kleene's theorem demonstrating that regular expressions and finite automata have the same expressive power. To each of the operations union, concatenation, and Kleene closure, there corresponds an automaton-based construction which accepts what the regular expression generates. By recursivly applying these constructions to subexpressions you can build an NFA to accept the language generated by a regular expression.

To do (2), you typically will want to use the powerset construction (sometimes called the subset construction). This involves constructing a DFA whose set of states equals the set of subsets of stats from the NFA. Transitions now connect subsets of states which are reachable from each other. The resulting DFA may have up to $2^{|Q|}$ states, where $Q$ is the set of states in your NFA.

To do (3), you can use the Cartesian product machine construction to generate machines with up to $|Q_1| \times |Q_2|$ states. Every state in your product machine will correspond to a pair of states from the operand machines. You must choose the set of accepting states to effect the correct operation; in our case, set difference.

To do (4), you can try all strings of length up to and including $|Q|$. If the machine accepts anything, it must accept some string of such a length. If you check all the strings and nothing's accepted, you know that $L(M) = \emptyset$. If that's the case, by construction, then the one language is a subset of the other. If both languages are subsets of each other, the languages are equal, by definition of set equality.


why the big-oh of a linear function is n^2?

A function does not have a unique big-oh. $O(f(n))$ denotes a class of functions that are big-oh of $f(n)$. Big-oh is used to give upper bounds.

For example, $f(n)=3n+5$ is $O(n)$, but it is also $O(n^2)$ and also $O(n^3)$ and also $O(2^{2^{2^n}})$. However, $f(n)$ is (in this example) not $O(\log n)$.

In set theory notation, we have $O(n)\subset O(n^2)$, i.e. any function that is $O(n)$ is also $O(n^2)$. However, if we had a function that is $O(n)$ and you gave $O(n^2)$ as an upper bound, that would not be incorrect, but it would be a weaker result than saying it is $O(n)$.

$\Omega$ works the other way around (i.e., it is used for lower bounds). A function that is $\Omega(n^2)$ is also $\Omega(n)$. $\Theta$ is used to give "tight" bounds: a function that is $\Theta(n^2)$ is neither $\Theta(n)$ nor $\Theta(n^3)$.


Find maximum element in sorted arrays in logarithmic time

If the elements need not be distinct, then you cannot have an $O(\log n)$ time algorithm.

Consider the sorted array $[0,0, \dots, 1]$ which has been cyclic shifted $k$ (unknown) times and you need to find where the $1$ appears. This needs $\Omega(n)$ time, as you need to examine at least $n-1$ elements.

However, if you assume the elements are distinct, then you can indeed give an $O(\log n)$ time algorithm.

Assume the array was sorted ascending. Once it is cyclic shifted, we will have that, in the rotated array (say $a[1,2, \dots n]$), that $a[1] \gt a[n]$. (It might help to draw a figure here, plotting $i$ on x-axis and $a[i]$ on the y-axis).

Now if you pick a $j$, you compare $a[j]$ with $a[1]$ and move right or left, depending on whether it is greater or lesser, like binary search.


A quick way of gaining some confidence or disproving a conjecture is using a computer to generate examples.

For Q1, if $x,y \in V$ such that $d(x,y) = D$, it is not true that any shortest path between $x$ and $y$ contains at least one central vertex (highlighted in red). Here, you can walk from 1 to 6 via 9, 5, and 8 avoiding the red vertex.

For Q2, the answer is also no. Below is a graph whose radius is 2 and diameter is 4. It has 3 central vertices (highlighted in red).

You can use ideas from these counterexamples to optimize the graphs further.


Interval schedule maximization when encountering intervals with equivalent end points

The greedy algorithm can be characterized as follows:

Let $I$ be the initial set of intervals

1) Select an interval, $x \in I$, with the earliest finishing time.

2) Remove $x$ and all intervals intersecting $x$ from $I$, obtaining $I^{'}$.

3) add $x$ to the solution

4) Set $I=I^{'}$

5) Continue until $I$ is empty.

Here, $x$ is some remaining interval that finishes before all other intervals in $I$. When we add $x$ to our solution we have already removed any interval with the same finish time as $x$ that may have had a start time which was "too early." If there is some other $y\in I$ with the same finish time as $x$ that is present when $x$ is chosen, then by necessity, both $x$ and $y$ begin after the last interval we added to our solution, so either is a legitimate choice.


Understanding the time-complexity of Insertion Sort

As I see this, it is clear that the array is indexed from 1 to length[A] instead of the usual 0 to length[A}-1.

The first statement is executed n times. It is just that (n-1) times it enters the loop and the last time n'th time when j > length[A] it exits from the loop.

Hence it is correctly mentioned that the internal statements get executed n-1 times.


Dividing EX stage of a pipeline into EX1 and EX2 stages

This is multi-cycle processor, where each stage takes a single clock cycle. The text suggest that the new MEM stage should take 2 clock cycles. Then, it can be seen as splitting this 2-cycle stage into 2 separate 1-cycle stages which we can call MEM1 and MEM2 respectively.
There is no new input. You only need to make sure that the "right" input travels along the pipeline and reaches the right stage at every time.


Best complexity to find solutions to $x^2+y^2=z^2$

I think you are asking about Pythagorean Triples (the form $x^2+y^2=z^2$ where $x$,$y$ and $z$ are integers).

Euclids Formula is generally thought to be efficient for finding primitive Pythagorean Triples.You can multiply these primitive triples with a constant to get non primitive Pythagorean Triples.

Here are some other methods of finding Pythagorean Triples


Proving that $\mathrm{SpaceTMSat}$ is PSPACE-complete

For any complexity class $X$, a language is $X$-complete if it's in $X$ and every problem in $X$ can be reduced to it. There are two main ways to prove that a language is $X$-complete: literally show that it meets the definition of $X$-completeness, or show that some other $X$-complete problem reduces to it.

In cases where the language is essentially, "Here's a machine in~$X$ and an input: does it accept?", it's usually best to go for the literal approach and show that every problem in the class can be reduced to your problem. Why? Because every problem in the class is decided by a Turing machine, and your language is about whether those Turing machines accept or not.


All-to-All Broadcast on a Balanced Binary tree

There are 8 processors: P0..P7, each contains one of the messages M0..M7 so

P0: M0, P1:M1, P2:M2, P3:M3, P4:M4, P5:M5, P6:M6, P7:M7

P0, P1, P2, & P3 are on the left subtree and P4, P5, P6, P7 are on the right subtree.

Step1:

All the processes make a copy of the message and left subtree processors exchange the copy with the corresponding processors on the right subtree. Result is that each processor now has two messages as shown below:

P0 & P7: M0, M7

P1 & P6: M1, M6

P2 & P5:M2, M5

P3 & P4:M3, M4

Step2:

Now P3 & P0 would make a copy of their messages and exchange the copy. Pairs of P1, P2 and P4,P7 and P5, P6 would repeat this action. The result is shown below:

P0, P3, P4 & P7: M0, M3, M4, M7

P1, P2, P5 & P6: M1,  M2, M5, M6

Step3:

Now P0 & P1, would make a copy of their messages and exchange the copy. Pairs of P2, P3 and P4, P5 and P6, P7 would repeat this action. The result is the final broadcast:

P0, P1, P2, P3, P4, P5, P6, P7 would all contain the messages:

M0, M1, M2, M3, M4, M5, M6, M7

Zulfi


Will Java's hashCode() reduce collisions regardless of table size?

Java's default implementation for hashCode() is probably doing quite a good job. If you were designing (or implementing) a language then you'd want to design your hashing function perform well. So yes, you should be generating your own hash codes.

If hash codes are more-or-less random (as they should be) then table size does not matter at all. Table size only starts to matter when the hash function is poor.

Suppose that, by some fluke, your hash function only output even numbers. Then, if the table size also were even, you'd only ever use half of the slots in your table (the even ones) - more than doubling the collision rate.

Now suppose that, all hash codes are $1$ modulo $3$. If your table size is a multiple of three, then you'd only ever use slots that are $1$ modulo $3$, cutting the effective size of your table by third.

The reason you want to pick a prime as table size is that this avoids any issues with poor hash functions (unless your hash codes all happen to be the same modulo that prime). On the other hand, picking $223092870$ as table size is a terrible idea.


Making a branch-and-bound algorithm more efficient for a large input

It isn't clear if you are asking about time or memory efficiency.  If you care more about memory, then it would be best to traverse the tree.  If you care more about time, then it would be best to copy and modify both lists at each node.  However, there are more than two alternatives.  You could store a single number at each node, which identifies the items in the knapsack.  For example, the binary number 10110 would denote the first, third, and fourth objects as being in the knapsack.

I don't want to do your homework for you, and you didn't ask me to, but I also recommend considering a more memory efficient DP approach if you haven't already.  Good Luck!


Closed (visited) list in state-space search - How do I make it efficient?

Use a hash table to store the visited list. Searching the list should take $O(1)$.


What data structure would efficiently store integer ranges?

I suggest you use a binary search tree, augmented so that leaves can contain an interval (a run of consecutive integers).  Maintain the invariant that the intervals do not overlap and are in order (following the search tree invariant).  (This can be considered a special case of an interval tree or a segment tree, for the special case where the intervals do not overlap.)

This data structure you can support all of your operations in $O(\lg n)$ time, where $n$ is the number of intervals.  Since we're guaranteed $n\le 65535$, I would expect this to be quite efficient.  (In particular, yes, you can split an interval into two pieces or merge two adjacent intervals into a single interval in $O(\lg n)$ time.)


Is the given language decidable for turing machine?

Consider a problem 'A' which is undecidable. If 'A' is reducible to another problem 'B', then problem 'B' is undecidable.

Consider following two statements:

p: Turing machine halting problem is undecidable.
s: A given Turing Machine 'M' reaches a state 'q' on reading input 'w'.

If we can modify statement 'p' in such a way that the answer to 's' will be answer to 'p', then we can say problem 's' ( statement 's' ) is undecidable.

Also note that I will be using a term "Dead Configuration" to mean the Turing machine is in a state from which no further transitions is defined i.e, a Turing machine halts because of a dead configuration.

Modified version of 'p': A Turing machine halts only at state 'q'.

That is, whenever a Turing machine reaches a dead configuration, we will make a transition to 'q'.
Modified version pf 'p' is undecidable, which means it is undecidable that a Turing machine reaches a state 'q' on reading any input.
Hence, problem 's' is also undecidable.

On the same lines statement 's' can be modified to prove that the problem, "Turing machine will accept a string" is undecidable.

Hence, if the problem: "whether a string is accepted by a Turing machine" is undecidable then the problem of counting the number strings in a language will also be undecidable.


Number of bits needed to represent an integer with a specifed base

You could, if you wanted, encode each digit of the base $b$ representation of an integer in $\lceil \log_2 b \rceil$ bits. This was actually done in the very early days of computing, when binary-coded decimal (BCD) encoding was used to store each digit of the decimal representation of an integer in four bits, from $0000$ for $0$ to $1001$ for $9$.

This somewhat simplifies user input and output (as long as your users always want to work in decimal). The downside is that it makes internal arithmetic more complex, and it wastes memory space. In BCD encoding one byte ($8$ bits) of memory can only store an integer between $0$ and $99$, whereas in binary encoding it can store any integer between $0$ and $255$.

All modern computers store integers internally in binary and do all their internal arithmetic in binary, and convert from or to other bases in their input and output as necessary.


We call a set of languages, $P\subseteq 2^{\Sigma^*}$, a property. If you think of this subset as the set of languages who satisfy some property, then we can simply say that a language $L$ satisfies the property iff $L\in P$.

Rice theorem tells you that you can't, given a Turing machine $M$, check if $L(M)$ satisfies some non trivial property $P$, i.e. $P\neq \emptyset$, $P\nsupseteq RE$. Note that Shaull makes a distinction between semantic and syntactic properties in the comments. To the best of my knowledge, the standard definition of a property in the context of Rice's theorem is a set of languages.


Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program

No. If you could do that in linear programming then you could force a variable to have binary values, so you'd be able to solve integer linear programs using LP solvers.
Indeed, we can simulate $x \in \{0,1\}$ with:
$$
\max\{x, 1-x\} \ge 1, \\
x \ge 0, \\
x \le 1.
$$


How can I calculate the new quotient if I came to know divisor is increased by one?

Knowing the ratio r = A / B and nothing else about the numbers A and B, there is very little we can say about for example A / (B + 1) or A / (B - 1). We have A = rB. If for example B = 1, then A = r, and A / (B + 1) = r / 2, half the value of A / B. On the other hand, if B = 1,000,000 and A = r*1,000,000 then A / (B + 1) = r * 1,000,000 / 1,000,001 = r - r / 1,000,001, barely different from r.

In the example A / B = 50 and r = 50, when B is replaced with B + 1, the ratio r changes from 50 to 25 if B = 1, but only from 50 to about 49.999,950 if B = 1,000,000.


Matrix Representation for logical gates?

Yes, "all of the propositional logical operators can be done with a unique binary 2×2 matrix".

In fact, every possible map $g: \{0,1\}\times\{0,1\}\to\{0,1\}$ can be done with a unique binary 2x2 matrix.

Here is a proof.

$$\begin{align}
 &\quad \begin{bmatrix} X, \  \neg X  \end{bmatrix}\begin{bmatrix} A & B\\ C & D\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} \\&= \begin{bmatrix} XA \oplus \neg XC, \ XB \oplus \neg XD \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} \\
&= XAY \oplus \neg XCY \oplus XB\neg Y \oplus \neg XD\neg Y\\
\end{align}$$

Suppose the above expression equals $g(X,Y)$.

Let $X=0, Y=0$, we get $0\oplus0\oplus0\oplus D=D=g(0,0)$.
Let $X=0, Y=1$, we get $0\oplus C\oplus0\oplus 0=C=g(0,1)$.
Let $X=1, Y=0$, we get $0\oplus0\oplus B\oplus 0=B=g(1,0)$.
Let $X=1, Y=1$, we get $A\oplus0\oplus0\oplus 0=A=g(1,1)$.

Conversely, if we have $A= g(1,1)$, $B= g(1,0)$, $C=g(0,1)$ and $D=g(0,0)$, the above expression can be verified to be equal to $g(X,Y)$ for all $X, Y$.

So we have proved that

$$ \begin{bmatrix} X, \  \neg X  \end{bmatrix}\begin{bmatrix} A & B\\ C & D\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = g(X,Y) \\ \Leftrightarrow A= g(1,1),\ B= g(1,0),\ C=g(0,1),\ D=g(0,0)$$

If we use in-fix notation for $g$, we have
$$ \begin{bmatrix} X, \  \neg X  \end{bmatrix}
\begin{bmatrix} 1g1 & 1g0\\ 0g1 & 0g0\\ \end{bmatrix}
\begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = XgY, $$
or
$$ \begin{bmatrix} 1g1 & 1g0\\ 0g1 & 0g0\\ \end{bmatrix}
 \equiv g. $$
In particular, we can substitute $g$ by anyone of $\land, \lor, \oplus, \odot, \Rightarrow, \Leftarrow, \equiv$.

For more related concepts and computation, please check boolean rings.


How to build 4 codewords with a code distance of 5?


Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?

The fundamental restriction is human computer programmers' inability so far to create computers equipped with real intelligence. "Never" is a very long time, so it's hard to accept that something will "never" happen unless there is a very good argument.

Human brains and computers are not fundamentally different. The practical difference is that some human brains are programmed in a significantly better way for finding mathematical proofs, while computers have other advantages. With equally good programming, computers would probably have the advantage.

And remember that the majority of humans are also unable to do any mathematics better than current computers can.

PS: P vs. NP is a red herring. Computers are not able to generally solve NP complete problems above modest size because it is too computational intensive (but often many instances can be solved, just not all). But nor can humans. No mathematical proof that humans have found ever involved solving a hard instance of an NP-complete problem. On the other hand, there are many problems in P that are just as unsolvable.

PS. In general the problem "given a mathematical hypothesis, is there a proof for it" will be NP-hard (take any instance of an NP-complete problem, and declare that "answer is YES" is a mathematical hypothesis). The question "is there a proof for Fermat's Last Theorem" is obviously an easy instance of that problem :-) Since it took humans 357 years to prove, we can take bets if computers will manage quicker.


Merging rectangles into rectilinear polygon

Form a list of the $4n$ edges making up the $n$ rectangles.
Delete every edge that appears twice.

The edges that remain describe the outside of the polygon.  If you want to list these edges in clockwise or anticlockwise order, that's easy enough to do -- just pick an arbitrary starting vertex and find one of the two edges it is incident on, then find the other edge that the other vertex of that edge is incident on, repeating this until you hit the original vertex again.  If you encounter two edges in the same direction, you might want to turn them into a single, longer edge as you go.


Consider the following problem I'll call check-for-ones (where it is easy to show a lower bound of $\Omega(n)$): given a binary array of length $n$, check if there are any 1s in this array. We'll reduce this problem to the sorted-2-sum problem, thereby showing that sorted-2-sum also should require $\Omega(n)$ time.

We need to be a bit careful what we mean by "reduce" here; the standard notion of polytime reduction is useless, and even a linear-time reduction doesn't say much since we can solve both problems trivially in linear-time. Our reduction will have the following property: it will reduce an instance $y$ of our check-for-ones problem to an instance $x$ of the sorted-2-sum problem such that for any index $i$, we can compute $x_i$ in time $O(1)$ given random access to $y$ (assuming that all word operations take $O(1)$ time).

Now, if you can solve sorted-2-sum in $O(t)$ time, you read in at most $O(t)$ values $x_i$, and each $x_i$ can be computed from associated $y_j$ in $O(1)$ time, and therefore you can also solve check-for-ones in $O(t)$ time.

Here is the reduction. Let the array $x$ have length $2n$. When reading a value $x_i$ proceed as follows:

If $1 \leq i\leq n$, let $x_i = -100(n+1-i)$
If $n < i \leq 2n$, let $x_i = 100(i-n) + y_{i-n}$

Now, the equation $x_{j} + x_{k} = 1$ has a solution iff there exists a $y_{i} = 1$ (in particular, $(j,k)$ must be a pair of the form $(n-a, n+a-1)$).

An example might help as well, let $y$ be the following:

$$y = \{0,0,1,0\}$$

We then have that $x$ (if we were to have read $O(n)$ values) would be:

$$x = \{-400, -300, -200, -100, 100, 200, 301, 400\}$$

We can see how $x_j + x_k = 1 \Leftarrow \Rightarrow \exists y_i =1 \in y$. In our case, $-300 + 301 = 1$ implies $y_3 = 1$.


I don't know whether there is an efficient (polynomial-time) algorithm for this problem.   I wouldn't be surprised if it is NP-hard.

One approach would be to formulate this as an instance of integer linear programming, and then apply an off-the-shelf ILP solver to find the best solution it can within some fixed amount of time.  This gets awfully ugly.  You could introduce a bunch of zero-or-one variables to represent the solution, write down constraints (inequalities) to capture that they are consistent, express the cost of a solution as a linear combination of these variables, and then use the ILP solver to minimize the cost.  However, writing down the set of inequalities might get super messy.

Alternatively, it might be possible to apply heuristics for weighted set cover or weighted exact cover to this problem.  Given any candidate combination of 3..5 terminals and a candidate location for the intermediate point, you can easily compute the cost of connecting them.  Consider this as a "set" that covers those terminals and that intermediate node, and whose cost is equal to the computed cost.  There are $n_1 \times ({n_2 \choose 3} + {n_2 \choose 4} + {n_2 \choose 5})$ many such "sets", where $n_1$ is the number of internal nodes and $n_2$ is the number of terminals.  This is $O(n^6)$, where $n$ is the number of nodes in the graph.  Now the goal is to find a cover, i.e., a subset of "sets" that covers each terminal exactly once and that covers each internal node at most once.

In principle you could then try applying any algorithm for exact cover.  However, I suspect this will be far too slow, as there will be a few hundred billion possible "sets" or so.

An alternative might be to apply a heuristic or approximation algorithm for set cover.  For instance, consider the greedy algorithm for set cover: at each step, it chooses a set that minimizes the cost of the set divided by the number of terminals that are newly covered by that set and haven't been covered yet (best "bang-for-the-buck").  This gives a solution that is not too much more expensive than the optimal solution.

Moreover, you can implement the greedy algorithm efficiently, without enumerating all sets.  At each step, we have already covered some of the terminals and some of the internal nodes, and we want to choose the next set with the best bang-for-the-buck ratio.  This seems feasible.  One naive way to do that is to iterate over all possible choices for the location of the intermediate point, and for the number $k$ of terminals (3..5), and then find the $k$ closest uncovered terminals to that intermediate point; each gives you a candidate set.  Also find the closest uncovered terminal to $s$; this gives you another candidate set (with no intermediate point).  Among these candidates, take the one with the lowest bang-for-the-buck ratio and add it to your solution so far.  If you precompute all-pairs shortest paths (e.g., with the Floyd-Warshall algorithm), then each step can be implemented in $O(n^2)$ time.  You need to do at most $n$ steps, so the total running time will be $O(n^3)$.

This might give a highly suboptimal solution, but it is at least one solution, and it should be relatively efficient with your parameter settings.

Alternatively, it might be possible to use local search or simulated annealing to optimize your solution.  The key requirement is to have a way, given a current solution, to find a way to perturb the solution in a random way.  The algorithm then tries this many times, hopefully gradually decreasing the cost of the solution over time.  In your situation, one way to random perturb a candidate solution is to either (1) randomly pick three terminals that currently aren't part of any pack and merge them into a pack, (2) randomly pick a terminal that currently isn't part of any pack and a pack of size 3..4, and merge them into a single pack, or (3) randomly split a pack of size 4..5 into a pack of size 3..4 and a terminal that isn't part of any pack.  You could then try simulated annealing together with such a choice of perturbation (neighborhood relation).  There might be smarter ways to choose the perturbation that makes those algorithms more effective.

Maybe someone else will be able to come up with a better approach.


How to order objects to minimize non-adjacency cost

Your problem is just the problem of finding a maximum-weight Hamiltonian path in a weighted graph.

A candidate way of ordering objects in your array corresponds to a Hamiltonian path.  The total weight of that Hamiltonian path (the sum of the weights on the edges in the path) is exactly the sum of the "non-adjacency costs" you don't pay.  Minimizing the sum of the "non-adjacency costs" you do pay is equivalent to maximizing the sum of the "non-adjacency costs" you don't pay.

Unfortunately, this problem is NP-hard, so you should start looking for approximation algorithms or heuristics or special cases.  For instance, there may be some special kinds of graphs (say, bounded treewidth or bounded clique-width) for which this problem might be solvable in polynomial time.

See also https://en.wikipedia.org/wiki/Hamiltonian_path_problem and https://en.wikipedia.org/wiki/Longest_path_problem.

You might also try looking at simulated annealing, which is often a good candidate approach to explore for these kinds of problems, and is in some ways a generalization of the sort of algorithm that you mention in your question.


Is the language of strings with an integer ratio of the number of a's to the number of b's context-free?

The language is not a CFL. The string $w$ that is the counter example to the pumping lemma is $a^{(N+1)^2}b^{(N+1)}$ where $N\geq 1$ is the pumping length. The idea is to take the number of $a$'s comparably larger by an order of $N$ to the number of $b$'s. Then if you pump you get strings with $\#_a={(N+1)^2+ik_1}$ and $\#_b ={N+1+ik_2}$ for $i\geq -1$. You would be able to prove that his string does not belong to $L$ for some $i$ and for any $k_1+k_2\leq N$.

Or if we take some crazy long string like $w = a^{(2N)!}b^{N+1}$, noting that the pumped string will have $\#_a={(2N)!+ik_1}$ and $\#_b={N+1+ik_2}$ for $i\geq -1$. If $k_1 = 0$ then we can take $i > \frac{(2N)! - N -1}{k_2}$. If $k_1 > 0$ then for $i=1$,
$\frac{(2N)!+k_1}{N+1+k_2}$ is a proper fraction, since $0\leq k_2 \leq N-1$, $1 \leq k_1 \leq N$ and therefore $N+1 \leq N+1+k_2 \leq 2N$ which implies $0<\frac{k_1}{N+1+k_2}<1$ is a fraction.


Bottom-up Mergesort vs Natural Merge Sort

Natural Mergesort usually refers to Timsort. In terms of comparison to bottom-up mergesort, Timsort has $O(n)$ best-case running time where as bottom-up mergesort is at least $O(n\log n)$ on any input.
However, analysis of the worst-case running time of Timsort proves to be more tricky; an 2018 paper [1] establishes that its worst-case time complexity is $O(n\log \rho)$, where $\rho$ is the number of maximal monotonic sequences in the input array.
[1]: Nicolas Auger, Vincent Jugé, Cyril Nicaud, Carine Pivoteau, "On the Worst-Case Complexity of TimSort"


Suppose you are given a 0-1-Integer-Programming instance. You need to substitute $x_i$'s, $x_i \in \{0,1\}$, with new variables $y_i$'s as G. Bach mentioned. The substitution is $x_i = y_i/2$, $y_i \in \{0,2\}$.

By this substitution, you get
 0-1-Integer-Programming $\leq_P$ 0-2-Integer-Programming
 and also 0-2-Integer-Programming $\leq_P$ 0-1-Integer-Programming by reverse substitution.
(This is because the polynomial reduction function in this case is invertible).

Therefore 0-2-Integer-Programming is also NP-complete
(from 0-1-Integer-Programming $\leq_P$ 0-2-Integer-Programming).

By the way, you are not allowed to add $x_i \neq 1$ in canonical integer programming problem. Basically it means $x_i \leq 0$ OR $x_i \geq 2$. We can't have OR constraints, all we can have is AND constraints.


Does canonicity imply weak normalization?

Canonicity does not imply weak normalization. First, let me phrase the involved definitions more precisely:

WN: every open term is reducible to a normal term
Canonicity: every closed term is reducible to a canonical term

(Note: in modern metatheory of type theory, it is more common to talk about conversion instead of reduction, and likewise to talk about unique existence of normal forms instead of weak/strong normalization. This answer remains valid if we replace "reducible" above with "convertible").
Normal and canonical terms are not the same. For example, the x variable in x : Bool context is normal but not canonical. Also, the closed term λ(b : Bool). if true then b else b is canonical but not normal.
Extensional type theory has the canonicity property but not WN, SN, or unique existence of normal forms. That's because in ETT it is possible to add an inconsistent definitional equality to the context, or add an equational theory of a Turing-complete system. For example, in the ETT context n : Nat, p : n = suc n the n variable has no unique normal form, since n can be expanded arbitrarily using p.
However, if we have a closed ETT term, we can't have anything dodgy in the context, so a closed term can be still evaluated to a canonical form.


Is Goedel's 1st theorem not algorithmically derivable?

Your reasoning is incorrect.

It is true that your hypothetical "proof deriver" cannot derive all true statements. No proof derivation system can, and indeed, it is not even possible to express the set of true statements in arithmetic, which is a consequence of Tarski's theorem on truth, itself a consequence of Gödel's theorem.

However, your algorithm does enumerate all provable statements, including the incompleteness theorem itself.

In fact, here's a much simpler algorithm:

Print a formal proof of the incompleteness theorem.
Halt.

So you need a much subtler argument to prove that computers can't do what humans can do in terms of proofs. Certainly you would need a better notion of what "prior knowledge" of a proof means. Indeed, many people today believe that there are no tasks which are fundamentally impossible for computers but possible for humans, and I know of no unassailable argument for that position.


Maximum flow with maximum flow on specific edge

I would do it kind of the other way around as you suggested.

First compute a flow that saturates $(u,v)$. This can be done with the Ford--Fulkerson algorithm. Look only for augmenting paths which contain $(u,v)$ and augment the flow until the edge is saturated.

In the second step you augment further, but avoid the edge $(u,v)$ when searching for augmenting paths in the residual network. There is no reason to desaturate $(u,v)$. If we desaturate the edge with one path and saturate it with another we can get to the same flow by augmenting with the "product" path which avoids $(u,v)$.

This is not a proof but should guide you in a possible direction how to solve this.


A very simple solution if your integers are not too big, let's say biggest integer is $U-1$ and there are $U$ different integers (between 0 and $U-1$), is to build a table T (bit matrix) of size $U$ with all bits set to $0$. Upon occurrence of item $k$ set $T(k)\leftarrow 1$.

If you want to search for an item $k$ you simply check if $T(k)$ is $1$ or $0$.
This solution takes $\Theta(U)$ space and $\Theta(1)$ time per inserted item, or per search.
If $U$ is much less than $n$ and you don't make deletions then I think
this solution is ideal in your case. If you make deletions of $U > n$ then more sophisticated solutions are needed


Suppose that there exists a polytime algorithm which finds a clique of size $n^\epsilon$ if there is any. Then you can approximate maximum clique to within $n^{1-\epsilon}$ (assuming $\epsilon \leq 1/2$), which is NP-hard by a classical result of Håstad. Indeed, run your algorithm (stopping it if it exceeds its advertized running time), and check whether its output is a clique of size at least $n^\epsilon$. If so, output $n^\epsilon$, otherwise output $1$.

You might want to look into the planted clique problem, in which the goal is to find a clique "planted" inside a uniformly random graph. This is possible in polytime (with high probability) as long as the clique is large enough, $\Omega(\sqrt{n})$. Your case may be different, but similar ideas might work in practice.


Make a list of all $2n$ beginning and ending points of the $n$ ranges.  Record each as a (position, type) pair.
Sort this list by position, with starting points comparing below ending points when positions are equal.
Loop through the sorted list, incrementing a counter variable (initially zero) whenever you see a beginning point and decrementing it whenever you see an ending point.  On a 0->1 transition of this variable, output the current position as a starting point.  On a 1->0 transition, output the current position as an ending point.


Your proposed factoring won't work correctly because both productions start with the same nonterminal. Remember that for an LL(1) parser you cannot have two productions that start with the same nonterminal (usually) because if you see anything in the FIRST set for that nonterminal, you wouldn't know which production to pick.

To left-factor the grammar, try something like this:

  C → AX

  X → BC | ε

Notice that this gives you the same strings as before, but (assuming that at least one of B and C doesn't produce ε) is LL(1).


Computing Cardinality of Sumsets using Convolutions and FFT

Here is a sketch of the main ideas.  Let $S,T \subseteq \mathbb{N}$ be two multisets of non-negative integers, and define $S+T$ to be the multiset

$$S+T = \{s+t \mid s \in S, t \in T\}.$$

Let $\chi_S$ represent the characteristic vector of a set $S$.  Then

$$\chi_{S+T} = \chi_S * \chi_T,$$

where $*$ is a convolution operator.

The Fourier transform $\mathcal{F}$ has the property that

$$\mathcal{F}(f*g) = \mathcal{F}(f) \times \mathcal{F}(g),$$

where $\times$ represents pointwise multiplication of functions.  Therefore,

$$\mathcal{F}(\chi_{S+T}) = \mathcal{F}(\chi_S) \times \mathcal{F}(\chi_T),$$

and in particular,

$$\chi_{S+T} = \mathcal{F}^{-1}(\mathcal{F}(\chi_S) \times \mathcal{F}(\chi_T)).$$

This gives us a method to compute $S+T$.  We can compute the characteristic vector $\chi_{S+T}$ for the multiset $S+T$ by computing $\mathcal{F}(\chi_S)$, the Fourier transform of the characteristic vector for $S$, and $\mathcal{F}(g)$; multiplying them; and then applying the inverse Fourier transform to the result.  Each of these steps can be implemented efficiently using the Fast Fourier transform.  The end result will be $\chi_{S+T}$, from which we can reconstruct $S+T$ or its cardinality.

The overall running time will be $O(n \log n)$, where $n$ is an upper bound on the largest element of $S,T$.


The first step in answering your question is determining the complexity of your algorithm. Determining the index $z_i$ takes time $\Theta(z_i)$, and so determining all of $z_1,\ldots,z_n$ takes time $\Theta(1+\cdots+n) = \Theta(n^2)$. Determining the $y_i$ from the $z_i$ likewise takes $\Theta(n^2)$, which is the running time of your algorithm.
If we are willing to spend memory $O(n)$, then we can improve the running time to $O(n)$. The idea is to notice that $p$ is a permutation, and therefore has an inverse $p^{-1}$, which can be computed easily as follows: go over $i=1,\ldots,n$, and set $p^{-1}(p(i))=i$. Given that, we can simply compute $z_i = p^{-1}(p^{-1}(i))$.
If you are really short on memory, there are algorithms for inverting a permutation in nearly linear time and small space, see for example Matthew Robertson, Inverting permutations in place. After inverting $p$, you need to square the result $p^{-1}$, which might be achievable using similar techniques (or even easier).


Time complexity for two multiplications modulo $p$

$O(2(\log n)^2$ is exactly the same thing as $O((\log n)^2)$. This follows from the definition of $O()$.


Is the language $(a^n)^mb^n$ context free?

The difficulty of trying every possible $m$ is, in fact, insurmountable. That language is not context-free.

For the sake of contradiction, assume it is context-free. Let $p$ be its pumping length. Consider the word $a^{p^2p}b^{p^2}$. I will let you take it from here.


How does a computer direct the processing of information

Given that this is an introduction, I wouldn't get too concerned about the wording. It's normal to describe things in general terms, and then go into specifics later.
In a typical computer system, everything ultimately happens because some program running in the CPU made it happen. Even with external events such as interrupts (e.g. someone typed on a keyboard, or a network packet arrived), it is software's responsibility to decide what that means.
Of course, the central processing unit isn't necessarily the only processing unit that you have to think about. Modern peripherals (e.g. DMA controllers, network adapters, USB hubs, monitors) tend to be quite "smart", and are often fully-realised computers in their own right.
For now, understand that the central processing unit is the programmable processing unit that a) directs the behaviour of the system as a whole, and b) is where general-purpose computation happens. This picture can be modified (e.g. to account for coprocessors) as you learn more.


Given a DCEL, how do you identify the unbounded face

Take any extreme vertex (say among the vertices having the minimum x-coordinate, the one that minimizes y). This vertex is  incident to two edges touching the outer face. Namely the first and the last half-edges leaving this vertex. The first one has the outer face on its right and the last one on its left.


Neural Network Normalization and de-Normalisation of data

You should definitely not be storing new max/mins after training is finished since that will mess up the values for the values that are within the old max and min.

You're network might not do very well on any of these new values anyway since they are more extreme than anything it saw during training. You should scale everything using the max/min you found during training. You could cap anything more extreme than that to be either 0 or 1.


A question regarding the Layered Architecture

"User Interface Management" does not have a standard accepted definition that I am aware of, so you'll have to work out what they mean by it based on context.


Remainder modulo 10 instead of last digit
What is the last digit of -206? It is 6 by convention. It is not 4, the least positive remainder of -206 divided by 10.
For simplicity, we will compute the value of polynomial modulo 10. We will just say "the remainder of some number" to mean the least positive remainder of that number divided by 10. (The idea and algorithm in this answer can be adapted easily if 10 is replaced by another number.)
Periodicity of the remainders of powers
The remainder of $x, x^2, x^3, x^4, \cdots$ are periodical for any integer $x$. Let $r(n)$ be remainder of $n$.

$r(x^k)=0$ if $r(x)=0$
$r(x^k)=1$ if $r(x)=1$
$r(x^k)=x$ if $r(x)=5,6$
$r(x^k)=r(x^{k+2})$ if $r(x)=9$
$r(x^k)=r(x^{k+4})$ if $r(x)=2,3,4,7,8$

$k$ goes over all positive integers if $r(x)=0,2,4,5,6,8$.
$k$ goes over all nonnegative integers if $r(x)=1,3,7,9$.
Algorithm
Because of the periodicity, we can reduce the number of multiplication to at most 4 and the number of modulo operation to 2 without increasing the number of additions.
Here is the algorithm in Python, which should speak for itself. Note for a list lst, lst[s::g] means the subsequence lst[s], lst[s+g], lst[s+2*g], ... all the way to the end.
# c = [c_0, c_1, ..., c_{n-1}]
# remainder([3,12,5], 2) is 7
def remainder(c, x):
    x = x % 10

    if x == 0:
        return c[0] % 10
    if x == 1:
        return sum(c) % 10
    if x == 5 or x == 6:
        return (c[0] + sum(c[1:]) * x) % 10
    if x == 9:
        return (sum(c[::2]) + 9 * sum(c[1::2])) % 10
    if x == 2:
        return (c[0] + 2 * sum(c[1::4]) + 4 * sum(c[2::4]) + 8 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10
    if x == 3:
        return (sum(c[::4]) + 3 * sum(c[1::4]) + 9 * sum(c[2::4]) + 7 * sum(c[3::4])) % 10
    if x == 4:
        return (c[0] + 4 * sum(c[1::2]) + 6 * sum(c[2::2])) % 10
    if x == 7:
        return (sum(c[::4]) + 7 * sum(c[1::4]) + 9 * sum(c[2::4]) + 3 * sum(c[3::4])) % 10
    if x == 8:
        return (c[0] + 8 * sum(c[1::4]) + 4 * sum(c[2::4]) + 2 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10

If remainder(c,x) will be called repeatedly for the same polynomial c, then we can precompute table d[i], where d[i] = remainder(c,i) for i from 0 to 9. Then for that polynomial c, we can return d[x%10] given x in $O(1)$ time.
We can also cache the result on the fly. This can be done nicely by returning a closure that computes each result fully at most once. That is linear time the first time and constant time later on for numbers with the same remainders.
# For example, r = remainder([3,12,5]); print(r(2)); print(r(2));
def remainder(c):
    d = [None] * 10

    def remainder_c(x):
        x = x % 10

        if x == 0:
            return d[0] if d[0] else c[0] % 10
        if x == 1:
            return d[1] if d[1] else sum(c) % 10
        if x == 5 or x == 6:
            return d[x] if d[x] else (c[0] + sum(c[1:]) * x) % 10
        if x == 9:
            return d[9] if d[9] else (sum(c[::2]) + 9 * sum(c[1::2])) % 10
        if x == 2:
            return d[2] if d[2] else (c[0] + 2 * sum(c[1::4]) + 4 * sum(c[2::4]) + 8 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10
        if x == 3:
            return d[3] if d[3] else (sum(c[::4]) + 3 * sum(c[1::4]) + 9 * sum(c[2::4]) + 7 * sum(c[3::4])) % 10
        if x == 4:
            return d[4] if d[4] else (c[0] + 4 * sum(c[1::2]) + 6 * sum(c[2::2])) % 10
        if x == 7:
            return d[7] if d[7] else (sum(c[::4]) + 7 * sum(c[1::4]) + 9 * sum(c[2::4]) + 3 * sum(c[3::4])) % 10
        if x == 8:
            return d[8] if d[8] else (c[0] + 8 * sum(c[1::4]) + 4 * sum(c[2::4]) + 2 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10

    return remainder_c

There are further micro-tuning for various special situations.
If you are interested in parallel algorithm, you can check Estrin's scheme that can speed up the computation.


Decreasing a digraph's edge-weights while keeping net weights of edges at each vertex constant

The second objective is just a simple circulation problem http://en.wikipedia.org/wiki/Circulation_problem
as the maximum circulation gives the highest reduction in weight. This problem is basically equivalent to max flow for which efficient algorithms are well known.

Not so sure about trading of the first and second objective. You might achieve something like this by modelling it as a min concave-cost network flow problem with capacities, e.g. by some cost function that is nearly flat at arc saturation, such that it favours saturating arcs once they are close, but this is NP-hard:
http://link.springer.com/article/10.1007/BF02283688

Maybe there is a more efficient way depending on what you are trying to achieve,  but the constraint that net edge weights remain the same indicate that you are looking for some network flow type algorithm.

Do you have an application for this in mind?


I suspect that the problem may lie in your title.

There's a whole lot of real-world variety imaginable in memory architectures, and your book will describe them in the abstract. Importantly, in the real world the particular combination of segmentation and virtual addresses is not used. Intel's x86 architecture supports it, but most Operating Systems don't bother and just set all segments to be identical.

This question therefore does assume something non-standard, which means there needs to be some specification of how the hypothetical mechanism works. Importantly, does segmentation happen before or after virtual address translation?

In the model where segmentation checks happen first, 0x0FEC is not in the code segment. The top bits suggest it is, but the code segment is only 3686 bytes, not 4077 bytes.

Since the virtual address does not lie in any segment, using it would fail even before a virtual-to-physical translation happens.

Now in the model where segment bounds are checked later, you'd first create a physical address, which would use the 12K base address and the 4076 offset. This produces an physical address of almost 16K, past the 15.6K end of the code segment.


Does a collision occur if two packets are sent at the same time in Slotted AHOLA?

A station is not allowed to send two packets at the same time.  Each station is only allowed to send one packet at a time.  If the station has multiple packets it wants to send, it can start sending one of them but it must queue the others and wait to send them later.

The protocol does not impose any requirements on how long a station must wait to send the other packets.  Suppose Alice has two packets to send.  Alice is required wait to send the second packet until some later point after she has finished sending the first packet.  Beyond that, it's up to her exactly when he tries to send it.  The protocol doesn't specify anything in particular.   Some stations might try to send the second packet immediately after they finish sending the first packet.  Other stations might wait a while (for whatever reason) in between.  There are no guarantees and no requirements.


Can the "divide" step in a merge sort be avoided?

The confusion arises from difference between the conceptual description of the algorithm, and its implementation.

Logically merge sort is described as splitting up the array into smaller arrays, and then merging them back together. However, "splitting the array" doesn't imply "creating an entirely new array in memory", or anything like that - it could be implemented in code as

/*
 * Note: array is now split into  [0..n) and [n..N)
 */

i.e. no actual work takes place, and the "splitting" is purely conceptual. So what you suggest certainly does work, but logically you're still "splitting" the arrays  - you just don't need any work from the computer to do so :-)


What Are the Ideas Behind Variations of the Coin Change Problem?

OP here, answering my own question for the greater good of mankind.

Let dp[i][j] denote the solution to the [i,j]-th subproblem; that is, dp[i][j] is the number of ways to make change for the amount i, using coins j through n.

Coin Change Problem with Repetition

dp[i - xs[j - 1]][j] + // 1
    dp[i][j - 1]       // 2

Use coin j, and since there is no constraint on the denominations, solve the smaller subproblem using the same denomination.
Don't use coin j.

Coin Change Problem without Repetition

dp[i - xs[j - 1]][j - 1] + // 1
    dp[i][j - 1]           // 2

Use coin j, and since we used coin j for this subproblem, we can't use it for any other.
Don't use coin j.


Does a weighted Breadth First search have "memory" when moving to the next vertex?

How about transforming your original graph to a graph with dummy nodes and just use regular BFS on it?

The idea is: if you have an edge with weight $k$ between $A$ and $B$, remove it. Then add a path between $A$ and $B$ with $k-1$ nodes in between, where all the edges have unit weight.

Now you can use regular BFS on your graph and it will reach the nodes in the same order as it would in the weighted version, without you having to transform the algorithm.

Ps. BFS always spreads out evenly, layer for layer like ripples in a pond. So if the next nodes to be added are A, B and C it will always add those nodes, but in which order does not matter- as long as the edges are unweighted.


Finally I've found some decriptions of these algorithms here.


Clock page replacement policy vs LRU page replacement policy, is Clock more efficient?

If I understand correctly I think you are confusing the cache and the cache hit data structure. The structure isn't used to access the page, its used to store the hit count. For LRU, the OS needs to examine the hit count for every page in the cache memory to find the least recently used. When a page is hit, it is moved up in the list to prevent it from being evicted. I don't see how this would translate to a hash map.

The clock algorithm, only keeps track of a set of the most recently used pages (typically since the time since a new page was requested). The clock algorithm acts as an approximation of LRU without the maintenance of the linked list.


Why does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?

This mostly comes down to what makes an interesting problem, and what can be easily analyzed.

The restriction of visiting each vertex once is common in these sorts of problems. A traversal that visits each vertex no more than once is called a "path", and these are well-studied in graph theory, so there are quite a few existing theorems based on them.

The version where you can visit vertices more than once can be readily reduced to the version where you can't (and in poly-time): for every pair of nodes, calculate the shortest distance between them, remove the edge directly between them (if any), and add an edge between them with weight equal to that shortest distance. (In your example graph, this would replace the 100 edge with a 2.)

So your modified version both doesn't play into existing graph theory problems, and can be easily reduced to the standard one. It's easier just to analyze the standard one instead.

TL;DR: It's because of precedent in graph analysis. See also the Hamiltonian cycle problem, which is very closely related, and the longest path, which is a bit more distantly related.


They logically exist, you can not un-invent them. Even if no one ever made one, they would still exist in your mind.
If is easier to say “open door if I want to go through door or you want to go through door” than to say “open door if I don't want to go through door nand you don't want to go through door”
An alternate question — Why do we build devices with just one gate? i.e. nand or nor?
We do this because it makes the electronics simpler, if all the devices are the some, as we only have to implement one type of gate. This is about simplicity of the device, not of the logic (as this could be a bit more complex). This logical complexity could push the size up, but the symmetry of all gates being the same pushes the size down. Also a lot of the logical complexity can cancel out.
A similar question — Why do we have multiply in maths. When we can do everything with addition?

Why do we have addition when we can just use increment: 3+4 = 3+1+1+1+1
Why do we have multiplication when we can use addition: 3×4 = 3+3+3+3
Why do we have exponentiation when we can use multiplication 3⁴ = 3×3×3×3

If you were to continue to look inside the computer, then you will see that it is,some what, like this:

transistors → nand or or
nand or nor → all logic gates
logic gates → addition
logic gates → flip flops
flip flops → shift registers → multiply by 2
multiply by 2 & addition → multiplication
…

Why do we have steel, when you can just have iron, carbon, cobalt … ?


See this answer - it's an example of a contradictory set of clauses where we cannot derive a contradiction without renaming variables. Note that it's not sufficient to only rename variables after the conversion to CNF, we have to rename variables to be distinct before every application of the resolution rule. You can view it as follows: A variable appearing in two distinct clauses has different meaning in each of them as they're implicitly universally quantified. If we don't rename the variable in one of the clauses, we make a false assumption that the variable means the same in both clauses.
By using MGU, we derive the most general clause in a resolution step. If we use any unifier that is more specialized than their MGU, the resulting clause is weaker. This means, that we didn't infer all the knowledge we could, and we can miss a derivation of an empty clause even if it exists. For example:
\begin{array}{c}
P(x,y) \lor Q(y) \\
\lnot Q(d) \\
\lnot P(c,d)
\end{array}
If we make a resolvent from the first two clauses using MGU which sends $y\to d$, we get $P(x,d)$ and we can proceed with the third clause. If we take a weaker unifier, like one that also sends $x\to d$, we get $P(d,d)$ and we're not able to make a resolvent with the third clause. This means the method is no longer complete.


Is the complement of this decision problem in $P$?

Careful how you come up with a complement. The original problem asks to satisfy the following, given M:
$$\exists p,q: ((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$
As you say, the answer is always NO.
The complement of the problem should by definition have the opposite answer (YES) for ever $M$. To see why that's the case, negate the original problem (carefully):
$$\neg\exists p,q: ((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$
Distributing through the $\exists$ gives:
$$\forall p,q: \neg((p\text{ and } q \text{ are prime})\land \neg(p\mid M)\land \neg(q\mid M) \land (pq=M))$$
And distributing again makes this pretty trivial:
$$\forall p,q: ((p\text{ or } q \text{ is not prime})\lor (p\mid M)\lor (q\mid M) \lor (pq\ne M))$$
So the complement is really asking: Given $M$, is it true that every pair of numbers $p$ and $q$ either has a non-prime or a divisor of $M$ or they don't multiply to $M$? It's a bit strange to claim this, but it's always true.


Given a $\overline{SAT}$ instance $\psi$ with $m$ clauses, let $\phi$ be the formula formed by adding to each clause a new variable $x$ (the same for all clauses), and a new clause $\bar{x}$. If $\psi$ is satisfiable then $\phi$ is satisfiable, whereas if $\psi$ is unsatisfiable then the maximum number of clauses that can be satisfied is $m$.


A nice question!

As the OP has pointed out, it is enough to show the following inequality for any tree $T$ of $n\gt0$ nodes, where for any node $x$, $l(x)$ is the number of nodes in the left subtree of $x$ and $r(x)$ is the number of nodes in the right subtree of $x$.

$$\sum_{x\in V(T)}\min(l(x), r(x)) \leq n \log n$$

Proof by mathematical induction.

base case when $n=1$. Both side is 0.
Suppose it is true when the number of nodes in the tree is smaller than $n$. Let us consider a tree $T$ with $n>1$ node. Let the left subtree $T_l$ of the root node has $p$ node and the right subtree $T_r$ of the root node has $n-1-p$ node. There are two cases.

$p=0$ or $p=n-1$ is easy.
$p\neq0$ and $p\neq n-1$. (This case is only possible when $n\ge3$.) WLOG assume $p\le n-1-p$; otherwise we can switch the left subtree and the right subtree.

$$\begin{aligned}
&\sum_{x\in V(T)}\min(l(x), r(x)) \\
&= \min(p, n-1-p) + \sum_{x\in V(T_l)}\min(l(x), r(x))+\sum_{x\in V(T_r)}\min(l(x), r(x))\\
&\leq p + p\log p +(n-1-p)\log(n-1-p)\\
&= p + p\log p +p\log(n-1-p) + (n-1-2p)\log(n-1-p)\\
&= p + p\log (p(n-1-p)) + (n-1-2p)\log n\\
&\le p + p\log \left((\frac{n-1}2)^2\right) + (n-1-2p)\log n\\
&\le p + 2p\log \left(\frac{n}2\right) + (n-1-2p)\log n\\
&= (1- 2\log2)p + (n-1)\log n\\
&\le n\log n
\end{aligned}$$

Proof is done. Note that we have actually proved a tighter upper bound, $\frac1{2}n \log_2 n$.


Given two DFAs $A,B$, it is decidable (even efficient!) whether $L(A) = L(B)$: use the product construction to get a DFA for $L(A) \triangle L(B)$, and now use reachability analysis.

In order to determine whether $A$ is a minimal DFA, one can just try all DFAs $B$ with less states, looking for one satisfying $L(A) = L(B)$. Alternatively, there are algorithms for minimizing DFAs which are vastly more efficient than that approach. They are even more efficient if all you want to know is whether the DFA is minimal or not.


Is the equality of two DFAs a decidable problem?

In order to decide whether the languages generated by two DFAs $A_1,A_2$ by the same, construct a DFA $A_\Delta$ for the symmetric difference $L(A_1) \Delta L(A_2) := (L(A_1) \setminus L(A_2)) \cup (L(A_2) \setminus L(A_1))$, and check whether $L(A_\Delta) = \emptyset$.

Here are some more details. You can construct $A_\Delta$ using the product construction: construct a product automaton, and use $(F_1 \times \overline{F_2}) \cup (\overline{F_1} \times F_2)$ as the set of accepting states.

In order to check whether $L(A_\Delta)$ is empty or not, it suffices to check whether some accepting state is reachable from the initial state, and this can be done using BFS/DFS.


Why is this youtuber applying comparing two functions with O(n^2), by applying a contant to one of the functions?

Look up the definition of big-O. It states that $f=O(g)\iff \exists c>0:\exists n_0\in\mathbb{N}:\forall n>n_0:f(n)\le cg(n)$


Showing party invitation problem is np-complete

Simple party invitation problem. Suppose there are $m$ housemates decide to throw a party. Each housemate $i$ specifies a group of people $P_i$ who could be invited, $1\le i\le m$. Is it possible to invite at most $k$ people to the party such that at least one person in $P_i$ for each $i$ is invited?

It is enough to show the simple party invitation problem is still NP-Complete, which is, in fact, true.

Let's try to do some pattern matching between the simple party invitation problem and the set cover decision problem.

In set cover, we are given many sets, and we want to find some sets that satisfy some constraints. In simple party invitation, we are given many persons, and we want to find some persons that satisfy some constraints. Hence it seems that a set among the given sets should correspond to a person that could be invited. (Yes, a set corresponds to a person, which might be counterintuitive and which might be why this problem is not immediate to solve.)

What about the constraints? In set cover, we want to find some sets the union of which will cover all elements. In simple party invitation, we want to find some persons to invite so that every lists of people will be covered, that is, there is at least one person invited in each list. It looks like an element in set cover corresponds to a list of persons in simple party invitation. (Again, an element corresponds to a list, which might not be straightforward and which might be why this problem is not immediate to solve.) The fact that an element is a member of a given set in set cover corresponds to the fact a list of persons contains a given person.

You take it from here.

You could also reduce the hitting set problem to the simple party invitation problem, which might be clearer intuitively if you are familiar with the former.

For the pattern matching part, I am following the great teaching style in this answer of Yuval.


Why the 127 encodings of ASCII needed to be extended to 256?

ASCII has 128 characters. Many countries had similar encodings for 128 characters. That is all history. Nobody uses ASCII anymore. There was a phase with lots of different encodings for more than 128 characters, some with 256 (Mac Roman and Windows 1152 were quite popular) and some like the Chinese GB with thousands of characters.

Nowadays people mostly use Unicode, with a bit over a million code points, which can be further combined to produce more characters. There are plenty of unused code points which can be assigned values in the future, and that happens all the time.

Please note that for most people English is a foreign language. And it would be “naïve” to think that ASCII let’s you write all English text.


This problem is indeed $NP-complete$ as you have suspected. To see this, we will show a reduction from $SubsetSum$.
The reduction
Let $A,s$ be an instance of $SubsetSum$, where $|A|=n$. We will define $L$ as all the numbers in $A$, in addition to another $n$ zeros. For example, if $A= 4, 5, 8$ then $L=4,5,8,0,0,0$.
Now, we define $M$ to be with $2n$ values, such that we have $n$ ones and $n$ zeros.
The target value will be $s$
Proof
Such a perfect matching defines us a subset $A'\in A$, that $a\in A'$ iff $1$ is matched with $a$. Since we have $n$ values in $A$, and we have $n$ ones and $n$ zeros in $M$, then each pair of $(0,1)$ in $M$ can be assigned to every pair $(a, 0)$ where $a\in A$, and thus any $a\in A$ can be matched with either $0$ or $1$, contributing to the total sum either $a$ or $0$. Therefore, there is a perfect match if and only if there is a subset with that sum (as the value of the matching is a sum of the subset $A'$).


This blog post summarises the situation well my opinion, but let me go through some of your concerns:

Reducible is NOT equivalent to acyclic: consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with a loop from $z$ to $y$. Then there is an SCC $\{y,z\}$ so it is not acyclic. But it is reducible because the SCC $\{y,z\}$ has a single entry point y. Notice how this corresponds to a program with a while/for loop. On the other hand, if you consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with again a loop $z\rightarrow y$ but also a forward jump $x\rightarrow z$. Not this is not reducible anymore because the SCC $\{y,z\}$ has two entry points: $y$ can be entered from $x$, but $z$ can also be entered from $x$. This intuitively corresponds to a program like that:

x: if <some condition> goto z
y: do { <instruction>
z: }while(<cond condition}
w: end

Notice how there is no way to jump to $z$ without a goto, this is the point of reducibility and it corresponds to well-structured code without goto.

Concerning the back edges, if you take the counter-example for above, notice that there are two different ways to explore this tree in a DFS:

from $x$, explore $z$ then $y$ and $w$: in this case the edge $z\rightarrow y$ is part of the spanning tree built by the DFS. But $z$ does not dominate $y$ because the path $x\rightarrow y$ does not go through $z$.
from $x$, explore $y$ then $z$ then $w$: in this case the edge $y\rightarrow z$ is part of the spanning tree built by the DFS. But $y$ does not dominate $z$ because the path $x\rightarrow z$ does not go through $y$.

Maybe the source of your confusion is that domination is related to the initial vertex $x$, and not to the DFS. Recall that a vertex $y$ dominates a vertex $z$ if every path from the initial vertex to $z$ goes through $y$.


It is quasi-polynomial time. See it under examples http://en.wikipedia.org/wiki/Time_complexity


Why does ε-greedy $Q$-learning not oscillate?

The assumptions for Q-learning's convergence proof require that:

  [...] all state-action pairs be visited infinitely often

So the convergence is understood in a mathematical sense - the Q-function converges to its fixed-point as the number of steps approaches infinity.

In practice, even after your Q-function will be good enough to induce an optimal policy, you will observe "unnecessary" updates each time a non-greedy action is chosen. To avoid that, you can set the learning rate to 0 after the acceptable quality of the solution is achieved.

Also, your intuition about modifying the ϵ parameter, in case of ϵ-greedy policy, seems right. Setting ϵ to 0 will have practically the same effect as setting the learning rate to 0 in the situation described above - in case of a non-stochastic environment.


Guaranteed existence of a blocking set in the accept definition of Stellar

What is guaranteed is that if a quorum of an intact nodes accepts a statement s, then eventually every intact node v will find itself v-blocked by a set of nodes that has accepted s, i.e. "accept s" cascades throughout all intact nodes until all have accepted and then confirmed s. This is called the cascade theorem in the paper "Fast and secure global payments with Stellar". You can find a brief justification of this theorem at the end of section 3.1.2. There is also a formal proof in Isabelle/HOL here: https://github.com/stellar/scp-proofs. Finally it is also guaranteed that if an intact node is v-blocked by "accept s", then at least one intact node saw a quorum voting for s.


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


diagonal lemma and the negation function

The way you've stated the diagonal lemma is odd (and I've not seen it put that way before). The standard phrasing is:

  For every formula $\varphi(x)$, there is some sentence $\sigma$ such that $$PA\vdash \sigma\leftrightarrow\varphi(\ulcorner\sigma\urcorner).$$

Note that there is no $f$ here! Rather, we're talking about properties: intuitively, the conclusion is that PA proves "$\sigma$ is true iff $\sigma$ has property $\varphi$." This makes things a little easier to see, in my opinion: in order to implement your argument we'd want to let $\varphi$ be the formula "is false."

So what your argument lets us conclude is that no such $\varphi$ exists - that is, Tarski's theorem.

Now let's shift to the language of the OP, and see how the version of the diagonal lemma that you state emerges.

Suppose $f$ is a computable function from (codes for) sentences to $\{0,1\}$ (treating $0$ as false and $1$ as true). Then $f$ is representable in PA, say by $\psi_f$. Let $\varphi_f$ be the formula $$\psi_f(\ulcorner\sigma\urcorner)=1.$$ Then applying the diagonal lemma as stated above with $\varphi=\varphi_f$ we get some $\sigma$ such that $$PA\vdash\sigma\leftrightarrow \psi_f(\ulcorner\sigma\urcorner)=1$$ (which could suggestively be written in a minor abuse of notation as "$PA\vdash\sigma\leftrightarrow f(\ulcorner\sigma\urcorner)$" - conflating $0/1$ with true/false and conflating $f$ with its representing formula).

The argument you gives shows that the map $n$ sending a sentence to the truth value of its negation is not computable; more snappily, the set of true sentences of arithmetic is not computable. (Note that this is actually weaker than the conclusion gotten above, since every computable function is definable.)


prove that there is a complete language in $L \cup \{A_{TM}\}$

We will show that $A_{TM}$ is complete for your class.

In order to show that, we need to show that for every language $A\in L\cup \{A_{TM}\}$, it holds that $A\le_L A_{TM}$.

First, if $A=A_{TM}$, then the trivial reduction suffices. That is, a reduction that given input $x$, return $x$. Clearly $x\in A_{TM}\iff x\in A_{TM}$.

Now, if $A\in L$, we need to work slightly harder. We need to show that $A\le_L A_{TM}$. In order to do that, we construct a reduction from $A$ to $A_{TM}$, as follows: let $M$ be a deterministic TM that decides $A$ in logspace (why does there exist such a machine?).

Now, the reduction works as follows: given input $x$, the reduction uses $M$ to check whether $x\in A$. If $x\in A$, the reduction outputs $\langle\epsilon, T_1\rangle$, where $T_1$ is a TM that accepts every input immediately. If $x\notin A$ the reduction outputs $\langle\epsilon, T_2\rangle$, where $T_2$ is a TM that rejects every input immediately. Note that $T_1,T_2$ are fixed, i.e. they are hard-coded in the reduction.

Try to prove that this reduction is correct, and that it is indeed in logspace.


Testing whether a tetrahedron lies inside a Polyhedron

I recently found one solution to this problem in a paper 'Robust inside-outside segmentation using generalized winding numbers' by Alec Jacobson et.al., here. It solves the problem of locating if a point is inside(or outside) an arbitrary(one with self-intersections, non-manifold, open-surfaces etc.) polygonal mesh using the notion of generalized winding number.

Problem can be solved if I compute the generalized winding number of the centroid of $t$ against the surface of $p$.