Time complexity of a backtrack algorithm I've developed the following backtrack algorithm, and I'm trying to find out it time complexity.

A set of $K$ integers defines a set of modular distances between all pairs of them. In this
algorithm, I considered the inverse problem of reconstructing all integer sets which realize a given distance multiset. i.e. :

Inputs: $D=\{p_i−p_j \mod N, i≠j \},K $

Output : $P=\{p_1,p_2,...,p_K\},\qquad p_i \in \{0,1,2,...,N-1\},\qquad p_i > p_j $ for $i>j$

Simply saying, the algorithm puts $K$ blanks to be filled. Initially, puts 1 in the first blank. For the second blank it looks for the first integer that if we add to P, it doesn't produce any difference exceeding the existent differences in $D$. Then, it does so, for next blanks. While filling a blank if it checked all possible integers and found no suitable integer for that blank, it turns back to the previous blank and looks for next suitable integer for it. If all blanks are filled, it has finished his job, otherwise it means that there weren't any possible $P$'s for this $D$.

Here's my analysis so far.
Since the algorithm checks at most all members of $\{2,...,N\}$ for each blank (upper bound) there is $N-1$ search for each blank. If each visited blank was filled in visiting time, the complexity would be $O((K-1)(N-1))$ since we have $K-1$ blank (assuming first one is filled with 1). But the algorithm is more complex since for some blanks it goes backward and some blanks may be visited more that once. I'm looking for the worst case complexity i.e. the case that all blanks are visited and no solution is found.

The running time of your algorithm is at most $N (N-1) (N-2) \cdots (N-K+1)$, i.e., $N!/(N-K)!$.  This is $O(N^K)$, i.e., exponential in $K$.

Justification: There are $N$ possible choices for what you put into the first blank, and in the worst case you might have to explore each.  There are $N-1$ choices for the second blank, and so on.  You can draw a tree of the choices made: the first level shows the choice of what to put in the first blank, the second level shows the choice of what to put in the second blank, and so on.  The degree of the root is $N$; the degree of the nodes at the second level is $N-1$; and so on.  The number of leaves is the product of the degrees at each level, i.e., $N (N-1) (N-2) \cdots (N-K+1)$.  In the worst case, your algorithm might have to explore every possible node in this tree (if it is not able to stop early before reaching the $K$th level and backtrack from a higher-up node).  Therefore, this is a valid upper bound for the running time of your algorithm.

If you want a tighter analysis, here is the exact worst-case running time (not an upper bound).  The number of leaves in your search tree, in the worst case, is the number of strictly increasing sequences of length $K$ over $\{1,\dots,N\}$ that start with 0.  (We can assume without loss of generality that the first blank contains a 0, as you point out, which is why we can restrict to sequences that start with a 0.)  That number is exactly $C(N-1,K-1) = (N-1)!/((K-1)!(N-K)!)$.

This is a tighter analysis, but it doesn't save us from exponential running time.  When $N\gg K$, $C(N-1,K-1)$ is still $O(N^K)$, i.e., exponential in $K$.

That said, evaluating your algorithm experimentally (by testing it on some real data sets) would probably be a better way to evaluate your algorithm than trying to derive a worst-case running time.  You might want to compare it to the performance of translating your problem into a SAT instance and using an off-the-shelf SAT solver.  Depending upon the value of $N$ and $K$, there might be other better alternatives as well.

See also the following question for a closely related problem, and for algorithms to solve it:

How to obtain the unknown values ai,bj given an unordered list of ai−bjmodN?


Similarity Of Matrices Give a randomized algorithm that takes input two $n \times n$ matrices $A$ and $B$ with integer
entries and does the following: If $A$ and $B$ are similar, then with high probability the algorithm outputs
an $n \times n$ invertible matrix $C$ with rational entries such that $CAC^{−1} = B$; otherwise it outputs $A$ not
similar to $B$. Ensure that your algorithm runs in polynomial time.

I don't get very well the point of the requirement in the problem of a randomized algorithm. Or maybe I am misinterpreting what is the notion of problem size with respect to which the running time is required to be polynomially bounded. With respect to the number of entries of $A$ and $B$ there is the following deterministic algorithm.
The requirement of $C$ having rational entries, or more generally entries in the same field as the entries of $A$ and $B$ points to using the Frobenius/Rational normal form (FNF). The Jordan normal form is inconvenient because, in general, it requires working in a field extension in which the characteristic polynomials of $A$ and $B$ factor completely (split).
Just like in the case of Jordan normal form, there are invertible matrices $P_1,P_2$ such that $P_1AP_1^{-1}=A_f$ and $P_2BP_2^{-1}=B_f$ and $A_f, B_f$ are the Frobenius normal forms of $A,B$, respectively. The additional property that we mentioned before is that all these matrices have entries in the same field as the entries of $A$ and $B$.So, if your matrices have integer entries, then these matrices will have rational entries.
Now, the matrices $A$ and $B$ are similar if and only if $A_f=B_f$. When this happens we can compute the required $C$ from $P_1AP_1^{-1}=A_f=B_f=P_2BP_2^{-1}$, since we get $(P_2^{-1}P_1)A(P_2^{-1}P_1)^{-1}=B$. So, we can take $C=P_2^{-1}P_1$.
The FNF can be computed (without emphasis on efficiency) by considering the polynomial matrices $A-xI$ and $B-xI$ and reducing them to their Smith normal form. This consists in a combination of Gauss elimination (row/column reduction, if you call it that way) combined with Euclid algorithm to compute some polynomial GCDs that are required. The Smith normal form tells you the invariant factors, and then the Frobenius normal form is the block-diagonal matrix in which the blocks are the companion matrices of the invariant factors. The sequence of steps to reduce $A-xI$ and $B-xI$ to their Smith normal forms give you the $P_1$ and $P_2$ required above.
Justifying all these claims requires a long exposition of the linear algebra (and either explicitly or implicitly the structure theorem of finitely generated modules over a principal ideal domain). This can be found in many linear algebra books. One that I know has it is Dummit and Foote's Abstract Algebra.

A guess of how randomization could be used is by trying random vectors $v$ and finding the maximal Krylov subspaces that it generates. This is, the space generated by $v,Av,A^2v,A^3v,...$, which ought to be generated by finitely many of those vectors. Each one of those give you a cyclic invariant subspace of $A$, which tell you a block of the Frobenius normal form. Then pass to the quotient space by this subspace and repeat until you find all blocks of the FNF. Understanding the theory is required again to see why.


A problem is NP-hard iff its complement is coNP-complete $A$ is NP-hard iff $\overline{A}$ is $coNP$-hard, where $\overline{A}$ does mean complement of $A$.

I can't figure out why it is true. Let $A\in NP-hard$. I know that each problem in $NP$ is polynomially reducible to $A$.  So, let's "negate" $A$, then by definition: $\overline{A}\in coNP$.  However, I am not sure why $\overline{A}\in coNP-hard$.  Could you explain it me ?

My intution is that $NP$ and $coNP$ contains only decision problems, using this fact we can use machine for $A$ and negate answer.

This argument is given for any complexity class.

If $C$ is a complexity class (for your question NP) and $L$ is $C-Hard$ (an 'identical' argument can be for complete languages):

If $A \in coC$ so $\bar A \in C$  so $ \bar A \le L$: ($\phi$ is the Karp-reduction for that matter)

$ \exists \phi.x\in \bar A \iff \phi(x)\in L $

Since it's iff the negation is:

$ \exists \phi.x\notin \bar A \iff \phi(x) \notin L$

Hence, (by definition of complementary)

$ \exists \phi.x\in A \iff \phi(x) \in \bar L$

$A \le \bar L \implies \bar L \in coC-Hard$

Negating the answer of an NP Turing machine won't help you to decide a language in coNP (except for trivial cases like language in P), since by definition an NP Turing machine accepts iff there exist an accepting branch in its' computation.

For simplicity, assume your NP Turing machine always has a rejecting branch in every computation (we can assume it for every NP Turing machine, why?), negating the answer will result in the trivial language $\Sigma $* every-time.


Why are the two farthest points vertices of the Convex Hull? I read that in a 2D space, the two points farthest away must be in the convex hull (CH).

Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be a point that is outside the convex hull (contradiction). I know that a vertex of CH has two adjacent edges that converge at that point, which is of further distance from any other vertex or point within CH, than  the non-vertices beside it. What I mean is shown in the image below: a vertex (p) with two adjacent edges,

Problem is, I don't see how I can prove this more formally.  I am looking for a more concrete proof.

Thank you in advance.

Let $p,q$ be two points in your set of points. The point $p$ can be represented as some convex combination $\sum_i \alpha_i p_i$ of points on the convex hull. The triangle inequality gives
$$
\|p - q\| = \left\| \sum_i \alpha_i (p_i - q) \right\| \leq \sum_i \alpha_i \|p_i - q\| \leq \max_i \|p_i - q\|,
$$
where both inequalities used $\alpha_i \geq 0$ and the second also $\sum_i \alpha_i = 1$. We conclude that $p$ can be replaced by some point on the convex hull. Similarly, having replaced $p$ by a point on the convex hull, we can replace $q$ by a point on the convex hull.


Suffix Tree algorithm complexity I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident with it to say so. Well on average we go $\log n$ deep and need at max $|\Sigma|$ steps to find a corresponding node that matches (or not). Thus I would come up with $O(n \cdot |\Sigma| \cdot \log n)$.

  Repeat the following for all suffixes of the given string, right to left.

  Scan if its in tree

  Not in tree -> add it as new node
  Is partly in tree -> fork here, such that the matching part remains

  Go back to step 1 until the sequence that was observed equals the source

There is no one complexity for all suffix tree algorithms.  There are multiple algorithms, with different running times.  It is not helpful to talk about this as though there was only one complexity that applies to all algorithms for computing a suffix tree.  If you want to ask what is the running time of an algorithm for this task, you need to specify which algorithm you are asking about.

There are also multiple different models.  Some algorithms are designed for the regime where $\Sigma=\{0,1\}$ or where you have a small finite-sized alphabet (e.g., $|\Sigma|=256$), where it is reasonable to consider $|\Sigma| \in O(1)$.  Consequently, the running time for those algorithms might not include any dependence on $|\Sigma|$ -- which is reasonable if you assume that $|\Sigma| \in O(1)$.  Other algorithms are designed to work even when the size of the alphabet is large.  For those, the dependence on $|\Sigma|$ is at the heart of the problem.  Therefore, you'll also find some algorithms designed for the large-alphabet regime, and typically the running times that are quoted for those algorithms do show the dependence on $|\Sigma|$.  Therefore, when you read a paper on a suffix tree algorithm, if you want to use the algorithm on a situation where the alphabet size is large, you need to carefully examine the assumptions that were made during the running time analysis.  Does the quoted running time include the dependence on $|\Sigma|$?  Does the paper assume $|\Sigma| \in O(1)$?

Finally, the dependence on $|\Sigma|$ can depend on subtle aspects of how the data structures are instantiated.  Therefore, a high-level description of the algorithm is often not enough -- you often need to know how the tree is represented and how the individual steps are instantiated to tell what the dependence on $|\Sigma|$ will be.

I suggest you read What are the effects of the alphabet size on construct algorithms for suffix trees?

I also suggest you take a look at What is the difference between an algorithm, a language and a problem?, to help you think clearly about the difference between a problem vs an algorithm.


Formal notations of equivalencence between floating point expressions In an informal context, most programmers might call these two expressions "equal" and no one would be mislead:

(a + b) + c
a + (b + c)

For floating point numbers, we know that these two expressions are not strictly equivalent (in the sense that they evaluate to equal values for any a, b, and c) because floating point addition is not associative. Nonetheless, these expressions seem to be similar in interesting and useful ways. For many inputs, these expressions produce nearly equal or equal outputs. The real number counterparts of these expressions are equivalent. In many programming contexts, these expressions can be swapped without concern.

Are there notions of equivalence between floating point expressions that describe this sort of similarity?

Stating simply that the real number counterparts of these expressions are equivalent is a bit too literal to be a useful answer.

One plausible notion of "nearly-equivalent" for floating-point expressions is that the relative error between the two is guaranteed small.

For example, if $x\ne 0$ and $y\ne 0$, define

$$D(x,y) = \max(\left|{x \over y} - 1\right|, \left|{y \over x} - 1\right|).$$

This measures the relative error between two real numbers.  Now, say that $x$ is nearly equivalent to $y$ if $D(x,y) \le \varepsilon$ (for some $\varepsilon$ fixed in advance; e.g., $\varepsilon = 10^{-6}$ or something).

Now, we can define two floating-point expressions e, e' to be nearly-equivalent if, for all possible assignments to the variables of these expressions, we have $D(e,e') \le \varepsilon$.

This implies that replacing e with e' will have only a small effect on the value of the expression (with "small" measured using relative error, rather than absolute error).

With these definitions, if you know that a, b, and c are positive and bounded away from zero, you should be able to prove that (a+b)+c and a+(b+c) are nearly-equivalent, for very small values of $\varepsilon$ (dependent on machine epsilon and the specific floating-point format used).  However, you can't prove them nearly-equivalent when nothing is known about a, b, c, because it is possible that (a+b)+c = 0 but a+(b+c) > 0, and then the relative error is infinite in this case.

Perhaps a more nuanced definition could allow them to be treated as nearly equivalent in the general case; I don't know.  For instance, we could alternatively imagine defining $D(x,y)$ to be the smallest value $\delta>0$ such that
$$\begin{align*}
(1-\delta) x - \delta &\le y \le (1+\delta) x + \delta\\
(1-\delta) y - \delta &\le x \le (1+\delta) y + \delta
\end{align*}$$
(This effectively captures a combination of relative error and absolute error.)  I suspect it might be possible to prove that (a+b)+c and a+(b+c) are nearly-equivalent, under this distance metric.  Is this useful?  I don't know.


Solve a recurrence relation with two recursion calls using the iteration method I can't figure out how to solve this recurrence relation using the iteration method:

$$T(n) =
\begin{cases}
0, & \text{if $n=0$} \\
1, & \text{if $n=1$} \\
3T(n-1)+ 4T(n-2),  & \text{if $n >1$}
\end{cases}$$


Greedy Optimum Dominating Set For A Tree I am trying to figure out a greedy algorithm that finds the optimum (minimum) dominating set for any tree in linear time.

So a greedy algorithm to find a dominating set for a general graph is not optimum. It's an approximation of the optimum dominating set. But since this is a tree I am assuming that a greedy algorithm can give the optimum.

What i have so far is:

Select a vertex with the maximum number of adjacent vertices that are not dominated (that is, it's neighbors are either not dominated by one it its neighbors or they are not a dominated vertex themselves). We add this vertex to the dominated set.

We repeat this proceudue until all vertices are either in the dominated set or are neighbors of one of the dominated vertices.

But I am not sure this will give an optimum solution.

There is a simple dynamic programming algorithm. Root the tree at some arbitrary vertex. For each subtree, compute the optimal dominating set (a) with the root, (b) without the root.


Convert C language code to problem specification by computing the invariant of a program Suppose that you need to give a problem specification of some problem P and you have an implementation of P, in C.

I have 2 questions:

Can you obtain the formal specification of the problem if you compute the invariant of the external for cycle?
What is the relation between the specification and the C code invariant?

You can not reconstruct the specification from just the code.

For one thing, you don't know whether the code is correct or not. For another, there are multiple possible specifications that are all compatible with the code.

For instance, consider the following function:

unsigned int f(unsigned int x) {
    return x+1;
}

Was the intended specification that retval == x+1?  Or that retval > x?  Or that retval > 0?  We can't tell.  There just isn't enough information to know.  (Ignore integer overflow for the moment.)


Are there are problems in NP that have been shown to be not NP-complete but it is still not known if they are in P or not? I am not talking about NP-indeterminate class because those problems have to be shown to not exist either in P or NP-complete class and existence of such problems proves P!=NP. I am interested to know if we are half-way there i.e. problems that have been proven to be not NP-complete but are in NP but we don't know if they are in P as well.

What about such problems whose deterministic polynomial solution was found only recently? Was primality testing such a problem?

I would appreciate if the answers are given for someone like me who only has a high level understanding of computational complexity theory.

Any problem that is provably not $\mathsf{NP}$ complete (w.r.t. polynomial time reductions) would mean that the class of problems reducible to it are distinct from $\mathsf{NP}$. In other words if you show some problem is in $\mathsf{NP}$ but is not $\mathsf{NP}$ complete would imply that $\mathsf{P}$ is not equal to $\mathsf{NP}$.

In short, there is no problem in $\mathsf{NP}$ that we know it is not $\mathsf{NP}$-complete.

Regarding primality and AKS algorithm for it:

Note that the according to the current state of knowledge, it is possible that primality is NP-complete. Existence of a deterministic polynomial time algorithm for a problem does not rule out the possibility of the problem being $\mathsf{NP}$-complete.

You are probably interested in the list of problems that are conjectured to be between $\mathsf{P}$ and $\mathsf{NP}$ (known as $\mathsf{NP}$-intermediate) in which case you can check the answers to Problems Between P and NPC.


Algorithm for grid with obstacles and movement restriction We are given an $n \times n$ grid with some of the squares darkened.

Our goal is to move from the bottom-left to the top-right corner with the following constraints:

1) We cannot step on a darkened square.

2) Each move must be up or to the right.

3) We cannot move in the same direction consecutively four times.

Design an algorithm that runs in $O(n^2)$ time and outputs the set of all squares that can be reached from the bottom-left corner.

My thoughts: We can convert the grid to a graph in $O(n^2)$:  each square (darkened or not) becomes a node, and adjacent squares correspond to edges; each edge is directed either rightwards or upwards. We can then remove the nodes that correspond to darkened squares. At this point, we can BFS or DFS from the top-left node, but we must keep track of condition 3 somehow, with some sort of "cost" array.

Another idea is to "chop off" (this can be formalized) a triangle from the upper left and lower right, which are "too high" and "too right" respectively. But then, the existence of the darkened squares causes some additional squares to be unreachable.

Any help would be appreciated.

You can depict states of the graph as following:
(grid_position,|consecutive_left|,|consecutive_up|)
if you are at state ([2,3],3,0) then you have no other option but to go
up to ([3,3],0,1)

so you have  n^2 * 4 * 4=16*n^2 states=O(n^2) states.
And you can also save some space by noticing that states such as ([x,y],2,1) are impossible.


Efficient rasterisation of vector image with polygons Imagine I have a 2D area where I have many simple polygons ("simple" meaning not self-intersecting, they are not necessarily concave). A polygon is given to me as a series of points. I have between 25 and 150 polygons in my area. I also have several thousand points that I need to figure out if they are inside any of the polygons or not. I need to do this about every second, with a new set of points. The set of polygons stays the same.
I know there are point-inside-polygon algorithms but they seem to be too computationally demanding for the numbers I have, particularly executing on a mobile phone in real time. So an alternative I am thinking is to pre-compute a black and white bitmap of the area (with white areas outside polygons and black inside). One pixel can simply be a single bit. Or you can see the whole thing as a 1D array of true and false values that the whole 2D area maps unto. So using area coordinates x,y  we can access an element in that array and get an answer true/false. This will be considerably faster. The problem then becomes constructing this bitmap. Ideally I want this construction to happen at the phone if it's not too costly. As an alternative the phone can download this bitmap.
So how do I efficiently create this bitmap? I can run the point-in-polygon algorithm for successive "pixels" with the resolution I want, but this seems inefficient for 100K-200K "pixels", and probably rules out the phone processing option. I suspect there are more efficient algorithms than that.  How do the programs convert SVG images to bitmap for example? I googled a bit, but what I get is the much more difficult problem of bmp->svg, also called vectorisation.
Update
Inspired by the D.W. suggestion I expanded it to an answer. I have not implemented it to tell you what kind of savings I might get but it seems a bit expensive. Happy to receive completely different approaches.
Practically what I am currently doing is rasterising an svg file using public tools/libraries. I am doing this outside the mobile phone, and transfer the image to the phone.

An alternative approach is to use a quad-tree.

One approach is to store each polygon in the deepest node that corresponds to a region that wholly contains the polygon.  Given a test point, you traverse the quad-tree, and when you visit a node, you do a point-in-polygon test for each polygon associated with that node.  This then lets you do a smaller number of point-in-polygon tests.

An alternative approach is to continue subdividing each region recursively.  Stop subdividing when a region intersects with at most 2 polygons (or replace 2 with any other constant) or when you have hit some maximum depth, mark that as a leaf node, and associate those polygons with the leaf node.  Given a test point, you traverse the quad-tree until you hit a leaf node, then you do a point-in-polygon test for each polygon associated with that leaf node.  This trades space for time: it uses more space (more quad-tree cells) but uses fewer point-in-polygon tests.

It should be straightforward to build either type of quad-tree.

You can think of a quad-tree as a recursive version of your bitmap idea, where the bitmap is stored in a sparse way (large regions of all-white or all-black can often be collapsed to a single node), and where you have an image pyramid of bitmaps.


What is the difference between "backhaul" and "core" network in cellular networks? I was reading some publications on cellular networks. They constantly mention two similar concepts — backhaul network and core network. I am not sure if these two are the same stuff, or in any way they are different. Does anyone know the differences? thanks!

Let's have a little bit of a glimpse from the diagram below;

What you can analyse in that diagram,is a convention point to point (PTP) and line of sight (LOS), a microwave link uses atail node and aggregation node,which allows remote base station to  access the core network through the backhaul link.

Therefore,backhaul network is a side network which communicates with the core network,i.e. it links packets to and from  the core network.

That said, cellphones also communicates with a single cell tower which constitutes a local network (subnetwork);whereby the link between the celltower and rest of the world(to the core network) begins with the backhaul link. The rest of the world is termed as autonomous network system,which is administered by global internet providers.

A high-level summary is that cellular backhaul refers to transport from remote cell towers to mobile telephone switching offices (MTSO). This backhaul is frequently provided by a third-party internet service provider via layer 2 circuits. The ISP's edge device (optical switch or router) with a customer handoff point (UNI) is located at the cell tower and the network demarcation between the ISP and the cell provider's core network (ENNI) is located at the MTSO. An EVPL (point-to-multi-point) configuration is commonly implemented with both circuits traveling from the tower to the MTSO over divergent paths to provide redundancy.

Hope this can give you some insights.


How can we combine badly trained decision trees to a good one? I was reading about decision trees and this is what I understood:

We build decision trees by choosing an attribute and building subtrees (which are also decision trees) as children of the node representing that attribute. This means that as we go down, in building a decision tree, the no. of training instances that we use to build a subtree decreases. This is because when we build a subtree, we only have to train it using a subset of the original data consisting of instances which satisfy the conditions on the path towards the root node of the subtree.

Now here's the question: We usually believe that if training data is not enough, the model built is incorrect. This would mean that the subtrees down in a decision tree may not be good models (as they were trained using much less data than its ancestors in the tree) and if they are not, how can they be recursively combined to give a full tree which may give a good model? Where is the fault in my reasoning?

Your question is a good one and note that in the extreme case, if every leaf node contains only one data point then you are almost certainly over-fitting and/or missing the "true" dimensions that separate the two points above. One way around this problem is to not split at a node (make it a leaf) if it contains fewer than C points, where C is something like 10. Also, a decision tree in the Brieman/Cutler framework uses $\sqrt{N}$ randomly chosen dimensions to try to split on, at a node with N points. Thus you are somewhat avoiding over-fitting because of this (but it's random so it's not very reassuring). The best solution is to create many (like 100 or more) bootstrap replicates of your data and build a decision tree for each bootstrap replicate. Then for prediction, you run the point through all 100 trees and take the average of the prediction indicator vectors to get predicted class probabilities. You can take the highest probability to be the predicted class. This strategy is much more robust to over-fitting because splits with low data support in one tree will only appear in the majority of trees (either exactly or approximately) if they have higher overall data support.


Efficient subtype testing Languages like Java, C#, Eiffel, and C++ have subtype hierarchies which are directed acyclic graphs, due to interfaces in Java and C# and multiple inheritance in Eiffel and C++. An obvious way to check whether type $A$ is a subtype of type $B$ is to traverse the graph of the subtype hierarchy starting at $A$ to see whether type $B$ appears 'above' it. This surely is not the most efficient way to implement subtype tests.

  What techniques exist to efficiently implement subtype testing for modern OO languages?

I'm interested in efficiency both in terms of time and memory and any trade-offs between the two.

Yves Caseau gave a method for efficiently encoding type hierarchies as bit vectors. See Efficient handling of multiple inheritance hierarchies.


What is the no free lunch theorem? I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about.  I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser exists". On the other hand, the Wikipedia article talks about 'candidate solutions" that are "evaluated one by one" - if we only consider algorithms of a particular form, then that is a much more limited claim.

Can anyone explain what this theorem actually claims?

The No Free Lunch theorem (NFL) was established to debunk claims of the form:

  My optimisation strategy X is always best.

In particular, such claims arose in the area of genetic/evolutionary algorithms.

The statement is, roughly: every optimisation strategy performs badly on many problems. Therefore, there can be no always-best strategy and your claim about X is wrong.


Relationshop between Theta and little-o (Big-O notation) Is
$$
f(n) \in \Theta(g(n)) \Leftrightarrow f(n) = g(n) \cdot (1+o(1))
$$

true?

For clarity, here are the definitions I use:
$$
f(n) \in o(g(n)) \Leftrightarrow \forall \epsilon > 0 \exists n_o\forall n> n_0: |f(n)|\leq \epsilon \cdot |g(n)|
$$
$$
f(n) \in O(g(n)) \Leftrightarrow \exists c > 0 \exists n_o\forall n> n_0: |f(n)|\leq c \cdot |g(n)|
$$
$$
f(n) \in \Omega(g(n)) \Leftrightarrow \exists c > 0 \exists n_o\forall n> n_0: c \cdot |g(n)| \leq |f(n)|
$$
$$
f(n) \in \Theta(g(n)) \Leftrightarrow f(n) \in \Omega(g(n)) \land f(n)\in O(g(n))
$$

What I have so far:

The $\Leftarrow$ direction is quite easy:

$$
f(n) \in o(g(n)) \Rightarrow f(n) \in O(g(n)) \land g(n)+o(1)\cdot g(n) \in \Omega(g(n))
$$

However, I am unsure about the other direction. I suspect that it's not, but can't proof it.

PS: This is not a homework assignment, but homework related: I am working on a seminar paper and want to understand this.

To expand slightly on Karolis's comment, you can get a counterexample by taking for any strictly positive function $f$ and, for any constant $\delta>0$, the function $(1+\delta)f(x)$.  $(1+\delta)f(x)\in \Theta(f(x))$ but $(1+\delta)f(x)\notin (1+o(1))f(x)$ since, for $\epsilon<\delta$, it is not true that $(1+\delta)f(x)\leq (1+\epsilon)f(x)$.


Clique decision problem restricted to a subgraph I know that the clique problem is NP-complete.

However, what if we change the problem a little bit?

For example,

Given a graph $G(V,E)$, an integer $k$ and a subset $S$ of $m$ vertices, we are given a decision problem to find a clique with size $k$ contained within $S$.

A real world example would be something like a social networking graph. Where each node is a person and an edge represents that they are friends with each other. Now what if we were to find clique with size $k$ amongst the set of teenagers.

Does that change the complexity? Since we are only looking into a subgraph, e.g. less vertices to look for?

Thanks!

Formally, time complexity is defined as

  Let T : N → N. A Turing Machine M has time complexity T(n) if $∀ x ∈ \{0, 1\}^*$
  , M(x) halts in at most T(|x|) steps.

That is to say, time complexity captures the (relative) amount of time taken for all inputs.

Thus the answer is no, that doesn't change the time complexity at all, because then you would just have an instance of the question: Given a graph $G(V',E)$, where $|V'| = m$, and an integer, $k$, determine if a clique with size $k$ exists.

As $m$ increases, the running time would increase in the way similar to how it would if |V| increases in the original problem.

However, if $m$ is defined to be a constant, then the time-complexity would be $O(1)$ (the TM would halt in at most x steps no matter what the graph is) but the problem itself would not make any sense

  Given a graph G(V,E), and k-integer, determine if a clique with size k exists after checking m vertices, where m is a constant.

because a decision problem is formally defined in terms of set-membership, and a different algorithm (a different way to finding if a clique exists) would yield a different result, for $|V| > m$.


Decrypting transposition ciphers How do I see if the following ciphertext eaeairtntrnaeemtve is a transposition cipher, using letter frequency?

This article suggest how to detect by using letter frequency detection and cryptanalysis but I am unsure of how to do this. Any suggestions?

It is impossible to do cryptanalysis on such a short message. It could be anything, encrypted with anything. Even if you somehow knew that it's a substitution cypher, it could be any 18-character message where the right characters match (there must be seven different letters; characters 1, 3, 13, 14 and 18 have to be the same; characters 1 and 2 must be different, etc.).

If you had a longer cyphertext (say a few hundred characters), you'd just compute the frequency of the characters appearing in the cyphertext and compare that to the frequency of the letters in the language you think the message was written in. The frequencies in English are: e 12.7%, t 9.1%, a 8.2%, o 7.5%, i 7.0%, n 6.9%, etc. If a decently long cyphertext comes decently close to that distribution, you'd expect a transposition cypher.  If you only have that the most common characters occur about 13%, 9%, 8%, 8%, 7%, 7%... of the time, you'd suspect a substitution cypher and you'd start guessing the letters based on their frequency. Note that the process is not automatic and you need to be flexible: for example, if the message is about the Zulus playing zithers in zoos in Zanzibar, the letter frequencies may be skewed quite some distance from the average over all English text.


If $L^*$ or $L^+$ is empty, can L be an infinite language? I have to prove or disprove the implications in these two situations

$L^* = \emptyset$ $\rightarrow$ $L$ is infinite
$L^+ = \emptyset$ $\rightarrow$ $L$ is infinite

Here are my thoughts.

I would say Kleene star operation (*) is union of

$\qquad L^0 \cup L^1 \cup L^2 \cup \dots$

and since $\_^0 = \{\epsilon\}$ (even $\emptyset^ 0 = \{\epsilon\}$), there is no language $L$ such that $L^* = \emptyset$.

How to prove finiteness/infiniteness?
Only language $L$ where $L^+ = \emptyset$ is $\emptyset$ which is a finite language. But how to prove there is no other language that is inifinite and the argument is valid for it?

EDIT: will it help if I rewrite the implications $A \rightarrow B$ to $\neg B \rightarrow \neg A$ ?

$L$ is finite $\rightarrow$ $L^* \neq \emptyset$
$L$ is finite $\rightarrow$ $L^+ \neq \emptyset$

2) can be now interpreted as $\emptyset^+ = \{\epsilon\}$ and $\emptyset$ is a finite language. So the implication doesn't work.

1) You need to take a look at this page. Remember that there is an implication to be proved true or false.

2) Consider the fact $L \subseteq L^{+}$ and apply it to the case $L^{+} = \emptyset$.


Does rice theorem applies to languages only or does it apply to machines as well? Rice theorem says that any non trivial property of a language recognized by a Turing Machine is undecidable.

Now does this theorem applies to machines as well since we can define a language consisting of strings which are encoding of machines?

For example whether a machine will run more than 100 steps on some input? This is nontrivial but wikipedia says it is decidable.

The Rice's theorem can also be stated in terms of index sets of TMs.

Lets start with a basic definition of a property of a language. A property of a language is a set of languages. For example $$P_{reg} = \{L \mid L \text{ is regular } \}$$ and $$P_{fin} = \{L \mid L \text{ is finite } \}$$ are properties of languages.

We also define a language of indexes as
$$L_P = \{\langle M \rangle\ \mid L(M) \in P\}$$
In simple words, a set of TM indexes such that the language recognized by $M$ belongs to the property $P$. Now, the Rice's theorem states that if $P$ is nontrivial then the problem whether $n \in L_P$ is undecidable, i.e., $L_P$ is undecidable.

However, we cannot apply it to the following sets
$$L_1 = \{\langle M \rangle\ \mid M \text { has } 5 \text{ states} \}$$
and
$$L_2 = \{\langle M \rangle\ \mid M \text { never writes to the tape} \}$$
since they talk about properties of Turing machines and not languages (we cannot say a language $L$ has 5 states). They may be decidable or not which may be proved the other way (not using the Rice's theorem). For example, $L_1$ is decidable since you simply count the number of states of a TM.

So, the answer to your question

  does this theorem applies to machines

depends on what set of TMs you are talking about. If this is a set of TMs whose recognizing languages belong to some nontrivial property of a language then the answer is "yes", otherwise the answer is "no".


What is a dichotomy? Whether 2-SAT itself is a dichotomy of SAT? Recently, I am reading papers about dichotomy. I do not understant what condition can be called as a dichotomy? What is the meaning of "a question is either in P or in NP-complete"? (assume P $\neq$ NP)

For example, I've known the Schaefer's dichotomy theorem, in which a dichotomy about "whether a class of SAT is in P" is given. In this theorem, the dichotomy contains six conditions, one of them is "2-SAT".

So my question is that, whether "2-SAT" itself can be called as a dichotomy or a trivial dichotomy, because 2-SAT is in P but 3-SAT is NP-complete? In another words, I wonder that "if a special class of an NP-complete problem is in P, then this class is a dichotomy? or a trivial dichotomy?"

A (coarse) dichotomy theorem states that in a certain class of problems, each problem is either in P or NP-hard. For example, Schaefer's dichotomy theorem concerns the class of problems of the form $\mathrm{SAT}(S)$. Here $S$ is a collection of Boolean relations, and $\mathrm{SAT}(S)$ is the problem of deciding satisfiability of propositions which are conjunctions of relations from $S$. This is best explained by an example. The problem 2SAT is $\mathrm{SAT}(S_2)$ with $S_2$ consisting of the following three predicates:
$$ (x,y) \mapsto x \lor y, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y. $$
That is, each instance of 2SAT is a conjunctions of clauses of one of these three forms, where you can substitute any variables you want for $x,y$. As another example, HORNSAT is $\mathrm{SAT}(S_H)$ where $S_H$ is the following infinite collection:
$$\begin{gather*}
x \mapsto x, \quad x \mapsto \lnot x, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y, \\
(x,y,z) \mapsto x \lor \lnot y \lor \lnot z, \quad
(x,y,z) \mapsto \lnot x \lor \lnot y \lor \lnot z, \\
(x,y,z,w) \mapsto x \lor \lnot y \lor \lnot z \lor \lnot w, \quad
(x,y,z,w) \mapsto \lnot x \lor \lnot y \lor \lnot z \lor \lnot w, \ldots
\end{gather*}$$
Schaefer's dichotomy theorem states that for each finite $S$, the problem $\mathrm{SAT}(S)$ is either in P or it is NP-complete (this is a dichotomy since there are only two possibilities). For example, 2SAT and $k$-HORNSAT are in P for every $k$, while 3SAT is NP-complete. This is surprising since if we believe that P$\neq$NP then Ladner's theorem shows that there are intermediate problems - problems which are neither in P nor NP-complete. Schaefer's theorem shows that these problems cannot be of the form $\mathrm{SAT}(S)$.

A more refined version of Schaefer's theorem states that $\mathrm{SAT}(S)$ is either in co-NLOGTIME, L-complete, NL-complete, $\oplus$L-complete, P-complete or NP-complete. In the past few years, countless generalizations of Schaefer's theorem have been proven or conjectured, including results about counting solutions and approximating the maximum number of satisfiable clauses, as well as results over non-Boolean domains. The main conjecture is the Feder-Vardi dichotomy conjecture which states that Schaefer's theorem holds for relations on an arbitrary finite-sized domains. For the status of Schaefer's original theorem in the case where $S$ is infinite, see this question.


top k selection in fixed size priority queue with dynamically changing values My question is something of a scheduling problem. I'd like to know what algorithm to use to find the top k items in a fixed length queue in which the values of the items change dynamically.basically a long running online top k selection

I imagine that operating systems do this all the time, but not being a systems guy, I don't know what terms to search for. Thanks in advance.

The problem is known as partial sorting. Wikipedia gives various algorithms, using heaps and so on.


Why is this not a valid Red-Black tree? I'm having some difficulty understanding the rules for valid red-black tree.
If my understanding is correct there are 4 rules that a tree has to follow to be a red-black tree.

Every node has a color either red or black.
Root of tree is always black.
There are no two adjacent red nodes (A red node cannot have a red parent or red child).
Every path from root to a NULL node has same number of black nodes.

So I drew the tree below in a quiz, and apparently it's not valid. Could someone tell me why this tree is invalid?

Thank you!

If you go to the empty leaf from the root in the pattern [Right, Left], you get to an empty leaf encountering 1 black node. If you go [Right, Right, Left] or [Right, Right, Right], you get to an empty leaf hitting 2 black nodes. This is not allowed in a Red Black Tree because by definition a path from root to an empty leaf should contain the same amount of black nodes as every other path from root to an empty leaf.

The other important thing to know is that NULL nodes (leaves) aren't drawn; only the internal nodes are drawn.  By convention, all leaves (NULL nodes) automatically are considered to be colored black.


Logic Question - Why is This an Implication? I have a question about predicate logic. Suppose we have the following predicates:

$\text{Study}(x,y)$: x studies y

$\text{Comp}(x)$: x is a computing student

I want to encode the following sentence in predicate logic: "Some, but not all computer students study logic."

A potential answer is:

$$\exists x(\text{Comp}(x)\land \text{Study}(x,l))\land\neg \forall x(\text{Comp}(x)\implies \text{Study}(x,l))$$

Why is there an $\implies$ and not a $\land$? Is this formulation correct?

Because $\neg\forall x\,(\text{Comp}(x) \wedge \text{Study}(x,l))$ means "It is not true that every student is both a computing student and studying logic." In particular, that would be true if there is at least one student who is not a computing student, regardless of whether all computing students do or do not study logic.


Context free grammar for nested arrays separated by commas I have to define a context free grammar for the following rules:

(i) A pair of square bracket tokens [] surrounding zero or more values separated by commas.
(ii) A value can be another array or a number.

A number is represented by the token NUMBER. So for example, [NUMBER, [NUMBER, NUMBER], NUMBER]. is valid.

I am stuck as how to approach this.

My intuition is always to look at the question and see that S->LSQ VALUE RSQ, VALUE->VALUE COMMA VALUE | VALUE | ARRAY | e | NUMBER, ARRAY -> LSQ NUMBER RSQ, NUMBER ->NUMBER. But I know this slips up.

What steps can I take to ensure I am always thinking in the right way?

your current implementation doesn't enforce the first condition "A pair of square bracket tokens [] surrounding zero or more values separated by commas" as an empty string or a NUMBER on its own would be accepted by the grammar.

You could use the following CFG to maintain the integrity of the constraints

array ::= [ ] | [ element ]

element ::= value | value , element

value ::= array | NUMBER

To derive [NUMBER, [NUMBER, NUMBER], NUMBER]

Start with array -> [element]

[ element ]
[ value, element ]
[value, array ]
[value, value, element ]
[value, array, value]
[value, [element], value]
[value, [value, element], value]
[value, [value, value], value]
[NUMBER, [NUMBER, NUMBER], NUMBER]

The grammar rules provided for JSON here might also be a useful reference: http://json.org/


Invariant Proof of For Loops? From CLRS (third edition, page 19), there is a footnote:

  When the loop is a for loop, the moment at which we check the loop invariant just prior to the first iteration is immediately after the initial assignment to the loop-counter variable and just before the first test in the loop header.

Why is the checking moment specifically chosen to be after the initial assignment but before the first test? Note the excerpt is talking about proving correctness of algorithms using loop invariants.

The loop invariant probably involves the loop control variable.  If so, it only makes sense to ask if the invariant is true, when the loop control variable is initialized. When the loop control variable is uninitialized, expressions that involve it are undefined.

Consider a simple example, a loop whose purpose is to determine whether all the elements of a (0-based) array $a$ are equal:

   all_equal = true
   for (i = 1; i < a.size; i++)
      if a[i-1] ≠ a[i]
         all_equal = false

Here the loop invariant is that $all\_equal$ is true if and only if the $a[k]$ are all equal for each $k$ with $0 \le k \le i$.

This is makes no sense at all unless the loop control variable $i$ has a well-defined value.  Before the initialization, it doesn't. After the initialization, we have $i=1$, and the loop invariant is true.


Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$ I'm having trouble constructing a Context Free Grammar for the following language:
$$a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$

I believe it's telling me that no string can be generated that has the same number of of $a$'s $b$'s and $c$'s.  This is due to the subtraction of the second set.

A good string from a newly formed language should be something like $aaabbc$ or $abbbcc$ and so on.

So I tried breaking the problem into three parts...

Single states:

$S_{1} \rightarrow aS_{1} \mid a \mid \lambda$
$S_{2} \rightarrow bS_{2} \mid b \mid \lambda$
$S_{3} \rightarrow cS_{2} \mid b \mid \lambda$

Two States

$S_{4} \rightarrow aS_{4}b \mid S_{1} \mid S_{2}$
$S_{5} \rightarrow bS_{5}c \mid S_{2}$
$S_{6} \rightarrow aS_{6}c \mid S_{3} \mid S_{1}$

States w/AB states

$S_{7} \rightarrow S_{1} \mid S_{4}S_{6}$
$S_{8} \rightarrow S_{2} \mid S_{5}S_{6}$
$S_{9} \rightarrow S_{3} \mid S_{6}S_{3}$

with an orginal start state of   ...

$$
S \rightarrow  S_{7} \mid S_{8} \mid S_{9}
$$

However I'm having problems building strings like $aaaabbbcc$ ...

Am I forming CFG's incorrectly?  I felt like I was on the right track but now I'm quite lost.

This question has been answered before, but let me summarize the answer:
$$
a^*b^*c^* \setminus \{ a^n b^n c^n \} = \\
\{ a^{n+1+m} b^n c^p \} \cup \{ a^n b^{n+1+m} c^p \} \cup \\
\{ a^{n+1+m} b^p c^n \} \cup \{ a^n b^p c^{n+1+m} \} \cup \\
\{ a^p b^{n+1+m} c^n \} \cup \{ a^p b^n c^{n+1+m} \}.
$$
All parameters $n,m,p$ are assumed to be non-negative.


Is it possible that $\mathsf{L} = \mathsf{NP}$? When I studied computer science 10 years ago, it was still an open question whether $\mathsf{L}$ and $\mathsf{NP}$ are truly different classes. Is that still the case or has the inequality been proven in the meantime?

(I know this is a somewhat stupid question, but there's nothing about it in the complexity zoo, and googling L and NP is surprisingly ineffective ;-))

$L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP$

From space hierarchy and time hierarchy theorems we can prove that

$L \subsetneq PSPACE$

$NL \subsetneq NPSPACE$

Note that we know $PSPACE = NPSPACE$.

$P \subsetneq EXP$

$NP \subsetneq NEXP$

Note that we don't know if $EXP \subsetneq NEXP$.

Whether the other inclusions are strict, are still open problems. Even though there are no proofs, many, but not all, believe most of the inclusions to be strict.


Efficiently storing and modifying a reorderable data structure in a database I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each item, but with the reordering requirements, that would mean renumbering everything with a higher order (down the list) than the place where you removed or where you inserted the moved item. So I started looking at data structures that were friendly to reordering, or to both deletion and insertion. I'm looking at binary trees, probably red-black trees or something like that. I feel like I could with great effort probably implement the algorithms for manipulating those.
So here's my actual question. All the tree tutorials assume you're creating these trees in memory, usually through instantiating a simple Node class or whatever. But I'm going to be using a database to persist these structures, right? So one issue is how do I represent this data, which is kind of a broad question, sure. I would like to not have to read the whole tree from the database to update the order of one item in the list. But then again if I have to modify a lot of nodes that are stored as separate documents, that's going to be expensive too, even if I have an index on the relevant fields, right? Like, every time I need to manipulate a node I need to actually find it in the database first, I think.
Also, I obviously need the content and order of each node on the front end in order to display the list, but do I need the client to know the whole tree structure in order to be able to send updates to the server, or can I just send the item id and its new position in the list or something?
I'm sorry if this veers too practical but I thought someone might want to take a crack at it.

There are two questions here:

How do you implement a pointer data structure such as a red-black tree in a database?
Should you implement a pointer data structure in your database to solve this problem in practice?

The answer to (1) is easy: add arbitrary IDs to each of your items and use those when you need to store a "pointer" to an item. For example, to implement red-black trees in a typical relational database, you would have a table with one row for each node, with the following columns:

an autoincrement non-nullable integer primary key column, storing the node ID
three nullable integer columns, storing the left, right, and parent node IDs
a non-nullable bit column, storing the red-black flag
columns for whatever actual data is associated with each node

And then you would have a table with one row for each tree, with an integer column pointing to the root node for that tree.
As for (2): if your lists are less than a few thousand elements, it's definitely likely—as @D.W. points out—that the best way to store the ordering in a database is not to do the above. Skip the pointer columns and just give your table of lists a blob column that stores that list's item IDs in order as a series of 2-byte or 4-byte ints. When your app wants to show the list, it reads the entire blob for that list; when it wants to reorder a list, it overwrites that list's blob with an entire new blob. [*]
If your lists are large enough, you might want to start profiling different options' performance. But you mention a drag-and-drop UI, and such UIs are rarely amenable to reordering lists longer than even a few dozen elements.
[*] Implementation note: If you go with this option, make sure you have another column on the items tracking which list each item belongs to, rather than just using a single autoincrement ID column. Otherwise, repeatedly creating and deleting lists could overflow your IDs even if each individual list only has a few items in it!


Point and Application of Recursive and Recursive Enumerable Languages What is the point and application of recursive and recursive enumerable languages. Finite Automaton is used for pattern matching, designing computer architecture and protocols, CFG is used for designing compilers but what about Recursive and Recursive enumerable languages?

Recursive languages correspond to whatever can be computed in your favorite programming languages. Recursively enumerable languages correspond to whatever can be enumerated in your favorite programming languages — for example, all provably true mathematical theorems.

Your question assumes a particular list of canonical language classes, including four classes: regular languages, context-free languages, recursive languages, and r.e. languages. However, this list is rather arbitrary, and it omits modern complexity classes, including the all-important classes $\mathsf{P}$ and $\mathsf{NP}$.

The class $\mathsf{P}$ is intended to capture what can be computed efficiently (whether it succeeds in this goal is another question). The class $\mathsf{NP}$ captures problems which can be solved using "exhaustive search", that is, SAT solvers, IP solvers, and the like.

It turns out that $\mathsf{NP}$ captures many natural combinatorial problems, many of which are "equally hard". This leads most researchers to think that these "equally hard" problems are actually hard, that is, cannot be computed efficiently, a conjecture known as $\mathsf{P} \neq \mathsf{NP}$.

Computational complexity theory mentions many other complexity classes of interest. Practically speaking, a relevant class of languages are those which can be decided in quasilinear time (broadly construed) in the RAM machine model. This class roughly corresponds to problems which can be solved in practice even on "big data".


If p(n) is a polynomial in n, then is 1/p(n) polynomially bounded? This is part of a homework exercise. Given is an algorithm that errs with probability $\frac{1}{2}-\frac{1}{p(n)}$ for some polynomial in the input size $n$. I'm trying to prove that a polynomial number of repetitions is sufficient to reduce the error probability to $\frac{1}{2^n}$.

Using the Chernoff bound I derived that $k \geq \frac{2n \ln(2)}{\bar{p}-1+\frac{1}{4\bar{p}}}$ with $p = \frac{1}{2}+\frac{1}{p(n)}$ repetitions is sufficient. However, I'm having a difficulty in showing that this quantity is polynomially bounded. Could someone shine some light on this?

In order to estimate the lower bound on $k$, you use the estimate $1/(1+\epsilon) = 1-\epsilon+\Theta(\epsilon^2)$, which is true as $\epsilon\to0$ (which is certainly your case). Using this, we can analyze the denominator:
$$
\begin{align*}
\bar{p}-1+\frac{1}{4\bar{p}} &= \frac{1}{p(n)}-\frac{1}{2}+\frac{1}{2}\frac{1}{1+2/p(n)} \\ &=
\frac{1}{p(n)}-\frac{1}{2}+\frac{1}{2}\left(1 - \frac{2}{p(n)} + \Theta\left(\frac{1}{p(n)^2}\right)\right) \\ &=
\Theta\left(\frac{1}{p(n)^2}\right).
\end{align*}
$$
Therefore the lower bound on $k$ is of order of magnitude $$\Theta(np(n)^2).$$


Tarjan's Algorithm failure case, what am I missing? I'm having a little trouble with Tarjan's Algorthm.

So here's my problem:  I have a graph such that these nodes are directionally-connected as shown:

A: B C D E
B: D E
C: B D E F
D: C E
E: B
F: A B D E

My problem is Tarjan's Algorithm never revisits nodes, apparently.  If the node isn't on the stack, it's not checked.

So here's what's happening:

My algorithm is going A, D, E, B.  B checks D.

A(id=0, link=0), D=1, E=2, B=3
-> D is visited, D is on stack, D's id is 1, B(id=3, link=1)

Cute.  B checks against E (cycle—it's a tie), which has an ID of 2, and is on the stack, no change.

B is out of neighbors, doesn't have a neighbor, returns out of the recursion so E can continue.

E, upon return from DFS of B, checks B's low-link value.  It's lower, so E's low-link value becomes 1.

A(id=0, link=0)
B(id=3, link=1)
C(undefined)
D(id=1, link=1)
E(id=2, link=1)
F(undefined)

Now return to D.  D's id and low-link value are 1, so no change.

Now here's the fun part.

D proceeds to check C.  C checks F.  F checks A, which has been visited and is on the stack.  A has an ID of 0, so D updates.

F(id=5, link=0)
C(id=4, link=0)
B(id=3, link=1)
E(id=2, link=1)
D(id=1, link=0)
A(id=0, link=0)

A proceeds to check the rest of its neighbors.  B and D have higher link values and IDs and are on the stack, so A doesn't update.

Every node has been visited.

There's a path from D to E to B to D, meaning those are part of the same SCC (in fact, all of these are in the same SCC—it's one SCC).

The stack is {A, D, E, B, C, F} with F at the top.

The two SCCs are {B,E} and {A,C,D,F}.

…you can reach A from B, and you can reach B from A.

What am I missing here?

Answer:  the low-link value is not the identifier.  I eventually found this while researching during the writing of this question.  Question posted because I wrote it and hey, maybe this will help someone else.

Everything up to the current node is popped off the stack when identifying an SCC.  My misunderstanding was trying to pop only what has the same low-link value.


Space complexity problem, relation between $DSPACE(log^kn)$ and $DSPACE(log^{k+1}n)$ I need help with the following:
Let $k\in \mathbb{N}$, define:
$L^k=DSPACE(O(log^k(n)))$
$NL^k=NSPACE(O(log^k(n)))$
and:
$PolyL=\bigcup_{k=1}^{\infty}L^k$
$PolyNL=\bigcup_{k=1}^{\infty}NL^k$

I need to prove, disprove or to determine if it is an open question:
1. For every $k\in \mathbb{N}$ it holds that $NL^k\subseteq L^{2k}$
2. There exist $k\in \mathbb{N}$ s.t. $L^k=L^{k+1}$

The first one is easy, since it is almost immediately the result of Savitch's theorem.
The second one I'm not sure...  I'd love to get some lead there.

Use the space hierarchy theorem, which is a finite form of the undecidability of the halting problem.


Division modulo a prime in modular arithmetic I am looking for a way to implement division in modular arithmetic using modulo prime.

The method I found in math books is to try $u$ such that

$au \equiv 1 \pmod{p}$

$b/a \equiv bu \pmod{p}$

where $a, b, u \in Z_p$ (remainder class modulo a prime $p$). But trying things is probably not a good and fast approach (as it seems to me it has linear complexity and my $p$ can be big, up to $10^9$). What is the right way to do division in modulo prime?

To divide $b$ by $a$, you follow two steps: first you find $u$ such that $au \equiv 1 \pmod{p}$, and then you compute $bu \pmod{p}$. To find $u$, you run the extended GCD algorithm on $a$ and $p$. If it is indeed the case that $a \not\equiv 0 \pmod{p}$, then since $p$ is prime $(a,p) = 1$. So the GCD algorithm will come up with numbers $u,v$ such that $$ au + pv = 1. $$ In other words, $au \equiv 1 \pmod{p}$.


What's the difference between physically based rendering and global illumination? I know that Physically based rendering means we try to simulate how light actually works in real world and global illumination is bouncing back of light when it strikes a surface. But what's actual difference between them and how are they related?

The two terms are, in a sense, orthogonal.

Global illumination refers to any process which simulates indirect lighting. Indirect lighting occurs when light bounces off surfaces or through media. The opposite of global illumination is local illumination, where only illumination directly from light sources is taken into account.

Physically-based rendering is a loosely-defined term, but the general idea is to model lighting, surfaces, and media in a way that is physically plausible. This includes, for example, ensuring conservation of energy, so that the solution to the light transport equations don't blow up.

Generally speaking, PBR can be thought of as a type of GI, but this isn't always the case; it's possible to use physically-based rendering without trying to solve the whole rendering equation. Moreover, PBR doesn't always try to model light exactly; quantum mechanical phenomena such as coherence and polarisation aren't commonly modelled (or are only coarsely modelled) in typical rendering methods.


Monitoring files in preservation archives What are efficient and accurate techniques for monitoring the recoverability and integrity of files in very large preservation archives?

In very large archives, the time taken to recompute checksums periodically (scrubbing) is substantial, perhaps taking more than all the available time depending on the read bandwidth available! Also, each access to a preserved file increases the risk of damage due to hardware or software failure. Tapes are most stable in a cold, dark place far from exposure to the hazards of data centers. Disks are most at risk when the read/write head is flying close to the medium. All approaches are probabilistic, so which are most efficient and accurate?

To give the problem specificity, let's assume a fixed probability of local single-bit errors for each medium (one probability for tape, another for disk, SSD, etc) during a standard time period, and ignore all other types of errors (loss of an entire volume, for instance). We can also assume a fixed read bandwidth for each medium.

This is not an answer to the question per se, but an extended comment.

There was an interesting set of slides regarding CERN's Advanced Storage (CASTOR) at CHEP'2010. This is a large mixed media archive with some 25 PB of tape archives (ca. 2010). One of the presentations: "Tape archive challenges" highlights some of the issues that seem to question the assumptions set in the OP.

  Tapes are most stable in a cold, dark place far from exposure to the hazards of data centers.

Not quite. Even if you have a controlled environment in the tape storage you should expect a very small percentage of the tapes to fail. Therefore it makes sense to keep repacking the data constantly. Also older tape drives may fail making the data on old tapes inaccessible.

The latter reason makes archivists keep copying tapes at a much higher rate than their physical life span would suggest. Marty Perlmutter, "The Lost Picture Show: Hollywood Archivists Can't Outpace Obsolescence".

  Disks are most at risk when the read/write head is flying close to the medium.

When the disk is spinning it constantly monitors itself for errors due to wear and errors due to defects in the manufacturing process. While rotation increases the probability of an error it also through predictive failure analysis reduces the chance of an error to occur undetected. On the contrary, as a mechanical unit a disk that was stored on a shelf might just fail to spin up.

A probabilistic approach to consistency checking has to be aligned with the statistical thresholds set for different actions. Suppose that a probabilistic model says that with probability 50% there is one error for a 1000 cartridges in a tape library. Does it give any hint on the possible action but to check consistency for the complete archive in order to find the possibly damaged part so that it can be rebuilt.

Many papers with statistical models of reliability of computer systems based on queuing theory have this problem. While they provide formulas to quickly estimate parameters of computer systems they often rely on some generic assumptions that may or may not apply in a particular setting.


Did Date and Darwen's "Third Manifesto" have a lasting impact? In 1995, two DB theory researchers, C.J. Date and H. Darwen, published a text with the rather impressive-sounding name "The Third Manifesto" with their ideas regarding future DBMSes, which would better harmonize a relational model with object-oriented programming, including user-defined types.

It is my understanding that object-relational DBMSes has been mostly/entirely abandoned as a subject of research. So, has this manifesto had a significant impact on the DBMS world community over the past 23 years? If so, what are the salient aspects of this impact?

Hmm, before some moderator closes this q as being a matter of opinion, not substance ...

I think you need to consider whether the first two manifestos (to which TTM was a response) had any impact? I'd say little or no: there were a few OODB ideas that made it into the SQL standard (but were little implemented). There are a few niche commercial products that claim to be OODBMSs. But mostly the industry has stuck with SQL tables; and applications or development tools provide an ORM layer (Object-Relational Mapping).

A comparable question: have 'Codd's 12 Rules' had a significant impact on the DBMS world? I'd say not much, even though most industry practitioners would at least be aware of them.

Hugh Darwen, by the way, is not principally a "DB theory researcher". He was part of the UK development team for an early IBM relational system Business System 12 -- which arguably was more relational than SQL has ever achieved [**]; and he was IBM's representative on the SQL standard committee for many years. He only lately moved into academe. His first draft of TTM was a visceral reaction against the fulminations of the SQL committee, written while he was at one of their plenaries.

Chris Date, IMO, is not much of a researcher either: he's more of an educator and writer of textbooks. I'm unconvinced he's added much to the research rigour of the TTM document.

Apart from that, your q seems to me to show many confusions.

If you read TTM (and the supporting explanations), I see no intent to "harmonise" with OOP. Note that an OODBMS is not aimed purely at OOP's: it's aiming to support notions of encapsulation of data. TTM's claim is that a Truly Relational DBMS already includes sufficient means to encapsulate data -- including under the Liskov/Wing Substitution Principle; and that SQL has bastardised the applicability of the Relational Model. Separation of concerns is principally to be achieved through schema design; we don't need perversion or subsumption of the Relational Model.

What has support for user-defined types got to do with it? Any modern language in any paradigm has those. The usual catchcry is 'types are orthogonal to the model'.

A large part of the TTM Prescriptions and Proscriptions are taken up not with opposing OODBMSs, but opposing SQL. Has TTM had a "significant impact" on SQL? I'd say no: SQL has continued to get worse and worse. Each revision of the standard has retained all the old awfulness (due to the shackle of backwards compatibility); has added new awfulness; and has multiplied up the effective awfulness in trying to support multiple 'features' that are in tension.

There are a few products that have attempted to implement TTM's ideas -- see "Projects" linked from the TTM website. I'd describe them as 'hobby products' developed and supported by individuals -- individuals who are rather cranky, strongly opinionated and difficult to deal with IMO. I would never recommend anybody use these products. (And for that reason, I'm not going to suggest you go ask your question at the TTM forum. You have been warned.)

[**] The more I discover about BS12, the more impressed I am by how much it got right even when the Relational Model was very far from mature. How come it was killed off but SQL continued? IBM internal politics, plus commercial pressure: Larry Ellison stole some significant brainpower from the IBM System/R research team (who arguably never understood what Codd was talking about); they re-implemented at Oracle what had been only a prototype at IBM; then commercial pressure resulted in a race to get 'something' to market, and never mind the quality. Mike Stonebraker/Ingres did originally try harder to follow the model, but eventually had to cave to commercial pressure.


Choosing a random bit from a bitmap Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so.

I have quite a large bitmap (~100 Million bits) (e.g. 100100101001010001001...010010). The bitmap is just an example, it doesn't have to start with 1 or end with 0.

Now, I need to choose randomly any 0-bit from the bitmap and retrieve it's position. Memory is not an issue in my case, I can maintain a few copies of the bitmap, if necessary. But the acceptable complexity of the  algorithm would be linear or O(n lnn) in the worst case. Couldn't you advice a direction to move to? I'll appreciate any advices or refernces to some related resources.

There is a simple $O(n)$ algorithm using the technique of reservoir sampling. Keep a currently selected element $x$ (initially, none). Go over all bits in the file in order. When seeing the $m$th zero, put it in $x$ with probability $1/m$. You can show (exercise) that the final contents of $x$ is a uniformly random zero from the file.

If you are allowed preprocessing, you can store the locations of all zeroes in a new file, and then choose a uniformly random zero in $O(1)$ by choosing a uniformly random position in the list.

Practically speaking, we expect bitmaps to contain a decent fraction of zeroes – say at least 1%. This suggests querying uniformly random locations in the file until you reach a zero. The expected runtime of this algorithm is at most 100 random queries.


A second question on "Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs" Let B={M1,M2,...} be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent machine in C and vice versa.

I saw a hint on solving this question which is given in the following picture:

But I have a difficulty in constructing such enumerator $E_{0}$, Also how will I show that every machine described in $B$ has an equivalent machine in $C$ and vice versa, could anyone help me in doing so?

Also it is worth to say that the solution of this problem is found here:

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

But I could not understand it. could anyone explain the solution for me in a simple way ? and in a way depending on the above hints?

Recall the padding lemma: given $\langle M \rangle$ we can compute $\langle N \rangle$ where $N$ is equivalent to $M$, but has a longer representation. (Essentially, we can always add more irrelevant states to a TM, effectively.)

Then, define $E_0$ to do the following:

Run $E$ until $M_1$ is produced.
Let $N_1 = M_1$
Output $N_1$
Continue running $E$ until $M_2$ is produced.
Let $N_2$ be $M_2$, after as many paddings as needed to make its representation larger than $N_1$.
Output $N_2$
Continue running $E$ until $M_3$ is produced.
Let $N_3$ be $M_3$, after as many paddings as needed to make its representation larger than $N_2$.
Output $N_3$
And so on.

By construction, $E_0$ prints larger and larger strings, hence its enumerated language is decidable: this is the wanted language C.

We now need to check the quivalence. For any $N_i$ in the language enumerated by $E_0$, we find an equivalent $M_i$ enumerated by $E$. Vice versa, for any $M_i$ in the language enumerated by $E$, we find an equivalent $N_i$ enumerated by $E_0$.


No Naive Set Theoretic Models of Polymorphic Lambda Calculus? In Philip Wadler's paper on Theorems for Free he states in Section 2 on Parametricity that

  there are no naive set-theoretic models of polymorphic lambda calculus

In the naive set-theoretic model types are sets and functions are set-theoretic functions which seems reasonable. So why does he say there are no naive set-theoretic models of polymorphic lambda calculus?

The standard reference you are looking for is indeed Reynold's Polymorphism is not Set Theoretic. While it is quite obvious that you cannot form, e.g. the product $\Pi_{S\in\mathrm{Set}}S$ over all sets using the usual set theoretic product, it's a legitimate, and non-trivial question whether there is some weaker notion of product that would work, while preserving the usual binary product $\times$ and function space $\rightarrow$.

This turns out to not be possible either, since on one hand, it is rather easy to build a type $\bf 2$ such that the interpretation has at least 2 elements, and show that the interpretation of $T=\Pi_X(X\rightarrow {\bf 2})\rightarrow{\bf 2}$ is isomorphic to $(T\rightarrow {\bf 2})\rightarrow {\bf 2}$, which is not possible for the usual interpretation of $\rightarrow$ by the usual cantor paradox. In this sense it is somewhat similar to the proof for the untyped calculus.

Note that a further paper, by Andrew Pitts, Polymorphism is Set Theoretic, Constructively, overturns this conclusion somewhat by showing that the above contradiction is only possible to construct in classical set theory, and that there are several constructive theories of sets in which polymorphism can be interpreted with the usual interpretations of functions spaces and products. Most notably these "large products" exists in the Effective Topos, the most comprehensive of introductions being given by Phoa.


Busy Beaver problem - Proof by contradiction I am trying to understand a proof regarding the Busy Beaver problem that uses a proof by contradiction approach to show $\sum(n)$ is Turing-uncomputable:

  Find $\sum(n) = max \{\sum(M) | M \in M(n) \}$

Where

  $n$ : Number of states

  $M(n)$: Set of Turing Machines with $n$ states and binary alphabet (0s and 1s)

  $[k]$: Configuration of having a block of $k$ consecutive 1s on an otherwise blank (All 0) tape, and with the head at the leftmost 1.

  $e$: Empty tape (All 0s)

  $\sum(M): \sum(M) = k$ if machine $M$ when started on $e$ halts with $[k]$. Otherwise $\sum(M) = 0$

The proof:

  Suppose there is some Turing machine $\sum$ that computes $\sum(n)$. Then  consider the following Turing machine $Q$ where $k$ is the number of states of the last 3 components:

I cannot understand from here, what exactly is the contradiction here?

I know it took me a few reads before a grasped what it was saying, so maybe if we build $Q$ in a different and (much) more verbose way, it'll help.

So let's start by assuming a Turing machine $\Sigma$ exist which, given a line of n 1's on an otherwise blank tape, can compute the busy beaver of n ($\Sigma(n)$) and write's out that many 1's on the tape.  Now, this Turing machine has some number of states, which we will say is a.

Next, let's assume that another Turing machine, $+1$ which runs to the end of a line of 1's and adds one more 1 to that line.  This Turing machine has some number of states, which we will say is b.

Next, let's assume that even another Turing machine exists, called $D$, short for Double.  Given a tape with some number of 1's on it, it doubles the number of 1's on the tape.  And let's say that it has some number of states c.

We now have three Turing machines, each with a, b, and c states respectively.  So now let us define a number k, such that k = a + b + c.

Now let us build another Turing machine, $K$, short of Write K.  $K$ will print out k 1's on a blank state, and have k states.  A simple machine, where each state writes 1, moves to the next position on the tape, and then goes to the next state.

So now let's combine all our machines into one big machine.

We start with $K$, then go to $D$, then $\Sigma$, and finally $+1$.  Let's call it $Q$.  Now, to find the number of states $Q$ has, you have to add up the members.  In order, that is k + c + a + b.  And given that a + b + c = k, this mean that $Q$ has 2k states.

Now, let's run $Q$ and see what happens.

We start with a blank tape.  Then $K$ runs and puts k 1's on the tape.  Next, $D$ doubles this tape in size, so it now has 2k 1's on the tape.  Next, $\Sigma$ runs and computes $\Sigma(2k)$ and prints that many 1's on the tape (replacing the 2k 1's).  Finally, $+1$ runs and adds one extra 1 on the end of the line.  So there are now $\Sigma(2k) + 1$ 1's on the tape.

Now, this means that $Q$, a Turing machine with 2k states, just wrote $\Sigma(2k) + 1$ 1's on a tape, which is impossible because the maximum number of 1's possible to write on a tape, given 2k states (and not counting cases that never halt), is $\Sigma(2k)$.  Contradiction (and thus $Q$ cannot exist, and namely $\Sigma$ inside of $Q$ cannot exist).

In short, $Q$ has 2k states because we purposefully built it to have exactly 2k states to aid in creating the contradiction.


How to perform measurement of a qubit? I am trying to implement the Deutsch algorithm.
My steps were:

Write down $|01\rangle$ in a matrix form $A$;
Apply $H^{\oplus2}$ gate to $A$ matrix;
Multiply it with $U_f$ matrix;
Apply $H$ to the first qubit;

After the above steps, I got a matrix:

array([[ 0.        ],
       [ 0.        ],
       [-0.70710678],
       [ 0.70710678]])

How should I perform a measurent step on the first qubit to get the answer?

You haven’t specified the order of entries in your vector. In general, the $i$’th entry is obtained with probability $|x_i|^2$.

Let’s consider two examples. In the first, the order of entries is $|00\rangle, |01\rangle, |10\rangle, |11\rangle$. The two final entries will be obtained with probability $1/2$ each, and so the first qubit will be measured as $|1\rangle$. If you measure only the first qubit, then you will still always get $|1\rangle$, and the other qubit will remain in the superposition $\frac{1}{\sqrt{2}}(|1\rangle-|0\rangle)$.

If the order of entries is instead $|00\rangle, |10\rangle, |01\rangle, |11\rangle$, then once again the two final entries will be obtained with probability $1/2$ each. This means that the first qubit will be measured as $|0\rangle$ or $|1\rangle$ with equal probability.


Is this truth table possbile I am trying to figure out if this truth table is possible. I've tried inverting the numbers, adding them, subtracting them, but I still cant find anything that works. I am starting to think that this is not possible.


Decreasing runs of inner loop in outer loop I am trying to determine the worst case runtime of this program:

while n > 1
  for i = 1,..,n
    m = log(n)
  n = n/2

Obviously the outer loop runs log(n) times, because n is halfed after each step.

But the inner for loop is dependent on the decreasing n and I am not quite sure how to deal with that.

A simple bound for it would be n, so the whole thing runs in at most log(n)*n, but I am sure the inner loop is faster than that.

If I look at each step of the outer loop, I see that the inner loop runs n,n/2,n/4,..,2 times. So I would say all together the inner loop runs at most 2n times which is in O(n).

Can I just deduct from that fact that the overall runtime is O(log(n)+n) = O(n)?

I am unsure because I am not multiplying anything, which I feel like I should when dealing with multiple loops.

When loops are nested, the running time is the amount of time the innermost loop is executed multiplied by the time it takes to execute the body of the loop. In your case, the innermost loop executes $n+n/2+n/4+\dots+1\lt2n$ and we'll assume that computing the $\log$ takes constant time. So the running time is linear in $n$.


Term rewrite system for terms of lambda calculus? Are there term rewrite systems, that can rewrite complex lambda term (with nested function application) into some other lambda terms, I.e. reorde function application and, possibly, introduce new variables and add some additional functions into the final term? Google is no help here, because it says, that lamda calculi itself is term rewriting system? Maybe I should use lamda calculus on the lambda calculus? Any reference would be great, some pointers. I can study the field further myself.

E.g I would like start by complex termi with nested functions Sentence(vp(John, walks)) and end with another complex term walks#(John). There may be or may not be some kind of semantic correspondence between input and output. I am just seek i ng framework and scientific tradition that allows to specify such transformations and execute them.

I think that what you are looking for is called higher-order rewriting. There are systems in which you can define rewrite rules of the form $F\;(\lambda x.\lambda y.C\;X[x,y]) \longrightarrow X[X[t,u],v]$ for example, where $F$ and $C$ denote a function symbol and a constant symbols respectively. Note that here, $X$ denotes a higher-order variable (or meta-variable) of arity $2$. In the left-hand side (or pattern), it can be matched against any term containing only variables of $\{x,y\}$. The matched term is then used to replace the occurrences of $X$ in the right-hand side to apply the rewriting rule.

Note that the only terms that match the rewriting rule above are of the form $F\;(\lambda x.\lambda y.C\;A)$, with $FV(A) \subseteq \{x,y\}$. In this case, the variable $X$ is instantiated with $\hat{A}[-,-]$, which is a kind of context such that $A = \hat{A}[x,y]$.


What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty? What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty (or randomness of some kind)? What are some examples in which the problems remain feasible? Can one tell in advance?

I am particularly interested in scheduling problems and what to know as to how the uncertainty in information (e.g. processing times of jobs) affects the difficulty of the problems. I believe the problem becomes more difficult when information is uncertain. Is it true?

Linear Quadratic Regulation is a standard control-theoretic problem that is easy when deterministic. The problem is to minimize a quadratic cost while steering a linear system:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic_regulator

Interestingly, the problem remains easy when additive Gaussian noise disturbes the system and your observations of it:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic%E2%80%93Gaussian_control

However, the problem becomes hard as soon as the noise is non-Gaussian (or even multiplicative Gaussian).


Are the definitions of recursively enumerate equivalent? There are a couple of definitions of recursively enumerable, for example in Judah: $A \subset \mathbb{N}$ is called r.e. if there exist a $\Sigma^0_1$ formula $\varphi(x)$ such that

$$A:=\{n \in \mathbb{N}: \mathbb{N} \vDash \varphi(n)\}$$

In Shoenfield: A predicate $P$ is r.e. if there is a recursive predicate $Q$ such that

$$P(\bar{a}) \leftrightarrow \exists x Q(\bar{a}, x)$$ for all $\bar{a} \in P$. And in here there is another one A new definition of recursively enumerable set?.

My question is: Are the definitions of recursively enumerate equivalent? Why?

Your two definitions are essentially the same: a $\Sigma_1^0$ formula is one of the form
$$\exists x Q(n,x),$$
where $Q$ is computable and $n$ is the parameter.

Another difference between the two definitions is that the first only defines r.e. sets, i.e. unary relations, whereas the second defines r.e. relations of arbitrary arity. The two definitions coincide in the case of unary relations.


Why are processes on the internet not required to use TCP or UDP? Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 5 (The Network layer), Page 455:
[Fifth, processes on the Internet are not required to use TCP or UDP. If a user on machine A decides to use some new transport protocol to talk to a user on machine B (for example, for a multimedia application), introduction of a NAT box will cause the application to fail because the NAT box will not be able to locate the TCP Source port correctly.]
My question is: in this context. what does "processes" mean? Is it a process of data exchange between routers? And why are processes on the internet not required to use TCP or UDP? Isn't it a part of IP protocol and thus it will be used on the internet?

In this context, a process is a normal computer application process, e.g., as defined in wikipedia:

a process is the instance of a computer program that is being executed by one or many threads. It contains the program code and its activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently

So, as Tanenbaum points out, a process that wishes to communicate over the Internet, need not use TCP or UDP. In fact, there are other transport protocols besides TCP or UDP, although those two are the most common. See wikipedia on transport protocols for other transport protocols like SCTP and DCCP. NAT boxes that need a TCP source port to work, would not be able to properly work with other transport protocols. I think Tanenbaum gives the example of a multimedia application, because the requirements can be quite different, e.g., for real-time multimedia, where there is yet another transport protocol combination, RTP/UDP/IP (Realtime Transport Protocol over UDP, then over IP) that is better suited for multimedia traffic than TCP/IP.
Why do we hear the phrase TCP/IP so often? Because we hear that, we may get confused and think like you thought, that TCP was "part of" IP. Actually, TCP and IP are separately protocols on different layers of the protocol stack (transport layer and network layer, respectively). However, in the Internet, TCP is so commonly used, that people started saying TCP/IP, for communications using TCP over IP.


Online approximation algorithm for median? Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $k$ elements of a stream $c_1,c_2,c_3,\dots$?
The scenario is: I have a stream of numbers, and at any point in the streaming process I should be able to query for the (approximate) median in the last $k$ elements.
Thanks!

If you need the exact median, store the last $k$ elements in a self-balancing binary search tree.  Also keep a linked list of the last $k$ elements.  At each time step you can delete the oldest element (the list will tell you which one) from the tree, then insert the newest one into the tree.  It is easy to obtain the median from the tree in $O(\log k)$ time.  Thus, you will do $O(\log k)$ work at each time step, and you will need $k$ space.
If you want to use much less than $k$ space, and are satisfied with the approximate median (you don't need the exact value), you can use various methods for approximating a streaming histogram.


How many possible ways to go right and up in an array Let's say we have a 2D matrix, and we begin at $(0, 0)$.

We must travel $m$ steps to the right and $n$ steps up, in any order. Each step moves the position right or up by $1$.

For example if $n = 5$ and $m = 4$, the following would all be valid:

UP UP UP UP RIGHT RIGHT RIGHT RIGHT UP

RIGHT UP RIGHT UP RIGHT UP RIGHT UP RIGHT UP UP

UP UP RIGHT RIGHT UP RIGHT UP UP RIGHT

How many possible different ways are there to travel up $n$ times and right $m$ times, if the ordering in which we travel right or up does not matter, as long as we start at $(0, 0)$ and finish at $(n, m)$

You can treat this problem as a combinatorics problem: How many ways are there to reach from $(0,0)$ to $(m,n)$?.

Your steps are either $\mathit{up}$ denoted by $1$ for clarity, or $\mathit{right}$, denoted by $0$

No matter what path you take, you must move exactly $n$ times $up$ and exactly $m$ times $right$.

it means you would, in total, perform $m+n$ moves

Since any move is essentially either $1$ or $0$, it can be reduced to the following questions: Given a sequence of moves $P$ of length $m+n$, how many such options are there for such a $P$ in which #$1=n$, #$0=m$ ?

Solution:

  $$\binom{n+m}{n} = \binom{n+m}{m} $$


IS there a consensus on the definition of a computer program in CS literature and if so, what is it? The following is what I came up with from my synthetic prior research but I might be wrong.

I understand it is possible to reduce any computer "program", in a maximal reduction(?), to these features:

Internal implementation: Everything from start to end, including possible functions and possible sub functions
External interface: A parameter set with which arguments might correspond in execution or call → if any

Internal implementation includes:

Data structures: Primitive data types and possibly also functions or modules (depends what term one prefers)
algorithms: outside or inside a function/algorithm → if any
Database interfaces → if any

I understand that external interface (very often represented by parenthesis) can be part of internal implementation (which, in programming languages, is very often represented by brackets) and that yes or no depends from language architecture.

IS there a consensus on the definition of a computer program in CS literature and if so, what is it?

Computer Science is far too diverse to have a single notion of program. For a theoretician, it might be an input tape to a universal Turing Machine, or any lambda expression in lambda calculus. For someone working on the front end of a compiler, it could be defined by a formal grammar while for someone working on the back end, or to the HW architect, it might be a sequence of binary instructions. For someone working on operating systems, it might be any file with the executable bit set.

Perhaps it could be said that a unifying theme is any form of information that can used to control the operation of a process, or an abstract or real machine, to produce information in the same or different form.

For some, I’m sure this will be too broad, for others, too narrow.


Possible unique paths to reach cell (0,n-1) from cell (0,0) given vector of must visited rows and allowed movement directions I've been given a matrix path problem to solve and I need some hints / advises. You're given a $m \times n$ matrix where $m$ is number of rows and $n$ number of columns. When you're in a cell $(i,j)$ you can only move to cells $(i,j+1)$, $(i-1,j+1)$ and $(i+1,j+1)$. Three subproblems have to be solved. I solved first two and I'm stuck solving the third one now.
First one is to find all possible paths from $(0,0)$ to $(0,n-1)$, second one is to find all paths with given obstacles. The third one is kind of tricky. You're given a vector of must visited rows while traversing (they don't have to be sorted). For example: if you're given a vector $[
r_2,r_1]$, you have to find all possible ways to reach row 2, then all possible ways to visit row 1 after visiting row 2 and finally all paths to come to cell $(0,n-1)$ with given restrictions.
Any advises or hints for this one?

Subproblem 1: Find the number of possible paths from $[i,j]$ to $[k,\ell]$ for all $i,k \in \{0,\dotsc,m-1\}$ and $j,k \in \{0,\dotsc,n-1\}$. Store them in a table $A$ of size $m$ x $n$ x $m$ x $n$. In other words, an entry $A[i][j][k][\ell]$ stores the number of possible paths from $[i,j]$ to $[k,\ell]$. You can construct this table since this is similar to the second variant of your problem while considering the restrictions.
Subproblem 2: Find the number of possible paths from $[i,j]$ to $[k,\ell]$ that does not goes through the entries: $[k,0], \dotsc, [k,\ell-1]$, for all $i,k \in \{0,\dotsc,m-1\}$ and $j,k \in \{0,\dotsc,n-1\}$. Store them in a table $T$ of size $m$ x $n$ x $m$ x $n$. In other words, an entry $T[i][j][k][\ell]$ stores the number of possible paths from $[i,j]$ to $[k,\ell]$ that does not pass through the entries: $[k,0], \dotsc,[k,\ell-1]$. You can construct this table from the entries of the previous table $A$ but it will require some more work.
Main Problem: Suppose the row vector is $(r_{i_{1}},r_{i_{2}},\dotsc,r_{i_{p}})$. Here, I am assuming the $0$ based indexing. In other words, if $r_{i_{j}} = 4$, it means it is the fifth row. For sake of better understanding of the solution, let me add $r_{i_{0}} = 0$ at the beginning of this row vector. Now, the row vector is $(r_{i_{0}},r_{i_{1}},r_{i_{2}},\dotsc,r_{i_{p}})$.
Now, we define a table $R$ of size  $(p+1)$ x $n$ such that $R[t][j]$ denote the number of possible paths from $[r_{i_{t}},j]$ (for valid $r_{i_{t}}$ and $j$) to the $[0,n-1]$ that goes through the row vector $(r_{i_{t+1}},\dotsc,r_{i_{p}})$
Output: The algorithm should output $R[0][0]$ since it denote the number of possible paths from $[0,0]$ to the $[0,n-1]$ that goes through the row vector $(r_{i_{1}},\dotsc,r_{i_{p}})$
Induction Step:
$$R[t][j] = \sum_{\ell = 0}^{\ell = n-1} \Big( T[r_{i_{t}}][j][r_{i_{t+1}}][\ell] \Big)\cdot \Big(R[t+1][\ell] \Big) $$
Base Step: When $t$ becomes equal to $p$, we get $R[p][j]$, which denote the number of possible paths from $[r_{i_{p}},j]$ to $[0,n-1]$ that does not goes through any row vector.
$$R[p][j] = A[r_{i_{p}}][j][0][n-1] \quad \textrm{ for all valid $j \in \{0,\dotsc,n-1\}$}$$

Since you just asked for hints, this is more than sufficient.


Finding a graph where the edge set satisfies a set of integer equations There is an easy and hard version of the problem I am asking about, so I will start with the easy to make for clearer reading.

Suppose that we are have a set of vertices $V =\{v_1,v_2,...,v_n\}$ and sets $S_1,S_2,...,S_m \subset V \times V$. Let

$s_{ijk} = 1$ if $\ (v_j,v_k) \in S_i $, 0 otherwise.

Given integers $\ k_1,...,k_m$ we want to find whether the set of equations

$$\begin{align*}
k_1 &= \sum_{j,k} a_{jk} s_{1jk}\\
k_2 &= \sum_{j,k} a_{jk} s_{2jk}\\
 &\vdots\\
k_m &= \sum_{j,k} a_{jk} s_{mjk}
\end{align*}$$

has a solution with all of the $a_{11}, a_{12}, ... , a_{nn}$ indices in $\{0,1\}$.

Explanation

This set of 0-1 equations is equivalent to checking whether or not there exists a (simple directed) graph with $\ k_i$ edges from each of the subsets $\ S_i$. My immediate instinct is that this problem is solvable in polynomial time, say by a straightforward backtracking algorithm. Another possibility is to solve the system using the appropriate technique (say Hermite Normal Form) and then applying LLL to get a short basis for the solutions. The proof that this is solvable in polynomial time isn't entirely clear to me though.

Example

We are given $\ v_1, v_2, v_3.$

$\ S_1 = (v_2, v_3) $

$\ S_2 = (v_1, v_3), (v_2, v_3)$

$\ k_1 = 1, k_2 = 0$

We return false because we have to pick $\ (v_2,v_3)$ but this forces $\ k_2 > 0$ since we have to pick it in the second set as well.

The harder version:

Does there exist a (directed) graph $G$ with $\ k_i $ edges from each subset $\ S_i$ such that

$\ G = cl(G)$,

where $\ cl(G) $ denotes the transitive closure?

We can solve this by testing the feasibility of a set of 0-1 linear equations and inequalities, but as we should know that problem is NP hard in general (unlike solving linear integer equations). However it does not look at all trivial to show that this particular problem is NP hard.

Questions

Can the first problem always be solved in polynomial time?

Is the second problem NP hard?

You are asking two questions.  I will answer the first one.  Your first problem is NP-hard, by reduction from exactly 1-in-3 positive 3-SAT.

Let $\varphi$ be a positive 3-CNF formula with $m$ clauses and at most $n^2$ variables $x_i$.  Label each edge $(v_i,v_j)$ with a distinct variable $x_{ij}$.  Each set $S_i$ will correspond to a clause of $\varphi$ as follows: the set $S_i$ contains one edge $(v_i,v_j)$ for each variable $x_{ij}$ that appears in that clause.  Let $k_1=k_2=\cdots = k_m=1$.

Now the resulting system of linear equations has a solution if and only if $\varphi$ has an assignment where every clause has exactly one of its three variables set to true.


Sorting in a Priority Queue Does a priority queue Queue<K,V> always sort its elements based on the value of each element or its key?

I know than the priority in the queue is based on the key, and that the element with the highest priority has the minimal key (Correct me if I am wrong) But I am not sure about wether the pq sorts based on value.

The definition of a priority queue is that elements will be dequeued in order of priority. The definition says nothing about the order of items of equal priority so an implementer can do anything, within reason, and still be justified in calling the resulting structure a priority queue.


Smoothed analysis of the Partition problem I am studying smoothed analysis and trying to apply it to the Partition decision problem: given $n$ real numbers with a sum of $2 S$, decide whether there exists a subset with a sum of exactly $S$.

The common definition of the smoothed runtime complexity of an algorithm is:
given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it is perturbed by a perturbation of size $\sigma$, e.g. by adding to each input a number selected randomly from a normal distribution with standard deviation  $\sigma$, or from any distribution with support $[0,\sigma]$.

If I apply this definition to the Partition problem, it seems that for any $\sigma > 0$, the runtime complexity is $O(1)$, since for any random noise that is added to the original numbers - no matter how small - the answer is "no" with probability 1.

This is strange, since in the more common examples of smoothed analysis, the runtime complexity depends on $\sigma$, and here it does not.

Is there something I misunderstood? What is the smoothed runtime complexity of Partition?

Smoothed analysis, as I have seen it, has typically been used for analyzing optimization problems, not decision problems.  The partition problem is a decision problem, which introduces the challenge you mentioned.  Perhaps one could consider the optimization variant of the partition problem: given $n$ numbers with a sum of $2S$, find the subset whose sum is as close to $S$ as possible.  I don't know whether the smoothed complexity of that optimization problem would be interesting or illuminating, but it eliminates the problems you articulate in the question.