Are all Integer Linear Programming problems NP-Hard?

If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard.
It is perfectly possible for other specific classes of instances to be solvable in polynomial time.

Consider for example the problem of finding a 3-coloration of a graph. It is a well-known NP-Hard problem. Now imagine that its instances are restricted to graphs that are, for example, trees. Clearly you can easily find a 3-coloration of a tree in polynomial time (indeed you can also find a 2-coloration).

Consider decision problems for a second.
A method of proving the hardness of a decision problem $P$ is devising a polynomial (Karp) reduction from another problem $Q$ that is known to be NP-Hard.
In this reduction you show that there exists a function $f$ that maps each instance $q$ of the problem $Q$ to an instance of the problem $P$ such that:
$q$ is a yes instance for $Q \iff f(q)$ is a yes instance for $P$.
This implies that solving $f(q)$ must be "at least as difficult" as solving $q$ itself.

Notice how it's not required for the image of $f$ to be equal to the set of the instances of $P$ . Therefore it's perfectly possibile for problem $P$ restricted to some subset of instances to not be hard.

To return to your original question:

The assignment problem can be solved in polynomial time, i.e., a solution to each instance of the assignment problem can be computed in polynomial time.
ILP is NP-Hard: in general it might be hard to compute a solution to an ILP problem, i.e. there are instances of ILP that are hard.
Some specific instances of ILP can be solved in polynomial time.


Convert ambiguous grammar to unambiguous and SLR(1)

Let's start where you probably started, with the classic expression grammar:

$$\begin{align}E&\to T\mid E + T\mid E - T\\
T&\to F\mid T * F\mid T / F\\
F&\to ( E )\mid x\\
\end{align}$$

and then we add the "fused" productions:

$$\begin{align}E&\to E + T * F\mid E - T * F\\
\end{align}$$

That grammar has a conflict because of the ambiguity:

$$\begin{align}E&\to E+T*F\\E&\to E+T \to E+T*F\end{align}$$
(and similarly for the $-$ operator).

So how to get rid of the ambiguity? Clearly, we don't want $E\to E+T$ to match $E+T*F$. So we need to define $$T' = T \setminus T * F$$ in order to be able to restrict the $E$ production to $E\to E + T'$.

Since the set difference operator is not valid in a CFG, we need to write the definition out the long way:

$$\begin{align}E\to&\;T\mid E + T'\mid E - T'\;\mid\\
&\;E + T * F\mid E - T * F\\
T'\to&\;F\mid T / F\\
T\to&\;T'\mid T * F\\
F\to&\;( E )\mid x\\
\end{align}$$


General question on approach to showing sample size required is $\Omega(\cdot)$

There is a difference between the two questions. Let $p_n$ be the number of heads in $n$ trials divided by $n$. We know that for large $n$, $p_n$ is very close to $p$; qualitatively this is the law of large numbers, and quantitatively this is the central limit theorem. This phenomenon is known as concentration. This is what you use to give an upper bound on $n$. In contrast, to give a lower bound on $n$ you need to show anti-concentration: that for small $n$, $p_n$ has a reasonable probability of being somewhat far from $p$. The techniques for showing anti-concentration are often more delicate.

In your particular example, concentration can be shown using classical inequalities such as Chernoff's inequality. For anti-concentration you can use the Paley–Zygmund inequality, but you won't necessarily get good bounds. To get nearly tight bounds you can use a general-purpose double-sided inequality such as Berry–Esseen, or a specialized one à la de Moivre–Laplace.


Bitvector approach is correct solution.

Problem statement tells that you are given $n$ different integers so there is no need to count multiple occurrence of number in sequence. This also allows you to cut down needed storage to $\lceil{\frac{750}{8}}\rceil = 94$ bytes.

Now the algorithm:

Input: $A$ - array of unique integers, 1 based

Output: None - we update given array

B[750] = 0; bitvector of len 750 initially set to 0
for each i in A
    B[i] = 1
k = 1
for j = 1 to 750
    if B[j]
        A[k] = j
        k = k+1

This obviously runs in $O(n)$ and uses $O(1)$ memory.

This can run in linear time because it isn't compare based sorting. As you correctly pointed out every compare based sorting must take at least $O(n \log n)$ steps.

This approach is special case of bucket sorting but we used information about problem statement (namely: unique integers and range of those integers)


Capacity of a discrete memoryless channel

This answer assumes that $Y = X + Z \bmod 2I$, which seems more reasonable than the current $Y = X + Z \bmod I$, which would mean that $X$ is effectively chosen from an alphabet of size $I$ rather than $2I$.

The capacity is $\log I$.

For the upper bound,
$$
I(X;Y) = H(Y) - H(Y|X) = H(Y) - H(Z) = H(Y) - 1 \leq \log(2I) - 1 = \log I.
$$

For the lower bound, if $X$ is chosen uniformly among the $I$ values $1,3,\ldots,2I-1$ then you can recover $X$ from $Y$ (without any error!), and so $I(X;Y) = H(X) = \log I$.


Prove the following language is in L (LogSpace)

A Boolean formula is a circuit whose graph is a tree (each node has a single parent). Perform an in-order pass on the tree while remembering the current node and the last value.

When at a $\lor$ gate with a previous value $b$: If $b = 0$ leave the value the same and go to the node's parent. If $b = 1$ check the other (right) son. Same with $\land$ gate, and $\lnot$ gates are easier (check if $b = 0$). Accept $(C, x)$ if the value computed by $C$ (using the in-order search) is $1$.

Saving the current node takes $\log n$ bits, the current value takes $1$ bit and computing the parent also takes $\log n$. Overall there is a TM that uses $O(\log n)$ space that decides $A$, so $A \in L$.


Information on Tavori and Dreizin ranged hash function?

Ami Tavory, Vladimir Dreizin (IBM), and Benjamin Kosnik (Red Hat) authored the "Policy-Based Data Structures" library. Ideas developed there were later used in the GNU implementation of the C++ standard library.
Link-only answers are typically discouraged, but let me post the link here anyway because it is not discoverable with Google in a simple way:
https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/
In particular, range hashing approach is described here:
https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/hash_based_containers.html


You can start by considering this related problem:

$$L'=\{w\#x\#n\,|\,\text{all states are reached when running }M_w\text{ on }x\text{ within $|n|$ steps}\}.$$

Argue that $L'$ is decidable. Then, noting that

$$L=\{w\#x\,|\,\exists n.\ w\#x\#n \in L'\}.$$

should give you an idea about how to proceed.


Artificial Intelligence: Condition for BFS being optimal

¡Nice question really!

The book is right and it just suffices for the path cost to be a nondecreasing function of the depth of the node ---though an additional note should be posted, see below. This directly implies that it is not necessary for nodes in the same level to have the same cost. Truth, however, is that it is hard to find such an example because the most obvious one consists just of considering all grounded actions to have the same cost.

Thus, let me try to start with the first statement (that it just suffices for the path cost to be a nondecreasing function of the depth of the node) with a theoretical example. Let $c(n,n')$ denote the cost of traversing the edge from node $n$ to node $n'$ and let us define it as:

$$
c(n,n')=2^{g^*(s,n)}
$$

where $g^*(s,n)$ is the minimum number of actions required to reach node $n$ from the start node $s$. I am certainly defining the cost of the edge as a function of the depth of the source node but it seems to be that this is absolutely okay with the statement in the book. Think of this as an attractive force exercised from the start state $s$ so that the farer you get, the more costly it is to progress. This function is clearly non-decreasing as it progresses as follows: 1, 2, 4, 8, ..., the total cost paths progressing as: 1, 3, 7, 15, ...

Now, let me show that Breadth First Search would certainly find an optimal solution. I will make it by induction:

Base case: the queue is seeded with the start state $s$. In the first iteration of BFS it is extracted from the queue and its children are generated, all of them with cost $2^0=1$. These nodes have been certainly reached through an optimal path so this satisfies the base case.

Induction step: let us assume that all nodes of depth $(d-1)$ have been already generated through optimal paths with a path cost $\sum\limits_{i=0}^{d-2}2^i=2^{d-1}-1$. In the induction step all nodes generated at depth $(d-1)$ are expanded to generate nodes at depth $d$ from the start state $s$. Obviously, all these nodes are generated through optimal paths as well since their cost corresponds to paths of minimum length from the start state (in other words, would there be a shorter path in terms of length instead of cost, it would have been discovered in a previous layer of the search tree traversed by BFS with a lower cost).

It seems to me that you would agree with this but it might not satisfy you because all nodes in the same level would have exactly the same path cost (and nodes at depth $d$ would have a total cost equal to $\sum\limits_{i=0}^{d-1}=2^d-1$), but the previous proof was necessary in order to consider the following case now:

Let us re-define the cost function as:

$$
c(n,n')=\left\{\begin{array}{l}
2^{g^*(s,n)}, \mbox{in some cases, whichever}\\
2^{g^*(s,n)}+\delta, \mbox{otherwise}\end{array}\right.
$$

where $delta$ is just a small number, say $\frac{1}{2}$, such that it is smaller than the smallest of all costs $2^0=1$. Now you have a lot of different ways to get different path costs of nodes lying at the same level. In this particular case, the path cost of a node at depth $d$ ranges in the interval $[2^{d+1}-1, 2^{d+1}+\delta\times d-1]$.

However, the optimality condition of BFS still applies because the maximum difference ($\delta\times d$) is not enough to shift any node at depth $d$ after nodes that lie at depth $(d+1)$ in the queue the reason being that the path cost of those nodes ranges in the interval $[2^{d+2}-1, 2^{d+2}+\delta(d+1)-1]$. For a value of $\delta$ small enough nodes with different costs (even if they lie at the same depth) are found through optimal paths. However, note that I am assuming here $\delta$ to be small enough. If it is not, then BFS could be easily fooled and sub-optimal paths would be easily found by BFS.

Nice question, really! Hope this contributes somehow,


Mathematics Courses for Computer Scientists

The Matrix in Computer Science (Brown)
http://cs.brown.edu/courses/cs053/current/lectures.htm

Coding the Matrix (Coursera)
https://www.coursera.org/course/matrix

Both are by Philip Klein
http://cs.brown.edu/~pnk/


Is finite abelian group isomorphism in Log Space?

The finite abelian group-isomorphism when groups are given in the form of multiplication tables known to be in $L$ and in $TC^0 (FOLL)$. For more detail you can see the thesis of the Dr. Fabian.

PhD  Thesis of Dr. Fabian ( see page number 180 and 185 )


Test if there are two subsets which cover a set

There is an $O(n2^n)$ algorithm which is better than the trivial $O(nm^2)$ algorithm when $m$ is really big. Let $f$ be the characteristic vector of $\mathcal{X}$, of length $2^n$; $f$ can be calculated in time $O(n2^n)$. The number of solutions $U,V$ is exactly equal to
$$ f' \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f. $$
Indeed, if $\chi_U$ is the indicator vector of $U$ then
$$ \chi'_U \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} \chi_V = \begin{cases} 1 & \text{if } U \cup V = S, \\ 0 & \text{otherwise}. \end{cases}$$
The vector $g = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f$ can be computed in time $O(n2^n)$ using an FFT-like algorithm, and then the inner product $f'g$ can be calculated in time $O(2^n)$. I'm lying a bit here: the numbers involved might get big. However, if we replace addition with OR, we still find out whether there are any solutions, and all the numbers are in $\{0,1\}$ now.

The function $g$ is in fact related the upward closure of $f$, which is given by $h_U = g_{\overline{U}}$. The FFT algorithm uses the basic operation $h_{U \cup \{i\}} = h_U \lor h_{U \cup \{i\}}$. This makes it clear why $\bigvee_U f_U g_U = \bigvee_U f_U h_{\overline{U}}$ is what we want.


A turing machine has a representation as a string. more specifically, you write the transition function. to do this, simply think of it as one big table, having in each row two states a letter, and a head transition (L for left or R for right).

Now, encode every entry of the transition function table, and space between them with 3 zeroes (its like a "magic number" so we would know where entries start and end). every entry will contain two numbers - each number representing one state, another bit for the letter and another bit for the head transition (say 1 would be R and 0 is L).

between the two numbers and the other bits put 2 more zeroes, just so you would be able to distinguish between them.

Now, to enumerate on all of the turing machines, just enumerate on all strings and check if they are in the format described above


Are counting problems the same as problems involving listing all possible combinations?

First of all note it is an NP complete problem if you are searching for a specific subset of denominations that sums to a particular integer.

You could solve this problem by brute-force simply generating all subsets of coins checking each time that the set adds up to the target. Time complexity of this algorithm is terrible, though there are pseudo-polynomial solutions too.

A counting problem which lists the number possible outputs doesn't have to be solved using recursive algorithm though a recursive algorithm in particular for generating subsets is much more shorter, intuitive, and readable.

Any recursive algorithm may be rewritten in a nonrecursive form. Similarly, there is nothing special with dynamic programming, it is just a way to solve a problem. But not all counting problems (or any problem) are solved or have to be solved using DP.

Also, once you generated a list of sequences or sets then of course you could count, in other words your listing solves corresponding counting problem. However, if you are interested just in the number of elements/sequences/sets then you don't have to list/generate sets. For example given $n$ you could compute that the total number of binary strings of length is $2^n$ without generating these strings. Computing $2^n$ is easier than listing all strings. Similarly, if you are interested in the number of subsets of size $m$ of a set of size $n$, then that value is $\binom{n}{m}$ which may be calculated using the Stirling's approximation. But listing all possible subsets is harder.

Thus counting problems ARE NOT always same as problems involving listing all possible combinations.


Algorithm to add sum of every possible xor-sum sub-array

After the first couple of lines the array $A$ contains the XOR of every prefix of the input numbers in binary. So a $1$ bit at position $k$ in $A[j]$ tells us that there are an odd number of input numbers in the range $0...j$ with $1$ at their position $k= \log p$.

For every $i,j$ s.t. $i \leq j$, if the $k$th bit of $A[i-1]$ is $1$ and the same bit in $A[j]$ is $0$ then there are an odd number of $1$s at bit-position $k$ of the input numbers in the range $i...j$. The same conclusion would be true if the $k$th bit was $0$ for $A[i-1]$ and $1$ for $A[j]$. Please observe that these are the only two situations where the number of ones at position $k$ is odd in the range $i...j$.

Therefore the number of pairs $(A^k[i-1],A^k[j])=(0,1)$ or $(1,0)$ is equal to the number of ranges in the input such that their XOR at position $k$ is $1$. Every such range contributes $p=2^k$ to the total sum. In that code, $c$ is the number of ones and $(N-c)$ is the number of zeros at position $k = \log p$. The "$+1$" is to count for the ranges of length one and a $1$ in their $k$th position.


Is there a way to calculate the number of all the languages over an alphabet?

It's uncountable infinite.

There are the languages $\{ a^0 \}$,  $\{ a^1 \}$,  $\{ a^2 \}$,  $\{ a^3 \}$ etc., which is already countable infinite.

But the powerset of the integers is uncountable infinite. So for every set S of integers, take the language $\{ a^k: k \in S \}$ and you have an uncountable infinite set.

(The number of languages that can be defined by any algorithm is only countable infinite, so most of these uncountable many languages cannot be described in any way).


Book containing many important CS papers

If I had to bet, I'd say:

Great Papers in Computer Science
Author: Laplante, Phillip A.
Publisher: West Publishing Co.

(this one or an older edition).

Contents

Algorithms and Data Structures

1.1 The Complexity of Theorem Proving Procedures (Stephen A. Cook)
1.2 On the Conceptual Complexity of Algorithms (J. Hartmanis, R. E. Stearns)
1.3 Quicksort (C. A. R. Hoare)
1.4 Finite Automata and Their Decision Problems (M. O. Rabin, D. Scott)

Programming Languages

2.1 The FORTRAN Automatic Coding System (J. W. Backus, et al.)
2.2 An Axiomatic Basis for Computer Programming (C. A. R. Hoare)
2.3 An Axiomatic Definition of the Programming Language Pascal (C. A. R. Hoare, N. Wirth)
2.4 The Contour Model of Block Structured Processes (John B. Johnston)
2.5 On the Translation of Languages from Left to Right (Donald E. Knuth)
2.6 Revised Report on the Algorithmic Language ALGOL 60 (Peter Naur, et al.)

Architecture

3.1 First Draft of a Report on the EFVAC (John von Neumann)
3.2 A Symbolic Analysis of Relay and Switching Circuits (Claude E. Shannon)
3.3 Alto: A Personal Computer (C. P. Thacker, E. M. McCreight, B. W. Lampson, R. F. Sproull, D. R Boggs)
3.4 The Best Way to Design an Automatic Calculating Machine (M. V. Wilkes)

Numerical and Scientific Computing

4.1 On Computable Numbers, with an Application to the Entscheidungsproblem (A. M. Turing)
4.2 On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction (A. M.Turing)

Operating Systems

5.1 Cooperating Sequential Processes (Edsger W. Dijkstra)
5.2 Solution of a Problem in Concurrent Process Control (Edsger W. Dijkstra)
5.3 A Formal System for Information Retrieval from Files (David Hsiao, Frank Harary)

Software Methodology and Engineering

6.1 No Silver Bullet — Essence and Accidents of Software Engineering (Frederick P. Brooks)
6.2 Guarded Commands, Nondeterminancy, and Formal Derivation of Programs (Edsger W. Dijkstra)
6.3 Go To Statement Considered Harmful (Edsger W. Dijkstra)
6.4 Proof of Correctness of Data Representations (C. A. R. Hoare)
6.5 On the Criteria to be Used in Decomposing Systems into Modules (David L. Parnas)
6.6 A Rational Design Process: How and Why to Fake It (David L. Parnas, Paul C. Clements)
6.7 Global Variables Considered Harmful (W. Wulf, M. Shaw)

Databases

7.1 The Theory of Joins in Relational Databases (A. V. Aho, C. Beeri, and J. D. Ullman)
7.2 Organization and Maintenance of Large Ordered Indexes (R. Bayer, E. Mccreight)
7.3 The Entity Relationship Model - Toward A Unified View of Data (Peter Pin-Shan Chen)
7.4 A Relational Model of Data for Large Shared Data Banks (E. F. Codd)

Artificial Intelligence and Robotics

8.1 Steps Toward Artificial Intelligence (Marvin L. Minsky)
8.2 Matter, Mind, and Models (Marvin L. Minsky)
8.3 Fusion, Propagation, and Structuring in Belief Networks (Judea Pearl)
8.4 Computing Machinery and intelligence (A. M.Turing)

Human-Computer Communications

9.1 Programming Considered as a Human Activity (Edsger W. Dijkstra)

History

10.1 Programming in America in the 1950s - Some Personal Impressions (John Backus)
10.2 The Evolution of Data-Base Management Systems (James P. Fry, Edgar H. Sibley)
10.3 The Evolution of the UNIX Time-Sharing System (Dennis M. Ritchie)


Graph where only two vertices have the same degree

It is possible for every $N\ge 2$. We can prove it by mathematical induction.

For $N=2$, it is trivial.

Suppose there is such a graph for $N=n$, there are following two cases:

No vertex has degree $0$.
There is a vertex with degree $0$.

In case 1, we just add an isolated vertex. Now the graph has $n+1$ nodes and only two vertexes in the previous graph have the same degree.

In case 2, no vertex has degree $n-1$. We add a vertex with edges to every vertex in previous graph. The new node has degree $n$. The degree of each vertex in previous graph is added by $1$, thus no one in the new graph has degree $n$. Now the graph has $n+1$ nodes and only two vertexes in the previous graph have the same degree.

So such graph is possible for $N=n+1$.

As a conclusion, it is possible for every $N\ge 2$.

If you only care about connected graph (i.e. no vertex has degree $0$), the result is the same while the proof should be revised somewhat: the new graph for $N=n+1$ is constructed via first constructing an intermediate graph for $N=n$ from the graph for $N=n-1$ (this intermediate graph has a vertex with degree $0$), then constructing the graph for $N=n+1$.


Let us first show that $T_{NP}$ is indeed in NP. Given an input, $m\#w\#^c$, nondeterministically guess a sequence $r$ of nondeterministic choices for $M_m$ of length $c$, simulate $M_m$ on $w$ for $c$ steps using $r$, and accept if $M_m$ accepts. This nondeterministic algorithm accepts iff $m\#w\#^c \in T_{NP}$. Furthermore, it runs in polynomial time in the input size (here it is crucial that the input contains $\#^c$ rather than $c$ encoded in binary).

To show that $T_{NP}$ is NP-hard, you can just use the definition. Suppose that $M$ is an NP machine. Then $M = M_m$ for some $m$, and $M$ runs in time $P(n)$ on an input of length $n$. Given an input $w$, map it to $m\#w\#^{P(|w|)}$. It is clear that $M_m$ accepts $w$ iff $m\#w\#^{P(|w|)} \in T_{NP}$. The reduction is polynomial since $P(n)$ is a polynomial.


Sorting algorithms which accept a random comparator

So basically, you want to know if there is any sorting algorithm which wouldn't degrade from its average case if given a compare function similar to:

int Compare(object a, object b) { return Random.Next(-1,1); }

... where Random.Next() is some method that will produce a randomly-generated integer between a specified inclusive lower and upper bound.

The answer is actually that most basic sorting algorithms will perform according to their average case, because they obey at least one of the following two conditions:

A comparison between two unique elements is never made twice in the sort, and/or
In each iteration of the sort, the correct position of at least one element is determined and so that element is never compared again.

For instance, SelectionSort iterates through the sub-list of unsorted elements, finds the "least" and/or "greatest" element (by comparing each one to the greatest so far), places it in its correct position and repeats. As a result, even with a non-deterministic comparator, at the end of every iteration the algorithm will have found a value that it thinks is least or greatest, swaps it with the element in the position it is trying to determine, and never considers that element again, thus it obeys Condition 2. However, an A and B can be compared multiple times during this process (as the most extreme example, consider several passes of SelectionSort on an array that's sorted in reverse order) so it violates Condition 1.

MergeSort obeys Condition 1 but not 2; as sub-arrays are merged, elements in the same sub-array (on the left or right side) are not compared to each other because it has already been determined that the elements on that side of the array are in order among themselves; the algorithm only compares the least unmerged element of each subarray to the other to determine which is lesser and should go next in the merged list. This means that any two unique objects A and B will be compared to each other a maximum of one time, but any given element's "final" index in the full collection is not known until the algorithm is complete.

InsertionSort obeys only Condition 1 as well even though its overall strategy and complexity looks more like SelectionSort. Each unsorted element is compared with sorted elements, greatest-first, until one is found that is less than the element under inspection. the element is inserted at that point, and then the next element is considered. The result is that the relative order of any A and B is determined by one comparison, and further comparisons between that A and B are never performed, but the final position of any element cannot be known until all elements are considered.

QuickSort obeys both Conditions. At each level, a pivot is chosen and arranged such that the "left" side contains elements less than the pivot and the "right" side contains elements greater than the pivot. The result of that level is QuickSort(left) + pivot + QuickSort(right) which basically means the position of the pivot element is known (one index greater than the length of the left side), the pivot is never compared to any other element after it has been chosen as a pivot (it may have been compared with previous pivot elements, but those elements are also known and are not included in any subarrays), AND any A and B that end up on opposite sides of the pivot are never compared. In most implementations of pure QuickSort, the base case is one element, at which point its current index is its final index and no further comparisons are made.

The only comparative sort I can think of that wouldn't obey either condition is a non-optimized BubbleSort. If the sort does not accept that the X greatest elements are in their proper place after running X passes, and/or uses a "double-check" pass to verify the list is sorted, the sort will only be considered "done" when the random comparator has returned -1 or 0 for every two adjacent elements in the list during a pass and thus no swaps were performed (an event which, if truly random, would occur with probability $(2/3)^{N-1}$; for a relatively small list of 25 elements, that's a one in 2000 chance, while for 100 elements the probability is 3.7*10-18). As the maximum absolute value of the result of the comparator increases, the probability for any one comparison to return negative or zero decreases towards .5, making the chance to end the algorithm that much less likely (the chance of 99 coin flips all landing heads, which is basically what this boils down to, is 1 in 1.2*1030)

EDIT A LONG TIME LATER: There are a few "sorts" designed specifically as examples of what not to do which incorporate a random comparator; perhaps the most famous is BogoSort. "Given a list, if the list is not in order, shuffle the list and check again". Theoretically it will eventually hit on the right permutation of values, just like the "non-optimized BubbleSort" above, but the average case is factorial-time (N!/2), and because of the birthday problem (after enough random permutations you become more likely to encounter duplicate permutations than unique ones) there is a nonzero possibility of the algorithm never completing to officially the algorithm is time-unbounded.


Topological sort, but with some fixed values

There's a natural algorithm:

Arbitrarily pick any vertex all of whose predecessors have already been labelled; call it $v$.
If $v$ is constrained to have a specific index, label $v$ with that integer.  Otherwise, pick the smallest integer greater than all of the labels on the predecessors of $v$, and label $v$ with that integer.
If at least one vertex remains unabelled, go to step 1.

This is an adaptation of Kahn's algorithm for topological sorting, and it can be implemented so it runs in linear time.

The crucial thing that makes your problem feasible is that the labels don't need to be unique.  If the labels need to be unique, I suspect the problem becomes much harder; at least, this algorithm doesn't work, and a generalization of the problem becomes NP-hard.


What is the amount of programs for which we can solve the halting problem?

If we read the question as written then the answer is 100%. Let us be careful about what is being asked.

Attempt 1

Consider the set of numbers $n$ such that the $n$-th program either halts or it does not. If you believe in classical logic then every number is in this set, because "the $n$-th program either halts or it does not" is an instance of the Law of Excluded middle. So the answer is 100%.

Attempt 2

Sometimes people try to fix Attempt 1 by differentiating between "program $n$ halts or it does not" and "we have a decision procedure for $n$" (as witnessed by the comment "For every fixed program the halting problem is decidable." by adrianN above). That is, they think that it makes sense to have many decision procedures, one for each number. This leads to the following (failed) attempt:

Consdier the set of numbers $n$ such that there is a decision procedure for the halting of the $n$-th program. Once again every number is in this set:

If the $n$-th program halts then the decision procedure is print "it halts".
If the $n$-th program does not halt then te decision procedure is print "it does not halt".

However, and this is quite important:

we are here not talking about a single (posssibly non-computable) decision procedure,
we are talking about many decision procedures, one for each number (which is weird, which is why this is a failed attempt)
if we try to combine the decision procedures together somehow, we have a problem: even though for each particular $n$ there is a decision procedure $D_n$, the function $n \mapsto D_n$ is not computable

Attempt 3

The lesson learned from Attempt 2 is that we need one decision procedure that handles all numbers. But there is no such decision procedure because it would be a Halting oracle. We can still ask how well can we do with a single procedure?

Say that a procedure $P$ is a partial Halting oracle if, for every $n$,

$P(n)$ is undefined, or
$P(n) = 1$ and the $n$-th machine halts, or
$P(n) = 0$ and the $n$-th machine does not halt.

Define the success rate $s_P$ of such a decision procedure $P$ to be
$$s_P = \lim_{n \to \infty} \frac{\big|\{i \leq n \mid \text{$P(i)$ defined}\}\big|}{n}$$
Now we can ask whehter $s_P$ is well-defined (does the limit exist)? If sohow big can $s_P$ be?

Summary: The way you asked your question looks like you are going for Attempt 1 or Attempt 2, but it is not really clear. The problem is that you speak of "a solvable program". That does not make any sense. Every single program "is solvable" because it either halts or it does not (attempt 1, maybe attempt 2). You need to phrase the question carefully.


NFA-style representation of regexps which includes AND

It is a bit  difficult to answer you because you state that you are using NFA
to do the matching. NFA being non deterministic, that leave the
interpretation technique open, depth first, breadth first, or
variants. So I am trying to give you an answer that should fit any
interpretation of the NFA. This technique should be applicable to
other constructions than intersection.

You have 2 NFAs, $A_i=(Q_i,\Sigma,\delta_i,\hat q_i, F_i)$ for
$i=1,2$. The intersection is a NFA $A=(Q,\Sigma,\delta,\hat q, F)$
defined as usual for the intersection, notably with $Q=Q_1\times
Q_2$.

The idea of the technique is to implement the transition function
$\delta$ not as a table, but as a function $\delta: (Q_1\times
Q_2)\times\Sigma\to 2^{(Q_1\times Q_2)}$, that calls in turn the
function $\delta_1$ and $\delta_2$.

function delta((q1,q2),a)
{ return (delta1(q1,a), delta2(q2,a))}

This is to be read as a non deterministic program, in the sense
described in this answer to How does one formulate a backtracking
algorithm? That means that, in actual interpretation, the functions
are actually returning sets of results, one by one if backtracking, or
together if breadth-first.

The rest is up to the way you translate non-determinism into
determinism, either by a compiler, or by hand. It can be done
depth-first or breadth first. It can even use memo function to compute
incrementally and remember the part of the transitions of the
automaton $A$ that is needed for the string at hand, and possibly keep
it for future strings to be matched.

Of course, if your automata are DFAs, this is much simpler to read as
usual deterministic functions (possibly implemented by tables for
delta1 and delta2. Then memoisation of delta will construct
incrementally the table for the cross product.

The can be seen as an incremental construction, or as a generalisation of call by need. Rather than building the automaton up-front, you build the parts you need when you need them (and you can even forget some, if you run out of space). This can also be used for the powerset construction, and in many other circumstances.


Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

Let's write the condition $x+w=y+z$ in a different way: $x-y=z-w$. We consider two cases: $x \geq y$ and $y \geq x$. If $x \geq y$, let $x = y+a$. Then we are interested in words of the form
$$
0^{y+a} 1^y 0^{w+a} 1^w = 0^a 0^y 1^y 0^a 0^w 1^w.
$$
If $y \geq x$, let $y=x+b$. Then we are interested in words of the form
$$
0^x 1^{x+b} 0^z 1^{z+b} = 0^x 1^x 1^b 0^z 1^z 1^b.
$$
We can generate words of the first form using the grammar
\begin{align}
&T_1 \to AW \\
&A \to 0A0 \mid Y \\
&Y \to 0Y1 \mid \epsilon \\
&W \to 0W1 \mid \epsilon
\end{align}
We can generate words of the second form using the grammar
\begin{align}
&T_2 \to XB \\
&X \to 0X1 \mid \epsilon \\
&B \to 1B1 \mid Z \\
&Z \to 0Z1 \mid \epsilon
\end{align}
Taking these two grammars together and adding a new rule $S \to T_1 \mid T_2$, we get a grammar for your language. Note that you can merge $X,Y,Z,W$. The resulting grammar is
\begin{align}
&S \to AX \mid XB \\
&A \to 0A0 \mid X \\
&B \to 1B1 \mid X \\
&X \to 0X1 \mid \epsilon
\end{align}


A Recursive Formula For Generalized Josephus problem

Let me explain the idea.
Assume that indices start from 0.
Take N = 6 and K = 3
So initial arrangement looks something like

  0->1->2->3->4->5->0.... like a circle.

After round 1 , '2' is eliminated .

  0->1->2->3->4->5->0->1...

  ....(k)->0->1->2->3->

    here (k) denotes the person is killed

Since we ought to start from the last position we killed, so lets look at the updated indices.

  Old Index |  New Index

    3 | 0

    4 | 1

    5 | 2

  and so on....
  looking closely we can easily see after each round

    OldPosition = (newPosition+k)mod N

Where N is the number of people left before the round started.

Also OldPosition signifies f(N,K)

and New Position signifies f(N-1,K) as one person has already been killed.

So putting it back to OldPostion = (newPostion+k) mod N
we get

f(N,K) = ( f(N-1,K)+ K ) mod N

But this is done only if u have indices starting from 0. If u want to rearrange for indices starting from 1, you can rearrange it to get the above result.

I found a beautiful paper on this

http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf

Hope this helps :)


Lower-bounding the Membership Problem in the Bitprobe Model

First, the reason why the authors had to omit so many details is that the paper was published in a conference (SOCG) with a strict page limit. When you publish your paper, please provide a full version on your website with all the proofs. In my area usually the full details are in an appendix which is not available from the conference website since back in the day, the proceedings were printed and so a strict page limit had to be enforced. Nowadays many proceedings are online only and then there is no page limit, but it seems that your paper dates from before that period.

I'll only address your main question. Consider the structure for storing $\{x,y\}$. When you query $x$, you get either "left" or "right" at the first probe. Say you got "right". Then the right endpoint of the edge $x$ must be 1 (we use the convention that the output is the last bit read, see the paper). When querying $x'$, we read the same first bit, and so the right endpoint of the edge $x'$ must be 0. This means that the left endpoint of $y$ must be 1. This means that when querying $w'$, the first bit read must be "right". But then when we query $w$, we read the right endpoint of the edge $w$ which is 1.

Suppose now that you got "left" in the first probe of $x$. Then the left endpoint must be 1, and so the first probe of $y'$ must be "right". Therefore the right endpoint of $y$ must be 1, and so the first probe of $z'$ must be "left". But then when we query $z$, we answer the left endpoint of $z$ which is 1. In both cases we have reached a contradiction.


Time estimation for successful brute force attack

Passwords are not encrypted they are hashed with proper password hashing algorithms like Scrypt, PBKDF2, or better Argon2, the last is the winner of the 2015 password hashing competition.
I would like to assume that you use one of the above, however, the time that you measured implies the opposite. At least, you used an iteration count as little as possible.
The attackers are not like you - and they will never be - to check a single candidate password one at a time. They like to use as much as possible parallelization. See hashcat as a good example. CPUs, GPUs, ASICs, and FPGAs can be combined to find the target. Simple hashing can be searched massively in parallel even in a single GPU.
Therefore we need to mitigate these attacks as much as possible. The proper password hashing algorithms are memory-hard functions to prevent the massive parallelization and they have iteration count to increase the timing. With these, the attacker's massive parallelization is prevented and the search timing is crippled. Usually, the work factor is adjusted for the user's perspective so that the user does not wait so much for a login. For example, 400K iteration is for PBKDF2 may enough.

I was thinking:

AvrgTimeToEncrypt^PasswordType x PasswordLength ?

Once we forced the attacker to a single run on the single CPU thread, or one in a GPU, etc. we can talk about the timings a bit more precisely.
Let formalize as;

$\mathcal{S}$ as the password space.
$t$ is the execution time of a machine to test a given password hash and candidate from $\mathcal{S}$. (we use a uniform approach here, the timing will be different in a CPU, GPU).
$c$ is the number of machines that the attacker can use.

Now the search time of the space $\mathcal{S}$ is
$$ \frac{|S|}{t \cdot c}$$


Solution to the following recurrence relation and initial condition?

Try to calculate $a_1$. You'll see that $a_1=2\times3$. Then $a_2=2a_1=2\times2\times3=2^2\times3$.

Conjecture that $a_n=3.2^n$ for all $n\ge 0$.

Prove by induction.


Concurrency is not parallelism: indeed, concurrency refers to the sharing of resources in the same time frame. As an example, several processes may share the same CPU or share memory or an I/O device.
Two processes (or threads) can be defined concurrent if an only if the second process starts execution before the first has terminated (assuming that the execution happens on the same core of a multi-core CPU).
Therefore, if the two processes both run on the same core of a multi-core CPU the processes are concurrent but not parallel: in this case, parallelism is only virtual and refers to the OS doing timesharing. The OS seems to be executing several processes simultaneously. But, since the processes execute on the same core, only one instruction from one process can be executing at any particular time. Since the human time scale is billions of times slower than that of modern computers, the OS can rapidly switch between processes to give the appearance of several processes executing at the same time.
If you instead run the two processes on two different CPUS, the processes are parallel: there is no sharing in the same time frame, because each process runs on its own CPU. The parallelism in this case is not virtual but physical.
Finally, it is worth noting here that two processes running on different cores of the same multi-core CPU can not be classified as fully parallel, because the processes share the same CPU caches and will even contend for them.
It should now be clear that performance-wise, parallelism is better than concurrency.


The situation when P is a superset of NP

Let $L$ be any NP-complete language over $\Sigma = \{0,1\}$, and take
\begin{align}
A &= \{ 0x : x \in L \} \\
B &= 0\Sigma^* \\
C &= 0\Sigma^* \cup \{ 1x : x \in L \}
\end{align}


Is the prime factorization problem not an instance of the change making problem?

When using as the set of coins all logarithms of the prime numbers or numbers in general

The change-making typically assumes a finite set of coins.

You can, of course, extend it to infinite sets of coins but then you get a different problem. Depending on the exact formulation, it seems plausible that integer factorization would reduce to that new problem.

  But then the change making problem is listed as non NP problem, but the prime factorization problem is found to be NP complete.

Careful with your terminology there.

The general change-making problem is certainly in NP since it can be solved by integer programming. I do not know if it is NP-hard, but the common algorithms do not show that it is in P since they are only pseudo-polynomial. This shows, at least, that the problem is not strongly NP-hard.

Real-world change-making usually deals with canonical sets of coins for which a simple greedy algorithm works; it runs in constant time assuming a constant set of coins and the uniform cost model.

Integer factoring, on the other hand, is not known to be in P nor NP-hard; it's an open problem, and if P ≠ NP it may be in neither (but in NPI instead).


Did you check what's the class of your problem? I'd try a reduction to a scheduling problem.

If you want to have something so you solve it today, use Branch and Bound. Bounds should be easy to find.


Parallelising random reads seems to work well — why?

Forget for a moment all of the issues related to the access to main memory and level 3 cache. From a parallel perspective, ignoring these issues, the program parallelize perfectly when using $p$ processors (or cores), owing to the fact that, once you partition the work to be done through domain decomposition, each core must process either $\left\lfloor {\frac{n}{p}} \right\rfloor$ or $\left\lceil {\frac{n}{p}} \right\rceil$ elements and there is no communication and/or synchronization overhead since there is no functional dependence among the processors. Therefore, ignoring memory issues you expect a speedup equal to $p$.

Now, let's take into account the memory issues. The super-linear speedup you actually observed on your high-end Xeon based node is justified as follows.

A parallel system might exhibit such behaviour if its memory is hierarchical and if access time increases (in discrete steps) with the memory used by the program. In this case the effective computation speed could be slower on a serial processor than on a parallel computer using similar processors. This is because a sequential algorithm using $n$ bytes of memory will use only $n/p$ bytes on each processor of a $p$ processor parallel system, while
cache and virtual memory effects could instead reduce the serial processor’s effective computation rate.

For $n = 2^{31}$ bytes, we need 2048 Mbytes of memory. But, when using 12 cores as in your last example, every core needs to deal with only 2048/12 Mbytes of data, which is about 170 Mbytes. High-end Xeon processors are equipped with a cache level 3 whose size ranges from 15 to 30 Mbytes of size. Clearly, with this huge cache size the cache hit ratio is high, and this explains the good or even super-linear speedup-observed.

Regarding your second question, current architectures already prefetch data by evicting cache lines and replacing them as required to exploit temporal and spacial locality of data. But this will not be enough for a single core processing 2048 Mbytes of data. If you restrict $n$ to about 170 Mbytes, then you should see on a single core more or less the same performances, since you are now running under (more or less, not exactly) the same conditions.

Finally, besides QSM (Queueing Shared Memory), I am not aware of any other theoretical parallel model taking into account at the same level the contention for access to shared memory (in your case, when using OpenMP the main memory is shared among the cores, and the cache is always shared as well among the cores). Anyway, even though the model is interesting, it did not obtain great success.


I can verify solutions to my problem in polynomial time, how would a non-deterministic algorithm arrive to a solution if it always takes $2^n$ bits?

As I see it, this decision problem is obviously in P. Therefore, there is nothing for non-deterministic Turing machine to guess. Non-deterministic Turing machine would call polynomial-time verifier for a given problem instance and the problem would be solved in polynomial time.


Why does this particular hashCode function help decrease collisions?

If the hashed codes are $x_1,\ldots,x_n$ (in that order), then the resulting hash value is
$$
x_n + 31 x_{n-1} + 31^2 x_{n-2} + \cdots + 31^{n-1} x_1 + 31^n \cdot 17 \pmod{2^{32}},
$$
assuming int is 32 bits, and ignoring signed/unsigned distinctions. In view of this, the integers 17 and 31 should satisfy the following two properties:

17 should be non-zero. This way, the hash depends on the input length. Otherwise it is completely arbitrary.
31 should be relatively prime to $2^{32}$ (i.e., odd) and have a high order modulo $2^{32}$ (that is, the minimal $m$ such that $31^m \equiv 1 \pmod{2^{32}}$); this way the multiplicands $31,31^2,\ldots$ are all different for the longest time possible. It turns out that the order of $31$ modulo $2^{32}$ is only $2^{27}$, so 31 is not an optimal choice. Its being prime makes no difference – we only care about its oddness and order.

In any case, this hash can be improved on – for example, the python hash function uses XOR instead of addition, thus making the resulting calculation non-algebraic.


When you applied the master theorem, f(n) is n^2 right. This is anyways asymptotically lesser than O(n) which is the n^2log(n). Hence at each node of the recursion tree, the O(n) would dominate computation hence T(n) is O(n). The reason why this is true is because when you apply the recursion tree the number of processes at each node if you calculate would be 2O(n/2)+4O(n/4)...... whose sum turns out to be lesser than O(n).


First off, I don't think this is the appropriate place for this question.

Second; why are you incrementing count2 by 2 each time you find a "name" field that begins with a B? Surely this should be incremented by 1, like count 1 is.

Out of interest, do you know what the correct results should be?

Could you post them?


How does a computer play a video while doing something else?

This is implemented using several different techniques.  Within the application (for example, the web browser), the program can execute different threads of execution.  One thread can perform the video streaming/playback, while a different thread can handle the user typing into the comment field.

These threads, along with many other threads and processes, are in turn scheduled by the operating system (even if you only have the web browser open, the operating system has many background tasks running, such as the windowing manager, the print spooler, the USB device manager, etc).  It is the job of the OS scheduler to determine which thread can actively run, on which processor core, and for how long.  In a typical system, a thread can run for up to some threshold value, suppose 100 milliseconds, before the scheduler allows another task to run.

This task switching is fundamental to all modern operating systems (Windows, Linux, UNIX, etc), and is usually a significant portion of an undergraduate operating systems course.


Assuming finite optimal cost of a specific LP, find an optimal solution directly

Hint: Since there are $n+1$ constraints on $n$ variables, there is a solution in which all but one constraint are tight. You can calculate all these solutions explicitly ("on paper"), and choose the best one.


Are graphic cards using the Map-Reduce model when performing typical gaming rendering

This model isn't appropriate for rendering games, so it's not used in game engines. However, it can be implemented on GPUs. F.e. if you are going to implement Spark / relational algebra on GPUs, it may be a part of implementation.


How to show that pda accepts empty language?

I am not aware of any straightforward algorithms. One roundabout way I can think of is:

Convert the PDA to a CFG (there is a standard construction for this covered in introductory automata classes, the resulting CFG has $O(|Q|^2)$ variables where $Q$ is the size of the PDA)
Check if the CFG's language is empty.

We can check if the language of a CFG $G$ is empty using an iterative algorithm that marks a variable if it can derive a string:

Mark all terminals in $G$ (or delete them from the rules)
While no new variables are marked:

For each rule $A \to \alpha_1 \ldots \alpha_k$, if $\alpha_1, \ldots, \alpha_k$ are all marked then mark $A$.

If the start variable is marked then $L(G)$ is nonempty, otherwise $L(G)$ is empty.

The algorithm above can be optimized with a worklist that skips re-visiting a same variable's rules after it's marked, and doing some processing to allow checking rules affected by the previous pass


Relation between Lattice and Boolean Algebra

I would hardly describe a lattice as a generalized form of boolean algebra, since there are many more things that a lattice can describe.

A better description would be to say that boolean algebra forms an extremely simple lattice. It has two elements, $\top$ and $\bot$, with $\bot \sqsubset \top$. The meet corresponds to conjunction (AND), and the join corresponds to disjunction (OR), though you can make a dual lattice with these flipped.

But, we don't teach this with boolean algebra for the same reason we don't teach group theory when teaching children about the whole numbers.

Lattice theory is way more than you need to understand booleans, and while it's a neat fact that booleans form a simple lattice, the mechanics of lattice theory, fixpoints, continuity, etc. were made to solve much harder problems than arise with booleans.


Is it correct to say L is RE if I can map reduction from LH to L?

Let's clear things a bit, since there are many equivalent/similar definitions that could lead to misunderstandings.

You can show that a language $L$ is recursive by constructing a recursive function $\chi_L$ (or a Turing machine or any other equivalent computation model) that decides it, i.e.
$$\chi_L (x) = \begin{cases} 1 & \quad ; x \in L \\ 0 & \quad ; \text{otw}. \end{cases}$$
notice that $\chi_L$ must be defined for all inputs.
You can show a that language $L$ is not recursive, by finding a "Turing reduction" from a non-recursive language to it. This is probably what what you mean by reduction, and it is defined as follows:

  We say that a language $A$ is Turing-reducible to a language $B$, written $A \le_T B$, if we can construct a recursive function (or Turing machine) that decides $A$ by assumption that there is such function for $B$.

As you see by definition, Turing reduction somehow "transfers recursiveness" from $B$ to $A$.

  For any $A$ and $B$ such that $A \leq_T B$, if $B$ is recursive, then so is $A$.

Hence if we already know that some $A$ is not recursive, then finding a reduction $A \leq_T B$ for any $B$ makes it non-recursive too.
You can show that a language $L$ is RE, by constructiong a recursive function $\varphi_L$ (or Turing machine) that $Dom(\varphi_L) = L$ (or halts on/accepts it), for example
$$\varphi_L(x) = \begin{cases} 1 & \quad ; x \in L \\ \uparrow & \quad ; \text{otw.} \end{cases}$$

where $\uparrow$ means "not defined" (or "does not halt"). There are other definitions of RE-ness, like its namesake "enumerability", which you can easily observe that are equivalent to this one.
But in showing a language $L$ is not RE, Turing reduction does not help, since it does not necessarily transfer RE-ness. For example observe that $\overline{L_{HALT}} \leq_T L_{HALT}$ (indeed any language is Turing-reducible to it's complement and vice versa), but we know that $L_{HALT}$ is RE, while $\overline{L_{HALT}}$ is not.

But there are other kinds of stronger reduction that do transfer RE-ness. One such reduction is called "many-one redicibility":

  We say that a language $A$ is many-one-reducible to a language $B$, written $A \leq_m B$, if there is a total recursive function $f$ such that for any input $x$
  $$x \in A \iff f(x) \in B$$

This is a stronger reduction in the sense that $A \leq_m B$ implies $A \leq_T B$ (and not necessarily vice versa). So, like Turing reduction, it transfers recursiveness. We also have

  For any $A$ and $B$ such that $A \leq_m B$, if $B$ is RE, then so is $A$.

To see how this is true, just take $\varphi_A(x) = \varphi_B(f(x))$.

Hence the correct method to show a language $B$ is not RE, is to find a many-one reduction $A \leq_m B$ for some non-RE language $A$. Notice that the above example does not work here, because $\overline{L_{HALT}} \nleq_m L_{HALT}$.

For further reading, see Computability Theory by S. Barry Cooper Pt. I, Ch. 7.


Orthogonal range reporting with fixed upper rectangular corner

The count of any rectangle $C(U, L, D, R)$ can be obtained combining the counts of 4 fixed "upper-left" retangles:

$C(U, L, D, R) = C(0, 0, D, R) - C(0, 0, U, R) - C(U, 0, D, L) + C(0, 0, U, L)$,

noting $C(up, left, down, right)$ the count in the rectangle delimited by $(up, left, down, right)$.

Thus, you cannot expect more than a factor 4 runtime improvement.


Two way finite state Automaton NP Compleness definition clarification?

For a problem to be in NP, there needs to be a polynomial time verifier for it. This polynomial time verifier need not be the "obvious" one. Ruling out one specific verifier doesn't prove that the problem is not in NP.

For a problem to be NP-complete, it needs to satisfy two properties: (i) it needs to be in NP, and (ii) it need to be NP-hard. You can look these concepts up in many sources. In particular, the fact that there is some natural exponential time algorithm for a problem doesn't imply that it is NP-complete, though it is true that every problem in NP has an exponential time algorithm.

Unfortunately I am not versed well enough in two-way automata to answer your specific question, but my comments above imply that the answer doesn't necessarily have a direct bearing on whether the emptiness problem for 2NFAs is NP-complete or not (or even in NP or not).


Suppose that $L$ were context-free. According to Ogden's lemma, there is a constant $p$ such that each word in $L$ with at least $p$ marked positions satisfies the constraints of the lemma. Consider the word $s = \underline{a^p}b^{p+p!}c^{p+p!}$, in which the underlined part is marked. According to Ogden's lemma, there is a decomposition $s = uvwxy$ in which $vx$ contains at least one $a$, and $uv^iwx^iy \in L$ for all $i \geq 0$. We now consider several cases:

$x$ contains $b$s but not $c$s, or $c$s but not $b$s. Choosing $i = 0$, we obtain a word in which the number of $b$s differs from the number of $c$s, and so does not belong to $L$.
$x$ contains both $b$s and $c$s. Choosing $i = 2$, we obtain a word not belonging to $a^*b^*c^*$, and so not belonging to $L$.
$x$ contains no $b$s nor $c$s, and $v \notin a^*$. In this case $x = \epsilon$, and so $v$ must contain at least two different characters. Choosing $i = 2$, we again obtain a word not belonging to $a^*b^*c^*$, and so not belonging to $L$.
$vx \in a^+$, say $vx = a^q$. Let $i = p!/q+1$. Then $uv^iwx^iy = a^{p+p!}b^{p+p!}c^{p+p!} \notin L$.

We have obtained a contradiction, and so $L$ is not context-free.


what is the difference between an adapter and a controller?

The distinction between the two[adapter and controller] is mainly one of packaging. Controllers are chip sets in the device itself or on the system’s main printed circuit board (often called the motherboard). An adapter is a card that plugs into a slot on the motherboard.Regardless, the purpose of each is to transfer information back and forth between the I/O bus and an I/O device.

Ref: Computer Systems: A Programmer's Perspective, 3rd Edition.


Are there decidable problems that are reducible to undecidable problems?

Any decidable problem can be reduced to the halting problem. Take a machine $M$ that decides some language $L$. Now produce a new Turing machine $M'$ that behaves identically to $M$ except that, if $M$ rejects, $M'$ loops forever. Now, $M'$ halts on input $x$ if, and only if, $x\in L$.

More generally, every decidable problem can be reduced to every undecidable problem. Let $Z$ be some undecidable language.  We know that $Z\neq\emptyset$ and $Z\neq\Sigma^*$, since both of those languages are trivially decidable. Therefore, there are strings $z^+\in Z$ and $z^-\notin Z$.  Now take any decidable language $L$.  Since $L$ is decidable, the function
$$ f(x) = \begin{cases}z^+&\text{if }x\in L\\z^-&\text{if }x\notin L\end{cases}$$
is computable, and it is a reduction from $L$ to $Z$.

  I am thinking a decidable problem could be reduced to a recognizable, undecidable problem because a polynomial time verifier would work on a decidable problem. Is this a correct idea?

I think you're confusing the set of recognizable languages with NP. A recognizable language has a computable verifier but the verifier doesn't necessarily run in polynomial time (and the time hierarchy theorem says that there are languages whose verifiers can't run in polynomial time). It's true that every decidable problem has a computable verifier (because being able to decide the problem essentially means that you can verify a given answer by just computing the correct answer and comparing) but that doesn't give you a reduction. Rather, it proves that every decidable language is itself recognizable.


Compute 'insertable' letters in a regular language

Edit: The OP changed the question. What follows works for one interpretation of the original question.

I'm assuming you are given a DFA $A = (Q,\Sigma,\delta,q_0,F)$. The method can be adapted to handle NFAs.

Let the word be $w = w_1 \ldots w_n$. For each $i \in \{0,\ldots,n\}$, calculate the state $s_i$ that the automaton reaches after reading the prefix of length $i$ of $w$. For each $i \in \{0,\ldots,n\}$ and each accepting state $q \in F$, calculate the state $t_{i,q}$ that the reverse automaton reaches when starting at $q$ and reading the reverse of the suffix of length $i$ of $w$. Let $T_i = \{ t_{i,q} : q \in Q \}$.

For each $i \in \{0,\ldots,n\}$ and each symbol $a \in \Sigma$, check whether $\delta(s_i,a) \in T_{n-i}$. If so, $a$ can be inserted at position $i$: $w_1 \ldots w_i a w_{i+1} \ldots w_n \in L(A)$.

The running time is $O(n(|\Sigma| + |Q|))$, and the method requires space $O(|Q|)$ (if implemented by going over $i = 0,\ldots,n$, in this order).


Converting DFA to Regular Expression Using State Removal

Think of it this way. You can reach 2 from 1 in two ways

$1\rightarrow 2$
$1\rightarrow 3 \rightarrow 2$

Then from 2, you can move to 1 by $2\rightarrow 1$. From there again, move to 2 from 1 in the above two ways. So this NFA can be expressed as an RE as follows:

$$RE = (1\rightarrow 2 + 1\rightarrow 3 \rightarrow 2) \cdot [(2\rightarrow 1)\cdot (1\rightarrow 2 + 1\rightarrow 3 \rightarrow 2)] ^*$$

Now its just the matter of finding the REs for $1\rightarrow 2$, $1\rightarrow 3 \rightarrow 2$ and $2 \rightarrow 1$.


P2P and C/S, is it possible to determine which one is more bandwidth consuming?

One would say that P2P is better. But in reality, you cannot tell by the information you provided.

For instance, the bandwidth depends on queuing delays. Therefore, assume that one of the nodes in the P2P network has a very small queue (or overloaded), while our server is super powerful and its queue is hugly big ! Similarly, it depends on the latency of the nodes.

It depends on the bandwidth of the channels in the network.
It depends on the round trip time.  Therefore, P2P peers may be very far away from each other ! (China, Iran, Venzuela for example). etc ..


Is Big-Oh notation preserved under monotonic functions?

By definition,
$$ f(n) \in O(g(n))$$
means there exists some positive constant $c$, such that for any large enough $n$,
$$ |f(n)| \le c |g(n)|$$
or equivalently, $\lim_{n\to\infty} \frac{f(n)}{g(n)}  \le c < \infty$

Taking $\log$ of both sides, for any large enough $n$ it holds that
$$ \log (f(n)) \le log (c) + \log(g(n)) $$

so,
$$\frac{\log f(n)}{\log g(n)} \le \frac{\log c}{\log g(n)}+ c$$

Now can this go to infinity? only if  $\log(g(n)) \to 0$

So let's try, and take $f(n)=2^{-n}$ and $g(n)=1/n$. Obviously $f(n) \in O(g(n))$.
Yet, taking the logs we have $\log f(n) = -n$, $\log g(n) =-\log n$, and it is clear that no constant $c'$ will satisfy $|\log f(n)| \le c' |\log g(n)|$ for large enough $n$. Yet, I always find it weird to discuss $O$ of negative functions.

EDIT:

Here's example w/o negative function. Get back to the requirement of $\log(g(n)) \to 0$. Take $g(n) = 1+1/n$. Thus $\log (g(n)) \to 0$.
(actually, the above example of $2^{-n}$ vs $1/n$ satisfies $g(n)\to 0$ rather than $log(g(n))\to 0$. Oops).

If we take $f(n) = 2 + 1/n$ then $\log f(n) \to 1$ (binary log, obviously).

so while $f(n) \le 3g(n)$ for every $n\ge 1$, it is not true that
$\log f(n) \le c' \log g(n)$ for all large enough $n$, as the right-hand side approaches zero, while the left-hand side approaches 1.


Complexity of special instance of Knapsack

Your problem is at least as hard as the known-prime-factor version of this problem. Shor's reduction also applies to that version, and can be made effective by using this answer rather than the Wikipedia link in Shor's answer.


Why is crossing paths bad in Traveling Salesman?

The statement is for Euclidean TSP only, and as you mention yourself, it is only used as a heuristic.
But try to create an example yourself and see what happens when you have crossing links as part of your solution:

From Urban OR:
Property 1: The optimum traveling salesman tour does not intersect itself.


algorithm for connectivity by path of given length

The problem is NP-complete and referred to as Longest Path.  It is FPT, though, so you can solve it in time polynomial in $n$ for fixed $k$.
If you want to solve it in FPT time, the easiest solution is to do color coding.  The trick is two-fold.

Suppose that vertices are colored with $k$ colors, and you are looking for a rainbow-path of length $k$, i.e. a path where every vertex has different color.  This problem can be solved by dynamic programming!

Repeat the following step: Randomly color the vertices of the graph with $k$ colors, and run the rainbow algorithm.

With probability depending only on $k$, if there exists a $k$-path, then you will output a rainbow path.


Is writing a number as two squares and writing the factors of a number equally hard?

Here's the situation as far as I can tell:

The most efficient way known to test membership in $L_1$ is to factor $r$.  No more efficient algorithm seems to be known.

However, there is no obvious reduction to prove $L_2 \le_P L_1$.  In other words, if we had a machine to decide $L_1$, there's no easy way to use that to factorize.  If we want to factor a number $N$, we can check whether $N \in L_1$, but this only gives us one bit of information about the factors of $N$.  Testing multiples of $N$ (i.e., whether $cN \in L_1$ for some integer $c$) doesn't give us any additional information, as knowing whether $N \in L_1$ suffices to predict whether $cN \in L_1$ for all $c>0$.  Testing other numbers doesn't seem to help in any obvious way, either. (Testing whether $N' \in L_1$ for some other number $N'$ doesn't seem to give any useful information, if $\gcd(N,N') =1$; and if we had a way to find another number $N'$ such that $\gcd(N,N')\ne 1$, we'd already know how to factor, but of course we don't know how to do that -- so any number we know how to generate is unlikely to give us any useful information on the factors of $N$.)  This is not a proof; it is just handwavy intuition.

So it seems plausible that $L_1$ might be easier than $L_2$, and it also seems plausible that they might be of the same difficulty.  I'm not aware of any further results on this subject.


Here is one solution:

Clearly Double-SAT belongs to ${\sf NP}$, since a NTM can decide Double-SAT as follows: On a Boolean input formula $\phi(x_1,\ldots,x_n)$, nondeterministically guess 2 assignments and verify whether both satisfy $\phi$.

To show that Double-SAT is ${\sf NP}$-Complete, we give a reduction from SAT to Double-SAT, as follows:

On input $\phi(x_1,\ldots,x_n)$:

Introduce a new variable $y$.
Output formula $\phi'(x_1,\ldots,x_n, y) = \phi(x_1,\ldots,x_n) \wedge (y \vee \bar y)$.

If $\phi (x_1,\ldots,x_n)$ belongs to SAT, then $\phi$ has at least 1 satisfying assignment, and therefore $\phi'(x_1,\ldots,x_n, y)$ has at least 2 satisfying assignments as we can satisfy the new clause ($y \vee \bar y$) by assigning either $y = 1$ or $y = 0$ to the new variable $y$, so $\phi'$($x_1$, ... ,$x_n$, $y$) $\in$ Double-SAT.

On the other hand, if $\phi(x_1,\ldots,x_n)\notin \text{SAT}$, then clearly $\phi' (x_1,\ldots,x_n, y) = \phi (x_1,\ldots,x_n) \wedge (y \vee \bar y)$ has no satisfying assignment either, so $\phi'(x_1,\ldots,x_n,y) \notin  \text{Double-SAT}$.

Therefore, $\text{SAT} \leq_p \text{Double-SAT}$, and hence Double-SAT is ${\sf NP}$-Complete.


When do type systems start needing a logic engine?

I'm not sure where you would draw the line between "direct type checker" and "logic engine". In a deep sense every type checker for a modern type system is a theorem prover (or proof-checker; more on this in a moment). The theorem to be proven is "the program is well-typed", or "this function has type X".

Modern type systems and their checking/inference algorithms tend to be specified in terms of logic; typically intuitionistic typed logic (a.k.a. Martin-Löf theory). If you have a look at, say, the paper for the standard Hindley-Milner type inference algorithm [1], you'll see that it's specified abstractly in terms of logic. Let-polymorphism also relies on the Robinson unification algorithm, famously used in Prolog.

I'm going to go out on a limb here and suggest that the degree to which a type inference algorithm resembles a "logic engine" (however you define it) depends on how "decidable" the rules are, and how much "inference" you need to do (as opposed to merely "checking"). The type system of the simply-typed lambda calculus is intuitionistic logic (and I do mean it really is the same thing; this is the famous Curry-Howard correspondence), so you'd think that any type checker for that system is a "logic engine" in any reasonable sense. But because you only need to "check" rather than "infer", it's a proof checker rather than a theorem prover.

The standard introductory reference on this topic is TaPL [2]. If you're at all interested in this topic, it's well worth a read; any well-stocked university library should have a copy.

Principal type-schemes for functional programs by Damas and Milner (1982).
Types and Programming Languages by Benjamin C. Pierce.


What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms?

I'm going to try to answer this myself, in the hope that my answer will give others a better idea of what I'm after and lead to better answers than mine.

I found that framing the problem in terms of the original golden ratio base helped me to think about a binary encoding more effectively.  I want to note however that there is no difference between BTTS and phinary except the length of the representation.  Both number systems represent the same set of numbers, save that BTTS more easily encodes negative numbers.  Just as 3 bits can theoretically represent 2 trits of BTTS, they should also be able to represent 4 bits of phinary (which is what 2 trits encode).  Keep in mind that in standard base-$\phi$ all instances of $011_\phi$ are replaced with $100_\phi$ and $1_\phi + 1_\phi = 10.01_\phi$, with a carry both one place to the left and two to the right.  The following table is my best attempt thus far:

Phinary  |  Binary | Octal
0 0 0 0  |  0 0 0  |   0
0 0 0 1  |  0 0 1  |   1
0 0 1 0  |  0 1 0  |   2
0 1 0 0  |  0 1 1  |   3
0 1 0 1  |  1 0 0  |   4
1 0 0 0  |  1 0 1  |   5
1 0 0 1  |  1 1 0  |   6
1 0 1 0  |  1 1 1  |   7

There are some benefits to this encoding. One is that $0_\phi$ and $1_\phi$ are the same as for binary.  Another is that a carry in the forward direction works as expected automatically:

$1010_\phi + 1_\phi = 1011_\phi = 1100_\phi =  1\ 0000_\phi$, and $111_2 + 1_2 = 1\ 000_2$.

Another advantage is that addition almost works as is:

$0101_\phi + 0010_\phi = 0111_\phi = 1001_\phi$ and $100_2 + 010_2 = 110_2$.

As far as I can tell, the only places addition breaks down are for $2_8 + 2_8$, $5_8 + 7_8$ and $7_8 + 7_8$.

$0010_\phi + 0010_\phi = 0020_\phi = 0100.1_\phi$, not $0101_\phi$.
$1000_\phi + 1010_\phi = 2010_\phi = 1\ 0020_\phi = 1\ 0100.1_\phi$, not $1\ 0101_\phi$.
$1010_\phi + 1010_\phi = 2020_\phi = 2100.1_\phi = 1\ 1000.1_\phi$, not $1\ 1001_\phi$.

All other additions work (excluding right carry logic).

We can handle right carries by looking at how they are produced. I'll be using octal for brevity.

1, 4, and 6 produce a right carry of 3 to the previous 3 bits when they are added to themselves or each other.
2 and 7 produce a right carry of 5 added to the previous 3 bits when added to themselves or each other.
4 + 3 gives a right carry of 3 and 5 + 7 gives a right carry of 5.

That's all we need to check for (I think) with the exception of also testing for 2 + 2, 5 + 7, and 7 + 7 and subtracting 1 from the result.

So basically we are taking advantage of the redundancy in a 4-bit phinary representation ($011_\phi = 100_\phi$) to represent the same numbers without redundant cases in 3-bits of binary.
A $2^n$ bit number can store $\lfloor 2^n / 3\rfloor * 4 + 1$ phinary bits.

I'm sure there are clever bit-hacky ways to do this better, but I'm hoping that this will clarify my intent and provide a starting point for both myself and anyone else wanting to tackle this.


Given a relation and asked to enumerate all FD's and mark the trivial FD's

I suppose that in the exercise, the request “organize them accordingly to the LHS”, is just a request of sorting all the functional dependencies (maybe lexicographically) with respect first to the attributes of the left hand side (the determinant of the functional dependency) (and then maybe on the rigth hand side for all the FD with the same left part).

For what concerns the list, I think it should include all the possible functional dependencies, including those with two attributes as determinant, as well as the (only) dependency with three attributes as determinant, as well as those with all the subset of attributes determined on the right part. So something like:

A -> A
A -> AB
A -> AC
A -> BC
A -> ABC
AB -> A
...
B -> B
...

If you want to be super-formal, you can include also the trivial dependencies A -> {}, etc., as well as the trivial dependency {} -> {}.


Standard information-theoretic lower bound?

I understand your question this way:

  Assume Alice has some $X\in\{0,1\}^n$. Alice encodes (compresses) $X$ into $s = s(X)$, where $|s|\le n$. Bob decodes $s$ to obtain $X'=dec(s)$.
  Show that unless $|s|=\Omega(n)$ it cannot hold that Hamming$(X,X') < n/3$.

If this is what you meant, then this follows from the fact that most strings cannot be compressed. Assume that for any $X$, $|s(X)|=o(n)$. Note that there are at most $2^{|s|}\ll 2^n$ such strings. More accurately, $2^{|s|} / 2^n \to_{n\to\infty} 0$.

Then, for each possible $s$ construct $dec(s)$ and define $Y_s$ to be a Hamming ball of radius $n/3$ centered at $dec(s)$. Verify that $|Y_s| = \sum_{d=0}^{n/3}\binom{n}{d} < 2^{n\cdot h(1/3)}$, with $h(\cdot)$ the binary entropy function.
Thus $\left|\bigcup_s |Y_s|\right| \le 2^{o(n)}2^{0.92n} \ll 2^n$. This means that there exists a string $X$ not covered by the $Y_s$ for any $s$, i.e., not within a Hamming-distance of $n/3$ from any of the decoding of any $s$.

 If this is not what you meant, you will have to formulate your statement in a proper way. For instance, you say "with probability 2/3", but there is no probability space defined in your statement, etc.


How do hand coded lexers generally work?

That depends on whose hand coded them :-). But:

Are they similar to either table-driven or direct-coded ones?

Table-driven hand-coded lexers are rare in my experience (if you were going to use a table anyway, why not use a tool to generate the table). Torczon & Cooper use "direct-coded scanner" to mean a scanner which effectively embodies the state machine (DFA) in code, so that the program counter is the state.
Most hand-coded lexers implement a state machine of some kind, although they are often not very rigid in their model. For example, a common approach is to use a switch on the first character of the token, and then, depending on the token type, use some standard library function to parse the rest of the token. While some hand-coded parsers implement a direct-coded trie for keywords, others just recognize identifiers and then check the token in a hashtable. And a large variety of other variations on the theme.
[Note 1]

Where can I find simple examples of hand coded lexers?

Check out the Bison manual, which has a number of simple examples which do not depend on lex.

Notes:

Some machine-generated lexers -- see Ragel or re2c, for example -- are direct-coded state machines. This was once believed to improve scanner speed, a theory also endorsed by the textbook. However, I'm not convinced that it is still the case with modern pipelined processors. In any event, it is very rare for scanner speed to be a noticeable part of compilation time.


How to prove an implication about an upper bound mentioned in the proof of master theorem?

The statement $f = O(h)$ just states that there exists a constant $C>0$ such that $f(N) \leq Ch(N)$ for all $N$ (some variants have this hold only for large enough $N$, but in most cases there is no difference). In your case, $f(N) \leq CN^{\log_b a-\epsilon}$ for all $N$. This holds for $N = n/b^j$ in particular, and implies that
$$
g(n) \leq C \sum_{j=0}^{\log_b n-1} a^j (n/b_j)^{\log_b a-\epsilon}.
$$

As for the two different definitions of big O: suppose that $f(N) \leq CN^{\log_b a-\epsilon}$ holds only for $N \geq N_0$, and let $M = \max(C,f(1),\ldots,f(N_0))$. Then $f(N) \leq MN^{\log_b a-\epsilon}$.


How to compute relative error for the rounding of floating point numbers when the rounded number is 0?

If x = 0 and is rounded to 0 then the error is 0, and the relative error is whatever you want it to be.

If x ≠ 0 and is rounded to 0, then the absolute error is x, and the relative error is 1 (or 100% if that is more intuitive).

If x = 0 and is round to y ≠ 0 then the absolute error is y, and the relative error is infinite or undefined, whatever you prefer.


Does intersecting the output of 2 programs give the output of another program?

Let $f$ be a computable bijection from $\mathbb{N}^*$ to $\mathbb{Z}$. For example, $f(1)=0,f(2)=1,f(3)=-1,f(4)=2,\ldots$

Note a non-empty subset of $\mathbb{Z}$ is the range of a program if and only if it is recursively enumerable. On the one hand, the range of a program $P$ can be enumerated by running $P(f(1)),P(f(2)),P(f(3)),\ldots$ On the other hand, for a non-empty recursively enumerable subset $X$ of $\mathbb{Z}$, there exists an enumerator $E$ that enumerates $X$. Suppose $E$ requires $n$ steps to output the first number, we can define a program $P$ that $P(i)$ returns the last number outputted by $E$ within at most $\max\{n,f^{-1}(i)\}$ steps.

Since the intersection of two recursively enumerable sets is still recursively enumerable, your $P_3$ exists if and only if the intersection is not empty.


Prove that any algorithm that has sublinear time have a constant time complexity?

I think to make this work we need to work in a model of computation where the input string is read sequentially. That is, in order to read the $i$'th character of the input string $S$, we first need to read characters number $1,2,\ldots,i-1$. In what follows I also assume that every substring of a valid input is a valid input (this in particular implies the fact that the length of the string cannot be explicitely encoded in, say, the first $O(\log n)$ bits of the input).
Let $S$ be the set of strings such that invoked on any input $x\in S$ the algorithm $A$ reads all of $x$. As the guideline suggests $S$ must be finite, as otherwise $A$ cannot be sublinear.
Now, let $k$ be the length of the longest string in $S$. I claim that $A$ never reads more than $k$ characters of its input. Indeed, suppose there is some input $x$ such that $A$ reads $k'>k$ characters when invoked on $x$. Let $y$ be the string consisting of the first $k'$ characters in $x$ (this is where I use the assumption that every substring of a valid input is a valid input). Because $A$ reads only the first $k'$ characters when invoked on $x$ it cannot distinguish between $x$ and $y$. In particular, it also reads all $k'$ characters when invoked on $y$. Thus, $y\in S$ and $y$ is of size $k'>k$, which contradicts the definition of $k$. We conclude that our assumption was wrong, and $A$ never reads more than $k$ characters of its input.
Because $A$ never reads more than $k$ characters of the input, it has a finite (constant) number of distinct possible executions. Thus, its worst-case time-complexity is also constant.
(I implicitly assumed a deterministic model of computation here, but it isn't hard to make the argument work under the presence of randomness, both for worst-case and expected time-complexity)


What is the name of this logistic variant of TSP?

The problem is in $\mathrm{P}$ if the number of items is constant.

Let $K$ be the number of items (independent of $n$). For every ordering of items, use backtracking to try all allowed routes: you first go through some warehouse for the first item (trying all warehouses), then one for the second item and so on.

There are $O(K!)$ orderings of the items. Let $W_i$ be the number of warehouses for item $i$. The number of routes is $\prod_{i=1}^K W_i \leq \prod_{i=1}^K n = n^K$. Therefore, the running time of the above algorithm is $O(K! n^K)$, which is polynomial for fixed $K$.

If the number of items can be linear in $n$, the problem is at least as hard to approximate as $TSP$: you can take an instance of $TSP$, make an item for every vertex as you noted, and then add extra vertices very far away from all other vertices to inflate $n$ (and therefore allow for enough items that every vertex of the $TSP$ instance has a different item), without destroying the hardness of approxability of $TSP$. Note that if your points are in the Euclidian plane, then this doesn't really help you as there is a $PTAS$ for planar $TSP$.


You haven't really specified an algorithm, but a similar idea is used by random walk algorithms for SAT such as Schöning's algorithm (see for example Giurgiu's Master thesis or one of the many online lecture notes on the topic).

The same approach is also used in the heuristic algorithm WalkSAT which has recently been used to prove an algorithmic version of the Lovász local lemma.


How can I sum pixel values over a rotated rectangle?

One simple technique that's probably not optimal, but is better than naively enumerating all pixels in the rotated rectangle, is to use "integral columns" (thanks to Yves Daoust for the name):

Preprocessing: Let $I[\cdot,\cdot]$ be the image.  For each $x$ value, build a 1D integral image for $I[x,\cdot]$.  In other words, we build a table $S[\cdot,\cdot]$ where $S[x,y] = S[x,0] + S[x,1] + \dots + S[x,y]$.  This can be done in linear time.

Answering a query: Given a rotated rectangle $R$, we find the range of $x$-values of pixels within $R$ (i.e., the leftmost part of $R$ and rightmost part of $R$).  This can be done in $O(1)$ time.  Next, for each $x$ in that range, we find the range $[y_\ell,y_u]$ of $y$-values such that $(x,y)$ is in $R$ for each $y_\ell \le y \le y_u$.  We sum the pixel values of those by computing $S[x,y_u] - S[x,y_{\ell}-1]$.  This takes $O(1)$ time per $x$-value, so the total running time to sum the pixels in a rectangle is proportional to the width of $R$ (in contrast, the naive method's running time is proportional to the area of $R$).

As a trivial optimization, you can precompute sum tables for both $x$ and $y$; for each $R$, you can check which is smaller, the width or height of $R$, and then decide whether to enumerate $x$-values or $y$-values.


I recommend you first try to understand the language denoted by the regular expression. Once done this can make it easier to build the DFA directly . If you can not think of how to build the DFA you can always turn your regular expression into an NFA and then the NFA into a DFA(Convert regular expression to DFA).

The strings denoted by your regular expression are:

   Empty string or a concatenation of strings formed by a chain of zero or more $a's$ followed by a $b$. This mean that your initial state should be a final state too and a word in this language "always"(except  $\epsilon$) finish with a letter $b$ so your DFA can't transition to a final state consuming a letter $a$. I hope those hints can help you to generate your DFA directly.


How to calculate point in 3D space from multiple perspective

For each camera, you can compute the direction on which is detected the object. The position and orientation of the camera let you find the direction of the center of the image. Depending on camera aperture, each pixel of the image corresponds to a slightly different direction. I don't know which definition you use for your angle so I won't risk any expression of it but you should convert the angle to obtain a vector in cartesian coordinates.

So from a camera with position at $(x_c, y_c, z_c)$ and detecting the object in the pixel of direction defined by the unitary vector $(x_d, y_d, z_d)$, you know the object is along the direction:

($x_c + x_d \times d, y_c + y_d \times d, z_c + z_d \times d$) with $d$ being the distance camera-object.

Now if you have 2 cameras, you can look for the nearest points from each line to the other and take their center as position of the object (see skew lines).


Regular expression for capturing a "C-style" string

Here is a regular expression for the set of all strings of the following form:

They start and end with ".
Every " in the middle must be escaped using a backslash.
Every backslash must be followed by a letter from $A$.
All other letters are from $B$; in particular, " is not in $B$.

For simplicity, I identify $A$ and $B$ with the regular expressions $\sum_{\sigma \in A} \sigma$ and $\sum_{\tau \in B} \tau$.

Here is the regular expression:
$$
\text"(B+\backslash A)^*\text"
$$


Shortest path problem where edge weight depends on path taken

Don't do that.  Instead, change the way you model the problem as a graph problem.

One crude approach: Rather than having a vertex for each bus stop, introduce one vertex for each pair of a bus stop and a time.  For instance, if $s$ is a bus stop and $t$ is a time, then $(s,t)$ is a vertex.  If we have a bus that goes from $s$ to $s'$, takes 5 minutes, and departs every 20 minutes, then we'd have edges $(s,0) \to (s',5)$, $(s,20) \to (s',25)$, $(s,40) \to (s',45)$, etc.  You can take it from here.  (Test for understanding: see if you can work out what the running time of finding the shortest path to some destination is.)

A smarter approach: Fix an original vertex $v_0$ (the starting point of all trips).  For each vertex $v$, compute $d(v)$, which is the time it takes to get from $v_0$ to $v$.  How do you compute $d(v)$?  Use dynamic programming.  If you know $d(u)$ for all predecessors $u$ of $v$, then you should be able to work out an easy way to compute $d(v)$.  Also, if you've studied shortest-paths algorithms, you should be able to find an ordering for assigning $d(\cdot)$ values.  This will provide an efficient algorithm.


Is unification over regular expression equations doable?

I'm fairly sure this is possible. This seems to me as a special case of set constraints over tree languages: we can view regular expressions as a restriction of regular tree languages where each node has 0 or 1 children. These can handle union, concatenation, and recursion (star), and you can solve for variables like you describe.

They're decidable, even when we allow negation. You can see a great survey here:  https://theory.stanford.edu/~aiken/publications/papers/ppcp94.pdf In general, Alexander Aiken has a lot of great papers on set constraints.

You might find more of what you're looking for with "word constraints" or "set constraints over words". The complexity situation isn't great for trees, but it might be better for words.


If I'm just trying to show something is NP-hard (as opposed to NP-complete) does my reduction need to be completed in polynomial time?

Hardness/completeness is always defined with respect to a specific kind of reduction.

Using exponential-time reductions doens't work at all, because that means your reduction is even more powerful than the thing you're reducing to.*
Every language except $\emptyset$ and $\Sigma^*$ is NP-hard under exponential-time reductions. To see this, let $L$ be any language except $\emptyset$ and $\Sigma^*$, and let $X$ be in NP.  We can reduce $X$ to $L$ as follows. Fix two strings $w_{\mathrm{yes}}\in L$ and $w_{\mathrm{no}}\notin L$. Now, given a string $x$, we can determine in exponential time if $x\in X$. If it is, the reduction maps $x\mapsto w_{\mathrm{yes}}$; otherwise, it maps $x\mapsto w_{\mathrm{no}}$.

* OK, technically, we don't know that EXP is more powerful than NP, but it's certainly at least as powerful, and probably more powerful.


Present syntax rules in a more succinct way

One direct way of solving this problem is to make the syntax rules parameterised, as follows:

\begin{eqnarray*}
e_{X,Y} &::=& e_C \mid \textit{prefix-op} \; e_{X,Y} \mid e_{X,Y} \; \textit{infix-op} \; e_{X,Y} \mid Y (e_{X,Y}, e_{X,Y},\ldots) \mid X \\
\end{eqnarray*}

And then to set
\begin{eqnarray*}
e_E &::=& E_{\mathit{specialE},~\mathit{function}_E} \\
e_V &::=& E_{\mathit{specialV},~\mathit{function}_V} \\
\end{eqnarray*}

This is using notation I just invented, and it could probably be reworked, but you get the idea, I hope.


Is there a language which has a polynomial length certificate but not known to have a polynomial time verifier?

For any instance of a problem, take the instance itself as the certificate. Linear size, verifiable in polynomial time for problems in P, not known for problems in NP.


Second normal form means that each non prime attribute must not depend on a proper subset of a candidate key.
In your example, assuming that the given FDs are a cover of the FDs of the relation, you have two candidate keys, ABC and ABD. Moreover, the attribute E depends on BC, which is a proper subset of the candidate key ABC (you can verify this by computing the closure of BC, BC+, and see that E belongs to that closure).
So the relation is not in 2NF.


Path between two vertices in directed graph without cyclic vertices

My previous suggestion was wrong. So I have deleted, and will now modestly suggest another approach. Hope this works.

It seems your problem is NP hard. I will sketch a reduction from 3SAT.
take a formula $\varphi$. Construct a single line of vertices, with alternatives in between. The path describes a valuation, and a verification that all clauses are true.

First, let the variables be $x_1,x_2, \dots,x_n$. Then we have vertices $u_0,u_1, \dots u_n$, $x_1, \dots x_n$, and $\bar x_1, \dots \bar x_n$. And we set edges $(u_{k-1},x_k)$, $(x_k,u_k)$ and $(u_{k-1},\bar x_k)$, $(\bar x_k,u_k)$ for $k=1,\dots,n$. A path from $u_0$ to $u_n$ sets the variables.

Now consider the $m$ clauses. We continue by having $m$ fresh vertices $v_0,v_1, \dots v_m$. Connect $u_n$ to $v_0$. Let the $k$th clause be (for instance, to avoid too many variables) $(x_3\lor \lnot x_7 \lor x_8)$. For have three vertices $c_1, c_2,c_3$ for the alternatives, and connect these in parallel between $v_{k-1}$ and $v_k$: edges $(v_{k-1},c_i)$ and $(c_i,v_k)$.
Now we want to be able to choose a path via $c_i$ if the corresponding variable makes the clause true: so connect $c_1$ with a back edge to $\bar x_3$,  $c_2$ with a back edge to $x_7$, and  $c_3$ with a back edge to $\bar x_8$.

This somehow reminds me of a problem called Geography, which also uses a similar reduction, but is even PSPACE complete! So, check out that reduction, for reference. Your problem has no two players, and is within NP: one easily guesses and verifies a solution in polynomial time.


I think you raise an important point, which is that in a high level language, specifications can be hard to distinguish from implementations. For example, in Coq, the specification of "The sum of the elements of a list of naturals" is probably going to look something like:

Fixpoint sum (l : List Nat) : Nat :=
  match l with
   | [] => 0
   | x::xs => x + sum xs

It's hard to imagine what the specification of this would be, other than some predicate like

 Inductive Is_Sum : Nat -> List Nat -> Prop :=
    | IS_Empty : Is_Sum 0 []
    | IS_Cons : Is_Sum s xs -> Is_Sum (x + s) (x::xs)

which really just seems like a re-formulation in terms of logic programming. Indeed it is very easy to show forall l : List Nat, Is_Sum (sum l) l.

At this point, it is indeed possible to test the definition of sum and make sure it lines up with our intuition, e.g. check sum [1,2,3] = 6. However, there is an important other step we can check in terms of "specification checking", that of proving derived properties. For sum, we could prove

Proposition sum_append : forall l1 l2, sum (l1 ++ l2) = sum l1 + sum l2

or

Proposition sum_leq : forall l x, In x l -> x <= sum l

These propositions establish the consistency of our definition against some of our intuitions, and avoid certain silly mistakes, e.g. if we had returned $1$ instead of $0$ for the empty list.

Indeed, often for our purposes the properties we actually are interested are the derived properties! Defining the full specification is only a means to an end, like strengthening the induction hypothesis.

Finally, it's probably useful to note that in real life, our specifications are often much simpler than our implementations! Indeed, if our implementations are doing nothing clever, then why do we care so much about proving them correct? (well, actually even the simplest of programs might benefit from proofs.)

One rather simple example is merge sort which while pretty straight forward, is certainly complex enough to warrant a proof of correctness, and at any rate is very different looking than its specification.


Your experiments show that 2-opt could outperform 3-opt. The reason is that there are many local optima, and some of the are better than others. Local search guarantees reaching a local optimum with respect to the moves being considered, but it doesn't provide any guarantee beyond that. It could be that one point which is locally optimal with respect to 2-opt is better than another point which is locally optimal with respect to 3-opt.

You can modify your algorithm to first try local search with respect to 2-opt and then with respect to 3-opt, and take the better solution. You could improve this by running a 3-opt local search starting at the 2-opt local minimum.

There are other degrees of freedom in the local search algorithm: for example, when there are several possible local improvements, which do you choose? A uniformly random one? The first one you found? The one which results in the best improvement? A random one chosen in proportion to the improvement? And so on. Each of these could result in a different solution. If you use a randomized strategy, each single run using the same heuristic could result in a different solution, so it makes sense to run local search many times.

An even more drastic option would be to replace local search with simulated annealing, which sometimes allows taking a local change which worsens the situation a bit. This might fare better on some instances.


Why is the period of Mersenne Twister prng $2^{19937}-1$ and not $2^{19968}$?

Here is the one-line explanation.

The number of effective bits in MT19937 is 624*32-31=19937. They cannot be all 0. So the period of MT19937 is $2^{19937}-1$.

All notations if not introduced below come from this Wikipedia article. The parameters for MT19937, (w, n, m, r) = (32, 624, 397, 31) will be used from time to time.

Explanation from the recurrence

  The series $x$ is defined as a series of w-bit quantities with the recurrence relation:
  $$x_{k+n}:=x_{k+m}\oplus \left(({x_{k}}^{u} \mid\mid {x_{k+1}}^{l})A\right)\qquad \qquad k=0,1,\ldots$$

Note the lower part of the lowest term $x_k$, ${x_k}^l$ is not used in the recurrence relation. Hence the number of effective bits used by the recurrence is $(k+n-k)w-r=nw-r$. Since 0 is excluded, the theoretical limit of period of Mersernne Twister is $2^{nw-r}-1=2^{19937}-1$.

Detailed explanation.

The above explanation is not rigorous enough because of a lack of proper reference. To convince myself, I followed the established pseudocode implementation.

// Generate the next n values from the series x_i
function twist() {
  for i from 0 to (n-1) {
    int x := (MT[i] and upper_mask)
              + (MT[(i+1) mod n] and lower_mask)
    int xA := x >> 1
    if (x mod 2) != 0 { // lowest bit of x is 1
         xA := xA xor a
    }
    MT[i] := MT[(i + m) mod n] xor xA
  }
  index := 0
}

The code above shows that the internal state of a Mersenne Twister is kept in MT[0], MT[1], ..., MT[n-1], which is an array of n values of w bits each. It seems that the period of a Mersenne Twister should be $2^{nw}=2^{19968}$.

Let us check the situation closely.

Every call to twist() will update the internal state. After each call to twist(), function extract_number() will be called $n$ times, each time extracting from MT[index] one word of w bits to output where index is one of 0, 1, ..., n-1.

How does twist() update the internal state?

the upper w-r bits of MT[0], the lower r bits of MT[1], and all bits of MT[317] are used to update MT[0].
the upper w-r bits of MT[1], the lower r bits of MT[2], and all bits of MT[318] are used to update MT[1].
the upper w-r bits of MT[2], the lower r bits of MT[3], and all bits of MT[319] are used to update MT[2].
...
the upper w-r bits of MT[306], the lower r bits of MT[307], and all bits of MT[623] are used to update MT[306].
the upper w-r bits of MT[307], the lower r bits of MT[308], and all bits of the updated MT[0] are used to update MT[307].
the upper w-r bits of MT[308], the lower r bits of MT[309], and all bits of the updated MT[1] are used to update MT[308].
...
the upper w-r bits of MT[622], the lower r bits of MT[623], and all bits of the updated MT[315] are used to update MT[622].
the upper w-r bits of MT[623], the lower r bits of updated MT[0], and all bits of the updated MT[316] are used to update MT[623].

Note that all bits in the array MT at the start of twist() are used except the lower r bits of MT[0]. So an effective internal state of MT is r bits less than all bits in array MT.  Since an effective internal state can never be all 0, the number of effective internal states is at most $2^{nw-r}-1=2^{19937}-1$, which is the theoretical limit of the period for a linear-feedback shift register like Mersenne Twister.

It is another level of interesting mathematical reasoning how MT19937 attains that theoretical limit of its period.

Another explanation by pseudocode

The following pseudocode is another implementation of Mersenne Twister.

Note the code MT[0] := MT[0] and upper_mask and MT[0] := MT[1] and upper_mask, which limits the number of effective bits in MT[0] to w-r. There are (n-1)w bits in MT[1], MT[2], ..., MT[n-1]. In total, there are (w-r)+(n-1)w = nw-r bits in the (effective) internal state of a Mersenne Twister.

// Adapted from https://en.wikipedia.org/w/index.php?title=Mersenne_Twister&oldid=896072298#Pseudocode by Apass.Jack

// Create a length n array to store the state of the generator
int[0..n-1] MT
int index := n+1
const int lower_mask = (1 << r) - 1 // That is, the binary number of r 1's
const int upper_mask = lowest w bits of (not lower_mask)

// Initialize the generator from a seed, which must be done once before repeated calls to next().
function seed_mt(int seed) {
    index := n
    MT[0] := seed
    for i from 1 to (n - 1) { // loop over each element
        MT[i] := lowest w bits of (f * (MT[i-1] xor (MT[i-1] >> (w-2))) + i)
    }
    MT[0] := MT[0] and upper_mask
}

function temper(int y) {
    y := y xor ((y >> u) and d)
    y := y xor ((y << s) and b)
    y := y xor ((y << t) and c)
    y := y xor (y >> l)

    return lowest w bits of (y)
}

function twist() {
    int x := MT[0]
              + (MT[1] and lower_mask)
    int xA := x >> 1
    if (x mod 2) != 0 { // lowest bit of x is 1
        xA := xA xor a
    }
    x := MT[m] xor xA

    MT[0] := MT[1] and upper_mask
    for i from 1 to (n-2) {
      MT[i] := MT[i+1]
    }
    MT[n-1] := x
}

// Generate the next value from the series MT[]
function next() {
    twist()
    return temper(MT[n-1])
}


What is the time complexity of an algorithm that calls a polynomial time algorithm?

I assume $n$ is the number of entries in array/set A.

Yes, since polynomials are closed against multiplication; specifically, $n(n-1) \cdot p(n)$ is always polynomially bounded as long as $p(n)$ is polynomially bounded.
As a consequence, the only way to achieve exponential running-time by calling a polynomial-time algorithm with parts of the original input is to call it exponentially often.

Example:

Foo(A)
  if |A| >= 2
    a = A[0]
    b = A[1]
    Polynomial-Time-Algorithm-Bar(A, a, b)
    Foo(A - a)
    Foo(A - b)

The number of calls to PTA-Bar is given by

$\qquad\begin{align*}
  C(0) &= 0,\\
  C(1) &= 0,\\
  C(n) &= 2C(n-1) + 1, \qquad n \geq 2,
\end{align*}$

which solves to
$C(n) = 2^{n-1} - 1$ for $n \geq 1$. Ergo, the running time of Foo is in $\Omega\bigl( 2^n \cdot p(n) \bigr)$ if PTA-Bar takes time $p(n)$.