Finding growth of "inter-recursive" functions consider following code
int f(int x)
{
  if(x<1) return 1;
  else return f(x-1)+g(x);
}
int g(int x)
{
  if(x<2) return 1;
  else return f(x-1)+g(x/2);
}

Questions:

How do I find the growth of f(x), being that it contains a recursion to another function?
Are growth and time complexity of a a function same thing? Are they the same for f(x)?

Growth and time complexity are not the same, though in this case they probably have similar values (up to a multiplicative constant). The recurrences for the time complexity are
$$
\begin{align*}
F(x) &= \begin{cases} \Theta(1) & x < 1, \\ F(x-1) + G(x) + \Theta(1) & x \geq 1. \end{cases} \\
G(x) &= \begin{cases} \Theta(1) & x < 2, \\ F(x) + G(\lfloor x/2 \rfloor) + \Theta(1) & x \geq 2. \end{cases}
\end{align*}
$$
If you're uncomfortable with the notation $\Theta(1)$, mentally replace it with $1$. The difference between these recurrences and the ones for $f,g$ is the addition $\Theta(1)$ term in the inductive case (second lines above).

Ignoring the floors for the moment, we have
$$ g(x) = f(x-1) + f(x/2-1) + f(x/4-1) + \cdots, $$
the sum ending when the argument is below $1$. Therefore
$$ f(x) = f(x-1) + g(x) = 2f(x-1) + f(x/2-1) + f(x/4-1) + \cdots. $$
The recurrence $f'(x) = 2f'(x-1)$ with a base case $f'(0) = 1$ already has the solution $f'(x) = 2^x$, so we know that $f(x) = \Omega(2^x)$. Since $2^x$ grows so fast, we know that $f(x/2-1) + f(x/4-1) + \cdots \ll 2f(x-1)$, and this shows for example that $f(x) = O((2+\epsilon)^x)$ for all $\epsilon > 0$.

At this point one can probably guess and prove an asymptotic formula for $f$, but I'll leave that for others to do. Given $f$, it should be easy to estimate $g$. Indeed, it seems probable that $g = \Theta(f)$.

Update: Experiments show that
$$
\begin{align*}
\frac{f(n)}{2^n} &\longrightarrow 1.9635473337171197318620139352\ldots\\
\frac{g(n)}{2^n} &\longrightarrow 0.98177366685855986593100696758\ldots
\end{align*}
$$
Let $\alpha = \lim_{n \to \infty} f(n)/2^n$.
Even more accurately, we get (for $n$ divisible by $4$)
$$
\begin{align*}
f(n) &= \alpha \left( 2^n - 2^{n/2} + \frac{11}{28} 2^{n/4} + O(2^{n/8}) \right), \\
g(n) &= \alpha \left( \frac{1}{2} 2^n - \frac{1}{4} 2^{n/2} + \frac{1}{14} 2^{n/4} + O(2^{n/8}) \right).
\end{align*}
$$
The curious reader can try to prove these expansions, up to the exact value of the constant $\alpha$.

Indeed, let $f'(x) = f(x)/2^x$. Then
$$ f'(x) = f'(x-1) + 2^{\lfloor x/2 \rfloor - 1 - x} f'(\lfloor x/2 \rfloor - 1) + \cdots. $$
Easy induction shows that $f'(x) = O(x)$ and so
$$ f'(x) = f'(x-1) + O\left(\frac{x\log x}{2^{x/2}}\right). $$
Since the series $\sum_{x \geq 1} (x\log x)/2^{x/2}$ converges and the sequence $f'(x)$ is increasing, $f'(x)$ tends to some limit. Using the estimate $f'(x) = \Theta(1)$ and being more careful, we obtain
$$ f'(x) = f'(x-1) + \Theta(2^{-x/2} + 2^{-3x/4} + \cdots) = f'(x-1) + \Theta(2^{-x/2}). $$
Let $C = \lim_{t \to \infty} f'(t)$. Then
$$ f'(x) =  C - \Theta\left(\sum_{t=x+1}^\infty 2^{-t/2}\right) = C - \Theta(2^{-x/2}). $$
This shows that
$$ f(x) \sim C 2^x - \Theta(2^{x/2}), $$
which in turn implies that
$$ g(x) = f(x) - f(x-1) = \frac{C}{2} 2^x \pm O(2^{x/2}). $$
The rest of the terms in the asymptotic expansion depend on the LSBs of $x$, and are left to the interested reader.


How are "Problem Complexity" and "Solution Complexity" different? I am in an algorithms course, and my professor keeps specifying "we are talking about Problem complexity here, not Solution complexity". I would like to gain an intuitive understanding of the difference between these two. Do you all have an example(s) that can help me to understand?

Problem complexity is the best we can achieve for a given problem (sometimes under given restrictions). We usually talk about problem complexity when dealing with lower-bounds and it means there is probably no algorithm with lower time/place complexity than the proved ones.

Algorithm complexity is on the other hand the resources needed for a specific algorithm to run. When some algorithm solves a given problem in time $t$, we know that this problem has at most time complexity $t$ and hence, the complexity of an algorithm is an upper-bound for the complexity of the problem it solves.


How to obtain a trilateration ordering in a graph? In a sensor network graph $G = (V,E)$
$V = \{1,2,...,n\}$ is the set of sensors and the edge $(i,j)$ denotes that sensor $i$ and sensor $j$ are inside each other's sensing range. The weight of that edge denotes the Euclidean distance between the corresponding sensors.
The problem is in 2D.

Our goal is to fix the positions of three sensors and find the positions of the remaining.
Starting from 3 nodes (seed nodes), we first start the localization by finding a common adjacent of those 3 nodes.
Determining the position of a fourth node using three already localized node is called trilateration.

We expand the localization using trilateration. We have a localized node set, and each time we search for three nodes from that set that has a common unlocalized adjacent.

When we find such node, it does not mean it is localizable.

A trilateration ordering is: starting from three nodes, the list of vertices  denoted by $a \rightarrow i, j, k$ so that when followed, the localization process is completed unless there can be no improvement.

For instance:
$1 \rightarrow 5, 6, 7$
$2 \rightarrow 5, 6, 7$
$4 \rightarrow 5, 6, 7$
$8 \rightarrow 1, 2, 4$

Is a trilateration ordering.

My question is:

How to obtain such ordering, starting from three seeds, without checking the same node triplet twice and without skipping any node triplet.

Focus on the right problem

I suspect you will find that the most important challenge is not finding a trilateration ordering, but rather choosing a strategy that minimizes the localization error.

It is easy to find a trilateration ordering, as I will describe below.  In contrast, minimizing the error is more challenging.  Trilateration might actually not be the best way to minimize the error.  For instance, when trying to localize a node, it is possible that you might get better accuracy by using four neighbors (e.g., doing multiple trilaterations) and averaging.  Also, the order in which you do the localization might matter.  If you choose a bad order, errors might accumulate.

So, I suspect you might not be focusing on the right problem.

Answering your question as posed

I'm going to answer your problem as posed, even though I'm not sure it is the right problem.

There is a trivial, straightforward algorithm to solve your problem.  You simply enumerate all possibilities.  That can be done as follows:

Let $S$ denote the set of nodes that are currently localized.  Initially, $S$ includes just the three seed nodes.
Repeat the following, until $S$ includes all nodes (i.e., until $S=V$):

For each node $v \in V\setminus S$, for all triples $s,t,u \in S$ of three nodes in $S$:

If $s,t,u$ are all adjacent to $v$, then append $v \to s,t,u$ to your
trilateration order.  Assuming localization of $v$ doesn't fail, add
$v$ to $S$, and continue to the next iteration of the outermost loop.

The running time is $O(n^5)$, i.e., polynomial in the size of the graph.

With standard optimizations, the running time can be reduced significantly.  For instance, you can use a worklist $W$ of nodes that are adjacent to some element of $S$ but not in $S$ themselves (i.e., $W= \{w \in V \setminus S : \exists s \in S . w \in N(s)\}$).  You can update this worklist efficiently.  You can also use a priority queue to sort the elements of $W$ by their "degree" (i.e., the number of nodes in $S$ they are adjacent to), and you can update this ordering efficiently.

But since you didn't list any specific running time requirements, this should be sufficient.

A better approach

I suspect that a better approach is to try to use statistical methods to estimate a global best-fit for the location of all sensors, simultaneously.  For instance, you might use least-squares methods.

Let me illustrate what I mean.  Suppose that you perform a bunch of measurements of the distances between pairs of sensors; create a graph $G=(V,E)$, where there is an edge $(v,w)$ if you have measured the distance between sensor $v$ and sensor $w$.  Let $m(v,w)$ be the measured distance between $v$ and $w$.

Now our goal is locations of all the sensors that best fit these measurements.  In particular, we are looking for a map $L : V \to \mathbb{R}^2$, where $L(v)$ represents the location of sensor $v$.  We are given the locations of three seed nodes, say $v_1,v_2,v_3$.  Also, we are given approximate distance measures between pairs of nodes that are connected by an edge in $G$.  We want to find a location map $L$ that minimizes the total error of the measurements.  Thus, the cost of a location map $L$ might be given by the total squared error:

$$\text{cost}(L) = \sum_{(v,w) \in E} (d(L(v),L(w)) - m(v,w))^2.$$

Here $d(p,q)$ represents the Euclidean distance between the two points $p,q \in \mathbb{R}^2$.

Now we want to find the location map $L$ that minimizes $\text{cost}(L)$, subject to the requirement that $L(v_1),L(v_2),L(v_3)$ have their given values (the locations of the three seed nodes).

This is an optimization problem that can be readily solved using standard methods, e.g., least-squares fitting.

Your problem then decomposes into two parts:

Select a set of measurements to perform.
Solve the optimization problem, e.g., using least-squares best fit, to find the location of all sensors.

A simple approach to decide on a set of measurements might be: each sensor looks at the set of other sensors that are within in its range, and selects 5 of them at random (and ensures that each sensor has its distance measured against at least 3 other sensors, to ensure its location can be uniquely determined; hopefully most will be measured against more than 3 other sensors).  Of course, you could adjust the parameter 5 based upon empirical accuracy/performance tradeoffs.

You could also imagine more sophisticated methods, e.g., where you perform a series of measurements, solve the optimization, look at the average error for each sensor (as a crude measure of how accurate its location might be), then perform a few additional measurements (e.g., only for sensors who average error in its location is too high), and solve the optimization problem again with the additional data.

I think you might find that this is a more effective and robust way to solve your localization problem.

I also encourage you to look at the literature on localization in sensor networks.  There is lots of prior work on this problem.  You know the saying: a month in the field can save you a week in the library.  So, spend the week in the library, and first inform yourself about what has already been tried in the literature.


Extract Tree from multi-edge undirected graph I have the following multi-edge, undirected graph.

I would like to extract the following tree from it, if I start from the node $A$.

Do you know of any algorithm that I can use to achieve that ?

The problem I am trying to solve is the following.

The first graph represent different relational tables I want to join. Each edge $e_i$ represents one join between two tables (two tables could be joined on different fields, for example).

From that graph, I need to create the tree depicted in the second figure. That tree is then used for executing the joins.

Thanks

The problem is under-specified; nonetheless, I will try to help assuming that you are looking for the graph traversal tree.
To obtain such a tree, you can use a graph traversal algorithm such as breadth-first search. You can find a nice implementation of this algorithm in The Algorithm Design Manual by Steven Skiena.
Note that you need to adapt an important aspect of the algorithm:

Do not set a node as discovered unless the node has been visited from all of its incoming edges. Without this adaptation, each node will only be visited once, and, therefore, the behaviour of the algorithm will be the same as if multi-edges did not exist.

You will also need a data structure to store the tree of interest. In Skiena's implementation, this data structure is an array that is called parent: if node i is discovered from node j, then parent[i] = j.

The vertex that discovered vertex i is defined as parent[i]. Every vertex is discovered during the course of traversal, so, except for the root, every node has a parent. The parent relation defines a tree of discovery with the initial search node as the root of the tree.
Steven Skiena - The Algorithm Design Manual

However, note that you will need a slightly more complex data structure to support duplicated nodes.


Count number of linearly independent subsets of columns of a binary matrix I have a binary $m \times n$ matrix of rank $m$ (hence $m < n$). I need to count how many subsets of its columns form matrices with a full column rank, i.e. columns in the subset are linearly independent.

Straightforward approach would be to iterate over all subsets of columns of size up to $m$ (because column rank cannot be higher than a row rank), and then check corresponding submatrix if it has full column rank. For instance, if $m=25$ and $n=50$, this way one needs to test
$$
\binom{50}{1} + \binom{50}{2} + \dotsb + \binom{50}{25} \approx 6.3 \times 10^{14}
$$
matrices. Hence one needs a really fast algorithm to test if a particular submatrix has a full column rank.

For example, assume I have 500 cores and I want to calculate the subject in 24h. Then I need to test $1.4 \times 10^7$ submatrices per second per core. Old good Gaussian elimination fails with this task (right?). Can I do something much faster than it?

Another approach might be some optimised method like branch and bounds, so that one does not need to check all the submatrices - but only a small portion of them. For example we can build the subsets recursively, and if we encounter a subset of columns that are linearly dependent, we can safely throw away all of the supersets of this subset - as they will never become linearly independent. However, I am not sure about either complexity or running time of this approach. I am to implement it now to see the running time behaviour.

P.S. All operations are over Galois field $\mathbb F_2$.

P.P.S. Do you think this problem is in NP?

Snook, Counting bases of representable matroids shows that counting the number of maximal linearly independent subsets of columns is $\mathsf{\# P}$-complete. Your problem is probably also $\mathsf{\#P}$-complete. This suggests that you need an enumerative approach.

On the other hand, you can efficiently (in theory) approximate the number of maximal linearly independent subsets arbitrarily well, see for example Anari et al., Log-Concave Polynomials II: High-Dimensional Walks and
an FPRAS for Counting Bases of a Matroid (might be an overkill).


How to come up with the runtime of algorithms? I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site.

I've seen in many sites and books, the big-O notations like $O(n)$ which tell the time taken by an algorithm. I've read a few articles about it, but I'm still not able to understand how do you calculate it for a given algorithm.

This part of computer science is called analysis of algorithms. Many times people are satisfied when they are given a guarantee that an algorithm’s performance is not worse than a specified bound and they dont’t care about the exact performance.

This bound is conveniently denoted with the Landau-notation (or big-Oh notation) and in case of $\mathcal{O}(f(n))$ it is an upper bound. That is for inputs of size $n$ the algorithms complexity is guaranteed not to exceed (a constant times) $f(n)$. Most of the time it is clear from the context what the “unit” this bound is measured in is. Note that “runtime” measured in actual time units (seconds, minutes, etc.) is frowned upon as you can’t compare them meaningful across different computers. Typically a “costly” elementary operation is identified, like compares and exchanges in sorting algorithms, or pushs and pops if the algorithm includes a stack, or updates to a tree data structure used in the algorithm. This elementary operation is understood as to be the dominating one, that has the largest contribution to the algorithm’s complexity, or perhaps it is more expensive than another one in a particular setting (multiplications are considered to be more expensive then additions for example). It has to be selected so that the cost of other operations are (at most) proportional to the number of the elementary operations.

This upper bound is called the worst-case bound or the worst-case complexity of the algorithm. Because it has to hold for all inputs of the same size $n$ and the worst-case inputs incur the highest (worst) cost. The actual performance for a specific input of size $n$ may be a lot lower than this upper bound.

While it is possible to do an exact analysis it is usually much more involved to arrive at an exact result. Also, an exact analysis means accounting for all operations in the algorithm, and that requires a rather detailed implementation; while counting elementary operations can be done from a mere sketch of the algorithm most of the time. It is nice if such an analysis is possible but it is not always necessary.  Because small inputs are not much of a problem, you want to learn what happens when the input size $n$ gets large. Knowing that the algorithm’s complexity is bounded by $5n^2+3n-2\log(n)$ is nice but overkill when looking at the performance asymptotically ($n\rightarrow \infty$), because the term $n^2$ dominates the others for large $n$. So proving an upper bound of $\mathcal{O}(n^2)$ suffices.

If you have two algorithms and you can guarantee that one performs like $\Theta(n^2)$ and the other like $\Theta(n)$ you can easily decide which one is “faster”, has a lower “cost”, uses less elementary operations, just by noting that a quadratic function grows faster than a linear function. In practice that means that the linear algorithm finishes earlier or that it can process larger inputs in the same time. But it might be that the constants hidden by $\Theta$ are such that for practical $n$ the $\Theta(n^2)$ algorithm is faster.

However if you have three algorithms all with a $\mathcal{O}(n^3)$ guarantee on their complexity you are hard pressed when you have to decide which algorithm to choose. Then more detailed bounds are needed, or perhaps even an exact analysis.

It may very well be that this analysis is hard to do and you can’t give a tight bound. Then there is a gap between the actual worst-case performance, perhaps $n^2$ and your bound of perhaps $\mathcal{O}(n^3)$. Then a clever idea, a more involved analysis is necessary to close the gap and provide an improved bound. This is just an improvement of the bound not to the algorithm. Typically you have to argue more carefully when you want to prove a tighter bound.

This all said, an analysis of an algorithm can be as simple as looking at the implementation and counting the nesting depth of the for loops to conclude that the operations in the innermost loop are executed not more than $\mathcal{O}(n^3)$ times when say three loops are nested.

For some types of algorithms the analysis follows always the same pattern, so there is a theorem like the master theorem, that tells you generically what the algorithms performance will be. Then you only have to apply the theorem to get the bound.

Perhaps you are faced with a recursive algorithm and you are able to describe the algorithms complexity by a recurrence relation. Then solving the recurrence gives the desired bound.

Typically you have to exploit some properties of the inputs. Sorting algorithms are deeply connected to permutations and knowing something about the number of inversions in a permutation helps a lot when analysing the performance.

There is no general approach on how to proceed in an analysis. As discussed above it depends on the algorithm, its inputs, its implementation, the elementary operation choosen, what mathematical tools you have at hands, the desired sharpness of the bound.

Some may prefer a smoothed-analysis or an average-case analysis over a treatment of the worst-case. Then different techniques are necessary.


Did Wheeler really believe that physics was undecidable? John Archibald Wheeler was a famous physicist

It has been stated that he thought that there was a strong connection between undecidability and quantum physics

  This idea was given an early formulation by Wheeler
  himself: in unpublished notes to a discussion held with,
  among others, Roger Penrose and Simon Kochen, he
  identifies the point of origin of the ‘quantum principle’
  as the undecidable propositions of mathematical logic

(https://arxiv.org/pdf/1805.10668.pdf)

But then, this same physicist proposed that the universe was similar to a computer and that reality emerged as digital informational processes in form of bits (It from Bit): https://en.wikipedia.org/wiki/Digital_physics

As far as I know, digital physics models cannot be undecidable. They must be decidable (If not, we could never construct an algorithm which would get a correct answer to a yes/no question)

So, what is happening here? Did Wheeler change of mind?

The inference "the universe would be completely computable, so no undecidable/uncomputable things could exist" is invalid.

In the effective topos, where everything is computable, there are many undecidable phenomena. For example, all real numbers are computable, but equality of real numbers is undecidable (and computable).

To give you an idea how this happens: equality of reals is a map $\mathbb{R} \times \mathbb{R} \to \Sigma$ which is implemented by a Turing machine that takes (Turing machines that compute) reals $x$ and $y$ and returns a non-boolean truth value represented by a Turing machine which terminates if, and only if, $x \neq y$.

In contrast, equality of natural numbers is decidable. It is a map $\mathbb{N} \times \mathbb{N} \to \{0,1\}$ which takes two natural numbers and outputs either $0$ or $1$, depending on whether they are equal.

As far as physcists are concerned, I would be careful about learning computability theory from them. I wouldn't want anyone to learn physics from me.


How are hash tables O(1) taking into account hashing speed? Hash tables are said to be amortized $\Theta(1)$ using say simple chaining and doubling at a certain capacity.

However, this assumes the lengths of the elements are constant. Computing the hash of an element requires going through the element, taking $\Theta(l)$ time where $l$ is the length.

But to discriminate between $n$ elements, we need the elements to have length at least $\lg n$ bits; otherwise by pigeonhole principle they won't be distinct. The hash function going through $\lg n$ bits of element is going to take $\Theta(\lg n)$ time.

So can we instead say that the speed of a hash table, taking into account a reasonable hash function which uses all parts of the input, is actually $\Theta(\lg n)$? Why, then, are hash tables in practice efficient for storing variable-length elements, such as strings and large integers?

The tale that hash tables are amortized $\Theta(1)$ is a lie an oversimplification.

This is only true if:
- The amount of data to hash per item is trivial compared to the number of Keys and the speed of hashing a Key is fast - $k$.
- The number of Collisions is small - $c$.
- We do not take into account time needed to Resize the hash table - $r$.

Large strings to hash
If the first assumption is false the running time will go up to $\Theta(k)$.
This is definitely true for large strings, but for large strings a simple comparision would also have a running time of $\Theta(k)$. So a hash is not asymptotically slower, although hashing will always be slower than a simple comparision, because comparison has a early opt out ergo $O(1)$, $\Omega(k)$ and hashing always has to hash the full string $O(k)$, $\Omega(k)$.

Note that integers grow very slowly. 8 bytes can store values up to $10^{18}$; 8 bytes is a trivial amount to hash.
If you want to store bigints then just think of them as strings.

Slow hash algorithm
If the amount spend hashing is non-trivial compared to the storage of the data then obviously the $\Theta(1)$ assumption becomes untenable.
Unless a cryptographic hash is used this should not be an issue.

What matters is that $n$ $>>$ $k$. As long as that holds $\Theta(1)$ is a fair statement.

Many collisions
If the hashing function is poor, or the hash table is small, or the size of the hash table is awkward collisions will be frequent and the running time will  go to $O(log(n))$.
The hashing function should be chosen so that collisions are rare whilst still being as fast as possible, when in doubt opt for fewer collisions at the expense of slower hashing.
A rule of thumb is that the hashing table should always be less than 75% full.
And the size of the hashing table should not have any correlation with the hashing function.
Often the size of the hashing table is (relatively) prime.

Resizing the hash table
Because a nearly full hash table will give too many collisions and a big (empty) hash table is a waste of space, many implementations allow the hash table to grow (and shrink !) as needed.
The growing of a table can involve a full copy of all items (and possibly a reshuffle), because the storage needs to be continuous for performance reasons.
Only in pathological cases will the resizing of the hash table be an issue so the (costly but rare) resizes are amortized across many calls.

Running time
So the real running time of a hash table is $\Theta(kcr)$.
Each of $k$, $c$, $r$ on average is assumed to be a (small) constant in the amortized running time and thus we say that $\Theta(1)$ is a fair statement.

To get back to your questions
Please excuse me for paraphrasing, I've tried to extract different sets of meanings, feel free to comment if I've missed some

You seem to be concerned about the length of the output of the hash function. Let's call this $m$ ($n$ is generally taken to be the number of items to be hashed). $m$ will be $log(n)$ because m needs to uniquely identify an entry in the hash table.
This means that m grows very slowly. At 64 bits the number of hash table entries will take up a sizeable portion of worldwide available RAM. At 128 bits it will far exceed the available disk storage on planet earth.
Producing a 128 bit hash is not much harder than a 32 bit hash, so no, the time to create a hash is not $O(m)$ (or $O(log(n))$ if you will).

  The hash function going through $log(n)$ bits of element is going to take $Θ(log(n))$ time.

But the hash function does not go through $log(n)$ bits of elements.
Per one item (!!) it only goes though $O(k)$ data.
Also the length of the input (k) has no relation with the number of elements.
This matters, because some non hashing algorithms have to examine many elements in the collection to find a (non)matching element.
The hash table only does 1 or 2 comparisons per item under consideration on average before reaching a conclusion.

  Why are hash tables efficient for storing variable-length elements?

Because irrespective of the length of the input ($k$) the length of the output ($m$) is always the same, collisions are rare and lookup time is constant.
However when the key length $k$ grows large compared the to number of items in the hash table ($n$) the story changes...

  Why are hash tables efficient for storing large strings?

Hash tables are not very efficient for very large strings.

If $not$ $n >> k$ (i.e. the size of the input is rather large compared to the number of items in the hash table) then we can no longer say that the hash has a constant running time, but must switch to a running time of $\Theta(k)$ especially because there is no early out. You have to hash the full key. If you're only storing a limited number of items then you may be much better off using a sorted storage, because when comparing $k1$ $\ne$ $k2$ you can opt out as soon as a difference is seen.

However if you know your data, you can choose not to hash the full key, but only the (known or assumed) volatile part of it, restoring the $\Theta(1)$ property whilst keeping the collisions in check.

Hidden constants
As everyone ought to know $\Theta(1)$ simply means that the time per element processed is a constant. This constant is quite a bit larger for hashing than for simple comparison.
For small tables a binary search will be faster than a hash lookup, because e.g. 10 binary comparisons might very well be faster than a single hash.
For small datasets alternatives to hash tables should be considered.
It's on large datasets that hash tables truly shine.


a cut containing exactly one edge in each path Given a digraph with a source $s$ and target $t$, must there be an edge cut which contains exactly one edge in every path from $s$ to $t$?  I'm not interested in a minimum cut; any cut would do.

If not, how close to "exactly one" can we get?

It really depends on what do you exactly mean by "path".

Edge-disjoint paths -- Given a graph $G=(V,E)$, a minimum edge-cut consists of one edge for every edge-disjoint path between $s$ and $t$.

Vertex-disjoint paths -- Given a graph $G=(V,E)$, a minimum vertex-cut consists of one vertex for every vertex-disjoint path between $s$ and $t$. Therefore, the set of edges incident to the vertices in the cut (out-edges) consist of one edge per vertex-disjoint path between $s$ and $t$.

Having exactly one edge per every simple path between $s$ and $t$ is impossible. The reason is that the number of edges in the cut must be equal to the number of simple paths between $s$ and $t$, however, the number of simple paths between two vertices $s$ and $t$ can be exponential in terms of $n$, while the number of edges is at most $n^2$. Using Pigeonhole principle, it can be shown that it is impossible to find such solution.

The following example shows that the number of paths between $s$ and $t$ is $2^{(n-2)/2}$, while the number of edges between them is $2n-4$.

If you are interested in finding a set of edges that consists of at least one edge from every path between $s$ and $t$, then you can use the minimum edge-cut between $s$ and $t$.
If you are considering a case where you need at least one edge from each path, and no more than one edges per path, you can use an approach that is similar to minimum cut algorithm, but I am not sure how efficient it would be in practice.

Find the minimum edge-cut between $s$ and $t$;
Using a graph traversal algorithm (i.e. DFS), find if there is a path that goes over two of the edges in the cut;
If you find a such a path, remove those edges $(u_1, v_1), \cdots, (u_k, v_k)$ from the cut $C$ and replace them with the minimum cut from each $u_i$ to $t$ ($1 \leq i \leq k$), and repeat from 2;
If there is no such path then output $C$ and terminate;


Are there any functions with Big O (Busy Beaver(n))? So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than exponentials, faster than the Aaronson sequence, and faster than a recursive use of Knuth's up-arrow notation.
This led me to a thought: are there any algorithms that grow in size with Big O (Busy Beaver(n)), aside from the Halting Problem? Is it even possible to design such an algorithm on that would run on a Turing Machine-equivalent computer?

The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of $\Theta(\mathit{BB}(n))$, or indeed $\Omega(\mathit{BB}(n))$. Indeed, such an algorithm could be used to solve the halting problem (assuming you knew a constant $c>0$ such that the running time is at least $c\mathit{BB}(n)$), since you could use the algorithm to get an upper bound on $\mathit{BB}(n)$.
On the other hand, any algorithm has a running time of $O(\mathit{BB}(n))$, precisely because the busy beaver function grows faster than any computable function.


Pagination of results from different sources merged by a unified scoring function Assume a Hotel reservation scenario, given $m$ ranked lists of attribute values such as distance, price, amenities (normalized between $0$ and $1$), and a unifying linear score function $F(\cdot)=\alpha_1*score_1+ \alpha_2*score_2+ \alpha_3*score_3$, the Threshold Algorithm (TA) is optimal in finding top-$k$ results that have higher $F$ values.

However, consider a pagination scenario with page index $p$ and page size $k$. Indeed, instead of asking for top-$k$ that can be obtained from indices [0,k] in the final ranked list, we ask for [pk, (p+1)k]. What is the best solution to obtain this window of the results?

You may consider this problem as the pagination of the merged results over a unified scoring function when there are multiple data sources that each contains a score value but the merged results have a combined score value as a (linear) function of individual score values.

Some solutions:

Totally naive: given the multiple ranked results, compute the unified score, sort them, slice it as needed.

Potentially better but inefficient when asking lower-ranked results (farther pages):
Execute Threshold Algorithm and ask for top-(p+1)k, return the [pk, (p+1)k] from it.

I think $F$ and its details are irrelevant, an appropriate comparison function that uses $F$ internally turns your problem into a regular sorting one. Then your problem is solved in $O(n)$ using a regular selection problem.

Find the element with rank $pk$ in $O(n)$ using a selection algorithm. Similarly find the element with rank $(p+1)k$. Then do a single linear scan over the array to find all elements that have a value between these two in $O(n)$.


Least fix point of CTL formula In the book Logic in Computer Science on page 244, there is a proof that $[[E(\phi U\psi)]]$ is the least fixed point of $G(X)=[[\psi]] \cup ([[\phi]]\cap\mathop{\textrm{pre}}_\exists(X))$. I don't get the idea of point 2. I tried to understand why this proof says that $[[E(\phi U\psi)]]$ is the least fixed point of $G$.

They prove that $G^{k+1}(\emptyset)\subseteq[[E(\phi U\psi)]]$ for each $k\geq0$.
This is fine, I understand each step on their the proof, I just don't understand why this proves that $[[E(\phi U\psi)]]$ is the least fixed point of $G$...

I can prove that $G^{k+1}(\emptyset)\subseteq S$  when $S$ is the group of all the states. $G$ is still the same function, and of course that for each such $i\geq0, G^i(\emptyset)\subseteq S$. This doesn't mean that $S$ is the least fixed point, or that each fixed point contains $S$.

So why this proof claims that $[[E(\phi U\psi)]]$ is the least fixed point of $G$?

They actually start by proving that $[[E(\varphi U\psi)]]=\bigcup\limits_{k\ge 1}G^k(\emptyset)$.

You can see (or prove by induction for the general case) that repeated applications of $G$ starting with the empty set yields:

$G(\emptyset)=[[\psi]]$,

$G^2(\emptyset)=[[\psi]]\cup ([[\varphi]]\cap pre_\exists([[\psi]]))=[[\psi]]\cup\left\{s\in S | s\in[[\varphi]] \land \exists s' \left(s\rightarrow s' \land s'\in[[\psi]]\right)\right\}$

$\vdots$

$G^{i+1}(\emptyset)=G^i(\emptyset)\cup \left\{s\in S| s\in[[\varphi]]\land\exists s' \left( s\rightarrow s'\land s'\in G^i(\emptyset)\right)\right\}$

The union of the above sets exactly coincides with the definition of $[[E(\varphi U \psi)]]$. To conclude the proof, they use the fact that $G$ is montone and that $G^{n+1}(\emptyset)$ is a fixed point of $G$, thus $\bigcup\limits_{k\ge 1}G^k(\emptyset)=G^{n+1}(\emptyset)$, which is the least fixed point of $G$.


2-way Graph Partitioning problem We have a graph $G=(V,E)$ and we need to divide this graph into two clusters $A$ and $B$. Some pairs of vertices $u$, $v$ should not be in the same cluster, and we define an edge $(u,v) \in E$. The total cost of a solution is the total number of edges with endpoints both in the same cluster. My goal is to find an algorithm that returns the optimal solution that minimizes this total cost. The solution does not have to be balanced in the sense that the clusters should be of the same size.

I was wondering what the general name for this problem is and what a proper algorithm is that can solve this efficiently. By a colleague I was pointed into the direction of using a (nice) tree decomposition.

You're looking for a maximum cut in the graph – maximizing the number of edges between the partitions minimizes the number within them.

Unfortunately, Max Cut is NP-hard on general graphs and also hard to approximate. There's a polynomial-time algorithm on planar graphs, if that's of any use to you.


Why does Radix sort require stable digit sorts? I'm reading the CLRS book and have a question about the following quote from the book.

  In order for radix sort to work correctly, the digit sorts must be stable.

Why is stability required? Wouldn't Radix sort still produce correctly sorted output even if there was no consistency in ordering of identical values, since Radix sort sorts on every digit position?

Integers that are equal in some digit aren't always equal (e.g., 12 and 13).

Let's sort [13, 12] using a LSD-first radix sort (base 10). But we'll use an unstable sort for each digit.

First we sort by the 1's place, so the array becomes [12, 13].

Now we sort by the 10's places, but 12 and 13 have the same digit. Since the sort is unstable, the resulting array could be [12, 13] or [13, 12]. We don't know.

If the sort were stable we would be guaranteed to get a correctly sorted array.


fast and stable x * tanh(log1pexp(x)) computation $$f(x) = x \tanh(\log(1 + e^x))$$

The function (mish activation) can be easily implemented using a stable log1pexp without any significant loss of precision. Unfortunately, this is computationally heavy.

Is it possible to write a more direct numerically stable implementation which is faster?

Accuracy as good as x * std::tanh(std::log1p(std::exp(x))) would be nice. There is no strict constraints but it should be reasonably accurate for use in neural networks.

The distribution of inputs is from $[-\infty, \infty]$. It should work everywhere.

With some algebraic manipulation (as pointed out in @orlp's answer), we can deduce the following:
$$f(x) = x \tanh(\log(1+e^x)) \tag{1}$$
$$ = x\frac{(1+e^x)^2 - 1}{(1+e^x)^2 + 1} = x\frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2}\tag{2}$$
$$ = x - \frac{2x}{(1 + e^x)^2 + 1} \tag{3}$$
Expression $(3)$ works great when $x$ is negative with very little loss of precision. Expression $(2)$ is not suitable for large values of $x$ since the terms are going to blow up both in the numerator and denominator.
The function $(1)$ asymptotically hits zero as $x \to-\infty$. Now as $x$ becomes larger in magnitude, the expression $(3)$ will suffer from catastrophic cancellation: two large terms cancelling each other to give a really small number. The expression $(2)$ is more suitable in this range.
This works fairly well until $-18$ and beyond which you lose multiple significant figures.
Let's take a closer look at the function and try to approximate $f(x)$ as $x \to-\infty$.
$$f(x) = x \frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2}$$
The  $e^{2x}$ will be orders of magnitude smaller than $e^x$. $e^x$ will be orders of magnitude smaller than $1$. Using these two facts, we can approximate $f(x)$ to:
$f(x) \approx x\frac{e^x}{e^x+1}\approx xe^x$
Result:
$f(x) \approx \begin{cases}
xe^x, & \text{if $x \le -18$} \\
x\frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2} & \text{if $-18 \lt x \le -0.6$} \\
x - \frac{2x}{(1 + e^x)^2 + 1},  & \text{otherwise}
\end{cases}
 $
Fast CUDA implementation:
__device__ float mish(float x)
{
    auto e = __expf(x);
    if (x <= -18.0f)
        return x * e;

    auto n = e * e + 2 * e;
    if (x <= -0.6f)
        return x * __fdividef(n, n + 2);

    return x - 2 * __fdividef(x, n + 2);
}

EDIT:
An even more faster and accurate version:
$f(x) \approx \begin{cases}
x\frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2} & \text{$x \le -0.6$} \\
x - \frac{2x}{(1 + e^x)^2 + 1},  & \text{otherwise}
\end{cases}
 $
__device__ float mish(float x)
{
    auto e = __expf(value);
    auto n = e * e + 2 * e;
    if (value <= -0.6f)
        return value * __fdividef(n, n + 2);

    return value - 2 * __fdividef(value, n + 2);
}

Code: https://gist.github.com/YashasSamaga/8ad0cd3b30dbd0eb588c1f4c035db28c
Benchmarks with other implementations: https://github.com/YashasSamaga/ConvolutionBuildingBlocks/tree/master/mish
$$\begin{array}{c|c|c|c|}
 & \text{Time (float)} & \text{Time (float4)} & \text{L2 norm of error vector} \\ \hline
\text{mish} & 1.49ms & 1.39ms & 2.4583e-05 \\ \hline
\text{relu} & 1.47ms & 1.39ms & \text{N/A} \\ \hline
\end{array}$$


Is arithmetic turing complete? Maybe my question doesn't make sense, because I lack some more thorough understanding, but I was curious if arithmetic was Turing complete?

As I understand it, a "model of computation" is a mechanism where you can compute outputs from inputs. Thus a "computation" is just a mapping from inputs to outputs.

So if say the universe of possible inputs and outputs is: 1 and 2. This would be all possible computations:

1 -> 1
1 -> 2
1 -> 1,2
1 -> 2,1
2 -> 1
2 -> 2
2 -> 1,2
2 -> 2,1
1,2 -> 1
1,2 -> 2
1,2 -> 1,2
1,2 -> 2,1
2,1 -> 1
2,1 -> 2
2,1 -> 1,2
2,1 -> 2,1

Now, I think this isn't even technically the full set, because the full set would be infinite, since I could have repeated inputs and outputs like 1,1 -> 2,2,1,1. But at least this is the general gist which I understand.

And in my "model of computation", I should be able to say, apply the computation X to some inputs, where X is one of the above mapping, and get back the corresponding outputs.

So from this, I understand that the Turing Model is proven to be able to map all inputs to outputs over the universe of non complex numbers.

So my question is, would arithmetic be Turing Complete in its ability to map inputs to outputs? Or is there some mappings that can not be formulated using arithmetic, but can using the Turing model?

It depends what you mean by "arithmetic".

It's a fairly well-known result that Peano arithmetic (PA) is powerful enough to model Turing machines.

There are other models of arithmetic, such as Presburger arithmetic (which is strictly weaker; it's essentially PA without multiplication) and real closed fields with a partial order, which are known to be decidable.


How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ?

Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I cannot understand What kind of function lays there?

Consider the function
$$
f(n) = \begin{cases} g(n) & \text{if $n$ is even}, \\ g(n)/n & \text{if $n$ is odd}. \end{cases}
$$


Bringing images into alignment I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I now want is to bring i1 and i2 into alignment, that is I want to know where pixel (x,y) in i1 is in i2. This "alignment-matrix" should be valid in general, that is not only for i1 and i2, but also for further images of the cameras c1 and c2 as long as they haven't been moved. I believe this problem is called "correspondence problem".

I have now read quite a bit about camera calibration, image rectification, essential and fundamental matrix. But there are still open questions and I would not know how to achieve my task.

So, the question basically is:

The essential matrix E and the fundamental matrix F both only give constraints for the correspondence problem (point p in i1 must lie on line l in i2). How do I actually solve the problem?

Thanks a lot for your time and answers!

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 does the OS Scheduler give/take control of HW? Imagine a uniprocessor system with a simple operating system with non-threaded processes and basic virtual memory (paging, no segmentation, no replacement to disk, etc).

Now assume a simple preemptive scheduler, round-robin, for example.

Because it is a uniprocessor, the scheduler must hand over control of the processor momentarily for any other processes it schedules to run. How does it regain control? It can't generate interrupts, as it is not running.

I originally assumed there must be some kind of register containing the time to return control to the scheduler, and a register pointing to the location of the scheduler. But if these registers existed, what would a nonpreemptive scheduler do with them? How would the processor know the difference between a preemptive and nonpreemptive scheduler, i.e. how would it know whether to use the registers to return, or allow the process to run to completion?

Your idea of interrupts is correct, but not how it works. The scheduler program will not raise an interrupt.

Let's take the round robin algorithm you have mentioned. A process is going to run for a period of time and then is supposed to relinquish the CPU. How does this work? Interrupt. It is the operating system that raises this interrupt using what is called an interval timer. The interval timer is programmable and is set to the time slice value of the round robin algorithm.

Once the interrupt is raised, the time quantum for the current process expires and the control is given to the scheduler process.


How do arrays work "under the hood"? In some languages (such as C), arrays seem very simple to me. When allocating memory for these, all you need to do is pick a starting point in memory and then allocate the next dataTypeSize * arrayLength bytes as reserved. Retrieving items just means looking at the memory address startPoint + (index * dataTypeSize).

But in other languages (such as JavaScript and ActionScript), there is no requirement to make them fixed when creating the array. In fact, most often in actual use, an empty array is created, then new items are one by one appended to the array in a for loop.

How is the memory managed when you could at any time append add an item to the end, or prepend an item to the beginning? Do you need to redefine space in memory every time the size changes?

There is no single standard implementation of JavaScript, so if you want to know what happens in a particular implementation, you should use your web search skills, focusing your efforts on that particular implementation. That said, a cursory web search reveals two main points:

Arrays can be implemented simply as associative arrays (also known as hash tables or, in python, dictionaries). This is appropriate if the array is sparse (contains only few non-zero values).
Arrays can be implemented as dynamically sized arrays, which are appropriate for the dense case. These are stored as classical C/Fortran arrays with a certain "extent". Once their length exceeds their extent, they are extended (say by doubling the extent) by allocating a new array the size of the new extent, copying the old values to the new array, freeing the old array, and changing the appropriate pointer to reflect the new location in memory. Arrays can potentially shrink as well according to a similar scheme.

Associative arrays are also dynamically sized, so in any case the second paradigm is being used.

Since the extent of the arrays increases exponentially, the average overhead is bearable, though once in a while, an operation may take a long time to perform (due to an array being resized). So such arrays are not a good choice for real-time systems.


Algorithm for generating all unlabeled trees with n nodes? How can one generate all unlabeled trees with $\le n$ nodes?

That is, generate and store the adjacency matrices of those graphs? (not just count them)

Visualization of all unlabeled trees with $\le6$ nodes:

Here is some python code
https://gist.github.com/hagberg/7979081

I would start with all the trees size N-1 appending a new node to each of the nodes
The tricky part is to identify whether each new tree is truly new and not isomorphic to previously generated trees. I'm guessing you need a system to code this topologies to detect symmetries.
I'd try to find the longest path
Longest path in an undirected tree with only one traversal
and find a deterministic way to represent the graph

This now gone project to verify the graceful Tree conjecture contains some c++ code that might help you
https://web.archive.org/web/20120729224449/http://www.eleves.ens.fr/home/wfang/gtv/index_en.html


Time complexity based on two variables Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have:

$T(m,c)\in O(m^2)$ for any constant $c$.
$T(c',n)\in O(n^2)$ for any constant $c'$.

What can we say about $T(m,n)$?

With this exact phrasing, and without additional assumptions on the structure of $T$, you can't really say anything about it's asymptotic behavior in general.

First, observe that the function $m^2n^2$ satisfies the constraints, so you can at least $\Omega(m^2n^2)$. However, you can get much more than that.

Let $f(k)$ be some function. Think of $f$ as a very quickly-growing function (e.g. $f(k)=2^k$).

Now, think of $\mathbb{N}^2$ as a two dimensional plane, with the $m$ and $n$ axes. We require that along every vertical and every horizontal line, the function is asymptotically quadratic. This means that we can do whatever we want with finitely many elements of every row/column.

Thus, for example, you can set $T(k,k)=f(k)$ for every $k$, and set $T(m,n)=m^2n^2$ for all entries where $m\neq n$.

The diagonal of this function is huge. That is, $T(k,k)=\Omega(f(k))$. However, the function still satisfies the constraints. Also, note that you can make this function monotonic by adding $f(k)$ to all elements in the relevant row/column. That is, take
$$T(m,n)=f(\min\{m,n\})+m^2n^2$$
This still has the same property, only here we change finitely many elements, instead of a single element.


Is the Calibron 12 puzzle NP-hard? So, I was analyzing the Calibron 12 puzzle and to me it looks like a bin-packing problem. Is this puzzle actually a bin-packing problem and thus NP-hard for the perfect solution?

Basically, you can make your own calibron 12-ish puzzle by doing the following:

Take a rectangular piece of wood. Cut the wood into randomly sized rectangles. Jumble the pieces. Now put it back together into the exact same shape. (note there are technically 4 solutions, due to mirroring vertically or horizontally also fitting the exact shape)

It depends what you mean by this puzzle. If you mean specifically Calibron 12 then no, there is no growth factor (there are only ever 12 pieces) so the solution can be found in constant time (a very slow constant).

If however you want to know about puzzles of this nature it is hard to determine. The problem could potentially be phrased as, Is there some arrangement of these $n$ objects that can completely fill this square. Now to me this does not seem likely to be polynomial-time in nature (I am speculating based on the permutations of arrangements, but I do not have a proof).

The bin packing comparison does not really work however since this has almost nothing to do with separating $n$ objects into  the smallest number of bins. This is a category of questions called tiling problems.

Here is a paper that deals with Rectangle tiling, which is a related problem.


Algorithm for finding largest subset with equal number of even and odd elements A sequence of positive integers $a_1, ..., a_n$ is given. Compute the
  length of the largest continuous subsequence such that the number of
  even integers is equal to the number of odd integers in the subsequence.

I have thought that we could take all those integers mod 2 and store those in an array, then take two pointers $i=0,j=n-1$ and somehow sweep the table until #(even) = #(odd) is found in the subsequence inside, so that $j-i+1$ would be the optimal length. But I don't know how exactly to choose which of the two pointers to increase/decrease each time, so that I get an $O(n)$ algorithm.

Is my algorithm on the track, or can't it be used here? What algorithm do I need to apply and how can I think of its idea? (It would be preferable if this problem could be solved without using special data structures, such as AVL, segment, suffix trees, etc.)

Here's an easy linear time solution which uses $O(n)$ space. You could probably bring this down to $O(1)$ space using the techniques you mentioned.

First compute
$$ D_i = \# \text{even integers among $a_1,\ldots,a_i$} - \# \text{odd integers among $a_1,\ldots,a_i$}. $$
You can do this in $O(n)$.

Second, for each $\Delta \in \{-n,\ldots,n\}$, compute $a_\Delta = \min \{ i : D_i = \Delta \}$ and $b_\Delta = \max \{ i : D_i = \Delta \}$ (possibly these are undefined). You can do this in $O(n)$.

Finally, compute $\max_\Delta b_\Delta - a_\Delta$ for all $\Delta$ for which these indices exist. This also takes $O(n)$.


Quantum computer simulators with proper measurements I have been looking for quantum computer simulators and came across QCAD (http://qcad.osdn.jp/). It is stated on their website that "Measurement gates on QCAD are different from real measurements."

I wonder if other simulators, like those listed on Quantiki (https://quantiki.org/wiki/list-qc-simulators), might have the same problem of incorrectly mapping the design with the experimental values.

Based on QCAD's help file, their measurement gates are more like measure-later-suggestions:

  The measurement gates on QCAD only set "measurement flags". After the calculation, the measurement is performed.

I'm very surprised they would return a wrong answer instead of throwing an error. Most simlators won't do this, and if they do it should be reported as a bug.

For example, I use the same cheat in my own simulator (which you can play with in your browser), but I prevent any later operations that would cause the result to differ compared to deferring the measurement. So it lets you hit a measured qubit with a NOT gate, but a Hadamard gate or a controlled-by-unmeasured-qubit NOT gate will be forcibly disabled. Which is frustrating, but at least not misleading.

But Why?

The reason this limitation exists is efficiency. It's the difference between $\Theta(4^n)$ operations and $\Theta(2^n)$ operations needed to simulate a gate applied to an $n$-qubit system. Operations on mixed states are much more expensive to simulate than operations on pure states, and deferring measurement allows the simulation to only use pure states.

Workaround

A simple workaround for this limitation is to include an extra qubit, CNOT the value you wanted to measure onto the extra qubit, then measure the extra qubit. This is mathematically equivalent to measuring the original qubit, but will sidestep the limitation in the simulator that prevents you from then doing more things with the original qubit and still getting the correct result.

Easy Alternatives w/o By-Design Silent Mistakes

Microsoft's LiQui|>

Google's in-browser "Quantum computing playground"

Davy Wybiral's toy in-browser simulator

"Quirk", my own toy in-browser simulator


How to prove the language of suffixes of a regular language is still regular? Prove that if $ L \subseteq \Sigma^\star$  is regular, $L'$ is also regular where

$$ L' = \{w\mid{uw \in L \mbox{ for some string }u \in \Sigma^\star}\}$$

I'm new learning formal language and haven't proved stuff like this. But I'm sharing my thoughts here to make sure I'm on the right track. The first idea came to my mind is using close properties. Since $u$$w$ $\in$ L and $u$ $\in$ $\Sigma^\star$ so we know L is also regular. $L'$ is the concatenation of two regular languages. The regular languages are closed under concatenation thus $L'$ is also regular.

Any feedback or suggestions?

Your conclusion that $L’$ is a concatenation of two regular languages is wrong.

$L’$ is basically the set of suffixes of all the strings in $L$. Try to prove it for the prefixes and use the “closed under reverse operation” property of regular languages.

Hint for prefix language: make some special states as final state in the DFA of a regular language.


Mutable Object Values in a Functional Interpreter I am writing a functional style interpreter for a non-functional programming language that supports both primitive and object values. Primitives are passed by value while objects are passed by reference. I understand how to deal with primitive values but cannot find any good resources on handling mutable object values.

For example, take this ECMAScript inspired language:

var a = {'x': 1};
var b = a;
a.x = 3;

print a.x; // outputs 3
print b.x; // outputs 3

What is not clear to me is where the object's internal representation should live in the interpreter's non-mutable state. I can store non-mutable values in lexical environment records but I believe I need another level of indirection for storing objects because they are mutable.

I have considered having the interpreter state store a record of active objects, with lexical environments then storing a reference to one of these objects. Such references would need to be resolved dynamically against the current state object.

How has this been addressed in other works?

The basic way of implementing state is to explicitly implement the state monad. In fact, if you want a pure interpreter, you will be forced to do so one way or another. Since you have objects, and very likely recursion on those, you probably cannot get away with a stack, you need a heap (beware of memory leaks).

Thus, your interpreter shall carry around three things:

The current runtime environment $\eta$, which assigns values to variables, and acts like a stack. When a new variable is declared, you push its initial value onto the runtime environment, and pop it when it goes out of scope.
The current state $s$, which maps locations to values. Thus a location is a primitive value. Since objects are the only mutable values, a location is the same thing as an object id (but not the object itself!). The state may be implemented in any number of ways, but it has to support lookup : state -> location -> object and update : state -> location -> object -> state, i.e., updates return the new state.
The program $p$ to be evaulated.

Because the run-time environment $\eta$ is like a stack whose discipline reflects the recursive calls of the interpreter to itself, you probably won't have any trouble with it (you called it the "lexical environment"). The main point is that you need to carry around the state s explicitly and thread it through the interpreter so that each interpreted command takes in the current state and return the new state. This way a command like

a.x = 3;

can be interpreted as:

In the runtime environment lookup the value of a, expect it to be a location L.
Modify the object at location L so that its field x is set to 3.

The second step is done with update, i.e., it takes in the current state and returns the new state.

You may wonder why the small-step evaluator should take in the whole program p and return a whole program p' yet to be evaluated (as opposed to taking in just one command). This is not strictly necessary (few things are), but it lets you implemented non-local control (exceptions) and loops. For example, to evaluate

WHILE B DO C DONE
P

we use the fact that this is equivalent to

IF B THEN
   (C ; WHILE B DO C DONE)
ELSE
   P

So you could evaluate a while loop by converting it to the above conditional statement. There are other, more efficient ways of course, but this is the essential insigth about while loops, i.e., they are a form of recursion.

The interpreter for boa in my Programming Languages Zoo is a bit like what you want, but I am cheating because ObjDict in type ob uses mutable references. However, this is the only place where mutable store is used by the interpreter, see lines 149 to 161 of eval.ml where Project dereferences and Assign mutates object attributes. Perhaps it is not too hard to change the source to get what you want.


What is the computational complexity of k bit subset sum problem? The k bit subset sum problem is:

Input:

$(S, k, b)$ where $S$ is multi set of positive integers encoded in binary (base 2), $k$ is also positive integer encoded in binary (base 2) and $b$ is bit (binary digit) so that always $b\in\{0,1\}$.

Output:

True if exists subset sum of $S$ whose $k$ bit (binary digit) equals to $b$.

False if does not exist subset sum of $S$ whose $k$ bit (binary digit) equals to $b$.

I'm assuming that when $k=1$, the $k$th bit is the LSB.

If $b = 0$ then the answer is always positive, since you can take the sum of the empty subset.

If $b = 1$ and one of the numbers has its $k$th bit equal to $1$ then the answer is positive, so we can assume that all $k$th bits are equal to $0$. Reduce all numbers modulo $2^k$. Since originally the $k$th bits were $0$, all numbers are less than $2^{k-1}$. If the sum of all numbers is less than $2^{k-1}$, then clearly the answer is negative. If the sum of all numbers is at least $2^{k-1}$, arrange them in some arbitrary order $x_1,x_2,\ldots$, and sum them one by one until reaching the first sum $s_i = x_1 + \cdots + x_i$ which is at least $2^{k-1}$. Since $s_{i-1} < 2^{k-1}$ and $x_i < 2^{k-1}$, we see that $s_i < 2^k$. Thus the $k$th bit of $s_i$ is $1$. Hence the answer is positive.

Summarizing, here is our algorithm:

If $b = 0$, answer True.
If $b = 1$ and there exists a number whose $k$th bit is $1$, answer True.
If $b = 1$ and all $k$th bits are $0$, reduce the input modulo $2^k$, and answer True if the sum of all reduced numbers is at least $2^{k-1}$.


What is the name for this search algorithm? A colleague came up with the following search algorithm:

We have an array of sorted, distinct integers [$i_0$ < $i_2$ < ... < $i_n$]
We are looking for the index of $i_k$ (for simplicity suppose that $i_k$ is in the array)
We suppose that the elements are pretty uniformly distributed between $i_1$ and $i_n$

The algorithm:

let "position" be initially be 0
if $i_k$ == $i_{position}$, stop
otherwise:

calculate distance = $i_k$ - $i_{position}$
if we have just switched direction (eg. the previous distance was positive and this one is negative or vice-versa), make sure that abs(distance) < abs(previous distance) by adding/subtracting 1 from distance such that it gets closer to 0. Note: if distance is already is 1 or -1, it isn't adjusted.
let position be position + distance (see note below for possible optimization)
if position is positive, let position be min(position, n) (ie. don't overshoot the end)
if position is negative, let position be max(position, 0) (ie. don't undershoot the beginning)

I would be interested if somebody studied this algorithm and if so, what's its name? The best I could come up with is that it's a variant of "interpolation search", however I expect the above algorithm to be faster on x86 hardware because it only uses addition/subtraction which is faster than the division/multiplication used by "standard" interpolation search.

Note:

Instead of updating position by adding the distance (ie. position = position + distance) we can use the "average distance between consecutive elements" as a scaling factor: $$position \leftarrow position + distance / {i_n-i_0 \over n+1}$$

This should give a more precise estimate about the element position.

A disadvantage of the above is that it involves a division which is slow(er) on x86/x64 platforms. Perhaps we can get away with finding the closes power of two to the scaling factor (average distance between consecutive elements) and use shift to perform the division (ie. if $2^t$ is the power of two closes to the scaling factor we can do $position \leftarrow position + distance >> k$.

Update:

as people have pointed out the initial element needs to be $i_0$
added steps to avoid oscillating indefinitely between undershooting / overshooting the target
discovered the "galloping search" from Timsort which seems related but not the same

You may be interested to a related algorithm, known as Interpolation Search, which achieves on average the complexity of $O(\log \log n)$ for searching $n$ keys. This is the usual search you do when you scan a phone book for example.

This paper discusses the algorithm, which was originally introduced earlier (1957) by Peterson.

Related data structures: dynamic interpolation search and interpolation search for non independent data.


What is a super universe? I'm reading this well-known paper On Universes in Type Theory.
At first I expected something similar to Setω in Agda, but it turns out that it's even something more general.
It seems to generalize the universe construction from a plain inductive-recursive type to a binder (similar to $\Pi$ and $\Sigma$).
The main question I want to ask is, what's the intention behind it?

Here's some Idris code defining usual Tarski-style universes:

mutual

  public export data U : (level : Nat) -> Type where
    GroundU : Ground -> U level
    BinderU : Binder -> (a : U level) -> (b : (x : T {level} a) -> U level) -> U level
    UnivU   : U (S level)
    LiftU   : U level -> U (S level)

  public export T : {level : Nat} -> (code : U level) -> Type

I'm trying to generalize it into something like

mutual

  public export data U : (a : Type) -> (b : (x : a) -> Type) -> Type where
    GroundU : Ground -> U a ???
    ...

What should ??? be? The author of the paper just said universes should be closed under set formers.

edit: I think ??? is simply b ...

One intention behind having a universe operator and a super-universe closed under it, is to give a type-theoretic version of large cardinal axioms known from set theory. An inaccessible cardinal is like a type-theoretic universe. The next interesting kind of cardinal is a Mahlo cardinal. Speaking intuitively, a Mahlo cardinal is one that has "a whole lot" of inaccessible cardinals below it. What would this be in type-theoretic terms? It ought to be some sort of a universe $U$ with lots and lots of universes in it. This is what Palmgren is addressing when he considers super-universes.

There is also a more practical side to having many universes. It is useful to have inductive-recursive types in type theory, for all sorts of purposes. But they let us define new universes, so the question is how many? To get a feel for what Palmgren is doing, instead of shooting for the super-universe right away, try the following sequence of constructions in Agda (using induction-recursion):

Define one universe $U_0$, containing (a code of) $\mathbb{N}$ and closed under $\Pi$ and $\Sigma$. This kind of universe corresponds to an inaccessible cardinal.
Define an operator $U$ which takes any type $A$ and defines a universe which contains (a code of) $A$ and is closed under $\Pi$ and $\Sigma$. This sort of universe operator is akin to Grothendieck's axiom of universes. How many universes can we get by repeatedly applying $U$, starting from $\mathbb{N}$?
To get even more universes, we postulate a super-universe $V$ which contains lots of universes, as follows:

$V$ contains $\mathbb{N}$, and is closed under $\Pi$ and $\Sigma$
Given (code of) a type $A : V$ and a family $B : A \to V$, there is a universe $U$, which is an element of $V$, it contains all types of the family $B$, and is closed under $\Pi$ and $\Sigma$.

How many universes does $V$ contain? Note that we can get a family $B : \mathbb{N} \to V$ such that $B(n)$ is the $n$-th universe, and so $V$ must contain a universe $U_\omega$ which contains all of these. And this is only the beginning!


Finding a subset of objects with max value with constraints There are m people and n kinds of objects. Each person has exactly one instance of each kind of objects, but these objects have different values associated. Now I want to find a subset of objects from all those m*n objects satisfying the condition: it should have p objects of each kind (p < m), and a person cannot contribute more than p objects. I want to maximize the total value of the objects picked. I have tried several obvious greedy algorithms, but none of them has found the optimal solution. Is there an algorithm that is not NP hard?

Yes sure. You can solve this problem using Minimum Cost Maximum Flow technique. With this algorithm you can find the maximum flow in a network with weighted edges that have minimum total weight (weights can be negative). So let's build the model that fits our problem best.

Build the following graph

There are $n$ nodes in the set $A$ that represent each person.
There are $m$ nodes in the set $B$ that represent each type of object.

The set $A$ and $B$ are full connected the edge $e_{i,j}$ that connects node $A_i$ and $B_j$ has:

capacity: 1 (It can be taken at most once)
cost: $-w_{i,j}$ (We are looking maximum which is the same as minimize the negation of each value)

Source node $S$ is connected with an edge to each node in the set $A$.

capacity: $p$ (each person can carry at most $p$ objects)
cost: 0

Nodes on set $B$ are connected to target node $T$.

capacity: $p$ (each object can be carried by at most $p$ persons)
cost: 0

Maximum flow in this graph is $m * p$ since there is an answer where each object is taken exactly $p$ times.
Minimum cost is the negation of the answer you are looking for.

This problem is in P.


Algorithm for finding the root element I have the following interface:

public interface TreeElement<T>{
    public List<TreeElement<T>> getChildren();
}

Now, suppose I have a collection of TreeElement<T> representing a valid tree. How to find it's root element? Is there something more efficient than iterating over the whole collection?

I will make slightly stronger assumptions than that are provided in the question: we have a data structure, representing a tree, that consists of an array of vertices of the tree (allowing random access) and given a vertex, we have access to an array containing that vertex' children (again allowing random access). Furthermore we can check vertices for equality, and given a vertex we can (in $O(1)$ time) locate it in the main array.

On a tree of $n$ nodes, any strategy must take at least $\Omega(n)$ time in the worst case.

Consider a path of $n$ vertices. Define a vertex to be "examined" if it is accessed via the main array, via a children array or is reported as the root. Every non-leaf vertex must be examined by the algorithm: if some non-leaf vertex $v$ is not examined, we can make $v$ the root, making $v$'s child a child of $v$'s predecessor. This is not seen by the algorithm and it will incorrectly report the old root: making $v$ changes its children array (which is not seen by the algorithm as $v$ is not accessed at all) and changes the child array of $v$'s parent (which by the assumption of $v$ not being examined is not seen by the algorithm either).

Thus every non-leaf vertex in a path must be examined and any algorithm thus takes $\Omega(n)$ time.


Genetic algorithm neural networks converges, but suddenly stops I'm trying to create a genetic algorithm to train neural networks (because I'm to bad at back-propagation), and it works well until generation 18, where the loss stops to decrease and gets constant. The loss gets from 112 to about 90 in 18 generations and almost doesn't change:

Here is the genetic algorithm (I think the problem doesn't come from the neural network algorithm as it's very basic) in python :

# This is my reproduce function :
def reproduce(first,other,mutate=0):
    child = Entity() # Creates a new Neural Network (class Entity is the class of the Neural Networks)
    # Only two synapse matrices, each get the mean of its two parents
    child.syn0 = (first.syn0 + other.syn0)/2
    child.syn1 = (first.syn1 + other.syn1)/2
    if mutate:
        # Add some mutation if it's enabled, but it didn't work without it
        child.syn0 += child.syn0*(np.random.random()*mutate-mutate/2)
        child.syn1 += child.syn1*(np.random.random()*mutate-mutate/2)
    return child

ent = [Entity() for _ in range(20)] # Creates 20 new Neural Networks with random weigths on their synapses

nb_dna = 1
gen = 0
scores = []
max_gen = 100

while gen < max_gen:
    np.random.seed(int(time.time()))
    # The Neural Networks goes forward.
    for i,e in enumerate(ent):
        e.set_input(int(np.floor(np.random.random()*nb_dna)))
        e.forward()
        # In the forward function, the score is calculated as the result of a squared error cost function

    if gen < (max_gen-1):
        # Do natural selection
        ent.sort(key=lambda x: x.score) # Sort my ascending score (the lowest the score is, the closest the NN is to the expected result
        ent = ent[:4] # Kill all entities except the five 1st

        # Reproduce the winners
        for i in range(4):
            for j in range(4-i):
                # 1st reproduces with 2nd, 3rd, 4th and 5th,
                # 2nd with 3rd, 4th and 5th,
                # 3rd with 4th and 5th,
                # and then 4th with 5th
                    new = reproduce(ent[i],ent[j],mutate=0.2) # Changing the mutation rate "mutate" will only change the convergence speed
                    ent.append(new)
    gen += 1

Can you tell me if I'm doing something wrong, or if I'm going the wrong way ?
Else, is that the best I can get ? It's actually the first "real" genetic algorithm I create (previous ones were easy JS algorithm to try to find a target word, starting with random letters)

Well, I'm not an expert at genetic algorithms, but here's what I would check, coming from a neural networks perspective:

1) Learning rate (in your case, I think this is your mutation rate? Please correct me if I'm wrong). When a neural network exhibits this type of 'convergence', often you need to decay the learning rate either as a step function after a fixed number of iterations, or smoothly through exponential decay. Is that an option for you?

2) Initialization. Have you tried initializing your algorithm from different points and seeing if the convergence behaviour changes?

3) Adding noise. Sometimes you can get stuck in a poor local minimum, or at a saddle point. Small neural networks are more likely to get stuck in local minima. Saddle points proliferate in high-dimensional space. When learning stalls like this, adding some jitter to your parameter values and trying to learn from that new location can sometimes move you from a saddle point or local min to a better location in error space, and learning can continue from there.

4) Hyperparameter selection. How do you know your network is the correct size? Have you done some cross-validation to determine the number of hidden units you need, for example? Have you tried any kind of regularization?

Hopefully that provides some inspiration, or at least a starting point. Best of luck!


How to change the algorithm implication by changing the invariant? I have this specification in GCL:

$[Ctx C: n\geqslant 0\ \wedge\ b:[0..n-1]\ \text{of int}$

$\{Q:\text{True}\}$

$sum,i:=0,0;$

$\{\text{Invariant}\ P: 0\leqslant i \leqslant n\ \wedge sum=\sum_{j=0}^{i-1} b[j]\}$

$\{T:n-i\}$

$do\ i\neq n \rightarrow\ sum, i:=sum+b[i],i+1;\ od$

$\{R: sum=\sum_{j=0}^{n-1} b[j]\}$

$]$

But then I have been requested to develop the same summation of the numbers located in $b$ but with the following invariant and dimension function ($T$):

$\{\text{Invariant}\ P: 0\leqslant i \leqslant n\ \wedge sum=\sum_{j=i}^{n-1}
b[j]\}$

and

$\{T:i\}$

But I don't how to proceed. What I firstly supposed is that the summation must be done in reverse order.

Some suggestion, ideas?

Well, the new invariant does not hold in the code you posted, so I guess you are asked to change the code accordingly.

  What I firstly supposed is that the summation must be done in reverse order.

That might be a wise choice. You could try something like this:

$$
\begin{array}{l}
sum,i:=0,n;
\\
\{\text{Invariant}\ P: 0\leqslant i \leqslant n\ \wedge sum=\sum_{j=i}^{n-1} b[j]\}
\\
\{T:i\}
\\
do\ i\neq 0 \rightarrow\ sum, i:=sum+b[i-1],i-1;\ od
\\
\{R: sum=\sum_{j=0}^{n-1} b[j]\}
\end{array}
$$

I have not checked that this Hoare triple is valid, but it should be, possibly with some minor changes.


Nondeterministic finite state machine without any initial state possible Is it theoretically possible to have a nondeterministic finite state machine without any initial state or does it need at least one initial state?

In my favourite definition a finite state automaton is specified as 5-tuple $(Q,\Sigma,\delta,q_0,F)$, where $Q$ is the finite set of states, $\Sigma$ is a (finite, nonempty) alphabet, $q_0\in Q$ the initial state, $F\subseteq Q$ the set of final states, and $\delta\subseteq Q\times\Sigma\times Q$ the set of transitions. In that definition we would have exactly one initial state.

It is however very well possible that, for reasons of symmetry, one specifies a set $I\subseteq Q$ of initial states. There you can have one, several, of no initial state.

Short answer: consult the book, lecture notes, or scientific paper you are using. They set the rules for the game. Not us, not wikipedia.


Cuckoo hashing proof of cycle If we come to the situation when we have to insert again the original key into the original table, I believe we have found a cycle. Is there a way to prove this?

Yes there is, using algorithms such as Brent's cycle finding algorithm.

However, this is quite expensive and has fairly complicated code. What most implementations do is define some constant cycle/chain length, for example $\log n$ where $n$ is the number of elements in the hash table. If you find a chain (or cycle, but we never investigate whether it's actually a long chain or a cycle) larger than that constant we rehash or increase the hash table size.

But if your goal is merely the prove that you have a cycle, and you do not care about efficiency, the simplest method is to invoke the pigeonhole principle, and just loop $n + 1$ times where $n$ is the number of possible slots in the hash table. If you never find an empty slot you must have a cycle.


Which algorithm to use to find all common substring (LCS case) with really big strings I'm looking for a particular case of longest common substring (LCS) problem. In my case I have two really big strings (tens or hundreds of milions byte characters) and need  to find the LCS and other long strings.

A simplified example

$S_0$ = ABBCADGGHEEASSSCC

$S_1$ = ABDCADGGHMEASSSAC

the LCS = CADGGH (6 chars) and other long strings with 5 chars are CADGG, ADGGH and EASSS.

Which is the fastest algorithm to get all substrings with its length? (list all substrigs and legths) And in my case (very big byte substrings) which is the fastest LCS algorithm? (only get longest common substrings).

NOTE: In particular I don't have any space limit now, but this algorithm may be implemented in a mobile device in a future and is possible to have a very limited RAM/disk space (but always, at least, I have the same disk space available as the sum of file lengths).

I came across this problem before. I compressed the strings and applied dynamic programming on the compressed strings.

For compression techniques, I followed the methods described in this paper:
http://pdf.aminer.org/000/145/966/data_compression_using_long_common_strings.pdf

The speed was decent. But, it consumed some space though.


Basic question on intermediate code generation In this diagram, I have a doubt in the 2nd picture. How can different languages have same independent code optimizer ?

I think that different languages will have their own code optimizer(different) and then the optimized code will be converted to target machine code based on different machines.

So the arrow should be from one independent code optimizer (for each language) to many target machines.

Am I correct ?

The intermediate language is a relatively normal programming language and as such you can write an optimizer for it. Optimization passes like common subexpression elimination, constant propagation, or strength reductions are fairly independent of the programming language.

As long as the intermediate language can express all concepts from the source language reasonably well, there is little loss in just optimizing the intermediate representation. For example LLVM's intermediate language is well suited for representing C-like imperative languages. It also comes with a type system, so not much information is lost when translating from C, or Ada, or Java to LLVM.

There is of course a problem if the source language contains information that can't be encoded in the intermediate language. For example you could think about just optimizing x86 assembly instead of first translating to something like LLVMs IR. However assembly lacks many high level constructs that make it easier for the compiler to optimize things. For example it lacks a type system. If your Ada code restricted the value of a variable to be less than five, the compiler could use that information to optimize some conditionals. Such information would be lost when translating to Assembly.

Because of this mismatch it is not uncommon to first do some high level optimizations in the target language and then translate to the intermediate language to leverage all the work that went into the optimization passes that are suitable for many languages. This article about Rust's Mid-Level IR provides an example of this. But this step is not strictly necessary (For example Rust didn't do this at first), you just lose some optimization opportunities if you skip it.

In the end it's probably an engineering tradeoff. You lose a few opportunities for optimization by using an intermediate language. But you save enormous amounts of developer time by reusing existing optimization passes.


How to prove that the complement of a regular language is always regular? If A & B are regular languages, prove that complement of A is also regular language. (Closure of regular languages under complementation)

Can anyone help me with the proof??

If a language is indeed regular that means there is an FA that accepts it. The complement of L is just the language of all words that are not in L.

Thanks to Rick Decker for mentioning in the comments that this only works for FAs that are deterministic and to D.W for correcting the answer.

Now, a trick we can perform to test that the complement of L, namely L', is actually regular is to take the FA that accepts L and reverse all final states to non-final states and all non-final states to final states. Note that start states in the old FA become start and final states in the new FA.

This new FA will then accept all words present in L' which are words not in L.

In conclusion, take the FA accepting L and then form a new FA by:

Changing all final states to non-final states
Changing all non-final states to final states

The new FA accepts all words not in L, which is the language L'.


Big-O complexity when c is a tiny fraction Finding Big-O is pretty straightforward for an algorithm where $f(n)$ is

$$f(n) = 3n^4 + 6n^3 + 10n^2 + 5n + 4$$

The lower powers of $n$ simply fall off because in the long run $3n^4$ outpaces all of them. And with $g(n) = 3n^4$ we say $f(n)$ is $O(n^4)$.

But what would Big-O be if instead of 3 we were given a really small constant, for example
$$f(n) = 0.0000000001n^4 + 6n^3 + 10n^2 + 5n + 4$$

Would we still say $f(n)$ is $O(n^4)$?

Medium answer - yes. As you said for the previous case, in the long run $n^4$ outpaces all of them. This is still true despite the constant in front.

Check it out: plot.

Also, remember that $n^3$ and $n^4$ are both $O(n^4)$, and in fact are both $O(n^{10})$ because big-O is an upper bound. So you might ask "is there any tighter big-O bound on this function than $O(n^4)$, like $O(n^3)$, and the answer would be no.


How to "convert" nested loops into code taking advantage of parallel computing? Let's say that an algorithm uses several nested loops to accomplish it's task, for instance :

An algorithm treating voxels on several frames, so there would be
four dimensions : t (for time), x, y and z.
An algorithm evaluating a
function that takes n entries, searching for which entries there is a
certain result. For instance if we search f(a, b, c, d, e) = 2001
where each variable is tested between 0 and 100.

From what I understand, several APIs make you model the way your kernel is executed by the GPU with a 1-2-3d grid, but many of them don't provide n-dimensional grids for execution.

So if I had to treat a simple 2D image of 1024x2048 pixels, I could have simply made my kernel execute itself over a grid of that size instead of having to nest loops, but since most grids seem to be limited to 3 dimensions, what to do when I need to execute work for more than 3 dimensions (like in my second example) ?
Should I put loops directly in my kernels ?

Thank you.

EDIT :
Some pseudocode :
Let's say that I want to test for which inputs a given function has a certain value, I could have some brute force approach like that :

for a in 1...100 {
for b in 1...100 {
for c in 1...100 {
for d in 1...100 {
     if f(a,b,c,d) == 1984 {
        equationSolutions.append((a,b,c,d))
     }
}

Now with grids, a certain kernel can be executed over the grid (sorry, I may not use the right term, there is a much better explaination about grids here), so if you want to treat each pixel of an image of 2048x512 pixels, instead of doing :

for x in 0...imageWidth {
for y in 0...imageHeight {
   treatPixel(x,y)
}

You will define grid as a 2D grid of size 2048x512 and then your kernel won't contain any loop, it will just get it's position on the grid as an argument :
func myPixelFunction(positionInGrid) {
treatPixel(positionInGrid.x, positionInGrid.y)
}

My question is that, since most grids are limited to 3 dimensions, what to do if you want to execute code that requires more than 3 dimensions ? (like my code trying to solve a function ?).

From what I understand, in cases like the ones I showed, grids make more sense than loops on GPUs since grids enable to parallelise the work, making several threads work in parallel on the same function/kernel, but while it's really easy to simply use position in grid when you are treating data that is representable by the grid, I don't understand how to write code using grids when I needs to word on "additional dimensions".

EDIT #2 :
This SE question is similar to mine.

Let's say you want to iterate over a,b,c,d each ranging from 0..99.  There are two ways to do that.

Approach #1: fewer nested loops

Set up a 100x100 grid, which will handle a,b.  Handle c,d by explicit nested loops:

treatPixel(a,b):
for c in 0..99:
    for d in 0..99:
        doSomething(a,b,c,d)

Approach #2: bigger grid

Set up a 10,000x10,000 grid.  Then decode the x-coordinate to a,b and the y-coordinate to c,d, like this:

treatPixel(x,y):
a := floor(x/100); b := x mod 100
c := floor(y/100); d := y mod 100
doSomething(a,b,c,d)

Which to choose?

Either one should work.

Assuming the number of iterations greatly exceeds the number of compute elements in the GPU, the difference between the two probably comes down to different memory locality effects.  You can try implementing both of them, benchmarking, and seeing if one is faster.  If there is little or no memory access and doSomething() is compute-bound, they'll probably both run at about the same speed.


Algorithm for finding a mouse hole in a wall in O(n) time There is this question:

  As a result of the US Election, a wall is built along the entire Canadian border. You have been told
  there is a mouse hole in the wall, but it can only be seen when you are standing in front of it. Your
  task is to find the mouse hole by walking along the wall; however, you are standing in Minnesota
  and do not know whether the hole is East or West of your current location.

  Give an algorithm that will allow you to find the mouse hole in O(n) steps, where n is the (unknown
  to you) distance in steps from your initial location to the mouse hole.

I was thinking that to find the mouse hole in O(n) steps, I would have to go both East and West at the same time.

But seeing that I can't do this (or maybe I can?), I thought that regardless of direction I first take since I'm traveling around the US border and then around the Canadian border, I would have traveled a linear time. I'm also thinking that this problem might resemble a graph?

How can I go about writing an algorithm to describe this?

This problem goes by various names, including the linear search problem and the cow path problem. The solution indicated in Denis's answer is optimal for deterministic algorithms (though the competitive ratio is 9 rather than 8), but randomized algorithms can do almost twice as better; see Kao, Rife and Tate.


What is the branching factor for nondeterministic games? Given a nondeterministic game how could one know the branching factor of it? Is it the number of all possible outcomes?

I have an example game in which you have some cards. The goal is to get rid of all of them. At the start of the game you get 7 random cards. There is a draw pile from which you take cards if you can't (or don't want to) play a card. You can't see the cards in that pile and they are in random order. The amount of card types in the simple version is equal to 52. If I understand correctly that means that the branching factor is at least 52 for every move plus 52 times the number of cards of the player (player's don't know other's cards). Is my thinking correct? It seems to be too big (416 at the start of the game (52 + 52*7) from the perspective of another player and 59 (52 + 7) from the player's own perspective, when Go has "only" 250) but I'm not expert in this.

The branching factor depends on exactly how you model the game.  A standard way to model games that have some randomness is to imagine adding another player (the "dealer") whose only purpose is to make a random choice.

So if your game involves only one player Alice, we'll add another player Declan (the dealer).  Alice and Declan alternate turns.  During her turn, Alice can either play one of her cards or choose to draw from the pile.  Thus, if Alice has $n$ cards, she has $n+1$ actions she can choose from.  During Declan's turn, if Alice previously chose to draw, Declan selects one of the remaining cards and adds it to Alice's hand; otherwise he does nothing.  Thus, if there are $m$ cards remaining in the pile, Declan has either $m$ actions he can choose from, or only one.

With this model, the maximum branching factor is 53 (assuming Alice can have up to 52 cards in her hand).


Will ternary computers be faster than binary? If we had a computer in base 3 which used the characters {0, 1, 2} instead of just {0, 1} (and we implemented a ternary logic on the hardware), will this computer be faster than computer using binary?
Why or why not?

If we had a computer with even a higher base than 3 will it be more fast or slow? Which is the best base for fast processing and computation?

It depends. A number represented in base 3 will have fewer digits than the same number in base 2. Perhaps this means computations will be faster, since you have to work with fewer digits. However, perhaps the operations will become slower (since they're more complicated) so there might be no net gain - or perhaps even worse performance! There's no way to tell how fewer, complicated operations will compare to more, but simpler operations.

Another consideration is arithmetic. If you are working in base 10, then division by 10 is really easy with divisions in other bases being more work. Similarly, in base 2, division by 2 is easy. In base 3, division by 3 would be easy. If your application requires frequent division by 3, then base 3 would be beneficial.


How to reduce 2-coloring to 2-SAT Let $G=(V,E)$ be an undirected graph in which $V = \{v_1,v_2,\dots,v_n\}$.

I need to describe a reduction from the 2-coloring problem to the 2-SAT problem (in polynomial time).

I thought of splitting each vertex $v_i$ into $v_i^*$ and $v_i^{**}$, one for each color. Then I was thinking about making for each edge $(u,v)\in E$, two correspond literals: $(u^* \lor v^*)$ and $(u^{**} \lor v^{**})$.

I know I'm on the right track but I can't prove it.

any ideas?

If all you require is a polynomial-time reduction, then test in polynomial time if $G$ is $2$-colourable. If it is, map it to the formula $X$; if it isn't, map it to $X\land\lnot X$.


What are the differences between computer vision and image processing? What are the differences between computer vision and image processing? For example, in object recognition, what are the roles of computer vision and image processing?

In image processing, an image is "processed", that is, transformations are applied to an input image and an output image is returned. The transformations can e.g. be "smoothing", "sharpening", "contrasting" and "stretching". The transformation used depends on the context and issue to be solved.

In computer vision, an image or a video is taken as input, and the goal is to understand (including being able to infer something about it) the image and its contents. Computer vision uses image processing algorithms to solve some of its tasks.

The main difference between these two approaches are the goals (not the methods used). For example, if the goal is to enhance an image for later use, then this may be called image processing. If the goal is to emulate human vision, like object recognition, defect detection or automatic driving, then it may be called computer vision.


Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates A Boolean function $f : \{0, 1\}^n → \{0, 1\}$ is called monotone if changing any of the $n$ input bits $x_1, \ldots , x_n$ from $0$ to $1$ can only ever change the output $f(x_1, \ldots ,x_n)$ from $0$ to $1$, never from $1$ to
$0$.

I know how to do a simple proof of exhaustion for $f : \{0, 1\}^1$ and $f : \{0, 1\}^2$, but I do not know how to prove the following statement for $f:\{0,1\}^n$: any monotone Boolean function is computable by a circuit containing only AND and OR gates.

Any Boolean function can be written as a DNF. Each clause in the DNF specifies one truth assignment for which the function holds. For example, the DNF form of XOR is $(x \land \lnot y) \lor (\lnot x \land y)$.

The main observation is that if the function is monotone, you can remove all the negated literals (why?). Once you do that, you get a formula for the function which uses only AND and OR. Some clauses in this formula subsume others (for example, $x$ subsumes $x \land y$). If you drop all the subsumed clauses, you arrive at the minterm representation of the function. (A minterm is a minimal satisfying assignment.)

It's a bit more confusing, but you can also do everything using CNFs. This way you arrive at the maxterm representation.


Smallest(k) in red-black tree. How is it O(logn)? Is it the same as find minimum for a binary search tree?
I know recoloring runs in O(logn) and rotations are O(1).

Even if we are wanting it to find the 'k-th' smallest key in the red-black tree.

Could someone help me understand it in more detail? Thank you!

The idea is to use an algorithm whose running time is linear in the height, which is $O(\log n)$ in a red-black tree. As JarkkoL mentions, you can maintain a count of the number of children in every subtree without effecting the asymptotic running time of the usual operations (insert, delete and search). You then go down the tree. Suppose you're at a vertex $v$ whose two children have subtrees of sizes $L,R$. If $k = L+1$ then $v$ is the $k$th smallest. If $k < L$ then you descend to the left child. If $k > L$ then you descend to the right child and replace $k$ by $k-L-1$. This algorithm runs in time $O(\log n)$.


Asymptotic vs real-world complexity Let's say an algorithm has an asymptotic time complexity of $\Theta(N)$. However in practice, $N$ is bound by a small upper limit (e.g. the size of a character set). Can we then say the complexity is $\Theta(1)$? Or is there a better way of describing the performance of an algorithm in a particular real-life situation?

If $N$ is bounded by a small upper limit, asymptotics cease to be useful. At that point you want either exact operation counts, or even better just measure actual speed.


Is 1-in-k SAT NP-complete for k > 3 It is well-known that 1-in-k SAT is NP-complete for k=3. What about for k > 3?

It's still in NP by using a truth assignment as a proof.

You can reduce 1-in-3 SAT to 1-in-$k$ SAT to show hardness as follows. Let $\phi$ be an instance of 1-in-3 SAT with clauses $C_i$ for $1 \le i \le m$. For each $C_i$ we define $C_i'$ by adding $k - 3$ instances of the literal $y$ (where $y$ is a new variable that does not appear in any $C_i$). We also construct the new clause $C_{m+1}'$ which has $k-1$ occurences of the literal $y$, and one occurence of the literal $\neg y$. Let $\phi'$ be the instance of 1-in-$k$ SAT with clauses $C_i'$ for $1 \le i \le m+1$. I claim $\phi'$ is a YES-instance of 1-in-$k$ sat if and only if $\phi$ is a YES-instance of 1-in-3 SAT.

First, assume $\phi'$ is a YES-instance, and choose a satisfying assignment. $C_{m+1}'$ is satisfied only when $y$ is false, so this assignment has $y$ false. Therefore, the literals $x$ are not satisfied, and so exactly one of the first 3 literals of $C_i'$ is satisfied for each $i$. These are exactly the literals of $C_i$, so exactly one of the literals of $C_i$ is satisfied for each $C_i$ and so $\phi$ is a YES-instance.

In the other direction, suppose $\phi$ is a YES-instance, and choose a satisfying assignment. Extend this assignment to give $y$ the value falsehood. This assignment shows that $\phi'$ is a YES-instance.

To illustrate the reduction, here is an example (going to 1-in-5 SAT):

$\phi = (x_1 \vee \neg x_1 \vee x_2) \wedge (x_3 \vee \neg x_2 \vee \neg x_2)$

$\phi' = (x_1 \vee \neg x_1 \vee x_2 \vee y \vee y) \wedge (x_3 \vee \neg x_2 \vee \neg x_2 \vee y \vee y) \wedge (y \vee y \vee y \vee y \vee \neg y) $