Which method is preferred for storing large geometric objects in a quadtree? When placing geometric objects in a quadtree (or octree), you can place objects that are larger than a single node in a few ways:

Placing the object's reference in every leaf for which it is contained
Placing the object's reference in the deepest node for which it is fully contained
Both #1 and #2

For example:

In this image, you could either place the circle in all four of the leaf nodes (method #1) or in just the root node (method #2) or both (method #3).

For the purposes of querying the quadtree, which method is more commonplace and why?

Assuming you are storing a reference, not the object itself, it may make sense to do this differently depending on your application.

For instance, if you were computing collisions with this (solid) circle and the collision was occurring in the lower left hand corner, it'd be easier if you had access to all geometry in that leaf directly from that leaf (method #3) (without having to traverse the tree upward and determine inherited geometry). But, say you were just using quadtrees for drawing geometry, you'd want to use method #1, because it only makes sense to draw something in the node for which it is fully contained (it would be more difficult to figure out which portion to draw for each leaf node and where).

As for what is more commonplace, my only experience with quadtrees is with writing an n-body simulation where the geometric objects were really just points that had no area, so I can't definitively answer that.


Analysis of updating vertex and one example? I see the following image on google:

And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should used sorted array or binary heap for implementation? non of others get us this Amortized Cost?

In Dijkstra's algorithm there are $|E|$ update operations and $|V|$ remove_min operations.
To implement the algorithm, we can employ different types of data-structures. Since you are looking for the best update cost per vertex, you can employ the Fibonacci heap or Hash map implementation since they give you the minimum update cost (as per the table mentioned in your question). Now, suppose you employ Fibonacci heap. Then, the total amortized update cost for Dijkstra's algorithm would be $|E| \cdot O(1) = O(|E|)$. Therefore, the amortized update cost per vertex is: $O(|E|/|V|)$.

These are the three main implementations of Dijkstra's algorithm:

Array Implementation (a.k.a. Hash Map as per your table): Update $O(1)$ and Remove_Min $O(|V|)$

Binary Heap Implementation (a.k.a. Hybrid Binary Heap as per your table): Update $O(\log |V|)$ and Remove_Min $O(\log |V| )$

Fibonacci Heap Implementation: Update Cost $O(1)$ and Remove_Min Cost $O(\log |V|)$

Note that Fibonacci Heap provides the best update cost and the best remove_min cost among these three options. Therefore, it is the best of both worlds. Hence, it is best for Dijkstra's algorithm and you can remember this implementation only.


Probability of reaching a state in asymmetric random walk Consider the following random walk:

Namely, if $S_i$ is the state at time $i$, then $\Pr(S_{i+1}=1|S_i=0)=1$, and for every $s>0$ we have
$$S_{i+1}|S_i=s=
\begin{cases}
s+1 & \text{w.p. }1-p\\
s-1 & \text{w.p. }p
\end{cases}.
$$
In my application, $p>\frac{1}{2}$. I'm interested in two quantities, $\Pr(S_T > H)$ and $\mathbb E(S_T)$. My intuition is that $\Pr(S_T > C \ln T)\leq \frac{1}{T^2}$ for some global constant $C$, and that $\mathbb E(S_T)=O(1)$. However, I couldn't show it (yet).
Any ideas?

Here are some trivial claims. First, $\Pr(S_T > H) \leq \exp(-\frac{H^2}{T})$ due to Azuma's inequality, but that doesn't use the value $p$ nor the fact that $p> \frac{1}{2}$. Second, $\mathbb E(S_T) \leq O(\sqrt{T})$ since $S_t$ is stochastically dominated by a symmetric random walk, for which the expected place at time $T$ is $O(\sqrt{T})$.
The stationary distribution is easy to find, being $\pi_0=1-\frac{1}{2p}$ and  $\pi_i = \frac{\pi_0}{p} \left(\frac{1-p}{p}\right)^{i-1}$, but I'm not sure how to use it.

Suppose that $S_T > C\ln T$. Let $T_0-1$ be the last time that the random walk reached the origin. Thus if we run an unconstrained biased random walk starting at position $1$ at time $T_0$, we reach beyond $C\ln T$ at time $T$. This can only happen if $T-T_0 \geq C\ln T$.
The probability that an unconstrained biased random walk starting at position $x$ ends up to the right of $x$ after $L$ steps is exponentially small in $L$, by Hoeffding's inequality. In your case, $L \geq C\ln T$, and so this probability is polynomially small in $T$. Taking a union bound over all possible values of $T_0$ (at most $T$ of them), you can choose $C$ so that the error probability is at most $\frac{1}{T^d}$ for $d$ of your choice.
(More formally, choose the $\pm 1$ steps $\xi_1,\ldots\xi_T$ of your walk ahead of time. You start at some fixed $S_0$, which here is implicitly assumed to be $S_0 = 1$, and then $S_{n+1} = |S_n + \xi_{n+1}|$. If $S_T > C\ln T$ then $S_{T_0} + \xi_{T_0+1} + \cdots + \xi_T \geq C\ln T$, by definition of $T_0$. We bound the probability that this happens for fixed $T_0$ and take a union bound.)

As for $\mathbb{E}(S_T)$, since you have a stationary distribution, then your chain is positive recurrent (see Chapter 21 of Markov Chains and Mixing Times). Your chain is not ergodic due to a parity issue, so let's consider the square of your chain (moving two steps at once). The square decomposes into two separate chains. The one of the even integers looks as follows:

At $0$, stay at $0$ with probability $p$, and transition to $2$ with probability $1-p$.
At $2n>0$, transition to $2(n-1)$ with probability $p^2$, stay at $2n$ with probability $2p(1-p)$, and transition to $2(n+1)$ with probability $(1-p)^2$.

The one on the odd integers looks as follows:

At $1$, stay at $1$ with probability $p(2-p)$, and transition to $3$ with probability $(1-p)^2$.
At $2n+1$, transition to $2(n-1)+1$ with probability $p^2$, stay at $2n+1$ with probability $2p(1-p)$, and transition to $2(n+1)+1$ with probability $(1-p)^2$.

Let's focus on the case of even integers. Let $f_{2n} = cn$. Using $p(i,j)$ for the probability to transition from $i$ to $j$,
\begin{align}
&p(0,0) e^{f_0 - f_0} + p(0,2) e^{f_2 - f_0} = p + (1-p) e^{-c}, \\
&p(2n,2n-2) e^{f_{2n-2} - f_{2n}} + p(2n,2n) e^{f_{2n} - f_{2n}} + p(2n,2n+2) e^{f_{2n+2} - f_{2n}} = p^2 e^{-c} + 2p(1-p) + (1-p)^2 e^c.
\end{align}
For any $c > 1$, the first line is strictly less than 1. For $c = 1+\epsilon$, the second line is
$$
p^2 (1 - \epsilon) + 2p(1-p) + (1-p)^2 (1 + \epsilon) + O(\epsilon^2),
$$
which is less than 1 for any small $\epsilon>0$ since $p^2 > (1-p)^2$.
We have thus verified Popov's conditions for geometric ergodicity (see for example Isaacson), and we conclude1 that there exists $\beta < 1$ such that
$$
 \left|\Pr[S_{2T} = 2n \mid S_0 = 0] - \pi^e_{2n}\right| = O(e^{f_0-f_{2n}}\beta^T) = O(\beta^T),
$$
where $\pi^e$ is the stationary distribution of the even component of the squared chain, given by $\pi^e_{2n} = 2\pi_{2n}$. Denoting the corresponding expectation by $E^e = \mathbb{E}(\pi^e)$, we conclude that
$$
 |\mathbb{E}(S_{2T} \mid S_0 = 0) - E^e| = O(\beta^T).
$$
Similarly,
$$
 |\mathbb{E}(S_{2T+1} \mid S_0 = 0) - E^o| = O(\beta^T).
$$
We obtain similar results for any other fixed starting point.
1This equation appears in Popov's paper but not in Isaacson's.


How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time To go with $O(n)$, we can use the linear sieve according to that $\mu(n)$ is multiplicative. But it seems that we don't have to work each $\mu(n)$ out and accumulate them together, because I only want to get $\sum_{i=1}^n \mu^2(i)$.

I am interested that is there any solutions that are faster than $O(n)$ to work $\sum_{i=1}^n \mu^2(i)$ out.

$\mu^2(i)$ is 1 if $i$ is square-free, or 0 otherwise.  Therefore, your question is equivalent to asking how to count the number of square-free numbers in the range $1..n$.  That has been studied before; see, e.g.,

Counting Square-Free Numbers, Jakub Pawlewicz, arxiv 1107.4890.

That paper claims it can be computed in $\tilde{O}(n^{0.4})$ time (ignoring polylogarithmic factors).


Kruskal's and Prim's algorithm Does Kruskal's and Prim's algorithm work on directed graphs? I want the two algorithms to find a minimum spanning tree. For further enlightenment, I would like to know what other problems Kruskal's and Prim's can solve. So far, I only know they can solve minimum spanning trees. If it turns out there are an infinite number of problems Kruskal's and Prim's can solve, then no need to list all of them. I am learning this by myself and so far I only know one problem the two algorithms can solve.

I think that Prim's will not work because it is possible to have a node that points outwards to other nodes. If this central node is not chosen, then Prim's will be unable to give the MST including all the children.

I wonder if Kruskal's works. . . My counter example is a central node where all the children of the central node point to this central node. Running Kruskal's algorithm, we would get an MST that is not a shortest path, since we do not have path.

By definition MST or Minimal spanning tree is defined on undirected graph only!

But if you are really want to (and I wander why) You can "make" Kruskal's algorithm work on it ,but you have to make sure you are ignoring loops because otherwise if you got a loop with small weight the algorithm will count it on the "MST" (because it isn't really MST).

Regarding to Prim's algorithm I can't see a way you cane make this work on directed graph.

I don't know other uses of Kruskal's and Prim's and I don't believe there are. Usually you make a slight changes on the algorithm in order to make them do something slight different.


How to convert a context free grammar (could generate regular language) to a right-linear grammar Consider the context free grammar:

$$S \rightarrow aSb \mid aSa \mid bSa \mid bSb \mid \varepsilon$$

It could generate regular language, which means it can be converted to a right linear grammar. Is there a general rule to convert CFG into a RLG? If there is no general rule, could you please show me how to convert this CFG to a RLG?

Assuming you want your general method to be computable, the answer is no. When you consider a CFG that generates a regular language and convert it into a right-linear grammar, the size-increase is not bounded by any computable (or "recursive") function (first shown by Meyer and Fischer in this paper; also, if you can access it, this paper by Kutrib is a nice survey on the general area of non-recursive tradeoffs).

If a (computable) general conversion method existed, you could use it to construct a computable bound on the blowup between CFGs and right-linear grammars, which would contradict the non-existence of such a bound. Thus, knowing that your grammar generates a regular language does not help you at all.


Sequence to explore the complexity of the NP problem Let $X$ be some problem known to be in $NP$. What is the natural next step in exploring the complexity of the problem? Is it trying to prove whether it is in $P$ or try to prove it is $NP$-Hard? Taking the example of the Graph-isomorphism problem it seems to me that after discovering that problem is in $NP$. It is not easy to decide what to do next. Some people suggest me to prove it into $NP \cap CoNP$.

Question : What is worth to try if it is only known that problem is in $NP$? Is there any sequence (like first $NP$, $NP$-Hard, ....) to explore the complexity of the problem?

So you have found out $X \in \mathbf{NP}$. Unfortunately, as Juho hints at in their answer, there is no "list" you can systematically go over to try and investigate $X$ further. This is mainly because separation results in complexity theory are (yet) few and far between, so most of the things you may try will not explicitly fail; you'll only be unsuccessful. For example, if you try to show $X \in \mathbf{P}$ you might succeed, but if it turns out to be incorrect it is very unlikely you will be able to prove it (since then $\mathbf{P} \neq \mathbf{NP}$).

This lack of "feedback" means you should tackle $X$ from different perspectives, and it is only experience (and a good deal of luck!) which will give you a "hunch" as to where the most promising one is. The following are a few options you might consider, as well as their implications if you manage to prove or disprove them (if any). Note I am only considering structural complexity theory here (which seems to be what you are interested in), but by all means this is what the entirety of complexity theory is about. Depending on the structure of $X$, it is also possible to consider $X$ from a parameterized complexity point of view, or try to find subexponential algorithms for it (see also number 4 below), and so forth and so on.

$X$ is $\mathbf{NP}$-complete

Prove: This is basically the end of the line for investigating $X$. It is also not a very surprising result since the list of $\mathbf{NP}$-complete problems is huge (and it already was when Richard Karp started to compile this list).

Disprove: Congratulations! You have proved $\mathbf{P} \neq \mathbf{NP}$.
$X \in \mathbf{P}$

Prove: This is the second most likely outcome and even more unsurprising than the former.

Disprove: Congratulations! You have proved $\mathbf{P} \neq \mathbf{NP}$.
$X \in \mathbf{coNP}$

Prove: Then $X$ is in $\mathbf{NP} \cap \mathbf{coNP}$ (which, for instance, includes factoring). Reconsider $X \in \mathbf{P}$.

Disprove: Congratulations! You have proved $\mathbf{NP} \neq \mathbf{coNP}$.
$X \in \mathbf{GI}$ (the graph isomorphism class)

Prove: Then $X$ admits a quasipolynomial-time algorithm (and is unlikely to be $\mathbf{NP}$-complete). Reconsider $X \in \mathbf{P}$.

Disprove: Congratulations! You have proved $\mathbf{P} \subseteq \mathbf{GI} \neq \mathbf{NP}$
$X \in \mathbf{BPP}$

Prove: Since it is widely suspected that $\mathbf{BPP} = \mathbf{P}$, this is only interesting if $X \in \mathbf{P}$ is not obvious. Consider also $X \in \mathbf{RP}$ or even $X \in \mathbf{ZPP}$.

Disprove: Congratulations! You have proved $\mathbf{NP} \neq \mathbf{BPP}$ (and quite likely also $\mathbf{P} \neq \mathbf{NP}$).

And the list goes on and on. As you can see, disproving any of these options leads to separation results, all of which would be major breakthroughs and, thus, unlikely to be proven simply by considering a random problem $X \in \mathbf{NP}$. This means you cannot expect to go through this list from head to tail making ticks and crosses as you go; you have to "guess" which of the options (if any!) is more likely and (with some luck) you'll be able to prove it.


Iterative binary search analysis I'm a little bit confused about the analysis of binary search.
In almost every paper, the writer assumes that the array size $n$ is always $2^k$.
Well I truly understand that the time complexity becomes $\log(n)$ (worst case) under this assumption. But what if $n \neq 2^k$?

For example if $n=24$, then we have
5 iterations for 24
4 i. for 12
3 i. for 6
2 i. for 3
1 i. for 1

So how do we get the result $k=\log n$ in this example (I mean of course every similar example whereby $n\neq2^k$)?

$n=2^k$ is a simplifying assumption that ensures binary search "goes through" properly. If the array has a length that is not a power of two, you have to break ties when choosing middle elements, "halves" are not equally large and not all decisions lead to the same number of steps.

The worst-case number of steps on an array of size $n$ can certainly bounded from above by the maximum number of steps on an array of size $2^k$, $n \leq 2^k$. If we choose $k$ as small as possible, we obtain $k = \lceil \log n \rceil$.

With $\lceil \log n \rceil \leq \log(n) + 1$ we see that the worst-case number of steps is indeed asymptotically equal to $\log n$.


Problems for which a small change in the statement causes a big change in time complexity I know that there are several problems for which a small change in the problem statement would result in a big change in its (time) complexity, or even in its computability.

An example: The Hamiltonian path problem defined as

  Given a graph, determine whether a path that visits each vertex exactly once exists or not.

is NP-Complete while the Eulerian path problem defined as

  Given a graph, determine whether a trail that visits every edge exactly once exists or not.

is solvable in linear time with respect to the number of edges and nodes of the graph.

Another example is 2-SAT (polynomial complexity) vs K-SAT (NP-complete) although someone could argue that 2-SAT is just a specific case of K-SAT.

What do you call this kind of problems --if they even have a name? Can someone provide a list of other examples or some references?

Given a graph, does it have a cycle of length $3$ ($4$)? Four-cycles there is an easy algorithm that requires $O(n^2)$ time. The best known algorithm for triangle detection is related to matrix multiplication and has complexity $O(n^\omega)$ where $\omega$ is the matrix multiplication exponent. It is an open problem to determine whether $\omega=2$.
Given a graph, decide if its vertices can be colored with 2 (3) colors. Two colors: it is equivalent to testing the graph for bipartiteness, Three colors: NP-Complete.
Given a graph, decide if its edges be colored with 2 (3) colors.
Two colors: trivial (color an first edge arbitrarily, follow all implied edges, repeat). Three colors: NP-Complete.
Given a system of Diophantine equations, does it a admit a (non-negative) solution? Solvable in polynomial time if variables can be negative, NP-Complete otherwise.
Given a graph and two vertices $s$ and $t$, what is the length of the shortest (longest) path between $s$ and $t$? Shortest path: essentially a BFS. Longest path: NP-hard.
A lot of graph problems that are hard in general, are easy on trees (vertex cover, independent set, dominating set, ...). See Kleinberg & Tardos, perfect graphs, and notice that a minimum dominating set on a tree can be found by greedily selecting a parent $v$ of a leaf, deleting $v$ and its neighbors, and repeating.
Given a directed graph, can you partition its edges into paths of length 2 (1)? For paths of length 1 the problem is trivial. For length 2 there it is a generalization of 3-dimensional-matching.
Given a set of numbers, can it be partitioned into groups of 2 (3) elements so that all groups have the same sum? For groups of two elements it is trivial (the match of an element is completely determined by the element itself). For groups of $3$ it is the 3-partition problem.
Given a NFA, does it accept (reject) at least one word? Accept: this boils down to a connectivity check between the initial state and the final states. Reject: PSPACE-Complete (search Universality problem).
Given a graph $G$, two vertices $s$ and $t$, and $c \in \mathbb{N}$. Does $G$ contain $4$ ($5$) edge disjoint paths of length at most $c$? For 4 paths the problem is solvable in polynomial time, for 5 paths it is NP-hard.
Given an edge-weighted graph $G$ and two vertices $s$ and $t$, what is the minimum (maximum) weight of a $s$-$t$ cut in $G$? See minimum-cut (polynomial) and maximum-cut (NP-hard).
Given a set of linear constraints, is there at least one (integral) point in their intersection? Solvable in polynomial-time if variables are not restricted to be integers, otherwise NP-hard.


How to calculate the runtime of a following code? Could someone explain how to calculate the Big O notation for a runtime of a snippet of a code?
for (int i=0; i<list.length; i++) {
    for (int j=0; j<list.length; j++) {
        for (int k=0; k<list.length; k++) {
            if (k%2==0) {
               list[i] += list[j];
            } else {
               list[i] += list[k];
            }
       }
   }
}

From my understanding, I'm thinking it's something like O(n^3) because the statement is executive n times for every i?

If I understand correctly, that you denote $n$=list.length and are calculating amount of   "list[i] +=" operation. Then of course, as it is triple loop, then for $n$ times  fixed "i" from first loop you take $n$ times "j" from second loop and $n$ times "k" from most inner, third, loop. So operation "list[i] +=" will be fulfilled exactly $n^3$ times. Now knowing, that $n^3 \in O(n^3)$ you can state that complexity for whole snippet is $O(n^3)$ .


Coloring grid with flexible number of colors and flexible number of occurrence per color Suppose we have an $m \times n$ grid or table, with $m$ being the number of rows and $n$ being the number of columns. The user can select the number of colors (let's say $k$ colors) and how often each color is allowed to occur (i.e., we have a vector of numbers of occurrence of the colors $(i_1, i_2, \dots, i_k)$). The only constraints that apply are pretty obvious: $\sum_j i_j = nm$ and $i_j \leq ⌈nm/2⌉$ for $1 \leq j \leq k$.

I would like to color the vertices/cells in a way that no two adjacent vertices/cells have the same color (adjacence is defined as up, down, left or right; i.e., it is allowed to have the same color on a cell that is on the diagonal of the current cell). If possible, there should be no strict segregation of colors along the field, i.e., each color should be distributed over the field as "randomly" as possible.

So far I've implemented a brute force algorithm based on random selection of the coordinates of the colors. However, this approach is too inefficient.

One thought of mine was to first randomly arrange the colors in a linear list (i.e., as if we would have a $1 \times (nm)$ grid), then to take out the first $n$ elements and re-arrange them into the first row, randomly shuffling the colors until the condition is fulfilled. Then taking the next $n$ elements, arranging them as a second row and shuffling the elements until all conditions are fulfilled, and so on. This way, I would still have a random component, but at each step I would only need to deal with one row, and I might realise at an earlier time point that I got stuck and need to restart. However, I'm not sure whether this approach would really improve the performance.

Is there a better way to achieve the result? And is there a way to early determine whether a valid solution for a given input exists at all?

You're asking for a $k$-coloring of a grid graph (with some extra constraints on how many times each color is used).

One approach is to encode this as an instance of SAT or integer linear programming (ILP), and let a SAT/ILP solver look for a solution for you.  For instance, you could introduce zero-or-one variables $x_{r,s,t}$, where $x_{r,s,t}=1$ if row $r$ column $s$ has color $t$, and then write down constraints to capture that this is a valid coloring (i.e., $x_{r,s,t} + x_{r',s',t} \le 1$ when $(r,s)$ and $(r',s')$ are adjacent, $\sum_t x_{r,s,t} = 1$, and $\sum_{r,s} x_{r,s,t} \le i_t$), then feed it to an ILP solver.

Related (but different): Number of ways to fill a 2xN grid with M colors, Counting Colorings of a Grid.


Is given point covered by any circle? Given  $N$ circles and $Q$ points. What is the optimal solution for checking "if point is covered by any circle" for every point?
The trivial solution would be $O(QN)$.

Let's suppose you have a spatial data structure that can be built over a set $S$ of points on the plane and expose the functions.

Build(S): Build and return the data structure storing all points in S
ds.Delete(q): Deletes point q from the set S
ds.Search(p): Return the closest point in S to point p

Now let's solve the problem backwards, instead of finding if a point is contained by some circle, lets find points for each circle the points it contains.

C: Set of circles
P: Set of points
ds := Build(P) # Build the data structure using points to be queried

for each circle c in C:
   do
      p = ds.Search(c.center)
      if p is inside circle c:
          ds.Delete(p)
   while (ds is not empty and one point was deleted)

All the deleted points from the data structure are the points that belongs to at least one circle, remaining points are not contained in any circle, otherwise they were being found when processing such circle.

Let $N:=|C|$ and $Q:=|P|$

The overall complexity of this algorithm is $$O(Build(Q) + (N + Q) \cdot Search(Q) + Q \cdot Delete(Q))$$

Here $Build(Q)$ is the complexity of building the set of $Q$ points, $Search(Q)$ is the complexity of searching for a point in a set of at most $Q$ points and $Delete(Q)$ is the complexity of deleting a point in a set of at most $Q$ points.

Notice that this cost is amortized, since after a point is recognized to be inside a circle it is deleted from the set.

One data structure that provides good balance for this operations is kd-tree, but I encourage you to find other spatial data structures that provides better complexity for your case.


Why is the unary representation of a number exponentially larger than a base k representation of it? According to a book I am reading, the unary representation of a number exponentially larger than a base k representation of it. I, however, feel that the unary representation should scale linearly with the input.

After all, 1 is 1, 2 is 11, 3 is 111, and so on, right? Wouldn't that be linear?

The base $k$ representation of the number $n$ takes $\log_{k}n$ bits, whereas the unary representation takes $n$, and of course $n = k^{\log_{k}n}$

The gap is more apparent with larger numbers, if we take our normal base 10 system, then writing 1000 takes 4 decimal digits, but writing it in unary takes 1000 ones.


Mapping reductions for dummies I am having trouble understanding a mapping reduction and I would appreciate your help. Define

$\quad \begin{align}
  A_{TM} &= \{ \langle M, w \rangle \mid M \text{ Turing machine}, w \in \mathcal{L}(M)\} \\
  S_{TM} &= \{ \langle M,w \rangle \mid M \text{ Turing machine}, w \in \mathcal{L}(M) \implies w^R \in \mathcal{L}(M)\} \\
\end{align}$

and consider the reduction of $A_{TM}$ to $S_{TM}$ as follows.

Given $\langle M, w \rangle$ the following Turing machine $M'$ is defined:

M' on input x:
  if x = 01 then accept
  else run M on w and accept x if M accepts w

I don't understand the reduction entirely, this reduction is supposed to solve $S_{TM}$ using $A_{TM}$.  Why do I need to check if x = 01? There is no need to check anything about the reverse of $w$?  How is that covered by the reduction?

The idea of the reduction you give in your question is the following:

I) If $\langle M,w\rangle \in A_{tm}$, then $L(M')=\Sigma^*$.
II) If $\langle M,w\rangle \notin A_{tm}$, then $L(M')=\{10\}$.

thus, for any $w$, $\langle M,w\rangle \in A_{tm}$ iff $\langle M',w\rangle \in S_{tm}$.
In case (I), for any $w\in L(M')$ also $w^R\in L(M')$ hence $\langle M',w \rangle S_{TM}$ for any $w$. For case (II), there is no $w\in L(M')$ such that $w^R\in L(M')$ as well, thus for any $w$, $\langle M',w \rangle S_{TM}$.

Now for your question about accepting "10" no matter what: Assume we avoid this step. Then, in case (II), $L(M')=\emptyset$, hence $\langle M',w\rangle \in S_{tm}$ for any $w$, since the condition on $w,w^R$ vacuously holds. Now the mapping cannot map inputs  $\langle M,w\rangle \notin A_{tm}$ to inputs outside $S_{TM}$ (since none exists).

The value "10" is arbitrary. Any other non-palindromic string will do.


What exactly (and precisely) is "offset"? Just like my previous question concerning 'hash'; what exactly is an (or the) "offset?"

Is it a value or data type? Or is it an address location? I have heard it used in different contexts within the computing world. Of course, I have come across it while mounting a disk image; but does it have any other usage than that. I ask this because I have come across the word at other places. Does it have to do anything with memory registers?

An offset is a difference between two indices, usually memory locations or array indices.

For example, suppose that you have an array $A$ in which each element occupies $x$ bytes. Suppose also that the address of $A$ is $M$. Then the address of the $i$th element (counting from zero) is $M + i \cdot x$. Here $i \cdot x$ is the offset. It's the difference between the address of the $i$th element and the address of the array (which is the address of the zeroth element).


Complexity of optimized bubblesort What is the runtime complexity of the following implementation of Bubblesort (for integers)?

    #define SWAP(a,b)   { int t; t=a; a=b; b=t; }

    void bubble( int a[], int n )
    /* Pre-condition: a contains n items to be sorted */
    {
       int i, j;
      /* Make n passes through the array */
      for(i=0;i<n-1;i++)
      {
     /* From the first element to the end
       of the unsorted section */
        for(j=1;j<(n-i);j++)
        {
        /* If adjacent items are out of order, swap them */
       if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
       }
    }
}

The first iteration will do will do $n-1$ comparisons, the next $n-2$, the second $n-3$ and so on. In total $n-1$ iterations are done.

Hence, you need to find the sum of $(n-1)+(n-2) + ... + 1$ which is $((n-1)^2+n-1)/2$ which still is $O(n^2)$. So the optimization does not improve the asymptotic running time.

Note that I edited your algorithm slightly: the outer loop is only iterated $n-1$ times. This is because for each iteration, one more element is put into the right place. Hence after $n-1$ iterations, $n-1$ elements will be in the right place and so element $n$ must also be in the right place.


Computing the Kolmogorov complexity of a string What would be the implications for complexity theory if you could compute the Kolmogorov complexity of a string generated by a psuedorandom generator?

If we're talking about a generator who can handle any length $n$ seed (perhaps this is more cryptographic PRG oriented), and stretch it to some length $n'>n$ pseudorandom string, then the answer is no. The reason actually has nothing to do with the properties of PRGs, but simply relies on the fact that the output of the generator is computable, and that its range is infinite.

Kolmogorov's complexity isn't computable on any infinite recursively enumerable set of strings. To show this you can follow the standard proof of uncomputability of Kolmogorov's complexity. Since the set is infinite, it contains strings of arbitrarily high Kolmogorov's complexity, so you can write a program which enumerates them until it finds some string of high enough complexity, and then stop and output it. This was also answered in this math.se question.


AVL tree worst case height proof The worst case height of AVL tree is $1.44 \log n$. How do we prove that?
I read somewhere about Fibonacci quicks but did not understand it.

We want to show that the number of nodes $n$ in a height-balanced binary tree with height $h$ grows exponentially with $h$ and at least as fast as the Fibonacci sequence.

Let $N_h$ denote the minimum number of nodes in a height-balanced binary tree having height $h$.  Recall that in a height-balanced binary tree of height $h$, the subtree rooted at one of the children of the root has height $h-1$, and the subtree rooted at the other child of the root has height $h-1$ or $h-2$.  Thus, $N_h > N_{h-1} + N_{h-2}$.  Thus, $N_h$ is at least $f_h$, the $h$th term of the Fibonacci sequence, where $f_h \approx \phi^h / \sqrt{5}$ and $\phi$ is the golden ratio $\frac{1+\sqrt{5}}{2}$.

So, if $n$ is the number of nodes in an AVL tree of height $h$, we have $n \ge \phi^h / \sqrt{5}$. Taking $\log_2$ of both sides, we get $h \le \frac{\log_2 n}{\log_2 \phi} + c = 1.4404 \log_2 n + c$, for some constant $c$. Thus, an AVL tree has height $h = O(\log n)$

An easier proof, if you don't care about the constants as much, is to observe that $N_h > N_{h-1}+N_{h-2} > 2N_{h-2}$.  Hence, $N_h$ grows at least as fast as $\sqrt{2}^h$.  So the number of nodes $n$ in a height-balanced binary tree of height $h$ satisfies $n > \sqrt{2}^h$.  So $h \log_2 \sqrt{2} < \log n$, which implies $h < 2 \log n$.


Proof that the length of the largest ascending subsequence is the number of decreasing subsequences Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is actually the length of one of the longest increasing subsequences. I need to this because I have to prove the greedy algorithm for finding all the decreasing subsequences having as few subsequences as possible. I have no idea of where to start, any help is much appreciated.

Edit:
The big, greedy problem sounds like this: decompose the sequence in a minimum number of decreasing subsequences (non-strictly). Those are the subsequences I am talking about.

Thank you.

You should read up on Patience Sorting first; that's a greedy algorithm to calculate a partition into nonincreasing subsequences (described there as piles of cards). Moreover, the number of subsequences (piles) is minimal.
To prove that, we need to consider two things.
Claim 1: the length of the LIS is a lower bound on the number of piles. That follows from the fact that each of the elements in the LIS must go into a different pile, for if any two elements end up in the same pile, it would no longer be nonincreasing.
Claim 2: the number of piles obtained by Patience Sorting is a lower bound on the length of the LIS. Wikipedia has a proof. To summarize: whenever we place a card C in pile X > 1, we add a pointer from card C to the current top card at pile X - 1 (which is necessarily smaller). If we end up with N piles, we can start at the card on top of pile N, and follow back pointers to construct a strictly increasing subsequence of length N (in reverse).
Combine 1 and 2 to conclude that the length of the LIS is equal to the minimum number of nondecreasing subsequences in the partition (and such a partition is produced by Patience Sorting).
If this is still unclear, there is a similar question about Patience Sort here:
How to prove the optimality of the "patience sort" algorithm?


Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$ I need to prove that the following recurrence relation is $O(5^n)$:
$$ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $$
And $T(n)=\Theta(1)$ for $n\le 9$.
I am trying induction, and proving that there exists $c$ such that $T(n)\le c\cdot5^n$, but I am stuck at the induction step:
$T(n)=5^n+3T(\big\lfloor n^\frac{2}{5}\big\rfloor)\le5^n+3c\cdot 5^{\lfloor n^\frac{2}{5}\rfloor}\le5^n+3c \cdot 5^{n^{\frac{2}{5}}}=\bigg(1+\frac{3c}{5^{n- n^\frac{2}{5}}}\bigg)\cdot 5^n$.
How can I continue in the induction (turn the parenthesis into the constant $c$)?

Assume that $n \ge 4$ (the induction step is only handling $n \ge 10$ anyway), then $n-n^\frac{2}{5} > n - \sqrt{n} \ge 2$ and you have:
$$
\left( 1 + \frac{3c}{5^{n-n^\frac{2}{5}}} \right) \cdot 5^n \ge
\left( 1 + \frac{3c}{5^2} \right) \cdot 5^n =
\left( 1 + \frac{3}{25} c\right) \cdot 5^n.
$$
The latter term is not larger than $c \cdot 5^n$ whenever $1 + \frac{3}{25} c \le c$, i.e., when $c \ge \frac{25}{22}$.
Pick $c$ large enough to satisfy $c \ge \frac{25}{22}$ and the base cases, and you're done.


Algorithm for printing all accepted strings (to an upper bound if infinite amount) from a given DFA As the title states I'm trying to write an algorithm that generates accepted strings to an upper bound from a given DFA.

It should not generate more strings than the upper bound n if it contains cyclic patterns, because obviously I can't print an infinite amount of strings, which leads me to my problem.

Machines with finite languages are very straight forward as I can just do a DFS search and traverse through the graph and concatenate all letters that connect the states recursively, but I have no clue how I should deal with infinite language DFAs unless I hardcode a limit on how many times the DFS should traverse states that can potentially lead to cycles.

So my question is; how should go about approaching this problem. Are there any known algorithms (aside from DFS, BFS) that I could use to tackle this task?

Thanks in advance. I tried hard to find similar questions but I couldn't find anything helpful.

Edit: Clarified problem a little bit.

The simplest one is to generate all strings up to length n and test them against the DFA.

The next option is a Breadth first traversal over the DFA (emitting the string each time you encounter a final state) however this can need a lot of memory. In the worst case all you need to keep all of length n in memory.

Next is a depth first traversal up to length n. Keep a counter of how long the string would be and backtrack when you exceed n.

To instead get the first n strings you run one of the above algorithms with a certain length and if it generates not enough strings you increment n until it does.


All 16 Boolean Logic Gates I was doing some reseach and I came across a website that had listed 16 different boolean logic operators. I was wondering if all of them were real, and if so, what do they do.

https://www.researchgate.net/figure/Method-for-implementing-all-16-Boolean-logic-functions-in-a-single-MR-unit-with-a_fig1_303770111

What do you mean by real? You can define as many logic gates as you want and build them. However, in a boolean logic with 2 inputs, there are 16 different combination of outputs. On the other hand, it proven that $\{AND,NOT\}$, $\{OR,NOT\}$, $\{NAND\}$ and $\{NOR\}$ are functionally complete (which means we can build all other combination from 16 outputs with only using gates in those sets ).

However, you may build a new gate directly with a technology (let say MOSFET) and use another name. You can still build that gates using one of the comprehensive gate set.


Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable? $$T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$$

I started with Rice's theorem (come up with an example where $|L(M)| = 2$) to see that $T$ was undecidable. Then I figured out $\bar{T}$ was unrecognizable, because $H =\{\langle M \rangle \mid M\text{ halts on the empty string} \}$ has a mapping-reduction to $T$, and $H$ is not co-recognizable, so $T$ is not co-recognizable.

Now I'm stuck. I tried mapping-reductions from $H$, $E = \{\langle M \rangle \mid M \text{ doesn't accept anything} \}$ and $F = \{ \langle M \rangle \mid L(M) \text{ is finite} \}$.

What's a good set to try and reduce from (or reduce to)? Am I right that $T$ is unrecognizable?

You can establish a reduction $\overline{H}\le_M T$ by mapping $\langle M\rangle\rightarrow \langle N\rangle$ where

N(x) =
   if x = 0, accept
   if M halts on the empty string
      if x = 1, accept

Now

If $\langle M \rangle\in H$ then $L(N) = \{0, 1\}$ which implies $\langle N\rangle\notin T$
If $\langle M \rangle\notin H$ then $L(N) = \{0\}$ which implies $\langle N\rangle\in T$

and since you already know $\overline{H}$ is not recognizable, $T$ must not be recognizable.


Does time or space complexity of arithmetic operations get affected by the number of digits? Suppose I have two 5-digit numbers (A and B) and two 50-digit numbers(C and D). Do the operations A+B and C+D have equal complexity in terms of time and space? or C+D is more complex due to the size of digits?

The complexity of arithmetic operations is typically measured in bit operations, though not everybody agrees this is the correct measure. There is a Wikipedia page listing the complexity of the best algorithms currently known for various operations, including addition and multiplication.


Different definitions of complexity class DP I would like to know how different defintions of class DP (also written $D^p$) are equivalent (brief explanations would do). The following are the two definitions I see:

Difference between two NP problems; i.e.,  DP $:=\{A\setminus B\ :\ A,B\in NP\}$.
$\{L_1\cap L_2\ :\ L_1\in \text{NP},\ L_2\in \text{co-NP} \}$.

Complexity zoo gives the full form "Difference Polynomial-Time" for DP and states that it is equivalent to BH$_2$. They give Definition 3 above as the definition of BH$_2$. (So, according to complexity zoo, the two definitions are equivalent).
This answer says that the definition of DP changed over time. Is this true? If so, which definition is accepted nowadays? Is there a book or survey that explains the complexity class DP (at least as a section) ?
According to this source, NP $\subseteq$ DP. Doesn't that mean DP-hard problems are NP-hard and the other direction is wrong (the latter, unless there is a collapse in complexity classes)?

Equivalence follows immediately from the definitions.  The definition of $\setminus$ is:
$$A \setminus B = A \cap \overline{B}$$
where $\overline{B} = \Sigma^* \setminus B$ denotes the complement of $B$.  Now taking $L_1=A$ and $L_2=B$, it is trivial to prove that $L$ meets the first definition iff it meets the second definition, since $B \in NP$ iff $\overline{B} \in coNP$.


Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?" Do two halting Turing machines accept the same language?
Proof that it is undecidable(credit to another user on this website: "Tom van der Zanden"):
Let M be an arbitrary Turing machine. Let M′ be a Turing machine that on input x, simulates M (on some predefined input) for |x| steps and accepts if (and only if) M halts within |x| steps. If M doesn't halt then M′ accepts the empty language. If M does halt then the language M′ accepts is non-empty. This gives a reduction from the Halting problem to the problem of detecting equality, since we just need to ask whether M′ is equal to the machine accepting the empty language.
How is this proof using "reduction from the Halting problem to the problem of detecting equality?" Asking whether a TM halts in a finite number of steps (|x| in the proof above) is decidable. So how would the problem of detecting equality outlined above provide a way of solving the halting problem?
In other words my problem with understanding the proof is this: How does detecting equality in the way described above decide whether the machine M halts on input x?

Let $\langle M, w\rangle$ be the input to the halting problem.
We will construct $M'$ that simulates $M$ as you described with $w$ as the predefined input.
As you have said, $L(M')\neq \emptyset\iff M \text{ halts}$. However, we simulated $M$ on $w$, hence $L(M')\neq \emptyset \iff M \text{ halts on } w \iff \langle M, w\rangle\in H_{TM}$ where $H_{TM}$ is the halting problem.
Define the function $f$ that given $\langle M, w\rangle$ will output $\langle M', M_{empty}\rangle$, where $M_{empty}$ is a TM that immediately rejects.
We will have: $\langle M, w\rangle \notin H_{TM} \iff L(M')= \emptyset \iff L(M')\neq L(M_{empty})\iff \langle M', M_{empty}\rangle\in EQ_{TM}$
$f$ is computable, and hence it is a reduction from $\overline H_{TM}$ to $EQ_{TM}$.
$\overline H_{TM}$ is not decidable, and thus also $EQ_{TM}$ isn't decidable


How to reduce a problem? I am a bit confused on how to reduce a problem. I'll give an example:
Let's say there is a problem called HALTEMPTY and we know it is undecidable.

$HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ is a Turing Machine that halts on input } \varepsilon\}$

The problem we are reducing to is

$HALT_{TM} = \{\langle M,w\rangle \mid M \text{ is a Turing Machine that halts on input } w\}$

So from what I think, we reduce $HALTEMPTY_{TM}$to $HALT_{TM}$ by creating a turing machine similar to $HALT_{TM}$ but it would delete the tape then run normally like $HALT_{TM}$. Am I thinking this right? Is there a systematic way of solving these type of problems?

You are thinking in the right direction, and you almost got it right. What we need is a partial computable map $r : \mathbb{N} \to \mathbb{N}$ such that, for all $n \in \mathbb{N}$,
$$n \in \mathrm{HALTEMPTY}_{\mathrm{TM}} \iff r(n) \in \mathrm{HALT}_{\mathrm{TM}}.$$
Your instinct about having to do something with empty tapes is right, but you should follow the definitions. An element of $\mathrm{HALT}_{\mathrm{TM}}$ is a code $\langle M, w\rangle$, which means that rather than "deleteing the tape", you should provide a tape $w$. In this case, it should be the empty tape $w_\mathrm{empty}$. So we may define
$$r(M) = \langle M, w_\mathrm{empty} \rangle.$$
Reduction in the other direction is more complicated, you should try to do it yourself.


Getting the sorted sequence from a level-wise sorted min-heap A heap sorted by levels is a heap which:

Every parent is smaller than its children.
The nodes in each level are sorted from the smallest to the greatest.

I need to describe an algorithm with $O(n)$ runtime that prints the values in the heap in sorted order.

I only manage to do it in $O(n \log(\log n))$ using another heap but  have no idea of how to do it in $O(n)$.

Use a recursive algorithm.  Suppose the heap has depth $D$.  Recursively compute a sorted list of all the numbers in the top $D-1$ levels (i.e., all but the bottom level); let $L$ be this list.  Let $L'$ be the list of numbers in the bottom level.  Note that both $L$ and $L'$ are in sorted order, so we can use the Merge procedure from Mergesort to compute a sorted list of all of the numbers.

If you work out the recurrence relation, you'll see that the running time of this algorithm is $O(n)$.  Indeed, Merge runs in $cn$ time, for some constant $c$, so the total running time will be $cn + cn/2 + cn/4 + \dots \le 2cn = O(n)$.


Computer Architecture-3 level RAM hierarchy In all computer architecture books we study that Cache memory could be divided into 3 levels (L1,L2 and L3) and its very beneficial to do so. Why don't we use the same approach in case of main memory (RAM). Is there any particular reason that we avoid this?

Cache memory levels are inherently a "subdivision" of main memory (RAM). To speed up the access of RAM, the cache was created using the notion of "The Principle of Locality". Frequently in programs, memory is accessed in locations that are close (local) to previously accessed locations, so it benefits to keep sections of data stored in nearby cache instead of going all the way to the hard drive. Also, cost has historically been a factor. Cache memory is more expensive than memory space on a hard drive, etc. Keep in mind, the landscape of computer memory models is always changing, and it is likely that other methods will be used in the future to speed up memory access. I think the current trend is to move away from mechanical storage devices with moving parts, hence the SSD's.


Algorithm: Cracking the Safe A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode.

For instance, if I enter the stream $012345$, I am trying each of the combinations $0123$, $1234$, and $2345$.

Clearly, a 40000-length string $000000010002...9999$ is guaranteed to crack the safe.

Can we try each of the 10000 combinations using a shorter string? What's the shortest string we can devise to try every combination?

The answer is to use a de Bruijn sequence, as discussed in response to this question on CS Theory. This gives a sequence of length $10^4=10\,000$. However, the sequence is cyclic, in the sense that if you wrote it on a paper tape and joined the ends together to form a loop, only then would it contain every possible 4-digit sequence and some of those sequences would cross the join. So, for a linear sequence, you need to repeat the first three items at the end, giving $10\,003$, improving on the obvious solution of length $40\,000$.

(Thanks to PålGD for pointing out the issue with cyclicity.)


Go-Back-N ARQ Protocol Throughput Question I am an undergraduate studying Data Coms and Networking and this question about go-back-N ARQ popped up that I am struggling to get my head around and cant find anything similar online. Any help at all would be greatly appreciated.

The only thing I have at all is that throughput could be defined by (Packet bits + overhead)/N. Is this at all on the right path?

QUESTION
Consider the Go-Back-N ARQ protocol with N=5 and 4 bits used for sequence numbering. The user data frame is 3000 bits long where 100 bits are overhead for header and error check, etc. The frame transmission rate is 2Mbps. Assume that the medium does not reorder the frames. The outstanding frames will be retransmitted when the sending window becomes empty. The probability that a data frame would be received without any errors is 0.3.

i)  What is the effective data transmission rate of this protocol?

ii) Suppose that at time t, the receiver is waiting for an information frame with binary sequence number 1001.  What is the possible sequence number Slast in binary inside the sender’s window at time t? Justify your answer.

Window size Ws is 5.
the time to transmit one frame is: tf=3000/2  Mbps=1.5ms
As the frame may be received in error with probability 0.7, each frame need to be transmitted 10/3 times on average. Then the time needed for successfully transmitting one frame is

tf+7/3*Wstf=

38/3*tf=19ms.

The effective rate is (3000-100)/19ms=152.6kbps.
ii)
1001 in binary is 9 in decimal. Frame 8 must have be received by the receiver and the ACK has been sent back to the sender. Therefore, frame 3 must not be included in sender’s window. As frame 9 hasn’t been received yet, 9 must be greater than or equal to Slast. Therefore, Slast can be any of these: 4 to 9 in decimal. Orin binary, 0100, 0101, 0110, 0111, 1000, 1001.


Recurrence : $T(n) = 4T(n/2) + Θ(n^2/\log n)$ Is there a way to solve this recurrence using master theorem:

$$T(n) = 4T(n/2) + Θ(n^2/\log n)$$

As mentioned by @Yuval Filmus in the comment, you can use the extension of the master theorem (case 2b). The result is $T(n) = \Theta(n^2 \log\log{n})$.


Consensus problem of distributed systems I just started reading about distributed systems for the first time ever. There is a fairly slick proof of the impossibility of consensus in an asynchronous model using some combinatorial topology. On the other hand, there are multiple consensus protocols used in practical systems to synchronize distributed state machines like Paxos and Raft. It seems like the key to this perceived contradiction is what is called failure detection.

My question is the following: What does protocols like Paxos and Raft give up, i.e. how are they not contradicting the theorem? How does failure detection fit in here?

Are there any papers that discuss these relationships that are worth looking at?

The FLP theorem [1] says that

  It is impossible for a set of processors in an asynchronous distributed system to agree on a binary value, even if only a single processor is subject to an unannounced crash.

There are several ways to circumvent this impossibility results, by, according to Jennifer Welch; I suggest you to read the linked webpage

changing the system assumptions

Assuming a synchronous system such as in the "Byzantine Generals" problem [2]
Assuming a partial synchronous system in which failure detectors [3] are used

or changing the problem statement

No guarantee for termination (progress) such as Paxos [4]
Randomized protocol [5]
No need to agree on a single value such as in $k$-set agreement problem
No need to agree on exact values in approximate agreement

[1] Impossibility of Distributed Consensus with One Faulty
Process) JACM, 1985.

[2] Reaching Agreement in the Presence of Faults JACM, 1980.

[3] Unreliable Failure Detectors for Reliable Distributed Systems JACM, 1996.

[4] Paxos Made Simple TR. By Lamport

[5] Another Advantage of Free Choice (Extended Abstract): Completely Asynchronous Agreement Protocols PODC, 1983. It has just received the 2015 Edsger W. Dijkstra Prize.


Dynamic Programming on bracketed sequences I am currently working on the following problem that involves developing a dynamic programming algorithm for finding the length of the shortest fully bracketed expression (FBE), $y$ that contains a given string $x = x_1x_2...x_n$. An FBE is defined as a string over the characters (,),[, and ] that is either

the empty string
the string $[T]$ or $(T)$, where $T$ is a fully bracketed expression, or
the string $TU$, where $T$ and $U$ are fully bracketed expressions.

So far I have worked through the potential recursive function $T(i,j)$ which I've defined as the length of the shortest possible FBE that contains $x_i...x_j$ as a subsequence (not necessarily a string). And I know that in the shortest FBE containing $x_i...x_j$ that $x_i$ is either "mathced" to an appropriate character $x_k$ such that $i + 1 \leq k \leq j$, or it isn't. So I think that I need two cases; either the former is true, or the latter is true.

I'm having trouble formalizing this and creating a recursion. I'm not sure how to deal with the addition of characters. Any help would be appreciated! Thanks!

Let $S(i,j)$ be the set of the shortest FBEs containing $x_i\ldots x_j$. We focus on non-trivial cases ($j-i\ge 2$).

If there is an element in $S(i,j)$ with the form $AB$ where neither $A$ nor $B$ is empty, there must exist $i\le k<j$ such that $x_i,\ldots, x_k$ belong to $A$ and $x_{k+1},\ldots,x_j$ belongs to $B$. Easy to see $T(i,j)=\min_k\{T(i,k)+T(k+1,j)\}$.

Otherwise, take an element from $S(i,j)$. Assume WLOG it has the form [$A$]. Note $x_{i+1},\ldots,x_{j-1}$ are contained in $A$, we have $T(i,j)\ge T(i+1,j-1)+2$. Furthermore, if either $x_i\neq$ [ or $x_j\neq$ ] (say $x_i\neq$ [ WLOG), then $A$[] (with the form $AB$) is also an FBE containing $x_i\ldots x_j$, which contradicts to the assumption. Hence $x_i$ and $x_j$ must match.

Combining the two paragraphs above, we have proved

if $x_i$ and $x_j$ do not match,

$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$

if $x_i$ and $x_j$ match,

$$T(i,j)\ge \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$

Note concentrating a shortest FBE containing $x_i\ldots x_k$ and a shortest FBE containing $x_{k+1}\ldots x_j$ constitutes an FBE containing $x_i\ldots x_j$, so $T(i,j)\le \min_k\{T(i,k)+T(k+1,j)\}$. In addition, if $x_i$ and $x_j$ match, say $x_i=$ [ and $x_j=$ ], and let $s$ be a shortest FBE containing $x_{i+1}\ldots x_{j-1}$, then [$s$] is an FBE containing $x_i\ldots x_j$, so $T(i,j)\le T(i+1,j-1)+2$. As a conclusion, if $x_i$ and $x_j$ match,

$$T(i,j)\le \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$

So the recursion turns out to be

if $x_i$ and $x_j$ do not match,

$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$

if $x_i$ and $x_j$ match,

$$T(i,j)= \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$


2OPT Approximation Algorithm for Multiway Cut Problem In the multiway cut problem, the input is an undirected graph $G= (V, E)$ and set of terminal nodes $s_1, s_2,\ldots s_k$ are in $V$. The goal is to find a minimum
set of edges in $E$ whose removal leaves all terminals in different components.

How do we show that this problem can be solved exactly in polynomial time when
$k= 2$?
How do we get an approximation algorithm with ratio at most 2 for the case when $k \geq 3$?

Minimum $k$-Multiway Cut

Given a graph $G =(V,E)$ and a set of terminals $S=\{s_1, s_2, \dotsc, s_k\} \subseteq V$ find a minimum set of edges $E' \subseteq E$ whose removal separates each pair of terminals in $S$.

Case when $k=2$

For the case when $k=2$ Minimum $k$-Multiway cut is exactly the Minimum $s$-$t$ Cut problem. To see this simply let $(s_1, s_2) = (s,t)$ and compute a min $s$-$t$ cut. This can be solved in polynomial time by various Maximum-Flow algorithms.

Case when $k \geq 3$

We can design a very simple 2OPT approximation algorithm for the $k$-Multiway Cut problem. For each $s_i$, where $1 \leq i \leq k$, collapse $S \setminus \{s_i\}$ into a single node $t_i$. Compute a min $s_i$-$t_i$ cut and call it $C_i$. Repeat this for each possible $s_i$. Output  $C = \bigcup_{i=1}^k C_i$.

Claim: $|C| \leq 2 \textrm{OPT}$

Let $A$ be the optimal multiway cut and let $A_i$ be a cut that separates $s_i$ from the rest of the graph. Since each edge in $A$ is adjacent to 2 components, each edge must be in two of the cuts $A_i$. Hence, $$\begin{align*}&\sum_i |A_i| = 2|A| &(*)\end{align*}.$$ Further, since $C_i$ is a minimal cut, $|C_i| \leq |A_i|$. This fact together with $(*)$ implies that our algorithm achieves a $2\mathrm{OPT}$ approximation ratio.

Claim: $\text{Proposed algorithm runs in polynomial time}$

The algorithm requires $k$ calls to a Minimum $s$-$t$ cut procedure. Since we only make a constant number of calls to a polynomial-time algorithm, our resulting algorithm is still polynomial.

You can further improve this to $(2 - \frac{2}{k})\mathrm{OPT}$ by dropping the heaviest cut. Beating that bound requires a slightly more advanced LP rounding schema.


A plane-sweep algorithm for a points in triangles inclusion problem I was given the following homework assignment:

Consider a set of $p$ points and $t$ triangles in the plane. The triangles are pairwise disjoint, that is, their edges do not intersect, no triangle lies in the interior of another, and no edge/vertex is part of more than one triangle. The points are in general position with respect to the triangles, that is,
no point lies on a vertex or an edge of a triangle. The triangles are given by the coordinates of their vertices, and also the points are given by their coordinates. All points and vertices have pairwise different coordinates. (See below for an example.)

The task is to determine for each of the $p$ points whether it lies inside a triangle, and if yes in which. Design an efficient algorithm for solving this task. Explain your solution in detail, show its correctness, and analyze its runtime and memory requirements.

I've coem up with the following algorithm, that closely resembles the Bentley–Ottmann algorithm for the intersection of line segments. The idea is to sweep the plane from left to right analogousely to it. The main point is the observation that a point p lies in a triangle iff $p$ lies $x$-wise between the triangle starting - and triangle endpoint as well as $y$-wise between the intersection points of the sweep line with the triangle sides. (For an illustration see below.)

SET-UP: Let $X$ be a priority in which we store the $x$-coordinates of the points of $P$ and $T$. Let further $Y$ be a Red-Black-Tree in which we store the $y$-coordinate-wise sorted list of triangle edges. At last let $T$ be the set of triangle points and $P$ be the set of the remaining points.

ALGORITHM:

1) $X := 0, Y := 0$

2) Insert the $x$-coordinates of all points of $P$ and $T$.

3) while $x \neq \emptyset$ do

Find the minimum $m$ of $X$ and delete it from $X$.
If $m$ is a triangle starting point then insert the incident edges into $Y$.
If $m$ is a triangle middle point then delete the incident edge to the left
of $m$ and insert the incident edge to the right of $m$ into $Y$.
If $m$ is a triangle end point then delete both incident edges from $Y$.
If $m$ is a point out of $P$ then do for all pairs of adjacent edges in $Y$:

Calculate the intersection points of the sweep line L with the
current pair of adjacent edges.
Check wether the $y$-coordinate of $m$ lies between the $y$-
coordinates of said intersection points. If it does the point
$m$ is in the respective triangle. Report $m$ and said
triangle.

I think that this algorithm should have $\mathcal{O}((p+t)*log(p+t))$ running time, but I don't know how to argue that in a more formal manner with the characteristic of Red-Black-Trees and so on. Could you help me with that?

Illustration 1
Illustration 2
Illustration 3

SOURCES:

http://www.ist.tugraz.at/_attach/Publish/Eaa17/assignment_06.pdf

Generally, you can analyze each step of the algorithm. Step 2 for constructing the tree (as insert operation can take $O(\log(n))$) is $O((p+t)\log(p+t))$.
All operations in if statements take $O(\log(n))$ (finding the minimum, deleting a member, inserting a member, and so on). Also, the main while loop takes $|X|= p + 3t$.
Hence time complexity of the algorithm would be $O((p+t)\log(p+t))$ as you guess.

In sum, to analyzing time complexity of an algorihtm in a formal manner, it would be enough discussed on each step of the algorithm.

For correctness, you should show that this algorithm can find a general point inside its triangle correctly.


Given a Turing Machine M, are there infinitely many Turing machines that recognize L(M)? I want to show this problem is decidable by describing a TM that answers the question.
I originally thought this was quite simple, and that the answer would just be a TM that outputs "yes" for any valid input of a TM M. My reasoning was that given any TM M, we can just add a new unreachable state to it and the new machine M' will still recognize the same language as M.
However, a Turing machine can only have a finite set of states so now I'm unsure if this reasoning is correct in order to produce infinitely many Turing machines and I'm unsure where to go from here.

Any help would be much appreciated.

Your attempt is fine. Yes, a Turing machine can only have a finite number of states, but you can add $i$ unreachable states for any natural number $i$ and there are infinitely many natural numbers, even though each one of them is finite.


Are there any benefits of implementing the Fisher–Yates shuffle algorithm from tail to head instead of head to tail? I was looking at the Fisher–Yates shuffle algorithm and followed the Python implementation for it.

Python starts from the end of the array to the start. Looking at the algorithm I didn't see any benefits in doing so compared to starting with the start and going to the end.

I was wondering, considering that looping backwards adds a thin layer of complexity, are there any benefits in doing so?

With 0-indexed arrays, and stopping the loop at the last non-trivial random selection, we have

for x = n to 2 step -1:
    swap A[x-1], A[uniform_random(0 inclusive to x exclusive)]

vs

for x = 0 to n-2 step 1:
    swap A[x], A[uniform_random(x inclusive to n exclusive)]

which would probably be implemented as

for x = 0 to n-2 step 1:
    swap A[x], A[x + uniform_random(0 inclusive to n-x exclusive)]

So the forward loop has at least as much complexity.

I would claim that the simplest version is looping backwards in a 1-indexed environment (i.e. 1-indexed arrays and random number generation):

for x = n to 2 step -1:
    swap A[x], A[uniform_random(1 inclusive to x inclusive)]

There are various other variants possible: e.g. in the first example, we could loop x = n-1 to 1 step -1; in the second example, we could use two loop variables instead of one; etc.


Find distinct groups with no common parents Given an array $arr$, element $arr[i]$ indicates its parent. If the element has no parent then $arr[i]=-1$. What is the optimal algorithm for finding the minimum number of groups such that no element in each group is a child node (whether directly or indirectly) of any other node in the same group.

arr[] can be considered a partial order, and the groups you're looking for are then called antichains. So, you're looking for a decomposition into a minimum number of antichains of the partial order represented by arr[]. According to Mirsky's theorem, the smallest achievable number of antichains is equal to the length of the longest chain -- that is, the longest path of descendants in the forest (set of trees) represented by arr[]. (It's impossible to do better than this, since every element in this longest chain needs to be assigned to a distinct antichain.)
That Wikipedia page also describes a neat way to actually construct an optimal set of antichains, based on the idea that if two elements have the same number of ancestors, neither of them can be an ancestor of the other. In short: Perform BFS on the forest defined by arr[], starting from all root elements (you can do this by initially inserting all such elements into the queue); every layer (set of nodes at the same depth) constitutes one antichain.


Permuting integer vectors $x$ and $y$ which add to integer vector $z$ I posted this on mathoverflow but haven't recieved any comments. I wonder if there might be some insight from this community. Thanks!
The problem
Suppose you have nonnegative integer vectors of length d,  $x$, $y$, $z \in \mathbb{Z^+}^d$. We know that $\sum_{i=1}^d x_i + y_i = \sum_{i=1}^d z_i$. I wish to find permutation matrices $\Pi_1$ and $\Pi_2$ such that
\begin{align}
\Pi_1 x + \Pi_2 y = z
\end{align}
without enumerating all possible permutations. If there is a solution, I'd like to know in as few steps as possible. If the solution is not unique, I'd like to know all permutation pairs which satisfy the above (or have an efficient means of enumerating them)
More context:
$x$ and $y$ actually represent integer partitions, and I actually have many $x$'s and many $y$'s for any given $z$, and will have to check all possible $x, y$ pairs for the given $z$.
Things I've tried:

We can immediately rule out some $x, y$ pairs using majorization. Let $\tilde{x}$ and $\tilde{y}$ be the sorted versions of $x$ and $y$. I can show that $\tilde{x} + \tilde{y}$ majorizes all other permuted sums of $x$ and $y$. If $z$ majorizes $\tilde{x} + \tilde{y}$ (and is not equal to it, modulo permutation), then it majorizes all permuted sums of $x$ and $y$, so there is no solution. Similarly, $\tilde{x} + \text{reverse}(\tilde{y})$ is majorized by all other permuted sums. If $z$ is majorized by $\tilde{x} + \text{reverse}(\tilde{y})$, then it is majorized by all permuted sums and there is no solution. By partially ordering all the $x$'s using majorization and doing the same for $y$, this method potentially knocks out many pairs without having to check them all.
We can avoid checking all pairs of permutations by using sorting.
Let $\tilde{x}$ be the sorted version of $x$ and let $\widetilde{\Pi}_x$ be a permutation which sorts $x$, i.e.  $\widetilde{\Pi}_x x = \tilde{x}$.
Enumerate all unique permutations of $y$, and subtract them from $z$.
Sort each difference vector, and compare it against $\tilde{x}$.
Given a match, $\Pi_1$ and $\Pi_2$ can be determined by the permutation of $y$ and the permutation which ``unsorts'' $\tilde{s}$.
Formally, suppose for some permutation $\Pi^*$, $s = z - \Pi^* y$ with $\tilde{s} = \tilde{x}$.
Then $\Pi_1 = {\widetilde{\Pi}_s}^{-1} \widetilde{\Pi}_x$ and $\Pi_2 = \Pi^*$.
I've found a reduction of the problem to filling in count matrices with specified row, column, and diagonal margins, but haven't found efficient ways of solving that problem. Please chime in if you have thoughts on this. I can say more about this if relevant.

I realize this question is somewhat algorithmic in nature, but I'm hoping there is some relevant area of mathematics that could help. I've tried to think about this from the perspective of symmetric groups, the elementary basis for symmetric functions, general equivalence classes, but I'm not getting very far. Any help or suggested directions would be appreciated!

Your problem is equivalent to numerical 3-dimensional matching and is NP-complete.
It is listed under code SP16 in Computers and Intractability; A Guide to the Theory of NP-Completeness by Garey and Johnson.


Expected number of swaps in bubble sort Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that will take place to sort the array using bubble sort.

I've tried the following:

The probability for an element $A[i] > A[j]$ for $i < j$ can be calculated easily from the given probabilities.
Using the above, I have calculated the expected number of swaps as:

double ans = 0.0;
for ( int i = 0; i < N-1; i++ ){
    for ( int j = i+1; j < N; j++ ) {
        ans += get_prob(A[i], A[j]); // Computes the probability of A[i]>A[j] for i < j.

Basically I came to this idea because the expected number of swaps can be calculated by the number of inversions of the array. So by making use of given probability I am calculating whether a number $A[i]$ will be swapped with a number $A[j]$.

Note that the initial array elements can be in any order, sorted or unsorted. Then each number can change with some probability. After this I have to calculate the expected number of swaps.

I have posted a similar question before but it did not had all the constraints.

I did not get any good hints on whether I am even on the right track or not, so I listed all the constraints here. Please give me some hints if I am thinking of the problem in an incorrect way.

Let $\sf{Bubble Sort}$ be defined as the following:

for (j = A.length; j > 1; j--)
    for (i = 0; i < j - 1; i++)
        if (A[i] > A[i + 1])
            swap(i, i + 1, A)

Given some permutation $x_1, \cdots, x_n$, an inversion is said to have occurred if $x_j < x_i$ for some $i < j.$ We see that $\sf{Bubble Sort}$ performs an inversion check for each pair, and if so, performs a swap. Let $X$ be the number of swaps. It is not hard to see in the worst case there are $X = \binom{n}{2}$ possible swaps made. But we are interested in the expected case, which we can compute by defining $X$ in terms of inversions in $\sf{Bubble Sort}$.

Now let $X = \sum_j \sum_{i<j} I_{ij}$ where $I_{ij}$ is the indicator variable that there exists an inversion for some pair $(i,j)$. The expectation is defined as $E[X] = E[\sum_j \sum_{i<j} I_{ij}] = \sum_j \sum_{i<j} E[I_{ij}]$. We now need to determine $P\{I_{ij}\}$.

When assuming any possible permutation as input, each with uniform probability, it can been shown that $P\{I_{ij}\} = \frac{1}{2}$. The reasoning behind this is that under any possible permutation, half of the time $x_j < x_i$ and half of the time $x_i < x_j$ for $i \neq j$.

Returning to our expectation calculation we see that $E[X] = \sum_j \sum_{i<j}E[I_{ij}] = \sum_j \sum_{i<j} \frac{1}{2} = \binom{n}{2} \cdot \frac{1}{2} = \frac{n(n-1)}{4}$


Given a set, partition it into ordered triples I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$.

The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$?

I was trying to prove that this problem is NP-hard by a reduction from Numerical 3D matching (N3DM).

Given an instance of N3DM; 3 sets $X$, $Y$, $Z$, and a bound $b$, normalize it to make $b=1$. I create an instance of my problem as follows: $S=X\cup Y\cup Z$ and for each $x_i\in X$, set $a_i=x_i+3M$, for each $y_j\in Y$, set $a_j=2M-y_j$, and for each $z_k\in Z$, set $a_k=M-z_k$. $M$ is chosen very large. The idea of this comes from https://cs.stackexchange.com/a/117122/48180.

If N3DM is solved, then $x_i+y_j+z_k=1$, thus $a_i-a_j-a_k=1$ and my problem is solved. But if my problem is solved I cannot prove that N3DM is solved because I could select for example two elements from the same set say $Z$, $x_i+3M-M+z_j-M+z_k=M+x_i+z_j+z_k\geq1$ but N3DM is not solved.

I was saying maybe the problem is easy after all?

Do you have any hints?

If you select two elements from $Z$, then by the pigeonhole principle, there must be a triple that does not contain any element from $Z$, which is impossible.


Fixed Point Combinator Turing proof I have to proof that Turing's combinator is a fixed point operator, but I can't get it. I tried this:
\begin{align*}
    Vg &= (UU)g = ((\lambda f.\lambda x.x(ffx)) (\lambda f.\lambda x.x(ffx)))g =
    (\lambda x.x((\lambda f.\lambda x.x(ffx))(\lambda f.\lambda x.x(ffx))x))g\\
    &= g((\lambda f.\lambda x.x(ffx))(\lambda f.\lambda x.x(ffx))x)g \\&= g(UUx)g = gVxg
\end{align*}
The problem is that I'm getting an extra $x$ at the final. Did I make a mistake while doing beta reduction?
Any help will be appreciated.

Your second $\beta$ reduction is wrong.
After the first reduction, you (should) have $(\lambda x.x (U U x)) g$, so after the second you have $g (U U g)$ as required, but you haven't substituted the second $x$ correctly, leaving both it and the $g$ that the function is applied to, giving you $g (U U x) g$, though you have substituted the first $x$ correctly.


Acceptance behavior of L and NL with and without cycling The complexity class NL seems to allow cycling, otherwise we wouldn't have SL $\subset$ NL. What about L? If an algorithm from L cycles for a given input, it certainly cannot accept (because it won't enter the accepting state), so we could define that it rejects in this case (which would be consistent with NL). Or is cycling simply not allowed for L?

Does this makes any difference at all, i.e. would NL or L get weaker (in the sense that we can't prove that they still accept the same languages), if we would completely forbid cycling?

Shaull's comment answers the question:

  Do you mean that the TM repeats a configuration? If so, it can always be avoided by keeping a (logspace) counter for the maximal number of configurations, and halting when the counter resets.

This technique can even be used, without knowing (beforehand) any bound for the amount of space used. The TM can just keep track of the amount of space used till the current step (excluding the additional counter), and halt when the counter exceeds the maximal possible number of different configurations given the space used.

The additional counter will take the same amount of space as the computation already used plus the logarithm of the length of the input already scanned. Tracking of the amount of space used adds the logarithm of that used space to the total used space. So this approach to detect (avoid) repeated configurations works for any non-sublogarithmic space complexity class.

When I asked that question, I had in mind a technique for finding cycles which only works for deterministic machines: I take two copies of the machine, and always perform one step for the first machine and two steps for the second machine, and then compare the configurations of the two machines. Those configurations can only be equal if the machines cycles, and any cycle will be found before the first machine repeats a configuration.

This technique only works for deterministic machines, and only when copying the machine doesn't violate any resource restrictions. For example, it doesn't work for stack machines (because having two stacks is fundamentally different from having only one stack), and it doesn't work for machines which may only read their input once.

For machines which can read their input only in forward direction and only once, the above two techniques can be slightly modified. Each time a new symbol from the input is read, the entire machinery for detection of repeated configurations is reset, and starts again from zero. So the input position must no longer be included in the number of possible states, and the copied machines (of the second technique) no longer need any access to the input. This allows to apply those techniques also to DFAs.

Similar modifications to also make those techniques applicable to stack machines would be nice, because we know that PDAs have no problems with repeated configurations either.


Largest possible cost of a shortest path in which every edge's length is either -1, 0, or 1 I'm doing an online course in which I'm struggling with the following (multiple-choice) question:

Suppose we run the FLoyd-Warshall algorithm on a directed graph $G =(V,E)$ in which every edge's length is either $-1,0,$ or $1$. Suppose further that $G$ is strongly connected, with at least one $u$-$v$ path for every pair $u,v$ of vertices. The graph $G$ may or may not have a negative-cost cycle. How large can the final entries $A[i,j,n]$ be, in absolute value? Choose the smallest number that is guaranteed to be a valid upper bound. (As usual, $n$ denotes $|V|$.) [WARNING: for this question, make sure you refer to the implementation of the Floyd-Warshall algorithm given in lecture, rather than to some alternative source.]

$+\infty$

$n^2$

$2^n$

$n-1$

I'm furthermore told that $n-1$ shouldn't be selected, with the hint "Experiment with graphs that have negative-cost cycles".
Here is the Floyd-Warshall algorithm as described in the lectures:

Let $A$ be a 3-D array, indexed by $i,j,k$.
Define the base cases:
$$ A[i,j,0] = \begin{cases}0 & i = j \\ c_{i,j} & (i,j)\in E \\ +\infty & \text{else}\end{cases}$$
For k = 1 to n
    For i = 1 to n
        For j = 1 to n
            A[i,j,k] = min(A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1])

Correctness: From optimal substructure and induction, as usual.
Running time: $O(1)$ per sub-problem, $O(n^3)$ total.

In the course's nomenclature, $n$ denotes the total number of vertices in the graph, so $A(i, j, n)$ is the shortest path from node $i$ to $j$ which may use all $n$ nodes.
As I understand it, a shortest path between any two nodes has at most $n - 1$ edges, so if the maximum cost of an edge is 1, I would expect the maximum cost of a shortest path to be $n - 1$. I don't see how the presence of negative-cost cycles could change this?

a shortest path between any two nodes has at most n - 1 edges

This is only true for simple paths (paths with no repeat nodes). If there is a negative-cost cycle, you can take the cycle multiple times to get a shorter path.


Difference between large-scale optimization and equation-based simulation Large scale optimization (for example using AMPL) can be used to solve equilibrium systems which have components with fixed mathematical relationships. What is the difference between this and using an equation-based simulation system (like Modelica) to solve an equation-based system?

Of course, most simulations have a time variable, but you can just as well have a time variable in AMPL. Are AMPL models therefore fully analogous to equation-based simulation like MapleSim/Modelica, or is there some fundamental difference between the technologies?

AMPL and Modelica are modelling languages, not a solver or optimization algorithm.  So, you don't use AMPL or Modelica to solve some optimization problem: you express the problem in AMPL or Modelica, then you use some other solver to find the optimal solution.

AMPL tends to be used for problems that can be solved with optimization methods: e.g., linear programming, integer linear programming, quadratic programming, convex optimization, that sort of thing.  Modelica seems to be used for problems that can be solved by solving differential equations or by using hybrid model-checking.

Modelica is for modelling how some continuous variables change over time.  Contrary to what you wrote, there's no simple way to model in that in AMPL by "adding a time variable".  To put it another way: Modelica lets us model, say, the position of a component as a function of time.  This is a function $f(t)$.  AMPL lets us model, say, the position, as a fixed continuous value.  This is a value $x$.  Adding a second variable $t$ still doesn't give you any way to model a function of $t$.

So, the two approaches are for modelling different kinds of problems; and typically they're used with different kinds of back-end solvers, which use different techniques.  They're not interchangeable.

Disclaimer: This is all based on my (rather limited) understanding of these systems.


How are games like chess provably harder than NP? From this question, I had the debate about how problems harder than NP are proved.
I said that intuitively I understand it as (from this video explaining that some problems are provably harder than NP):

Generalized chess is harder than NP, and is EXPTIME-complete for the
decision problem "Given an nxn board with a given position, can white
force a win?" because the proof would require an exponential amount of
steps to show that each branch of the tree eventually leads to a win.
Therefore it's not in NP.

And a user replied:

Your first paragraph is faulty. It has the form "because this one
algorithm I thought of takes exponential time, the problem must not be
in NP". That's faulty -- maybe there's some other algorithm you
haven't thought of that's better.

I'll admit I'm still new at this and the user that wrote the above comment has much more experience in the field than I do. So I trust this user is correct. However, the explanation the video gave seems very intuitive. But can anyone explain why the video's explanation is wrong?
My thought process is as-follows. One of the definitions of NP is "the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes"." So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win. This cannot be done in less than exponential time and thus is provably harder than NP.

The fault lies in this statement:

  So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win.

The second sentence might be right, but it might not.  Perhaps there is a cleverer, faster way that the verifier can check a certificate, or a cleverer format for the certificate that makes it easy to check.  How do we know that's impossible?  We don't.  That would need proof.

The argument has made an assumption about how a verifier "would have to" behave, without substantiating or proving that assumption.  This is basically an argument from failure of creativity: "I can't think of any other strategy a verifier could plausibly use, so there must not exist any valid strategy".  Needless to say, this is not a persuasive form of argument.

For instance, let me give you an example.  Suppose we replace "generalized chess" by "generalized tic-tac-toe", which works as follows: we have a nxn game board, and the first person to get three in a row wins.  Try working through the same argument.  It's tempting to draw the same conclusion, that generalized tic-tac-toe is NP-hard.  But there are reasons to doubt that conclusion: for instance, this form of generalized tic-tac-toe is always a first-player win when you start from the empty board, for all $n>3$.

There are better examples.  In particular, there are games where there are in fact polynomial-time algorithms to play optimally, but the algorithm/strategy is not at all obvious, and if you weren't already aware of it, you might be inclined to be persuaded by the above reasoning that the game is NP-hard.  Examples include Nim, Brussels Sprouts, and Wythoff's game.  This illustrates that the line of reasoning can't possibly be right -- it leads you to draw conclusions that are false.


Weighting function for Non Uniform Learning Consider a hypothesis class $H = \cup_{n=1}^{\infty} H_n$, where for every $n\in N$, $H_n$ is finite. Find a weighting function $w : H ->[0, 1]$ such that $\sum_{h \in H}  w(h) ≤ 1$ and so that for all $h \in H$, $w(h)$ is determined by $n(h) = min\{n :h \in H_n\} $
and by $|H_n(h)|$.
Since every $H_n$ is finite, it is agnostic PAC learnable. And hence their union  $H$ is non-uniform learnable. However I am unable to proceed from here.

For every $n\in \mathbb{N}$, and $h\in H_n$, we can use $w(h)$ = $\frac{2^{−n}}{|H_n|} $.


Make appends not degrade a splay tree Splay trees offer armotized O(log n) access to tree elements. However, if you keep repeatedly appending elements to a splay tree, without splaying any other elements, it degrades into a linked list with O(n) access. Is there a way to avoid that? I have the idea of splaying a random element during an append, but will that do any help?

It's true that if you consider a long sequence of operation, it's possible to point at one operation and say "that one operation might take a really long time" (e.g., $O(n)$ time).  That's in some sense the essence of amortized analysis.  An amortized running time of $O(\log n)$ means that the average time per operation is $O(\log n)$, but it's still true that there might be a rare operation here and there that take much more (though it will be compensated by most operations taking less time).  Amortized running time bounds are only useful if you're willing to accept that limitation.

If you want worst-case running time bounds, then don't use a data structure that only offers amortized worst-case bounds; use a different data structure, one that offers worst-case running time bounds.  For instance, self-balancing binary search trees (like red-black trees, AVL trees, etc.) offer worst-case running time guarantees.  If amortized running time bounds aren't good enough, maybe splay trees aren't the data structure for you.


Prove that this solution to the Closest 3-Sum problem always works I was working on a Leetcode problem, 3Sum Closest. I came up with a solution but struck it down because I didn't think it could be correct. But, turns out it was. I want to know why.
Here's the problem, transcribed:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

The top solution was basically this:

Sort the list.
Loop over each number using index i.
Pick j to be i+1, in other words, the leftmost number of the segment after i.
Pick k to be n-1, in other words, the rightmost number of the segment after i.
If the sum of the numbers at (i, j, k) are less than the target, then j++. Otherwise, k--.

But isn't it possible that we might prematurely increment j (or decrement k), dismissing it forever, when in fact it may have been the optimal pairing had we tried a different k (or j)?
It seems we'll never backtrack to check other combinations.
Can someone provide a minimal, intuitive proof of why such a case never occurs? I'm unable to come up with a counterexample, and I trust the experienced members of Leetcode, so I know I must be wrong, but I can't seem to prove it. I can prove it for the Exact 3-Sum problem, but I don't know how to work with inequalities.

The core of the problem is to solve the 2 sum closest problem for a particular i:

Given a target value, find a pair of numbers who's sum is closer to the target value.

The two pointer approach is the procedure you have described with j and k. (from now on called l and r for left and right)

Your question is why can we decrease r or increase l.

The answer is as the array is sorted, and suppose nums[r] + nums[l] < target, we would not gain any better result comparing nums[l] with any of the values of nums between l and r. Because for any other value in nums[l to r] the sum is even smaller.
 As we wouldn't get any better result, why not forget about the value nums[l] all together? Right?
And that is what we do by increasing l.

This reasoning happens since the beginning of the 2 sum closest search. When l=0 and r=len(nums). We discard values one by one until we are left with l=r-1.


Avoiding the trivial certificate in complexity class NP One definition of the class NP is that there is a certificate whose size is bounded by a polynomial function of the problem instance size which can be used on a deterministic TM, along with the original input, to decide whether the input is a part of the language.

Doesn't this definition allow the trivial loophole where we let the certificate simply be 1 if the input is a part of the language and 0 otherwise?  Then the deterministic just uses the certificate entirely and totally ignores the input.

The point that you're missing is that the deterministic algorithm is given an input to the NP problem and string and it has to say either "That string is a valid certificate for the input" or "That string is not a valid certificate for the input." For example, for compositeness, the verifier would have to be able to accept "Six is composite because it is two times three" and reject "Five is composite because it is two times three." This can be done easily, by checking the arithmetic and checking that the claim isn't something like "$p$ is prime because it is $p$ times one."

If the certificate is just one bit, the only way the verifier could check that a string is a valid certificate would be to ignore the certificate and solve the problem.  Using compositeness again, the verifier's input would be just "Six is composite because, well, I promise it is" and "Five is composite because, well, I promise it is." The verifier can't just "believe" that the string is a valid certificate.


Richard Karp's 21 NP-Hard problems, the meaning of his research? In Richard Karp's paper "Reducability among combinatorial problems" he lists 21 NP-Hard problems. Though I can somewhat understand the ideas and motivation behind the paper I am searching for some clarity.

From what I know and understand this paper showed the parallels between the various problems. Specifically that they are all abstractly the same problem. That given a solution (specifically a P-time solution?) to one of these problems you could solve all of them because they are all statements of a more abstract problem.

Is this a proper summary of the work he presents? Is there a more eloquent and proper yet short way to say it?

Karp's paper: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf

The short way to say it is that these problems are $\mathcal{NP}$-complete.

Of course this only has meaning to those who understand what $\mathcal{NP}$-complete means.

Not only does this say these problems are all somehow equivalent (polynomial-time equivalent to be marginally more precise), but that you can use them to solve any problem in $\mathcal{NP}$, not just each other, with only a polynomial blow-up in the time cost. This immediately gives us that if any of them have a polynomial-time algorithm, then everything in $\mathcal{NP}$ does, and hence we would have $\mathcal{P} = \mathcal{NP}$ (summed up in Theorem 3 from the paper).

To see what Karp's paper in particular represents however, we have to pay attention to a touch of history (not all that usual for most computer scientists I know, but bear with me ;) ). This paper was published in 1972, it was only the year before that Cook proved that $\mathsf{Satisfiability}$ was $\mathcal{NP}$-complete , this was the first "natural" problem proven $\mathcal{NP}$-complete1, but Cook doesn't mention $\mathcal{NP}$, let alone $\mathcal{NP}$-completeness (and he used a weaker type of reduction than Karp, but that's another story). So what you see in Karp's paper is the first codification some of the ideas that have formed one of the central parts of complexity theory, not only does he get these ideas out into the literature, he also says "hey, there's a lot of problems that we're interested that are $\mathcal{NP}$-complete".

So in one go, he coherently defines $\mathcal{NP}$-completeness, shows what it means for solving problems efficiently2, and gives a bunch of (interesting) problems that are $\mathcal{NP}$-complete.

In some sense it is the founding document of complexity theory. It took a lot of ideas that were starting to gain currency, and put them together in a (relatively3) clear statement of how all this complexity stuff can work.

Footnotes

The definition of $\mathcal{NP}$ almost immediately gives complete problems - anything along the lines of "Does this non-deterministic Turing Machine halt in a polynomial number of steps?" or similar, but these are not the most interesting problems in the world (to most people).
Using Edmonds' idea of deterministic polynomial-time as a working definition of "efficient".
Though the reductions are fairly cursor and opaque by modern standards. On the other hand, he crams 21 in there.


Primary/Secondary On Call Rotations I'm trying to setup a primary and secondary on call schedule with 6 people.

I'm trying to schedule people to be on call, so that they will be paired with everyone and they have the longest "break" between their schedules.

Ex for one rotation:

week:      1 2 3 4 5 6 7 8 9 10 11 ...
primary:   1 2 3 4 5 6...?
secondary: 3 4 5 1 2 4...?

Week 1 has people are {1,3}
Week 2 has people are {2,4}

Person 1 has a two week "break" before they're on shift again.
Person 2 has a two week "break" before they're on shift again.

Also, a person can't be both primary and secondary on the same week, ex: {3,3}.

What's the best way to generate a sequence like this, for any number of people so that they have the longest "break" between their shifts, and they are paired with someone different as much as possible?

Given $n$ persons, this question is about a sequence of unordered pair of persons, called a two-person schedule(TPS). A TPS is good if any of its initial contiguous subsequences satisfies the following two conditions.

(fairness requirement) Any person cannot appear two times more than any other person.
(non-repeating requirement) Any unordered pair of persons can appear at most once.

This question asks the best way to generate a good TPS that is as long as possible.
Let us define a perfect TPS as a TPS that satisfies the following requirement.

(inclusive requirement) Each unordered pair of persons is included.

It turns out that a good TPS of the longest length must be a perfect TPS.
In fact, if each unordered pair of person compete with each other, this question is none other than the round-robin tournament as explained by Wikipedia, which has complete solutions. Because of the durability and reliability of wikipedia as well as the size of the solutions, readers are encouraged to check the wikipedia item as well as the references listed thereof. Also there are plenty of resource on the web if you search for "round robin tournament scheduling", such as a nice explanation of Round Robin Tournament Schedule and Javascript code to schedule round robin tournament.
A program that produces Perfect TPS
You can play with a scheduling algorithm in this Javascript playground. Modify the number of persons as you want to on the last line of the code, document.writeln(JSON.stringify(robin(8))). Hit Run code button. You will see output like the following.
[[[1,8],[2,7],[3,6],[4,5]],[[1,7],[8,6],[2,5],[3,4]],[[1,6],[7,5],[8,4],[2,3]],[[1,5],[6,4],[7,3],[8,2]],[[1,4],[5,3],[6,2],[7,8]],[[1,3],[4,2],[5,8],[6,7]],[[1,2],[3,8],[4,7],[5,6]]]


Predicting the outcome of sporting events with multiplicative scoring In the Olympic format for sport climbing, eight athletes compete in three rounds of climbing. Their final score is the multiplication of their rankings in each round. For example, an athlete who comes 1st in the first round, 5th in the second round, and 7th in the third will have a final score of $1\times5\times7=35$. The athletes  with the lowest final score wins.

Assuming that the competition is already partly underway (possibly even mid-round), is there a computer algorithm to quickly compute the probabilities $P_{ar}$ of each athlete $a$ achieving a final ranking $r$, assuming the performance of the athletes is entirely random from here on? Even with 8 athletes the brute force method seems too computationally intensive.

If this isn't computationally possible in a reasonable time, is there an algorithm to get "close enough" to those probabilities?

Brute force

If you want something easy to implement, brute force might be fast enough, assuming at least one round has been completed.

There are $8! = 40320$ possible permutations of the athletes, so in any round, there are 40320 possible rankings.  Assuming the first round has been completed, there are only $40320^2 \approx 1.6 \times 10^9$ possible rankings for the next two rounds, all of them equally likely.  A program should be able to enumerate all of them in a few seconds or minutes and compute the probability distribution of the final rankings for each athlete.

There are faster algorithms, and I will describe them below, but I'm unsure whether the time it takes to understand and implement them will outweigh the amount of CPU time they save.

Convolution

Let the random variables $X_1,X_2,X_3$ denote the athlete's ranking in the first, second, and third rounds.  Then their final score will be $S = X_1 \times X_2 \times X_3$.  Our strategy will be to compute the probability distribution for each $X_i$, then use that to compute the probability distribution for $S$.

Note that if a round has been completed, then the corresponding probability distribution is easy to compute: it assigns probability 1 to the rank the athlete actually obtained, and 0 to all others.

We can compute the probability distribution for a round that hasn't begun by enumerating all $8! = 40320$ possible permutations, observing the athlete's rank in each, and summing up how often each occurs.  Or, more simply, we can note that since all permutations are equally likely, the distribution on the athlete's rank in this round is uniform, i.e., all possibilities have probability $1/8$.

We can compute the probability distribution for a round that has been partly completed by enumerating all $8! = 40320$ possible permutations, filtering out all of them that are incompatible with the results observed so far, then observing the athlete's rank in each that remains, and summing up how often each occurs.

So in this way we can obtain the probability distribution for $X_1$, $X_2$, and $X_3$.  Now we obtain the probability distribution for $S$ from these distributions.  In particular, the probability distribution for $T = X_1 \times X_2$ can be obtained as

$$\Pr[T=t] = \sum_{i=1}^8 \Pr[X_1 = i] \Pr[X_2 = t-i].$$

This requires 8 simple steps for each value of $t$, and there are $30$ possible values of $T$, so this can be done in $8 \times 30$ steps.  Next, the probability distribution for $S = T \times X_3$ can be obtained in the same way.  There are $80$ possible values of $S$, so this can be done in $8 \times 80$ steps.

The result is the probability distribution for $S$, the athlete's final score.  This works with any number of unfinished rounds, even if one round is partly completed.  The total running time is at most $40320 + 8 \times 30 + 8 \times 80$ simple steps, which is very fast; an implemention should complete the computation in millliseconds.

Related:
Estimate distribution of a composite variable, largest samples of set of random variables, Polynomial Computation of the probability of a number of independent events.