State whether the language is in $R$, $RE$, etc. The intuition for the solution I saw the solution but can't understand the intuition of the following question:
Let's define
$$L^{\ge k} = \{w\in L : |w| \ge k\}$$
and
$$L=\{\langle M\rangle | \exists k:L(M)^{\ge k} = \overline{HP}^{\ge k} \}$$
$L\in R$ because $L=\emptyset$, the proof is a bit long and anyway I understood most of the steps, My question is about the intuition, what is the hint here that $L=\emptyset$ or any other hints for the solution?
EDITED
$$
\overline{HP}=\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\}
$$
It's the complementary language of
$$
HP=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\}
$$

The intuition is that finite languages are very simple in the sense that throwing a finite number of words from a language does not affect membership in $\text{R}$ or in $\overline{\text{RE}}$, etc. Therefore, since $L^{\geq k}$ is the result of throwing a finite number of words from $L$, we get that:

$L(M)^{\geq k} \in \text{RE}$, and
$\overline{HP}^{\geq k} \notin \text{RE}$.

So the language $L = \{ \langle M \rangle: \exists k: \ L(M)^{\geq k} = \overline{HP}^{\geq k}\}$ must be empty.

Formally speaking, we have the following claims:
Claim 1: For every non-trivial language $A$, and every finite strict subset $B\subsetneq A$, it holds that $A \leq_m A \setminus B$.
Hint for the proof of claim 1: $B$ is finite and thus decidable. Therefore, given input $x$ for the reduction, we can check whether $x\in B$. Then you can proceed easily. Think where to map inputs $x$ from $B$, and where to map inputs $x$ from $\overline{B}$.
We also have the following similar claim which could be useful.
Claim 2: For every non-trivial language $A$, and every finite strict subset $B\subsetneq A$, it holds that $A\setminus B \leq_m A $.
Given the above claims, we're done. Indeed, $\overline{HP} \notin \text{RE}$, and for every $k$, $\overline{HP}^{\geq k} = \overline{HP}\setminus \{w\in \overline{HP} : |w| < k\}$. That is, $\overline{HP}^{\geq k}$ equals a non-trivial infinite language minus a  finite subset, and so by claim 1, $\overline{HP}^{\geq k} \notin \text{RE}$. Also, it holds that $L(M)^{\geq k} \in RE$ for every machine $M$ (this is easy, you can prove that directly using standard closure properties and the fact that  $L(M)^{\geq k} = L(M)\setminus \{ w\in L(M): |w| < k\}$. Alternatively, you can use claim 2 but you have to be careful regarding the edge cases where $L(M)$ is trivial, etc.). Therefore, it cannot be the case that there is a machine $M$ with $L(M)^{\geq k} = \overline{HP}^{\geq k}$.


2:1 Mutual exclusion with semaphores I'm stuck on this semaphore exercise (it's a exam question of a previous exam and I'm studying for that exam):

There are three processes: A, B and C. Process A wants to execute method a(); Process B wants to execute b(); and Process C c();. The Processes are each started once.

The execution of a(); must not overlap with the execution of b(); or c();. However b(); and c(); must always be able to run concurrently. The order of execution must not be forced.

I can use as many semaphores as I want. With every solution I tried so far I always get the case that when e.g. b(); is executing and a(); is waiting, that I will also block c();. The solution is probably simple but I'm too blind to see it.

There's a simple solution which takes advantage of the fact that semaphores naturally allow controlling access to a resource with multiple instances. Model the exclusion as a resource with two instances. A requires both instances while B and C each require one. When A starts, it grabs both instances, preventing B and C from starting. When B or C starts, it grabs one instance, which allows the other to start concurrently, but blocks A.

A:                  B:                  C:
  V(S, 2)             V(S, 1)             V(S, 1)
  …                   …                   …
  P(S, 2)             P(S, 1)             P(S, 1)

This solution works even if the processes run multiple times. A critical ingredient that makes it work is that A atomically excludes both B and C from running.

If you treat B and C's resources as distinguishable, with A requiring both, you run into a classical problem, which is the order of grabbing locks. This problem is similar to the dining philosophers problem. When A starts, it either grabs the B resource first, or the C resource first. Let's say A grabs B, and then tries to grab C. If C is not available, what should happen? If A keeps the B resource then it prevents process B from starting. So A must release B and try again. Since A knows that C is busy, it can wait on C first. In this particular exercise, where the processes only run once, this works. Note that this requires semaphores with a non-blocking “try” operation.

A:                  B:                  C:
  lock(B)             lock(B)             lock(C)
  if try_lock(C):     …                   …
    …                 release(B)          release(C)
    release(C)
    release(B)
  else:
    release(B)
    lock(C)
    lock(B)
    …
    release(B)
    release(C)

If B and C could run multiple times, this strategy wouldn't work: A must never keep one lock while waiting for the other, because that prevents the corresponding process from running again. In this case, I think there's no wait-free solution with only binary semaphores.


Is < binary relation a strict partial order on IEEE doubles? To me it looks that it is:

irreflexivity: NaN < NaN == false
transitivity: if a < b and b < c then a < c (the antecedent is never true for NaNs)
asymmetry: if a < b then not b < a (again, the antecedent is never true for NaNs)

However, it cannot be extended to non-strict partial ordering <= because there's no (reflexive) equality for doubles (NaN != NaN).

Yes, it is. (Though you need to consider signed zero as well as NaNs.) For extra confirmation:

So, the floating-point operator< does not form weak order and therefore does not form a total order. It is, however, a partial order.

However, it cannot be extended to non-strict partial ordering <= because there's no (reflexive) equality for doubles (NaN != NaN).

It can be extended, but <= as defined by IEEE isn't that extension.


Computability of sequential cubic-order algorithms I have a cubic-order algorithm which must be executed sequentially; there appears to be no way of making it parallel.

I need to come up with an estimate of maximum input size that can be solved using today's technology. So, the essential problem seems to be how to relate the cost of a single step to execution time on a "typical" hardware. Is there a gold-standard way of doing this, e.g. something an attentive peer-reviewer would like to see being done in a manuscript?

Estimate the constant of the leading term in your complexity, i.e., write your complexity as $c n^3 + o(n^3)$. You can get an idea of $c$ by a careful inspection of your algorithm and you can test it experimentally.

Then decide what "can be solved using today's technology" means. You probably want your program to terminate withing a certain amount of time $T$. Estimate how many operations $N_T$ your machine can perform within time $T$.

Finally solve $c n^3\le N_T$, i.e., $n \le \sqrt[3]{n/c}$.

Keep in mind that this is just an estimate there are a lot of thing that can go wrong: $c$ depends on a lot of practical factors (the language of your implementation, the target architecture, cache locality, ...), the complexity of the algorithm might not be uniform across different instances of the same size, the complexity of the algorithm might not scale up nicely, the asymptotic notation is... asymptotic while you're dealing with small input sizes, and more.
You know the details of your algorithm so you probably have a better idea of how these factors will impact your estimate.


Is persistence a property of a database? I was having a discussion in another forum on this topic, and I couldn’t get a satisfactory answer. Originally, a statement was made that a redis data store couldn’t be considered a database because it’s not persisted to disk. I queried that, because I didn’t see why persistence is a required property of a database. I understand a database to simply be some structured/organised data.
So: is persistence a required property of a database, and why?

The databases I've seen are persistent.  But rather than trying to figure out the "one true meaning" of the word database, if this aspect matters in a specific context, then I suggest you just be explicit about how you are using the word.  That's probably best in any case if this is critical.
A rose by any other name would smell as sweet.  (Shakespeare)


Reduction from SAT to shortest cycle? I have been assigned a homework problem that I cannot figure out:

  Prove that SAT has a polynomial-time reduction to the language of undirected non-negative weighted graphs with simple cycle of weight less that or equal to w.

This bears a resemblance to the all-pairs shortest path problem which has polynomial-time algorithms, but I've read multiple times that this problem is np-hard (plus, I suppose it would be a cruel trick to give such an assignment).

Starting from hamcycle, I have managed to produce a reduction for several variations on this problem (e.g., tsp, longest positive path, shortest negative path), but whenever it comes to this language I can always come up with a counterexample that invalidates my attempt at a reduction.

So, is there a reduction from SAT?  What am I missing?

In the spirit of "give a man a fish, and he'll be fed for a day; teach a man to fish, and he never need be hungry again", I'll share with you some problem-solving techniques that might be helpful for approaching this problem (and other problems) -- but I'm not going to spoil it for you by solving your exercise for you.

Technique #1:  If you don't know how to solve a problem, change the problem: look for "nearby"/"similar" problems you do know how to solve.  If you can't reduce SAT to the original language, is there some related/variant language you can reduce SAT to?  You may need to try multiple variants, and get a feeling for which ones you can easily find a reduction for and which ones you struggle with.  This may give you some intuition about what the barrier/difficult part of your problem is, which may help you identify what aspect to focus your energy on.

Hint #1 (possible spoilers):

   If you changed "less than or equal to w" to "equal to w", would the problem be any easier?  What if you changed it to "greater than or equal to w"?

Technique #2: You can chain reductions.  If you can reduce SAT to some variant, and reduce that variant to the original problem, you're in business.

Hint #2 (possible spoilers):

   It seems that short cycles are a headache.  If you have a graph $G$, can you think of some way to transform it to remove all short cycles (without changing whether or not it contains a cycle of length $w$)?  (If you can't immediately see how to do it, can you write out a precise specification of what such an algorithm would need to do?)

And that's as much as I'm going to say.  It's a good exercise, and it's your exercise, so you should have the chance to play around with it and discover a solution for yourself.  It's tricky but doable.


MESI Protocol Invalid cache line is attempted to be stored? I am implementing a sample MESI simulator having two levels of cache (write back). I have added MESI status bits to both levels of cache. As it is a write back cache, the cache line is updated to L2 only when it is flushed. My doubts are

what should be the behavior when a cache line with INVALID state is flushed from L1 cache. Will it just ignore the transaction? It seems that is the only possibility..but it doesn't seem right.
Consider processor1(P1) modifying a cacheline shared by processor2(P2). Then that cache line in P2 will get status INVALID. If P2 has to update the same cache line in future and sees the state is INVALID, it should read the updated value from??what if it is still in modified state in P1(not yet written back to L2/Main memory)?
Consider a similar situation that P1 has a cache line in MODIFIED state, P2 has the same line in INVALID state. When P3 tries to retrieve the same line, it broadcasts a request to all L1 caches. According to the theory,if P3 cant get the cache line from any other L1 caches, it sends request to L2/main memory. In this case where will P3 get the requested cache line from? From P1 or from the L2/main memory? Or will P1 update to the main memory first and then send the cache line to P3?
I am using LRU for flushing the cache(write back). When flushing a cache if it is INVALID what should be the behavior? It just ignores the line?

INVALID means "not in the cache," so there is nothing to flush. When you mark a cache block as INVALID it means that the data and the tag are not relevant.

Similarly, for your second question.  The line is not in P2's cache, so it should treat the line the same way it treats any other cache miss: (if it's a snoopy coherence mechanism then it should broadcast a message to all the other caches.  If it's a directory based coherence mechanism then it should send a request to the directory.)


Is the halting problem decidable for pure programs on an ideal computer? It's fairly simple to understand why the halting problem is undecidable for impure programs (i.e., ones that have I/O and/or states dependent on the machine-global state); but intuitively, it seems that a pure program's halting on an ideal computer would be decidable through e.g. static analysis.

Is this in fact the case? If not, what are some counterexamples or papers disproving this claim?

Here is a proof of undecidability by reduction from the Halting problem.

Reduction: Given a machine $M$ and an input $x$, build a new Turing Machine $H$ which does not read any input, but writes $M$ and $x$ on the tape and simulates $M$ on $x$ until $M$ halts.

The behaviour of this new machine $H$ is independent of the input tape, so it is a pure Turing Machine on which only static analysis is applicable. If static analysis were sufficient, then it could show whether $H$ halts, which would show whether $M$ halts on $x$, which would solve the halting problem for impure machines, which we know is undecidable, and therefore your problem is undecidable too.


Why will the Hindley-Milner algorithm never yield a type like t1 -> t2? I'm reading about the Hindley-Milner typing algorithm while writing an implementation, and see that, as long as every variable is bound, you'll always get either atomic types or types where the arguments will determine the final type, such as t1 -> t1 or (t1 -> t2) -> (t1 -> t2) where t1 and t2 are type variables.

I cannot think of a way you'd get something like t1 -> t2 or simply t1, which I understand would mean the algorithm is broken since there would be no way to determine the actual type of the expression. How do you know you'll never get a type such as these "broken" ones as long as every variable is bound?

I know the algorithm yields types with variables, but these are always resolved once you pass the arguments to the function, which wouldn't be the case in a function with type t1 -> t2. This is why I want to know how we know for sure the algorithm will never yield such types.

(It seems that you can get these "broken" types in ML, but I'm asking about lambda calculus.)

In the lambda calculus with no constants with the Hindley-Milner type system, you cannot get any such types where the result of a function is an unresolved type variable. All type variables have to have an “origin” somewhere. For example, the there is no term of type $\forall \alpha,\beta.\; \alpha\mathbin\rightarrow\beta$, but there is a term of type $\forall \alpha.\; \alpha\mathbin\rightarrow\alpha$ (the identity function $\lambda x.x$).

Intuitively, a term of type $\forall \alpha,\beta.\; \alpha\mathbin\rightarrow\beta$ requires being able to build an expression of type $\beta$ from thin air. It is easy to see that there is no value which has such a type. More precisely, if the type variable $\beta$ does not appear in the type of any term variable in the environment, then there is no term of type $\beta$ which is in head normal form. You can prove this by structural induction on the term: either the variable at the head would have to have the type $\beta$, or one of the arguments would have to have a principal type involving $\beta$, i.e. there would be a smaller suitable term.

Just because there is no value of a certain type doesn't mean that there is no term of that type: there could be a term with no value, i.e. a non-terminating term (precisely speaking, a term with no normal form). The reason why there is no lambda term with such types is that all well-typed HM terms are strongly normalizing. This is a generalization of the result that states that simply typed lambda calculus is strongly normalizing. It is a consequence of the fact that System F is strongly normalizing: System F is like HM, but allows type quantifiers everywhere in types, not just at the toplevel. For example, in System F, $\Delta = \lambda x. x \, x$ has the type $(\forall \alpha. \alpha) \rightarrow (\forall \alpha. \alpha)$ — but $\Delta\,\Delta$ is not well-typed.

HM and System F are examples of type systems that have a Curry-Howard correspondence: well-typed terms correspond to proofs in a certain logic, and types correspond to formula. If a type system corresponds to a consistent theory, then that theory does not allow proving theorems such as $\forall A, \forall B, A \Rightarrow B$; therefore there is no term of the corresponding type $\forall \alpha,\beta.\; \alpha\mathbin\rightarrow\beta$. The type system allows one to deduce “theorems for free” about functions over data structures.

This result breaks down as soon as you add certain constants to the calculus. For example, if you allow a general fixpoint combinator such as $Y$, it is possible to build terms of arbitrary type: $Y (\lambda x.x)$ has the type $\forall \alpha. \alpha$. The equivalent of a general fixpoint combinator in the Curry-Howard correspondence is an axiom that states $\forall A, \forall B, A \Rightarrow B$, which makes the logic obviously unsound.

Finding the fine line between type systems that ensure strong normalization and type systems that don't is a difficult and interesting problem. It is an important problem because it determines which logics are sound, in other words which programs embody proofs of theorems. You can go a lot further than System F, but the rules become more complex. For example, the calculus of inductive constructions which is the basis of the Coq proof assistant, is strongly normalizing yet is capable of describing common inductive data structures and algorithms over them, and more.

As soon as you get to real programming languages, the correspondence breaks down. Real programming languages have features such as general recursive functions (which may not terminate), exceptions (an expression that always raises an exception never returns a value and hence can have any type in most type systems), recursive types (which allow non-termination to sneak in), etc.


Is there a way to incrementally degrade the quality of a PRNG? I have an application that depends on a random number generator to perform.  The application might be sensitive to the quality of the random numbers, but I don't know for sure.  I'd like to test this, and if it is, what the degree of sensitivity is.

I've currently got a xorshift1024* PRNG plugged in.  It's fast and I can directly inject a full 1024 bit state.

I need to be able to degrade it in a controlled fashion, ranging from it's high quality native mode to something quite bad.  By quite bad, I mean something far far worse than a simple linear congruential generator.  I'm not interested in slowly changing it's output distribution from uniform to say, normal.  I just want to be able to make it (technically) crappier and crappier.

I have the sense that this might be a common requirement in other testing applications, so there might be a best practice methodology.  At this point my only alternative is to switch off the generator entirely.

Is there a way to incrementally degrade the quality of my PRNG?

There are many possible ways to degrade its output, but here is one simple choice:

Think of your PRNG as outputting a sequence of bits.  For a good PRNG, each bit would be uniformly distributed (equally likely to be 0 or 1), independent of the previous bits.  We can build a degraded PRNG where each bit of the output is 1 with probability $p$ or 0 with probability $1-p$, independent of all of the previous bits.  This gives us a parameter $p$ that can be varied from $1/2$ down to $0$: with $p=1/2$, there's no degradation, and smaller values of $p$ correspond to increasing amounts of degradation.  Effectively, $p$ is a tuning knob that allows us to control the amount of degradation.

From this, you can derive a way to get other quantities.  If you want a 32-bit integer, you generate each of its bits using this degraded PRNG.  etc.

This model has some nice properties.  For instance, if you generate a random $k$-bit value using your degraded PRNG, the resulting value will have $k h_2(p)$ bits of entropy.  This varies from $k$ bits smoothly down to $0$ bits as $p$ varies from $p=1/2$ down to $p=0$.  As a very crude approximation, the $k$-bit value will be approximately uniformly distributed on a set of size $2^{k h_2(p)}$; as $p$ gets smaller (as you introduce more degradation), the size of this set gets smaller smoothly.

Of course, we can't tell you whether this is the "right" degradation model for your particular application, as that will depend on your particular application.  There are many other possible ways of degrading a PRNG's output, and since we haven't been given any specific criteria for selecting among them, I have semi-arbitrarily chosen one that is especially simple to implement and simple to think about.


Can I include some manual effort in creating an otherwise automated research prototype tool? I am a research student in the area of programming language/software engineering. I am claiming to provide an automated technique to solve a research problem in one of my papers. The prototype tool that I am creating for this paper is required to test some real-world libraries. I am using a symbolic execution tool in my research and it crashes on encountering native functions in some third-party libraries. To mitigate this problem, I provide my own model class that is basically a dummy class with non-native functions. Instead of using the original class which contained the native functions, I change the library to use this model class so that symbolic execution works better. Will this be called manual effort in my tool? Can't I call my technique an automated one now? Moreover, is it cheating?

You can do that.  I have seen other papers that generate dummy classes like that (e.g., Klee).  How useful this will be may depend on how much effort it takes to write those dummy classes and how many are needed.
What matters is less the name (automated vs manual) and more that you describe clearly in your paper what its advantages and drawbacks are.  Usually it is valuable to compare to prior papers.  Can you demonstrate that your method is easier to apply than prior work?  Maybe because it requires less manual work?  If so, you may be in business.


How to prove that the minimum square partition of a 3X2 rectangle has 3 squares This question is motivated by an older question about tiling an orthogonal polygon with squares.

Given a $3\times 2$ rectangle like the first image, the second image is a square partition of that rectangle.

A square partitioning is a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
A minimum square partitioning is a square partitioning, for which is no square partitioning that is made of a lesser number of squares.

  How can we prove that the second image is a minimum square partitioning of the $3\times 2$ rectangle?

Can we generalize this to ${\rm M{\small IN}S{\small QUARES}}(R_{w,h=w-1})=w$? (see followup question )

The case $w = 3$ is somewhat boring. Here is how to show that you need at least three squares. There is some square $S_1$ touching the bottom-left corner. There is some square $S_2$ touching the bottom-right corner. These squares must be different. At least one of them doesn't go all the way to the top, and so one of the other two corners remains uncovered, requiring another square.

I'm not sure how to extend this proof beyond $w > 3$. Let me just mention that a classical result of Dehn shows that if an $h \times w$ rectangle can be tiled by squares then $h/w$ is rational, and moreover there is some integer $c$ such that if you scale everything by $c$ then all squares have integer sides.


Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|).

Now let's modify the Dijkstra to stop once it reaches T (Destination) from S(Start). The given performance is:

Understand that we don't need to explore the full G in the modified Dijkstra run.
Can someone explain why it is the diamond shape(the 45 degree rotate of a perfect square)?

What does it means with the radios of |m|+|n|, (typo of radius ?)

What is m and n in this case? (m means vertices? n means edges?) seems to me that $(|m|+|n|)^2$ is half of the vertices and edges visited，which is half of the Diamond/Square. Then not sure how is it is computed.

added new pic for the additional questions

In the example, we can assume the start cell $s$ is the origin in a plane consisting of square cells with Descarte coordinates.  That is, $s$ is $(0,0)$. The coordinate of destination cell, $t$ is $(m,n)$. The distance of any two cells is given by the taxicab geometry. That is, the distance between cells $(p_1,p_2)$ and $(q_1,q_2)$ is
$$d((p_1,q_2),(q_1,q_2))=|p_1-p_2|+|q_1-q_1|$$
In particular, $d(s,t)=|m|+|n|$.

At the last step of running Dijkstra's algorithm with source cell $s$ when we visit cell $t$, all cells whose distance to $s$ is smaller than $d(s,t)$ must have been visited. Some of the cells whose distance to $s$ is $d(s,t)$ may have also been visited. If you color all cells that are no more than $d(s,t)$ away from $s$, you will get a diamond shape whose boundary cells $(p,q)$ are given by the following equations.

$$ \begin{align}
p+q = d(s,t)  &\text{ where }p\ge0, q\ge0. \text{ This is the top right segment.}\\
p-q = d(s,t)  &\text{ where }p\ge0, q\le0. \text{ This is the bottom right segment.}\\
-p+q = d(s,t) &\text{ where }p\le0, q\ge0. \text{ This is the top left  segment.}\\
-p-q = d(s,t) &\text{ where }p\le0, q\le0. \text{ This is the bottom left segment.}\\
\end{align}$$

That diameter shape is, in fact, a circular disk with center $(0,0)$ and radius $|m|+|n|$ in the taxicab geometry. Yes, as you pointed out, "radios" should be "radius".

How many cells are there in the diamond shape? The diamond shape is actually a square the length of whose diagonals is $2(|m|+|n|)$. So its area is $(2(|m|+|n|))^2/2=2(|m|+|n|)^2$, which is about the number of cells in the it asymptotically.

Exercise. The exact number of cells in a disk with radius $r$ in the taxicab geometry is $2r^2+2r+1$. In particular, there are 13 cells in a disk with radius 2.


Why we write "Ignore the input " when describing an Enumerator?(Sipser Chapter 3) The Theorem and its proof is given below:

But I am wondering why we write "Ignore the input " when describing an Enumerator? could anyone explain this for me please?

It's just an explicit statement that the behaviour of the machine doesn't depend on its input in any way. This could be inferred from the rest of the machine's description, but explicitly saying it makes it clear that it's not a mistake.


Construct a DAG from given multiple topological orderings I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as first $n$ natural numbers. (Note that once created, the graph $G$ may have more topological orderings apart from the ones given.)
The following constraints should be met:

The maximum outdegree of every node should be 1
The number of nodes having indegree 0 should be minimum.

There can be multiple solutions, any of them should work.

What I have tried. (Approach 1 which is wrong as it fails one example given in the answer. Please scroll to the second approach, which still I'm not able to find a mistake.)

Approach 1
From all the given orderings, first, create a directed graph by creating a directed edge from every node to its next node. This means if the orderings are:
$$ 1, 3, 2, 5, 4, 6 $$
$$ 3, 1, 5, 2, 4, 6 $$
$$ 1, 5, 3, 2, 4, 6 $$

I will create a directed graph with a directed edge from $1$ to $3, 3$ to $2, 2$ to $5$ and so forth.

This ensures that the number of nodes with indegree 0 remains minimum. Now, I'll remove all the cycles and make sure all the orderings are valid and finally, eliminate all the extra edges any node has. WHile doing so, I'll make sure that if there are two nodes whose edge is coming from the same node, I'll remove the edge from the node having a higher indegree, so that condition 2 is met.
The graph constructed then, should look like:

This DAG created, follows both the constraints, and IMO has the minimum number of nodes of indegree as 0, although, it's not proven.

I have coded the approach and it is giving expected results for the use cases I supply, but I know that it is wrong.
What am I missing here? Can anyone provide an alternative use case, which fails the above approach?

Approach 2
I create a directed graph $G$ by creating an edge from  $a_i $ to $ a_j$ for all $ j > i$ in all the orderings given.
So, for the orderings:
 $$ 1, 2, 3, 4, 5$$
$$ 2, 4, 1, 5, 3$$

I will create the following graph:

The first step after this is to validate all the orderings. Removing cycles separately is not required as they will be removed by this step itself.
For any ordering
$$ a_1, a_2, a_3, a_4, ... a_n $$
I will check if there exists any edge from $a_j$ to $a_i$ where $ j > i$, I'll remove that edge.
Doing so, will give the following graph:

The last step is to remove extra edges from all nodes as maximum outdegree of any node can be $1$ max. I'll remove the outgoing edges such that the number of nodes having indegree $0$ is minimum. First I calculate the indegree of each node. Then for each node which has more than 1 outgoing edges, I'll remove all the edges except the one with the minimum indegree.

The final graph $G$ will look like:

This graph satisfies both the constraints. But I know this approach is wrong! Can anyone help to find why is this wrong?

Approach 1
For example, consider the two orders: 1, 2, 3, 4, 5 and 2, 4, 1, 5, 3.
According to your approach, we will get a cycle 1->2->3->4->1. We then remove 3->4 and 4->1, and obtain a graph:
     ______
    /      \
1->2->4->5->3
 \______/

Now 5->3 and 1->2 respectively violate the first and the second orders, so we remove them, and get
     ______
    /      \
1  2->4->5  3
 \______/

Now node 2 has 2 outgoing edges. Removing either one makes a final graph where 3 nodes (1, 2, 3 or 1, 2, 4) have in-degree 0.
However, there exists a graph
1->3 2->4->5

where both orders are satisfied but only 2 nodes have in-degree 0.
So Approach 1 is incorrect.
Approach 2
Consider an optimal solution. Every edge in this optimal solution must be the form $(a_i,a_j)$ where $i<j$ in each order. This means all edges in the optimal solution are contained in the intermediate graph. So if you then remove the outgoing edges such that the number of nodes having in-degree 0 is minimum, you will get a correct optimal solution.
However, your approach that trying to make the number of nodes having in-degree 0 minimum is incorrect.
For example, consider the three orders:
\begin{align}
1, 2, 3, 4, 5, 6, 7, 8 \\
5, 1, 6, 3, 8, 2, 4, 7 \\
2, 7, 3, 8, 1, 4, 5, 6
\end{align}
First we can obtain the following intermediate graph:
    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3->4 5->6 7 8
 \ \__/
  \__/

Applying your approach, we will remove 1->4, 2->4 and 3->4 (or 3->8), and there are 5 nodes with in-degree 0: 1, 2, 3, 4 (or 8), 5. However, the optimal solution would be
     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5->6 7 8
 \___/

where only 4 nodes have in-degree 0: 1, 2, 3, 5.


What is the difference between E-Science Infrastructures and Distributed Computing Infrastructures? What is the difference between eScience infrastructures and grid computing or distributed computing infrastructures? And what are some of their examples.

I can not distinguish them clearly. Is it how a grid is used make it an e-science platform?

Both eScience infrastructures and grid computing are based on distributed computing, which is related to loosely-coupled applications. There are several models including client-server, peer-to-peer etc. The issues arising in distributed computing, such as security, failures, network partition etc must be taken into account at design time, since in this context failures are the rule and not the exception. Many large-scale scientific endeavors rely on distributed computing, such as for instance SETI@HOME, the projects using the BOINC middleware etc. However, these projects are not examples of grid computing.

Grid computing refers to the coordinated sharing of resources installed at different administrative domains, usually HPC resources. Each domain is called a Virtual Organization.
In contrast, the resources shared in projects such as SETI@HOME are usually common PC and laptops.

The grid computing paradigm emerged as a new field distinguished from traditional distributed computing because of its focus on large-scale resource sharing and innovative high-performance applications such as:

distributed supercomputing;
on demand computing;
high throughput computing;
data-intensive computing;

Distributed supercomputing applications require multiple supercomputers to solve problems otherwise too large or whose execution is divided on different components that can benefit from execution on different architectures. This class of applications present a number of challenges to be faced, like resource discovery and scheduling, coordinated startup, configuration at multiple sites, wide area message passing and fault tolerance. An example of such application is SF-Express, a distributed interactive simulation of a military battle. On demand computing refers to the possibility of dynamically acquiring online instruments (e.g. microscopes, satellite sensors and telescopes) connected by high-speed networks to gather and process the data generated. An experiment of microtomography at photon sources in 1999 demonstrated the feasibility of on demand computing. The aim of high throughput computing (HTC) is to schedule many independent jobs for parametric studies or data analysis; in this case a measure of efficiency is the number of jobs processed per unit of time. The two most important tools for HTC, namely Condor and Nimrod are now grid-aware. Data-intensive applications extract new knowledge from geographically distributed data archives or digital libraries; issues related to this class of applications include scheduling and configuration of multiple data flows through several hierarchy levels.

In the past, eScience infrastructures were almost always based on grid computing. Right now, cloud computing is also emerging as a viable alternative in some cases.


Anti-symmetry of polynomial time reductions I read somewhere that, if $A\leq_p B$ and $B\leq_p A$, then it is said that $A\equiv_p B$. What exactly does this mean? Is it saying that both $A$ and $B$ are the exact same level of complexity?

$A\equiv_p B$ is by definition $A\le_p B$ and $B\le_p A$.

It means that they are in the "exact same level of complexity", but only with respect to polynomial time reductions! For example, if $A\in LOGSPACE$ and $B\in NLOGSPACE$, then trivially $A\equiv_p B$. But clearly $A$ and $B$ are not in the "same level of complexity".

This is part of a general observation about reductions: A reduction that is computable by a machine that works in $t(n)$ time (resp. $s(n)$ space) is only useful if you use it in classes that are provable at least as strong as $TIME[t(n)]$ (resp. $SPACE[s(n)]$), and are conjectured to be stronger.

So, polynomial time reduction are used in $NP$ and $PSPACE$, $LOGSPACE$ reductions are used in $NLOGSPACE$, etc.


Algorithm to generate a token as survey summary I'm searching for an algorithm but struggle to find anything, as I'm not sure how to formulate it correctly. I created a simple survey app in Angular with 24 questions and each has 2-5 answers. When the user answered all the questions I'd like to give him a token (as short as possible) on the result page that he can note down, so the next time he can enter the token instead of having to answer all the questions again.
My thought process so far:

I can store the information in an array with 24 entries [1, 4, 2, ..., 2, 3]
As all values have 1 digit I can remove everything but the numbers 142...23

This still leaves me with a 24 digits long number. Nothing one would like to note down and type out by hand. So next I tried to convert this number (with ().toString(2)) to a binary with the goal to turned that binary into a human readable string with String.fromCharCode. But all I got was the rather not so human readable æ\u000f\u0000³KH\u0000\u0000\u0000 for my test input.
I could break down the number into digit pairs (e.g. 120422... -> [12, 04, 22, ...]) and map each of these to a character (00 -> A, 01 -> B, ...), but I think there must be something more elegant and efficient, as it would only half the original size. Although using 3 digits for mapping would result in 125 combinations which is rather hard to map to the alphabet, even with upper/lowercases and special characters. But I'd be very happy to hear your ideas. Many thanks in advance!

I think you should try converting your 24-digits (in base 10) number, in another base, which would reduce a lot the length of your token, while keeping the same information.
You should try experimenting with this website for example, which convert in base 36 (10 number + 26 letters):
http://www.unitconversion.org/numbers/base-10-to-base-36-conversion.html
Here, the number 986541236547896541258745 becomes 4GNE5T9XUQO08CKK
I'm sure you can devise an algorithm in base 62 (10 number, 26 lower cases letters, 26 upper cases letters), or event more if you use other characters, such as +-*&"# ... etc
EDIT:
found this website that allows you to convert from and to any bases between 2 and 62:
https://www.dcode.fr/base-n-convert
Here, the number 986541236547896541258745 becomes 4VMCgFPOG10DLH


Valid method to prove NP completeness of a problem? Suppose we are given that checking if there is a Hamiltonian path in a graph is NP Complete (HP problem). I want to prove that given a graph, node x, and node y, checking if there is a Hamiltonian path between x and y is NP Hard (HPN problem). Here is my proof:

Define a conversion from HP to HPN as follows:

result = False
for x in Nodes(G):
  for y in Nodes(G):
    result = result or hpn(G,x,y)
return result

This clearly solves the HP problem since it considers all possible starting and ending points. Also, HPN is called a polynomial (O(|Nodes(G)|^2) number of times. Hence, HPN must be NP-Hard since if it wasn't HP wouldn't be NP Complete and we know that this isn't true.

I understand I haven't used a reduction in the formal sense in my proof. However, I wanted to know if these sorts of "conversions" are valid in proving NP Hardness/Completeness.

Edit :  The goal was actually to prove NP hardness, not completeness, sorry!

No, they're not. NP-completeness is defined using many-one reductions and you've used a Turing reduction.  The difference, in a nutshell, is that for a many-one reduction, you're only allowed to make one call to the function you've called hpn, and you must return its result as your result.  Schematically, your reduction needs to look like:

Compute a graph G' and vertices x and y from the input graph G;
return hpn(G',x,y);


Recover NLFSR description from given output Given Fibonacci's Nonlinear Feedback Shift Register output, how can I recover the description (nonlinear feedback function and current seed)?

The clean output of consecutive and unmodified is large and the generator is available to ask for next values. The source code of PRNG is not available, the seed is unknown.

For the linear case there is already known Berlekamp-Massey (or Reed-Sloane) algorithm yielding the shortest polynomial. Is there a similar method for nonlinear case?

Normally we evaluate PRNGs under the model where the source code is available and fully known, and where the output is a deterministic function of the seed.  This leaves multiple possibilities for how to build a NLFSR: we can have a fixed feedback function (hardcoded in the source code), and use the seed to specify the initial state; or we can use part of the seed to generate a feedback function and use the remainder of the seed to specify the initial state.

If the feedback function $f$ is known, it is trivial to predict the next outputs of the NLFSR from the past $n$ bits, where $n$ denotes the width of the state.  Also, it is often possible to predict past output, but this depends on the feedback function and on $n$.

If $f$ is not known but derived from part of the seed, then the procedure depends on the details of how it is derived.  There are $2^{2^n}$ possible feedback functions $f:\{0,1\}^n \to \{0,1\}$.  If we use $2^n$ bits from the seed so we can sample uniformly at random from the set of all functions (i.e., all $2^{2^n}$ functions are possible and equally likely), then the PRNG is not very useful in practice.  After seeing about $O(2^{n/2})$ bits of output, you can usually distinguish the output of the PRNG from true-randomness and predict future outputs, because (by the birthday paradox) it is likely that the internal state will repeat at some point in there and the generator will enter a cycle (of length at most $O(2^{n/2})$).  Of course this design requires more than $2^n$ bits of true randomness as input, and can only produce $O(2^{n/2})$ bits of output before its output is recognizable, so this is a fairly crummy PRNG; you've basically wasted the randomness, and you might as well have just used the true-randomness directly without a PRNG.

Alternatively, perhaps you had in mind that part of the seed is used to select a feedback function $f$, via some algorithmic process -- but not all feedback functions are possible or equally likely.  Then the ability to distinguish, predict future outputs, or recover the seed is dependent upon the details of that algorithmic process.  However, we can say this much.  The output of the PRNG can be distinguished from truly-random after $O(2^{n/2})$ outputs, for reasons sketched above (due to the birthday paradox).

The period of a NLFSR is determined by the function $F:\{0,1\}^n \to \{0,1\}^n$, defined by

$$F(x_1,\dots,x_n) = (x_2,\dots,x_n,f(x_1,\dots,x_n)).$$

Let me mention some typical cases.

First, if $f$ satisfies $f(0,x_2,\dots,x_n)=f(1,x_2,\dots,x_n) \oplus 1$ for all $x_2,\dots,x_n$, then $F$ will be bijective, the period of the NLFSR will typically be about $2^n$ (if $f$ has no other regularities), and given about $2^n$ bits of output you'll be able to predict all future outputs (since it cycles) or recover the original seed.  Also, you'll be able to distinguish the output of the NLFSR from truly random with about $O(2^{n/2})$ bits of output (by the birthday paradox, a true random stream will have some $n$-bit value repeat twice within that range, but that'll never happen in the output from this type of NLFSR).

Second, if $f$ has no regularities or patterns and is basically random, then $F$ will fail to be bijective, and the period will typically be about $2^{n/2}$.  So, after $O(2^{n/2})$ bits of output you'll be able to predict all future outputs (since it cycles), and you'll be able to distinguish the output of the NLFSR from truly random with about $O(2^{n/2})$ bits of output (a true-random stream won't cycle but this NLFSR will).

If the feedback function $f$ is chosen randomly from a small list of possibilities (e.g., the ones listed in the paper you cited), then it is easy to recognize output from such a PRNG: just try each possibility in turn, and use the method described for the case where $f$ is known.  If there are $m$ possibilities for $f$, then $n+\lg m+O(1)$ bits of output suffice to infer which possibility is correct and verify that the output is consistent with such a NLFSR with high probability.

What this fails to account for is other attacks, which try to take advantage of structure in $f$.  For instance, suppose $f$ is chosen to have small circuit size.  Then it may be possible to recover $f$ with many fewer than $2^n$ bits of input: each consecutive $n+1$ bits of output gives us a known input-output pair $(x,y)$ for $f$ (namely, $x = $ the first $n$ bits, and $y =$ the $n+1$st bit), and given many such pairs, we can try to find a function $f$ that is consistent with all the pairs and has low circuit complexity.  That might be enough to uniquely determine the function $f$; if so, it may or may not be possible to recover it explicitly within a reasonable amount of computation (e.g., with BDDs, Karnaugh maps, or other methods).

Since the question is rather vague, that makes it rather hard to assess the possibilities for the latter kind of method.  So, I'll just end with a disclaimer that the analysis above might overestimate the number of bits of output needed to recognize/detect this kind of LFSR.


What does the "big O complexity" of a function mean? What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?

First of all, when people talk about big O complexity, they refer to the complexity of an algorithm, usually its running time. A somewhat better term is big O asymptotics. Big O makes sense to functions beyond the running time of an algorithm, indeed beyond any kind of complexity measure of an algorithm. Big O notation actually first appeared in the context of number theory, where it is used to simplify many statements.

Now back to your question. There really isn't any such thing as the big O complexity of a function. Let us take as an example your function. It has many big O estimates, such as:

$9n^2 + 10n = O(9n^2 + 10n)$.
$9n^2 + 10n = O(n^2)$.
$9n^2 + 10n = O(n^3)$.

The first two estimates are better than the third one, since they are tight: not only do we have $9n^2 + 10n = O(9n^2 + 10n)$, but in fact $9n^2 + 10n = \Omega(9n^2 + 10n)$, whereas it is not true that $9n^2 + 10n = \Omega(n^3)$. Comparing the first two estimates, the second one is better since it is simpler.

What does simple mean? Although this is an informal notion, everybody will agree that functions of the form $a^n n^k \log^\ell n$ are simple. If we fix this class of simple functions, then the unique simple function $f(n)$ such that $9n^2 + 10n = O(f(n))$ and moreover this is a tight bound is $f(n) = n^2$ (i.e., $a=1$, $k=2$, $\ell=0$). This could be termed "the" big O asymptotics of $9n^2 + 10n$, but a much better term would be the big $\Theta$ asymptotics of $9n^2 + 10n$, since the statement $9n^2 + 10n = \Theta(n^2)$ encompasses the property that this a tight upper bound.

This discussion suggests that when you are given an explicit function, you shouldn't be looking for big O and big $\Omega$ estimates – instead, you should aim higher, at a simple big $\Theta$ estimate.

The true role of big O and big $\Omega$ is in other situations. One situation is when analyzing the running time of an algorithm. The exact running time could depend on the input in a complicated way. For example, when running binary search on an array of length $n$, the algorithm could terminate after one step, two steps, or more – but always within $O(\log n)$ steps. We cannot describe the running time using big $\Theta$, since the best lower bound $\Omega(1)$ and the best upper bound $O(\log n)$ do not match. The same cannot be said about your example.

Another situation in which it makes sense to use big O and big Omega is when it is hard to find the exact asymptotics of a function. Take as an example the central binomial coefficient $\binom{2n}{n}$. Since $\sum_{m=0}^{2n} \binom{2n}{m} = 4^n$ and since
$$\binom{2n}{0} < \binom{2n}{1} < \cdots < \binom{2n}{n-1} < \binom{2n}{n} > \binom{2n}{n+1} > \cdots > \binom{2n}{2n-1} > \binom{2n}{2n}, $$
we can obtain the following upper and lower bounds:
$$
\frac{4^n}{2n+1} \leq \binom{2n}{n} \leq 4^n.
$$
This shows that $\binom{2n}{n} = O(4^n)$ and $\binom{2n}{n} = \Omega(4^n/n)$, where in both cases we are using simple functions as our estimators. The true rate of growth is $\binom{2n}{n} = \Theta(4^n/\sqrt{n})$, but this is harder to establish. In more complicated cases, it could be hard to find the exact rate of growth, or perhaps we are content with only an upper bound or only a lower bound, and then it makes sense to use big O or big $\Omega$.

One could also come up with contrived examples, which rarely happen in practice, in which there is no simple big $\Theta$ estimate for a given function. For example, consider the function
$$
f(n) = \begin{cases} n & \text{ if $n$ is even}, \\ n^2 & \text{ if $n$ is odd}. \end{cases}
$$
The best simple lower bound one could give is $f(n) = \Omega(n)$, and the best simple upper bound is $f(n) = O(n^2)$, but the two don't match.

Finally, while in analyzing algorithms we usually don't care about multiplicative constants, since they depend on details which our analysis abstracts away on purpose, in other situations it makes sense to ask for information beyond big Theta. For example, we can get an asymptotic estimate of the form
$$
\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}.
$$
Or we could ask for an asymptotic series, such as
$$
\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} - \frac{4^n}{8\sqrt{\pi} n^{3/2}} + O\left(\frac{4^n}{n^{5/2}}\right).
$$

At this point in your training, however, it's probably better to concentrate at the more elementary stuff, which is of more widespread use in computer science.


Daily Applications of Type Theory I want to understand type theory but I have to know first how I can apply it. Could there be more non-obvious applications of type theory aside from in type systems in programming? Could there be other applications, let's say in personality profiling and the likes?

You may be interested in the work on Ceptre, a result of the PhD research of Chris Martens, which uses type theory for interactive storytelling. Quoted below is the thesis abstract:

  Interactive storytelling weaves together deep computational ideas with humanity's rich history of story and play, providing an important context for tools and languages to be built. At the same time, formal specification languages offer a palette of representation and inference techniques typically reserved for the analysis of programming languages and complex deductive systems. This thesis connects problems in the interactive storytelling domain to solutions in formal specification.

  Specifically, we examine narrative from a structural point of view and observe that alternative narrative paths play a complementary role to simultaneous interacting timelines. Linear logic provides the representational tools necessary to investigate this structure, and by extending the correspondence to proofs and proof construction, we find a suite of computational possibilities. We present three efforts toward realizing those possibilities: (1) the use of linear logic programming to generate narratives; (2) a new programming language for authoring interactive narratives, games, and simulations; and (3) techniques for stating and proving design-level program properties.

  We find that linear logic programming, enriched with a minimal extension to its logical semantics, enables a wide range of programming idioms and domain encodings. As evidence, we give five case studies, including social simulation, combat-based adventure games, and board games. To support reasoning about design correctness, we present techniques for stating and proving program invariants, as well as a decidability proof for automatically checking those invariants for a large fragment of the language.

  These findings show that linear logic is a fruitful representation language to serve as the basis for modeling and executing interactive worlds, and they invite future investigations on using proof-theoretic methodologies for creative systems.


Understanding definition of epsilon closure and finite automata states I am going through the book , introduction to compiler design , by Torben Ægidius Mogensen.

It provides the following definition  of an epsilon closure :

Given a set M of NFA states, we deﬁne $\ \epsilon $-closure($\ M $) to be the least (in terms of the subset relation) solution to the set equation $\ \epsilon $-closure($\ M $) =$\ M $ $\ \cup $ {$\ t $|$\ s $ ∈ $\ \epsilon $-closure($\ M $) and $\ s^\epsilon t$∈T}, where T is the set of transitions in the NFA.

Initially , it defined the notion $\ a^b c $ to mean that  a transition from state $\ a $ to $\ b$  takes place when a symbol $\ c $ is encountered .

But in the above definition  $\ s^\epsilon t $ , $\ t$  is an element of the set of transitions , not the set of states .

This has resulted in a bit of confusion as to what exactly does an epsilon closure mean .

One more terminology word-play that wanted to be clear about is , the exact meaning of a sentence of the following sort :

"We extend the set of NFA states  with those  you can reach  from these by using only epsilon transitions ."

But in  a set of NFA states  , the epsilon transition would direct one state to another which would be already included in the set of NFA states. So , how is it possible to extend the same set with the elements already contained in it ?

Your textbook is being very formal, probably since it aims at using set equations later on. However, $\epsilon$-closure is a very simple concept. The $\epsilon$-closure of a set $M$ of states is the collection of states that can be reached from a state in $M$ by taking any number of $\epsilon$-transitions (possibly zero).

The textbook uses a different (but equivalent) definition: it defines the $\epsilon$-closure of $M$ to be the smallest set of states that contains $M$ and that for every state $s$ that it contains, contains all states reachable from $s$ by a single $\epsilon$-transition.

Regarding the second quote, there is some context missing. Here is one possible context which would make sense. For an NFA without $\epsilon$-transitions, we define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$. When we have $\epsilon$-transitions, there are several different possible definitions of the transition function. One possibility is to define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$ and then an arbitrary number of transitions labeled $\epsilon$ (possibly none).


Can't find a mistake in reduction from RE language to a non-RE language In the book Introduction to Automata Theory there is a question 9.3.4 that asks if a question "whether a language L(M) is infinite" is RE or non-RE? I've seen the answer, that its non-RE, however I tried a reduction from a Universal Turing machine language(which is RE) and it also seemed to work. Since a language can't be both RE and non- RE, there is a mistake and I can't figure out where. Please help!

My reduction from Lu (univeral TM) to Lm (infinite language TM):
The input to Lu is (M,w).
Build a new TM M' with an input x as follows, let it simulate a string w on M and if it accepts, then M' goes to states where it accepts a language 0^n, n>1, and accept its input x. If M rejects w or doesn't halt, then M' never accepts its input x. Then take the description of this machine M' and feed it into Lm. Therefore, if M accepts w, M' accepts an infinite language and Lm accepts it. If M doesnt accept w, then M' only accepts ∅ language, which is finite, hence Lm rejects.

Your reduction actually shows that $L_m$ is not co-RE. Indeed, if $L_m$ were co-RE, then your reduction shows that $L_u$ is also co-RE. However, $L_u$ is known to be RE but not recursive, hence cannot be co-RE.

Similarly, you can show that $L_m$ is not RE, by reduction from the complement of the halting problem: given an instance $(M,w)$ of $L_u$, create a new machine $M'$ which on input $n$ simulates $M$ on $w$ for $n$ steps. If $M$ halts, $M'$ gets into an infinite loop, and otherwise it halts. You can check that $M$ halts on $w$ iff $L(M')$ is finite.

The language $L_m$, usually known as INF, is actually one of the canonical examples of $\Pi_2$-complete languages, making it harder than the halting problem.

Your title suggests that you believe that RE languages cannot be reduced to non-RE languages. But in fact, every recursive language can be reduced to every non-RE language. I'll let you work this out.


QuickSort of linked lists optimised for duplicates This is an past year question for a school exam that I do not suggested solutions for.

Problem Description

Quick Sort is not stable because of need to swap values in array when partition is done. If we store the values to be sorted in a linked list, we can make quick sort stable. Also, we can easily improve the performance of Quick Sort by grouping all the values that are equal to the pivot to the middle so they do not need to be considered during the subsequent partitions. Consider the following code.

function ListNode quickSort(ListNode head)
    partition(params1)
    ListNode front = quickSort(params2)
    ListNode middle = params3
    ListNode back = quickSort(params4)
    return combine(front,middle,back)

Task

Identify what should be params1,params2,params3,params4

Use pseudocode to describe the partition method. Make sure that special cases such as when there is a null in parameter is taken care of. Also, the new version of QuickSort is in-place.

I think that quickSort should return the head node of the list, but then middle seems strangely placed in the code as I would think of putting it after after partition. Also, I do not know the pseudocode standards for linked list and whether it is similar to the case of the normal one done with arrays. Can anyone help me with this?

The point is that with linked lists you can reorganize them in-place. So, your partition method should return three separate lists: lower, middle and higher. Each list contains nodes from source list, only pointers are manipulated.


A $log(k)$ algorithm for the matroid secretary problem I'm reading the following article that presents a $log(k)$ algorithm for your secretary problem.

I'm in the analysis section at the left part of page 5 there is the following claim:

  $B^*$ is a set with elements $x_1,...,x_k$ with respective values
  $v_1,...,v_k$ where $v_1\geq...\geq v_k$. Denote $n_i(B^*)$ as the number of
  elements in $B^*$ with value at least $v_i$. Then the sum of the $q$
  largest elements is
  $[\sum_{i=1}^{q-1}(v_{i+1}-v_{i})n_{i}(B^{*})]+v_{q}n_{q}(B^{*})$

I fail to see how the sum presented is the sum of the largest $q$ elements. From what I understand $n_{i}(B^{*})=i$ since the elements with value at least $v_{i} $ are $v_{1},...,v_{i}$.

If I open the sum than all the inner element ($v_{2},...,v_{q-1}$) has a coefficient of $1$, but the coefficient of $v_{1}$ is $-1$ and the coefficient of $v_{q}$ is $2q$.

Can someone help me understand this equality?

It seems that there is a typo – $v_{i+1} - v_i$ should be $v_i - v_{i+1}$.

Suppose first that all elements are distinct. Then (using the convention $v_0 = 0$)
$$
 \sum_{i=1}^{q-1} (v_i-v_{i+1}) n_i(B^*) + v_q n_q(B^*) = \\
 \sum_{i=1}^{q-1} i (v_i-v_{i+1}) + q v_q = \\
 \sum_{i=1}^q i v_i - \sum_{i=2}^q (i-1) v_i = \sum_{i=1}^q v_i.
$$

Consider now the general case, in which we have
$$
v_1 = \cdots = v_{j_1} > v_{j_1+1} = \cdots = v_{j_2} > \cdots,
$$
where $j_r = q$. Then for $j_0 = 0$, $j_{r+1} = j_r+1$, and $v_{q+1} = 0$, we have
$$
 \sum_{i=1}^{q-1} (v_i - v_{i+1}) n_i(B^*) + v_q n_q(B^*) = \\
 \sum_{\ell=1}^{r+1} \sum_{t=0}^{j_\ell-1} (v_{j_{\ell-1}+t} - v_{j_{\ell-1}+t+1}) n_{j_{\ell-1}+t}(B^*) = \\
\sum_{\ell=1}^{r+1} (v_{j_{\ell-1}} - v_{j_{\ell-1}+1}) (j_1 + \cdots + j_{\ell-1}) = \\
\sum_{\ell=1}^r v_{j_\ell} j_\ell = \sum_{i=1}^q v_i.
$$
(This calculation might not be 100% correct, but you get the idea.)


Reductions versus generalizations I am reading Chapter 8 NP-complete problems in  Algorithms by Dasgupta et al and looking at some questions at the end of the chapter.
My own questions are below (after the image with the textbook questions). Note that I am not asking what the solutions are (those may be for separate questions) but rather the approach that makes the solutions right compared to what is in the chapter. My confusion  is in the difference between reductions and generalizations.

In the questions above, we are saying that a special case of any of the problems above are NP-complete complete. This seems like a misnomer though. Shouldn't this be a specialization rather than a generalization?

Another part of my confusion is how these so-called generalizations compare or contrast to reductions. Are we saying that some (special) version of a problem is NP-complete and therefore all the other instances are NP-complete? I thought that we needed to show that all instances of the problem are the NP-complete problem.

Regarding the direction of reductions: we reduce from a NP-complete problem (the hard problem) to the problem that we have at hand. For example, in the reduction from 3SAT to independent set we reduce from 3SAT that we know is NP-complete to what we have at hand, the independent set - did I misunderstand? Are these reductions generalizations? I thought that they were for all instances of the independent set.

Are generalizations reductions?

In the questions above, we are saying that a special case of any of the problems above are NP-complete complete. This seems like a misnomer though. Shouldn't this be a specialization rather than a generalization?

No.  The problem you are proving NP-complete is a generalization of a known NP-complete problem.  E.g. the MAX-SAT example contains Boolean satisfiability; just set $g$ large enough to demand satisfaction of all the clauses.

Another part of my confusion is how these so-called generalizations compare or contrast to reductions. Are we saying that some (special) version of a problem is NP-complete and therefore all the other instances are NP-complete? I thought that we needed to show that all instances of the problem are the NP-complete problem.

No, we're saying that if an NP-complete problem can be specified using the rules that describe a different problem without changing those rules, then that different problem is NP-hard, and is also NP-complete if that different problem is in NP.

Regarding the direction of reductions: we reduce from a NP-complete problem (the hard problem) to the problem that we have at hand. For example, in the reduction from 3SAT to independent set we reduce from 3SAT that we know is NP-complete to what we have at hand, the independent set - did I misunderstand? Are these reductions generalizations? I thought that they were for all instances of the independent set.

No, you should just think of reductions as reductions.  A generalization of an NP-complete problem contains that problem as a special case within the generalized problem.  A reduction provides a way to go from an instance of one problem to an instance of another without regard to whether one problem is a special case of another.

Are generalizations reductions?

No, they are an expansion of the original problem that still contains the original problem.  E.g. Boolean satisfiability is a generalization of 3-satisfiability because 3SAT is contained within the expanded problem set.


Will this program terminate for every Integer? In a Part Test for GATE Preparation there was a question :

f(n):
     if n is even: f(n) = n/2
     else f(n) = f(f(n-1))

I answered "It will terminate for all integers", because even for some negative integers, it will terminate as Stack Overflow Error.

But my friend disagreed saying that since this is not implemented code and just pseudocode, it will be infinite recursion in case of some negative integers.

Which answer is correct and why?

The correct answer is that this function does not terminate for all integers (specifically, it does not terminate on -1). Your friend is correct in stating that this is pseudocode and pseudocode does not terminate on a stack overflow. Pseudocode is not formally defined, but the idea is that it does what is says on the tin. If the code doesn't say "terminate with a stack overflow error" then there is no stack overflow error.

Even if this was a real programming language, the correct answer would still be "does not terminate", unless the use of a stack is part of the definition of the language. Most languages do not specify the behavior of programs that might overflow the stack, because it's difficult to know precisely how much stack a program will use.

If running the code on an actual interpreter or compiler causes a stack overflow, in many languages, that's a discrepancy between the formal semantics of the language and the implementation. It is generally understood that implementations of a language will only do what can be done on a concrete computer with finite memory. If the program dies with a stack overflow, you're supposed to buy a bigger computer, recompile the system if necessary to support all that memory, and try again. If the program is non-terminating then you may have to keep doing this forever.

Even the fact that a program will or will not overflow the stack is not well-defined, since some optimizations such as tail call optimization and memoization can allow an infinite chain of function calls in constant-bound stack space. Some language specifications even mandate that implementations perform tail call optimization when possible (this is common in functional programming languages). For this function, f(-1) expands to f(f(-2)); the outer call to f is a tail call so it doesn't push anything on the stack, thus only f(-2) goes onto the stack, and that returns -1, so the stack is back to the same state it was in at the beginning. Thus with tail call optimization f(-1) loops forever in constant memory.


Show that problem is PSPACE-complete - path in directed graph I have a following problem:
Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch circuit on this input and get result $0$.

Problem:
Is there exists path from vertex $k$ to vertex $l$ ?

I can reduce arbitrary problem from $PSPACE$ to above problem. The only thing that I can't do is showing that problem given in exercies belongs to PSPACE.

Tell me please, if my reasoning is correct (it seems to be too simple):
We know that $PSPACE = NPSPACE$. So we can give non-determinitic algorithm. Algorithm can guess sequentially verticles and check (using circuit) if there exists path).
I can say more, let algorithm guess ansewr (0 or 1).

Can you help me ?

Given $k$ and $l$ you can check if there is a path between these nodes using DFS. DFS requires polynomial space and time. So,  that problem is in PSPACE.

Update: I'd be glad to take into account the downvoter's opinion and improve the answer.


Polynomial multiplications and counting I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically speaking
$$S = \{s ; \text{ there exists } P \in {A\choose k} \text{ such that } s = \sum_{a \in P} a\}.$$
The object of the problem is to compute $S$ and for each integer $s \in S$, we have to find how many subsets of $A$ of size $k$ there are that sum up to $s$.

The constraints: $k$ is very small (can be considered constant) and I am looking for something subquadratic in $n$.

I tried to formulate the problem as a polynomial multiplication problem and solve it using FFT. So I built the polynomial $\rho$ as follows. I started with $\rho = 0$ and For each element $a \in A$, I added $x^a$ to $\rho$. Now for each exponent $r$ in $\rho^k$, the coefficient represents the number of combinations of $k$ elements in $A$ that sum up to $r$. However, these combinations include using the same element more than one time and count reorderings of the same subset.

I have been trying the following ideas:

Rebuilding my polynomial to count better.
Build and multiply different polynomials each representing a part of the problem (with some kind of divide and conquer technique).
Edit the polynomial resulting from the multiplication with some combinatorial argument (Subtract the numbers resulting from counting twice etc.). This helps when $\rho^2$ but could not make it work for higher values of $k$.

I appreciate any thoughts or hints about the problem :)

You already explained what to do when $k = 2$. Let's see what to do when $k = 3$. Let $P_i$ be the polynomial corresponding to $iS$ (for example, the solution for $k = 2$ is $(P_1^2 - P_2)/2$).

We can construct the following table:
$$
\begin{array}{c|ccc}
& aaa & aab & abc \\\hline
P_1^3 & 1 & 1 & 1 \\
3P_2 P_1 & 3 & 1 & 0\\
P_3 & 1 & 0 & 0
\end{array}
$$
So the solution for $k = 3$ is $(P_1^3 - 3P_2P_1 + 2P_3)/6$.

More generally, the solution will involve terms corresponding to all partitions of $k$. The coefficients presumably appear in some change-of-basis formula for symmetric polynomials, and you can find formulas by browsing monographs on the subject.


What's the regex corresponding to this DFA? Here is a DFA from a research project. We created the DFA manually.
We are interested in which regex is this DFA corresponding to.
Certainly, there could be multiple regex corresponding to it; we prefer a simpler one.

Inspired by the first answer from Karolis Juodelė, one correct Answer should be:

(00*10*1|1(0*|(10)*)*110*1)*1(0*|(10)*)*110*

$$(00^*10^*1 ~~~ | ~~~ 10^*(10)^*110^*1)^*~~~10^*(10)^*110^*$$
This should be one representation. Not sure if it could be made simpler. The part from $($ to $|$ represents one lap in the upper cycle. The part from $|$ to $)$ represents a lap in the lower cycle. The last part represents the path from $A$ to $D$.


Is the language in the description context free? I am stuck on a question. Lets say there is a string that can be created from three alphabets a,b,c the condition is number of a<= number of b<= number of c. I can solve if there are a and b (two alphabets) but I am not able to solve for 3. Any help will be appreciated.
Thanks

The basic problem here is that context-free languages are not closed under intersection.

The example you give illustrates this. Thus, $\{ w\in\{a,b,c\}^* \mid |w|_a \le |w|_b\}$ is context-free, and similarly, so is $\{ w\in\{a,b,c\}^* \mid |w|_b \le |w|_c\}$. The intersection of these two languages $\{ w\in\{a,b,c\}^* \mid |w|_a \le |w|_b \le |w|_c\}$ is not context-free.


Algorithm to figure our deps in a graph that can resolve deps from cache (dictionary) of walked paths I have a graph like this that starts from one top node and has cycles:

I need to write an algorithm to figure if node1 depends on node2. The most primitive algorithm I've written simply starts with node1 and recursively follows all available edges looking for node2 starting from node1. It's very inefficient because I traverse the graph over and over again. I'm wondering if there's an algorithm I can look at that caches nodes and dependencies it already walked through so that I don't go through paths I've walked once and can figure if there's a dependency or not from cache?
For example, if I'm given node D and the question is whether it depends on node F, I'll walk D->E->F, and when next time I get the question if node E depends on F, I'll get that from cache without walking the graph.
Thanks for any ideas and suggestions!

This is a classic problem known as "reachability querying". There are various algorithms possible, with different complexities.
Unless you are working with some huge graphs and can not afford to store the index, the simplest is storing the $O(|V|^2)$ transitive closure of your graph. This can be computed quite simply with Floyd-Warshall in $O(|V|^3)$, and with a lot more effort in $O(|V||E|)$ using the methods found in Nuutila's thesis.
Now if your graphs are truly large and you can not afford to spend $O(|V|^2)$ memory you enter an academic world of dozens upon dozens of papers, each with slightly varying performance characteristics (very often incomparable, yet almost always claiming to beat the competition), and varying difficulty of implementation. I guarantee you that almost all of them will be hard to implement however.
Allow me to reproduce Table 1 from Reachability querying: an independent permutation labeling approach, a recent paper by Hao Wei et. al. Here we have as main parameters $n = |V|$, $m = |E|$, $k$ is the width of the graph, $t$ is the number of non-tree edges of the graph after a spanning tree is formed.


What is the difference between Big O and Theta notation in terms of inputs? In Coreman , it's written :

  The $O(n^2)$ bound on worst-case running time of insertion sort also applies to its running time on every input. The $\Theta(n^2)$ bound on the worst-case running time of insertion sort,however, does not imply $\Theta(n^2)$ bound on the running time of insertion sort on every input.

So, is there any difference between the two notations in terms of input? If so, then why does it use $\Theta(n^2)$ in worst case running time of insertion sort?

The best case runtime of insertion sort is linear, i.e. $\Theta(n)$. Therefore, there is no $\Theta(n^2)$ bound on all inputs, since that would require $\Omega(n^2)$ on all inputs.

This is just one example proving that while $O$-bounds on the worst-case translate to all-case, but $\Omega$-bounds (and therewith $\Theta$-bounds) do not. (Which is, of course, the point in the text.) You can also investigate this mathematically by unfolding the definitions.


What is Memory Mapping in Cache? People all over the internet are asking "What are the different Memory Mapping Techniques in Cache", but i couldn't find anywhere the answer to "What is Memory Mapping exactly?".

Please tell what do you mean by memory mapping?

Memory mapping is the (complex) process that associates an address value (usually a 32 or 64 bits number) to some existing physical location in the hardware. This location can be in RAM, in a cache of some level, or even on the hard disk ! During program execution, data can move from one location to another, and possibly be duplicated.

The system keeps track of that and makes the mapping transparent so that the program can keep using the same address. Things get tricky when the values are modified and coherence between the copies must be guaranteed.


Algorithm SAGE- PARI? for splitting polynomials over field extension I tried to follow with SAGE the solvability of solvable quintic polynomial. I took the example of the solvable polynomial $f=T^5+15T+12$, fully studied in Dummit. I understand that the splitting field $L$ is radical with $[L:\mathbb{Q}]=20$.

The square root of the discriminant is (SAGE)  $2^53^25^2\sqrt5$ so we have a quadratic subfield $k=\mathbb{Q}(\sqrt{5})\subset L$. This polynomial (as a function) is strictly increasing over $\mathbb{R}$  so has a unique real root $x$.  We consider the extension $k(x)/k$ of degree $5$ ($f$ is still irreducible over $k$) so the last extension of the chain of subfields $\mathbb{Q}\subset k=\mathbb{Q}(\sqrt{5})\subset k(x)\subset L$ is quadratic. The polynomial $f$ must split over $k(x)\;(\subset\mathbb{R})$ into a product of the linear factor $(T-x)$ and two quadratic factors $P_1,P_2 \in k(x)[T]$ whose roots are the pair of complex conjugated roots $x_1$,$\bar{x}_1$,$x_2$,$\bar{x}_2$ of $f$.

We can write the euclidean division $f(T)/(T-x)$ in the form:
$$P_1P_2=T^4+xT^3+x^2T^2+x^3T+x^4+15$$
   $$= \left(T^2 +A(x)T+N_1(x)\right)\;\left(T^2 +C(x)T+N_2(x)\right)\in k(x)[T]$$

How does SAGE gives the coefficients of $P_1=(T^2 +A(x)T+N_1(x))\in k(x)[T]$?
The result given by SAGE is: (recall that the ground field is $\mathbb{Q}(\sqrt{5})$ and that $x$ is a root of $T^5+15T+12$, in other words $x^5\equiv -15x-12$)

$A(x)=\frac{\sqrt{5}}{10}x^4 + \frac{\sqrt{5}}{10}x^2 +(\frac{\sqrt{5}}{10} + \frac12) x + \frac{6\sqrt{5}}{5}=x_1+\bar{x}_1$

$N_1(x)=(\frac{\sqrt{5}}{20}+\frac14)x^4+ (\frac{\sqrt{5}}{20} - \frac14) x^3 + (-\frac{3\sqrt{5}}{20} + \frac14)x^2 + (\frac{3\sqrt{5}}{20} - \frac34) x + 3=x_1\bar{x}_1$

and I feal that understanding how SAGE/PARI computes this would give a better understanding of field extensions.

Further, the simplier example for the last quadratic extension $L/k(x)$. It is generated by any other root. Take one root $x_1$, so $x_1^2\in k(x)$, and define the quadratic extension $L=\{k(x)+x_1k(x)\}$ generated by this root. It's conjugate (over $k(x)$) is $x'_1=-A-x_1$. The other pair is $x_2=a+bx_1$ whose conjugate (over $k(x)$) is $x'_2=a'-bx_1$, and both are roots of $P_2=T^2+CT+N_2$ with $x-A=C$ and $xN_1N_2=-12$. How does SAGE finds the values $a,a',b$?

I though the answer was easier than what I found, so no real chance to do this "by hand". The article from Factoring Polynomials  describes a process over $\mathbb{Q}$ called the Zassenhauss method:  first factor modulo $p$ (say Berlekamp algorithm, rather accessible), then Hensel lift back and check bounds on coefficients and other tests. The Klueners article describes the "van Hoeij" algorithm which I admit is above my math understanding capabilities.

It also describes the "Trager method" over a field extension. Find a primitive element, compute it's minimal polynomial over $\mathbb{Q}$, factor it with say the previous method, so the extension is the field modulo the maximal ideal generated by the minimal polynomial, and apply chinese remainder to decompose the given polynomial.


What is the most recent comparison of signature files and inverted indices? Modern papers on search indices often contain a statement that inverted indexes (posting lists) are categorically superior to signature files (bloom filters). Here are some examples from papers published in 2016:

While this [signature file] technique provides a relatively low computation overhead, studies by Zobel et al. [1998] have shown that inverted files significantly outperform signature files.
Inverted indexes have been benchmarked as the most generalisable, and well performing structure (Zobel et al., 1998)

Every paper seems to cite Zobel et al., Inverted files versus signature files for text indexing.
However, if I'm reading Zobel et al. correctly, the argument they make isn't fundamental (e.g., an asymptotic bound or an information theoretic limit). Rather, the argument seems to be, given signature files implemented with techniques X, Y, and Z compared to inverted indices implemented with techniques A, B, and C, and the current technology of the day (disks with very high seek/access overhead), inverted indices are superior because they require fewer seeks and there are faster.
Is there a more recent comparison that compares these techniques on SSD, NVMe, or RAM, or is there a more recent comparison that looks at "new" techniques that have been invented since 1998?

Don't know any fresh references.

Off the top of my head:

Signature files require candidate verification via forward files. This requires lots of random accesses, basically one per potential match. One random memory access is 100+ CPU cycles. You can do a lot of work in 100 CPU cycles (e.g., you can decompress more than 100 IDs single core http://boytsov.info/pubs/simdcompressionarxiv.pdf).

Random access speed is even worse in the case of HDD or even SSD. There is in fact a growing gap between random and sequential access speed.

Before making this random access you cannot do pruning, early-termination, etc... BTW, for the most fancy recent data structure, you should probably check partitioned Elias-Fano indices:
http://pages.di.unipi.it/rossano/wp-content/uploads/sites/7/2015/11/sigir14.pdf


Digraph vertices: classification by counting outgoing walks I'm reproducing a question I posted on MSE (yet with no answer both there and by myself).

Given a (finite) directed graph $G = (V, E)$. For each vertex $v \in V$ and a natural number $n$, let $W_v(n)$ be the number of walks in $G$ of length exactly $n$ originating at $v$. That is,
$$W_v(0) = 1 \quad\text{and}\quad W_v(n + 1) = \sum_{\substack{u \in V \\ (v, u) \in E}} W_u(n).$$
Now, for $u, v \in V$, let $u \sim v$ iff $W_u(n) = W_v(n)$ for all $n$. This equivalence of vertices induces a partitioning of $V$. What is known on the complexity of computing this partition?

(By "computing", it may have meant an algorithm that assigns each vertex $v\in V$ a number of its class, so that two vertices are equivalent iff they get assigned the same number. I do see some resemblance to the Hopcroft's DFA minimization algorithm, but still the problem being solved is different... and I see this to be a corner case of some harder problems.)

Let $A$ be the adjacency matrix of the graph, let $\mathbf 1$ be the all-ones vector, and let $\delta_v$ be the indicator of vertex $v$. Then
$$
W_v(t) = \delta_v A^t \mathbf 1.
$$
It follows that $v \sim u$ iff for all $t$,
$$
(\delta_u - \delta_v) A^t \mathbf 1 = 0.
$$
Let $n = |V|$. The Cayley–Hamilton theorem shows $A^t$ is always a linear combination of $A^0,\ldots,A^{n-1}$. Therefore
$$
v \sim u \Longleftrightarrow (\delta_u - \delta_v) A^0 \mathbf{1} = \cdots = (\delta_u - \delta_v) A^{n-1} \mathbf{1} = 0.
$$
The latter property can be checked in polynomial time, so the partition can be computed in polynomial time. This procedure can be optimized by computing the kernel of the matrix
$$
\begin{bmatrix}
A^0 \mathbf{1} \\
\cdots \\
A^{n-1} \mathbf{1}
\end{bmatrix}
$$
and then finding all $\delta_u-\delta_v$ that belong to it.


What algorithm to use for this kind of routing optimization? Let's imagine a situation in order to fully understand the problem : let's say a lone human is walking back home at a very late time. He needs to find the safest path home. He naturally use the GPS with a start point A and a destination point B. Now the data I have may be GPS locations with an information stating the danger of that location, and those datas are usually available for the whole city. How can I actually plot the safest and also (if possible) fastest route from A to B using my datas ?

I actually looked for the way google maps plot it's routes and I understood it used the Dijkstra's algorithm, but it doesn't seem to be adapted to my problem.

I believed google maps could actually send me back every possible routes from A to B, then I could use my datas to calculate the safest route using a TSP algorithm (probably the ACS applied to the TSP) in order to optimize the use of the datas and with edge weights corresponding to the associated safety of the sub-path ?

Or maybe another algorithm should be used ?

The answer depends on what you mean by "safest".

According to one interpretation, each short stretch of the route has a "danger" rating, and the overall danger of a route is the sum of the dangers of the individual stretches. In this case your problem is just shortest path in disguise – given each edge a weight according to its danger. If you want to consider both the danger level and the length, assign the weights as some linear combination of the two.

According to another interpretation, the danger of a route is the maximum of the dangers of the individual stretches. In this case you can use binary search to reduce your problem to shortest path. Given a danger level $D$, you can compute the shortest distance that only goes through edges of danger at most $D$. In this way you can find the minimal $D$ for which it is possible to get from A to B, as well as (for example) the minimal $D$ for which it is possible to get from A to B using a path at most twice the distance from A to B.


How to read off the set represented by a van-Emde-Boas tree? I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to understand the actual data structure. I have no clue how the "min" and "max" members are actually used, I'm not talking about the procedures but just how the following picture is supposed to be interpreted. Can anyone help me with this?

If you haven't done so, I suggest you read chapter 20 from the beginning. They develop the final data structure bit by bit, supposedly for didactic reasons.

In 20.3.1, they write:

  min stores the minimum element in the vEB tree, and max stores the maximum element in the vEB tree. Furthermore, the element stored in min does not appear in any of the [subtrees].

What might confuse you is that the actual elements to not appear. As explained earlier in the chapter, the elements are encoded by position: the domain of the tree is $[0..15]$, and the subset is essentially encoded by a bit vector stored in the leaves of the tree. Figure 20.4 is annotated helpfully in this regard; note that the minimums are moved up to the min fields here, though.

In the full VEB tree, the encoding itself is a little tricky. Here goes:

Here is how you read the tree (ignore the dark summary nodes for this purpose):

u denotes the size of the domain of a node.
The root has domain [0..u-1].
The domain of a node cluser[i] is the the i-th chunk of size cluser[i].u in the domain of its parent.
If they are not nil, min and max are indices into the domain of the node.
If min and max are nil, the node represents no elements.

Examples:

root.cluster[1].min is 0; it represents element 0 + 1*4 * 0 = 3.
root.cluster[0].cluster[1].min/max are nil; therefore 0 + 0*4 + 1*2 + 0/1 = 2/3 are both not in the node.
But 2 is in the set anyway, since it's represented by root.min!
root.cluster[3].min is 2; therefore, 0 + 3*4 + 2 = 14 is in the set.
root.cluster[3].cluster[1].min/max are 1; therefore 0 + 3*4 + 1*2 + 1 = 15 is in the set.


Analyzing parallel performance question I was reviewing for my CS class and came across this question and answer combo that didn't have any explanation why it was correct. I'm confused on how they got the answer:

We have a system to which we can instantaneously add and remove cores
-- adding more cores never leads to slowdown from things like false sharing, thread overhead, context switching, etc
When the program foo() is executed to completion with a single core in
the system, it completes in 20 minutes. When foo() is run with a total
of three cores in the system, it completes in 10 minutes.
If 100% of foo() is parallelizable, with 3 cores it would take
20/3=6.66 minutes. Since it instead takes 10 minutes, what fraction of
foo() is parallelizable?

ANSWER GIVEN: 0.75

How many minutes would it take to execute foo on this magical system
as the number of cores approaches infinity?

ANSWER GIVEN: 5
Could someone explain how the staff got these answers?

Suppose that the fraction of foo() that is parallelizable is $\alpha$. Then the total execution time with $n$ cores is:

the non-parallelizable execution, done by only one core: $(1- \alpha)\times 20$
the parallelizable execution: $\alpha \times 20 \times \frac{1}{n}$

Then, for the first question, we have to consider that the number of cores is $3$, and the total time is $10$. The equation becomes:
$(1-\alpha)\times 20 + \alpha\times \frac{20}{3} = 10\Leftrightarrow \alpha = 0.75$.
For the second question, we suppose known the answer to the first question: $\alpha = 0.75$, and we suppose then that $n = \infty$. The total execution time becomes:
$0.25 \times 20 + 0.75\times \frac{20}{\infty} = 0.25 \times 20 = 5$.


Closest pair of points in a Plane I want to write an algorithm to find the closest pair of points among n points in an XY-plane. I have the following approach in my mind:

Find the minimum x co-ordinate(minX) and minimum y(minY) co-ordinate.
Name the point origin= (minX,minY)
Find the distance of all points from this origin and store it in a vector dist[].
Sort the vector dist[].
Traverse through the vector dist and for each i=1 to n-1, do dist[i+1]-dist[i] and keep track of the minimum of these and the pair that form this minimum.
Return minimum and the pair.

I am not sure if this algorithm would work because of how triangle inequality works.

Any help on why this algorithm should/should not work?

No, your approach will not work

Let $O$ be your chosen origin. Let $A$, $B$ be two of your other points. $OAB$ form a triangle.

The vector you have in mind would contain the distances $\overline{OA}$ and $\overline{OB}$. You can not determine the distance $\overline{AB}$ using only the two other sides of the triangle. You would need at least one of the angles for that.

As for a concrete counter example:

$O = (0,0), A = (0,2), B = (0,5), C = (2,0)$

so your vector would be:

$\overline{OA} = 2, \overline{OC} = 2, \overline{OB} = 5$

The differences are:

$\overline{OA}-\overline{OC} = 0$

$\overline{OC}-\overline{OB} = -3$

$(C, B)$ forms the minimum of but the closest pair is $(A, B)$ with a distance of 3.


Algorithm to establish a global ranking given individual rankings I am looking for an algorithm(s) that can compute a global ranking (partial ordering) given individual rankings, in some kind of principled manner.

I want to establish a partial-ordering of some projects, and had some users create their own partial orderings.

I've looked at these algorithms so far:

borda-0
borda-1
Dowdall

My problem is that these algorithms were not really designed to establish partial-ordering and are instead for choosing N winners. I haven't been able to find any widely-used algorithms for this purpose.

I looked at adapting STV to this purpose, but raw STV gives no instructions on how to resolve ties, and it's unclear to me what properties it would have when applied to partial ordering.

Is there a widely-used algorithm/family of algorithms for the problem?

There is an entire area, rank aggregation (in your case, partial rank aggregation) which deals with these issues. You can take a look at Dwork et al., Rank aggregation revisited and Ailon, Aggregation of partial rankings, $p$-ratings and top-$m$ lists and the pointers therein. There are many other relevant papers online.


Does integer programming $\in$ NP imply $NP=CoNP$? Although it is relatively simple to see that integer linear programming is NP-hard, whether it lies in NP is a bit harder. Therefore, I'm wondering whether the following reasoning shows that $ILP\in NP$ implies $NP=CoNP$.

To be precise, I am considering the decision variant of ILP over a non-unary input encoding, so the problem is: given an integer matrix $A$; an integer vector $b$,  does there exist an integer vector $y \in Z_n$ with $Ay \leq b$?

The main issue here is that if we take such an $y$ as NP-certificate, it might be of exponential size in terms of the input, but this of course does not mean a certificate cannot exist.

My idea was that if we assume ILP in NP, we can use a discrete version of the Farkas lemma (see here) to transform an ILP instance with the answer NO to an ILP instance with the answer YES, which then would imply that ILP is in coNP. So we get an NP-complete problem in coNP, which implies that $NP=coNP$. Since most people think $NP\neq coNP$, this is 'evidence' for ILP not being in NP.

However, I'm not sure if my reasoning is correct. In particular, does this 'discrete Farkas lemma' work in polynomial time and create an ILP of polynomial size of the original one?

The notion of duality suggested by the discrete Farkas lemma found in Lasserre's paper does not correspond to an integer program. There is a notion of duality for integer programs (see for example here), but strong duality does not hold, so I doubt it can be used along the lines you suggest.


DFS - Checking if a graph is bipartite I wonder what will be the complexity of this algorithm of mine and why, used to check whether a graph (given in the form of neighbors list) is bipartite or not using DFS.

The algorithm works as following:

We will use edges classification, and look for back edges.

If we found one, it means there is a circle in the graph.

We will now check whether the cycle is odd cycle or not, using the the pi attribute added to each vertex, counting the number of edges participating in the cycle.

If the cycle is an odd one, return false. Else, continue the process.

Initially I thought the complexity will be O(|V| + |E|) as |V| stands for the number of vertices in the graph, and |E| stands for the number of edges in the graph, but I am afraid it might take O(|V| + |E|^2), and I wonder which option is correct and why (it may not be any of the above as well). Amortized or expected run times may also be different, and I wonder how can I check them as well. Please help me figure!

pseudo code

DFS(G=(V,E))
// π[u] – Parent of u in the DFS tree
1 for each vertex u ∈ V {
2 color[u] ← WHITE
3 π[u]← NULL
4 time ← 0}
5 for each vertex u ∈ V {
6 if color[u] = WHITE
7 DFS-VISIT(u)}

and for the DFS-Visit:

DFS-Visit(u)
// white vertex u has just been discovered
1 color[u] ← GRAY
2 time ← time+1
3 d[u] ← time
4 for each v ∈ Adj[u] { // going over all edges {u, v}
5 if color[v] = WHITE {
6 π[v] ← u
7 DFS-VISIT(v) }
8 else if color[v] = GRAY // there is a cycle in the graph
9 CheckIfOddCycle (u, v);
10 color[u] ← BLACK
// change the color of vertex u to black as we finished going over it
11 f[u] ← time ← time+1

and as for deciding what type of cycle is it:

CheckIfOddCycle(u, v)
1 int count  ← 1;
2 vertex p = u;
3 while (p! = v) {
4 p ← π[p]
5 count++ }
6 if count is an odd number {
7 S.O.P (“The graph is not bipartite!”);
8 stop the search, as the result is now concluded!

Thanks!

While your algorithm is visiting a node $v$, if it detects a back edge $(v,u)$ then it backtracks until it reaches $u$, using the parent information stored in pi, counts the number of edges,  and then decides if it is bipartite or not. In this case your edges and nodes are visited at most two times (once when you move forward and once when you backtrack) which is still linear, i.e. is $O(V + E)$.

As for average and amortized case analysis I have never done such a thorough analysis of dfs but my guess is both are $O(V+E)$.


Why is the node with the greatest DFS post-order number not necessarily a sink? A sink in a directed graph is a node with no outgoing edges. If I perform a depth first search, why is it that the node with the least post-order number (and thus the highest pre-order number) not necessarily a sink - isn't this node found last?

Also, intuitively, the node with the greatest post-order number should be a source - a node with no incoming edges.

If your graph is strongly connected, there is no sink, so I guess that answers your question...


TSP when cost depends only on location in sequence I want to change the original TSP problem as follows: the cost to visit a city is not related to the previous city that it visited just now, but only on its position in the sequence. Is the problem of finding the minimal cost tour still NP-complete?

Your problem is the same as minimum-weight perfect matching in a bipartite graph. If there are $n$ cities, consider the bipartite graph in which one side consists of vertices $p_1,\ldots,p_n$, the other side consists of vertices $c_1,\ldots,c_n$, and the weight of the edge $(p_i,x_j)$ is the cost of city $j$ at position $i$.

A minimum-weight perfect matching in a bipartite graph can be found efficiently (this is known as the assignment problem). In particular, the problem is not NP-hard unless P=NP.


What are the differences between search problems, optimization problems, and decision problems? How do we differentiate these classes of problems?

A decision problem has this form:

Input: $x$
Output: "Yes" if $\phi(x)$ holds, "No" otherwise

A search problem has this form:

Input $x$
Output: $y$ such that $\psi(x,y)$ holds, if such a $y$ exists. "No" otherwise.

Finally, an optimization problem has this form:

Input $x$
Output: $y$ such that $f(x,y)$ is the minimum possible, i.e. $f(x,y) = \min_{y'} f(x,y')$

Here $\phi$ and $\psi$ are some boolean properties, and $f$ is some natural number function of $x$ and $y$.


What happens to multi-qubit quantum state after one of qubits is measured? If we have a quantum state consisting of (let's say) 3 entangled qubits and we read the value of one of them, what happens to the probabilities of the remaining possible states?

For example, if we have three entangled qubits and have an amplitude for every state from $|000\rangle$ to $|111\rangle$ and we measure the second (middle) qubit to be 1, the remaining states are $|010\rangle, |011\rangle, |110\rangle, |111\rangle$. If we know the amplitudes for all possible 9 states before the measurment, how do we get the amplitudes of the remaining states after measurment?

The amplitudes are scaled so that their norm is 1. In your case, if the original amplitudes are $\alpha_{000},\ldots,\alpha_{111}$, then after measuring the second bit to be 1, which happens with probability $p = \alpha_{010}^2 + \alpha_{011}^2 + \alpha_{110}^2 + \alpha_{111}^2$, the quantum state is
$$
\frac{\alpha_{010} \left|010\right\rangle + \alpha_{011} \left|011\right\rangle + \alpha_{110} \left|110\right\rangle + \alpha_{111} \left|111\right\rangle}{\sqrt{\alpha_{010}^2 + \alpha_{011}^2 + \alpha_{110}^2 + \alpha_{111}^2}}.
$$