Hash tables - probing for collisions run time The question is a true or false question:

Hash tables using probing for collisions run in constant time with respect to how many items are in the hash but are at least linearly dependent on how full the hash is.

I think it's true but I don't fully understand why and I don't understand the term linearly dependent.

Any help would be great, thanks.

The average number of positions addressed is
$$ \frac{1}{2} \left(1 + \frac{1}{1-\alpha}\right) $$
for linear probing and $1 + \alpha/2$ for chained hashing. Here $\alpha$ is the load factor. For each constant $\alpha$, this average is constant, but it depends on $\alpha$. The expression $1/(1-\alpha)$ blows up as the table gets full ($\alpha \to 1$), which is probably what is meant by the dependence is at least linear. The dependence is on the load factor rather than on the absolute number of elements in the table, which is not the deciding factor.

Usually, a linear dependence (not to be confused with the same terminology from linear algebra!) would be $\Theta(\alpha)$, at least linear would be $\Omega(\alpha)$, and more than linear $\omega(\alpha)$; but here $\alpha \to 1$ rather than $\alpha \to \infty$ so terminology is not standard. Perhaps the correct variable, which does go to $\infty$, is $1/(1-\alpha)$. In this case, we do have linear dependence for linear probing.


Decidability of factoring algebraic equations Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution:

$$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$

And some arbitrary factorization constraints, say:

$$f(x)g(\theta)e^{\phi(\theta)^{T}u(x)}$$

Can I factor the equation into the form above where f, g, and phi are functions depending only on x, theta, or x respectively? This is something as humans we do all the time. The problem I gave above is an instance of "is this distribution in the exponential family", but of course there are simpler and less puffy versions of this:

Given the equation:

$$f(x,y,z) = x^2 + y^3 - e^{z}$$

Can I factor this into:

$$ f(x)*g(y)*h(y,z)$$

This feels undecidable to me. The tree of legal "algebra moves" from the root is infinite. If a program cannot find a solution in n moves, there is no guarantee that the solution is not at n + 1 moves, so I can't think of a halting condition. There doesn't even seem to be a good greedy solution to this, other than human intuition.

Any mathematica wizards out there know how to write a one liner to this?

Interesting question. Factorization of functions, including factorization of polynomials is in fact a classical problem throughout history of mathematics.

For the sake of contradiction, assume that $$x^2 + y^3 - e^{z} = f(x)*g(y)*h(y,z)$$

For the sake of simplicity, assume that $f, g, h$ are continuously differentiable inside $D$, the place where we are interested.

Now treating $y$ and $z$ as constant, take partial derivative with respect to $x$. (Aha, you might say, why didn't I think of that?!)

$$2x = f'(x)*g(y)*h(y,z)$$

Since $2x$ is not constant, $f'(x)$ cannot be constant 0. Shrinking $D$ if necessary to make sure $f'(x)$ is never 0, we have $$2x/f'(x) = g(y)*h(y,z)$$
That means, both $2x/f'(x)$ and $g(y)*h(y,z)$ are constant functions since the former is constant w.r.t. to $y$ and $z$ and the latter is constant w.r.t. to $x$. So we will have
$$ -e^z=\frac{\partial(x^2+y^3-e^z)}{\partial z} = \frac{\partial(f(x)*g(y)*h(y,z)}{\partial z}=\frac{\partial(f(x)*\text{(some constant)})}{\partial z}=0$$
which cannot be true.

The above reasoning should give you a pretty good idea that particular factorization cannot hold nicely because of too many independences between the variables in the factorization. In fact, we can show that no such $f,g,h$ exist without assuming continuity of any of $f, g, h$, as long as it is required that equality holds for a small 3D space. Note that 2D space will not be enough since we can have, letting $x=0$, $$0 + y^3-e^z=1*1*(y^3-e^z)$$

It will require some work to formulate the more general questions of decidability of function factorizations clearly enough so that it might be able to have a clear answer. It looks like if many dependencies are required, then the set of problems is probably decidable. If you are interested enough, you could try formulating those problems and raising new questions.

For related result on polynomials, we can search for "decidability of polynomial factorization".


Reason behind declaring iteration variables on a method level Lately, I have been in touch with some C++ snippets, and I have a very strange observation on the tiny detail:
Most of the times, I see, that people declare iteration variables outside of the for/while definitions, and then initialise them inside for/while definitions, like:
int i, j, k;

for(i = 0; ..; ..) { } //note, this omits declaration of "i"

I wonder what is the reason behind this? why would one want to scope a loop-level temporary variable and its identifier on a method-level?
Is this conventional? does it help compilation's lexical translation? an optimisation for static code analysis? what is the purpose?
It (important) certainly looks ugly, especially when there are numerous variables in the method; it (important) reserves variable identifiers (on a method-level); and (less important) it definitely occupies more space in the memory.
Any points?
Appreciations.

No, this is not conventional if writing C++. People who do this might have a C background. Indeed, in old C89, you had to declare all variables at the beginning of your scope. Of course, even if you didn't start programming with C89, you might have been exposed to out-dated guides or material and you might have picked up the habit. As we know, it is sometimes difficult to unlearn something.
In general, variables should be declared as close as possible to their actual site of usage and thus we don't unnecessarily pollute the scope, exactly as you point out. This is also defensive programming, it helps readability and protects from mistakes.


The notion of density of distribution I have difficulties in understanding the notion of density for distribution.

Notion of density for distribution. A distribution $H$ over $\{0,1\}^n$ has density $\sigma$ if for every $x \in \{0,1\}^{n}$, $Pr[H=x] \leq \frac{1}{2^n\sigma}$.

The following is my desperate tries to understand the notion.
if $H$ is uniform distribution over $\{0,1\}^n$ then  for every $x \in \{0,1\}^n$, $Pr[H=x]=\frac{1}{2^n}$.

if a distribution $H$ has density $\sigma = 1$ then $P[H=x]\leq\frac{1}{2^n}$, so distribution $H$ is upper bounded by the uniform distribution.

if a distribution $H$ has density $\sigma = \frac{1}{2}$ then $P[H=x]\leq\frac{1}{2^{n-1}}$, so distribution $H$ is upper bounded by the uniform distribution over $\{0,1\}^{n-1}$.

if a a distribution $H$ has density $\sigma = \frac{1}{2^n}$ then $P[H=x]\leq 1$.

So density $\sigma$ might determine the part of distribution over $2^n$ where the actual "probabilistic weight" should be placed? However it's always upper bounded, therefore we can always say something about the upper bound?

As you see I don't have intuition behind this notion and I would appreciate any help.

This notion seems to be a measure of uniformity. If $\sigma=1$ you get a uniform distribution on $\{0,1\}^n$ (since the sum over all strings of length $n$ is $1$), but for other $\sigma$s (e.g. $\sigma = 2^{-k}$) it's still  distribution on $\{0,1\}^n$, not on $\{0,1\}^{n-k}$ or similar. Thus saying that a distribution on another (disjoint) set is an upper bound is absolutely wrong (but they are related, s.b.).

If for some $x$ the probability is greater than $\frac{1}{2^n}$ it has to be smaller for others. On the other hand for $\sigma=\frac{1}{2}$ at least half of the strings have nonzero probability since the sum of any number of elements $< 2^{n-1}$ is smaller than $1$. This holds for any $\sigma > 0$, i.e. $\sigma 2^n$ elements have nonzero probability.

Using this you can compare the distribution for $\sigma=2^{-k}$ to the distribution for $\sigma=1$ (i.e. uniform) on $\{0,1\}^{n-k}$. It's easy to see that the entropy of the distribution with $\sigma=2^{-k}$ on $\{0,1\}^n$ (let $H$ be a random variable with this distribution) is at least the entropy of the uniform distribution on $\{0,1\}^{n-k}$ (RV denoted by $U$) since for every injection $f: \{0,1\}^{n-k}\rightarrow \{0,1\}^n:$
$$\mathbb{P}(U=x)\geq \mathbb{P}(H=f(x)) \quad .$$


Point Location Problem in Polygon in Repetitive Mode for a Simple Polygon I consider Point Location Problem in Polygon in repetitive mode in the case of simple polygon.

In computational geometry,Point Location Problem in Polygon problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon.

There are few method that work in Single-Shot approach, where the input is a polygon $P$ and a single point $q$ (no preprocessing time). Ray casting algorithm is the famous algorithm for single-shot, it takes $O(n)$ to determine whether a point $q$ belongs to polygon $P$.

In addition, there is a repetitive approach, where instead of single point $q$ we should check the sequence of points, therefore the preprocessing is required. Division wedge is a algorithm that works in repetitive mode. Query time of division wedge is $O(\log n)$ and preprocessing time is $O(n)$. Division wedge assumes that there is a central point in polygon, visible from every vertex of polygon (part of the kernel of the polygon). The problem is a central point can be easily determined in convex polygon as well as in star-shaped polygon, but what to do in the case of simple polygon.

If division wedge is applied in the case of simple polygon how we can determine a central point in simple polygon? If division edge in not applied if there is the more efficient way to solve a problem in simple polygon than in arbitrary planar subdivision.

First question:

By (my interpretation of the) definition, a "central point" exists if and only if the polygon is star-shaped; this condition can be tested in $Θ(n)$ time.  So the only thing you can do is run this algorithm, apply division wedge if you find a non-empty kernel, and apply another algorithm if you find an empty kernel.


Constructing a Divide and Conquer Algorithm I'm thinking of using something similar to the Merge Sort algorithm. So the recurrence running time of Merge Sort is T(n) = 2T(n/2) + n. What should I do about if n/2 is less than or equal to m, OR if n/2 is greater than or equal to m?

I believe the given function should be location inside the "Merge" function of the Merge Sort.(Since we're merging a sorted array) Thank you for your time.

Edited:
I'm thinking if n/2 is less than or equal to m, use the "Given" function . Otherwise use the original "Merge" function (The usual Merge for Merge Sort)

I believe you have misunderstood the question. The magical merge algorithm merges two lists of size $m$ in time $m^{1-\epsilon}$ for every possible $m$ (of course, such an algorithm is impossible). Since merging usually takes linear time $O(m)$, it is always better to replace it with the magical merge algorithm. You then get a different recurrence for your magical merge sort, and the running time should come out linear rather than $O(n\log n)$.


Water Jug Problem in AI In AI we can classify a problem in 3 classes,  ignorable, recoverable or irrecoverable problems. Now while reading Water jug Problem

I am wondering in which of these 3 class it should fall? It should reside under recoverable right? As we can go back to the previous state in Water Jug Problem by altering the water level, I think it is recoverable. Is my thinking right?

Recoverable, as we can pour all water back to the 12L jug to restore the original state, hence any state derived thereof (by following the same steps from the start). The problem is, also, solvable:

[12, 0, 0]
[4,  8, 0]
[4,  3, 5]
[9,  3, 0]
[9,  0, 3]
[1,  8, 3]
[1,  6, 5]
[6,  6, 0]  # <-- SOLVED; 7 steps

DETAILS: The problem stated as-is is recoverable, and in a machine learning problem statement, we take the problem as-defined, not how it could be defined. For any # of jugs of any sizes, as long as we start with only one jug filled, the entire system is recoverable - but if more than one jugs are filled, that changes the entire problem, and can make it irrecoverable.

[0, 0, ..., X,   ..., 0] <-- only one jug filled
[2, 0, ..., X-2, ..., 0]
...
[2, 4, ..., ?,   ..., 7] <-- some arbitrary state
...
[0, 0, ..., X,   ..., 0] <-- RECOVERED; empty all other jugs into original jug

Update: the system is also recoverable if starting with any # of jugs filled, as long as they're fully filled. They also don't necessarily have to be fully filled, but it then becomes jugsize-dependent, and no generalization w/o mathematical formulation can be made.

DEFINITIONS: OP hasn't defined "recoverable", "irrecoverable", or "ignorable" - and neither Google nor DuckDuckGo reveal much. Giving my best attempt at making sense of it, each can be defined as follows:

Recoverable: state t0 can be restored from any other state T when starting at t0
Irrecoverable: there exists some state T we can get to from t0, but no longer revert to t0
Ignorable: we don't care, and can solve the problem at hand either way

Irrecoverable example: [0, 1, 2] --> [0, 0, 3]. Goodbye forever, 1 liter & 2 liters.

Ignorable example: goal: two jugs empty. In this case, both the original [12, 0, 0] and the irrecoverable case [0, 1, 2] work.


Concatenate multiple integer arrays such that number of inversions in resulting array is minimal Given N arrays of variable length.

Find a way to concatenate the arrays in such a way that the number of inversions is minimum

An inversion for an array Arr can be defined as,

a pair of indices (i,j) such that,

i != j

i < j

Arr[i]>Arr[j]

I tried to concatenate the arrays on the basis of sum, such that the one with minimal sum goes first and one with maximal sum goes last.

It didn't work out though.

Example:-

[14, 18, 18, 20, 16, 6, 11] SUM:- 103

[2, 4, 11, 40, 20, 14, 19] SUM:- 110

[14, 18, 18, 20, 16, 6, 11, 2, 4, 11, 40, 20, 14, 19] Inversions:- 42

[2, 4, 11, 40, 20, 14, 19, 14, 18, 18, 20, 16, 6, 11] Inversions:- 40

As an exercise to the reader, two lemmas:

Lemma 1. If $a, b$ are strings of symbols with a partial order, and
$\text{numinv}$ counts the number of inversions in a string of symbols then
$$\text{numinv}(ab) = \text{numinv}(a) + \text{numinv}(b) + \text{crossinv}(a, b)$$
where $$\text{crossinv}(a, b) = |\{(i,j) \in \{1,\dots,|a|\}\times\{1,\dots,|b|\} \mid a_i > b_j\}|.$$
Lemma 2. $\text{crossinv}$ has the distributive property over
concatenation, that is for strings $a, b, c$ we have
\begin{align}
\text{crossinv}(a, bc) &= \text{crossinv}(a, b) + \text{crossinv}(a, c)\\
\text{crossinv}(ab, c) &= \text{crossinv}(a, c) + \text{crossinv}(b, c).
\end{align}

You can use the above two lemmas repeatedly to generalize, and see that for a tuple of strings $(x_1, \dots, x_n)$
$$\text{numinv}(x_1x_2\dots x_n) = \sum_{i=1}^n \text{numinv}(x_i) + \sum_{i=1}^n\sum_{j=i+1}^n\text{crossinv}(x_i, x_j).$$
Since the first sum is constant for any re-ordering of $x$, we can ignore it for our problem. In fact, if we sort the symbols inside each $x_i$ you can compute $\text{crossinv}(x_i, x_j)$ in $O(|x_i| + |x_j|)$ time. So we only need to minimize the second sum by re-ordering $x$.
However, I do believe that this is a difficult problem to solve optimally. A greedy swapping approach won't work. As a counter-example (I apologize for the somewhat length counterexample, it's just one I found during experiments with randomly generated arrays) consider the following array of arrays:
$$(39, 23, 9, 31, 1, 44), (35, 41, 1, 49, 23, 38, 4, 11), (13, 10, 17, 5, 38, 50, 46), (28, 21), (45, 46, 33)$$
This has $102$ inversions when concatenated. The unique optimal concatenation order is
$$(28, 21), (39, 23, 9, 31, 1, 44), (35, 41, 1, 49, 23, 38, 4, 11), (13, 10, 17, 5, 38, 50, 46), (45, 46, 33)$$
with $100$ inversions. However this can't be generated with a simple swap. I've found similar counterexamples for single-symbol substring rotations.
A simple greedy growing approach won't work either. $(41, 3, 31), (16, 11, 47)$ is uniquely optimally ordered, but if we extend this with $(30, 20)$ the unique optimal ordering becomes
$$(16, 11, 47), (30, 20), (41, 3, 31)$$
Which is in no way a simple extension of the previous.
To go even further, Tim shows in this answer that if you view $\text{crossinv}$ as a black box function, and you don't exploit any of its special properties, then this problem is NP-complete and you're doomed to fail. So any efficient optimal algorithm must use some special property of $\text{crossinv}$.
For very large amount of arrays you will probably see the best real-world results using a non-deterministic technique such as genetic evolution to optimize the number of inversions, although this wouldn't guarantee optimality. Or perhaps I'm overestimating this problem's difficulty and someone comes along with a better answer.


Application of shortest vertex-disjoint path with time window I am working on finding shortest disjoint path problem, When there are distinct origin destination pairs and there is a predefined time window (or length) associated with each object (which we want to move from one origin to its specific destination). This time window will tell us how long it will take for the object to pass a particular point on the network.

These objects should not encounter each other in any ways on the network, so it is a vertex-disjoint path problem with respect to time. For example if I have two objects A and B, and object A will pass node 1 from 10:00 a.m. to 12 p.m., during these time periods object B cannot cross this node, but any time after 12.00 and before 10 (as long as the time window of B allowed) B can pass through node 1.

I want to know if there is any application of this problem in computer science?

Your problem is not clearly defined, but it's likely it can be solved by running a standard algorithm on a longer graph.

If $G=(V,E)$ is your original graph, build $G'=(V',E')$ by making $t$ copies of each vertex in $G$, one per time slot (where there are $t$ time slots): call the copies $v_1,\dots,v_t$.  Now for each vertex $v \in V$, add an edge $v_i \to v_{i+1}$ for each $i$ (this corresponds to an object staying at vertex $v$ throughout time slot $i$).  Also, for each edge $(v,w) \in V$, add an edge $v_i \to w_{i+1}$ for each $i$ (this corresponds to an object moving from vertex $v$ to $w$).

Now you're looking for vertex-disjoint paths in $G'$.  There are standard algorithms for finding vertex-disjoint paths in $G'$ (e.g., using network flow or other methods).  If you want a collection of shortest vertex-disjoint paths, that might be possible, but you'll need to define precisely what objective function you want to minimize before we can suggest an algorithm.

This general approach can likely accommodate many additional requirements, such as that traversing a particular edge takes a certain amount of time (just use that as the length on the edge), or that we don't know the starting time when each object enters the system (add a source vertex for each object, with edges from the source to each place that the object might enter the system).


Context free grammar construction My problem with CFG is, I am to generally create ones that don't have requirements such as:

$\qquad \{a^m b^n \mid m \le n \le 2m \}$

I have no clue where to begin, and how to approach it. I was wondering if you can provide some hints for such daunting problems, along with how to solve that problem.

This is not homework, this is merely me trying to learn it. I solved many problems that did not have such requirements, but those problem are the ones where I am forced to look at the solution.

Just read the constraint carefully. $m\le n$ tells you that you must have at least as many b's as a's. The other part: $n\le 2m$ tells you that you cannot have more than twice as much a's.

Here is an EBNF description that yon can convert to BNF.

$S\to aSb[b] \mid \epsilon$


Why does the concatenation of the empty set with any language give the empty set? Why does the concatenation of $\emptyset$ with any language give $\emptyset$. I would like to know the intuitive explanation for it.

Let $L_1, L_2$ be languages, then the concatenation $L_1\circ L_2=\{w\mid w=xy, x\in L_1, y\in L_2\}$. If $L_2=\varnothing$, then there is no string $y\in L_2$ and so there is no possible $w$ such that $w=xy$. Thus for any $L_1$, we'll have $L_1\circ\varnothing = \varnothing$.


How to read a number from highest place value to lowest? So we all know it's easy to read a number from lowest place value to highest.
A simple algorithm would be like :
while(n):
    a=n%10;
    n/=10;

but the question is how do you read it oppositely?
for eg : 12312. must result in me getting first 1 then 2 then 3 and so on.
I don't wanna form an array or reverse the number, unless there is a way to reverse the number with constant time-complexity.
Edit : I think the question is extremely vague so I'll try to explain what I need it for.
So i've been working on optimizing my code for an algorithm to convert binary to decimal.
My algorithm is : while(n) c+=(n%2)<<b++ , n/=10;
But then I figured I don't need the variable b, if i could somehow start from the front then an algorithm like c=2*c+n%2 would work.
I don't really wanna use a while loop to reverse a number as I think it would be inefficient than just having an extra variable.
An alternative that I thought of was having a float c then c=c/2+n%2 but the you'll need to know the number of digits of n. Which I could use logarithm for but I don't know that at that point if it is just better to use another variable. At its heart it is a time vs space complexity problem.

Well, you could construct the inverse of that number. 12312 will become 21321 and then use the piece of code you wrote. So:
while (n)
{inverse = inverse * 10 + (a % 10), a /= 10;}.


Find all pairs (i, j), such that i + (i+1) + (i+2) + ... + j = n We have give positive integer $n$, and we want to find all the pairs $(i, j), i\leq j$ such that: $$i + (i+1) +(i+2)+(i+3)+ \dots + j = n$$

Clearly we can try all possible pairs in $O(N^2)$, but that is pretty slow. Here is my observation.

We already know that the sum of numbers from $1$ to $n$ equals $\frac{n\cdot(n+1)}{2}$. Using simple math we can show that the sum of the numbers in the range from $i$ to $j$ equals $\frac{(j-i+1)\cdot(i+j)}{2}$. If we fix number $i$ using this formula we can find $j$, and check if it is positive integer, but this is $O(N)$, can we go faster?

Another algorithm:

Find all factorizations of $2n$ into a product of two integers, say $2n=r \times s$ with $r \le s$.  Then find $i,j$ such that $j-i+1=r$ and $i+j=s$, i.e., $i=(s-r+1)/2$ and $j=(s+r-1)/2$.  Check whether $i,j$ are positive.  If they are, output this pair $i,j$.  Do this for each way of expressing $2n$ as the product $2n=r \times s$.

How do you find all factorizations of $2n$ into two integers?  First factor $2n$ into a product of prime powers, say

$$2n = \prod p_i^{e_i}.$$

Next, for each $c_i$ with $0 \le c_i \le e_i$, you can let $r = \prod p_i^{c_i}$ and $s = \prod p_i^{e_i-c_i}$.  So in this way you can enumerate all such factorizations.  There will be $\prod (1+e_i)$ of them.

The running time for this is significantly faster than $O(n)$.  In the worst case the number of such factorizations can be no larger than $O(n^{1/2})$, so the worst-case running time of this method is $O(n^{1/2})$ -- already a significant speedup over Hendrik Jan's elegant answer.  Even better, in the average case, the number of such factorizations is far smaller than $n$, exponentially smaller, making this much faster.  Often, the dominant cost will be the cost to factor $2n$, which can be done in subexponential time using standard algorithms.


Problem with understanding proof of the Space Hierarchy Theorem The Space Hierarchy Theorem states that

If $f(n)$ is space contructible, then for any $g(n) \in o(f(n))$ we have $SPACE(f(n)) \neq SPACE(g(n))$

An example of a SHT proof can be found here or here but they are generally based on the same idea differing only in technical details. We would like to find a language $L$ such that $$L \in SPACE(f(n))$$ and $$\forall{g \in o(f(n))}: L \notin SPACE(g(n)).$$ So the proof claims that a language that fulfills these constraints is the following (for the sake of this post we do not care about $M$s whose description is too short for the asymptotic behavior of their space complexity to kick in) $$ L = \{ \langle M \rangle: M\text{ rejects }\langle M \rangle\text{ using }\leq f(|\langle M \rangle|)\text{ space}\} $$ and it describes a TM that accepts this language in $f(n)$ space. Then it tries to prove the second constraint using diagonalization argument in the following way:

Suppose there is $M'$ such that $L(M') = L$ and $M'$ is of $g(n) \in o(f(n))$ space complexity. Then

If $M'$ accepts $\langle M' \rangle$ then (from assumption) $\langle M'\rangle \in L$ then (from definition of $L$) $M'$ rejects $\langle M' \rangle$
If $M'$ rejects $\langle M' \rangle$ then (from assumption) it does so in $o(f(n))$ space then (from definition of $L$) $\langle M'\rangle \in L$ then (from assumption) $M'$ accepts $\langle M' \rangle$

Contradiction. Therefore such $M'$ does not exist.

So what bothers me is that in the argument above we could just as well take a TM $M''$ that runs in $f(n)$ space and the argument would still hold, therefore breaking the first constraint.

Apparently, there is a misunderstanding of the original proof from Sipser's book Introduction to the Theory of Computation that's been erroneously duplicated in a couple of sources including Wikipedia and Berkeley's CS172 lecture notes.

Namely, Sipser defines the language in terms of a TM $M$ that

takes an encoded machine description $\langle M' \rangle$
simulates $M'$ on input $\langle M' \rangle$ on a tape bounded by $f(|\langle M' \rangle|)$
inverts the answer, if the machine stops.

The resulting $L(M)$ is different from

$$ L = \{ \langle M \rangle: M\text{ rejects }\langle M \rangle\text{ using }\leq f(|\langle M \rangle|)\text{ space}\} $$

because $M$ rejects $\langle M \rangle$ due to recurrent simulation that requires infinite space and therefore $\langle M \rangle \notin L(M)$ and $\langle M \rangle \in L$ from the definition of $L$.

As a result, in the diagonalization argument we should replace references to the definition of $L$ with references to the acceptance of $M$, which breaks the argument for $M$ itself.


Why can’t a qbit be both entangled and in a pure state? Not sure if I should ask this on CS or physics SE, but here goes.

I’m reading on quantum computing, and one thing that keeps confusing me is the following basic fact about QM:

Say we have a qbit A, and a qbit B, then two possible quantum states for $A$ are:

$$|+\rangle=\frac {|0\rangle + |1\rangle}{\sqrt 2}$$

$$\frac {|00\rangle + |11\rangle}{\sqrt 2}$$

In the first case, the qbit $A$ is in a quantum superposition between $0$ and $1$. In the second case, the qbits $A$ and $B$ are ALSO in a quantum superposition, but they are now entangled. I understand that there is a difference between these states, in the sense that the second is an entangled state, whereas the first one is not.

However, what I don’t understand, is why, solely from the perspective of $A$, there is a difference between these states. I read that in the second, entangled state, $A$ (taken as an individual qbit) is not in a superposition state, but in a mixed state. I know that this is a very important basic fact about QM but I still don’t really get it.

why is it not possible for $A$ to be both in an entangled state, AND in a superposition “with itself” (i.e. a pure state, rather than a mixed state). I.e. by what principle of quantum mechanics do we know this, and from what does this principle follow?
Is there an intuition behind this? I.e. how would quantum mechanics no longer make sense if it weren’t the case.

First, let's look at the density matrix for A in the two cases. When A is in the pure state $|+\rangle$, we have
\begin{align}
\rho_+ = |+\rangle\langle+| = \frac{1}{2}\left(|0\rangle + |1\rangle\right)\left(\langle0| + \langle1|\right)
\end{align}
As a matrix, we'd write this
\begin{align}
\rho_{+} = \frac{1}{2}
\begin{pmatrix}
1 & 1\\1& 1
\end{pmatrix}.
\end{align}
When A is entangled with B, we can obtain the (reduced) density matrix for A by tracing over all B states:
\begin{align}
\rho_A &= \frac{1}{2}\text{Tr}_B\left[\left(|0\rangle\otimes|0\rangle + |1\rangle\otimes|1\rangle\right)\left(\langle0|\otimes\langle0| + \langle1|\otimes\langle1|\right)\right]\\
&= \frac{1}{2}\left(|0\rangle\langle0| + |1\rangle\langle1|\right),
\end{align}
or, as a matrix,
\begin{align}
\rho_{A} = \frac{1}{2}
\begin{pmatrix}
1 & 0\\0& 1
\end{pmatrix}.
\end{align}
Ok, you say, the density matrices are different. Who cares? Well, we don't really care about states, because we can't measure states directly. But we can measure observables, and we can find the expectation value for those measurements using our states. Specifically, we can find the expectation value of $\mathcal{O}$ by taking $\langle\mathcal{O}\rangle = \text{Tr}\,(\rho\mathcal{O})$. Let's look at the example of the $X$ operator. We have
\begin{align}
\langle X\rangle_+ &= \frac{1}{2}\text{Tr}\,(\rho_+ X)\\ &= \frac{1}{2}\text{Tr}\,\left[ \begin{pmatrix}1&1\\1&1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}\right]\\
&=\frac{1}{2}\text{Tr}\,\begin{pmatrix}1&1\\1&1\end{pmatrix} = 1.
\end{align}
In the state $\rho_A$, however, we have
\begin{align}
\langle X\rangle_A &= \frac{1}{2}\text{Tr}\,(\rho_A X)\\ &= \frac{1}{2}\text{Tr}\,\left[ \begin{pmatrix}1&0\\0&1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}\right]\\
&=\frac{1}{2}\text{Tr}\,\begin{pmatrix}0&1\\1&0\end{pmatrix} = 0.
\end{align}
We obtain different experimental predictions for the outcome of measurements in these two states, and so we can distinguish between them.

Edit: I didn't really answer your question beyond showing how states in the example you gave lead to different predictions. I would say the more broad lesson to draw is that when system A is entangled with system B, measurements on B can change the outcome of measurements on A. This leads to an additional, classical uncertainty in our measurements that is not present when A is in a pure, unentangled state.


Is the unweighted vertex cover problem equivalent to its weighted version? Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that $$\text{UVC} \leq_\mathrm{m} \text{WVC}$$ but $$\text{UVC} \not \equiv_\mathrm{m} \text{WVC} \enspace ?$$

I think the first part is easy to prove, since one can construct an instance of WVC by taking an instance of UVC and letting the weight of all of its vertices be the same.

I find not that easy to prove the second part though. As WVC is a generalization of UVC, intuitively $\text{WVC} \leq_\mathrm{m} \text{UVC}$ can't hold, but I'd appreciate some help to demonstrate it in a formal way.

If you're talking about determining whether there exists a cover of weight $\le T$, then the problem is obviously in NP and thus reduces to unweighted vc (since $VC$ is NP complete).

If however were talking about whether the minimal cover is of weight $\le T$, then the problem is $\Sigma_2$ complete, and is therefore not reducible to vc unless the hierarchy collapses to the first level.


Reducing randomness needed by turing machine I am reading an article related to streaming algorithms named "Turnstile streaming algorithms might as well be linear sketched" by Yi Li, Huy Nguyen and David Woodruff,

At some point they have a random algorithm (uses a tape of random bits) that solved a problem over $\mathbb Z_{|m|}^{n} = \{-m,..,m\}^n$ that succeeds with probability $1-\delta$

They want to reduce the number of bits needed for randomness used by that algorithm using via the following statement:

  Theorem 9: Let A be a randomized automaton solving problem P on
  $\mathbb Z_{|m|}^{n}$ with failure probability at most $\delta$. There
  is a ranomized automaton B that only needs to pick uniformly at random
  one of $O(\delta ^{-2}nlogm)$ deterministic instances of A and solves
  P on $\mathbb Z_{|m|}^{n}$ with failure probability at most $2\delta$

  Proof: Let $A_1 ,A_2 ,.., A_{O(n\delta ^{-2}logm)}$ be independent
  draws of deterministic automata picked by B.

  Fix an input $x\in \mathbb Z_{|m|}^{n}$.

  Let $p_A(x)$ be the fraction of automata among $A_1 ,A_2 ,..,
> A_{O(n\delta ^{-2}logm)}$ that solve problem P correctly on x and
  $p_B(x)$ be the probability that B solves P on x correctly.

  By a Chernoff bound, we have that $Pr\{|p_A(x)-p_B(x)|\geq \delta\}
\leq exp(-O(nlogm)) < (2m+1)^{-2n}$.

  Taking a union bound over all choices of $x\in \mathbb Z_{|m|}^{n}$,
  we have  $Pr\{|p_A(x)-p_B(x)|\geq \delta \ for\  all\  x\} > 0$.

  Therefore, there exists a set of $A_1 ,A_2 ,.., A_{O(n\delta
> ^{-2}logm)}$ such that $|p_A(x)-p_B(x)|\leq \delta$ for all $x\in
> \mathbb Z_{|m|}^{n}$. The automaton B simply samples uniformly at
  random from this set of deterministic automata

I am having trouble understanding some parts of the proof:

the random variable $p_A(x)$ should be the amount of $A_i$'s that succeeds divided by the amount of them that B has sampled?

if so than by the low of total probability its easy to see that:

  $p_B(x) = \sum_{i}P[B\ choose\ A_i] P[B\  succeeds\  on\  x\  |\ B\ choose'  A_i] = \sum_{i}\frac{1}{O(\delta^{-2}nlogm)} P[A_i\ succeeds\
on\  x] = p_A(x)$

where the last move comes from the fact the each instance $A_i$ is deterministic so its either 1 for success or 0 for failure.

So the whole $|p_A(x)-p_B(x)|$ they use is actually 0

I understand from the end of the proof that $|p_A(x)-p_B(x)|$ should some how represent the distance between A's success to B's success but could not see how this happen.

Also I did not understand the use of Chernoff the way they did.

Here is another way of looking at $p_A$ and $p_B$. We can think of $B$ as a deterministic algorithm which accepts an additional input $r$ representing the randomness. This input is drawn from some distribution $R$. Also, denote by $P(x)$ the correct answer. Then
$$
p_B(x) = \Pr_{r \sim R} [B(x,r) = P(x)].
$$
Let $M = O(n\delta^{-2}\log m)$, and sample $r_1,\ldots,r_M \sim R$. The algorithm $A_i$ simply runs $B$ with randomness $r_i$, that is $A_i(x) = B(x,r_i)$. We can define another algorithm $A$ which first choose $i \in \{1,\ldots,M\}$ uniformly at random, and then runs $A_i$. The success probability of $A$ is
$$
\begin{align*}
p_A(x) &= \Pr_{i \in \{1,\ldots,M\}} [B(x,r_i) = P(x)] \\ &= \Pr_{r \in \{r_1,\ldots,r_M\}} [B(x,r) = P(x)].
\end{align*}
$$
Thus in $B$, the randomness is chosen according to $R$, whereas in $A$, the randomness is chosen uniformly from a set $\{r_1,\ldots,r_M\}$. If we choose $r_1,\ldots,r_M \sim R$, then we expect the performance of $A$ to be very similar to that of $B$, and this can be quantified using Chernoff's inequality.

The probability $p_A(x)$ itself depends on the choice of $r_1,\ldots,r_M$. What may confuse you is how we conceive of this two-step random process. We first choose $r_1,\ldots,r_M$, and this gives us the function $p_A(x)$, which is a random function depending on the choice of $r_1,\ldots,r_M$. Note that we don't take probability over the choice of $r_1,\ldots,r_M$ – if we did, we would just get $p_B(x)$.


Kirchhoff's Spanning Tree Algorithm Recently I have studied Kirchhoff's spanning tree algorithm to count the number of spanning trees of a graph, which has the following steps:

Build an adjacency matrix
Replace the diagonal entries with the degrees of the corresponding nodes
Replace all the other ones excluding the one's included in the
diagonal by $-1$
Then find the minor of any one of the elements to get your answer.

These all steps looks like magic to me. Can anyone explain how Kirchhoff derived this to obtain the number of spanning trees, I want to know the logic behind how this algorithm works, but all I can find in YouTube is the above steps only.

It looks like magic because the proof of Kirchhoff's Matrix Tree Theorem is nontrivial.
It relies on several algebraic properties of the matrix constructed in steps 1-3, which is called the Laplacian matrix of the graph.
Let $A$ be the adjacency matrix, and let $D$ be the diagonal matrix with the degrees of the nodes on the diagonal. Steps 1-3 build the matrix $L = D-A$: this is the Laplacian matrix of the graph.

So the question becomes, why should a minor of the Laplacian matrix be equal to the number of spanning trees of the graph?

To answer this question, we need to use other properties of $L$. One property is that we can also write $L$ as $B \cdot B^\top$ where $B$ is the oriented incidence matrix of the graph, that is, a matrix with one row per node $u$ and one column per edge $e$, where entry $B_{ue}=1$ if $e=\{u,v\}$ with $u<v$, $B_{ue}=-1$ if $e=\{u,v\}$ with $v < u$, and $B_{ue}=0$ if $e$ does not contain $u$.
For example, for a triangle graph, the Laplacian matrix is
$$ L=\left[\begin{array}{ccc} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{array}\right] $$
and the incidence matrix is
$$ B=\left[\begin{array}{ccc} 1 & 1 & 0 \\ -1 & 0 & 1 \\ 0 & -1 & -1 \end{array}\right]. $$
Note that the inner product of two distinct rows of $B$ is $-1$ if the corresponding nodes are adjacent, and 0 if they are not. The inner product of a row of $B$ with itself equals the degree of the corresponding node. (Just use the definition of $B$.) This is why $L=B\cdot B^\top$.

Assuming the graph is connected, the rank of $B$ is exactly $n-1$ where $n$ is the number of nodes of the graph. It is not $n$ because if you sum all rows, you get a zero vector. It is $n-1$ because the number of independent columns of $B$ is $n-1$: if you take any subset of columns corresponding to the set of edges of any spanning tree of the graph, these columns will be independent; the only way to have a dependent set of columns is when the edges selected contain a cycle.

If we delete a row and corresponding column of $L$, we obtain a matrix $M$. If we delete the corresponding row of $B$, we obtain a matrix $C$. Now $M=C \cdot C^\top$ for the same reasons that $L=B \cdot B^\top$. We are interested in $\det(M)=\det(CC^\top)$. In the example of the triangle graph above,
$$ M=\left[\begin{array}{cc} 2 & -1 \\ -1 & 2 \end{array}\right] $$
and
$$ C=\left[\begin{array}{ccc} 1 & 1 & 0 \\ -1 & 0 & 1 \end{array}\right]. $$

The last step is to invoke another algebraic fact, the Cauchy-Binet formula. This says that for any matrix $C$,
$$ \det(C C^\top) = \det (C_{K_1}) \det(C_{K_1}^\top) + \ldots + \det (C_{K_q}) \det(C_{K_q}^\top) $$ where each $C_{K_i}$ denotes an $(n-1) \times (n-1)$ submatrix of $C$ and the sum runs over all such submatrices. Thus,
$$ \det(C C^\top) = \det (C_{K_1})^2 + \ldots + \det (C_{K_q})^2. $$

However, $\det(C_{K_i})=\pm 1$ if the edges corresponding to $C_{K_i}$ comprise a spanning tree, while $\det(C_{K_i})=0$ otherwise (because then the set contains a cycle and the corresponding columns are not independent). Thus, the value of the sum is exactly the number of spanning trees.


Merging nodes of a DAG I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them.
After each merge operation, the graph should remain acyclic.
Let's say my graph contains blue nodes and white nodes.

A and B are connected, they may be merged:

The above graph is DAG.
Merging node {A,B} with node {D} is illegal since it creates a cycle!

My current algorithm is based on union-find.

For each blue node b:
   Make-Set(b)
For each two connected blue nodes a,b:
   Union(a,b)
For each set://Created at the previous step
   merge all nodes of the set

The bug is the output graph contains cycles. How can I avoid merges that create cycles in the graph?
Before each Union, I need to check that it "safe". Safe means that after merging cycle will not be created.
I can find all passes between the set of a and set of b before Union but this solution is too expensive (time complexity).
I can't use solutions with a quadratic time complexity since my graph is too big.
Edit:
We can merge nodes according to topological order but the following case will be messed (D):

Nodes A, B, and D may be merged, but we will merge only A and B.
Max Cluster example: at the graph below the cluster is {A, B, C, D, E}

I think instead of performing merge at the beginning. We can add a node which has the similar edges as the two merged vertices.

Having the following DAG.

If we want to merge node A and B. We add a new node which has the similar attributes as A + B.

Then trasverse  from new node AB (should be Depth-first):

If it find Node A or B, then the merge should be cancelled because it creates a cycle. simply delete Node AB.
If we do not se Node A or B, the merge is valid so delete node A and node B.


What is this hash of array data structure called? I've created a data structure that is a hash of arrays with a special property: the hash keeps track of the combined order in which items are appended to its arrays.

For example (pseudocode):

h = HashOfArray()

h["a"].append(1) // accessing an unset key returns an empty array
h["b"].append(2)
h["a"].append(3)
h["b"].append(4)

h["a"]
>>> [1, 3]

h["b"]
>>> [2, 4]

h.items()
>>> [1, 2, 3, 4]

I'm struggling with coming up with a good name for this data structure. Does it have a commonly used name? I've called it HashOfArray but that fails to convey its main property: that it maintains the combined append order of the arrays.

Example implementation in Ruby:
https://gist.github.com/kajic/7981533

No, this data structure does not have a commonly-used name. It so similar to a  hash table that it is very unlikely to have been the subject of a peer-reviewed publication.


For every 4 ‘c’ in the input push a ‘c’ in the stack (Push down automata) Given the following language: L = {$a^{2m}$ $c^{4n}$ $d^{n}$ $b^{m}$ : m,n >= 0}
I’m trying to design a PDA. My aproach is:

-for every 2 ‘a’ push an ‘a’

-for every 4 ‘c’ push a ‘c’

-then pop them to solve the 2nd half of the language

This is the first part to count 2 ‘a’, but the ‘c’part is not very clear:

Any hints or solutions for the problem: ‘’for every 4 ‘c’ push a ‘c’ on the stack‘’

Thanks!

You can recognise the language $L = \{c^{4n}|n\geq 0\}$ with a normal DFA. Use this automata as a base and just use one designated state, that pushes a C onto your stack, for which I would choose the first one. For every transition one c is consumed from the word.

$\{(q_1, c, S, CS, q_2) ,
(q_2, c, S, S, q_3),
(q_3, c, S,S,q_4),
(q_4, c, S,S,q_1),
(q_1, d, C, \varepsilon, q_d)\} \subset \Delta $
with $S \in \Gamma$


In-place "clumping-by-color" algorithm faster than sorting by color? I don't know what to call this, so I'm calling it "clumping by color".

Suppose I have an array of length $n$
where each of the items has one of $m$ "colors".  I'd like to permute the elements so that all the items are "clumped" together with other items of the same color.  That is, in the final array ordering

$$ x_0, x_1, \cdots x_{n-1}$$

if $x_i \neq x_{i+1}$, then $\forall j \lt i,\, x_j \neq x_{i+1}$ and $\forall k \gt i+1,\, x_k \neq x_i$.

I know I can solve this "in place" in time $O(n \log n)$, and additional space $O(\log n)$ because I can use an in-place sort (like introsort to produce a permutation that satisfies the clumping constraint, but I'm hoping for at least a smaller constant factor by taking advantage of the fact that I don't care about the order of the colors.

Right now we have an $O(n^2)$ algorithm that is analogous to selection sort

i = 1
while i < n:
  pivot = x[i-1]
  while (i < n) and (x[i] == pivot):
    i = i+1

  for j = i+1 to n:
    if x[j] == pivot:
      swap(x[i], x[j])
      i = i+1

We've also tried a quicksort, which works a little better when the number of colors is large and mostly sorted by the arbitrary integer values assigned to the colors, but worse when the number of colors is small.  It would seem that something like counting sort might be a desirable way to go but (a) we really need this to be in-place (the colors actually represent pages, we're doing the clumping to avoid tlb misses, and out-of-place sorts (like counting sort) are just going to make the tlb thrashing worse.)  And (b) while the number of colors in an array of length $n$ obviously can't be larger than $n$, the number of colors in the "universe" is much larger (something like $2^{52}$ on a machine with 64-bit virtual addresses).  And (c) part of the reason quicksort is often worse than our $O(n^2)$ algorithm is that it sorts the colors by their arbitrary numeric value, which wastes time.

If I understand correctly, you're asking if preserving the locations of grouped values will give a speedup over reordering them, so for instance {2,2,2,1,1,1} would be left in place instead of rewriting the array as {1,1,1,2,2,2}.  I would say no, because comparing-and-swapping is not slower than simply comparing in practice, and you probably need the same number of compares regardless.

I've done tests of different Dutch National Flag algorithms and found no variation in times between versions that do a lot of swaps vs. ones which do little (there was a period when that number was important, and a number of papers have been published on it).  They all do the same number of comparisons, but the mechanics of moving elements into cache, etc. seems to make swaps almost free.

As greybeard notes, you're probably using the wrong Quicksort.  Try the one described here:  https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf .  2-way Quicksort is quadratic with duplicate values, for instance n duplicates will take o(n^2) since it will place all remaining values on one side of the pivot during each recursion.


Finding a finite model Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this:

  Suppose $L$ is a language which includes an infinite list $c_1,c_2,\cdots$ of constant symbols. Let $\Gamma$ be a set of sentences $\Gamma = \{c_i \neq c_j \mid i,j\in N, i < j\}$. Let A be a sentence such that $\Gamma \Rightarrow A$. Prove that $A$ has a finite model.

I am not sure whether I would prove this via a contradiction (i.e., assume $A$ has an infinite model, or if I show a finite model that works or some how assume that we can have an infinite model and then use some sort of compactness to show it can be finite. I am a little all over the place with this question, please any help would be great!

Note that you're looking for a model of $\{A\}$, not of $\Gamma \cup \{A\}$ (which obviously has no finite model since all the constants need to be pairwise distinct).

Proof by contradiction would be “assume $A$ has only infinite models or no model at all”. This isn't likely to lead anywhere.

Compactness could let you find a model of some set of sentences but you'd still have to prove the existence of a finite model at some point. Anyway, there is an easy direct proof.

The smallest model of a set of sentences is the one that collapses all the ways in which the differences between elements don't matter. You don't have to go all the way to apply this intuition: you can find a smaller model by collapsing some elements that don't matter. Here, you have an infinite number of constants; to find a finite model, you'll have to map infinitely many to the same element of the model (possibly to several elements).

In particular, if some constants do not appear in your theory at all, they can all be mapped to the same model element.

   The theory is $\{A\}$. This is a finite theory, consisting of (one) finite formula. Only a finite number of constants appear in this formula. Let $C(A)$ be the set of constants that appear in $A$. Define $\mathscr{M}: c \mapsto c$ if $c \in C(A)$, $c \mapsto c_1$ if $c \notin C(A)$. Then $\mathscr{M}$ satisfies $A$.


Why would we want a self-hosting compiler? I understand that a self-hosting compiler is a compiler which can compile the code of the language that it is written in into different language but I don't understand why we would want to do that. What are the benefits (and drawbacks) of a compiler which is self-hosting?

There's no direct technical benefit for a compiler to be self-hosting. If anything, it makes things more complicated, because you have to have a working compiler before you can compile the compiler — the bootstrapping problem. (Solved either by having another implementation of the same language — often an interpreter — or by keeping around binaries of a previous compiler version.)

Compiler writers often like the language that they're writing a compiler for. This is the primary reason why many compilers are self-hosting.

Having a compiler that compiles itself does have an indirect technical benefit: it's a litmus test. A compiler is a complex program. If the language is comfortable enough to write a program in, that's a sign that it's comfortable enough for a large class of programs. If the compiler can compile itself without bugs, that's a sign that it's in a good enough shape to compile other programs with confidence.


How do I prove all constants to some exponential power belong to little-o of some function I'm trying to prove that c2n = o((loglog n)n) (That's little-o) for any constant c. I understand that we can prove one function grows at a smaller rate than the other by taking the limit as n approaches infinity, and I can very easily pick some arbitrary integer value for c and show that indeed ((loglog n)n) grows at a faster rate. But how do I prove this to be true for any constant c?

Try proving that $5^{2n} = o((\lg \lg n)^n)$.  Write out the proof in detail, and make sure you  understand every step.

Then, try replacing the $5$ in the base with an arbitrary constant $c$.  Does every step still go through?  Hint: you should be able to extend the argument to handle an arbitrary constant $c$, with very little change.

If you're still stuck, edit the question to show us what you've tried, including showing us your proof that $5^{2n} = o((\lg \lg n)^n)$ and your reasoning about which steps are still valid when you replace $5$ with an arbitrary constant $c$.


A puzzle in Permutation There are two stacks A and B.

A :  a,b,c,d   ('a' is on top and 'd' is at the bottom of the stack)
B :  (empty)

There are two rules.

If an element of A is popped, it must be printed immediately or pushed into B.
If an element of B is popped, it can only be printed.

So, how many permutations of a,b,c,d are possible?  (continue reading)

P.S. Well, I did calculations manually(didn't use any formula) and got 14 as the answer. However, it took around 10 minutes to do the lengthy steps. So, is there an easy way to do this?

This problem looks like the problem of single stack sorting. "Single" because onle your stack B is used to sort, the stack A is only for input. Donald Knuth has analysed this, and characterized it as the 231-avoiding permutations, and has shown their number equals the Catalan numbers.

Now if my observation is correct, you must have counted wrong (original number you gave was 28). The Catalan numbers are 1, 2, 5, 14, 42, 132,

(added, after you recomputed)
Thus, we get a formula, the number of "single-stack sortable permutations of length n" is the $n$-th Catalan number $C_n = \frac 1{n+1}{2n \choose n}$. That does not yet explain the connection. There is a lot to learn about Catalan numbers, see the wiki-page for a lot of situations where they arise! Also the page to the online encyclopedia of integer sequence I referred to has more than enough links to keep you busy for a long time.


Can you insert into sorted list with time O(1)? Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap with one slot for each possible integer. 2 billion different integers * 4 bytes per integer = 8 gigabytes....but it'd technically work. There has to be a better way to do this though, right?

Sounds like you want a solution for bounded integers, 32-bit for example. If so, any sorted dictionary whose complexity depends on the key length only will do what you want. Two examples are binary trie and van Emde Boas tree.


Can $\{a^mb^nc^n\mid m,n \ge 1\}$ be proved non-regular using the pumping lemma? $\{a^mb^nc^n\mid m,n \ge 1\}$ intuitively seems like a non-regular language. It looks like the machine needs to remember the number of $b$s (which isn't limited). The pumping lemma can be used to prove a language is non-regular. In reference to the Wikipedia article linked (see "Use of Lemma"), every string I have tried doesn't give a contradiction. For example, a string like $a^1b^pc^p$ (where $p$ is the pumping length) seems to nicely split into $x = \varepsilon$, $y = a^1$, $z = b^pc^p$. What am I missing here?

You've forgotten that $y$ can be pumped any number of times, including zero. The string $xy^0z = b^pc^p$ is not in the language.


Showing that the set of TMs which visit the starting state twice on the empty input is undecidable I'm trying to prove that

$L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$.

I'm not sure whether to reduce the halting problem to it or not. I tried to construct a new machine $M'$ for $(\langle M \rangle,w)$, such that $M'$ visits $q_0$ twice, iff $M$ halts on $w$. This is specific $q_0$ given to me, but I didn't come to any smart construction, which would yield the requested. Maybe it's easier to show that it's $RE$ and not $coRE$? It is obvious that it's in $RE$, and I need to show that $L_2^{c}$ is not in $RE$.

What should I do?

Don't make this more complicated than it is. Instead of giving you a full solutions, I will give you a partial solution, which should allow you to work out the details by yourself:

Every TM be turned into a TM that visits its initial state exactly once. To do so, introduce a new state $q^'_0$, which will be the new start state. Then add a $\varepsilon$-transition from $q^'_0$ to $q_0$. This is the only way to "leave" the state $q'_0$.

For this modified machine, a accepting run visits the initial state once, and ends in the accepting state. What is left to do is to modify the machine further, such that it jumps back to $q^'_0$, after the machine was in the accepting state. But you have to assure that when $q^'_0$ is visited the second time, you will jump to a new accepting state. But it's not difficult to record how often you visited a state.

If you want that another state is visited twice, then you can always made a detour in the beginning that visits this state (you record that the machine is in "detour" mode be writing a flag on a special tape). Than you reroute the normal computation, such that if it should visit the requested state it visits a copy of this state. Finally, when accepting, you jump back to the requested state. Conceptually, this is not very different to relabeling the states.


Alternatives to Defunctionalization Defunctionalization is a transformation first described 1972 by John C. Reynolds to eliminate higher-order functions. Are there alternative transformations (more efficient?) to eliminate higher-order functions?

There are three main approaches (that I'm aware of) for implementing higher-order functions.  Defunctionalization, closure conversion/lambda lifting, and combinators.

Let's write $A \Rightarrow B$ for the type of a higher-order function from $A$ to $B$ and $A \to B$ for the type of C-style function pointers from $A$ to $B$.  (If we wanted to formalize this, we could say that function pointer abstraction is only allowed in the empty environment.)

Closure conversion is the idea that we choose the representation $$A \Rightarrow B \equiv \exists E.(E, (E, A) \to B)$$ The $E$ will typically be the tuple holding the values of free variables at the site of lambda abstraction.  It could be some other representation though.

Lambda lifting takes a somewhat different and more global approach where a lambda abstraction is pulled outward into containing scopes adding free variables as parameters along the way, until it reaches the top-level scope.  While this deals with block structuring, to actually handle higher-order uses of functions requires allowing partial application.  You can then pass around partially applied functions, but this is basically the same representation as closure conversion.

If you wanted to eliminate function pointers we can use defunctionalization, which, in this special case, simply produces an enumeration.  There's little reason to do this though, as function pointers are natural constructs in most assembly languages.

The next approach is to use combinators.  This is basically the same as lambda lifting and using partial applications except a fixed set of top-level functions are used, and all other functions are expressed as combinations of those.  (If they don't have a predefined fixed set of combinators, then this is usually just a lambda lifting based approach like I described above.)  A higher-order function would then be effectively represented by a value in a data type using Haskell syntax like the following (using SK combinators):

data CA = S | K | App CA CA -- plus other things in reality, like primitive values

A representation more like the spine calculus probably makes more sense for efficiency.  Or you could do something like:

data CA = S0 | S1 CA | S2 CA CA | K0 | K1 CA

Applying a higher-order function splits into two cases: either a combinator has been fully applied and thus it should be executed, or we return a new value that represents the (partial) application.

I haven't done an exhaustive survey, but I'm pretty confident variations on closure conversion are by far the most common implementation strategy for higher-order functions (hence them often being called "closures").  It has the nice properties of being modular, simple, and reasonably efficient even in its naivest form.  It takes a good choice of base combinators and some cleverness to get combinator-based approaches to perform well.  Defunctionalization just isn't widely used as far as I can tell, but there is little reason not to take advantage of function pointers.  To the extent that you do, e.g. instead of a large case analysis you have a table of function pointers that you index into, you've basically recreated closure conversion.

There are some other approaches.  One is template instantiation which is basically to take $\beta$-reduction literally, and simply literally substitute terms into other terms.  Usually, this requires having and manipulating an abstract syntax tree-like structure.  Higher-order functions are then represented by their (syntactic) lambda terms or "templates" thereof which can simplify performing the substitutions.


Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)? I'm a student, so I apologise if this is an idiotic question: Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (posing conjectures, proofs, etc.)? Why or why not?

I have heard arguments that computers will never be able to do mathematics close to the ability of humans, and these arguments are sometimes justified with reference to P vs NP (assuming that $P \not = NP$). It is said that, since these problems are NP rather than P (?), the solutions (proofs) could either be so lengthy as to not be understandable and/or verifiable by humans, or the solutions (proofs) would take so much time that the task practically becomes impossible. Are these statements true? Why or why not?

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

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

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

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

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


What do time complexity reductions prove? I may have missed something in my classes - but with $A\leq_{P}B$... Does this show that, if $A\in \textbf{NP-Complete}$, that $B\in \textbf{NP}$ or $B\in \textbf{NP-Complete}$?

Or maybe I got things backwards. If $A$ is polynomial-time-reducable to $B$, and $B$ is $\textbf{NP}$-complete, does that make $A$ $\textbf{NP}$ or $\textbf{NP}$-complete?

$A \leq_p B$ denotes that you can reduce $A$ to $B$ in polynomial time. That is, you can always transform an instance of $A$ to an instance of $B$ and you do this in polynomial time. Now if you have a polynomial time algorithm for solving an instance of $B$, you also have a polynomial time algorithm for solving an instance of $A$, clearly.

To show that $C$ is $\mathsf{NP}$-complete, you need two conditions to hold. First, $C$ must be in $\mathsf{NP}$. Second, every problem in $\mathsf{NP}$ is reducible to $C$ in polynomial time.


Showing that algorithm has STOP property and finding its computational complexity function The task is to show that given algorithm has STOP property and to find its computational complexity function.

$\alpha:$ $n \ge 0$

void fun(int n) {
    a=0;b=n+1;
    while ((a + 1) != b) {
        p = (a + b)/2;
        if (p ∗ p > n)
            b = p;
        else a = p;
    }
}

I have already proven its partial correctness as it was also part of the task, however I do have problem with these things that I have mentioned above.

I think it can be easily seen that it is gonna stop as 'a' is getting bigger and bigger, but I don't really know how to notate or show it in more mathematical way.

Thanks for your help.

You have already proven $a < b$. Let $g$ be the gap between $a$ and $b$, so $b - a$.

Show that the algorithm terminates when $g = 1$.
Show that when $g > 1$ we have as postcondition that the new $g' \leq \lceil g/2 \rceil$ in the loop body, and thus $g' < g$.
Show that it's impossible to skip $g = 1$, and thus the algorithm must terminate.


Compute the mode of an array concurrently As an academic exercise, I have to write a parallel algorithm that given a sorted array of $n$ integers computes the mode (i.e. the item with the highest frequency) efficiently using $p$ processors, where $p \le n$ is a constant.

The model we use to describe these algorithms allows lock/unlock primitives to synchronize concurrent access to shared variables.

We cannot use hash tables. Could anyone share any hint on the optimal algorithm to solve this problem?

Edit: rephrased question according to comments.

Edit 2: adding my solution for feedback.
While trying to solve the exercise I thought of an algorithm in the lines of

Declare two global variables, mode and modeFrequency and initialize them appropriately;
For i where $1 \le i \le p$, invoke a concurrent process on a portion of the array.
In each concurrent process:
3.1.. Find the local mode of the partition;
3.2. Store the local mode and its frequency in two local variables;
3.3. Compare the local mode with the global one:
3.3.1. if the mode is the same, add the local frequency to the global one;
3.3.2. if the local mode is different than the global one and the local frequency is higher than the global one, set the local mode/frequency to the global ones
Return the global mode.

but I am not convinced of the correctness of the algorithm. Please note that I omitted locks/unlocks for brevity. Also, can the way I partition the array make any difference on the correctness of the algorithm?

Since you asked for a hint:

   Partition the array.

Think about that for a while.  If you need more of a hint:

   If you partitioned the array into $p$ partitions and assigned each partition to a single processor, could you compute the mode of the numbers within a particular partition efficiently?  Would that help get you closer to a solution to what you want to achieve?


Finding the greatest $k$ numbers with a certainty of $p$ Given $n \in \mathbb{N}$ pairwise distinct numbers. I want to do as few comparisons per number as possible - and every number should experience roughly the same amount of comparisons as another number - and find the greatest $k \leq n$ numbers, e.g. $k = \frac{n}{10}$. In order to minimise the number of comparisons per number, I allow an error, say I am okay if I know that the result is correct with only a probability of $p$.

I study mathematics and only had a very shallow introduction to algorithms so far, and the only relevant algorithms we discussed would be sorting algorithms. QuickSort comes to mind, but firstly I am not sure how I would implement my "tolerance of an error" and secondly, I think the fact that I only need the greatest $k$ numbers and I don't want to sort them, there might be more efficient algorithms.

Any basic approach would be a great help already, I'll gladly do the maths on my own.

Thanks in advance for any help.

I propose the following algorithm. You take some random element $p$ of your input as pivot element for $k=n/10$. Next, you scan through all your data and split it  into a list of elements $\le p$ and a list with elements $>p$.

Case 1: The list with the larger elements contains more then $k$ elements. Then take this list and repeat.
Case 2: The list with the larger elements contains less than $k$ elements, say $m$. The repeat with the other list, but set $k=k-m$.
Case 3: Otherwise you are done.

This is very easy to implement and should find the solution quickly. (You said you want to do the math by yourself ;) )

Remark: There is a classic $O(n)$ algorithm for this. You can determine the $k$-th biggest element in $O(n)$ by the algorithm of Blum et al. and then use this element as pivot. However, I think the the constant in the $O(n)$ makes this variant slower then the above solution. Especially if you are fine with an imprecise solution.


What is the relationship between problems and languages? I want to ask exactly what is the relationship between problems and languages.
We know that the set of all languages uncountable.
Is the set of problems also uncountable?
Can every problem be defined by a language?
Can a language solve more than one problem and vice versa?
Is there one-to-one correspondence between problem and languages?

Decision problems and languages are just the two sides of the same coin: every problem can be rephrased as the membership problem of some language.  The problem of, say, determining whether a number is prime is exactly the membership problem of the language of prime numbers.

Formally, a language is a set of finite strings over some fixed finite alphabet (sometimes, the strings are allowed to be infinite; that's a different but related scenario).  Problems that aren't directly questions about strings will need to be encoded as strings so, for example, it would have been more precise to write the last sentence of the previous paragraph as, "If we fix an alphabet and an encoding of natural numbers as strings over that alphabet, the problem of, say, determining whether a number is prime is exactly the membership problem of the language of strings that encode prime numbers."

To quickly run through your subquestions,

  We know that the set of all languages uncountable. Is the set of problems also uncountable?

Yes, since problems and languages are essentially the same thing.

  Can every problem be defined by a language?

Decision problems, yes. Optimization problems (what's the smallest X with property Y) and counting problems (how many X's have property Y) can be rephrased as decision problems (is the Z the smallest X with property Y?; are there N X's with property Y?), though that's usually not the most natural way of treating them.

  Can a language solve more than one problem and vice versa?

Yes and yes, because you have to use encodings to translate between problems and langauges. For example, the languages $\{10,11,101,111,1011,\dots\}$ and $\{2,3,5,7,11, \dots\}$ both encode the primality problem (in binary and decimal, respectively). Conversely, though perhaps a little artificially, the language $\{0, 10, 110, 1110, \dots\}$ encodes the problem of determining whether a binary number is of the form $2^k-2$ for some $k$ and the problem of determining whether a string of 1's and 0's has exactly one 0, which is its final character. (Perhaps somebody can come up with a better example of a language that naturally encodes two problems without one being such a trivial rephrasing of the other.)

  Is there one-to-one correspondence between problem and languages?

No, since this question is just the complement of the previous one. :-)


Populating a vector of numbers to expose an error in a function implementation So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect on specific inputs. In fact I might do this for all vector sizes under a certain size, but I would never enumerate all possible values, just all possible vector sizes.
It occurs to me however that it might be possible to populate the values of the vector such that I can still verify every possible vector under a certain size as long as I make a certain assumption about the implementation of the function under test.
Say I have a function $f : \mathbb{N}^n \to \mathbb{N}$ such that $f(x) = \sum_{i=1}^nc_i\prod_{j=1}^n x_j^{e_{ij}}$ for some $e$ and $c$ such that $e_{ij} \in \{0,1\}$ and $c_i \in \{0, 1\}$. I want to see if this is equal to some known golden function $g$ but I'll have to manually work out $g$ for specific inputs. I belive it to be true that there exists an input $r$ such that $f(r)$ uniquely determines $f$. This makes testing to see if a particularly implementation of $f$ is the one we expect trivially easy.
for $n = 2$ the possible values of $f(3, 7)$ are the following:
0,
1,
x = 3,
y = 7,
xy = 21,
2,
1+x = 4,
1+y = 8,
1+xy = 22,
x+x = 6,
x+y = 10,
x+xy = 24,
xy+xy = 42
So if I make the assumption that a partiuclar function I'm testing has the above from characterized by $c$ and $e$ then I only need one input to fully test an implementation of $f$.
A good heuristic for generating these inputs is to start with the first prime higher than the number of terms you have, and then try successively higher primes for each next input until you work out the few kinks that remain. The intuition is that no two products will be the same because you chose primes and that each unique product will be spaced out by so much eventually that the sums will also all be unique as well.
Is there an algorithm to generate an input to such a function that makes all possible such functions result in unique values? What if we're willing to be probabilistic in some sense such as "the expected output is probably unique for this input"? Are there other forms of functions for which this question has been studied?

Multilinear polynomials
If you're willing to use probabilistic methods, I suggest using a randomized algorithm for polynomial identity testing.
You want to test whether $f(x)=g(x)$ holds for all $x$, where $f,g$ are multilinear oolynomials.  This is an instance of the polynomial identity testing problem.  There are effective randomized algorithms for polynomial identity testing.
To make this answer self-contained, I'll give you a brief overview of a reasonable algorithm.  First, randomly pick a large prime $p$.  Next, randomly pick $x=(x_1,\dots,x_n)$, with each element $x_i$ chosen uniformly at random modulo $p$.  Finally, check whether $p(x)\equiv g(x) \pmod p$.  If no, then you know that your implementation is faulty.  If yes, then your implementation has a good chance of being good.  (In particular, a faulty implementation that computes some other multilinear polynomial has a low probability of going undetected, thanks to the Schwartz-Zipple lemma.)  You can repeat this procedure multiple times for stronger guarantees.
This procedure assumes you can inspect the code of the algorithm and verify that it computes a multilinear polynomial, which seems to be something your question proposes that we can assume.  If you have a complete black box and you have no knowledge whether it computes a multilinear polynomial or not, you can't get strong guarantees that $f$ will be correct everywhere: for instance, your implementation $f$ might be correct on all but one input where it is special-cased to outputs the wrong answer.
More general cases
You might be interested in the theory of self-testing, pioneered by Blum, Luby, Rubinfeld and further developed by others.  See, e.g., the following seminal paper:
Self-Testing/Correcting with Applications to Numerical Problems.  Manual Blum, Michael Luby, Ronitt Rubinfeld.  Journal of computer and system sciences, 47(3), 549-595.
They generalize your idea by considering testers that invoke the program-under-test multiple times; by allowing probabilistic tests, where there is a chance we fail to notice problems, but this probability can be controlled or bounded; and by allowing for self-correction, where we use the possibly-faulty program as a subroutine to construct an output that will be correct with high probability.  Nonetheless, despite these generalizations, the class of functions that we know how to build efficient self-testers for is fairly limited, and we don't know how to do it for arbitrary functions.


Computer vision: Why do random filters perform similar to edge detectors? I read here that "a randomly initialized filter acts very much like an edge detector!". I want to know if there are any papers describing and explaining this phenomenon.

Intuition, for a small case

Why?  Let's look at the simplest possible case, where the kernel is 1x2 (i.e., two pixels wide and one pixel high).

Here's a kernel matrix for an edge detector that detects vertical edges:

$$E_1 = [-1 \; +1]$$

Here's another matrix for an edge detector that also detects vertical edges:

$$E_2 = [+1 \; -1]$$

In particular, convolution with $E_1$ responds strongly to edges that are vertical and where the right side of the edge has higher intensity and the left side has lower intensity (whiter on the right, blacker on the left).  $E_2$ responds strongly to vertical edges with the opposite intensity variation (whiter on the left, blacker on the right).

We can see that the same is true for other examples.  For instance, consider

$$E_3 = [+1.7 \; -1.7]$$

This behaves almost identically to $E_2$, except for rescaling at its output.

For simplicity, let's focus on convolution kernels that have been normalized so their entries sum to zero.  (Many convolution kernels we use in practice have this form, because they have nice properties.)

What about a random 1x2 matrix?  Well, if it has been normalized, then it will necessarily have the form

$$M = [+\alpha \; -\alpha]$$

for some constant $\alpha$ (where $\alpha$ is random).  Regardless of what $\alpha$ is, we see that this behaves like either $E_1$ or $E_2$.

Conclusion: a random, normalized 1x2 convolution filter behaves like a vertical edge detector, with high probability.

Bigger cases

This can be generalized to other sizes of kernels.  For a random, normalized 2x1 kernel, we'll basically get a horizontal edge detector.  A random, normalized 2x2 kernel will likely respond to edges in some direction (maybe at some angle; the specific direction will depend on the entries of the matrix).

As the matrix gets larger and larger, this effect diminishes (I think).  However, typically in practice we use a relatively small convolution kernel (a fairly small receptive field), so we really care mostly about the behavior with small convolution kernels.

Normalization

What about normalization?  So far I've been talking about matrices that were generated randomly and then normalized to sum to zero.  What if we skip the normalization step?

Well, this doesn't change very much.  Without normalization, a $m \times n$ random matrix $M$ can be decomposed into $M=M' + c \cdot A$ where $M'$ is normalized so its entries sum to zero, $c$ is a constant, $A$ is the matrix containing $1/(mn)$ in every entry.

Convolving the input image with $M'$ has a good chance of being basically applying an edge detector filter to the input image (as discussed above).  Convolving the input image with $c \cdot A$ will basically blur the image and then multiply by $c$.  Thus, the output image is the (weighted) sum of these two: the (weighted) sum of an edge detector filter plus a blurred version of the image.

For a random matrix, there's a decent chance that $c$ will be relatively small (since the mean of the sum of a bunch of random variables is often fairly small), so multiplying by $c$ makes the output image be determined more by the edge detector than by the blurring.  If $c$ is small, we can basically ignore the second term of the sum and approximate the output image as the result of an edge detector filter.

That's why convolution with a random matrix has a decent chance of looking like applying some kind of edge detector to the input image.

Looking at the example images on those pages, to my eyes the first one looks more or less like an edge detector, and the second one looks more or less like a blur operator.  This is consistent with the analysis above.


Is there anything lower than the bit level of 1s and 0s? When learning about the architecture of computers and how it works, we are thought that the lowest language that we can find that the machine understands is binary as 1&0. And anything that we input will have to be transformed/converted to binary, but being binary numbers wouldn't that mean that we would need another interpreter/compiler to transform binary into actual machine language? We all know from electronics that a computer is mainly composed of cpu which is an IC that is therefore made out of transistors etc, and the only thing that those tools understand is electricity, therefore electricity will be the lowest understandable language for a computer. So my concern is, is binary really 1s&0s or the 1s&0s are just used to represent the absence and or presence of electricity?
Supposing that it's just a representation for absence or presence of electricity, wouldn't there be another intermediate or even lower language between the commands that we input and binary, so that the circuits would know where to send the current to and where not to?

Digital computers work so that (almost) at any given point in time, any wire carries (roughly) one of two possible voltages, one signifying $0$ and the other signifying $1$. The voltages depend on the convention being used. In this sense, digital computing does work with $0$s and $1$s. However, even digital computers interface with analog devices, such as physical storage and networks. The way that data is encoded in networks can be somewhat different, since several bits can be encoded at once, depending on the encoding.

Let me explain my qualifications in the first sentence above. "Almost" refers to the fact that when wires switch from $0$ to $1$ or vice versa, there will be intermediate voltages. These switches are synchronized across all the wires so that whenever wires are "read", the switch (if any) has already occurred. "Roughly" refers to the fact that the voltages are not exact. There are two small ranges of voltages which correspond to $0$ and $1$. The devices should be able to "read" bits throughout these ranges, but usually "write" them more restrictively.


Search Heuristics Where the Search Space Has No Gradient If I'm not mistaken, search heuristics rely on problems where the best answer is very close to pretty-good answers. For example, the traveling salesman problem. If there is a route which is the optimal except for a small anomaly somewhere, where the route isn't quite optimal, the algorithms still says that's "pretty good" and continues searching that space until it finds the optimal. I'm going to call this "gradient" because there isn't a sharp difference between optimal and something where everything is optimal except for a small part.

What happens if there is no "gradient"? For example, let's say I wanted to develop some electronic circuitry using a search heuristic. This probably isn't done much, or at all, but bear with me. The optimal circuit would be one which, say, does addition. But, if there is one small difference, like an AND logic gate instead of an OR gate, it doesn't perform at all and produces a terrible result. Now, in traditional search heuristics, it would probably drop this and say "this isn't even close to optimal". It has no way of telling whether something is close to optimal or far away to optimal, because there is really only one circuit that produces good results, and everything else fails miserably.

So what should I do in these situations? By the way, the circuit thing isn't my problem; just a way to demonstrate my issue.

Phrased Differently What does a search heuristic do when it has no way of "grading" how good a given state is, and only the optimal state produces good results? Everything else, no matter how close to the optimal, produces terrible results.

BONUS: What other group of algorithms might perform well in these situations?

Search heuristics will be useless on those kinds of problems.  It will effectively degenerate to brute-force search: trying all possibilities in hopes that one of them works.  That's very unlikely to find you the solution, except in the smallest possible problems, as its running time is exponential.

What else can you do instead?  You'll need to consider other kind of approach: e.g., a  SAT solver or ILP solver, an approximation algorithm or any of the other standard methods of dealing with NP-hardness.


What is the "continuity" as a term in computable analysis? Background
I once implemented a datatype representing arbitrary real numbers in Haskell. It labels every real numbers by having a Cauchy sequence converging to it. That will let $\mathbb{R}$ be in the usual topology. I also implemented addition, subtraction, multiplication, and division.
But my teacher said, "This doesn't seem to be a good idea. Since comparison is undecidable here, this doesn't look very practical. In particular, letting division by 0 to fall in an infinite loop doesn't look good."
So I wanted my datatype to extend $\mathbb{Q}$. Since equality comparison of $\mathbb{Q}$ is decidable, $\mathbb{Q}$ is in discrete topology. That means a topology on $\mathbb{R}$ must be finer than the discrete topology on $\mathbb{Q}$.
But, I think I found that, even if I could implement such datatype, it will be impractical.
Proof, step 1
Let $\mathbb{R}$ be finer than $\mathbb{Q}$ in discrete topology. Then $\{0\}$ is open in $\mathbb{R}$. Assume $+ : \mathbb{R}^2 → \mathbb{R}$ is continuous. Then $\{(x,-x): x \in \mathbb{R}\}$ is open in $\mathbb{R}^2$. Since $\mathbb{R}^2$ is in product topology, $\{(x,-x)\}$ is a basis element of $\mathbb{R}^2$ for every $x \in \mathbb{R}$. It follows that $\{x\}$ is a basis element of $\mathbb{R}$ for every $x \in \mathbb{R}$. That is, $\mathbb{R}$ is in discrete topology.
Proof, step 2
Since $\mathbb{R}$ is in discrete topology, $\mathbb{R}$ is computably equality comparable. This is a contradiction, so $+$ is not continuous, and thus not computable.
Question
What is bugging me is the bolded text. It is well-known that every computable function is continuous (Weihrauch 2000, p. 6). Though the analytic definition and the topological definition of continuity coincide in functions from and to Euclidean spaces, $\mathbb{R}$ above is not a Euclidean space. So I'm unsure whether my proof is correct. What is the definition of "continuity" in computable analysis?

Different people have different views on what the definition of continuity should be, but the way I see it, we should define continuity to be computability relative to some oracle. For example:
Definition: A function $f : \mathbf{X} \to \mathbf{Y}$ is continuous, if there is a computable partial function $F :\subseteq \mathbf{X} \times \mathbb{N}^\mathbb{N} \to \mathbf{Y}$ and some $p \in \mathbb{N}^\mathbb{N}$ such that $f(x) = F(x,p)$.
So the most primitive concept in handling a space is what representation we are using for it, which then yields the notion of computability, and from that we get the notion of continuity.
So far, the definition of continuity seems rather unrelated to continuity from topology, and one may wonder why that term has been chosen. One reason is that we usually use admissible representations, which have the characterization that the functions between them which are continuous in the computable analysis definition are exactly the functions which are continuous in the topological sense.
If we have an admissible representation $\delta : \subseteq \Sigma^\mathbb{N} \to \mathbf{X}$, we get the topology on $\mathbf{X}$ as the final topology along $\delta$, i.e. a set $U \subseteq \mathbf{X}$ is open iff there is a set $W$ of finite words such that $\delta^{-1}(U) = \operatorname{dom}(\delta) \cap \bigcup_{w \in W} w\Sigma^\mathbb{N}$. Matthias Schröder has shown that the topological spaces which have admissible representations are exactly the $T_0$ quotients of countably-based spaces.
Now to slowly come back to the starting point of your question, what prevents us from using the discrete topology on the reals? The reason we cannot do that is that every countably-based space is separable, ie has a (countable) dense sequence. Taking quotients preserves being separable, so every topology associated to a representation is necessarily separable. A discrete space is separable iff it is countable, so we cannot get the discrete topology on the reals.
There is a way to get an admissible representation of $\mathbb{R}$ that makes $\mathbb{Q}$ a discrete subspace (essentially, treat $\mathbb{R}$ as $\mathbb{N}^{*} \cup \mathbb{N}^\mathbb{N}$), but as you have argued in the question, that makes addition uncomputable (and overall, has very little resemblance to the reals as we would want them).
On a side note, that we cannot avoid getting stuck without even recognising it when accidentally trying to divide by $0$ is a significant obstacle if we are trying to do linear algebra with real numbers.
References:
Pieter Collins:
Computable analysis with applications to dynamic systems. Math. Struct. Comput. Sci. 30(2): 173-233 (2020)
Martín Hötzel Escardó:
Synthetic Topology: of Data Types and Classical Spaces. Electron. Notes Theor. Comput. Sci. 87: 21-156 (2004)
Takayuki Kihara, Arno Pauly: Dividing by Zero - How Bad Is It, Really?. MFCS 2016: 58:1-58:14
Arno Pauly: On the topological aspects of the theory of represented spaces. Computability 5(2): 159-180 (2016) arXiv
Matthias Schröder:
Extended admissibility. Theor. Comput. Sci. 284(2): 519-538 (2002)


Constructing a tree from disjoint graphs I will preface my question with the definition of a simple tree that applies to my question:

  A simple tree is an undirected and connected graph with no cycles.

I am having difficulty coming up with a compelling argument that a tree of the above definition can be constructed by taking a set of disjoint valid graphs and adding a vertex between each of them. The practice problem states:

  Prove that some graph $G$ is a tree if and only if it can be constructed from a set $X_1, X_2, \dots, X_i$ of disjoint valid graphs by adding a new node adjacent to one node from each of $X_1,\dots, X_i$. A single node is a valid graph.

I'm confused whether this question is asking me to prove that two graphs, or trees ("valid"), can be made into one tree by adding a node and adding edges from one preexisting node from each of the trees. If that is how the question should be interpreted, then is it enough to prove that the new tree (or "graph," I guess) has no cycles, and is connected?

I'm new to graph theory and I'm wondering if you can help me understand it.

The reverse direction is relatively straight forward, as we start with disjoint vertices, and at each step only add edges to a new vertex, we cannot introduce a cycle, furthermore at each step we connect the "graph so far", so we finish with a connected graph.

For the forward direction, we just need to consider how we could construct a tree in such a manner. The key observation being that a subtree is also a tree. Thus we can recursively break down a tree (the construction is then a series of applications of adding a new node and some edges) by picking a vertex in the tree, and taking each of its subtrees as the sets $X_{1},X_{2},\ldots$. Each of these is a tree (and hence "valid"), so we can construct them in the same manner. Eventually we reach a set of leaves (individual vertices) which are by definition "valid".

The diagram gives a little sketch of this, with the "valid" components $X_{1}$, $X_{2}$ and $X_{3}$ all representing trees, with a new vertex added, and a single edge from each component to this new vertex.


Difference between Lamport timestamps and Vector clocks Lamport timestamps and vector clocks sound like almost the same thing. Both are used to determine the order of events in a distributed system. What are their key differences?

Although similar they have different purposes: version vectors can distinguish whether two operations are concurrent or one is causally dependent on the other; Lamport timestamps enforces total ordering. Total ordering although more compact cannot tell whether two operations are concurrent or causally dependent.


Connection between NAND gates and Turing completeness I know that NAND gates can be used to create circuits that implement every truth table, and modern computers are built up of NAND gates. What is the theoretical link between NAND gates and Turing completeness? It seems to me that NAND gate circuits are closer to finite automata than Turing machines. My intuition is that I can build flip-flops, and therefore registers and memory, out of NAND gates, and unbounded memory is a crucial property of Turing complete systems. I'm looking for a more theoretical or mathematical explanation, or pointers on what to read.

There is indeed little connection. For a thorough understanding, let me explain the connection between programs and circuits.

A program (or algorithm, or machine) is a mechanism for computing a function. For definiteness, let us assume that the input is a binary string $x$, and the output is a Boolean output $b$. The size of the input is potentially unbounded. One example is a program that determines whether the input is the binary encoding of a prime number.

A (Boolean) circuit is a collection of instructions for computing some finite function. We can picture the circuit as an electrical circuit, or think of it as a sequence of instructions (this view is called confusingly a straight-line program). Concretely, we can assume that the input is a binary string $x$ of length $n$, and the output is Boolean. One example is a circuit that determines whether the input encodes a prime number (just as before, only now the input has to be of length $n$).

We can convert a program $P$ into a circuit $P_n$ that simulates $P$ on inputs of length $n$. The corresponding sequence of circuits $P_0,P_1,P_2,\ldots$ is not arbitrary – they can all be constructed by a program that given $n$ outputs $P_n$. We call such a sequence of circuits a uniform circuit (confusingly, we often think of the sequence as a "single" circuit $P_n$ for an indefinite $n$).

Not every sequence of circuits is uniform. Indeed, a sequence of circuits can compute every function from strings to Boolean, computable or uncomputable! Nevertheless, in complexity theory we are interested in such non-uniform models in which the circuits are restricted. For example, the question P=NP states that NP-complete problems cannot be solved by polynomial time algorithms. This implies that NP-complete problems cannot be solved by polynomial size uniform circuits. It is moreover conjectured that NP-complete problems cannot be solved by polynomial size circuits without the requirement of uniformity.

Turing-complete computation models are models which realize all computable functions (and no more). In contrast, complete systems of gates (such as AND,OR,NOT or NAND) allow computing arbitrary finite functions using circuits made of these gates. Such complete systems can compute completely arbitrary functions using (unrestricted) sequences of circuits.


What makes an operational semantics good? Some papers define an operational semantics of a programming language. That is nice, but what makes such a semantics fit for the purpose?

An idea is to have a progress theorem, i.e. well-formed expression is either a value or a reduction can take place

another is type preservation, that an reduction preserves the type of an expression.

What else is a test for the adequateness of a semantics? What should I prove about it?

I think you have it a bit backwards: proving type preservation is a good property of the type system with respect to the operational semantics, rather than the opposite.

Alternately: the whole point of a programing language is the ability to use it to perform some computational task. Because of this, the operational semantics is one of the requirements of having a programing language. The only real "fitness test" you need is

  Can I write the programs I want using this language?

You might then want to prove that say, a compiler is correctly implemented by showing that the computational behavior of (well-behaved) code is equivalent in some sense to the operational semantics, but again, here I would take the semantics themselves to be primal rather than the opposite.

In certain fields of mathematics, notably in the area which studies the propositions-as-types correspondence, one might be more interested in the static semantics (the type system) and have the operational semantics more as an afterthought, where progress, preservation and termination have consequences on the type system as a logic (typically, that the logic is consistent).

But again, usually the operational semantics is primitive, and it is well-defined exactly when it enables the programmer to write the program she wishes to write (and possibly prevents some "bad" programs).


Computing 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time I've constructed an algorithm that solves the 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time. I'm new to algorithms and was wondering how good is my running time? Googling didn't help.
thanks..

There are known algorithms that take strictly less than $O(n^2)$ time (i.e., they run in $o(n^2)$ time), under certain theoretical computational models.  See, e.g.,

Subquadratic Algorithms for 3SUM.  Ilya Baran, Erik D. Demaine, Mihai Patrascu.

However, it is not clear to me whether this leads to a practical improvement in real implementations.

Did you do a literature search for work on the 3SUM problem?  The above paper immediately comes up as soon as you search for "3SUM" on Google Scholar.  On this site, we expect you to do your own research first before asking here, and to show what you've tried in your question.  Please make sure to read the help center to learn more about how this site works.  You might want to do a literature search, including reading the relevant references cited in the paper above, then editing your question to reflect this research -- or adding an answer to answer your own question.


Find non-smooth function that meets conditions I learned the following theorem in class:
"If $T(n)$ is asymptotically non-decreasing and $f(n)$ is smooth, then $T(n) =
O(f(n)|n=b^k, k=integer)$ implies $T(n) = O(f(n))$."

I'm trying to show using a counterexample that this theorem doesn't hold if $f(n)$ is non-decreasing but not smooth. Smoothness means that $f(bn) = O(f(n))$.

From my understanding, the above conditions mean that $f(n)$ must be an exponential. Other than that, how would I go about finding a function that meets the conditions outlined above?

Since this is a homework problem, please don't give an actual function, but instead give a series of steps to take to find the function. Thanks.

As you mention, the function $f(n)$ needs to grow fast, though not necessarily exponentially fast ($n^{\log n}$ also works, for example). Nevertheless, let's take your suggestion $f(n) = 2^n$ for definiteness. Simplifying things a bit, you are looking for a function $T(n)$ such that

$T(n)$ is non-decreasing.
$T(2^k) = 2^{2^k}$.
$T(n)$ is not $O(2^n)$.

To satisfy the third condition, we would like $T(n)$ to be "as large as possible" given the first two conditions.

  (a) Find the function $T(n)$ which is "as large as possible" subject to the first two conditions.

  (b) Show that it satisfies the third condition as well.

  (c) For which functions $f(n)$ does this construction work?


Parallel algorithm for LU-decomposition I need to implement LU-decomposition in Kaira. In Kaira the programmer writes the "parallel part" as the diagram similar to Petri Nets.

So, could you, please, recommend me some parallel algorithms for LU-decomposition which are really easy to understand and implement? The low difficulty of the implementation has the highest priority for me, because I'm not very familiar with Kaira and I'm in hurry a little.

I looked at a Fined-grained LU-factorization, but I'm curious if some other algorithms are used.

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