Why is least fixed point (lfp) important in program analysis I am trying to get a big picture on the importance of least fixed point (lfp) in program analysis. For instance abstract interpretation seems to use the existence of lfp. Many research papers on program analysis also focus heavily on finding least fixed point.

More specifically, this article in wikipedia : Knaster-Tarski Theorem mentions that lfp are used to define program semantics.

Why is it important? Any simple example helps me. (I am trying to get a big picture).

EDIT

I think my wording is incorrect. I donot challenge the importance of lfp. My exact question (beginner) is: How does computing lfp help in program analysis? For e.g., why/how abstract interpretation uses lfp? what happens if there is no lfp in the abstract domain?

Hopefully my question is more concrete now.

Any form of recursion or iteration in programming is actually a fixed point. For instance, a while loop is characterized by the equation

while b do c done  ≡  if b then (c ; while b do c done)

which is to say that while b do c done is a solution W of the equation

W  ≡  Φ(W)

where Φ(x) ≡ if b then (c ; x). But what if Φ has many fixed points? Which one corresponds to the while loop? One of the basic insights of programming semantics is that it is the least fixed point.

Let us take a simple example, this time recursion. I will use Haskell. The recursive function f defined by

f :: a -> a
f x = f x

is the everywhere undefined function, because it just runs forever. We can rewrite this definition in a more unusual way (but it still works in Haskell) as

f :: a -> a
f = f

So f is a fixed point of the identity function:

f ≡ id f

But every function is a fixed point of id. Under the usual domain-theoretic ordering, "undefined" is the least element. And indeed, our function f is the everywhere undefined function.

Added on request: in the comments OP asked about the partial order for semantics while loops (you presumed it was a lattice but it need not be). A more general question is what is the domain-theoretic interpretation of a procedural language which can manipulate variables and has the basic control structures (conditionals and loops). There are several ways of doing this, depending on what exactly you want to capture, but to keep things simple, let's assume that we have a fixed number $n$ of global variables $x_1, \ldots, x_n$ that the program can read and update, and nothing else (no I/O or exceptions, or allocation of new variables). In that case a program can be seen as a transformation of the initial state of the variables to the final state, or the undefined value if the program cycles. So, if each variable holds an element of a set $V$, a program will correspond to a mapping $V^n \to V^n \cup \{\bot\}$: for every initial configuration $(v_1, \ldots, v_n) \in V^n$ of the variables, the program will either diverge and yield $\bot$, or it will terminate and produce the final state, which is an element of $V^n$. The set of all maps $V^n \to V^n \cup \{\bot\}$ is a domain:

we use the flat ordering on $V^n \cup \{\bot\}$ which has $\bot$ at the bottom and all the elements of $V^n$ "flat" above it, and then $V^n \to V^n \cup \{\bot\}$ is ordered pointwise,
the least element is the function which always maps to $\bot$, corresponding to the program while true do skip done (and many others),
every increasing sequence has a supremum

Just to give you an idea of how this works, the semantics of the program

x_1 := e

would be the function which takes as input $(v_1, \ldots, v_n) \in V^n$, calculates the value $v_e$ of the expression e in state $(v_1, \ldots, v_n)$, and returns $(v_e, v_2, \ldots, v_n)$.


Can preorder and postorder traversals be used on any type of trees? I could not find an answer to the question directly by google.
I think this question is rather simple but I am not really sure about it.
Any advice is welcomed.
Thanks

Well, yea. But you need to define formally what a "type of tree" could be. General trees, are described by the mathematical notion of a tree graph. Given some ordering on the nodes of the tree, and some definition of which node is the root of the tree, you can perform the "pre-order" and "post-order" traversals.
The algorithms that computes them are also very similar to the ones you are probably familiar with, with the small change that you need to iterate all children instead of just traversing on the two children (since the number of children isn't restricted here).
However, the in-order is not defined properly for trees without also defining a notion of what children are "to the left" of the root and what children are "to the right" of the root. When you give a formal definition to this idea as well, you can perform the in-order traversal as well.


Language of all strings that has exactly 1 triple b I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.

Suppose we have a language L, Language of all strings that has exactly 1 triple “b” defined over alphabet set Σ = {a, b}
Now after several tries, I came up with this
(a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )* but then I realize that this is wrong too because the string abbbabababb doesn't fit on this.

Kindly someone point out at my mistake or help me solve it as I have spent almost an hour on this.

It seems you are almost there.  You just need to care substrings with $abb$. One possible way is
$R.E = (a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$

Note that I came upon this regular expression from the $FM$ of language you described. So, another way to find $R.E$ is from $FM$ directly.


Is the set of language decidable by some Turing machine computing in some given computable time bound decidable Let $T : \mathbb N \to \mathbb N$ be some computable function. Then by $\mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an input $w$.
In On the Computational Complexity of Algorithms by J.Hartmanis and R.E. Stearns it is stated that $\mathcal C_T$ is recursively enumerable (they consider a notion of computable sequences, but this is the same as a $\{0,1,\}$-sequence could be considered a subset of $\mathbb N$, and going from to $\mathbb N$ to $\Sigma^*$ does not change anything) and their proof goes by enumerating all machines, and modifying them in order to stop after $T(|w|)$ moves and print zero (this used the computability of $T$). By this procedure for each element in $\mathcal C_T$ some machine is enumerated for it.

But I noticed that also the complement of $C_T$ is recursively enumerable. A machine to accept this set (and do not halt for elements not in the set) could operate according to the following scheme:

Given a Turing machine $M$ as input, we want to know if it halts in at most $T(n)$ steps on each input. Let $\Sigma^{\ast} = \{w_1, w_2, w_3, \ldots \}$
and $c : \mathbb N \to \mathbb N \times \mathbb N$ be some computable pairing function. Then set up a counter $i = 1, 2, 3, \ldots$ and for each $i$ write $(j,k) = c(i)$. Then simulate the machine $M$ on input $w_j$ for $k$ steps, if $k > T(|w_i|)$ and the $M$ has not halted before $k$ steps (i.e. is still in a non-halting state) then accept it.

A turing machine could operate according to the above algorithm and this would give us a machine that takes another machine and accepts presicely those that run on some input of length $n$ more than $T(n)$ steps (and runs forever for all the others).

Hence it accepts the complement of $\mathcal C_T$. So both sets are recursively enumerable, hence the set $C_T$ is recursive/decidable.

Is this reasoning right? I am just wondering why J.Hartmanis and R.E. Stearns have not included this stronger statement in their paper back then...

This is a situation where coding is non-trivial. $\mathcal{C}_T$ is a class of decidable languages. To make sense of $\mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it.

So what does it mean for $\mathcal{C}_T$ to be recursively enumerable? It means that we can effectively produce a list $(M_i)$ of TMs such that $\{L(M_i) \mid i \in \mathbb{N}\} = \mathcal{C}_T$. Note that this does not give us that $\mathcal{C}_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $\mathcal{C}_T$.

The familiar "semi-decidable = computable enumerable" holds only for spaces with decidable equality -- and the space pf decidable languages does not have decidable equality.

Furthermore, the complement of $\mathcal{C}_T$ is not semi-decidable, either: While we can recognize that a given TM takes too much time, we cannot rule out that there is another TM deciding the same language, but respecting our time-bounds.


Crafting a dataset to train a NN that recognizes image styles In this paper the authors show how to use two NN that respectively recognize an art style and an image content to apply style filters to photographs.

However, I am confused about how would one train a NN to consistently identify the style of a given author, given that the dataset cannot be too big (an author may paint around ~100 famous canvas in his life?) and normally you need a really big dataset to train for such a thing.

I am just being pessimistic about NN capacity to learn from small datasets or is there a technique for expanding a dataset which could be used in this context?

Reference: A Neural Algorithm of Artistic Style, by Leon A. Gatys, Alexander S. Ecker, Matthias Bethge

You have to know how to read these papers, and set your expectations low.  The prior ability to do anything of this sort was so low that any advance, even a highly imperfect one, is exciting and unexpected.

It's like one of those animal trick shows, where the cute dog sits in front of the piano and plays Happy Birthday on it.  You're not expecting Beethoven's Moonlight Sonata or mastery-level playing.  It would be churlish to complain that the piece was overly simplistic, the playing lacked expression, and halfway through, the dog got distracted and started chasing his tail and never finished playing.  Come on, it's a piano-playing puppy!  How often do you see that?

Same deal here.  It's probably not really fully capturing "style" as a human would consider it.

Don't think of this as transforming an image to make it look like it was painted by some specific painter or artist.  It's not going to take my cellphone-snap of a tree in my backyard and make it look like an Ansel Adams composition.  Don't think of this as learning the style and idiosyncracies of a particular painter.  Don't even think of this as learning "style" as humans would consider it.

Rather, what they do is propose a technical transformation to an image, and then they look at its effect on some examples and -- woah -- the effect is pretty cool!  In some cases it comes surprisingly close to mimicking some aspects of human style.  It's not wonderful, but hey, it's more than one would otherwise expect.

At a technical level, they identify some particular attribute or property of an image that they can compute: if $I$ is an image, let $f(I)$ denote the value of this attribute.  Then, given an image $I_1$ and an image $I_2$, they show how to modify $I_2$ to get a new image $I'_2$ such that $f(I'_2)$ is similar to $f(I_1)$.  They look at some examples and empirically find that (a) $I'_2$ often seems to have "similar visual content" to $I_2$, and (b) $I'_2$ often seems to have captured some of the aspects of "artistic style" of $I_1$ (it seems to have a similar "style" as $I_1$), in some vague sense.

Based on this, they decide to call $f(I)$ the "style" of $I$.  That's probably playing a bit fast and loose with naming, as I suspect $f(I)$ falls far short of always capturing all of the elements of artistic style as a human would judge it.

At a technical level, $f(I)$ is computed by computing some kind of correlation matrix on the responses of internal layers of a particular neural network when applied to image $I$... or something like that.  The details don't matter so much, as the fact that empirically their transformation provides results that are interesting and unexpected.

And that's why they don't require a large training set per artist: they don't try to capture anything specific to a single artist.  They're not doing what you seemed to expect them to be doing.  Also, the neural network was obtained by pre-training it on a dataset of millions of images, so it probably captures some kind of information about typical patterns that are seen in images.


How is the complexity/size of a problem (for instance SAT) determined? We say an algorithm runs in polynomial time if it is of the form $O(n^k)$ where $n$ is the size of the input, right?

So how do we judge how many inputs there are in: $(x_1 \vee x_2 \vee \overline{x_3}) \wedge (\overline{x_1} \vee \overline{x_2} \vee x_4) \wedge (x_2\vee x_3\vee x_5)$

...actually, in looking for an actual definition of an algorithm running in polynomial time, wolframAlpha says:
"An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is $O(n^k)$ for some non-negative integer $k$, where $n$ is the complexity of the input. "

So, then my question is, for my example, what is the complexity of the input? Is the complexity based on how many variables, or how many clauses?

The complexity of SAT relates to the number of arguments to the Boolean function (i.e. the "distinct literals" in the expression), not the number of terms in a particular normal form.

The complexity of an algorithm which solves SAT is related to the size of the input that you give it. So if the input is the Unicode string (x1∨x2∨¬x3)∧(x1¬∨x2¬∨x4)∧(x2∨x3∨x5), then the size of that is the number of Unicode codepoints (or bytes or bits used to encode those codepoints).

The subject of SAT is the function, not the representation of the function. The complexity class (i.e. the complexity of any solver which is optimal for its computer) is the same whether functions are written as product-of-sums or a sum-of-products. This complexity varies with the number of arguments to the function.

The input to a SAT solver is the representation of the function. Your example is in the product-of-sums normal form, which is a common way to express SAT problems. This is not a coincidence — SAT is solved mindlessly if you instead give it a sum-of-products expression! The brute-force method of solving SAT is to enumerate the sum-of-products, where each term either contradicts itself (b ¬b) or represents a satisfied piece of the function's domain. This simple approach doesn't trivialize SAT because going from one normal form to the other causes a combinatorial explosion. The size of the domain of a function of $n$ Boolean arguments is $2^n$.

Thus, feeding a gigantic problem description into a simple algorithm may have the same computational (and space) complexity as feeding a simple but equivalent description into a sophisticated algorithm. For brevity, we tend to prefer to imagine the description to be simple and the algorithm to be complicated.


Solving a problem with instance of size $n$ in $O(n)$ Today I read the following text in CLRS:

We say that an algorithm solves a concrete problem in time $O(T(n))$ if, when it is provided a problem
instance $i$ of length $n = |i|$, the algorithm can produce the solution in $O(T(n))$ time

It is ambiguous for me, because if we consider a problem in which a number $n$ is given and we have to print $1$ for $n$ times, and our input is the number $n$ in binary format, our input has a size of $O(lg(n))$, and since we do an action $n$ times, the algorithm runs in $O(n)$, and since $O(n) = O(2^{lg(n)})$, the algorithm is exponential.
What am I doing wrong here?

You are not doing anything wrong. Typically, you would want to consider the running time with respect to some variable defined in the question. In this case, you could either consider it to be linear in $n$, or to be exponential in the number of bits in the input.
When talking about formal algorithms in the context of turing machines, the running time is defined with respect to the size of the input (which in this case would result in an exponential algorithm).
In other contexts, the running time is usually calculated with respect to one of the following things:

Number of elements in the input list, if the problem's input is a list
The values given in the input (for example, $n$ in this case)
The size of the input in bits


If an NP complete problem 'A' is polynomial time reducible to another problem 'B' does that imply 'B' is also NP complete? The following question was asked on a quiz:

  Let S be an NP-complete problem, and Q and R be two other problems (that we don't know much about). If we now know that Q is polynomial time reducible (i.e., can be reduced in polynomial time) to S, and S is polynomial-time reducible to R, which one of the following statements can be deduced from the above information?

It was asked to choose a correct option out of these four options:

  R is NP-complete
  R is NP-hard
  Q is NP-complete
  Q is NP-hard

All that you know is that R is NP-hard.

To show that R is NP-complete, you need to show that it is in NP.  But that is not automatically true.

As an example, let S be the question "Is there a path of cost at most l that visits every node of a graph G?" and R be the question, "What is the cheapest path that visits every node of a graph G?"  These are variants of the Traveling Salesman problem.  S is in NP while R is believed not to be.  The issue being that given a proposed solution, you just add it up for S.  But for R, there is no known polynomial way to verify that you actually have the best path.


Binary Tree Question Using the diagram of a binary tree and algorithm answer the following:

If the following commands store(1,laurence), store(1, ron), store(1,graham), store(1,abe) and store(1,martin) are executed what will be stored at location (3)?

ron
abe
graham
empty

The answer is ron but I am struggling to work out why. How does the algorithm correspond to the tree? Thanks.

We start in store(1,laurence) and since 1 is empty, we simply put laurence in 1.

We then go in store(1,ron) and see that 1 is not empty so we compare ron to the value of 1: laurence, and since laurence$\not>$ron, we then go to store(1.upper,ron). So since 1.upper$=$3, we are now in store(3,ron). Since 3 is empty, we simply put ron in 3.

Now, since we always check that the spot is empty before settings its data, the data of 3 will never change. So at the end, it's still ron.

The tree is just here to tell you that 1.upper$=$3.

But you can "run" the algorithm on this visual representation of the tree: Start at the leftmost node. If there's nothing written, write whatever you want to write, otherwise, depending on how what you want to write compares to what is written, either go up or down.

By the way, having "upper" pointing down and "lower" poiting up is really confusing...


Proof of correctness of reversal algorithm for array rotation We are given an array A of size n and we have to rotate it in left direction by d positions. So e.g. if A = {1, 2, 3, 4, 5, 6, 7} then for d = 2, the resultant rotated array is {3, 4, 5, 6, 7, 1, 2}.

One algorithm which does this goes as follows:

Reverse A[0..d-1] (0-indexing)
Reverse A[d..n-1]
Reverse A[0..n-1]

These three steps surprisingly rotate the array correctly. What is the math behind this algorithm? Why does it give a correct solution? It feels magical to me. I am not able to put up a formal proof of its correctness.

Here is a proof by picture, which follows the steps of the algorithm:
$$
0,\ldots,d-1,d,\ldots,n-1 \\
d-1,\ldots,0,d,\ldots,n-1 \\
d-1,\ldots,0,n-1,\ldots,d \\
d,\ldots,n-1,0,\ldots,d-1
$$
You can easily turn this into a formal proof by giving a formula for the permutation after each step, which you can easily prove correct.


Programming Language Hierarchy I know that Assembly is the lowest level of the stack besides machine code, but are the languages above it all considered "high level languages" or is there a hierarchy amongst these languages. For instance, are C++, Ruby, and Python all "high level languages"?

There are supposedly generations of languages. According to Wikipedia:

First generation: Machine language.

Second generation: Low-level programming languages such as assembly language.

Third generation: Structured high-level programming languages such as C, COBOL and FORTRAN.

Fourth generation: Domain-specific high-level programming languages such as SQL (for database access) and TeX (for text formatting)

The fifth generation was supposed to be developed by Japan's fifth generation project in the 1980s but didn't really go anywhere. Some people consider constraint-based languages to be fifth generation (Wikipedia).

There is also a supposed hierarchy of language power, expressed by Paul Graham as the "Blub Paradox" in his essay Beating the Averages. In this controversial approach, languages such as Basic and Cobol are low in the hierarchy, Python and Perl would be in the middle, and Lisp would be at the top.


Bucket sort has uniformly distributed data Implementation of bucket sort is mainly useful when input is uniformly distributed over a range. So the ques here is what is the significance of having input data uniformly distributed for applying bucket sort? What happens if this does not hold?

Bucket sort will be slower if the data distribution is highly non-uniform.  The primary advantage of bucket sort over other sorting algorithm is that it is faster when the data is uniformly distributed; so if the data is highly non-uniformly  distributed, the advantages of bucket sort may evaporate.


Anonymization of dataset preserving unique identities The $k$-anonymization paradigm (and its refinements) means to create datasets where every tuple is identical with $k-1$ others.

However I'm in a situation where people are in the dataset many times. And I want to follow their progress through the health care system, so I need to know who is who. If I give each person a unique ID, which is necessary in this situation, a linking attack from within the table is possible!

Does anyone know of any relevant theory or have attempted to deal with similar problems?

I'm inclined to think it is impossible to give any good guarantee of anonymity in this situation.

This will possibly be used for my MSc thesis topic.

The point of k-anonymity is that you can't uniquely identify your patients. So I will rephrase your question:

  Given two anonymized tuples $x$ and $y$, can we tell if they are anonymizations of the same person?

Let's suppose for purposes of contradiction that we could. Then this means there is a "meta-tuple" which uniquely identifies a patient. But this violates anonymity (unless $k=1$). So it is impossible.


What is different between Set and Type in Coq? AFAIU types can be a Set whose elements are programs or a proposition whose elements are Proofs. So based on this understanding:

Inductive prod (X Y: Type) : Set :=
| pair: X -> Y -> prod X Y.

Following code should compile but it does not due to the following error. If I change Set with Type or the other Type with Set it compiles fine. Can someone help me understand what the following error means? I am trying to teach myself Coq using Software Foundations book.

Error:

Error: Large non-propositional inductive types must be in Type.

Coq has 3 "big" types:

Prop is meant for propositions. It is impredicative, meaning that you can instantiate polymorphic functions with polymorphic types. It also has proof irrelevance, meaning that if $p_1, p_2 : P$ then $p_1 = p_2$. This allows terms that are only used for proof to be erased in any code generated by Coq.
Set is meant for computation. It's predicative, and doesn't have proof irrelevance, which lets you do nice things like not assuming $1 = 2$. The Set parts remain during code extraction.
Type is a supertype of both of these, allowing you to write code once that works with either

I'm pretty sure your error is because you're defining a Set whose parameters can be Type, which means they can be Prop, which isn't allowed. If you change to this:

Inductive prod (X Y: Set) : Set :=
| pair: X -> Y -> prod X Y.

your code should work.


Search problem when the effects of actions are not deterministic The standard search problem studied in AI contains:

An initial state $A$;
A final (goal) state $Z$;
A set of actions that can change the state; each action takes as input a certain state and returns another state.
A solution to such a problem is a sequence of actions starting at $A$ and ending at $Z$.

I am interested in the following variant:

Each action can return one of several states; it is not known which state will be returned.
A solution is a tree in which each path from the root ends at $Z$.

For example: Suppose we start at state $A$ and do the action "ABRA". This action can return state $D$ or state $E$. In state $D$ we can do the action "DAMA" which returns state $Z$; in state $E$ we can do the action "EAGL" which can return either state $Z$ or state $Y$. In state $Y$ we can do the action "YADA" which returns state $Z$.

The motivation here is automatic construction of algorithms. Every solution is an algorithm for reaching from $A$ to $Z$. For example, the above solution can be read as the following algorithm:

Begin (state=A)
   ABRA
   If D then
      DAMA
      End (state=Z)
   Else If E then
      EAGL
      if Z then
         End (state=Z)
      Else  (state=Y)
         YADA
         End (state=Z)
      End If
   End If
End

MY QUESTIONS:

What are good references that deal with this kind of search problem?
Are there any usable solvers for solving such problems (similar to e.g. planners or solvers for usual search problems)?

One helpful way to think of this is as a two-party game.  When it is Alice's turn, she chooses an action; then, Bob chooses among the possible states that the action could return, and the system transitions to that state.  We start at the start state $A$.   Alice wins if she eventually reaches the goal state $Z$.  Bob is trying to prevent Alice from ever reaching $Z$.

With this viewpoint in mind, there's a straightforward algorithm to determine whether Alice has a strategy to win this game.  Let $S$ denote the set of all possible states.  If $R \subseteq S$ is a set of states, define $f(R)$ to be the set of states $s$ such that there exists an action $a$ so that every state $t$ that could be returned by action $a$ (applied to $s$) satisfies $t \in R$.  Also let $R_0 = \{Z\}$.  Now compute the following sequence:

$$\begin{align*}
R_1 &= R_0 \cup f(R_0)\\
R_2 &= R_1 \cup f(R_1)\\
R_3 &= R_2 \cup f(R_2)\\
&\vdots
\end{align*}$$

Iterate until you reach a fixpoint, i.e., $R_{i+1}=R_i$.  Then $R_i$ is the set of states that can reach $Z$: for every $s \in R_i$, there exists a strategy that Alice can use to ensure she will reach the goal state $Z$.  So, we can simply check whether $A$ is in $R_i$ or not.

You can make the running time of this algorithm linear, by a simple trick.  Store the set $R_i$ explicitly in memory.  Also, you maintain a separate data structure for "the fringe": the set of states that can reach $R_i$ in a single step.  For each state $s$ in the fringe and each action $a$ available on $s$, you maintain a counter that counts how many of the possible results of applying $a$ to $s$ will take you to the current set $R_i$.  On each iteration, you can compute $R_{i+1}$ and update all of the counters.  Each counter only decreases; it never increases.  Also, a state $s$ is in $f(R_i)$ just when one of the actions available on $s$ has a counter that has decreased to zero, so computing $f(R_i)$ is just a matter of scanning the fringe and finding the counters that have hit zero; then you compute $R_{i+1}$, update the fringe, and update the affected counters.  The running time of this algorithm is linear in the size of "the graph", i.e., in the number of states plus the number of transitions (triples of state $s$, action $a$ available on $s$, and state $t$ that could be returned by this action).

However, this straightforward algorithm is not very memory-efficient: it requires explicitly storing a large set of states.  Also it requires enumerating the statespace, or a large part of the statespace.  Therefore, it might be sufficient for small systems, but for large systems it might not be attractive.

For larger systems, you might want to consult the model checking literature to see if there are better solutions.

For example, I suspect you might want to look at Alternating-time Temporal Logic (ATL), in the model checking literature.  It deals with search problems for two-party games.  I think I recall that there are model-checking algorithms for solving problems associated with these kinds of two-party games, but I'm not certain about that.

(Incidentally: another way to think about your problem is that the possible results from each action correspond to non-deterministic choices, and there is an adversary (Bob) who is resolving all non-determinism in the worst possible way.)


Prove that any tree contains a matching of size |InternalNodes|/2 How can i prove that any tree contains a matching of size |InternalNodes|/2?
Thanks in advance

You can prove the following stronger claim by induction:

  Given a rooted tree containing more than one vertex, there is a matching which covers all non-leaf nodes.

The proof is quite simple – we match the root to an arbitrary child, remove the edge, and recurse on the remaining rooted trees. Each remaining tree in which the root is a non-leaf in the original tree will contain more than one vertex, and so the induction hypothesis applies.

I'll let you come up with the details.


How do I solve a maze using velocity and acceleration? I need to solve a maze. I can move an object around in a 2D maze by giving it 1 acceleration in any 8 of its 8 directions.
The object starts at rest at 0 velocity.
By only adding an acceleration at each step, I need it to be able to solve the maze and finish at the end position with a final velocity of 0.
This maze is shaped with big open areas and not narrow corridors of tight corners.
It should also take the least amount of steps possible to get to its destination.

This as you can imagine, would look different than simply finding the shortest path.

At any point, the state of the system is a pair $(p,v)$ where $p$ is the current position and $v$ is the current velocity vector.  At any state, there are 8 possible actions (transitions out of that state, to another state).  Search over this state space using any algorithm for searching state spaces to find the lowest-cost path from the start state to the desired end state; for example, you could use BFS, A*, etc.  This should solve the problem in a clean, straightforward, and efficient way.


Analysis of time complexity of travelling salesman problem Recursive definition for travelling salesman problem can be written like this :-

T(i,S)=min((i,j)+T(j,S-{j})) for all j belonging to S, when S is not equal to NULL

T(i,S)=(i,S) when S is equal to NULL

Here, T(i,S) denotes the tour starting from i covering all vertices in Subset S and then travel back to i.

I built the recursive tree and calculated the subproblems at each level. For k elements, number of subproblems comes out to be :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+(n-1)(n-2)(n-3)......(n-k).

For k=4, number of subproblems at level 1,2 and 3 are 3,6 and 6 respectively.

I tried to solve it but couldn't find the actual solution but it can be seen clearly that the time complexity is factorial. Now, in the recursion tree there are repeated function calls at the last level which we use to improve our time complexity using dynamic programming. Now, half of the function calls at last level are repeated that would reduce the number of subproblems to :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+((n-1)(n-2)(n-3)......(n-k))/2.

But, I think the time complexity is still factorial. I read on various resources that time complexity of travelling salesman problem using dynamic programming is $O(n^2*2^n)$ which is exponential.

Is there something wrong in my analysis? Can anyone prove how the time complexity comes out to be $O(n^2*2^n)$ ?

When solving TSP using dynamic programming you get something akin to the following:

TSP(graph, start, target) {
  if start == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, start, target) {
    tour_length = TSP(remove(graph, start), neighbor, target)
                  + distance(graph, start, neighbor);
    if tour_length < min {
      min = tour_length;
    }
  }
  return min;
}

(neighbors only returns target as a viable neighbor if no other choice is available)

This algorithm recursively finds the shortest tour starting from each neighbor and returns the minimum of those. If you do all this with dynamic programming you can calculate the amount of work you're doing like so:
There are $n$ possible start vertices and $2^n$ possible subgraphs. So this function will be called on at most $n\cdot2^n$ distinct arguments (the target never changes). Each call performs at most $O(n)$ work (there are at most $n$ neighbors). Hence the total work you're doing is $O(n^2\,2^n)$.


Single Source Shortest Path: What does the weights on the vertex and edges tell you? In MIT's open courseware (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf), I do not see how computing a set of numbers on the edge and the vertex will produce the shortest path.

Can someone please explain what information I can get by looking at the above example? How can I tell what is the shortest path to where?

In this example, the numbers on the edges are "given" - they are weights of the edges of the graph in which you want to compute the shortest paths from the source vertex S to all other vertices.

The rest of the information on this graph is the result of the shortest path computation (though this slide doesn't give the algorithm used to compute it - the algorithm is given in subsequent slides).

The result consists of two parts:

The numeric value of the shortest distance from S to each other node. Every node is labeled with its shortest distance. E.g. it's 0 for S itself, -2 for C, 8 for D, etc.
The "shortest paths tree", which allows to reconstruct the actual shortest path to any vertex, not just the length of the path. More on it below.

The actual shortest paths are encoded in a peculiar way, relying on the fact that if you take all edges that participate in at least one shortest path from S to some other vertex, you'll get a tree. Here's why:

Take any vertex - e.g. B. The shortest path from S to B is S-C-A-B. The vertex A is B's "predecessor" ("parent") in this path. For a fixed vertex S, obviously each other vertex has a predecessor (parent). On this picture, "X's predecessor is Y" is denoted as $ X.\pi = Y $.

What's a structure where each vertex has a parent? It's a tree! So we obtain a tree of shortest paths. This tree is a subset of the graph's edges. On your picture, the edges included in this subset are highlighted with red color.

This tree can be used to reconstruct the shortest path from S to any vertex. E.g., for vertex D, its parent is B, B's parent is A, A's parent is C, C's parent is S, so we get S-C-A-B-D.

Note that this tree construction relies on a certain (rather obvious) property of shortest paths: for any vertex, the shortest path to it goes through the shortest path to one of its adjacent vertices.


Non-uniform random distribution: How do I get a random between 100 and 180 that is on average close to 120? (like in a Gaussian distribution) Presume I have the following case:

int value a
int value b, for which a < b
int value i, for which a <= i < b
I need an int value x, for which a <= x < b, randomly chosen, according to a non-uniform distribution: the distribution should follow a bell curve which is centered around i.

In Java, I have the following methods available on java.util.Random:

nextInt(int m): int between 0 and m
nextDouble(): double between 0.0 and 1.0
nextGaussian(): double between -Infinity and +Infinity, usually close to 0.0.

How do I build such a non-uniform distribution from these building blocks? How do I reliably and efficiently transform nextGaussian() into nextGaussian(a, b, i)? The part I am struggling with is to enforce that x is selected between a and b (without doing a trial-and-error).

Your problem is rather vague: "bell curve" and "centered around i" are not well defined.

One possible recipe is to generate a truncated gaussian: define s= min(b-i,i-a)/c where c is a free parameter (suggested values:  [1,3] range), generate a gaussian with mean i and standard deviation s  - and round it to the nearest integer. If the value falls outside the [a,b] range, try again.

Related.


Is Deciding Decidability Decidable? I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.

Major edit of my original:

A naive reading of your question seems to be, let $P$ be the problem

  $P=$ Given a language, $L$, is it decidable?

Then you ask

  Is $P$ decidable?

As D.W. and David have noted, the answer is, "yes it is", though we don't know which of the two trivial deciders is the right one. In order to frame your problem so that it's not quite so trivial, I'd suggest this. First, let's restrict things slightly by considering only those languages $L(M)$ which are the languages accepted by some TM $M$. The reason for doing this is that if a language is not accepted by any TM, then it's not r.e. (recognizable) and so can't be recursive (decidable). Then we can recast $P$ as

  $P'=$ Given a description, $\langle M\rangle$ of a TM, $M$ is $L(M)$ decidable?

Now $P'$ is a language of TM descriptions, rather than a language of languages as $P$ seemed to be (under a generous interpretation), and it's now perfectly reasonable to ask whether the language $P'$ is decidable. Under this reading, the language
$$
\{\langle M\rangle\mid M \text{ is a TM and $L(M)$ is decidable}\}
$$
consisting of TM descriptions is not decidable. This is an easy consequence of Rice's Theorem. So now we have two answers: my "no" and D.W.'s "yes", depending on the interpretation.


An algorithm for making 2 carts meet Say I have 2 carts on an infinite railroad, each cart is initially under a lamp.
There are only 2 lamps, and they are at a fixed location, hence they don't change their location. The distance between them is D, but its not known.
Each cart has a processing unit, both will execute a copy of the same program once the whole system is "initiated".

The task: to write a code in pseudo-code, which will make the 2 carts collide.

Restrictions:
The following commands can be used:

  move left/right *insert_number_here* steps //each movement takes 1 clock cycle, meaning that "move left C steps takes C clock cycles
  if underlamp *put_instruction_here* //if the cart is under a lamp
  goto *number_of_line_here*
  stop

Variables, loops and not (!) are usable.

the given solution is:

  for i=1 to infinity:

  go left i steps.
  if underlamp stop.
  go right i steps.

Now, I need a hint to help me make a simple improvement to the algorithm that is given in the trivial solution, so when the distance between the lamps is D, the total number of steps of both carts will be a first order polynomial function of D.

My lecturer gave the following solution, and told me to improve the given code using a different idea.
This is his solution:

  go right.
  go right.
  go left.
  if underlamp goto 6.
  goto 1.
  go right.
  goto 6.

My improvement of the given code, but I'm not sure that in this one, the total number of steps is a first order polynomial function of D.

  for i=1 to infinity:

  go right i steps.
  if underlamp goto 4.
  go left.

  4.for j=1 to infinity:

  go right j steps.

You asked for a hint.  OK, here goes:

Obviously, we don't know $D$ (otherwise the problem is too easy).  But suppose we do know an upper bound $U$ on $D$.  In other words, suppose we know an integer $U$ and are promised that $D \le U$.  Then it is possible to build a solution whose running time is a low-order polynomial of $U$.  In fact, it is possible to build a solution whose running time is $O(U^2)$.  Take a close look at your professor's algorithm (the one labelled "the given algorithm"), and think for a bit, and maybe you'll see how to accomplish this.

But what about the fact that we don't know the value of $U$?  Well, you might ponder the sequence $1,2,4,8,16,32,\dots$.  I'm being deliberately terse here since you asked for a hint, but if you ponder on this, I think you'll be able to find an algorithm that it meets all your criteria.


What can be defined as a Regular Set I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive be considered part of a regular set? Lets say I have that same set, but instead of being even, they are divisible by 5, would it still be a regular set?

I've been looking at this helpful guide I found online, but I'm still confused about what can be defined as a regular set.

A regular set is the same thing as a regular language. You haven't explained how to encode integers, but suppose you encode an integer in binary notation, MSB first; so each zero is represented as $0$, and all other numbers start with $1$. The set of even positive integers is the represented by the regular expression $1(0+1)^*0$ (why?), and so is regular. The set of non-negative integers divisible by $5$ is also regular, since there is a DFA that accepts it; the minimal DFA has $5$ states corresponding to the value of the current prefix modulo $5$, which is updated in the obvious way. I'll let you figure out the details.


Data versioning in a relational database I've been working on an industrial project where my job was to design a data model in-memory and in a relational database in such a way, that can capture the time-varying nature of the production planning of a factory. In other terms, there exist input data and whenever a planning occurs, I have to take a snapshot of the current state of the world and store it.

My solution was to add a header object/table for all relevant input data and output data and have them reference each other's header by its unique auto-incrementing id. Such headers are then considered final and immutable and I do a deep-copy only if something needs to change.

I believe this approach isn't new but I can't recall any (relational-) data modelling courses explicitly mentioning this. My PhD advisor (who is not into general CS) wants me to have a thesis point about this and I'm unable to convince him that either this isn't new or at most a trivial extension to some existing methodology. I've tried searching Google Scholar, but didn't find any articles, perhaps due to wrong keywords.

Can someone point me into the right direction?

I've seen a thesis on this subject, but that was long ago.

One thing to search for a combination of relational databases and versioning, which will produce things such as tuple versioning; another is temporal databases.

As far as I know, there really is no standard way to address your problem. How best to model it depends on what information you want to be in the snapshot and on how you want to use the information later.

For instance, if you never ever want to pose queries that combine information from different snapshots, you can save each snapshot to a different database.
That allows you to use the same constraints and queries on your snapshots that you use on the live data.

If you never need to pose queries that combine information from your live operational state with information from your snapshots, you probably want to save the snapshots to a different database than the live information. That way, you can at least continue to use constraints and queries on the live data that do not take the extra snapshot information into account.  On the snapshots, you will need to rewrite the constraints and queries. But it will be easier to pose queries that combine information from different snapshots.

To be honest, I don't understand what you mean by "add a header object/table for all relevant input data". If all of the snapshots are put into the same database, without creating separate tables for each snapshot, I expect to see one or two columns for every table whose tuples should be in the snapshot. The extra column(s) would contain a snapshot identifier: a timestamp or a foreign key into a new table with more information about snapshots. In case of two columns, they would indicate the first and last snapshot in which the given tuple is present. This can save space if you have many snapshots, but it can also make querying harder.


What's a good algorithm for deleting multiple elements in a heap? I have a binary min-heap, size n, and I want to delete a number of
elements, identified by some predicate.

Any algorithm needs at least n tests of the predicate (preferably,
exactly n), so the interesting performance metrics are the number of
moves of elements, and the number of additional tests of the
predicate.

One possible way is to first delete elements from the corresponding
array, using a single pass to delete elements and compact the array.
And then rebuild the heap from the array. Both steps are O(n). But as
far as I understand, the rebuild step can need n moves of elements
even if only one or two elements are deleted, if they are at unlucky
positions in the array.

I wonder if there's some good algorithm which

needs O(n) element moves in the worst case
needs few extra tests of the predicate, say total n + O(log n) tests
in the worst case
needs a lot fewer then n element moves in the special cases that
only a few elements are deleted, or only a few elements are kept.

I think you're optimizing for the wrong metrics.  The total running time will be $\Theta(n)$ no matter what you do.  Scanning the entire array to identify which elements to remove will take $\Theta(n)$ time, so your total running time can't be any better than $\Theta(n)$.  Conversely, there is a simple algorithm that achieves $\Theta(n)$ time.  MakeHeap can be done in $\Theta(n)$ time, so it gives you a simple $\Theta(n)$ running time algorithm: scan the entire array, delete whatever you want to delete, then run MakeHeap.

However, if you're trying to optimize the amount of work per deletion and for some reason the time taken to scan the array "doesn't count" (I don't understand why it wouldn't count, but let's just run with it):

In this case there is an alternative algorithm.  Deleting a single element from a heap can be done in $O(\lg n)$ time.  So, if you want to delete $k$ items, delete each one-by-one.  Total running time: $\Theta(n)$ to scan the array, $\Theta(k \lg n)$ to delete them.


Is there an anti-Bloom filter? A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing.  When there are many data items then a Bloom filter can result in a significant memory saving over a hash table.  The main feature of a Bloom filter, which it shares with a hash table, is that it always says "not new" if an item is not new, but there is a non-zero probability that an item will be flagged as "not new" even when it is new.

  Is there an "anti-Bloom filter", which has the opposite behaviour?

In other words: is there an efficient data structure which says "new" if an item is new, but which might also say "new" for some items which are not new?

Keeping all the previously seen items (for instance, in a sorted linked list) satisfies the first requirement but may use a lot of memory.  I am hoping it is also unnecessary, given the relaxed second requirement.

For those who prefer a more formal treatment, write $b(x) = 1$ if the Bloom filter thinks $x$ is new, $b(x) = 0$ otherwise, and write $n(x) = 1$ if $x$ really is new and $n(x) = 0$ otherwise.

Then $Pr[b(x) = 0 | n(x) = 0] = 1$; $Pr[b(x) = 0 | n(x) = 1] = \alpha$; $Pr[b(x) = 1 | n(x) = 0] = 0$; $Pr[b(x) = 1 | n(x) = 1] = 1 - \alpha$, for some $0 < \alpha < 1$.

I am asking: does an efficient data structure exist, implementing a function $b'$ with some $0 < \beta < 1$, such that $Pr[b'(x) = 0 | n(x) = 0] = \beta$; $Pr[b'(x) = 0 | n(x) = 1] = 0$; $Pr[b'(x) = 1 | n(x) = 0] = 1 - \beta$; $Pr[b'(x) = 1 | n(x) = 1] = 1$?

Edit: It seems this question has been asked before on StackExchange, as https://stackoverflow.com/questions/635728 and https://cstheory.stackexchange.com/questions/6596 with a range of answers from "can't be done" through "can be done, at some cost" to "it is trivial to do, by reversing the values of $b$".  It is not yet clear to me what the "right" answer is.  What is clear is that an LRU caching scheme of some sort (such as the one suggested by Ilmari Karonen) works rather well, is easy to implement, and resulted in a 50% reduction in the time taken to run my code.

Going with Patrick87's hash idea, here's a practical construction that almost meets your requirements — the probability of falsely mistaking a new value for an old one is not quite zero, but can be easily made negligibly small.

Choose the parameters $n$ and $k$; practical values might be, say, $n = 128$ and $k = 16$.  Let $H$ be a secure cryptographic hash function producing (at least) $n+k$ bits of output.

Let $a$ be an array of $2^k$ $n$-bit bitstrings.  This array stores the state of the filter, using a total of $n2^k$ bits.  (It does not particularly matter how this array is initialized; we can just fill it with zeros, or with random bits.)

To add a new value $x$ to the filter, calculate $i \,\|\, j = H(x)$, where $i$ denotes the first $k$ bits and $j$ denotes the following $n$ bits of $H(x)$.  Let $a_{i} = j$.
To test whether a value $x'$ has been added to the filter, calculate $i' \,\|\, j' = H(x')$, as above, and check whether $a_{i'} = j'$.  If yes, return true; otherwise return false.

Claim 1: The probability of a false positive (= new value falsely claimed to have been seen) is $1/2^{n+k}$.  This can be made arbitrarily small, at a modest cost in storage space, by increasing $n$; in particular, for $n \ge 128$, this probability is essentially negligible, being, in practice, much smaller than the probability of a false positive due to a hardware malfunction.

In particular, after $N$ distinct values have been checked and added to the filter, the probability of at least one false positive having occurred is $(N^2-N) / 2^{n+k+1}$.  For example, with $n=128$ and $k=16$, the number of distinct values needed to get a false positive with 50% probability is about $2^{(n+k)/2} = 2^{72}$.

Claim 2: The probability of a false negative (= previously added value falsely claimed to be new) is no greater than $1-(1-2^{-k})^N \approx 1-\exp(-N/2^k) < N/2^k$, where $N$ is the number of distinct values added to the filter (or, more specifically, the number of distinct values added after the specific value being tested was most recently added to the filter).

Ps. To put "negligibly small" into perspective, 128-bit encryption is generally considered unbreakable with currently known technology.  Getting a false positive from this scheme with $n+k=128$ is as likely as someone correctly guessing your secret 128-bit encryption key on their first attempt.  (With $n=128$ and $k=16$, it's actually about 65,000 times less likely than that.)

But if that still leaves you feeling irrationally nervous, you can always switch to $n=256$; it'll double your storage requirements, but I can safely bet you any sum you'd care to name that nobody will ever see a false positive with $n=256$ — assuming that the hash function isn't broken, anyway.


Pseudo-random sequence prediction Disclaimer: I am a biologist, so sorry for (perhaps) basic question phrased in such crude terms.
I am not sure if I should ask this question here or on DS/SC, but CS
is the largest of three, so here goes. (After I posted, it occurred to me that Cross-Validated might be the better place for it, but alas).

Imagine there is an agent, who makes binary decisions. And an environment, which, for each of the agent's decisions ("trials"), either rewards the agent or not. The criteria for rewarding the agent's decisions are not simple. In general criteria are random, but they have limitation, for example, environment never rewards more than 3 times for the same decision and never alternates rewarded decision more than 4 times in a row.
Sequence of criteria might look something like this then
0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 ...

but never
0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 ...

because reward criterion cannot repeat more than 3 times.
In these conditions it is quite easy to formulate the strategy ideal observer should undertake to maximize the reward. Something along the lines of

decide randomly
if you detect that criteria repeated 3 times -- decide opposite than last criterion
if you detect that criteria alternated 4 times, decide according to the last criterion

Now, the difficult part. Now the criterion on each trial depends not only on the history of previous criteria, but also on the history of agent's decisions, e.g. if agent alternates on more than 8 out of the last 10 trials, reward same decision as agent made last time (as if to discourage the agent from alternating) and if agent repeated same decision on more than 8 of the the last 10 trials, i.e. he is biased, make criterion opposite of the bias. The priority of history of criteria over history of decisions is specified in advance, so there is never ambiguity.
The sequences of decisions (d) and criteria (c) might now look like this
d: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 ...
c: 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 ...
                       ↑ here criteria counteract bias in decisions

I do not see any simple way of inventing maximizing strategy for the agent. But I am sure there must be one, and some kind of clever machine learning algorithm should be able to identify it.
My question is not so much about how to solve this problem (although I would be happy if you suggest a solution), but more how these types of problems are called? Where can I read about it? Is there an abstract solution or only simulation can help? In general, how can I, as a biologist, approach this type of problem?

You can approach this problem using Reinforcement Learning.

A classic book for this is Sutton and Barto:

The draft of the second edition is available for free:
https://webdocs.cs.ualberta.ca/~sutton/book/the-book.html

In order to make your problem Markovian, define each state as a vector of the last ten decisions. You actions will be 1 or 0.


Sum of series (n/1) + (n/2) + (n/3) + (n/4) +…….+ (n/n) I wonder if there is a formula to calculate the sum of n/1 + n/2 + n/3 + n/4 + ... + 1. (Integer division)
The number n can be as large as 10^12, so a formula or a solution having the time complexity of O(logn) will work.
This is how far I can get:

The sum can be described as n * (1 + 1/2 + 1/3 + 1/4 + ... + 1/n). The series inside the parenthese is the Harmonic Progression which has no formula to calculate. So I don't think this can lead to a solution.

Playing with some numbers, this is what I get:

11 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
10 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1
9 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 1
8 + 4 + 2 + 2 + 1 + 1 + 1 + 1
7 + 3 + 2 + 1 + 1 + 1 + 1
6 + 3 + 2 + 1 + 1 + 1
5 + 2 + 1 + 1 + 1
4 + 2 + 1 + 1
3 + 1 + 1
2 + 1
1

So by skipping the number 1s, we can reduce the time by a half. If using a loop to calculate the sum, we only need to loop until n/2. Since the rest contains only number 1s.
I've been trying to come up with a formula to calculate the series that is not 1 + 1 + ... + 1.
Please help if you know the acceptable answer (a formula or a O(logn) solution).

Based on the following observation, you can derive a $O(\sqrt{n})$ time algorithm ( by computing the sum on the right-hand side naively in a $O(\sqrt{n})$-sized loop): (For $n=10^{12}$ this yields $n=10^{6}$ which is enough for say competitive programming sites which usually allow ~10^8 operations)

For any positive integer $n$, Let $k=\lfloor\sqrt{n}\rfloor$:
$$
\sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor = 2\sum_{i=1}^k  \left\lfloor\frac{n}{i}\right\rfloor - k^2
$$

This post on Math StackExchange provides a clear visual proof of the equality above.
The following is a proof for the equality above that does not depend on a graph.
All variables below stand for positive integers. Let us fix $n$ and $k=\lfloor\sqrt{n}\rfloor$. For all $i, j\le n$, let
$\delta(i,j)=1$ if $i\cdot j\le n$. $\delta(i,j)=0$ otherwise. In particular,

$\delta(i,j) = 1$ if $i,j\le k$.
$\delta(i,j) = 0$ if $i,j\ge k+1$.

Proposition. $\left\lfloor\dfrac{n}{i}\right\rfloor = \displaystyle\sum_{j=1}^n \delta(i,j) $ for all $i$.
Proof. Both sides count the number of positive multiples of $i$ that are smaller than or equal to $n$. $\ \checkmark$
$$\begin{aligned}
\sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{i=k+1}^n \left\lfloor\frac{n}{i}\right\rfloor \\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{i=k+1}^n \sum_{j=1}^n \delta(i,j)\\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{i=k+1}^n \sum_{j=1}^k \delta(i,j)\\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{j=1}^k \sum_{i=k+1}^n \delta(i,j)\\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{j=1}^k\left(\sum_{i=1}^n \delta(i,j)-\sum_{i=1}^k \delta(i,j)\right)\\
&= 2\sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 - \sum_{j=1}^k\sum_{i=1}^k \delta(i,j))\\
&= 2\sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 - k^2 \quad \checkmark \\
\end{aligned}$$
The proof above is, basically, a direct translation of the visual proof.


Calculating product of totient functions Suppose that i need to compute product $~\phi(1) \dots \phi(n)~$ modulo prime $500009$ as fast as possible. Memory limitations are rather tough: $64$ mb so i can't just keep all the values of totient function. $n$ can be as large as $10^9$ and time given is $2$ s.

My main idea is to somehow estimate the prime factors and their exponents in factorization of this product. And then apply fast modular exponentiation. But i don't understand yet how to do such estimation.

Any ideas are highly appreciated. Thanks in advance.

P.S.
This is not a hometask or a problem from a current contest. I'm just surfing number theory problem bank and solving them for fun.

Let $p=500009$ and $m=12p+1$. One possibility is to use the fact that $\phi(m) \equiv 0 \pmod{p}$, and hence it's enough to pre-calculate all values up to $m$. Storing each answer in a 32-bit integer, this is a table of size 24MB.

If you don't like pre-calculating everything, you can use in some other way the fact that only numbers below $m$ need to be considered. Be creative.


Subset of numbers whose XOR has least Hamming weight I'm given $n$ numbers (let's say of some 100 bits or so). Is there a way to find a non-empty subset xor of these $n$ numbers which has the least Hamming weight (no. of set bits) in better than $O(2^n)$ complexity? I was thinking of some trie based implementation but don't think that will work at all. Would a dynamic programming approach work by any chance? If possible, a hint would be nice!

Your problem is known as calculating the minimal distance of a (binary) linear code, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, Miccancio and Sudan.


How to generate all possible test cases of length $n$ for comparison sorts Comparison sorts only care about the relative order of elements, not their exact values. So if the relative order of two arrays are the same, a comparison sort algorithm will act the same way on those two arrays.

For example, [0, 3, 1, 9, 1] is the same as [-3, 12, 7, 13, 7], since their relative orders are the same.

I want to generate all possible test cases of length $n$ for comparison sorts that all possible relative orders are considered, and no two different test cases have the same relative order.

The number of possible test cases of length $n$ is given by A000670.

Here are all possible test cases of length 0:

[]

Here are all possible test cases of length 1:

[0]

Here are all possible test cases of length 2:

[0, 0]
[0, 1]
[1, 0]

Here are all possible test cases of length 3:

[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[0, 2, 1]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

Is there a generic way rather than brutal force to generate these test cases?

Yes, there is an algorithm to generate all the possible test cases with length equal to $n$ and only them, significantly faster than the naive brute force algorithm would do.

Firstly, let's sort the numbers of each testcase you provided with length equal to 3 in ascending order and list only the different testcases that we get as result.

[0, 0, 0]
[0, 0, 1]
[0, 1, 1]
[0, 1, 2]

There are $4 = 2^2 = 2^{3 - 1}$ results. Note that the first value always has to be zero and while we move to the left within a specific testcase we can keep the previous value or increase it by one. So the number of different sorted testcases of length $n$ is $2^{n - 1}$. You can produce these sorted testcases by using a binary array whose value is initially zero and it's increased by one after each step.

After creating the sorted testcases you would like to have all the permutations of each one of them. Note that the number of permutations of a testcase is lower than $n!$ for all testcases except one (the $[1, 2, 3, \dots, n]$). Also note that the permutations of the different sorted testcases do not overlap. There is a built-in function in C++ which can create these permutations efficiently, named "next_permutation". The algorithm used for its implementation is nicely described on a Stack Exchange accepted answer which you can read here: std::next_permutation Implementation Explanation. I encourage you to read this description of the algorithm.

Bellow I provide you with a C++ implementation of the full algorithm that takes $n$ as input and produces all the different testcases that you want efficiently.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 105  // Assumed maximum value of n

int A[MAXN];  // The binary array used to create the sorted testcases
// Initially A is 0 (every number in it is zero)

vector<int> C;
// A vector that stores current sorted testcase and is used to obtain its permutations

int main()
{
    int n;
    cin >> n;  // Read n
    do
    {
        C.clear();  // Clear the vector C to create a new sorted testcase
        int cnt = 0;
        // cnt counts how many times we have increased the number to be inserted in the testcase
        for (int i = 0; i < n; i++)  // Create the sorted testcase of length n number by number
        {
            if (A[i]) cnt++;  // Binary array at current index shows if we should increase the number
            C.push_back(cnt);  // Put the current number in the end of the current sorted testcase
        }

        // Output all permutations of the current testcase
        do
        {
            for (int i = 0; i < n; i++) cout << C[i] << ' ';
            cout << '\n';
        } while (next_permutation(C.begin(), C.begin() + n));  // Continue while there are unprinted permutations

        // Increase binary array by one
        A[n - 1]++;  // We add one at the position n - 1 (least significant bit)
        int p = n - 1;
        while (p && A[p] == 2)  // We move the carry from right to left
        {
            A[p] = 0;
            A[--p]++;
        }
    } while (!A[0]);  // First number of sorted testcase must be 0, so when it becomes 1 we have finished
    return(0);
}


Is it possible to constract Moore or Mealy machine with a different size of input and output? Is it possible to constract Moore or Mealy machine to take input tape: 0011 and output: 00001111 (or vice versa). In other words, input and output have different size.

I want to construct FSMs to produce different transformation patters:

copy 2 times: 11 -> 11011, 101 -> 1010101
trim: 011100 -> 111, 000110 -> 11
fill zeros by 1 between 1: 01000100 -> 01111100, 01010 -> 01110

Can you please suggest is it possible to do it with FSM (Moore or Mealy machine) or should I switch to context free languages?

Can you please suggest is it possible to do it with FSM (Moore or Mealy machine)

The machine you are looking for is called a finite-state transducer. They can be defined in either Moore or Mealy variants. For the Mealy variant (which I believe is more common), you have a finite state machine where the edges are labeled with output, and the initial states are also written as initial edges that can have associated output. (That is so that output can be produced on the empty input, if desired).

There are two types of finite-state transducers: one-way transducers and two-way transducers. The difference is that:

One-way transducers just read the input from left to right, like a normal state machine.
Two-way transducers have, for each edge, a label which says whether they move left, right, or stay still. The input tape also has start and end symbols: for example, the input 001 would be written $\triangleleft 00 1 \triangleright$. The machine has a special "halting" state. It moves back and forth on the input tape, reading symbols and producing output, until it is finished.

Two-way transducers are more expressive than one-way transducers.
For some of the tasks you listed, one-way transducers are enough, but all of them can be done with two-way transducers.

  copy 2 times: 11 -> 11011, 101 -> 1010101

This can be done with a two-way transducer. It reads the input, producing it as output, then goes back to the start of the tape, produces a zero, and reads the input again, producing it as output again.

  trim: 011100 -> 111, 000110 -> 11

A one-way transducer can do this. It only needs one state; then depending on the input symbol, it either produces output or produces no output.

  fill zeros by 1 between 1: 01000100 -> 01111100, 01010 -> 01110

A one-way transducer can do this. You should be in a different state depending on whether you want to fill the zeros, or leave them be, and then switch between these states whenever you encounter a 1.

  or should I switch to context free languages?

I hope not! Context free languages are much more complex and difficult to work with, and not necessary for the kinds of tasks you list.


Operating system processes I'm a bit confused about this question:

  "Multiple jobs can run in parallel and finish faster than if they had run sequentially. Suppose that two jobs, each needing 10 minutes of CPU time, start simultaneously. How long will the last one take to complete if they run sequentially? How long if they run in parallel? Assume 50% I/O wait."

Answer from textbook (Modern Operating Systems 4th edition by Tanenbaum)

  "If each job has 50% I/O wait, then it will take 20 minutes to complete in the absence of competition. If run sequentially, the second one will finish 40 minutes after the first one starts. With two jobs, the approximate CPU utilization is 1 − 0.52. Thus each one gets 0.375 CPU minute per minute of real time. To accumulate 10 minutes of CPU time, a job must run for 10/0.375 minutes, or about 26.67 minutes. Thus running sequentially the jobs finish after 40 minutes, but running in parallel they finish after 26.67 minutes."

I don't understand why it will take 20 minutes for each job to complete if the IO wait time is 50%. Doesn't that just mean 5 minutes of CPU time is spent waiting for I/O?

50% I/O wait time means that a process is not in execution(i.e. CPU is sitting idle) for 50% of the total time a process requires from CPU to complete itself(its execution). Thus CPU Utilization turns out to be
//whereas 50% I/O time means it needs 50% of total execution time(10 minutes) to complete its I/O.

50%=50/100 = .5

thus the time needed to complete a process which requires 10 minute of CPU will be = CPU time required by process/CPU utilization=

10/CPU utilization=  10/0.5 =  20 minutes.

when two processes run sequentially(one after the other) then the total time required will be =  10/0.5 + 10/0.5 =  20+20=40 minutes (ANSWER)

in case of parallel execution we again find the CPU utilization..
since two processes are in parallel thus the formulae becomes-->

{1-(I/O time)^no. of processes in parallel execution}
=1-(0.5)^2=1-.25=0.75
now the CPU utilization for 1 process will be 0.75/2=0.375
Therefore the time required will be =
CPU time required by process/CPU utilization=
10/0.375=26.67 minutes.

Since the two processes are running in parallel thus the time required by 1 process will be the total time required by 2 process=26.67 minutes(ANSWER)


Trigonometry in computer science What's the use of studying trigonometry in computer science? I mean, is it essential? Does it have a specific application in computer science? Because I can't seem to muster enough motivation for learning it.

Rotations: that arise in Computer Graphics and Robotics , through rotation matrices, Quaternions, etc.
 Cordics  for computing these functions on a Microprocessor / FPGA
 Transforms in Image Compression and elsewhere  , e.g. FFT computation in $O(n \log n)$ time
Anything to do with the interface between CS and Signal Processing
Pretty much anywhere in navigation and tracking, e.g. anything involving a GPS, IMU,etc.
Somewhat indirectly in  Computational Geometry (CG), in its application like in coverage & localization in wireless sensor networks.

.. to name a few! So if you want to really avoid trig functions, you should  learn CG :-)


Understanding the proof of the halting problem I came across the following example that proves that the blank tape halting problem is not decidable.

I understand the proof technique, but I just don't see how the blank tape problem is shown to be undecidable in the proof.

It says $M_{w}$ starts with a blank tape but then writes $w$ onto the tape, so there is no difference to the general halting problem.

How does this imply that the blank tape halting problem is not decidable? I can't find the logical conclusion. Couldn't we just replace the blank tape halting problem with another DECIDABLE problem and argue the same way?

The argument shows that if you can solve the blank tape halting problem then you can solve the halting problem. Since you can't solve the halting problem, it follows that you can't solve the blank tape halting problem. (Here "solve" means "decide with a program that always halts".)

It's true that the same argument shows that many other problems are undecidable. But if you try to prove that a decidable problem is undecidable this way, then something will go wrong. Try it out!


Number of optimal solutions for Longest Common Subsequence (Substring) problem The Longest Common Subsequence (or Substring) problem (LCS) asks, given two strings $s_1$ and $s_2$, to find one string which is substring both of $s_1$ and $s_2$ and it is of maximum length.

Each instance of the problem (i.e. each choice of $s_1$ and $s_2$) can have multiple optimal solutions.
The size input of the problem is the sum of the length of $s_1$ and $s_2$.

Is the number of optimal solutions polynomial with respect to the size of the instance?

Consider the following two strings:
$$
s_1 = (abc)^n, s_2 = (bac)^n.
$$
You can show that the longest common substrings of $s_1,s_2$ have length $2n$. There are at least $2^n$ of these: $\sigma_1 c \sigma_2 c \ldots \sigma_n c$, where $\sigma_i \in \{a,b\}$.


Is changing or appending data an idempotent operation? As far as I know idempotent operation is a operation that can be applied many times with the same effect. Also I learnt recently that updating a tuple in a database is also idempotent. I thought that an idempotent operation was like a read-only stateless call (thanks to HTTP world with its famous GET request example). So, is changing data in a file (or database) idempotent? Is appending (extending) data in file/database idempotent? Why?

An operation $O$ is idempotent if $O(O(x)) = O(x)$. For example, if you update record $R$ to value $T$ and then again update record $R$ to value $T$, then it's the same as if you updated only once. But if you append $T$ to record $R$ twice, it's not the same as appending only once.


Solving the 10 players duel game Players #1 to #10 with hit probabilities $0.1,0.2,...,0.9,1$ (which are common knowledge) take part in a shooting game.

Rules of the game: Players from #1 to #10 take turns to fire at each other. After round one, survivors repeat the circle (still in the order of #1 to #10). The game lasts many rounds until only one player survives. Players are rational and each calculates to maximize his survival probability.

Question: What is each player's optimal choice of target in his turn, when all 10 players are alive? And what are their respective survival probabilities? (Technically, I'm looking for a pure strategy subgame perfect Nash equilibrium, where the players follow deterministic strategies. Barring the very unlikely circumstance of ties, in which firing at one or the other player yields the same survival probability for the shooter, such an equilibrium is unique.)

My problem is I don't know how to write a tractable program to solve it. Let's consider 4 players with probabilities $(p_1,p_2,p_3,p_4)$. In this case, my reasoning is that the problem is solved by the following equations:

$s_{i1}^4 = p_1*$(i's survival probability after 1 hits his target) $＋ (1-p_1) * s_{i2}^4$

$s_{i2}^4 = p_2*$(i's survival probability after 2 hits his target) $＋ (1-p_2) * s_{i3}^4$

$s_{i3}^4 = p_3*$(i's survival probability after 3 hits his target) $＋ (1-p_3) * s_{i4}^4$

$s_{i4}^4 = p_4*$(i's survival probability after 4 hits his target) $＋ (1-p_4) * s_{i1}^4$

for $i=1,2,3,4$, where $s_{ij}^4$ denotes i's survival probability when it's j's turn to fire, with 4 player alive. Notice that after a play hits his target, there's only 3 players left. So if we already know the 3 players case, the above equations can be solved. But I have no idea how to define a suitable structure and sub-programs to implement these thought... or maybe this is not the best way to look at the problem?

Robert Israel's answer on Math Overflow provides the key insight:

If $S$ is the set of players remaining alive and it is player $j$'s turn, player $j$ should shoot at the player $k$ such that, if $k$ dies, the remaining set gives $j$ the best survival chances.

This enables us to build a dynamic programming algorithm, as Robert Israel states.  I'll explain in a bit more detail how that works.

Represent a configuration of the game by $(S,j)$, where $S$ is the set of players remaining alive and $j$ is the player whose turn it is to shoot next.
Define $f_i(S,j)$ to be $i$'s probability of survival, under the equilibrium strategy for all (under optimal play), in configuration $(S,j)$.  Then the insight above means that in configuration $(S,j)$, player $j$ should shoot at the player $k$ such that $f_j(S\setminus\{k\},j+1)$ is as large as possible.

(As a conventional notation, when I write $(S,j+1)$, you should interpret $j+1$ as the next person to shoot after $j$, given that players $S$ are alive.)

Based on this, we can write recursive equations for $f$:

$$f_i(S,j) = p_j \cdot f_i(S \setminus \{g(S,j)\}, j+1) + (1-p_j) \cdot f_i(S,j+1)$$

where

$$g(S,j) = \arg \max_k p_j(S \setminus \{k\}, j+1).$$

We'll start by calculating the values of $f_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=1$.  Then, we'll calculate the values of $f_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=2$.  Then, we'll calculate the values of $f_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=3$.

At the $k$th stage, to calculate the $f$-values, we solve a system of linear equations in $k^2 \times {n \choose k}$ unknowns.  (The unknowns are the terms $f_i(S,j)$ where $|S|=k$ and $i,j \in S$.  Note that at this point $f_i(S \setminus \{\text{anything}\},j$ is known, since the first argument to $f$ will be a set of size $k-1$, which we've already calculated in the previous stage.)  In your problem, $n=10$, so the $k$th stage involves solving a system of linear equations in $k^2 \times {10 \choose k}$ unknowns.  This has a maximum at $k=6$, where we have 7560 unknowns.  The system of linear equations can be solved using Gaussian elimination, which takes cubic time.  In particular, Gaussian elimination on a $7560 \times 7560$ matrix is entirely feasible on a computer (probably it will take at most seconds).

Therefore, this should provide an efficient algorithm to compute the survival probabilities and strategy you are looking for.


Sub-Array with a unique element You have an Array of length n. If you pick a sub-array from the array, it must contain at least one unique element. The sub-array could be of any length but must contain consecutive/successive elements.

The question is what is the minimum number of characters you need to ensure that your array has the property mentioned and how should those elements be placed in the array? the answer needs to be in terms of n.

For Instance,

Let n be 10. Then you can place n different characters in it.

a, b, c, d, e, f, g, h, i, j

such that any sub-array would contain all unique elements. In this case the answer is n. But, of course this is not optimal as you need only one unique element in the sub-array.

In the same example of to pick 2 elements a and b and place them as

a, b, a, b, a, b, a, b, a, b

and you pick a sub-array of the first 4 elements a, b, a, b then you do not have any unique element. In this case the answer is 2 but is Incorrect.

So, what is the minimum number of unique element (and their placement in the array) you need to ensure your array has the property mentioned.

$\lceil \lg n \rceil$.

For example, for $n=10$, try ABACABADAB.  See if you can work out the pattern.

(I'll leave it at that, as this is a nice exercise problem and I'll let you have the joy of solving it on your own.)


Find the computational complexity of a concatenated system I have a network which includes $L$ blocks ($B_1,\cdots,B_L$) connected one after the other. I have an algorithm having computational complexity $\mathcal{O}(N)$ which runs in each block individually.

I first run the algorithm  on $B_1$ and get the output. Based on that output, I select the second data set in $B_2$. Then run the same algorithm on $B_2$ and get the output, and so on till $B_L$. The important thing is that the present data set depends on the previous block output.

Now I want to know the overall system complexity. I guess it is  $\mathcal{O}(LN)$. Is that right?

To summarize what you're saying:

You have an algorithm that runs in $O(n)$.
You're running it on $L$ different blocks, sequentially (no parallelism).
Every block has size $N$.

In this case, the total running time is indeed $O(LN)$.


(Nontrivial) Algorithms for finding the third largest element of a set According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for finding the third largest in a set of $n$ distinct elements?

Given that the tight lower bound is still unknown, I want to know the algorithms currently published in papers (meaning that they are not trivial, for example, by finding and removing the largest and the second largest elements and finding the third largest one in $(n-1) + (n-2) + (n-3) = 3n - 6$ time) for finding the third largest element.

Searching for "algorithm finding the third largest element" in Google does not bring me useful references.

For $n>5$, this paper proves that the number of comparisons
deterministic algorithms need is $n  +  \big(2 \cdot \lfloor \log_{2}(n)\rfloor \big) - \big(\text{an element of } \{1,2,3\}\big)$,
where that element depends on $n$'s position relative to the nearby powers of $2$.

Furthermore, for $n>7$, that paper gives a
deterministic algorithm which achieves those values.

By pages 330 and 331, the average number of comparisons needed is  $n + \Theta(\ln\ln n)$.

Theorem 5 is that the average number of comparisons used by that
paper's algorithm is at most $n + 5 \cdot ( 11 + \ln\ln n)$.
I have currently not located anything else regarding non-worst-case
algorithms for your problem, although I've kept finding more as I go along.


Does iterated PSPACE trace equal ELEMENTARY? I have the following feeling (I wouldn't even call it a conjecture yet) which I'd like to ask whether it's true in some form.

Take the class of all programs running in polynomial space.

Surprisingly or not, they can still output an exponentially large output: at each step of their running they may output something, and since they may perform 2^poly(n) steps, they may output such a large output as well.

Now suppose we take this output and feed it again to a PSPACE machine, and so on. It can also be seen as inputing to one PSPACE Turing machine the trace (if we don't like the idea of outputting outside of the tape) of the running of another PSPACE Turing machine, which again might be exponential in size wrt the original input's size.

By that, do we cover the whole ELEMENTARY complexity class? If not, then any known class? It seems to me obviously beyond PSPACE and EXPSPACE or even n-EXPSPACE if we allow n+1 such iterations.

As per D.W.'s request, here's a more precise formulation of the question.
Consider the class consisting of all possible pairs of PSPACE Turing machines. We consider running the pair of machines as follows. One machine takes an input and runs, and the second machine takes as input the trace of the running of the first machine. Which complexity class would this capture? It seems to me like EXPSPACE. Similarly if we took a triple of machines, two as above, and the third taking the trace of the second, it'd look to me like 2-EXPSPACE. Is that the situation indeed? What would be the computational power (in terms of complexity classes) of such iterated two (or more) different machines, one taking as input the trace of the other?

I guess that if this is correct and two iterated PSPACE machines capture EXPSPACE or beyond, then it'll prove that P!=PSPACE. So either it's all wrong and one can show me why it's wrong, or maybe even if it's right it doesn't actually imply P!=PSPACE.

Yup. If you have two algorithms $A,A'$ both in PSPACE, and you run $A'$ on the output from $A$, the resulting algorithm is in EXPSPACE.  Think about it: how much space is used by them together?  Well, it's the amount of space for $A$, plus the amount of space for $A'$.  If the input is length $n$, then the output of $A$ is at most $2^{p(n)}$, so the amount of space used by $A'$ is $q(2^{p(n)}$, where $p,q$ are polynomials.  Thus the computation is in EXPSPACE.

Also, any computation in EXPSPACE can be expressed in this way.  Suppose you have any language that can be computed in EXPSPACE, i.e., in $2^{p(n)}$ space.  Then you can take $A$ to copy its input to the output, then output a string of $2^{p(n)}$ 1's; then $A'$ can do the computation itself, and since the input to $A'$ has length $2^{p(n)}$, $A'$ will use space polynomial (in fact linear) in its input length.

You are also correct about the iteration of three of these; the result is in 2-EXPSPACE.


If A is mapping-reducible to B and is not mapping-reducible to co-B, is A Turing-reducible to co-B? If $A \leq_m B$ and $A$ is not mapping reducible to $co\text{-}B$, then $A \leq_T co\text{-}B$.

Is this true?

My intuition is false even if we can find some special case to make it true such as $A=B=co\text{-}A_{TM}$. However, I still can't find a counterexample.

Could anyone give me a little hint?

Hint: If $A \leq_m B$ then there is a computable function $f$ such that $x \in A$ iff $f(x) \in B$ iff it is not the case that $f(x) \in \text{co-}B$. Can you use this to Turing-reduce $A$ to $\text{co-}B$?


Alternative to Hamming distance for permutations I have two strings, where one is a permutation of the other. I was wondering if there is an alternative to Hamming distance where instead of finding the minimum number of substitutions required, it would find the minimum number of translocations required to go from string a to string b.

My strings are always of the same size and I know there are no errors/substitutions.

Example:

1 2 3 4 5
3 2 5 4 1

This would give me two:

3 2 5 4 1 (start)
-> 3 2 1 4 5
-> -> 1 2 3 4 5

If this is already implemented in R that would be even better.

Finding the minimal distance is called the "Sorting By Translocation" problem. Part of an abstract from a paper:

"Given two signed multi-chromosomal genomes Pi and Gamma with the same gene set, the problem of sorting by translocations (SBT) is to find a shortest sequence of translocations transforming Pi to Gamma, where the length of the sequence is called the translocation distance between Pi and Gamma. In 1996, Hannenhalli gave the formula of the translocation distance for the first time, based on which an $O(n^3)$ algorithm for SBT was given. In 2005, Anne Bergeron et al. revisited this problem and gave an elementary proof for the formula of the translocation distance which leads to a new $O(n^3)$ algorithm for SBT."

What's called "translocation" here is called a transposition, i.e., a permutation of exactly two elements in a list, in traditional combinatorial language.


Longest increasing subsequence on pairs Given a sequence of pairs $(a_1, b_1), (a_2, b_2), ..., (a_n, b_n)$ such that $a_1 \le a_2 \le ... \le a_n$ (i.e, sorted in ascending order by $a$'s), we solve the longest increasing subsequence problem for $b$'s. Now suppose the length of the longest increasing subsequence is $X$.

If we now sort the initial sequence by the second component and solve the LIS problem for $a$'s, is the length of this sequence also equal to $X$?

Intuitively I think this is true, but I don't know if it really is.

When you solve the longest increasing subsequence problem in its original formulation, you are finding the longest sequence $i_1,\ldots,i_\ell$ such that
$$
a_{i_1} < \cdots < a_{i_\ell} \\
b_{i_1} < \cdots < b_{i_\ell}
$$
This holds even if you shuffle the indices. Since the object you are maximizing is symmetric in the $a$s and $b$s, you will get the same length in both cases.


Inverse Homomorphisms and Kleene star The exercise is to prove or give a counterexample to the following proposition with $L \subseteq \Gamma^*$ regular and $h: \Gamma \to \Sigma^*$ a homomorphism.

Is there any regular language $L'$ such that $h^{-1}(L^*) = L'^*$
?

I know that it isn't that easy to see, since $h^{-1}(L^*) \not= h^{-1}(L)^*$ in general with $L = \{a\}$ and $h : \{a,b\} \to \{a\}^*$ with $h(a) = a, h(b) = aa$. It is $h^{-1}(L^*) = \{a,b\}^* \not= \{a\}^* = h^{-1}(L)^*$.

I still fail to deliver a proper argument to prove it.

Since you solved the first question, let me answer the second one. If you don't mind, I will use $h$ instead of $h'$ for simplicity. Let $L$ be a regular language and let $K = h^{-1}(L^*)$. Since regular languages are closed under inverses of homorphisms, $K$ is regular. Moreover, if $u, v \in h^{-1}(L^*)$, then $h(u), h(v) \in L^*$ and hence $h(uv) = h(u)h(v) \in L^*$. It follows that $uv \in h^{-1}(L^*)$ and thus $K = K^*$. Consequently, $h^{-1}(L^*) = K^*$, which answers your question.


Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ time Suppose you are given an input set $S$ of $n$ numbers, and a black box that if given any sequence of real numbers and an integer $k$ instantly and correctly answers whether there is a subset of input sequence whose sum is exactly $k$. I want to show how to use the black box $O(n)$ times to find a subset of S that adds up to $k$.

This is what I've done: the first time we enter our set $S$. If it returns yes we can continue, otherwise it isn't possible to form the sequence which sums up to $k$. The next step is to test our set without the first element. If the black box returns yes we can delete it from our set otherwise we know that it is needed. We do this for each element and our $S$ shrinks to a set which sums up to $k$. Can I use induction to prove this?

Let $S = \{a_1,\ldots,a_n\}$, and denote $S^t$ the set after deciding the fate of $a_t$. If you want to use induction, here is your induction hypothesis:

If there is a subset of $S$ that sums to $k$, then there is a subset of $S^t$ that sums to $k$.
Every subset of $S$ that sums to $k$ includes $S^t \cap \{a_1,\ldots,a_t\}$.


Has it been shown or can we show that if $SAT \in P$ then SAT can't be in any complexity class C so that $C \subsetneq P$? I'm already guessing that the answer is no because we cannot know whether there is a class "in between" already known classes? Or can we?
I am very new to complexity theory.
Thanks for any answer in advance!
EDIT: Now that I think about it again, what I am asking is if SAT was in P, could we show that SAT could not be in any class less complex than P? Or could not be in any class that requires as much time complexity as P?

SAT is NP-hard with respect to NC$^0$ reductions, and in particular, it is P-hard with respect to NC$^0$ reductions.
Now let $C$ be a complexity class which is closed under NC$^0$ reductions. If SAT is in $C$ then every problem in P can be reduced to $C$ using NC$^0$ reductions, and so belongs to $C$, implying that $C$ contains P.


Turing Machine which will double every 'b' in all inputted string I am trying to construct a Turing machine which will double every 'b' in all inputted strings over{c,b}.
How can I double 'b' in inputted string? because I cannot replace b with bb because one cell  of tape can contain only one character.

When you encounter $b$ change state to shifting tape right: move to next cell read content and put blank character.
Keep replacing characters until you encounter blank character (end of your tape content).
Put your last character at the end and move head left until you find blank character. Pur $b$ there.
Keep moving right until you find $b$ and repeat.

In your example:
$\color{green}cbcbcb\_$
Move right
$c\color{green}bcbcb\_$
Change state to copy and put blank:
$cb\color{green}\_bcb\_$ switch state to put $c$ and memorize next element
$cb\_\color{green}ccb\_$ switch state to put $b$ and memorize next element
$cb\_c\color{green}bb\_$ switch state to put $c$ and memorize next element
$cb\_cb\color{green}c\_$ switch state to put $b$ and memorize next element
$cb\_cbc\color{green}b\_$ blank encountered, move back to blank
$cb\_cb\color{green}cb\_$
$cb\_c\color{green}bcb\_$
$cb\_\color{green}cbcb\_$
$cb\color{green}\_cbcb\_$ blank encountered put $b$
$cbb\color{green}cbcb\_$ now repeat move right and switch to copy mode when another $b$ is found. When you reach end of the tape then all $b$'s are doubled.


Is the complement of a semidecidable (r.e.) language always a semidecidable (r.e.) language? Is the complement of every semi-decidable language a semi-decidable language?

No. A language $L$ and its complement $\bar L$ are semi-decidable if and only if $L$ is decidable (see here).

For example, the language containing all programs that terminate is semi-decidable, as you can run any program to see if it halts.
Its complement on the other hand is not semi decidable, as you cannot have a routine that determines, if a program will run forever or not.


Can we minimise regular expressions using known DFA minimisation algorithms? Of course, converting NFA to DFA is not a problem. But what about the other direction?

My motivation is the notion of minimization regular expressions using the DFA minimization algorithm.

You should have asked first what you wanted : your second line.
Why assume that you have to reverse the determinization procedure to
get back to a regular expression. You confused your readers. You might add it as a possible way you imagined to go about it, after you stated what you want, not before.

To find out how to get a RE from a FA, just search the web for :
"convert finite automata to regular expressions". It is an interesting topic.

If you want a "minimal regular expression", just search for that.
But I am not sure what minimal would mean (number of operators used
?).

If you want to find a "minimal NFA" search for that, but I gather it is a
rather difficult problem, still under research.

If you want a "minimal DFA", search for that. It is a well explored
problem.


Help comparing relative error for different parenthesizations of addition I am given two functions:
$ fl(fl(x+y)+z) $ and $ fl(x+fl(y+z)) $ and asked to derive their relative error. Then, given a set of conditions:

a) $ x < y < x $

b) $ x > 0, y < 0, z > 0 $

c) $ x < 0, y > 0, z < 0 $

determine which parenthesization has less relative error.

After some algebra I determined the following relative errors where

$ \epsilon_1 = RE(fl(x+y)),\ \epsilon_2 = RE(fl(fl(x+y)+z) $

$ \epsilon_3 = RE(fl(y+z)),\ \epsilon_4 = RE(fl(x+fl(y+z)) $

$$
\left| \epsilon_2 + \frac{(x+y)}{(x + y + z)}\epsilon_1 \right| \ \text{and}\
\ \left| \epsilon_4 + \frac{(y+z)}{(x + y + z)}\epsilon_3 \right|
$$

I determined that for the case $ x < y < z,\ fl(fl(x + y) + z $ has less relative error. With the largest variable, $ z $ in the denominator alone, as $ z \rightarrow \infty $ the coefficient of $ \epsilon_1 $ would approach $ 0 $.

But for $ x > 0, y < 0, z > 0 $ I'm struggling to generalize anything. I don't see how a conclusion can be drawn without an ordering between $z$ and $x$. And what about when $ y = x + z $? Although this case is independent of the relative parenthesizations. And similarly for the case $ x < 0, y > 0, z < 0 $.

With nothing but an upper bound for the relative error: Consider that the final sums are almost the same, so bounds for relative error will be almost the same. What’s significantly different is the absolute error of the first addition, and that will be smallest if the first sum has the smallest possible absolute value.

In the first case 0 < x+y < y+z, so the first function has the smaller error.

In the second case it depends whether x+y or y+z is closer to zero, which we don’t know. And exactly the same in the third case.


Algorithm for getting the outer boundary of a large graph I am trying to create an isochrone based on the OpenStreetMap data set. Everything works fine, I extracted data, processed it into a DAG, ran a Dijkstra algorithm over it. The result is a subset of the complete graph. This is an impression of the covered parts of the subset displayed over Google Maps:

However, when the area gets larger, the number of reached vertices gets very large and displaying like this gets slow. What I would like to do is convert the set of edges and vertices into a polygon. Basically, this should be posible by removing all of the inner edges, leaving just the edges around the boundary of the area and the edges pointing out from it. I know coordinates for all vertices and approximating each edge as a line would be fine. Larger inner areas should become holes inside the polygon.

My first attempt was to use an geospatial library (in my case the SqlServer spatial extensions), create a multiline from all of the edges and doing an ST_Buffer on it. Turns out to be very slow and memory consuming for large numbers of edges (> 1000)

I was thinking along the lines of finding small polygons in the set (turning left at every turn?) and removing every edge that is part of 2 of these polygons.

Extra image to use in comment below:

I think you can do this with marching squares, which is both fast and easy to implement.

To use marching squares you need to construct a scalar grid over your domain. Impose a regular grid over your region of interest. For each point in the grid, compute the distance (or time, etc.) between the grid point and your point of interest using a shortest path algorithm. Store this value at that point to serve as the scalar values of your grid. Then apply the marching squares algorithm to generate an isocontour for some isovalue $d$; all points on this contour will be distance $d$ away from your point of interest. More on the details of this algorithm on Wikipedia.

Additionally you can speed up the shortest path computation since your graph is a DAG. First topologically sort your DAG and then relax each edge, like you would in Bellman-Ford, in the order given by the sorting. The correctness follows from relaxing each edge along every path from the source node to every other node. Thus the single source shortest path can be computed for a DAG in $O(V+E)$.


How to solve a recurrence when the master theorem fails? How do solve the following recurrence?

  $$ T(n) = \frac{1}{2} T\left(\frac{n}{2}\right) + \frac{1}{n}. $$

Master's theorem cannot be applied as $a$ is equal to 0.5 which is less than 1. Hence the theorem fails. How do I solve a recurrence when the theorem fails?

You can explicitly unroll the recursion:
$$
\begin{align*}
T(n) &= \frac{1}{n} + \frac{1}{2} T\left(\frac{n}{2}\right) \\ &=
\frac{1}{n} + \frac{1}{n} + \frac{1}{4} T\left(\frac{n}{4}\right) \\ &= \cdots \\ &=
\frac{m}{n} + \frac{1}{2^m} T \left(\frac{n}{2^m}\right).
\end{align*}
$$
This easily leads to the solution
$$T(n) = \frac{\log_2 n + T(1)}{n},$$
which is valid for powers of 2.