As Wikipedia states,

  The improvement in performance gained by the use of a multi-core processor depends very much on the software algorithms used and their implementation. In particular, possible gains are limited by the fraction of the software that can run in parallel simultaneously on multiple cores; this effect is described by Amdahl's law. In the best case, so-called embarrassingly parallel problems may realize speedup factors near the number of cores, or even more if the problem is split up enough to fit within each core's cache(s), avoiding use of much slower main-system memory. Most applications, however, are not accelerated so much unless programmers invest a prohibitive amount of effort in re-factoring the whole problem.

Whether you'll see an improvement when running a particular software application depends upon how that software application is built, and whether it can make use of threads to parallelize computation.  Some can; others can't.

I don't know what the situation is for Tensorflow, but my impression is that Tensorflow tries to use your GPU if possible, because the GPU is far faster than the CPU at the kinds of tasks Tensorflow is designed for.  And, if Tensorflow is using your GPU, then there's little or no benefit to having a multiple-core CPU or multiple threads.

Parallelization can be useful for some tasks.  For instance, some video processing applications are designed to make use of multiple cores, so even if you're running only one application (the video editor application), it still runs faster with multiple cores than with a single core.  It's not just for running multiple applications at the same time.

See also https://superuser.com/q/153833/93541, https://superuser.com/q/2489/93541, https://superuser.com/q/453799/93541, and https://superuser.com/q/949030/93541 for more background.

Hyperthreading is best ignored until you understand the fundamentals of multi-core procoessors and multi-threaded applications.


Concentration bound for sum of dependent geometric random variable?

No. It is not true. If the uniformly picked edge $u$ have more neighbors, the probability of edges which have $u$ is more than others! Hence, it's not uniform. Moreover, the number of neighbors of each node is changing over time, and this can be more unbiased over the time. Therefore, your selections are not independent of each other.

A solution to uniformly removing an edge can be indexing all edges from $1$ to $|E|$ (using an adjacency list for example) and then pick a random number from $1$ to $|E|$ as your uniformly picking edge in your graph. And do it for the new graph after removing the randomly picked edge.

Hint: As uniform version will remove an edge each time, the probability in this version can be an upper-bound for the $\mathbb{P}(|E[T]-T|)$ in your solution.


For some graph classes $C$, the question "is there a fast algorithm for deciding whether a graph $G$ belongs to class $C$?" is perhaps only of theoretical curiosity. But it can also be argued otherwise: suppose a problem you care about is hard in general, but efficiently solvable for graphs of class $C$. Wouldn't it be nice if you could quickly test if you can use a fast algorithm, instead of always using a slow brute-force, for example?

In general, it is not hard to imagine some graphs arising from applications are naturally planar, like road networks, printed electric circuits, railways, or chemical molecules. For more concreteness, it seems like a good set of keywords is "planar graph applications". One of my first hits was [1] from the domain of computer vision.

[1] Schmidt, Frank R., Eno Toppe, and Daniel Cremers. "Efficient planar graph cuts with applications in computer vision." Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009.


Converting a 2-SAT formula into an implication graph

(¬x v y) = (¬y-->x)

$$\begin{align}
\text{rule: } &A \vee B &=& (\neg A \implies B)\\
& \neg x \vee y &=& (\neg\neg x \implies y)\\
& &=& (x \implies y) &(1)\\
\end{align}
$$

          = (¬x-->y)

So now this becomes:

$$\begin{align}
\text{rule: } &A \implies B &=& (\neg B \implies \neg A)\\
&(x \implies y) &=& (\neg y \implies \neg x) & (2)
\end{align}
$$

And we get:

$$\begin{align}
(x \implies y) & (1)\\
(\neg y \implies \neg x) & (2)
\end{align}
$$

And the truth table:

$$
  \left.\begin{array}{rrrr}
    x & y & (\neg x \vee y) & (x \implies y) & (\neg y \implies \neg x) \\
    0 & 0 &               1 &             1  &                   1 \\
    0 & 1 &               1 &             1  &                   1 \\
    1 & 0 &               0 &             0  &                   0 \\
    1 & 1 &               1 &             1  &                   1 \\
  \end{array}\right.
$$

As you can see they are equivalent.


generate all unlabelled trees up to size n

If you just want to define such a function, then you can just consider the equivalence relation $\rho$ where $T_1 \rho T_2$  iff $T_1$ and $T_2$ are isomorphic. Partition the set of all trees w.r.t. $\rho$. Let $C(T)$ be the equivalence class in which $T$ belongs and select one representative $T^C$ for each equivalence class $C$. Define $s(T) = T^{C(T)}$.

If you want a signature that can be easily/quickly computed, you can define one recursively. For simplicity I am going to define it over binary strings, but you can interpret this string as an integer. I am also going to assume that you are interested in rooted trees (see below if this is not the case).
If $T$ is a singleton let $s(T)=\epsilon$, where $\epsilon$ is the empty string. Otherwise let $r$ be the root of $T$ and $u_1, u_2, \dots, u_\ell$ be the children of $u$ sorted in nondecreasing order of $s(u_i$). Define: $s(T) = \bigcirc_{i=1}^\ell (1 \circ s(u_i) \circ 0)$, where $\circ$ denotes concatenation.

Algorithmically, this amounts to starting with $s(T)=\epsilon$ and performing a DFS visit of $T$:
every time that an edge $e$ is traversed append a $0$ (resp. $1$) to $s(T)$ iff $e$ is traversed away (resp. towards) the root. The order in which the children $u_1, \dots, u_\ell$ of a vertex are visited is determined by  the values of $s(u_i)$ themselves.

If you are interested in unrooted trees, then you can use the same approach by first rooting $T$ in one of its centers. If $T$ has only one center, then $s(T)$ is unique. If $T$ has two centers, you can select the one that results in the smallest value of $s(T)$ (w.r.t. the lexicographical order).

This has been used, e.g., here in Section 3.1.


You have asked (at least) two questions. The answer to your first question is that sometimes it is much easier to refute a formula given that $x=0$ compared to given $x=1$. Hence the $\max$. In other cases, $x=1$ is easier. That's why we need to go over both possible values of $b$. Finally, the reason why the formula in part 3 of the lemma also maximizes over the variable $x$ is that $x$ represents the last variable which is cut (the one at the root of the tree).

The answer to your second question is as follows. The cut rule allows deriving $a \lor b$ given $a \lor x$ and $b \lor \bar{x}$. Here $a,b$ are arbitrary formulas, in this context clauses. In particular, from $x$ and $\bar{x}$ you can conclude contradiction. The cut rule is the only rule in the resolution proof system.


How to prove NP-hardness of a longest-path problem?

Assuming I understand your definition, your problem is related to the optimisation version of LONGEST PATH:

  LONGEST PATH
  Input: A graph $G=(V,E)$, an integer $k$.
  Question: Is there a path with at least $k$ vertices in $G$

This problem is NP-complete, there's a fairly obvious reduction from HAMILTONIAN PATH - just set $k = n$, and clearly if we are given an (ordered) set of vertices, we can easily check that it is a path over at least $k$ vertices.

Note that we can assume that $G$ is connected, and we will do so from now on.

The optimization version max-LONGEST PATH where we ask for the path of maximum length is then NP-hard (the polynomial-time equivalence of these two problems is a straightforward exercise).

Then the difference between max-LONGEST PATH and your problem is that you have two specified vertices that are the start and the end of the path. Now we need a reduction from some NP-hard problem to your problem, but we already have one that's really close.

Given an instance $G$ of max-LONGEST PATH you should now be able to construct an instance $G'$ of your problem such that if $p$ is the longest path in $G$, then this is almost the longest path in $G'$.

A further hint if you are still beating your head against a wall in about, say, 2 hours:

   Try taking $G$ and adding two new vertices $s$ and $t$ and connecting them so that they can start and end such a path $p$ - remember though that you don't know what $p$ is.


Why is the array used for a restricted hashing scheme always sized to a 4k + 3 prime?

The mentioned scheme is the most probably Quadratic probing collision resolution in the Hash Table, so it is non-perfect.

The $4k + 3$ prime size of the table is to allow all cells to be probed, the size of different length will result in non accessible cells in the array, degrading performance and wasting space.

Please read about limitations of QP.


Proving that the set of deciders is not Turing-recognizable

The basic idea of the proof is to come up with a Turing machine which doesn't belong to the enumeration, hence contradicting the claim that deciders can be enumerated. To this end, we use diagonalization – for each potential machine in the enumerate, we ensure that there is at least one input on which the diagonalizing machine has a different behavior.

If the diagonalizing machine $D$ has alphabet $\Sigma$, then we already know that any machine in the enumeration with a different alphabet cannot be $D$. Therefore $D$ doesn't care much about these machines. What $D$ has to ensure is that for every machine $M_i$ with alphabet $\Sigma$ there is an input $x_i$ such that $D(x_i) \neq M_i(x_i)$.


Keywords for classification of 2D time series data?

The one-nearest neighbor classifier is very competitive for time series.
http://www.cs.ucr.edu/~eamonn/ICML2006.pdf
If you want code or data, I have lots of both.
eamonn


What is an algorithm to find the largest rectangle of white space in an image?

Subtract $254.9999999$ from all pixel values, so black corresponds to $-254.9999999$ and white to $0.0000001$.

Find the 2D subrectangle with maximum sum.  There are standard $O(n^3)$-time algorithms for this problem (e.g., https://stackoverflow.com/q/19064133/781723, https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/).  As long as you have no more than 10,000,000 pixels in the image, this will be the solution to your problem (since each white pixel contributes another $0.0000001$ to the sum).

Proof that this finds the optimal solution: only all-white subrectangles have a positive sum (if  you have a single non-white pixel, then its contributes a negative value of $-0.9999999$ or lower to the sum, which cannot be outweighed by any number of white pixels); and the larger the all-white subrectangle, the larger its sum.


DFA for words with $a$s not a multiple of 3 and at least one $c$

The product construction is a way of taking two DFAs for languages $L_1,L_2$, and constructing a new DFA for the language $L_1 \cup L_2$ or $L_1 \cap L_2$. In your case, $L_1$ consists of all words in which the number of $a$s is not a multiple of 3, and $L_2$ consists of all words containing at least one $c$. You have already constructed a DFA for $L_1$. Construct one for $L_2$, and use the product construction to construct one for $L_1 \cap L_2$.


Let's analyze how many hash bits you need in your new scheme versus a Bloom filter.

First of all, we need to agree about terminology.  I will use $q$ to represent the probability of a false positive.

For a Bloom filter the design problem of choosing $m$ and $k$ given that you want to hold $n$ elements with false positive rate $q$ is solved by $k = -\lg_2 q$ as the number of hashes, and $m=\frac{n k}{\ln 2}$ bits for the table.  (See the wikipedia page or several of the previous cs.se questions about Bloom filters.)  (This works out to a table with maximum entropy: your table is about half 1s and half 0s after $n$ insertions.)  The number of hash bits you need to produce per insertion is $k \lg_2 m$

Now your structure:  Let's assume that the desired $n$ and $q$ are the same.  $k$ and $m$ are going to be about the same, but now $k$ is going to be the average number of bits that remain set after ANDing your $b$ independent $m$-bit hashes.  How big does $b$ need to be?  Well you want the probability of any particular bit in your final hash to be about $k/m = p = 2^{-b}$.  So $b = -\lg_2 k/m = \lg_2 m - \lg_2 k$.  But that means that you have to generate $b m = m(\lg_2m-\lg_2k)$ hash bits, which is way more than $k \lg_2 m$.  For example, if $n = 709$ and $q = 1/16$ then $k = 4$ and $m = 4096$.  So a bloom filter would require $4 \times 12 = 48$ bits of hash, while your scheme requires $b = 10$ and a total of $40960$ bits of hashing.

Worse, there are some elements whose hash works out to 0 (i.e., whenever you look them up the probability of getting a false positive is 100%).  Suppose I AND together 10 different bit vectors of length $m$.  The probability that each bit will be set to 1 is 1/1024.  The probability that all the bits will be set to 0 is $(\frac{1023}{1024})^{4096}\approx e^{-k} \approx 0.0183$.


For 2D cameras, you can't.  There's a reason why the matrices only give constraints that let you say that point p in i1 must lie on line l in i2 -- that's because that's all you can say.

In particular, for a particular point p in image i1, with 2D cameras, you don't know the depth of the corresponding object.  The depth affects where it appears in image i2, so without knowing the depth, you can't know which pixel in i2 corresponds to p.  If the object is very close, then there might be a very large offset; if the object is very far away, there might be a very small offset.

This is in fact the basis of binocular vision.  Some 3D sensing methods work by somehow finding the correspondence using various heuristics (e.g., image similarity metrics), and then using this to infer the depth of the object.

So, the intrinsic and extrinsic parameters are not enough to uniquely deduce the correspondence, if both cameras are 2D cameras.  With a 3D camera, this problem can be solved.


How exactly Hashing performs better than a Binary Search?

You are asking excellent questions!

The answer to your first question, regarding the difference between $O(\log n)$ and $O(1)$, is that whereas binary search scales with the size of the array, searching for an item in a hash table scales with the size of the data item, which we often think of as constant. In practice, calculating the hash also takes time (as you also mention), and so to know which data structure has better performance, we need to empirically compare implementations of both data structures.

The answer to your second question, about the time complexity of computing the hash function, is that it takes time linear in the size of the data item. Most hash functions used in this context are "rolling hash", in which a small has value is being updated as the data item is read. This ensures that the time complexity is indeed linear. Hash functions for such uses are designed with speed in mind, and so usually memory access is not an issue. The division operation at the end – if at all – is not too costly for modern CPUs, and can be avoided entirely if the size of the hash table is a power of 2.


Why is Boolean satisfiability such a rare case?

Your trick doesn't really work.  There are several issues.

First, your trick shows that for every unsatisfiable circuit of size $n$, there exists a satisfiable circuit of size $n+1$.  But that doesn't tell you anything about the relationship between the number of unsatisfiable circuits of size $n$ vs the number of satisfiable circuits of size $n$.  And, in general, there are way more circuits of size $n+1$ than circuits of size $n$, and most circuits are satisfiable, so the mapping you've found doesn't prove what you want it to prove.  To prove what you're trying to prove, you'd need to find a bijection between unsatisfiable circuits of size $n$ and satisfiable circuits of size $n$ (not $n+1$); no such bijection exists.

Second, the mapping you describe isn't a bijection.  Consider for example the circuit $\phi(x) = x$.  This is satisfiable.  Slapping a "not" in front if it, to get $\phi'(x) = \neg x$, yields another circuit that is also satisfiable.  Many circuits are both satisfiable (there exists an assignment that makes $\phi$ true) and their-complement-is-satisfiable (there exists a different assignment that makes $\phi$ false).  So negating an unsatisfiable circuit makes it satisfiable, but negating a satisfiable circuit doesn't necessarily make it unsatisfiable.

Finally, there's the distinction between circuits vs formulas, as David Richerby explains.  If you negate the output of a CNF formula, the result isn't a CNF formula.


Minimum number of sets of unreachable vertices for directed acyclic graph (DAG)

The problem is fixed-parameter tractable, where the parameter is the number of output sets.

Define an undirected graph $G'$ with an edge $(v,w)$ for each unreachable pair of vertices in the original graph.  Now you want to find a minimal edge clique cover of $G'$.  The minimal edge clique cover problem is fixed-parameter tractable, where the parameter is the number of cliques.

I don't know if there is a polynomial-time algorithm.  The minimal edge clique cover problem is NP-complete for general graphs.  I don't know if $G'$ has any special properties that makes the minimal edge clique cover problem easy on it.  (It's not necessarily chordal, unfortunately.)


Minimize the maximum component of a sum of vectors

We cannot discuss the complexity of a problem when the problem size is fixed to a constant, because (most part of) the complexity theory deals with the asymptotic behavior of the complexity of the problem as the problem size tends to infinity.  Here, I consider both the number of rows and the dimention of the vectors as variables.

Then the problem is NP-complete even if the numbers in the input are given in unary.  This is not an answer to your question because you are asking about approximation, but it is something.

Define the problem rigorously:

Instance: n pairs of vectors ai, bi ∈ ℕm (i ∈ {1, …, n}), and K ∈ ℕ, all in unary.
Question: Can we choose either ai or bi for each i so that the sum of these n vectors has at most K in each coordinate?

The following is a known NP-complete problem called 3-partition:

3-partition
Instance: B ∈ ℕ, and 3k integers c1, …, c3k between B/4 and B/2, exclusive, such that ∑i=13k ci = kB, all in unary.
Question: Can the multiset {c1, …, c3k} be partitioned into k multisets S1, …, Sk such that the sum of each Sj is equal to B?

Given an instance (B; c1, …, c3k) of the 3-partition problem, construct an instance of the above problem as follows.  For each i = 1, …, 3k and j = 1, …, k, we will construct a pair of 4k-dimensional vectors, representing the choice on whether ci belongs to Sj or not:

The vector representing the choice “ci ∈ Sj” has only one nonzero entry, which is (k−1)ci at the jth coordinate.
The vector representing the choice “ci ∉ Sj” also has only one nonzero entry, which is B at the (k+i)-th coordinate.

It is not hard to see that the instance (B; c1, …, c3k) of the 3-partition problem has a solution if and only if there is a way to choose a vector from each of the 3k2 constructed pairs so that all the coordinates of the sum of these vectors are at most (k−1)B.  (In fact, when this happens, all the coordinates of the sum are equal to (k−1)B.)  So this is a reduction from the 3-partition problem to the above problem.

So far, I ignored the two additional constraints stated at the end of the question, but both are easy to enforce by modifying this reduction slightly.  The condition that the sum of the elements of each vector is equal can be enforced by appending dummy coordinates which contain only 0 or 1.  The condition that this sum is less than the dimension can be enforced by appending dummy coordinates which contain only 0.


How can a language whose compiler is written in C ever be faster than C?

There is no necessary relation between the implementation of the compiler and the output of the compiler. You could write a compiler in a language like Python or Ruby, whose most common implementations are very slow, and that compiler could output highly optimized machine code capable of outperforming C. The compiler itself would take a long time to run, because its code is written in a slow language. (To be more precise, written in a language with a slow implementation. Languages aren't really inherently fast or slow, as Raphael points out in a comment. I expand on this idea below.) The compiled program would be as fast as its own implementation allowed—we could write a compiler in Python that generates the same machine code as a Fortran compiler, and our compiled programs would be as fast as Fortran, even though they would take a long time to compile.

It's a different story if we're talking about an interpreter. Interpreters have to be running while the program they're interpreting is running, so there is a connection between the language in which the interpreter is implemented and the performance of the interpreted code. It takes some clever runtime optimization to make an interpreted language which runs faster than the language in which the interpreter is implemented, and the final performance can depend on how amenable a piece of code is to this kind of optimization. Many languages, such as Java and C#, use runtimes with a hybrid model which combines some of the benefits of interpreters with some of the benefits of compilers.

As a concrete example, let's look more closely at Python. Python has several implementations. The most common is CPython, a bytecode interpreter written in C. There's also PyPy, which is written in a specialized dialect of Python called RPython, and which uses a hybrid compilation model somewhat like the JVM. PyPy is much faster than CPython in most benchmarks; it uses all sorts of amazing tricks to optimize the code at runtime. However, the Python language which PyPy runs is exactly the same Python language that CPython runs, barring a few differences which don't affect performance.

Suppose we wrote a compiler in the Python language for Fortran. Our compiler produces the same machine code as GFortran. Now we compile a Fortran program. We can run our compiler on top of CPython, or we can run it on PyPy, since it's written in Python and both of these implementations run the same Python language. What we'll find is that if we run our compiler on CPython, then run it on PyPy, then compile the same Fortran source with GFortran, we'll get exactly the same machine code all three times, so the compiled program will always run at around the same speed. However, the time it takes to produce that compiled program will be different. CPython will most likely take longer than PyPy, and PyPy will most likely take longer than GFortran, even though all of them will output the same machine code at the end.

From scanning the Julia website's benchmark table, it looks like none of the  languages running on interpreters (Python, R, Matlab/Octave, Javascript) have any benchmarks where they beat C. This is generally consistent with what I'd expect to see, although I could imagine code written with Python's highly optimized Numpy library (written in C and Fortran) beating some possible C implementations of similar code. The languages which are equal to or better than C are being compiled (Fortran, Julia) or using a hybrid model with partial compilation (Java, and probably LuaJIT). PyPy also uses a hybrid model, so it's entirely possible that if we ran the same Python code on PyPy instead of CPython, we'd actually see it beat C on some benchmarks.


How to analyse the complexity of a problem with two or more size measures

There's nothing wrong with your approach. You have a two-variable function with a known (almost, up to a multiplicative constant) upper bound. In that case, it's perfectly acceptable to take a "slice" through the function by holding one of the variables fixed and ask how the resulting one-variable function behaves. One does this sort of thing often, when, for example, we take the derivative of $f(x, y)$ with respect to $x$.


Finding the lightest simple path in trees with integer weights

Order the tree, so we can speak about a node and its subtrees. Now evaluate the tree recursively. In each node keep track of two values: (1) the value of the optimal path below the node (starting and ending somewhere below in the subtrees), and (2) the value of the optimal path below that additionally ends in the node itself.


How can I do a subtraction on unary numbers terminated in X on turing machine?

First of all, notice that if you have to compute $N-M$ you can subtract one from each operand and the result will not change (i.e. $N-M = (N-1) - (M-1)$.
Keeping that in mind, I would remove a 1 from each operand replacing it with another symbol Y just to avoid spaces on the tape, and repeat until either operand "runs out" of ones --that means that either $N$ or $M$ is now zero. When it happens, clean out the tape a little bit: the left operand is the result of the computation.
So, executing this algorithm in your examples:
example 1
11X1111X input
Y1XY111X
YYXYY11X notice that the left operand is zero
  X      cleanup

example 2
1111XX input
Y111XX notice that the right operand is zero
1111X  cleanup

As you can see from the second example, if the first operand is bigger than the second you will have to revert the last substitution replacing a Y with a 1.
Another meaningful example:
1111111X1111X input
Y111111XY111X
YY11111XYY11X
YYY1111XYYY1X
YYYY111XYYYYX
YYYYY11XYYYYX notice that the right operand is zero
    111X      cleanup

As for the actual program, here is just a sketch, try to write it yourself:

in q0 search for a 1 to replace. That means, skip all the Ys and continue moving right until you find a 1, then don't move and go to q1.
in q1 replace the 1 with a Y, then move right and go in another state (q2) to reach the other operand.
in q2, go right until you find an X (that means you have reach the second operand), then move right and go to q0 to remove a 1 from the second operand too.

This part will replace a 1 from both operands (if there are enough ones), the states of the machines are q0 -> q1 -> q2 -> q0 -> q1 -> q2.
At this point the scanner is placed at the end of the input string, you realize it when you find an empty cell in q2, so;

in q2, if you find an empty cell, move left and go to q3 (which will move the scanner at the beginning of the input).
in q3 move left ignoring any character until you find an empty cell. That means you have reached the beginning of the string. Move right and go to q0.

This loop continues until either operand runs out of 1s. You realize it when you find an X in q0, so:

in q0 if you find an X, move right and go to q4 that is the state that initializes the cleanup part
in q4 move right ignoring any character until you find an empty cell, that means you have reached end of the input, move left and go to q5 to perform the cleanup phase.

Complete the program as an exercise: if you want you can edit this answer to add the sketch of the cleanup phase.


The problem is NP-hard by a reduction from hitting set. Thus, there is no efficient or "easy" algorithm in this sense. Of course, any algorithm you might execute with pen and paper can also be realized on a computer.

With that being said, just try all possibilities by hand. As you observe, it is easy to see if the solution is of size one or two. It can get much more tedious after that, and the reason is NP-hardness.


The statement

  Determining a that a Graph is not Hamiltonian is in NP-Class.

is neither true nor false. It doesn't have a truth value, since there's a type mismatch. Similarly, the statement

  The color red is in NP.

is neither true nor false.

Here is something which is true. Let $L$ be the language of all Hamiltonian graphs. That is, $x \in L$ if $x$ encodes a Hamiltonian graph. (We fix the encoding once and for all.) The language $L$ is in NP since to prove that $x \in L$, one just needs to present a Hamiltonian circuit (a proof whose size is polynomial in the input size), and this proof can be verified in polynomial time.

Furthermore, $L$ is NP-complete. The book you're consulting probably has a proof. Therefore, if $L$ were in coNP, then NP=coNP, which is believed to be false. So it is probably the case that $L$ is not in coNP. But we don't know for sure.

The language $L'$ of non-Hamiltonian graphs is the complement of $L$ (modulo boring technicalities arising from the fact that not every string encodes a graph). Since $L$ is NP, $L'$ is in coNP. We can also see it directly: to prove that $x \notin L'$, one just needs to present a Hamiltonian circuit.

Furthermore, $L'$ is coNP-complete, since $L$ is NP-complete. Again, it is probably the case that $L'$ is not in coNP, since otherwise NP=coNP, which is believed to be false.


Is it possible to do multitasking without context switch with just one cpu?

Yes, it is possible (depending upon what you mean by "context switch").  See cooperative multi-tasking.  In cooperative multi-tasking, the operating system never needs to perform a context switch between tasks -- instead, tasks voluntarily take care of saving their own state and switching between themselves.


This is related to a well known problem with a conjecture due to Karpovsky and Moskalev [1] (I still believe is open) that at most V-1 paths are needed.  It is tied to conjector of Erdos, Goodman, and Posa [2].

If you want the state of the art today, I suggest doing a thorough reverse-citation search on [1].

[1] Karpovsky, M. G., and E. A. Moskalev. "Covering of edges of graph by a minimal set of paths." Discr. Math 58.2 (1986): 214. (This is in the "research problems" section)

[2] Erdos, Paul, Adolph W. Goodman, and Louis Pósa. "The representation of a graph by set intersections." Canad. J. Math 18.106-112 (1966): 86.


First, notice that, in trees, the path between any pair of vertices is unique. This means that the sub-forest you want is the union of these paths.

To find them, do the following:

Pick any vertex to be the root of the tree.  Orient all the edges towards the root and store the distance from the root at each vertex.
To process a pair $(u_i,v_i)$ start a walk towards the root from the element of the pair that is farther from it.  (Break ties arbitrarily.)  As you walk, mark edges.  If the walk reaches the other item of the pair, stop.  Otherwise do the same thing from the other item of the pair.
Once all the pairs are processed, output the marked edges.

This is correct, since either $u_i$ and $v_i$ are on a path towards the root or the path between them goes through the root.  It's also too slow, since we may end up walking over the same edge multiple times, so we end up with $O(n^2)$ running time.

To speed this up, we can just use a union-find data structure.  The edges are partitioned into classes labeled by the lowest vertex they can reach by a path of marked edges.  Now when we walk, we can skip upwards every time we encounter a marked edge, at the same time merging any classes that we need to.

With this scheme, marked edges are encountered at most twice, so get a total of $O(\alpha(n)n)$, where $\alpha$ is the inverse Ackermann function.


The sets that can be defined this way are called rational.
As an example, the pairs of input-output strings $(u,v) \in \Sigma^*\times\Delta^*$ of accepted computations in finite state automata on two tapes define rational subsets in $\Sigma^*\times\Delta^*$ (with pair-wise concatenation as monoid operation). The word problem in $\Sigma^*\times\Delta^*$ is trivially decidable, but equality for their rational languages (of pairs of words) is not.

A special collection of monoids that were extensively studied for their rational language decision problems are the so-called trace monoids (or free partially commutative monoids). A special case of these monoids is $\Sigma^*\times\Delta^*$.

An overview of the literature in that area is given by Sakarovich, in his paper "The "last" decision problem for rational trace languages".


Load and Store Data hazard problem in 5-stages pipeline

Assuming the stages are IF, ID, EX, MEM and WB, I believe the Load instruction cannot be carried out until the value has been written back in the first instruction i.e the WB stage.

This is what happens in the ID stage (from Hennessey-Patterson, Computer Architecture - A Quantitative Approach 4 ed.):

  Decode the instruction and read the registers corresponding to register source specifiers from the register file.

Since we have to read the registers in the ID stage, this cannot be done until the WB stage of the previous instruction has been completed as otherwise, it would lead to reading an incorrect value.

EDIT: On further notice, I've realised this might be incorrect. I wrote this answer under the assumption that the Store instruction passes through all the five pipeline stages. However, here, it is mentioned that:

  The store instruction stores to memory, so the "write" is performed inside MA.

So it won't have to wait till the WB stage, it can read the value after the MEM stage of the previous instruction.

That being said, more details about the instruction set would be helpful and how exactly are Load and Store defined would be helpful.


I had the same problem when I was an undergrad. I can see you understand the algorithm. And, to prove that it works is to explain it formally that it works.

Why we have many proofs ? because we may have algorithms that are not correct, and we need to show that our algorithm is correct and actually work always!.

Same for the analysis. If we want to prove for example that our algorithm is better than others, then we prove it. You may tell me that we can implement our algorithm and and test it, but this does not consider all the possible cases of input. Therefore, what we do is to prove it.

(We usually prove the correctness and complexity of an algorithm (which is a measure of its performance)).

This is just an answer for your second question. For your first question, a hint is to say why we will visit every other vertex if the graph is connected. [Hint: because the graph is connected than for every pair of vertices there is a path.] ...(back to your second question).. if you note here that I am using one fact to prove my original fact (i.e., there is a path connecting every pair of nodes --> DFS is correct). The first fact is clear in our case given the definition of connectivity. In many other cases, it is not clear. So we will need to prove one fact by proving another, and perhaps do that again and again. This is why we have a lot of lemmas and theorems.

They are boring now. but once you see their magic, you will love them ! As a fun excercise try to solve simple algorithmic problems and prove their correctness and analyses. To verify your answers, re-read your answers. If they convince you, then you are correct. If not, then re-do it again.


If there is just one symbol which can appear on the tape, then nothing about the tape can ever change. Thus, the tape is absolutely useless, and you are left with a finite bidirectional automaton.
However, the blank symbol $\bot$ is often treated as a special case. We could thus consider the situation where each cell on the tape can carry either $0$ or $\bot$, and where we can write a $0$ on a place previously containing a $\bot$, but we can never erase a $0$ and return that cell content to $\bot$. This is as close to unary as we can really get for a TM.
As long as we only consider decision problems, these machines still have the full power. Essentially, the idea is to insert a bunch of auxiliary bits between the bits containing the actual content, and then so simply copy everything to a fresh chunk of tape whenever we need to erase a bit, except for the bit to be erased.
Having a finite number of tape symbols greater than 1 doesn't make much a difference. So binary is just special here because its the smallest alphabet that easily works.


Modifying Dijkstra’s algorithm to favor the path with least amount of edges

Yes, it should. You can simply keep a count of edges traveled. If you discover a new shortest path which is of the same distance as the last shortest path, make an if statement asking whether or not the new path has less number of edges. Here is a short pseudo code that you can use in the "relaxation" part of algorithm.

if (new_path == shortest_path && new_path_edges < shortest_path_edges)
    shortest_path= new_path
elseif (new_path < shortest_path)
    //The relaxation part of Dijkstra's algorithm

EDIT. Fuller answer below.

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:
 3          dist[v]      := infinity;
            dist_edges[v]:= 0;
 4          visited[v]   := false;
 5          previous[v]  := undefined;
 6      end for
 7
 8      dist[source]  := 0;
        dist_edges[source] := 0;
 9      insert source into Q;
10
11      while Q is not empty:
12          u := vertex in Q with smallest distance in dist[] and has not been visited;
13          remove u from Q;
14          visited[u] := true
15
16          for each neighbor v of u:
17              alt := dist[u] + dist_between(u, v);
                alt_edges := dist_edges[u] + 1; //Note the increment by 1
                if (alt = dist[v] && alt_edges < dist_edges[v])
                    previous[v] := u;
                    dist_edges[v]= alt_edges
18              if alt < dist[v]:
19                  dist[v]  := alt;
                    dist_edges[v] := alt_edges;
20                  previous[v]  := u;
21                  if !visited[v]:
22                       insert v into Q;
23                  end if
24              end if
25          end for
26      end while
27      return dist;
28  endfunction


The class of languages that can be certified in a small amount of space

(Note that X is not known to differ from NP.)  Yes - X is equal to PSPACE.  In fact, one gets that from just brute force, rather than needing Savitch's theorem.

You might also be interested in NL, which is only known to satisfy

L  $\subseteq$  NL  $\subseteq$  coNLOGLOGTIME-uniform SAC1   .

(Note that, to get a certificate characterization of NL, we probably must

"restrict the verifier to have one-way access to the certificate".)


Constructing preorder traversal from postorder of a Binary Search Tree in O(n)

This can indeed be solved in $O(n)$ time. What you mentioned (checking value of root, calling recursively for left and right subtree) almost works, the issue is just that we don't know the size of the right subtree, so we cannot immediately recursively solve the left subtree as we don't know where it ends. But this is not an issue: Just recursively solve the right subtree first, then have that return the subtree's size.

The following C++ program should solve the problem in $O(n)$. Please note that while I tested a few inputs but there could be bugs, though the idea behind the algorithm works for sure.

#include <iostream>
#include <vector>
using namespace std;

// Finds preorder traversal of a subtree of a binary search tree given the postorder traversal
// res: Vector to write preorder traversal to
// postorder: Vector containing the postorder traversal
// j: Position in array to write last node in preorder traversal to
// hv: Maximum value of a node in this subtree
// lv: Minimum value of a node in this subtree
// b: Position where this subtree ends in the postorder traversal
// Returns size of the subtree called on
int preorder(int b, int lv, int hv, int j, const vector<int>& postorder, vector<int>& res) {
    if (b < 0 || postorder[b] < lv || postorder[b] > hv) return 0;
    int rs = preorder(b-1, postorder[b], hv, j, postorder, res); // Size of     right subtree
    int ls = preorder(b-1-rs, lv, postorder[b], j - rs, postorder, res); // Size of left subtree
    res[j - ls - rs] = postorder[b];
    return ls + rs + 1;
}

int main() {
    int n; // Size of the tree
    cin >> n;

    vector<int> po(n); // Postorder
    for (int i = 0; i < n; ++i) cin >> po[i];

    int lv = po[0]; // Minimum value in the tree
    int hv = po[0]; // Maximum value in the tree
    for (int i = 0; i < n; ++i) {
        lv = min(lv, po[i]);
        hv = max(hv, po[i]);
    }

    vector<int> res(n); // Preorder
    preorder(n-1, lv, hv, n-1, po, res);
    for (auto v : res) cout << v << ' ';
    cout << '\n';
}

This is clearly $O(n)$, since the function "preorder" gets called exactly once per node, and (outside recursive calls) does $O(1)$ work.


Least common multiple of a list of numbers

Suppose that we are interested in the LCM of all numbers from $1$ to $n$. It is not hard to check that the answer is the product of $p^{k_p}$ for all primes $p \leq n$, where $k_p$ is the largest integer such that $p^{k_p} \leq n$. For example, the primes at most 10 are $2,3,5,7$, and so the answer is
$$
2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520.
$$
Similarly, the primes at most 20 are $2,3,5,7,11,13,17,19$, and so the answer is
$$
2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19.
$$


Can a Language be determined by its kleene closure?

Consider $L_1 = \{a\}$ and $L_2 = \{a, aa\}$. In this case $L_1^* = L_2^*$. Thus a language is not uniquely determined from its Kleene closure.

Moreover you cannot determine a lot of information about a language from simply querying an oracle. Even if you had access to an oracle for $L$ itself rather than $L^*$, you would not learn much.

That is because you can only ever do a finite number of queries to the oracle. So for a finite number of strings, you know if they are in the language. It could be that every string, which you did not query, is in the language, which would make $L$ regular. Or it could be that none of the strings, which you did not query are in the language, which would also make $L$ regular. It is also possible to simply pick any arbitrary regular language $L'$ and assume that the rest of the strings are in $L$ if they are in $L'$ and vice versa. In that case $L$ would also be regular, because adding or removing a finite number of strings from a regular language would also produce a regular language.

The parts of $L$ which you did not yet query the oracle about could also have a non-regular structure, it could even be non-computable.

There are properties about $L$ which could help. For example if a property about $L$ was stated in such a way, that there would only be a finite number of languages satisfying the property, the problem would get a lot simpler.

For certain properties about $L$, it would even be possible to identify an $L$ from an infinite set of candidates, however such an algorithm would not necessarily terminate, if given an input not satisfying the property.

For example if it is required that $L$ consists of exactly one string, there are infinitely many candidate languages, but knowing the alphabet, it is possible to search for this string and find it in finite time. If this algorithm was executed on $Ø$ (which does not satisfy the property), the algorithm would never terminate.


A good rule of thumb is to use Church's thesis: can you personally solve the problem? While this is of course informal, in practice it works very well after you develop a bit of experience with Turing machines. (That said, ultimately the theorem you'll learn and use here is Rice's theorem.)

By way of example, let's first consider the following two sets:

Those Turing machines which halt (on input $0$) in at most $42$ steps.
Those Turing machines which halt (on input $0$) and output $42$.

It should be fairly easy to see that we can informally compute the former: given a Turing machine, just run it on input $0$ for $42$ steps and see what happens. The latter, though, is harder: if I'm presented with a candidate Turing machine, if I know it halts I can run it until it halts and check whether the output is $42$, but in the absence of that information I seem to be stuck since I don't see a way around the infinite search involved in "wait until it halts, if it ever does."

So now let's look at a couple candidates on your list.

(1): in principle, we'd need to check each possible input to be confident that a Turing machine has the desired property: a single counterexample tells is it doesn't, but we don't know where such a counterexample might be and so as we go along checking all possible strings we'll never be fully confident that there isn't a counterexample (= a string of odd length which is accepted) which we just haven't found yet.
(2): Here, there are only finitely many things we need to check, namely all those strings of length $<2019$. However, think about what's involved in checking a single candidate: the only a priori way to tell that a Turing machine doesn't accept a string is to run it forever, and "at the end of forever" you'll know that it in fact doesn't accept that string, but that's clearly bonkers. So there's still an infinite search involved, and this appears undecidable.

Now how do we make further distinctions between the undecidable sets - in particular, between semidecidable (more commonly, computably enumerable) and not-even-semidecidable?

Again, Church's thesis is the key: is it the case that, in order to be certain that something is in our set, we need to see some finite amount of information? If so, then it's computably enumerable. Otherwise, it's not - and in particular, if it's falsified by a counterexample (instead of verified by a witness) its complement is computably enumerable. So our Church's thesis analysis of (1) and (2) says that each is not even computably enumerable.


Hint: What's the size of the state space?

The state of the world at any point is determined by _____.  Therefore, there are ____ many possible states.

Fill in the blanks, then think about how to use those facts to help you devise an algorithm.


How does $n^c \lg n, 0<c<1$ compare to other common time complexities

$O(n^c \log n)$ is above $O(n^c)$ but below $O(n^{c+\varepsilon})$ for any $\varepsilon > 0$. This is true for any $c \geq 0$, including $c < 1$.

For example, $n^{0.5} \log n$ is not in $O(n^{0.5})$ but is in $O(n^{0.500001})$.

This is one of the reasons for the invention of the "soft O" notation $\tilde{O}(n^c)$, defined as the union of $O(n^c (\log n)^d)$ for all $d \geq 0$. Soft O allows you to fudge log factors and focus on the most important part, which is the highest-order polynomial exponent.


TF IDF Spark values are small after cosine similarity

From the
documentation:

  Since logarithm is used, if a term appears in all documents, its IDF value becomes 0.

So if you're only considering similarity between two strings, then you only have one document in your corpus, and either your TF value will be 0 (since the word doesn't appear in the document), or the IDF value will be 0 (since the word does appear in the document), thus all terms in TF-IDF will be 0.

If you just have two strings, then cosine similarity should be enough for you - IDF is attempting to weigh the relative importance of each word within the entire corpus (from an information theoretic perspective, it basically treats the word as appearing uniformly across the documents it appears in within the corpus - under that assumption, one can consider IDF to be a form of information gain; i.e., how many bits of information does having this term gain you, relative to selecting a document at random from within the whole corpus. If every document in the corpus has a term, then under that uniform model, providing that term in the query doesn't help you at all in narrowing down your selection).


Show that $L$ and $\overline L$ cannot be both finite

If $L$ and $\overline{L}$ were both finite, then so would $\Sigma^* = L \cup \overline{L}$ be, which we know is false.
This is a qualitative statement. We can make it quantitative by considering densities. Let us say that a language is dense if for infinitely many $n$, it contains at least half the words of length $n$. It is easy to check that at least one of $L,\overline{L}$ is dense.


Show that C(n) = {a^k | k is a multiple of n} is a regular language

It’s easy to construct a DFA which recognize $a^n$.

Then add an $\epsilon$ transition from all its final state to its initial state.


Procedure for finding if Overflow occurs on addition

I found the solution and have answered it here

The final answer is

(((NOT a) AND (NOT b) AND s) OR (a AND b AND (NOT s))) AND 1000


That's probably not what was meant by "round".  I suspect "round" probably meant to round to the nearest single-precision float.  In particular, you can easily verify that 41 is the smallest number with this property:

>>> from numpy import *
>>> float32(float32(1.0/3.0)*3.0)
1.0
>>> float32(float32(1.0/40.0)*40.0)
1.0
>>> float32(float32(1.0/41.0)*41.0)
0.99999994

But you should double-check the definition of the function round() with whoever told you this problem.  We can't read their mind.


Guessing the best choice to maximize returns

One simple way, better than random choice, is to use modification of one step ExpectiMax. Each round you will give each Objects Value some new estimated value V(obj).

V(obj)= $\frac{ObjectValue(obj)}{ ( 1+ \sum\limits_{i=1}^n P_{i}(obj) )}$

where $ P_{i}(obj)$ = probability that person i will chose Object obj

And every round you will chose the one Object with greatest estimated value V.

You can choose at the beginning  $ P_{i}(obj)$ to be some function over the Object Value- the bigger the value the greatest probability that it will be picked.

Learning:

From your question "Note that keeping track of other player's decisions and their accumulated values can help in future decision making." and your comment  "(learning opponent strategy under uncertainty) " I guess that you need to learn the strategies of your opponents.

One way is after each game to see which Object Value was picked by each of your opponents and how the picked value differs from your expectations ($ P_{i}(obj)$). Using this information you can slightly modify the probabilities $ P_{i}(obj)$ (decrease or increase them a little for specific Object Values) and use the improved probabilities for each of the opponent in the next rounds s.


Restricted traversal on an undirected graph

Yes, here's an algorithm for that.  Construct a new graph $G' = (V\times V, E')$ where you have an edge $(u,v) \to (v,w)$ for each triple of vertices $u,v,w \in V$ such that $(u,v) \in E$, $(v,w) \in E$, and $w((u,v),v,(v,w))=1$.  Now look for the shortest path in $G'$.  This graph basically keeps track of the current node and the previous node; the node $(u,v)$ in $G'$ corresponds to a traversal in $G$ where the current node is $v$ and the previous node was $u$.

If you know finite automata, this is basically a product construction (parallel composition).


Algorithm to find out if a set contains two number with sum in the same set using a blackbox function

Your question is essentially answered on the Wikipedia page on the 3SUM problem, specifically the part on 3 different arrays.


When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$

You're absolutely right that $\Theta$ is the tightest asymptotic bound. But it's still asymptotic, and that means that we don't care about constant factors or terms of lower degree: when $n$ (or $v$ or whatever) gets big enough, the smaller terms become negligible.

In this case, $\frac{v(v-1)}{2} = \frac{1}{2} v^2 + \frac{-1}{2} v$. So removing the constant factors and lower terms leaves us with $v^2$.


How many neurons is needed for UAT to hold?

There is not a particular number. You have to decide how much you want to approximate your function.

UAT, in informal language, means that neural network can approximate any given function f when given appropriate parameters (which are to be found experimentally; their learnability isn't a question here!).

If you have a function of 3 variables, then a neural network with 20 neurons may approximate it far better than one with the 10 neurons. It is possible that after a certain number of neurons, the difference between the outputs, i.e., (F - f) becomes very less.

I answer this question following Occam's razor, thus not mentioning any un-necessary terms. Please ask, if you have any additional or specific questions in it.


Difference between hypervisor and exokernel

The thing that runs on top of a hypervisor is one or more full operating systems.  A hypervisor virtualizes the hardware, so that each operating system is "tricked" into believing that it has an entire machine to itself.  The engineering genius that goes into hypervisors is how to provide this virtualization at little or no cost (compared to running one operating system directly on the physical hardware.)

The thing that runs on top of an exokernel is a bunch of user-level processes.  The processes each attach to a library (maybe the same library maybe different libraries) that provide various services and policies.  The goal of the exokernel is to provide only protection (keeping one process from using the resources devoted to a different process,)  and leave user-level programs to select the policies that were most efficient for them.  Exokernel was really a research project whose main output was a series of studies about different kinds of operating system services and the barriers to implementing those services efficiently.  Another way to view the Exokernel project was that it was a project to investigate how to make a microkernel that isn't dreadfully inefficient and slow.

One of the big problems with microkernels is that they are constantly "crossing process boundaries" and/or switching back and forth between user mode and kernel mode more frequently than would a monolithic kernel (like Linux.)  The cost of switching from user mode to kernel mode or from kernel mode to user mode is surprisingly high (in the 1000s of machine cycles per switch).

It's not clear to me to what degree the Exokernel project succeeded or failed.  There are certainly several cases where they came up with surprising new ways to provide resource protection (like their disk model where the operating system manages permissions for disk blocks and the entire file system is managed at user level).  They also were able to leverage several of the good ideas from around that time, for example, Carl Waldsburger's Lottery Scheduling techniques.  And there were some cases in which capability-based protection turned out to be pretty efficient.

There were other cases where providing policy flexibility dramatically increased the number of kernel boundary crossings and they had to resort to other techniques.  For example, in network packet filtering instead of doing the filtering at user level they did it in the kernel, but gave the user program the ability to submit a little program (in a limited (and therefore safe) programming language) that would run in the kernel.  Similar ideas in this domain were being investigated around the same time by University of Washington's SPIN operating system project.


Hint:
While it's certainly possible to choose a concrete language and show a reduction from it, in this case it's actually easier to show a reduction from every language in NP.

As a starting point, recall that a language $L$ is in NP iff there exists a polynomial-time verifier for it.

Let $L$ be a language in NP, and let $M$ be a polynomial verifier for it, and let $f(n)\in O(n^k)$ be the runtime of the verifier. Observe that for every word $x$ we have that $x\in L$ iff there exists a witness $y$ such that $M$ accepts $(x,y)$ within $f(|x|)$ steps.

This looks a lot like your language, see if you can complete the proof from here.


How to find the original coordinates of a point inside an irregular rectangle?

This is what the concept of a homography was invented for.  You know the coordinates of the four corners on your screen and on the wall, and you want to find a transformation that maps from screen coordinates to wall coordinates.  There will be a homography that maps between the two coordinate systems.  So, your task is: given four points with known mappings, find a homography that is consistent with that.

If you're using OpenCV, see the findHomography() method, as well as warpPerspective().


Grammar for describing boolean expressions with AND, OR and NOT

It is an almost copy of the grammar Wirth gives for arithmetic expressions in "Algorithms + data structures = programs" (as far as I can remember it; I might be wrong with the source, though). So I strongly believe it is correct.

Write the corresponding recursive descent parser, and try it on some correct strings, and some badly built ones. Get somebody else, without coaching on your part, come up with examples and broken cases. Also generate some random combinations to try.


Ε-R diagram with conditions , is it possible?

This can be expressed in a one to many relationship with a 0..5 end:

LibraryPatron 1 <----> 0..5 BorrowedBook

Using relational algebra they can be expressed using check constraints as Renzo suggested.   Some ER tools may also allow you to express this as a constraint.


It could help if you wrote $n^{\log\log n}$ as $2^{\log n\log\log n}$. Then it should be clear that $2^{\log n\log\log n} = o(2^n)$. The morale of this is that the base of an exponent doesn't count as much as the exponent itself.


Terminology needed for the computational solution to the Rubik's Cube

Kociemba wrote very nice algorithm, which is the fastest working algorithm returning optimal or almost optimal solution very efficiently.

If you want to derive your own system, try in steps:
0) invent notation for the cube, do not try to optimize it.
1) try BFS or something like A* (this one will be harder, with heuristics).
2) try some kind of memoization, and state precomputation.
3) if something is not efficient step back to 0 and change type of notation.

Why should you not optimize your notation?
Because a few bytes overhead is nothing in compare to smooth transitions between states.

Honestly, pure BFS will do the job, but without any help or reductions it will be very slow. You can make encoding relative to color and put your reference point (one corner or the cross), it will decrease hashing time.
To check your approach just take several thousands of permuted cubes, count turns per cube and time it took per cube to solve.
If you are interested in AI, solving cube is doable, but guaranteed least moves will take some time.

There is Rubik Group but language induced solvers in contrary to graph or group solvers are not common, so there might be some hidden treasure there. Look at Kociemba algorithm, he does not use Rubik Cube group per se, but changes it so he has smaller number of instances.


Dependency graph with general (AND/OR) dependencies

Sorry for the crappy mspaint, but you could make an intermediate layer where the nodes in the middle represent each of the combinations of (A,B), like in a truth table:

~ABB~


Assume you have a table of items of quantity Q, price P and Value, V and a computed value ratio P/V for each item.

I would use a Successive Approximation Register approach using the most significant item rated by P/V ratio using a product sum that does not exceed the total or consumes all your inventory of that item then repeat down your ranked list by Price/value ratio. Just as SAR is the fastest for ADC's, this would be my optimum solution.

The trade may not be attractive to the other person, since you have offered items with the least value to you, so a practical solution must consider the V/P ratio of your item to  the other person, which may be unknown.

Tony
EE since 1975.


How to find the vertices on simple path between two given vertices in a directed graph

Thanks for your answers.
As master foo pointed out, the second problem -- given a directed graph and three distinct vertices $s, t$ and $i$, decide if there exist a simple path from $s$ to $t$ going through $i$ -- is indeed NP-complete.

From the paper The Directed Subgraph Homeomorphism Problem by Steven Fortune, John E. Hopcroft and James Wyllie, it is clear that the pattern graph $s \to i \to t$ is one for which the fixed directed subgraph homeomorphism problem is NP-complete since it is a tree of depth two.

Here are few definitions from this paper:

  The subgraph homeomorphism problem is to determine: if a pattern graph p is
  homeomorphic to a subgraph of an input graph G. The homeomorphism maps nodes
  of P to nodes of G and arcs of P to simple paths in G. The graphs P and G are either both directed or both undirected. The paths in G corresponding to arcs in P must be pairwise node-disjoint. The mapping of nodes in P to nodes in G may be specified or left arbitrary. This problem can be viewed as a generalized path-finding problem. For example, if the pattern graph consists of two disjoint arcs and the node mapping is given, then the problem is equivalent to finding a disjoint pair of paths between specified vertices in
  the input graph.

Basically, only the pattern graphs that are trees of depth one and their reverse graphs (with possibly loops arcs on the root) can be solved in polynomial time.

  Let C be the collection of all directed graphs with a distinguished node called the root possessing the property that either the root is the head of every arc or the root is the tail of every arc. Note that the root may be both the head and tail of some arcs and thus loops at the root are allowed. Equivalently, a graph is in C if, when all loops at the root are deleted and multiple arcs between pairs of nodes are merged into single arcs, the resulting graph is a tree of height at most one.

  [...]

  Next we show that for each pattern P not in C the fixed subgraph homeomorphism
  problem with pattern P is NP-complete.

I have not read the proof yet so I'll stop here.

There is also a close connection from the problem I have just mentionned and the two disjoint paths problem as pointed out by one of my collegue. The two dijsoint paths problem is:

  Given a directed graph and four distinct vertices $s_1, t_1, s_2, t_2$, decide if there exist two pairwise node disjoints simple paths from $s_1$ to $t_2$ and from $s_2$ to $t_2$.

This problem for directed graphs is well known to be NP-complete.
However, there is a simple transformation from the two disjoint paths problem to the $s \to i \to t$ problem. In order to do that, we need to add one extra node $i$ and the two extra edges $t_1 \to i$ and $i \to s_2$.

If there was a polynomial algorithm to solve the $s \to i \to t$ problem, we could use it to solve the two disjoint paths problem in polynomial time with the simple transformation above and thereby solving the $s \to i \to t$ problem.


In a kernel, what are "global constructors"?

The link you provided has a clear definition:

  This tutorial discusses how to correctly invoke global constructors, such as those on global C++ objects. These are supposed to have run before your main function, which is why the program entry point is normally a function called _start.

In most OSs, there is a step where the process' memory is filled with its initial values.  For C code, that is typically sufficient.  However, sometimes you want to execute some code before main(), which is your official entry point.  For example, in C++, you need to be able to call the constructor of all global objects before main() is invoked.

To resolve this, and any other run-time activities which must be done before main(), each system provides some way to execute a function before main.  The article mentions that some treat it as a simple array of function pointers, but some compilers will obscure it and hide it.

The key takeaway is that these are handled before the entry point of your program.


How to prove that { : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

Yuval's answer describes the main component. For the sake of completeness I'll precise a couple of details.
First, $L(M_1) \neq L(M_2)$ means that there is a string that is accepted by one of the automaton but not the other. Let's "build" an automaton $M$ that accepts precisely such strings, and we will then want to check whether it accepts a least one string. Then $M$ has states $(q^1_i, q^2_j)$ for each state $q_i$ of $M_1$ and $q_j$ of $M_2$. A state $(q^1_i, q^2_j)$ of $M$ is accepting if and only if $q_i$ is accepting in $M_1$ and $q_j$ is not accepting in $M_2$ or vice versa. Now, in order to tell if $M$ accepts a string, we need to know if there's an accepting node that is reachable from $(q^1_0, q^2_0)$. We can first guess such a state $(q^1_m, q^2_n)$ as its representation uses only a logarithmic number of bits. Then we can, one step at a time, guess a path of states from $(q^1_0, q^2_0)$ leading to $(q^1_m, q^2_n)$. Of course after each guess we need to actually verify that there is an edge in $M$ from the previous state to the recently guessed one. In order to do that we can always keep two states in memory, the current one and the state we just guessed as the next one, this uses logarithmic memory still.


Show that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model

Recall the following lemma. Let $X,Y$ be two random variables satisfying $\Pr[X\le\epsilon]\ge 1-\delta$ and $\Pr[Y\le\epsilon]\ge 1-\delta$ then $\Pr[X\le \epsilon \land Y\le \epsilon]\ge 1-2\delta$.
Suppose $\mathcal{H}$ is PAC learnable (realizable and proper). Let $m(\epsilon,\delta)$ be the guaranteed PAC sample complexity. Given $m(\epsilon,\delta/2)$ samples from $D^+$ and $m(\epsilon,\delta/2)$ samples from $D^-$, find $h_{ERM}$ that is consistent with all samples (both positive and negative). Since $\mathcal{H}$ is PAC learnable, we know that
$\Pr[L_{D^+}(h_{ERM})\le\epsilon], \hspace{1mm} \Pr[L_{D^-}(h_{ERM})\le\epsilon]\ge 1-\delta/2$. Note that we strongly used the fact that the PAC bound is achieved by any sample consistent hypothesis. Now Use the above lemma to show that the overall empirical risk minimizer is a 2-oracle PAC learner for $\mathcal{H}$.


You keep track of your work so far. As you say, a node is expandable if it has a child node which you haven't visited so far. In your program, every time you reach a new node in the expansion phase, you calculate all its children (you can also do this dynamically, but let's keep things simple). As time goes on, you mark each child which has been visited. In order to know whether a node is expandable, you just check whether all its children have been marked.

Of course, you don't really need to check all children. You can keep a counter at each node that counts the number of unvisited children. The next question would be – how do I find an unvisited child. It's a nice elementary exercise finding a way to achieve this efficiently.


How many vertices should be disconnected to make a graph acyclic?

A set of vertices whose removal makes the graph acyclic is called a feedback vertex set (FVS). What you seem to be doing is finding the smallest FVS, subdividing all edges incident to each vertex in the FVS, and finally deleting the vertices in the FVS.
Computing the smallest FVS is NP-hard, but it admits 2-approximation.


Data-flow analysis problem adjust to Ullman-Aho's framework?

Checking initialization: Yes, you can use this framework.  You need only a single boolean for each variable.  The lattice is $V\to \{\bot,\top\}$, i.e., $2^V$, where $V$ is the set of variables. The height of this lattice is $n+1$ where $n=|V|$ is the number of variables.  The transfer functions are monotonic.  Consequently, you can use the framework.

Range computation:  No.  The lattice of ranges has infinite height.  Consider, e.g., the sequence of ranges $[0,0]$, $[0,1]$, $[0,2]$, $[0,3]$, and so on: it never ends.  Consequently, you need something more, such as widening operators.

Common subexpressions: I don't know of any nice way to express this in that framework (though there could always be something I'm not aware of).


Your first definition only holds if $\epsilon \notin L$.

The Kleene star and plus are defined using recursive sets $V_i$. We have:

$$V_0 = \{\epsilon\}$$
$$V_1 = L$$
$$V_{i+1} = \{ vw : v \in V_i \wedge w \in L\}$$

Then:

$$L^* = \bigcup\limits_{i=0}^{\infty} V_i$$
$$L^+ = \bigcup\limits_{i=1}^{\infty} V_i$$

Note that $L^+$ omits $V_0 = \{\epsilon\}$, but does not subtract $\epsilon$ from $L$.


Yes.  This is eminently doable.  Here's the general recipe:

Define an "loss function" $L$.  The loss function takes as input the location of the connecting points, and it outputs a measure of how good/bad this set of connecting points is.  Smaller is better.  You mention "minimizing some distance"; this is where you put that, but you'll need to decide on a specific loss function you want to minimize.  If there are four connecting points, the loss function will take the form $L((x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4))$ and will output a single real number.  Choose a function that is continuous and differentiable.
Use gradient descent to find a location for the connecting points that minimizes the loss function.  Pick some reasonable initialization value (e.g., where the user initially drew the lines; or use some heuristic to pick a crude guess at where to put the connecting points), and then use gradient descent to improve this initial choice and find a minimum for $L$.

This should be very efficient.  It's also very flexible: if you decide you want a different criterion for what the line should look like, you achieve that by modifying the loss function.  There are standard libraries for gradient descent, or if you prefer, you can implement it yourself without too much difficulty.


Good data structure for finding all points in one set a distance from each point in another set

Sort the big set $Y$ into a regular grid, then for any query point $x_i,$ find its cell and you only have to check the adjacent cells to determine $E_i$ very quickly. For sorting, indeed, some parallel algorithms are faster than others, see this poster for an overview and example of using fast GPU radix and count sort.


Is Knapsack Feasibility and Knapsack with Unit Values NP-Hard?

Just finding a feasible solution is in $P$.  The empty set is a feasible solution.  It achieves an objective of zero.  So, the answer to "does a feasible solution exist?" is always "yes!" (to the extent that the question is even well-defined).  Similarly, the answer to "is any solution whose value is $\ge 0$?" is always "yes!".  Thus, those problems are not NP-hard.

When all values are one, there is also a trivial polynomial-time algorithm to find the optimal solution.  You should be able to find it yourself: just try a few examples, and you will quickly discover the trick.


Word Wrap Algorithm and Datastructure that supports modifications of text and window size

I think you can handle single-word modifications in $O(d \log n)$ time, where $d$ (density) is the maximal number of words in a line, which is hopefully small for any reasonable $A$ and fixed $W$.
Let's take one of your sentences as an example. We want it to be wrapped with $W = 30$ characters like this:
I'm looking for an algorithm
and datastructure that would
allow for linearithmic
preprocessing on A and
something like logarithmic
time modifications and
queries.

First, let's find all possible lines. This can be done greedily in $O(n)$ using two pointers scanning through $A$. If one of these lines ends where the other begins, we connect them.

The path from node $1$ to the root of the tree represents $I_W$.
Now let's remove "an" from the first line, forcing all other lines to shift:
I'm looking for algorithm and
datastructure that would allow
for linearithmic preprocessing
on A and something like
logarithmic time modifications
and queries.

But here's one nice thing about the tree: any single-word change can only affect $O(d)$ edges. We find these edges by re-running the same pre-processing on a small window around the changed word. In our case, the changes are:

Edge 1-6 removed
Edge 4-8 removed
Edge 1-7 added

So, we need to be able to do these operations efficiently:

Add new edge into the tree
Remove existing edge from the tree
Find $k$-th ancestor of a given node.

All these operations can be done in $O(\log n)$ via Euler tour technique. I won't describe its implementation in detail, but feel free to ask a separate question about it.


Proving that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not context-free

If $v x y$ is just 0s or 1s, pumping does unbalance the 0s and 1s.

If $v$ is $0^a$ and $y = 1^b$, pumping once gives $0^{N + a} 1^{N^2 + b}$, now prove that that can't possibly work out as $a + b \le N$ (in particular, $N^2 + b$ can't be a perfect square).


Computation tree logic and Kripke structures

CTL formulas are always evaluated from the starting state of the Kripke structure. Indeed, CTL stands for computation Tree logic, and the tree in question is the unwinding of the Kripke structure, starting from the initial state.

If you want to specify that $EF q$ should hold from every (reachable) state, that can be specified as $AGEFq$, which is still a CTL formula.


Can a Turing Machine be defined over many languages?

A Turing machine isn't defined over a language.

Given a Turing machine $M$, we can define the language of inputs on which $M$ halts; or the language of inputs which $M$ accepts; or the language of inputs which $M$ either accepts or doesn't halt on; and so on.

Usually we are interested in either the language of all inputs on which $M$ halts, or (for a machine halting on all inputs), in the language of all inputs which $M$ accepts.


Generating many graphs satisfying some properties

There are methods for randomly sampling graphs with a given degree sequence. You could try sampling and post-selecting for 2-connectedness, since that test is essentially a DFS. See for example

Efficient and Exact Sampling of Simple Graphs with Given Arbitrary Degree Sequence


One solution would be to use integer linear programming (ILP).  This is not guaranteed to have a polynomial worst-case running time (ILP can take exponential time), but ILP solvers are pretty impressive, and for reasonable-sized graphs, this might just be an effective solution in practice.

For each edge $e \in E$, let $x_e,y_e,z_e$ be integer variables with the constraint $0 \le x_e \le 1$, $0 \le y_e \le 1$, $0 \le z_e \le 1$ (so that $x_e,y_ez_e$ are forced to be either 0 or 1).  The meaning of $x_e=1$ is that $e$ is part of the path $l_1$, and the meaning of $y_e=1$ is that $e$ is part of $l_2$, and the meaning of $z_e$ is that $e$ is part of both $l_1$ and $l_2$.

Now introduce the following constraints:

$\sum_{(a,v) \in E} x_{(a,v)} = 1$ (i.e., at least one of the edges out of $a$ must be selected in $l_1$).
$\sum_{(v,b) \in E} x_{(v,b)} = 1$ (i.e., $l_1$ contains an edge into $b$).
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} x_{(u,v)} = \sum_{(v,w) \in E} x_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
$\sum_{(b,v) \in E} y_{(b,v)} = 1$ (i.e., $l_2$ contains an edge out of $b$).
$\sum_{(v,a) \in E} y_{(v,a)} = 1$ (i.e., $l_1$ contains an edge into $a$).
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} y_{(u,v)} = \sum_{(v,w) \in E} y_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
$\sum_{e \in E} w(e) (x_e + y_e) \le 1.1 (\alpha+\beta)$ (condition 3 in the question holds).
For each $e \in E$, $z_e \ge x_e + y_{-e} - 1$, $z_e \le x_e$, and $z_e \le y_{-e}$, where $-e$ is the reversal of the edge $e$ (i.e., if $e=(u,v)$, then $-e=(v,u)$).  (This enforces that $z_e = 1$ if and only if $x_e = y_{-e} = 1$.)

Now minimize $\sum_{e \in E} w(e) z_e$.  This will minimize the total weight of the edges that are common to both $l_1$ and $l_2$.


How to construct an ordinary matching from a fractional matching?

It is not possible to get a maximum matching from any fractional matching by only looking at the values of the fractional matching. Consider the undirected triangle graph with  vertices $v_1,v_2,v_3$ and edges $e_1=(v_1,v_2), e_2=(v_1,v_3), e_3=(v_2,v_3)$. If we assign $f(e_1)=f(e_2)=f(e_3)=\frac{1}{2}$, this is a valid fractional matching. However, an actual matching can only contain one of the edges, so we cannot distinguish these edges by their value.

It is of course always possible to obtain a matching from a fractional matching by first selecting all edges with at least a certain fraction and then removing edges such that you end up with a matching. This matching, however, is usually not a maximum matching.


How do I find the shortest representation for a subset of a powerset?

I believe I found a reduction from Hamiltonian path, thus proving the problem NP-hard.

Call the word $w\in\Sigma^*$ a witness for $A$, if it satisfies the condition from the question (for each $L\in A$, there's $m\geq 1$ such that $\{w_{m+i}\mid 0\leq i<|L|\} = L$).

Consider the decision version of the original problem, i.e. decide whether for some $A$ and $k\geq 0$, there's a witness for $A$ of length at most $k$. This problem can be solved using the original problem as an oracle in polynomial time (find the shortest witness, then compare its length to $k$).

Now for the core of the reduction. Let $G=(V,E)$ be a simple, undirected, connected graph. For each $v\in V$, let $L_v=\{v\}\cup\{e\in E\mid v\in e\}$ be the set containing the vertex $v$ and all of its adjacent edges. Set $\Sigma=E$ and $A=\{L_v\mid v\in V\}$. Then $G$ has a Hamiltonian path if and only if there is a witness for $A$ of length at most $2|E|+1$.

Proof. Let $v_1e_1v_2\ldots e_{n-1}v_n$ be a Hamiltonian path in $G$ and $H=\{e_1, e_2, \ldots, e_{n-1}\}$ the set of all edges on the path. For each vertex $v$, define the set $U_v=L_v\setminus H$. Choose an arbitrary ordering $\alpha_v$ for each $U_v$. The word $w=\alpha_{v_1}e_1\alpha_{v_2}e_2\ldots e_{n-1}\alpha_{v_n}$ is a witness for $A$, since $L_{v_1}$ is represented by the substring $\alpha_1e_1$, $L_{v_n}$ by $e_{n-1}\alpha_n$, and for each $v_i$, $i\notin\{1, n\}$, $L_{v_i}$ is represented by $e_{i-1}u_{v_i}e_i$. Furthermore, each edge in $E$ occurs twice in $w$ with the exception of $|V|-1$ edges in $H$, which occur once, and each vertex in $V$ occurs once, giving $|w|=2|E|+1$.

For the other direction, let $w$ be an arbitrary witness for $A$ of length at most $2|E|+1$. Clearly, each $e\in E$ and $v\in V$ occurs in $w$ at least once. Without loss of generality, assume that each $e\in E$ occurs in $w$ at most twice and each $v\in V$ occurs exactly once; otherwise a shorter witness can be found by removing elements from $w$.
Let $H\subseteq E$ be the set of all edges occurring in $w$ exactly once. Given the assumptions above, it holds that $|w|=2|E|-|H|+|V|$.

Consider a contiguous substring of $w$ of the form $ue_1e_2\ldots e_kv$, where $u,v\in V$, $e_i\in E$. We say that $u,v$ are adjacent. Notice that if $e_i\in H$, then $e_i=\{u,v\}$, because $e_i$ occurs only once, yet it is adjacent to two vertices in $G$. Therefore, at most one of $e_i$ can be in $H$. Similarly, no edge in $H$ can occur in $w$ before the first vertex or after the last vertex.

Now, there are $|V|$ vertices, therefore $|H|\leq |V|-1$. From there, it follows that $|w|\geq 2|E|+1$. Since we assume $|w|\leq 2|E|+1$, we get equality. From there we get $|H|=|V|-1$. By pigeonhole principle, there is an edge from $H$ between each pair of vertices adjacent in $w$. Denote $h_1h_2\ldots h_{n-1}$ all elements from $H$ in the order they appear in $w$. It follows that $v_1h_1v_2h_2\ldots h_{n-1}v_n$ is a Hamiltonian path in $G$. $\square$

Since the problem of deciding the existence of Hamiltonian path is NP-hard and the above reduction is polynomial, the original problem is NP-hard too.


Proving that grammar generates language with multi variable inequalities

The grammar produces words that we can separate into two cases:

$S$ gets replaced by $A$, then the second rule is used $k\geq0$ times with the branch that keeps the $A$ present. Then it is used with the branch that replaces $A$ by $C$. Finally, the last rule gets used $r\geq0$ times with the branch that keeps the $C$ present, followed by the branch that replaces it with the empty word. This generates words of the form $0^{2k+r}1^{k+r}$.
$S$ gets replaced by $B$, then the third rule is used $k\geq0$ times with the branch that keeps the $B$ present. Then it is used with the branch that replaces $B$ by $C$. Finally, the last rule gets used $r\geq0$ times with the branch that keeps the $C$ present, followed by the branch that replaces it with the empty word. This generates words of the form $0^{k+r}1^{2k+r}$.

In the first case $m=2k+r,n=k+r$ satisfy $m=2k+r\leq 2(k+r)=2n$ and $n=k+r\leq 2(2k+r)=2m$. In the second case $m=k+r,n=2k+r$ satisfy $m=k+r\leq 2(2k+r)=n$ and $n=2k+r\leq 2(k+r)=2m$. Therefore, all words produced by the grammar belong to $L$.

Now, suppose that you take a word in $L$. This would be a word of the form $0^m1^n$ with $m\leq 2n$ and $n\leq 2m$. As before, let's separate the analysis in two cases:

Assume that $m\geq n$. Define $r=2n-m$. Observe that since $m\leq 2n$ we have $r\geq0$ and that $r\leq n$, since $m\geq n$. Define $k=n-r=m-n$ and note that $m-r=2(m-n)=2k$. Therefore, $0^m1^n=0^{2k+r}1^{k+r}$. Now you can see how to produce this word using the grammar by following the flow in case 1 above.
Assume that $n<m$. Define $r=2m-n$. Observe that $r\geq$, since $n\leq 2m$ and that $n-r=n-m\geq0$. Define $k=n-m$. Then $m=k+r$ and $n=2k+r$. Therefore, $0^m1^n=0^{k+r}1^{2k+r}$. Now you can see that you can produce this word using the grammar as in case $2$ above.


Your brute force solution is far from optimal. One improvement is to use dynamic programming. For every $i,j$, determine the minimal maximum number of pages per day when reading the first $i$ chapters in $j$ days. Implemented naively, this leads to an $O(n^2d)$ solution, though you might be able to improve this to $O(nd)$ using a smart implementation.

A perhaps better solution is to use binary search. You state that it is easy to determine whether a certain maximum number of pages can be achieved. To find the minimum number that can be achieved, use binary search with the decision algorithm as an oracle. The running time in principle depends on the total number of pages, but in fact there are only $n^2$ different possible answers, and this leads to an $O(n^2)$ algorithm, which can probably be improved to $O(n\log n)$ with some additional ideas.


Proof that pseudorandom generators implies one-way function

One-way functions need not be invertible. A one-way function which is invertible is known as a one-way permutation.
Here is the definition of one-way function from Goldreich's primer:

A function $f\colon \{0,1\}^* \to \{0,1\}^*$ is one-way if it can be computed in polynomial time, and is hard to invert: for every polynomial time algorithm $A$, $$ \Pr_{x \in \{0,1\}^n}[f(A(f(x),1^n))) = x] \text{ is negligible}. $$

(A function $\epsilon(n)$ is negligible if $\epsilon(n) = O(1/n^k)$ for all $k$.)
As you can see, there is no promise that $|f(x)| = |x|$; it could be that $f(x)$ is longer than $x$, or even shorter than $x$ (which is why we feed $A$ the auxiliary input $1^n$, an arbitrary string of length $n$).


Performant algorithm to find edges without cross overs

As it is mentioned in this paper, you can find a concave-hull of points in a 2-dimensional plate in $O(n \log n)$ (as complex as finding a convex hull).


Algorithm for exploring a parameter space

Problem statement: You have a function $f:\mathbb{R}^2 \to \mathbb{R}^2$ where you know how to compute $f$ but not $f'$.  Given $(x,y)$, you want to find $(\alpha,\beta)$ such that $f(\alpha,\beta)=(x,y)$.

One approach is to use mathematical techniques for black-box optimization.  Define $g:\mathbb{R}^2 \to \mathbb{R}$ by

$$g(\alpha,\beta) = \|f(\alpha,\beta)-(x,y)\|^2,$$

i.e., the squared L2-norm of how far off the answer is.  Then your goal is to find $(\alpha,\beta)$ that minimizes $g$. Such a minimum will be a solution to your original problem.

The minimization problem could be solved using gradient descent, Newton's method, or some other iterative method.

The iterative methods will often require you to be able to compute the gradient of this function.  The gradient can be computed in a black-box way by using

$${\partial g \over \partial \alpha}(\alpha,\beta) = {g(\alpha+\epsilon,\beta) - g(\alpha-\epsilon,\beta) \over 2\epsilon}$$

where $\epsilon$ is a sufficiently small number, and similarly for ${\partial g \over \partial \beta}$.

This method assumes that $f$ is a "nice" function: e.g., continuous and differential and doesn't change too quickly, if you make small changes to its inputs.


Suboptimal Solution for a combinatorial problem

If you are willing to replace the induced $2$-norm with the Frobenius norm, then you can solve the problem column-by-column instead of all at once.

In a lot of practical situations I would expect the frobenius minimizer will be exactly the 2-norm minimizer, and is a common choice of norm to minimize in matrix completion problems.

edit: In a recent edit the original poster made it clear that what they are looking for is the frobenius norm, even though the notation $||\cdot||_2$ is traditionally used for the induced 2-norm. (the edit makes the problem much less interesting). Since the rest of this post is about justifying the Frobenius norm as an approximation to the induced 2-norm, it's basically irrelevant to the edited version of the question.

A little bit more on why the Frobenius norm could be a good approximation.

Since all norms are equivalent on a finite dimensional space, immediately we have
$$c(s)||\hat{X} - X||_{Fro} \le ||\hat{X} - X||_2 \le C(s) ||\hat{X} - X||_{Fro},$$

so the Frobenius minimizer will be within a constant of the $2$-norm minimizer when the dimensions of the matrix are fixed. The issue, as usual, is that the constants $c(s), C(s)$ depend on the number of entries in the matrix and go to zero/blow up as $s$ becomes larger and larger.

However, there is a situation where the constants do not blow up and that is, roughly, when

you are dealing with a sequence of matrices $\hat{X}_s, B_s$ that are stably larger and larger approximations of some extremely high dimensional (or infinite dimensional) true matrices (operators) $\hat{X},B$, and
the very large or infinite "true" problem has a solution in the sense that there exists $X_{optimal}$ such that $\hat{X} - X_{optimal}$ is compact.

A little bit more on these conditions: 1) is the case if, for example

your matrices are generated by incomplete sampling of data (eg., measurements from a scientific experiment where you could get better results by taking more data, or shopping data from a small subset of amazon's customers that are supposed to represent the customerbase as a whole), and you could get similar but bigger problems from the same distribution just taking more samples, or
the size $s$ of your matrices comes from the level of discretication of a continuum problem like a partial differential equation.

Furthermore, 2) must always be the case if you reasonably expect a solution, since if there is no approximation that makes $\hat{X} - X$ compact, then by definition it has no finite rank approximation, so you can never come up with a good result to the real problem by solving limited data versions with $\hat{X}_s, B_s$ nomatter how big $s$ is.

Now, assuming that the compactness condition holds, the singular values $\sigma_1, \sigma_2, \dots$ of $\hat{X} - X_{optimal}$ are summable (and thus square summable), and so we have the explicit equivalence,
$$||\hat{X} - X_{opt}||^2_{Fro} = \sum_{i=1}^{\infty} \sigma_i^2 = \left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)\sigma_1^2 =  \left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)||\hat{X} - X_{opt}||_2^2.$$

These constants are independent of $s$, and moreover the more compact the error, the faster the singular values decay, so the closer to 1 the equivalence constant is. Thus assuming that the matrices $\hat{X}_s, B_s$ come from stable sampling schemes or stable discretizations of $\hat{X},B$, we have the equivalence
$$||\hat{X}_s - X_{s,opt}||^2_{Fro} \le \gamma_1\left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)||\hat{X}_s - X_{s,opt}||_2^2 \le \gamma_2  ||\hat{X}_s - X_{s,opt}||^2_{Fro},$$
where $\gamma_1$, $\gamma_2$ come from the stability and coercivity constants of the sampling/discretization process.

So, since the assumptions above apply to a wide range of circumstances, replacing $2$-norm minimization with Frobenius norm minimization often makes sense in practical contexts.


Expressing statements on elephants in propositional logic

If you're willing to consider predicate logic (with predicates and quantifiers), there's a plausible way to express this.  Let $P(x)$ stand for the proposition "$x$ can carry coconuts".  Let $S$ denote the set of African elephants and $T$ denote the set of Asian elephants.  Then one interpretation of your sentence is

$$\forall x \in S . P(x) \quad \land \quad \forall y \in T . \neg P(y).$$

Propositional logic doesn't allow quantifiers or predicates; I don't see any reasonable way to express that sentence in pure propositional logic.

Important caveat:  logic is not a way of encoding all English sentences.  It is not intended as a model of conversational language.  Rather, it is a way of making precise certain mathematical subjects, and supporting a particular type of mathematical reasoning.  So don't expect it to be more than it is.


What Happens if I swap the forget gate and update gate in LSTM model?

The two formulas are mathematically equivalent; the only change is that you have swapped the names of the variables (changes them to names that are less intuitive, compared to what effect they have), but that doesn't affect the behavior of the system.


Sampling perfect matching uniformly at random

There is a classical paper of Jerrum and Sinclair (1989) on sampling perfect matchings from dense graphs. Another classical paper of Jerrum, Sinclair and Vigoda (2004; pdf) discusses sampling perfect matchings from bipartite graphs.

Both these papers uses rapidly mixing Markov chains, and so the samples are only almost uniform. I imagine that uniform sampling is difficult.


Techniques/tools for constructing hard instances of a puzzle game

As I understand it, the problem you are interested in is Bounded PlanSAT which asks whether there is a solution of length $k$ or less. PlanSAT on the other hand asks whether there exists any plan than solves the problem. Bounded PlanSAT is, for example, decidable even if we add function symbols to our language and thus make the number of states infinite. Both of these decision problems are indeed in $\text{PSPACE}$.

As for your problem of generating hard instances (meaning long solutions), one approach could be GRAPHPLAN which uses a data structure called the planning graph. Now, the planning problem asks if we can reach a goal state $G$ from the initial state $S_0$. Suppose we are given a tree of all possible actions from the initial state to successor states, and their successors, and so on. Indexed appropriately, we could answer the question of "is $G$ reachable from $S_0$?" just by looking it up. This is naturally impractical, since the tree is of exponential size. The planning graph is a polynomial-size approximation to this tree that can be constructed quickly.

The planning graph can't answer for sure whether $G$ is reachable from $S_0$, but it can estimate how many steps it takes to reach $G$. The estimate is always correct when it reports $G$ is not reachable, and it never overestimates the number of steps. Hence it is an admissible heuristic.

I agree this is perhaps not exactly what you are looking for. Nevertheless this way, one does not have to actually solve the instance. I don't think solve time is a particularly useful measure of hardness. For some solvers, some instances are easy. For some solvers, they are hard. In this sense, something like long solutions seem like a good measure of hardness.

Another thing that crossed my mind was the fact that classical planning can be represented as a constraint problem (SAT/CSP, see for example SATPLAN). If translated as SAT for example, one can use all the tools available in that domain. You might be interested for example in the question Measuring the difficulty of SAT instances. As for directly generating an instance of planning that has a solution of length more than $k$, I don't know the answer to.

By the way, if you want to solve instances in practice, Helmert (2001) analyzes many classes of planning problems and notes that constraint-based approaches such as GRAPHPLAN and SATPLAN are best for $\text{NP}$-hard domains while search-based approaches do better in domains where feasible solutions can be found without backtracking. Both have problems in domains with many objects because they must create many actions. One can also check out the International Planning Competition (IPC), similar to the SAT competition(s).


Proof of proposition between Precise Turing Machine and Proper Complexity function

For interested readers, here are some of related definitions.

A function $f : \Bbb N \to\Bbb N$ is a proper complexity function if $f$ is nondecreasing and there is a $k$-string TM Mf with input and output such that on any input $x$,

$M_f(x) = \sqcap^{f(|x|)}$ where $u$ is a tally (“quasi-blank”) symbol,
$M_f$ halts within $O(|x|+f(|x|))$ steps, and
$M_f$ uses $O(f(|x|))$ space besides its input.

Let $M$ be a deterministic/nondeterministic multi-string Turing machine (with or without input and output). Machine $M$ is precise if there are functions $f$ and $g$ such that for every $n\ge 0$, for every input $x$ of length $n$, and for every computation of $M$,

$M$ halts in precisely $f(|x|)$ steps and
all of its strings (except those reserved for input and output
whenever present) are at halting of length precisely $g(|x|)$.

Proposition 7.1 is intuitively simple and clear. If there is such a $M$, we can just extend the computation steps or space used by $M$ to the same limit $g(n)$ for all inputs of the same length $n$, where $g(n)$ is some function large enough but still bounded by $O(f(n))$.

It is not clear why do we need exactly to define $M_f$? I mean, we could simulate $M'$ by M directly without $M_f$.

The issue is how you can make $M'$ precise? For different inputs of the same size, $M$ can halt at different number of steps using different amount of spaces. You must have some reference or standard that can display or communicate the expected number of computation steps or spaces, which $M'$ can look up to and adjust itself to.

What is "yardstick" or 'alarm clock'? Are they the same?

A yardstick is "a fact or standard by which you can judge the success or value of something", according to Cambridge dictionary. That is the "reference or standard" I just said in my last paragraph.
For the sake of simpler explanation, let us assume $M$ is a deterministic $t$-string Turing machine with time bound. Here is how we construct $M'$ in slightly more detail.
Suppose $M_f$ is defined on a $k$-string Turing machine. We will define $M'$ on a $(k$+$t)$-string Turing machine.
Let $x$ be a given input of size $n$, which is given at the start of the first string (tape).
First, $M'$ will copy the input to the start of the $k$+$1$-th string (tape).
Second, $M'$ simulate $M_f$ with input $x$ using the first $k$ strings. Then reset $M'$ state to initial state, without touching the quasi-blanks on the first $k$ strings.
Third, $M'$ simulate $M$ using the remaining $t$ strings, the $k$+$1$-th, $k$+2-th, $\cdots$ and $k$+$t$-th strings. At the same time, whenever $M'$ make one computation step, it will advance its heads on the first $k$ strings once.
Lastly and most importantly, if the simulation of $M$ by $M'$ halts before $f(n)+1$ time, just continue to move the heads on the first $k$ strings until a true blank is encountered, which is an alarm and why this part is referred as "an alarm clock". Then $M$ will halt. This step homogenizes the running time of $M$.
It is possible I miss a detail in a place or two. Besides, there is a problem of choosing which head to move when we stipulate $M'$ to advance its head. I will let you figure out how to fill this obvious loophole. In any case, the idea and concept here are pretty easy to grasp, although the details are long, tedious and error-prone. Just make sure you have convinced yourself and you are confident to convince anybody.

More information can be found in Turing Machines as Clocks, Rulers and Randomizers written by José Félix Costa.