If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree? If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time?

Intuitively this sounds correct, as BFS does not visit a node twice, and it only traverses from vertex $v$ to vertex $u$ iff it hasn't visited $u$ before, such that there aren't going to be any cycles, and if $G$ is connected it will eventually visit all nodes. Since the weight of all edges is equal, it doesn't matter which edges the BFS chose.

Does my reasoning make any sense?

If your graph is unweighted, or equivalently, all edges have the same weight, then any spanning tree is a minimum spanning tree. As you observed, you can use a BFS (or even DFS) to find such a tree in time linear in the number of edges.


Number partitioning targeting ratio of subset sums and equal size I've seen a number of questions and answers related to the partitioning problem of dividing a set into 2 subsets of equal size and sum that use greedy or dynamic programming solutions to get approximate answers. However, I am looking to split a set into 2 subsets of minimum difference in size but with a target ratio of sums.

I have tried variations of greedy algorithms that will work to minimize the largest difference of the two metrics at any point in the calculation, but this just results in a result that splits the difference between the two. I'm happy with an approximate solution since it needs to run in a reasonable amount of time.

The problem is NP-hard (assuming the numbers are represented in binary).  If you could solve your problem efficiently, you could solve the Partition problem: Partition is the special case where the minimum difference is zero (and the target ratio is 1:1).  Therefore, you should not expect any simple algorithm to be both efficient and always correct.

If you want a heuristic that gives an approximation, greedy algorithms are reasonable.  I suggest you try adapting the standard algorithms for the Partition problem.  Another approach is to use an integer linear programming solver.


An algorithm for topological sorting based on depth-first search: why do we need two tags? Wiki gives an alternative algorithm for topological sorting is based on depth-first search, as follows:

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop   (not a DAG)
    mark n with a temporary mark
    for each node m with an edge from n to m do
        visit(m)
    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

I couldn't see the necessity of introducing two tags: permanent and temporary. As far as I can see, the following algorithm would work, using only one tag -- explored.

L ← Empty list that will contain the sorted nodes
while exists nodes without an explored mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    mark n as explored
    for each node m with an edge from n to m do
        if m is unexplored
            visit(m)
        if m is explored
            stop(not a DAG)
    add n to head of L

If it's not the case, please tell me where I went wrong within this algorithm.

Consider the following graph $G = (V, E)$ where
$$V = \{1, 2, 3\}, E = \{(1, 3), (2, 3)\}.$$
If your example started at $1$, it will add $3$ to the list and then it will add $1$. In the next step the algorithm will choose $2$ as an unvisited vertex, which has an edge to a visited vertex $3$. Hence, It will conclude that the graph is not a DAG. However, the graph is a DAG and your algorithm is not always correct.

The reason why we need two kinds of marking is to distinguish cycles from components we already done in previous iterations. Reaching back to an ancestor in the recursion tree means that there is a path going back to a vertex we came from and hence a cycle. Meanwhile an edge to a vertex that is permanently marked (and hence was visited in a previous iteration) can never introduce a cycle, since else we would have reached the current vertex in the same iteration as well.


kth nearest vertex in a unweighted graph Given an unweighted undirected graph $G$ with $10^5$ vertices and a subset $S$ of special vertices and an integer $k$, I want to find the $k$th nearest special vertex for each vertex.  What algorithm can I use for this problem?

I'm actually thinking of algorithm for finding shortest paths from every vertex to all other vertices (like Floyd-Warshall algo, but in our case graph is unweighted and we need much better performance).

Letting $G = (V,E)$, and $|V| = N$, your problem essentially boils down to computing a portion of the shortest path tree for every vertex in $G \setminus S$, where the shortest path tree is truncated after the $k$th "special vertex."

You mention the Floyd-Warshall algorithm; however, that algorithm seems inappropriate here, since it's designed for weighted graphs, and only returns the lengths of the shortest paths between every pair of vertices.

A more natural approach might be to run BFS on every vertex in $G \setminus S$, halting when you reach the $k$th "special vertex." Since you'd be running BFS on every vertex in $G \setminus S$, your worst-case runtime would be $O(N' \cdot |E|)$, where $N' = N - |S|$. (I'm assuming you only want the $k$th nearest special vertex for the non-special vertices.)

You would be able to improve the performance slightly by caching the portions of the shortest-path trees you compute on each call of BFS, but those changes wouldn't shift the worst-case performance. I believe any known shortest-path algorithm will have complexity dependent on $|E|$, so I'm not sure that you could solve this problem in $O(NlogN).$


Problem to understand a Bellman Ford algorithm exercise I am trying to understand the following exercise from Introduction to algorithm (3rd edtion).

Exercise 24.1-3 (page 654)
Given a weighted, directed graph $G=(V, E)$ with no negative-weight cycles, let $m$ be the maximum over all vertices $v \in V$ of the minimum number of edges in a shortest path from source $s$ to $v$. (Here, the shortest path is by weight, not the number of
edges.) Suggest a simple change to the Bellman-Ford algorithm that
allows it to terminate in $m + 1$ passes, even if $m$ is not known in
advances.

So what is $m$ exactly? I am really have the trouble to understand the first sentence.

The only way to understand it is to break it down.

Given a weighted, directed graph $G=(V, E)$ with no negative-weight
cycles, let $m$ be the maximum over all vertices $v \in V$ of the
minimum number of edges in a shortest path from source $s$ to
$v$. (Here, the shortest path is by weight, not the number of edges.)

Okay, so $s$ is fixed, and let us suppose you have a vertex $v$.
Now we look at all the cheapest paths from $s$ to $v$ and we take the
path that has the fewest edges; this number of edges we refer to as $m_v$.
If we repeat this for every vertex $v \in V$, then we get one $m_v$ for
each $v$.  The value $m$ is the maximum of all $m_v$s, or $\max_{v \neq s}m_v$.
Or in other words, over all cheapest paths starting in $s$, let us look at
the vertex with the longest shortest.  It has length $m$.
It is confusing because we want the longest shortest over all the cheapest.


Transitive reduction with vertex additions? The transitive reduction of a (finite) directed graph is a graph with the same vertex set and reachability relation and a minimum number of edges. However, what if vertex additions are allowed? In some cases, the addition of vertices can considerably reduce the number of edges required. For example, a complete bipartite digraph $K_{a,b}$ has $a + b$ veritices and $ab$ edges, but the addition of a single vertex in the middle results in a digraph with the same reachability relation that has $a + b + 1$ vertices and only $a + b$ edges.

More formally, given a directed graph $G = (V, E)$, the challenge is to find $G' = (V', E')$ and injective function $f: V \rightarrow V'$ such that $f(b)$ is reachable from $f(a)$ in $G'$ if and only if $b$ is reachable from $a$ in $G$ and such that $|E'|$ is minimized.

Are there any known results or algorithms related to this problem?

I don't think that any such "small" graph can exist in general.

Let $n$ be a multiple of $4$ and pick your favorite binary string $s = \langle s_0, \dots, s_{\ell-1} \rangle$ of length $ \ell = \frac{n^2}{4}$.

Build a directed bipartite graph $G_s = (A \cup B, E)$ on $n$ vertices where $A = \{a_0, \dots, a_{\frac{n}{2}-1}\}$ and $B = \{b_0, \dots, b_{\frac{n}{2}-1}\}$. $E$ contains the edge $(a_i,b_j) \in A \times B$ iff $s_{\frac{in}{2} + j}$ is $1$.

Let $G'_s$ be the smallest graph obtainable from $G_s$ that preserves connectivity relations.
Notice that, from $G'_s$, it is possible to recover the whole string $s$.

There are $2^\ell$ choices for $s$, which means that, for at least one graph $G_s$, the minimum number of bits needed to encode $G'_s$ must be at least $\ell = \Omega(n^2)$.

Notice that $O(m \log n)$ bits suffice to encode any graph with $m$ edges and $n$ vertices. This means that $G'_s = (V', E')$ must be such that $|E'| \cdot \log |V'| \cdot \log n = \Omega(n^2)$.


Are all pseudo-random number generators ultimately periodic? Are all pseudo-random number generators ultimately periodic? Or are they periodic at all in the end?

By periodic I mean that, like rational numbers, they in the end generate a periodic subsequence...

And pseudo-random means algorithmic/mathematical generation of random numbers...

All pseudorandom generators that don't rely on outside randomness and use a bounded amount of memory are necessarily ultimately periodic since they have finite state. You can think of them as huge deterministic finite automata which have special "output" states in which they give their output. All finite automata are eventually periodic, and so all pseudorandom generators produce eventually periodic output.

However, the period length can be enormous. For example, a PRNG with a cryptographic state of 128 bits might only cycle once every $2^{128}$ bits of output, and so even if outputting one bit every nanosecond, the solar system will be dead ere the PRNG repeats.

If the PRNG is allowed to use an unbounded amount of memory (which isn't realistic) then it can, for example, output the binary expansion of $\sqrt{2}$, which we know isn't eventually periodic (since $\sqrt{2}$ is irrational).


Is there a formal definition of "data structure"? Data structure is a term that I've heard use I think only somewhat informally in software engineering. Is there a formal definition of it in CS?

No, the term doesn't have a formal definition.

You might be interested in the notion of an abstract data type, which does have a formalization.


k-enclosing rectangle in two-colored point set I was asked to write an algorithm for the following problem, and discuss complexity:

  There are p points of two colours, black and white, in an n*m grid.
  Any cell in the grid can contain 0 or more points, of any colour.
  We are looking for an axis aligned rectangle, having (0,0) as a corner, containing k black points, and maximizing the number of white points in it.

It was mentioned that this problem is famous and I can use any online resource.

So far, the closest I have found is this paper, which deals with finding exact colored k-enclosing rectangles, that don't necessarily have the origin as a vertex.

Maybe someone here will be able to point me to some resources that discuss this version of the problem?

Ok as you have a working solution but seem concerned by optimization, I will detail here how to do it very efficiently. I assume that your rectangle has to follow the discretized grid (I now have a doubt on it reading your question).

Let's build 2 $n \times m$ count arrays $NB$ and $NW$ which are the number of respectively black and white points in each cell. You can fill these arrays in $O(p)$ as you just have to consider any point and decide which value of the array you increment.

Then you build the 2 $n \times m$ accumulator arrays $RB$ and $RW$. $RB[i, j]$ and $RW[i, j]$ are the number of respectively black and white points in the rectangle (left=0, up=0, right=$j$, down=$i$). You can fill these arrays with a very simple DP using $NW$ and $NR$, in $O(nm)$. Note that computing row after row, and in the row looping on elements, you can break the latter loop whenever $RB > k$.

The overall time complexity will be $O(max(p, nm))$.


Why does the substitution {x/f(y), y/z} work this way? There is an example of applying a substitution to an expression, and I am having a problem with it.
Let $\theta = \{ x/f(y), y/z \}$, and $E=p(x,y,g(z))$,
then $E\theta = p( f(y),z,g(z) )$.

Why is $y/z$  not applied to $E$ after using $x/f(y)$, so that the answer would be $E\theta = p( f(z),z,g(z) )$?

Because that's not how substitution is defined.

Seriously, there isn't much more to it than that. In some situations (such as applying a single step of a collection of rewriting rules), having the ability to substitute "each variable once, all at once" like this is important for the correctness of the definition. So substitution is defined so that there is a way to write these definitions correctly.

In other situations (such as the output of a unification algorithm), authors require that substitutions be idempotent, i.e. applying the substitution a second time does not change the result. This prohibits substitutions such as the one in the question, thereby avoiding the issue.


Is there a Tree with deterministic traversal, but which nodes can vary? I have a dynamic closest-pair problem. In my problem though, the points never move, but instead disappear and reappear.

That is, I would like to find for a point $p$ (where $p\in\mathbb{R}^3$)* in a set of points $P$, the closest point in $S$ where $S\subset P$. The catch its, while $S\subset P$, which elements of $P$ it contains can change at any time.

I was thinking of pre-computing a kd-tree where each leaf contains exactly one element of $P$, and each node/cell has an 'active' property. Then when I get a new $S$ I can recursively 'turn on' the levels of the tree which lead to active leaves. The active branches can then be traversed very quickly, ignoring nodes and leafs which do not contain active points.

The problem with this though is as particles are deactivated the bounding volumne goodness-of-fit will change and its no longer trivial to determine which branch should be traversed when there is a choice.

Is there a tree or spatial subdivision structure that will retain its deterministic traversal property even as points are added and removed (so long as they don't change position)?

The tree should be suitable for traversing on the GPU; primary consideration is performance.

*I've specified $p$ as having three dimensions, but it may have/be able to have 2 or even 1, if it is significant for the tree. Getting into details, $P$ will be an isomap of a 3D triangle mesh, but the mesh will not be simple, therefore its hard to say right now whether the isomap will have less than three dimensions or if the error will be too large if I try to fit it in 1 or 2. Three dimensions will be the worst case.

You can do this with any binary space partitioning tree, such as a k-d tree or an octree.

Your basic approach can actually be made to work.  The reason you think it won't work is because you have a misunderstanding about how nearest-neighbor search is done in these trees.  Let me show you how they work and how to adapt them to your situation: you'll see that your idea does work fine and is quite a nice approach.

The basic principle of nearest-neighbor search is:

Each subtree represents a (rectangular) region of space.
You'll keep track of the closest point to $p$ found so far.
For each subtree T, you'll figure out whether it's possible that any point in the region corresponding to T could be closer to $p$ than the closest found so far.  If not (if it's impossible), then you won't look at T or any subtree of T.  Otherwise, you'll recursively test each child of T.

This yields a recursive algorithm that explores some subset of the nodes in the tree.

The basic point is that nearest-neighbor search doesn't explore just one path through the tree.  Rather, it might "fork" and explore multiple paths.  However, it's still faster than looking at every leaf, because they're able to prune some (but not all) subtrees.

For example, build an octree representing $P$, the set of all points.  Each leaf of the octree corresponds to one point in $P$.  Each internal node of the octree corresponds to an "octant" (a rectangular volume of 3D space).

Next, augment the octree as follows: each internal node $x$ has a bit that indicates whether any of the leaves under $x$ are active (whether any of them correspond to points in $S$).  Call the octant "active" if it contains at least one point of $S$, so the bit for node $x$ indicates whether the corresponding octant is active.  You can update these active bits efficiently: adding or removing a point to $S$ can be done in $O(\log |P|)$ time.

Now, to find the neighbor nearest to point $p$, invoke $\text{Closest}(p, r)$, where $r$ is the root node of the octree and the procedure Closest is defined as follows:

$\text{Closest}(p, x)$:

If $x$ is not active, return $\infty$.
If $x$ is a leaf, return $d(p,x)$.
Otherwise, set $\text{curBest}$ to $\infty$.
For each child $y$ of $x$, do:

If $y$ is active and $d(p,y) < \text{curBest}$, set $\text{curBest} := \min(\text{curBest}, \text{Closest}(p, y))$.

Return $\text{curBest}$.

Here we define $d(p,y)$ (the distance from $p$ to an octant $y$) to be the distance from $p$ to the nearest point in $y$, i.e., the minimum of $d(p,z)$ where $z$ ranges over all points in $y$.  Notice that this can be computed efficiently through a straightforward but ugly case analysis.

Notice that the structure of the octree depends only on $P$, but not on which points are active.  Thus, you don't need to adjust the partitioning or split points as you change which points are active.

You can do the same with a k-d tree instead of an octree.

There is no guarantee about what the worst-case running time of this procedure will be.  However, in practice, I would expect this to be pretty efficient, as large swathes of the octree can be "pruned".  In particular, I would expect it to be faster than the naive algorithm of computing $d(p,s)$ for each $s \in S$, if $S$ is large.


Markov Chain Mixing Time of the Complete Graph I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn).

We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically 1/degree(vi). This is assuming the edges have no weights and there are no self-loops.

Also, the stationary distribution pi exists such that pi*P=pi.

For the complete graph, pi can be defined as a 1xn vector where each element equals 1/(n-1). I got this from defining each element to be deg(vi)/sum(deg(N(vi))) - the degree of node i divided by the sum of the degrees of its neighbors.

What would be the mixing time? I'm not sure how to go about finding it.

Let $M$ be an ergodic Markov chain with stationary probability $\pi$. For a state $x \in M$, let $p_x^t$ denote the distribution of a point which starts at $x$ and performs $t$ steps according to the transition matrix of $M$. The variation distance between $\pi$ and $p_x^t$, which is a measure of the similarity between the distributions, is given by the formula
$$
\|\pi - p_x^t\| = \frac{1}{2} \sum_{\sigma \in M} |\pi(\sigma) - p_x^t(\sigma)|.
$$
The sum goes over all states in $M$. The mixing time of a Markov chain $M$ is the smallest $t$ such that for every state $x$, $\|\pi - p_x^t\| \leq 1/(2e)$ (your account may use a different constant).

Given a graph $G$ without disconnected nodes, we can define a Markov chain as follows. The state space is the vertex set of $G$. When at state $x$, the next state is chosen uniformly at random from the neighbors of $x$.

In the particular case of the complete graph $K_n$, the random walk simply chooses a random vertex different from the current vertex. As you mention, $\pi$ is the uniform distribution. Let us compute some variation distances, for some vertex $x$ (the results are the same for all vertices):
$$
\begin{align*}
&\|\pi - p_x^0\| = \frac{1}{2} \left[|\tfrac{1}{n} - 1| + (n-1) |\tfrac{1}{n}-0|\right] = 1 - \frac{1}{n}. \\
&\|\pi - p_x^1\| = \frac{1}{2} \left[|\tfrac{1}{n} - 0| + (n-1)|\tfrac{1}{n} - \tfrac{1}{n-1}|\right] = \frac{1}{2} \left[\frac{1}{n} + \frac{n-1}{n(n-1)}\right] = \frac{1}{n}.
\end{align*}
$$
In both cases we have split the sum into two parts: $\sigma = x$ and $\sigma \neq x$. For all $n$ we have $\|\pi - p_x^0\| > 1/(2e)$. For $n > 2e$ (i.e., $n \geq 6$), we see that $\|\pi - p_x^1\| < 1/(2e)$. Therefore for $n \geq 6$, the mixing time is $1$.

With some effort, we can compute explicitly the variation distances for larger $t$. The transition matrix of the Markov chain is $(J-I)/(n-1)$ (where $J$ is the all ones matrix and $I$ is the identity matrix). Denoting by $e_x$ the basis vector corresponding to $x$, we have $p_x^t = (J-I)^t/(n-1)^t e_x$. Next, notice that $(J-I)/(n-1) \cdot \mathbf{1} = \mathbf{1}$ (where $\mathbf{1}$ is the constant 1 vector), and all other eigenvectors have the eigenvalue $-1/(n-1)$ (the corresponding eigenspaces being all vectors with zero sum). In particular, we can write $e_x = \frac{1}{n} \mathbf{1} + (e_x - \frac{1}{n} \mathbf{1})$, and so
$$
p_x^t = \left(\frac{J-I}{n-1}\right)^t e_x = \frac{1}{n} \mathbf{1} + \left(-\frac{1}{n-1}\right)^t (e_x - \tfrac{1}{n} \mathbf{1}).
$$
Explicitly, we have
$$
p_x^t(y) = \begin{cases}
\frac{1}{n} + \left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right) & \text{if } y = x, \\
\frac{1}{n} - \left(-\frac{1}{n-1}\right)^t \frac{1}{n} & \text{otherwise}. \end{cases}
$$
Therefore
$$
\begin{align*}
\|p_x^t - \pi\| &= \frac{1}{2}\left|\left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right)\right| + \frac{1}{2} \left|\left(-\frac{1}{n-1}\right)^t \frac{1}{n}\right| \\ &=
\frac{1}{2(n-1)^t} \left[1 - \frac{1}{n} + \frac{n-1}{n} \right] \\ &=
\frac{1}{(n-1)^{t-1}n}.
\end{align*}
$$
Using this explicit formula, we find that the mixing time of $K_2$ is infinity (indeed, the chain is periodic), and the mixing time of all of $K_3,K_4,K_5$ is $2$. For $n \geq 6$, as commented above, the mixing time of $K_n$ is $1$.


Reversible computation and no cloning theorem in quantum computing I am having a problem in understanding a conflict between reversibility in quantum computation and the No cloning theorem. Given a function f, we construct the reversible version of f by adding additional input and output wires to the circuit for f, possibly outputting junk bits. We then "copy" the output to another register to not to lose the output information using CNOT gates. But doesn't this contradict the No Cloning Theorem? We cannot copy the state of a quantum bit. Can we?

No-cloning theorem refers to creation of independent copies of a qubit. With CNOT gates you’ll only create mirrors.

For instance, if you have $\alpha \left| 0 \right> + \beta \left| 1 \right>$ and measure it, you’ll get 0 with probability $p_a=|\alpha|^2$ and 1 with $p_b=|\beta|^2$. Now if you clone this qubit and measure both, you should get 00 with probability $p_a^2$, 01 with $p_a p_b$, 10 with $p_b p_a$ and 11 with $p_b^2$.

Mirroring with CNOT gives a different picture: 00 with $p_a$, 11 with $p_b$ and zero probability for 01 and 10.


Lower Bound for Sorted 2-Sum Given a sorted array of integers $x$ and a target value $t$, determine if there exists a pair $x_i, x_j \in x \wedge i \neq j$ such that $x_i + x_j = t$.

What is the lower bound for this problem?

I know for the generalized $k$-sum (unsorted) there is a lower bound of $\Omega(n^{\lceil \frac{k}{2}\rceil} )$. This would mean if the array were unsorted we could prove a lower bound of $\Omega(n)$. I would assume sorting it would give us some sort of extra information. I also haven't seen any lower bound claims of this problem so feel free to link a solution if one already exists.

It is relatively easy to show  a lower bound of $\Omega(\log_2 n)$ using an adversary:

Create $x$ such that every sum of each pairs of integers is unique (hint: Fibonacci Numbers).
We also have that the target $t$ is larger than all values so no values can be preemptively discarded (hint: add a reasonable constant to all values).

Now we have $\frac{n(n-1)}{2}$ possible target values. Using an optimal binary search of these target values it takes $\Omega(\log_2 (n^2)) = \Omega(\log n)$. So it's easily lower bounded by $\log n$.

Although the algorithm can't necessarily perform an optimal binary search, because it takes at least $\Omega(n^2)$ to create all the unique sums of pairs. Unless it could figure out the median of all sums of pairs in less time than it takes to create them (another interesting question).

I would assume we can take advantage of this lack of knowledge in some way to establish a greater lower bound, possibly $\Omega(n)$. The standard algorithm to solve this takes $O(n)$ using two pointers. It does this because it's difficult to discard particular values without explicitly checking them. Any help would be greatly appreciated.

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

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

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

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

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

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

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

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

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

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

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


Regular language? Union of the dictionary and an non-regular language I'm attempting to figure out if a union of two languages is regular.

$$
L_1 = \{all\ the\ words\ in\ the\ Oxford\ dictionary\} \\
L_2 = \{w : w\ has\ twice\ as\ many\ a's\ as\ b's\}
$$

$L_2$ is well established to be a non-regular language. However, I am not sure if $L_1$ would be considered a regular language. The language should be finite (albeit large), which suggests it is regular, but I'm not certain.

If $L_1$ is regular, then I would consider the union $L_1 \cup L_2 $ would also be regular, as by the same argument, the language would be finite.

What does everyone think?

The best way to see that $L_1 \cup L_2$ is not regular is through closure properties of the regular languages.

Theorem. If $L_1$ is finite and $L_2$ is not regular, then $L_1 \cup L_2$ is not regular.

Proof. Since $L_1 \setminus L_2$ is finite, it is regular.
Suppose $L = L_1 \cup L_2$ were regular. Then $L \setminus (L_1 \setminus L_2) = L_2$ would also be regular, contrary to assumption. $\qquad\square$


Checking whether the win-loss standings of a league are possible You're hosting a 1 v 1 basketball league with a game schedule. At the end of the league you have each player report their supposed win-loss record (there are no ties), but you want to check whether the proposed standings were actually possible given the schedule.

For example: you have four players (Alice+Bob+Carol+Dave) and your schedule is a simple round robin. The reported standings [A: 3-0 B: 1-2 C: 1-2 D: 1-2] and [A: 2-1 B: 1-2 C: 1-2 D: 2-1] would be possible, but the standing [A: 3-0 B: 0-3 C: 0-3 D: 3-0] would not be.

Now suppose the schedule is instead a 3 game head to head between Alice+Bob and Carol+Dave. The reported standing [A: 3-0 B: 0-3 C: 0-3 D: 3-0] is now possible, but [A: 3-0 B: 1-2 C: 1-2 D: 1-2] would no longer be.

(The schedule does not need to be symmetric in any way. You could have Alice only play against Bob 10 times, then make Bob+Carol+Dave play 58 round robins against each other.)

Problem: Given a schedule with k participants and n total games, efficiently check whether a proposed win-loss standings could actually occur from that schedule.

The O($2^n$) brute force method is obvious, enumerate all possible game outcomes and see if any match the proposed standings. And if k is small increasing n doesn't add much complexity - it's very easy to check a two person league's standings regardless of whether they play ten games or ten billion games. Beyond that I haven't made much headway in finding a better method, and was curious if anyone had seen a similar problem before.

This can be modelled as a Max-Flow problem.

As a preprocessing step, make sure that the number of games is equal to the sum of the number of wins (if not, you know something is wrong).

Let $G$ be a set of vertices corresponding to the games played, and $P$ a set of vertices corresponding to the players. Let $s$ and $t$ denote two additional vertices (source and sink).

Now for every game $g\in G$ played between $p1\in P$ and $p2\in P$, add an edge from $s$ to $g$ with capacity $1$ and edges from $g$ to $p1$ and $g$ to $p2$ also with capacity $1$. This models the fact that the game can give one point to either player.

Then for every player $p\in P$ add an edge from $p$ to $t$ with capacity equal to the reported number of wins for player $p$. This models the fact that this player should win at most this number of games.

It is easy to see from here that if the reported scores are possible, there will be a saturating flow from $s$ to $t$ and reciprocally. So all you need to check is if the maximum $s,t$-flow in this graph is equal to the number of games played.

Alternatively, you could also have a graph with one vertex per game and a number of vertices for each player corresponding to the number of wins, connect them the same way as before, and look if the number of edges in a maximum matching is equal to the number of games (but this is almost the same thing really).


Evaluating the average time complexity of a given bubblesort algorithm. Considering this pseudo-code of a bubblesort:

FOR i := 0 TO arraylength(list) STEP 1
    switched := false
    FOR j := 0 TO arraylength(list)-(i+1) STEP 1
        IF list[j] > list[j + 1] THEN
            switch(list,j,j+1)
            switched := true
        ENDIF
    NEXT
    IF switched = false THEN
        break
    ENDIF
NEXT

What would be the basic ideas I would have to keep in mind to evaluate the average time-complexity? I already accomplished calculating the worst and best cases, but I am stuck  deliberating how to evaluate the average complexity of the inner loop, to form the equation.

The worst case equation is:

$$
\sum_{i=0}^n \left(\sum_{j=0}^{n -(i+1)}O(1) + O(1)\right) = O(\frac{n^2}{2} + \frac{n}{2}) = O(n^2)
$$

in which the inner sigma represents the inner loop, and the outer sigma represents the outer loop. I think that I need to change both sigmas due to the "if-then-break"-clause, which might affect the outer sigma but also due to the if-clause in the inner loop, which will affect the actions done during a loop (4 actions + 1 comparison if true, else just 1 comparison).

For clarification on the term average-time: This sorting algorithm will need different time on different lists (of the same length), as the algorithm might need more or less steps through/within the loops until the list is completely in order. I try to find a mathematical (non statistical way) of evaluating the average of those rounds needed.

For this I expect any order to be of the same possibility.

Recall that a pair $(A[i], A[j])$ (resp. $(i,j)$) is inverted if $i < j$ and $A[i] > A[j]$.

Assuming your algorithm performs one swap for each inversion, the running time of your algorithm will depend on the number of inversions.

Calculating the expected number of inversions in a uniform random permutation is easy:

Let $P$ be a permutation, and let $R(P)$ be the reverse of $P$. For example, if $P = 2,1,3,4$ then $R(P) = 4,3,1,2$.

For each pair of indices $(i,j)$ there is an inversion in exactly one of either $P$ or $R(P)$.

Since the total number of pairs is $n(n-1)/2$, and the total number and each pair is inverted in exactly half of the permutations, assuming all permutations are equally likely, the expected number of inversions is:

$$\frac{n(n-1)}{4}$$


Halting problem of TM which recognize recursive languages is undecidable? I am preparing for an exam and I came across this question in one of the tests.

  Halting problem of Turing machines which recognize recursive languages
  is undecidable. (True / False)

The solution given says the statement its False.

But I think the statement is True. Halting problem in itself is undecidable. We can't determine whether the Turing Machine will halt or not.

The test series has a history of wrong answers that's why I am seeking an explanation even if I am wrong.

Edit:
I was looking at the answers and I have trouble understanding the explanations. I know that 'By definition, recursive languages are decideable by Turing machines.'
I will tell you how I breakdown the question. I am given a TM and told that this TM recognizes a recursive language. How do I know that the TM will halt?

By definition, recursive languages are decideable by Turing machines. Thus for recursive languages the TM will always halt.


Douglas-Peucker line simplification algorithm time complexity I am analyzing the time complexity of the Douglas-Peucker line simplification algorithm. Reading online I've found that it has a worst-case running time of $O(n^2)$ where $n$ is the number of points on the line. However, I haven't been able to provide complete proof. Here is the pseudo-code I am working with:

Here is my analysis:
Line 1: $O(1)$
Line 2: We can say that it goes through all points in the polyline formed by the first point and the last point in $PL$ and return the point with the maximum distance to the straight line between the mentioned points. We can safely say this is $O(n)$
Lines 4-6: If we are here we are doing two recursive calls. The number of elements used in each call could be different (not always in half). Depends on the point found in Line 2. Leaving implementation details aside, we can say that splitting is $O(1)$. Also, we have a $JOIN$ operation which would take $O(n)$ to join both lists.
Line 8: This is also a $JOIN$ operation but this only takes $O(1)$.
After looking at these steps I think we have the following recurrence relation:
$T(n) = T(index + 1) + T(n - index) + 2n$ where $index \in \{1, \dots, n-1\}$
Am I right? If so, how could I prove this is $O(n^2)$? Master Theorem?
Thank you very much in advance
EDIT: Changed description on Lines 4-6. Thus, also changed recurrence formula.

Your analysis seems correct, except for that you need $T(n)=T(index)+T(n-index+1)+2n$ instead because when $index$ is either $0$ or $n-1$ you won't get in the right hand side another factor of $T(n)$, which is not allowed.
In fact, it will yield something very close to the recurrence of the running time in the quicksort algorithm.
Worst case scenario
When index is either $0$ or $n-1$, the recurrence will boil down to $T(n)=T(1)+T(n-1)+2n = T(n-1) + (2n + T(1))$. You can easily show by induction that $T(n)=\Theta(n^2)$ in this case.
Best case scenario
We assume the input in the recursion will always be cut down by half. That is, the recursion is $T(n)=2T(n/2)+2n$.
Define $b=a=2$ and $f(n)=2n$. Then, $T(n)=aT(n/b)+f(n)$.
We can calculate $c_{crit}=\log_{b}(a)=\log_2(2)=1$ and thus $f(n)=2n=\Theta(n)=\Theta(n^{c_{crit}})$.
Now we can directly use the second case to get that $T(n)=\Theta(n^{c_{crit}}\log(n))=\Theta(n\log(n))=O(n^2)$
Average case scenario
If we assume that the input is a random variable, such that the choice of $index$ is uniformly distributed in $\{0,\dots,n-1\}$, then the algorithm takes expected time $\Theta(n\log(n))$. Take a look at the proof for quicksort to see how its done.


Logical characterization of $NC^1$ Morioka in his 2005 dissertation [1] referenced "On Uniformity within $NC^1$" by
Barrington, Immerman, and Straubing. Using the following statement:

  Every $\mathbf{NC^1}$-predicate is computed by a Dlogtime-uniform family of polynomial-size propositional formulas

This sentence is essential to defining a reduction from an $\mathbf{NC^1}$ function to the $\Sigma_1^q$-witnessing problem for $G_0$, however I'm not able to understand how this statement was reached from the original paper, either I'm missing something important here or my expertise in circuit complexity is just not enough, can someone intuitively explain how this sentence came to be?

Morioka considers uniform versions of his circuit classes:

  Throughout this paper we write $\mathbf{NC^1}$ to mean $\mathbf{Dlogtime}$-uniform $\mathbf{NC^1}$, which is equivalent to the class $\mathbf{Alogtime}$ of languages accepted by an alternating Turing machine in $O(\log n)$ time.

The paper you mention should imply the equivalence of these two definitions. The statement you quote, however, is just true by definition.


What is the best Approximation algorithm to schedule a task graph? If I have a task graph T and want a schedule to optimize the make-span, what is currently the best approximation algorithm for this problem? Are there any constant approximation algorithms?

You get a $2-\frac1m$-approximation (where $m$ is the number of machines), by greedily scheduling tasks as they become available, and this is essentially the best we can do at the moment. Improving this is actually a major open problem in scheduling (see e.g. this ).


What is the relation between countability and recursive enumeration? Does recursive enumeration implies countability?
Does countability implies recursive enumeration?

I believe the first implication holds but not sure about the second. A good  example would suffice.

If a language is recursively enumerable then it is countable. However, there are languages that are countable but not recursively enumerable. For example, consider the $A_{TM}$, the language of the Halting problem. This language is recursively enumerable while its complement $\Sigma^*-A_{TM}$ is not recursively enumerable, otherwise $A_{TM}$ would be decidable. However, $\Sigma^*-A_{TM}$ is clearly countable since it is a subset of a countable set $\Sigma^*$.

Hence one simple relation between countability and enumeration is that every r.e. set is countable, but the opposite is not always true.


Space and time complexity of balanced parentheses enumeration algorithm Consider the following recursive algorithm for printing all balanced strings with $n$ left and right parentheses. It is called with prefix = $\epsilon$ (the empty string):

A(prefix):

If prefix contains $n$ right parens: print prefix and return.
If prefix contains more left parens than right parens: call A(prefix + ")").
If prefix contains less than $n$ left parens: call A(prefix + "(").

As an optimization, instead of counting the number of left and right parens at each step of the recursion, we carry them around (so A gets two more parameters, which are the number of parens of teach type in prefix).

For example, when $n = 3$, this outputs the following strings:

   ()()()
   ()(())
   (())()
   (()())
   ((()))

This is a simple enumeration algorithm. The space complexity is $O(n)$, and the time complexity is the size of the output, since you do not doing anything useless.

By the way, the number of rows in the Catalan number. $C_n=\frac 1 {n+1}\binom {2n} n$.


Eliminating left recursion and left factoring this grammar I have a grammar S-> SS* | SS+ | a
Really confused on how to remove the left recursion and do left factoring

My attempt on removing left recursion :
S -> aS'
S' -> S+S' | S*S' | epsilon
If this is correct, I'm stuck in left factoring. Help!

check this image the problem is explained


How is the Time Complexity of a Function Problem different than its corresponding Decision Problem? Every function problem has a corresponding decision problem, which is simply the graph of the function problem, according to

https://en.wikipedia.org/wiki/Decision_problem#Function_problems

which reads that the time complexity of a function problem and decision problem underlying decision problem "...may not be considered equivalent in some typical models of computation".  This seems to be the case with the Greatest Common Divisor decision problem, according to

https://en.wikipedia.org/wiki/Greatest_common_divisor#Complexity

So I'd like to use this as an example.  I am having a difficult time understanding why the complexity of the GCD function problem is different than its corresponding decision.  If the Decision Problem is simply the graph of the Function problem, which is solvable in under quadratic time, how could the decision problem be solvable only in polynomial time?

The Wikipedia article is confusing.

There are two things going on here.

Here's first thing: the complexity class P is defined to be a class of decision problems.  Thus, by definition, no function problem is in P.  So it's correct that the decision problem for gcd is in P, but the function problem for gcd is not.  Of course, this is pretty trivial.  So the first thing is not very interesting -- but it does explain why the Wikipedia article makes that odd comment about the decision problem for gcd being in P.

The second thing is more interesting: is there a difference in the running time between the decision problem and function problem?  Sometimes there is.  For instance, consider factoring.  A function problem is: given a number $t$, factor $t$ into a product of primes.  A decision problem is: given a number $t$ and primes $p_1,\dots,p_k$, check whether $t = p_1 \times \dots \times p_k$.  There is no known polynomial-time algorithm for the function problem, but there is an easy polynomial-time algorithm for the decision problem.  So, it's apparently easier to check whether the answer is correct than to find the answer.  Indeed, for any NP-complete problem, we believe it is easier to check the answer than to compute it, so the function problem appears to be harder than one plausible formulation of the decision problem.  (For that reason, when we turn function problems into decision problems, we usually do it in a different way than the one you mention.)

What about for gcd?  The function problem is: given $x,y$, compute $\gcd(x,y)$.  The fastest algorithm known for this takes $O(T(n) \log n)$ time, where $n$ is the number of bits of $x,y$ and $T(n)$ is the time to multiply two $n$-bit numbers.  It is an open question whether this can be done faster than that, or exactly how fast this is.  A plausible decision problem is: given $x,y,d$, check whether $\gcd(x,y)=d$.  Here it is not known what the fastest possible running time is.  You can check whether $d$ divides $x$ and $y$ in $O(T(n))$ time, so you can check whether $d | \gcd(x,y)$ in $O(T(n))$ time -- faster than we know how to compute the gcd in the first place.  But I don't know of any algorithm to turn this into a way to check whether $d = \gcd(x,y)$ asymptotically faster than computing the gcd from scratch in the first place.  So we just don't know in this case whether the decision problem can be solved faster than the function problem.


Recurrent relation for algorithms with two stages I am trying to do the recurrence relation for my algorithm, but it has two variables $T(n,m)$. For sufficiently small $n$, $m$ is practically the same as $n$, but $m$ cannot grow beyond some constant $k$. So once $n$ grows beyond $k$, $m$ turns to constant $k$. So it has two different stages.

I have done the relation in both cases: when $m$ is another variable, and when $m$ is a constant, but how do I put them together?

Using $a=2, b=2$ as an example: this recurrence relation with $m$ as a variable like $n$:
$$T(1)=1$$
$$\begin{equation*}
\begin{split}
T(n) & = 2T(\frac{n}{2})+m \\
& = 2T(\frac{n}{2})+n\\
& = n+nlog_2n
\end{split}
\end{equation*}$$

Treating $m$ as a constant:
$$\begin{equation*}
\begin{split}
T(n) &= 2T(\frac{n}{2})+m \\
&= n+mn-m
\end{split}\end{equation*}$$

Please feel free to check my math. Now how do I represent this as one recurrence relation? $m$ cannot grow beyond constant $k$.

Just solve both cases separately. I.e., consider cases for $m < k$ and $m = k$ separately. The solution for the first one (i.e., $T(n, k - 1)$) gives the starting point for the second recurrence (i.e., $T'(n) = T(n, k)$, presumably for $n \ge k$).


Minimal DFA: Number of states I am trying to solve a problem with regards to a DFA. What is the minimal number of states for the following language:

$$L:=\{x\in\{a,b\}^n\ \ | \ \ |x|_a=|x|_b\}$$

where $|x|_a$ denotes the amount of $a$'s in the word $x$. I have done some calculations and got $3\cdot2^{(n/2)}-1$. Is this the correct number of states?

Here is the DFA for $n=4$:

Hint. Your answer is plain wrong. First, it trivially does not work if $n$ is odd. But it is also wrong if $n$ is even (except for $n = 2$). Just compute the minimal automaton of $\{aabb,abab,abba,baab,baba,bbaa\}$ to be convinced. Your formula gives $3\cdot 2^2 - 1 = 11$ states but the minimal automaton only has $10$ states.


Is the set cover problem NP-complete when the cardinality of the collection of sets is equal to the cardinality of the universe? In the set cover (SC) problem we are given a universe  $U$ (a set) of $n$ elements and a collection $S$ of $m$ sets whose union equals the universe. The set cover problem is to identify the smallest sub-collection of $S$ whose union equals the universe.

If I add the constraint that $m=n$ to SC, is this new problem still NP-hard?

My attempt is as follows:

To construct an instance of the new problem we do:

If $n=m$, then we are done.
If $n>m$, then we simply add $n-m$ dummy sets to the collection $S$ and we are done.
If $n<m$, then ... (I am stuck). But I think since the union of the $m$ sets is $U$ then we must have that $S$ contains redundant sets. Is this OK?

Yes, it is still NP-complete. If you have an instance with $n < m$, then you can pad $U$ with $m - n + 1$ new elements and add new subset containing only the new elements. The original instance has a solution of size $s$ if and only the padded instance has a solution of size $s + 1$. The reduction is obviously polynomial time.


Implementing mathematical theory of arithmetic in Haskell via Curry-Howard correspondence I have to ask for forgiveness in advance if the whole question doesn't
make a lot of sense, but unfortunately, I have no better intuition as
of right now and this seems like the best starting point I could come
up with.

I'm reading Tarski's book "Introduction to Logic: and to the
Methodology of Deductive Sciences", I'm on Part VII Chapter 43
"Primitive terms of the theory under construction; axioms concerning
fundamental relations among numbers". It begins by laying out an
elementary mathematical theory of arithmetic of real numbers.

The primitive terms are:

real number (denoted as variables like x, y)
is less than (<)
is greater than (>)
sum (+)
N meaning "the set of all numbers". Thus, an expression "x is a
number" would be written as x ∈ N
is not less than (≮)
is not greater than (≯)

Among the axioms of the theory under consideration, two groups may be
distinguished. The axioms of the first group express fundamental
properties of the relations less than and greater than, whereas those
of the second are primarily concerned with addition. For the time
being, we shall consider the first group only; it consists, altogether,
of five statements:

AXIOM 1. For any numbers x and y (e.g., for arbitrary elements
of the set N) we have: x = y or x < y or x > y
AXIOM 2. If x < y, then y ≮ x
AXIOM 3. If x > y, then y ≯ x
AXIOM 4. If x < y and y < z, then x < z
AXIOM 5. If x > y and y > z, then x > z

Our next task consists in the derivation of a number of theorems from
the axioms adopted by us:

THEOREM 1. No number is smaller than itself x ≮ x
THEOREM 2. No number is greater than itself: x ≯ x

Now I have to stop and finally explain my intentions. I've heard many
times about a so-called "Curry–Howard–Lambek correspondence", and it
made sense whenever I've read examples of it. I am also not
comfortable with manually writing out the reasoning to prove the
theorems, I'd like the machinery of going through reasoning steps to
be checked by a computer for me.

So, I tried to encode the terms, axioms and potentially theorems (got
stuck earlier) in Haskell, but I failed in many ways. I won't show you
all the examples of what I did, but here's the most naive approach of
encoding propositions as types and their proofs as programs:

data Nats
  = NatX
  | NatY
  | NatZ

x :: Nats
x = NatX

data OpGt =
  OpGt Nats
       Nats

data OpLt =
  OpLt Nats
       Nats

data OpEq =
  OpEq Nats
       Nats

data OpNotLt =
  OpNotLt Nats
          Nats

data OpNotGt =
  OpNotGt Nats
          Nats

data Ax1Res
  = Ax1ResLt OpLt
  | Ax1ResGt OpGt
  | Ax1ResEq OpEq

-- how to implement best?
ax1 :: Nats -> Nats -> Ax1Res
ax1 = undefined

-- this doesn't describe the x and y in the type
ax2 :: OpLt -> OpNotGt
ax2 = undefined

This piece of code brings more questions than it gives answers:

should axioms be implemented or kept as unimplemented functions
which we just assume to exist?
how do I limit the implementation of my functions to only rely on
available theorems and axioms if I can construct basically any term?
Should I hide the constructors?
types should obviously contain variables like x and y, I tried
that in other approaches but that gets even hairier

My questions are:

what would be a proper implementation of such proofs in Haskell?
what materials should I read in order to make a proper
implementation myself and understand the topic better?

I hope the vagueness and my level of ignorance in the question will not
put you off from answering it. Thank you!

Proofs in Haskell?

Okay, first let's talk about the Curry-Howard correspondence. This says that one can view theorems as types and proofs as programs. However, it says nothing about which specific logic a particular programming language represents.

In particular, Haskell lacks dependent types. That means that it can't express statements with "forall x" or "exists x". So immediately there's no way to encode your axioms.
The problem is that Haskell's types only let you refer to other types, not to specific values of those types. Your axiom says "forall x and y, Property holds for x and y": it's reasoning not about $Nat$ as a class, but about specific values of that class.

There are ways to fake it in Haskell, by encoding values with a type-level representation, but I'd strongly recommend against those for a beginner.

What does the Curry-Howard Correspondence Actually Mean?

What Curry-Howard is actually saying is not that we can write a program that implements a checker for proofs. What is says is that we can view a proof as a form of a program in a purely-functional language. Specifically, a proof is like a program that takes proofs of its assumptions as input, and produces proofs of its conclusions as outputs.

The key is that propositions are like types, and proofs are like programs. So in your example, it doesn't make sense to have an implementation of your axioms, since axioms are propositions that you take as true, without proof. An implementation would correspond to a proof of them.

The real magic of Curry-Howard comes when we introduce dependent types. The key is the dependent function type: instead of just having $A \to B$, we have $(x:A) \to B$, where $x$ can occur in $B$.

There's a lot going on here. First, we've blurred the line between types and values. In the same way that the type constructor List takes an argument to become a type, like List Int, we now can have type constructors that take values as arguments.

The classic example of this is $Eq$ for representing proofs of equality. For any values $x,y$, $Eq\ x\ y$ is the type of proofs that $x = y$. So we have a type indexed on values.

Secondly, we've now given names to our arguments in the type, not just in the implementation. So the order of arguments very much matters, because the types on the right can refer to the names on the left. They depend on the names, thus the name dependent types.
What this is really saying is that the return type of the function can change, depending on the value of the argument given.

Curry-Howard then says that, if we produce a well typed function of type $(x:A) -> B$, this is the same as saying "for all $x$ that satisfy $A$, $B$ holds".

The dual of this is dependent pairs, which code "exists" proofs. Instead of having the tuple type $(A,B)$, we now have $(x:A, B)$, where $B$ can refer to $x$. This means that the type of the thing on the right can depend on the value of the thing on the left. This is a constructive form of an existential proof: the way you prove "there exists an x satisfying B" is by saying "here's the x, and here's the proof it satisfies B".

Where to learn more?

If you want to prove things in a formal setting, I'd recommend
Coq, Agda, Idris, or Isabelle, since they have the machinery
for dealing with dependent types and proving things.

Some good free resources:

Software Foundations
Certified Programming with Dependent Types
Lean You An Agda and Achieve Enlightenment

Some nice articles/papers/tutorials on the topic include:

Propositions as Types
The Power of Pi
Tutorial Implementation of Dependently Typed Lambda Calculus

The Idris book is popular, but not free:
Type Driven Development in Idris


Transform PDA with acceptance of final state + empty stack to just final state "It is a well known result that every PDA with acceptance condition of an
empty stack and reachability of a final state can be transformed to an equivalent PDA with acceptance
condition requiring only reachability of a final state. Transform PDA ____ to an equivalent PDA with
acceptance requiring only reachability of a final state."

I'm just a bit confused on what steps I have do to. My thought process is...final state + empty stack acceptance is a subset of just a final state acceptance? When I try to 'transform' my PDA, it ends up looking exactly the same as the original.

Given a PDA $M$, you can define the following associated languages:

The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state with an empty stack. We denote this language by $L_1(M)$.
The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state. We denote this language by $L_2(M)$.

The two languages are not always the same, that is, it could well be that $L_1(M) \neq L_2(M)$. You have to show that for each PDA $M$ there is another PDA $M'$ such that $L_1(M) = L_2(M')$.


Algorithm for length of longest common subsequence The case of multiple strings. A slight modification of the dynamic programming algorithm for two strings is used as a subroutine. Here is the pseudo code:

# The modified dynamic programming algorithm for longest common subsequence.
# Inputs: x, y - the strings
          xL, yL - their respective length vectors
lcs(x, xL, y, yL)
    u = |x|
    v = |y|
    T = 2-dimensional table with default value 0 for all elements.
    for i in 0..u-1
        for j in 0..v-1
            if x[i] == y[j]
                T[i, j] = T[i - 1, j - 1] + 1
            else
                T[i, j] = max(T[i - 1, j], T[i, j - 1])
            # limit the value of the table element by the length vectors:
            T[i, j] = min(T[i, j], xL[i], yL[j])
    # Take the element wise minimum of the vectors for each of the strings and the bottom row and right-most column respectively.
    return x, element-wise-minimum-of(xL, T[_, v - 1]), y, element-wise-minimum-of(yL, T[u - 1, _])

# Algorithm to compute the length of the longest common subsequence of multiple strings.
# Inputs: strings - a list of strings
mlcs(strings):
    if for any string x: |x| == 0
        return 0
    R = a dictionary indexed by a string x, where the value is initialized to be the length vector of x (initially [1,2,..,|x|]).
    N = initially a copy of R.
    while true
        for i in 0..|strings|
            for j in i + 1..|strings|
                x, y = strings[i], strings[j]
                _, xL, _, yL = lcs(x, R[x], y, R[y])
                R[x], R[y] = xL, yL
        if for every string x: N[x] is element wise equal to R[x]
            break
        else
            N[x] = R[x]
    return the last element of any of the vectors in R

What follows is an implementation in the python language.

import collections

def lcs(x, xL, y, yL):
    u = len(x)
    v = len(y)
    T = collections.defaultdict(int)
    for i in range(u):
        for j in range(v):
            if x[i] == y[j]:
                T[i, j] = T[i - 1, j - 1] + 1
            else:
                T[i, j] = max(T[i - 1, j], T[i, j - 1])
            T[i, j] = min(T[i, j], xL[i], yL[j])
    return (x, [min(xL[i], T[i, v - 1]) for i in range(u)]), (y, [min(yL[j], T[u - 1, j]) for j in range(v)])

def mlcs(strings):
    if any(len(x) == 0 for x in strings):
        return 0
    R = {x: list(range(1, len(x) + 1)) for x in strings}
    N = {x: R[x] for x in strings}
    while True:
        for i in range(len(strings)):
            for j in range(i + 1, len(strings)):
                x, y = strings[i], strings[j]
                (_, xL), (_, yL) = lcs(x, R[x], y, R[y])
                R[x] = xL
                R[y] = yL
        if all(all(N[x][i] == R[x][i] for i in range(len(x))) for x in strings):
            break
        else:
            for x in strings:
                N[x] = R[x][:]
    return R[strings[-1]][-1]

The idea is to initialize for each input string a vector which holds information for each position of that string about what is the maximum length of a LCS up to that position. These are updated each time a pair-wise LCS computation is done. This in turn is done for all pairs until all the vectors are stable (ie. don't change) between iterations.

So far testing gives me mixed results. The correct length at first seems to be produced pretty reliably, but when trying to use the function mlcs as an oracle in an algorithm for retrieving an actual longest sequence, sometimes the result is not what is expected. This may or may not indicate that there are cases for which an incorrect length is produced.

So on to the question: Is the idea of the length computing algorithm sound?

The algorithm is incorrect. That is it may return a length that is greater than the actual length of a longest common subsequence. Here is a test case which fails to produce the correct length: ['baaa', 'aaba', 'baba'].


Matrix chain multiplication: Greedy approach some suggested a thread in which the algorithm multiplies the 2 matrices with lowest values first. Mine is different: it divides by parenthesis the 2 matrices. And continues to the next section.

The problem is: finding the most efficient way to multiply a series of matrices together, using an algorithm of some sort, and comparing these algorithms to find the most efficient one.

The dynamic algorithm approach works at a time complexity of theta of N^3.

My question is, what is the runtime of this algorithm:

A= 5x2
B= 2x7
C= 7x3

1) First, find the matrix with the lowest dimension ( a matrix which has the lower number from the rows or columns of all the matrices).

*If the lowest number is in the last dimension, it is the same like putting the entire sequence in parentheses.

*There is no guidance as to what to do if the lowest number appears twice in the sequence, so I suggest the algorithm just takes 1 randomly.

2) Then divide the sequence to 2: (A)(B•C).
The parentheses will close on the matrix from the right and open on the next matrix. This way they will divide the series to 2 parts.

Then repeat the process for the 2 parts. Stop when you have 1 (or 2) matrices in the sequence.

Is this algorithm optimal?
It has to be better than N^3 (the usual algorithm)

Consider the product $ABC$, where

$A$ is $5\times 2$
$B$ is $2\times 3$
$C$ is $3\times 100$

Your algorithm first computes $BC$ (600 products) and then $A(BC)$ (1000 products), for a total of 1600 products.

The optimal solution first computes $AB$ (30 products) and then $(AB)C$ (1500 products), for a total of only 1530 products.

Suppose that $A$ is $a\times b$, that $B$ is $b \times c$, and that $C$ is $c\times d$. There are two possibilities:

Compute $AB$ and then $(AB)C$: cost is $abc + acd = ac(b+d)$.
Compute $BC$ and then $A(BC)$: cost is $bcd + abd = bd(a+c)$.

The first option is preferable if
$$
\frac{b+d}{bd} < \frac{a+c}{ac}
$$
or equivalently
$$
\frac{1}{b} + \frac{1}{d} < \frac{1}{a} + \frac{1}{c}.
$$
For example, above we have $a = 5$, $b = 2$, $c = 3$, $d = 100$. Since
$$
\frac{1}{2} + \frac{1}{100} < \frac{1}{5} + \frac{1}{3},
$$
the order $(AB)C$ is preferable.

Your decision procedure would prefer this order if $c < b$, that is, if
$$
\frac{1}{b} < \frac{1}{c}.
$$
Your condition misses the contribution of $a,d$.


how can i proof $3^n$ has a greater growth than $n2^n$? i want to prove that $3^n$ has a greater growth than $n2^n$ or $3^n = O(n2^n)$. but how can i do it mathematically? by induction or contradiction or other ways of proof.

One simple way would be divide both sides by $2^n$ to get $n$ and $(1.5)^n$. You can simply take a limit of $l  i  m_{n\to\infty} \frac{(1.5)^n}{n} = \infty$ To show that $(1.5)^n$ grows larger. This limit holds for any number larger than 1.


Bubble sort: average number of total key comparisons I want to know the steps for finding a Formula for Average number of total comparisons in bubble sort.
Please look at this example:

4 3 2 1 -> 3 2 1 4 ->   3 comparisons
3 2 1 4 -> 2 1 3 4 ->   2 comparisons
2 1 3 4 -> 1 2 3 4 ->   1 comparisons

For ordered and reverse ordered input we have different formula for number of total comparisons:
Min = n-1
Max = n(n-1)/2

And I want a formula with steps to get average of it - all possible inputs - / expected number of key comparisons for each of n input values selected from a uniformly random source
My try
(Sum of total comparisons)/(n-1) =>  n(n-1)/2/(n-1) => (n-1)

NOTE : (n-1) is number of steps
is it right?

I'm assuming that all elements in the array you're sorting are distinct.
The average number of comparisons over all permutations of the array is equal to the expected value of the number of comparisons, so let's calculate that instead.
The total number of comparisons done to sort some array $A$ (length $N$) is equal to $N - 1 + (\text{Number of inversions in } A)$, where an inversion is a pair of indices $i < j$ where $A_i > A_j$. By linearity of expectation, the expected number of comparisons is thus
$$
N - 1 + \sum_{i < j}P(A_i > A_j) = N - 1 + \frac{N(N - 1)}{4}
$$


History/Etymology- Map/[Hash]Map vs map() Forgive me/delete this question if it doesn't qualify as Computer Science:

I've always wondered about the relationship between Map the data structure and map() the function. I know they are two different things. Why share the name?

Well, I am only a beginning MSc student in computerscience but if if followed the classes correctly the purpose of a hash is to create some memory space, let say this memory space is 10 adresses big. With a hashmap, every value you put in the hashmap gets coupled with a key. That key will first be mapped by a hashfunction to produce a unique number. That number is within the range of possible adresses in the vector. $ f: A \mapsto B $ with A the collection of possible keys and B a collection of possible adresses. Mathematically speaking this is a mapping. The value gets then saved to that adress. Now it is possible that you want to save more values than the vector allows or the hashfuntion is not completely one on one (that is every y has a unique x value it corresponds to) In that case you wil need to make the vector longer and remap every value within the vector or you reshash the value from the hashfunction with that same same value it has returned (usualy slightly edited to avoid all values being at the same place in the vector) as the parameter to find a new adress that wasn't used before. There are a number of other techniques involved and other methods but that is beside the point.
Long story short. This mapping of key values is, i believe, the reason it is called a hashmap.


Slowest growing upper bound for the minimum length of a complementary prefix regular expression A postfix regular expression acting on a binary alphabet (specification from this post) can be described using the following grammar,

R → 0 or 1 or _ or ! or RR; or RR| or R+

where,

0 and 1 match their selves,

! matches nothing,

_ matches the empty string,

; is concatenation,

| is alternation,

R+ matches 1 or more occurrences of R.

(The linked post above gives some example regular expressions and the strings it matches.)

What is the slowest growing upper bound on the length of the regular expression complementary to another regular expression as a function of the length of the latter?

So far, I have a double exponential. I show that an "input" regular expression $r_1$ will give an NFA that has 1 more state than the length of $r_1$. By the powerset construction, the resulting DFA will a maximum of have $2^{1+\text{length(}r_1\text{)}}$ states. Clearly, the complementary DFA will have the same number of states, i.e. the same size.

I then use an algorithm to construct a regular expression given a DFA to get the upper bound of the length of this regular expression as a function of the size of the DFA. This gave another exponential, $\frac{16}{3}(4^n-1)$ where $n$ is the size of the DFA.

Combining the two gives $\frac{16}{3}(4^{2^{n+1}}-1)$, where $n$ is the length of $r_1$, as the length of the complementary regular expression. I am not concerned about the constants, as stated in the question, only how fast it grows. So, if I got my big-O notation correct, this gives $O\left(4^{2^n}\right)$.

This seems unnecessarily large, can it be lower? Can it be lowered to a mere exponential?

Wikipedia says that taking the complement "can cause a double exponentially blow-up of its length" and cites the following paper:

Succinctness of the Complement and Intersection of Regular Expressions.  Wouter Gelade and Frank Neven.  STAC 2008.

In particular, they give a concrete language that triggers the doubly exponential blowup.  See Theorem 4.1 in the paper.

That paper considers the normal representation for regexps rather than postfix, but I don't see any reason to expect that to change the bottom line.  You could work through their example and their proof if you want to be sure.


modular multiplication I was reading the Modular Multiplication page on wikipedia...and could not understand the algorithm to compute $a \cdot b \pmod{m}$.

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
  long double x;
  uint64_t c;
  int64_t r;
  if (a >= m) a %= m;
  if (b >= m) b %= m;
  x = a;
  c = x * b / m;
  r = (int64_t)(a * b - c * m) % (int64_t)m;
  return r < 0 ? r + m : r;
}

I get that:

$$ a \cdot b \pmod{m} \equiv ((a \mod{m}) \cdot (b \mod{m})) \mod{m}$$

the step I didn't get is c=x*b/mand later doing r = (int64_t)(a * b - c * m) % (int64_t)m; what is that for?

The article says:

  by employing the trick that, by hardware, floating-point
  multiplication results in the most significant bits of the product
  kept, while integer multiplication results in the least significant
  bits kept

I can't see how this is related !!!

Here's a more compact and mathematical description of what is going on.  Let $a$ and $b$ be the input, already reduced modulo $m$, so $a < m$ and $b < m$. (Code-wise, this means after the b %= m line.) We want to calculate $ab \mod m$, which is to say, setting $x=ab$, we want to find $r_x$ such that $x = q_xm + r_x$ for some $q_x$.

The Non-Overflowing Case

In the non-overflowing case, we could just calculate the modulus and be done with it. Instead, the code calculates: $$y = \left\lfloor\frac{x}{m}\right\rfloor = \left\lfloor q_x + \frac{r_x}{m}\right\rfloor = q_x + \left\lfloor\frac{r_x}{m}\right\rfloor = q_x$$
Now $x - ym = q_xm + r_x - q_xm = r_x$. I elided a concern here though. It could be that $x$ doesn't fit in the mantissa of our floating point variable. As long as $m$ fits, though, this will not be a problem as $x = ab < m^2$. We'll end up with $x' = x + e$ where $e$ is some round-off error whose magnitude is less than $m$. We proceed as before: $$y = \left\lfloor\frac{x'}{m}\right\rfloor = \left\lfloor q_x + \frac{r_x+e}{m}\right\rfloor = q_x + \left\lfloor\frac{r_x+e}{m}\right\rfloor$$
In this case, we can't eliminate the $\left\lfloor\frac{r_x+e}{m}\right\rfloor$ because, while $r_x < m$ and $e < m$, it may be the case that $r_x+e > m$ or $r_x+e < 0$, though it will certainly be (strictly) between $-m$ and $2m$, so $\left\lfloor\frac{r_x+e}{m}\right\rfloor$ is either $0$ or $\pm1$. Now $$x - ym = q_x m + r_x - q_x m - \left\lfloor\frac{r_x+e}{m}\right\rfloor m = r_x - \left\lfloor\frac{r_x+e}{m}\right\rfloor m$$
Performing the modulus operation now will get rid of that extra term, however, due to the convention C chooses, (-1)%m = -1. To get a convention where we always return a positive number, we can add $m$ to the result if negative.

The Overflowing Case

Let's assume that we are doing the integer arithmetic mod $N$, e.g. $2^{64}$, and let's assume $ab > N$ which means $m^2 > N > m$.  Now the multiplication is going to wrap. We'll write $x = ab = z + kN$ for an integer $k < m$. That means the computation a*b will give the number $z$. The floating point computation is as before assuming, again, that the $m$ fits in the mantissa (which may require 80-bit extended precision floats for larger $m$). For the modulus, define $z = q_z m + r_z$ and $kN = q_N m + r_N$ so $x = q_z m + q_N m + r_z + r_N$. As before storing $x$ as a floating point variable may produce some round-off error $|e| < m$ so again have $x' = x + e$. If we do the same calculation as before it looks like: $$\begin{align}
z - \left\lfloor\frac{x'}{m}\right\rfloor m
& = q_zm + r_z - q_z m - q_N m - \left\lfloor\frac{r_z+r_N+e}{m}\right\rfloor m \\
& = r_z - q_N m - \left\lfloor\frac{r_z+r_N+e}{m}\right\rfloor m \\
& = r_z + r_N - \left\lfloor\frac{r_z+r_N+e}{m}\right\rfloor m \\
\end{align}$$
I've pulled a rabbit out of the hat here. Here, we're doing addition mod $N$, and mod $N$ $q_N m + r_N = kN = 0$ so $q_N m = -r_N$. As before, we mod by $m$ to get $r_z + r_N = x \mod m$, and, as before, the C convention may lead to this being negative which will need correcting.

There's one potential remaining issue. $\left\lfloor\frac{r_z+r_N+e}{m}\right\rfloor$ could be $2$. This causes no problem unless $2m > N$ in which case you'd get the wrong answer. For $N = 2^{64}$ this means $m > 2^{63}$. (As an aside, if $2m = N$ it causes no issue since we'll end up with $0$.) If we configure the floating point hardware to round down so that $e \leq 0$, this case will not come up. (Though don't forget my restriction that the mantissa can hold $m$!).

Connecting this to most/least significant bits

To specifically address the part that you quoted, consider an integer, $B$, greater than 2 which we'll think of as a base, as in "base $10$".  In the usual $B=10$ case, the number $21$ is represented as $21 = 2B+1$. In a floating point representation we'd write this as $2.1\times B^1$. Now let's say we wanted to multiply two (positive) single base-$B$ digit numbers, the result would require at most two digits, say $cB+d$ where (as required by a [standard] base-$B$ representation) $0 \leq c < B$ and $0\leq d < B$. If we're restricted to only being able to store one base-$B$ digit of the result, there are two obvious choices, either $c$ or $d$.

Choosing $d$ is equivalent to working mod $B$ as $cB + d = d\mod B$, this is what happens with integer arithmetic. (Incidentally, at the assembly level, integer multiplication often does produce both of these digits.)

Floating point arithmetic, on the other hand, effectively corresponds to choosing $c$, but compensating that by incrementing the exponent. In effect, we represent the result as $c.d\times B^1$ but since we can store only one base-$B$ digit, this becomes just $c\times B^1$. (In practice, we'll consider numbers as multi-digit numbers in a small base (i.e. 2), rather than 1- or 2-digit numbers in a large base. This allows us to save some of the higher digits of $d$ if they aren't needed to store $c$, but in the worst-case scenario all of $d$ is lost. None of $c$ is lost until we start running out of room in the exponent. For the code above, this is not an issue.)

As long as $m$ can be represented faithfully in the floating point format, the expression $\left\lfloor\frac{ab}{m}\right\rfloor$ can be viewed as extracting that upper digit in base-$m$.  You can view the code and math above as the interplay between base-$N$ and base-$m$ representations of a number.

Practicalities

Based on section 5.2.4.2.2 of this draft, the C11 standard appears to only require long double to have a mantissa roughly 33 bits in length. (In particular, it appears to only specify the minimum number of decimal digits that can be faithfully represented.) In practice, most C compilers when targeting general purpose CPUs and particularly x86-family CPUs, will use IEEE754 types. In this case double will effectively have a 53-bit mantissa. x86-family CPUs support an 80-bit format with a mantissa with effectively 64-bits, and several but not all compilers will have long double indicate that when targeting x86. The range of validity of the code depends on these implementation details.


Regularity of the exact middle of words from a regular language Let $L$ be a regular language.
Is the language $L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$ regular?

I know it's very similar to the question here, but the catch is that it's not a simple substring of a word in a regular language, but rather an "exact middle" - we have to count the prefix and suffix length.

Therefore, I assume it's not regular, but I couldn't find a way to prove it. I also couldn't think of any way to modify the NFA of $L$ to accept $L_2$.

Hint: Consider some DFA for $L$. For every $n \geq 0$, let $A_n$ be the set of states $s$ such that there is some word of length $n$ which leads the DFA from the initial state to $s$. Let $B_n$ be the set of states $t$ such that there is some word of length $n$ which leads the DFA from $t$ to an accepting state. Finally, for any two states $s,t$, let $R_{s,t}$ be the (regular) set of words leading the DFA from $s$ to $t$. We have
$$ L_2 = \bigcup_{n \geq 0} \bigcup_{\substack{s \in A_n \\ t \in B_n}} R_{s,t}. $$
Since there are only finitely many possibilities for $s,t$, the union is in fact finite, and so regular.


Maximize area of light with 4 light sources on a diagram of a room Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized.
Here is a simple example diagram so the problem can be better understood:

The solution I thought was to find the spot with most light and from there find the second one and so on. But something makes me think that it may exist a configuration which is better that doesn't need to be the best from the beginning, kinda feels like a special case of the knapsack problem, if so I'd think of implementing a greedy algorithm or using genetic algorithms to give an approximation of the best places.
The problem could be viewed as a particular case of "the Art gallery problem" but instead of finding the least amount of guards, you have 4 guards and you have to put them in certain places so they can observe the most area of the gallery possible.
I'd be grateful if at least someone points me in the right direction so I can do a better research, thank you very much!

This is an optimization problem, where a function $f: \Bbb R^8 \rightarrow \Bbb R$ is defined as an area of the visibility polygon, corresponding to four points, situated inside a polygon with holes. So, your research should go in two directions:

Global optimization - a branch of numerical analysis, that deals with various iterative algorithms, able to find an argument of the optimized function, giving its minimum or maximum value over all the function domain. Sometimes the global optimization problem is solved as a sequence of local optimizations (with random starting points), however in general case there are no guarantee that the optimal solution will be found by this method. Please see this paper, where authors apply the Gradient descent method to maximize the area of the region, visible to the observer in a simple polygon (without holes).

Visibility polygon for a point $p$ in the plane configuration with possible boundary and obstacles is the polygonal region $V(p)$ of all points of the plane visible from the p. You'll need to compute visibility polygons many times for different points, so it makes sense to pre-process the original polygon (together with its holes) to make this computation faster. Please see this paper, where authors do exactly that - their approach needs $O(n^3log(n))$ pre-processing time, and it allows to compute the visibility polygon with $k$ vertices in $O((1+min(h,k))log(n)+k)$ time, where $h$ is the number of holes. The visibility polygon for four points will be a union of four visibility polygons (and this union can have holes) - so you'll need to compute this union. Please see Boolean operation on polygons as a starting point for your research as well.

Optimization problems on real numbers are intrinsically inexact and their solutions are approximations - the question is how close your solution should be to the optimal one. The gradient descent method might be enough in your case, where the bounding polygon is simply a rectangle, and holes also have simple shape.


Difference Between Tree Automata and Tree Transducers Wondering what the differences are between Tree Automata and Tree Transducers.

Wikipedia says:

  Tree transducers extend tree automata in the same way that word transducers extend word automata.

And about word transducers it says:

  A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton that maps between two sets of symbols.[1] An FST is more general than a finite-state automaton (FSA). An FSA defines a formal language by defining a set of accepted strings while an FST defines relations between sets of strings.

But I don't understand what the implications are and what the differences really are, even though there is the extra tape. Not sure about the tapes in the Tree Transducers.

All I see so far is tree transducers have the extra "output alphabet" for constructing a new tree (which you plug the state into):

$$ {\displaystyle q(f(x_{1},\dots ,x_{n}))\to u}$$

For instance:

$${\displaystyle q(f(x_{1},\dots ,x_{3}))\to g(a,q'(x_{1}),h(q''(x_{3})))}$$

but the automata have pretty much the same signature, just using the input alphabet only:

$$q(f(x_1,...,x_n)) → f(q_1(x_1),...,q_n(x_n))$$

A tree automaton accepts trees. A tree transducer maps trees into trees. Although string automata generally work natural from left to right, there is no such natural choice for tree automata: they can process the tree from top to bottom, from bottom to top, and there are even models that walk over trees (like two-way string automata walk over the input).

As far as I understand, you example has the following meaning. Your automaton is working top to bottom.

$q(f(x1,\dots ,x3))\to g(a,q′(x1),h(q′′(x3)))$

To the right of the rule we read $q(f(x1,\dots ,x3))$. This means the input is a tree that has a root labelled with symbol $f$. This root has three children represented by the variables $x1,\dots ,x3$. The transducer is at state $q$ when it visits the root labelled $f$.

To the right we see the tree that is constructed when the rule is applied. The tree has a root labelled $g$ and three children. The first child is a leaf labelled by $a$. The next two subtrees are computed by two copies of the original transducer. The second child (of the output) $q′(x1)$ means a copy of the transducer starts at the first child "$x_1$" of the input tree in state $q'$, and the third child $h(q′′(x3))$ indicates a tree with node labelled $h$ which has a single child computed by another copy of the transducer started at the third child "$x_3$" of the input in state $q''$.


Can parameters be contra- or covariant in Python? I've just now studied about covariance and contravariance in static languages (more specifically C#). This concept is rather clear to me, however I'm in doubt on how this applies to dynamic languages like Python.

Since Python is duck typed (or structural typed) it seems to me that there is not even a notion of variance and covariance in this language?

If I'm not mistaking, things like contravariance and covariance are checked at compile-time in a language like C#, this is possible because a variable has a type, and the value it is bound to has a type as well and these have to match or be co(ntra)- or invariant. However, since there is no notion of typing at compile-time with a language like Python I don't know how to apply this concept.

Any thoughts?

My thoughts: The concept of covariance means that whenever we expect a type of X, any subclass of X will do as well. So, in Python this doesn't come up, because there is no type check to do this. The only check that happens is wether or not the object has the necessary implementations by means of methods and attributes.

In C# for example where we have a method:

void DoStuff(Person p)
{
    p.Dance();
};

We could very well call this method with an instance of a Student (if this is a subclass of Person).

Now, in Python, we could very well pass in a Bird object that would not be related to Person in any way in the inheritance hierarchy(except it would also inherit from object), as long as this bird implements Dance().

This is why I'm asking about this concept. From what I understand Python is covariant and contravariant in.. well, everything?

Here are some general thoughts on how contra- and co-variance issues affect programming in dynamically typed languages.

Covariance: If B is a subtype of B' then functions A $\rightarrow$ B form a subtype of A $\rightarrow$ B'.

Contrvariance: If A is a subtype of A' then functions A' $\rightarrow$ B form a subtype of A $\rightarrow$ B.

For example, if Auto is a subtype of Vehicle, then the contravariance rule says that a function that takes a Vehicle argument can be regarded as a function taking an Auto argument (because the Auto can be regarded as a Vehicle).  However, a function taking an Auto argument cannot be treated as a function that takes a Vehicle argument.  If you do, then sooner or later, you might pass it a non-Auto argument, say a Bicycle, and you would get a run-time error.

Whether the language is statically typed or dynamically typed makes little difference to the logic you use to design programs.  If the language is statically typed, the type checker would complain about the design flaws in your program that show up as type-mismatches.  If it is dynamically typed, you are likely to get a run-time type error such as "message not understood".  That is if you are lucky.  If you are unlucky, the problem would go unnoticed during testing, and the program would crash in the hands of the end-user.


Understanding B tree key deletion step from CLRS algorithm CLRS explains B tree key deletion as follows:

  If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$.
  If the key $k$ is in node $x$ and $x$ is an internal node, do the following:

  a. If the child $y$ that precedes $k$ in node $x$ has at least $t$ keys, then find the predecessor $k'$ of $k$ in the subtree rooted at $y$. Recursively delete $k'$, and replace $k$ by $k'$ in x. (We can find $k'$ and delete it in a single downward pass.)

  b. If $y$ has fewer than $t$ keys, then, symmetrically, examine the child $z$ that follows $k$ in node $x$. If $z$ has at least $t$ keys, then find the successor $k'$ of $k$ in the subtree rooted at $z$. Recursively delete $k'$, and replace $k$ by $k'$in $x$. (We can find $k'$ and delete it in a single downward pass.)

  c. Otherwise, if both $y$ and $z$ have only $t-1$ keys, merge $k$ and all of $z$ into $y$, so that $x$ loses both $k$ and the pointer to $z$, and $y$ now contains $2t-1$ keys. Then free $z$ and recursively delete $k$ from $y$.
  If the key $k$ is not present in internal node $x$, determine the root $x.c_i$ of the appropriate subtree that must contain $k$, if $k$ is in the tree at all. If $x.c_i$ has only $t-1$ keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least $t$ keys. Then finish by recursing on the appropriate child of $x$.

  a. If $x.c_i$ has only $t - 1$ keys but has an immediate sibling with at least $t$ keys, give $x.c_i$ an extra key by moving a key from $x$ down into $x.c_i$ , moving a key from $x.c_i$’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into $x.c_i$.

  b. If $x.c_i$ and both of $x.c_i$ ’s immediate siblings have $t - 1$ keys, merge $x.c_i$ with one sibling, which involves moving a key from $x$ down into the new merged node to become the median key for that node.

I have a doubt in step 2c. In this step, $y$ is a node containing the predecessor of the key and $z$ is a node containing the successor of the key, both of which has minimum number of keys ($t-1$) and hence authors say we need to merge both of nodes. The authors give following example:

  First tree is before deleting $G$, second is after deleting $G$, which utilized step 2c.

  Here, $y=[D,E]$ is a predecessor node of $G$, with predecessor $E$ and $z=[J,K]$ is a successor node of $G$, with successor $J$. So we merge both $[D,E]$ and $[J,K]$ forming $[D,E,J,K]$.

My doubt is do we always end up successor and predecessor node if they contain minimum number of nodes ($t-1$)? This is what authors must mean to say when they say "merge $k$ and all of $z$ into $y$" in step 2c. But I feel they might not be the predecessor and successor nodes, they are just immediate next children of key $k$, as can be seen in this example I tried out:

Here we have not merged nodes of predecessor (node $[N,O]$) and successor (node $[R,S]$), but have merged immediate children of $Q$, i.e. node $[C,G,L]$ and node $[T,X]$.

So am I right with "we need to merge immediate next children of key $k$ but not predecessor and successor node"? If yes, is book have mistake? Or book does indeed tries to say the same and I am misinterpreting? Or I got it all wrong? Or am unnecessarily overthinking?

You are probably overthinking it by thinking in terms of predecessor/successor nodes.

The rule just says, if the key to be deleted has both children at least capacity, you cannot take a predecessor(or successor) from its left(or right) child without violating the B-Tree property. So, we decide that we will merge it with both its children and push the decision to delete one level downward. That's it.

An intermediate step in 2c. would be where G is pushed downward and merged with [DE] and [JK] to give

[[AB] , [C], [DEGJK], [L], [NO]]

Now we can apply the algorithm to this node [DEGJK], and since it's a leaf node, step 1 will apply here and we can simply delete G from it.


How to find the shortest path from some vertex in set $S$ to set $S'$ If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? That is, we are looking for a shortest path among all $S$-$S'$ paths. We can also assume all edge weights are positive.

Here is how I have approached this problem so far:

I already have the distance matrix information $(d)$ for graph $G$ which was calculated by applying the Floyd-Warshall algorithm in a previous operation.

I then iterate over all vertices in $S$ for each vertex in $S'$ and find the pair $(s_1,s_2)$ with the smallest value in matrix $d$.

Dijkstra's algorithm is then used to calculate the shortest path between $s_1$ and $s_2$, so connecting vertex sets $S$ and $S'$.

Is there a more efficient way of achieving this same outcome?

If all edge lengths are non-negative, then this can be solved in $O(|E| \lg |V|)$ time using a single invocation of Dijkstra's algorithm.

We're going to modify the graph slightly by adding a new vertex $s$.  Also, add an edge of length 0 from $s$ to each vertex in $S$.

Next, run Dijkstra's algorithm, starting from the source vertex $s$.  Dijkstra's algorithm will compute for you the distance from $s$ to every other vertex $v$, i.e., it will compute $d(s,v)$ for all $v \in V$.  Note that $d(s,v)$ will be exactly the length of the shortest path from some vertex in $S$ to the vertex $v$.

Finally, compute $\min \{ d(s,v) : v \in S' \}$.  This will be the length of the shortest path from some vertex in $S$ to some vertex in $S'$.  That's your answer.

There's no need to run Floyd-Warshall.

If you can have negative edges, then it can be done in $O(|V| \cdot |E|)$ time.  Simply replace Dijkstra's algorithm with the Bellman-Ford algorithm.


Can a 3 Color DFS be used to identify cycles (not just detect them)? Can a 3 color DFS be used to identify all cycles in a directed graph not just detect them?

In other words if I have a directed graph with multiple cycles, can I run a function on them such that the function returns the list of nodes that compose each simple directed cycle in the graph and not just a boolean true or false? Most answers online show pseudocode for detection and not identification (ie functions which return boolean values instead of node lists). You can assume that the graphs I'm referring to are mostly tree like in structure and aren't deeper than 5 nodes or so.

So for example, for this graph:

The list would be [[a,b,e], [f,g], [c,d], [d,h]]

With white, grey, black DFS a cycle is found when a node already colored grey is visited a second time through a different edge. What I'm struggling to wrap my head around is when this happens, how do we back track to identify all of the nodes involved in this detected cycle without increasing complexity or running DFS a second time. In the example below, if we do a DFS (exploring right edges first) starting at A, the stack will look like this [A,B,C,E,D,B] and the cycle will be detected when B is visited a second time. Given this stack how do we deduce that C D and B only are part of the cycle and not E or A?

I am aware that there are plenty of algorithms other than DFS that can do this (such as Johnson's algorithm or Tarjan's with a twist) I just want something simple to implement.

The moment you find a grey node, you have the edge that closes the cycle in hand. All other edges are part of the DFS tree. That is, store the "cycle-closing" edge and obtain the rest afterwards.

That is, assuming that those are the cycles you are interested in. Other cycles (such that contain more than one non-DFS-tree edge) are more complicated, but I don't think those are easy to cover. A directed graph may have super-exponentially many cycles, so you can't expect to list them all with a simple, linear-time traversal.


Binary Tree Multithreaded Time Complexity Let's say you want to get the value of all nodes in a binary tree (order doesn't really matter). If in each thread, you spawn two more threads to deal with the left subtree and the right subtree, then wouldn't the big O time complexity be O(log n). I was under the impression that you could never traverse an entire tree in less than O(n) since you'll have to search each node. However, it seems like by using multithreading, one can reduce the amount of nodes to be searched in half at each node.

Would the space complexity still be the same O(n)? Also, if the the time complexity really is O(log n), are there any optimizations that could possible make it a bit faster?

[..], then wouldn't the big $\mathcal{O}$ time complexity be $\mathcal{O}(\log n)$

People often forget that big-$\mathcal{O}$ notation only is meaningful in a certain context, here this becomes obvious:

You are probably used to count some set of instructions (like comparing, adding etc.) as one unit - called unit cost model - each instruction happening sequentially. In that model you're right, traversal and outputting every vertex of a binary tree is $\Omega(n)$ (ie. you cannot do better than linear).

However when talking about parallel algorithms and their complexity things change, first of all you will need to specify $p$ how many processors you use1. You will also need to specify  whether multiple processors have exclusive or concurrent access for reading/writing.

You were probably talking about the CREW (concurrent read, exclusive write) PRAM and assumed $p = n$ in your question:

  you could never traverse an entire tree in less than $\mathcal{O}(n)$

In total all the processors will have looked at $\mathcal{O}(n)$ vertices in the binary tree, this does not change and is called the work.

You were right that the time complexity (refered to as depth) is $\mathcal{O}(\log n)$ for that algorithm.

To illustrate my point even more, assume that the binary tree is given as an array with a certain order and still using $n$ processors with a CREW machine. Now, every (numbered) machine can simply lookup the value at its position in that array.

This algorithm has still $\mathcal{O}(n)$ work, but $\mathcal{O}(1)$ depth.

Conclusion

Always be aware of the context (eg. what model, what input format) since this has a great influence on the complexity. Once you introduce parallelism things become different and it's important to be precise about what assumption you make and how many processors an algorithm uses.

1: From now on I will assume a parallel random-access machine since it's very simple but still useful.


Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input:

[10, 14, 18, 3, 21, 25, 27]
i = 2
j = 4

The following array is returned:

[25, 21, 18]

18 is the 4th largest element in the array and 25 is the 2nd smallest element in an array. I've done a problem where you retrieve a list of the K largest elements in an array: in such a problem, the solution is pretty trivial (using a fixed-size minimum heap of size K to keep track of the K largest elements). In this case however, a heap seems out of reach to use because the minimum heap can only remove the smallest element from the heap (removing the kth smallest element within the heap seems really inefficient).

I could do QuickSelect (j - i) times to get all the elements, but that means doing a linear O(n) walkthrough (j - i) times, which yields a total time complexity of O((j-i) * n), but I was thinking about if it's possible to quicken the algorithm's time complexity to just O(n). Is there an O(n) algorithm to solve this problem?

I could do QuickSelect (j - i) times to get all the elements

Overkill. Two calls to QuickSelect and one linear pass are sufficient.


mapping reductions from R to RE Let $L_1$ be some language in $R$. Let $L_2$ be some language in $RE$. Is it necessarily that
$L_1 \leq_m L_2$ ?
I know that for non trivial $L_1$,$L_1$ in $R$ it is right to say that $L_1 \leq_m L_2$.
But I can't prove the first case.
and another question:
I am almost certain that the following is true, though I have not found any reference to it on the Internet:
The identity function is a mapping reduction from $\emptyset$ to $\emptyset$.

If $L_2 \neq \Sigma^*$ and $L_2 \neq \emptyset$ then $L_1 \in R$ and $L_2 \in RE$ implies $L_1 \le_m L_2$.
Let $T$ be a Turing machine that decides $L_1$. Let $a,b \in \Sigma^*$ such that $a \in L_2$ and $b \not\in L_2$.
For $x \in \Sigma^*$, define $\phi(x) =
\begin{cases}
a & \text{ if $T(x)$ accepts }\\
b & \text{ if $T(x)$ rejects }
\end{cases}$.
It is easy to check that $\phi$ is a mapping reduction from $L_1$ to $L_2$.
If $L_2 = \Sigma^*$ then $L_1 \in R$ and $L_2 \in RE$ does not imply $L_1 \le_m L_2$.
This can be seen, e.g., by choosing $L_1 = \emptyset$.
If $L_2 = \emptyset$ then $L_1 \in R$ and $L_2 \in RE$ does not imply $L_1 \le_m L_2$.
This can be seen, e.g., by choosing $L_1 = \Sigma^*$.