Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering? Imagine I have an ordering on a bunch of elements like so:

Where an arrow $X \leftarrow Y$ means $X < Y$. It is also transitive: $\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(X < Z\right)$.

In order efficiently answer queries like $A \stackrel {?}{<} D$, some sort of labeling or data structure is required. For example, you could number the nodes from left to right, and thus you can simply do integer comparison to answer the query: $A \stackrel {?}{<} D \implies 1 < 4 \implies T$. It would look something like this:

Where the number is the ordering, and the letter is just a name.

But what if you needed to insert elements "in between" two other elements in the ordering, like so:

How can you maintain such an ordering? With simple numbering, you run into the problem that there are no integers "in between" $2,3$ to use.

Instead of simple numbering, you could spread the numbers out over a large  (constant sized) range, such as integer minimum and maximums of a CPU integer. Then you can keep putting numbers "in between" by averaging the two surrounding numbers. If the numbers become too crowded (for example you end up with two adjacent integers and there is no number in between), you can do a one-time renumbering of the entire ordering, redistributing the numbers evenly across the range.
Of course, you can run into the limitation that all the numbers within the range of the large constant are used. Firstly, this is not a usually an issue, since the integer-size on a machine is large enough so that if you had more elements it likely wouldn't fit into memory anyway. But if it is an issue, you can simply renumber them with a larger integer-range.
If the input order is not pathological, this method might amortize the renumberings.
Answering queries
A simple integer comparison can answer the query $\left(X \stackrel{?}{<}Y\right)$.
Query time would be very quick ( $\mathcal{O}\left(1\right)$ ) if using machine integers, as it is a simple integer comparison. Using a larger range would require larger integers, and comparison would take $\mathcal{O}\left(\log{|integer|}\right)$.
Insertion
Firstly, you  would maintain the linked list of the ordering, demonstrated in the question. Insertion here, given the nodes to place the new element in between, would be $\mathcal{O}\left(1\right)$.
Labeling the new element would usually be quick $\mathcal{O}\left(1\right)$ because you would calculate the new numeber easily by averaging the surrounding numbers. Occasionally you might run out of numbers "in between", which would trigger the $\mathcal{O}\left(n\right)$ time renumbering procedure.
Avoiding renumbering
You can use floats instead of integers, so when you get two "adjacent" integers, they can be averaged. Thus you can avoid renumbering when faced with two integer floats: just split them in half. However, eventually the floating point type will run out of accuracy, and two "adacent" floats will not be able to be averaged (the average of the surrounding numbers will probably be equal to one of the surrounding numbers).
You can similarly use a "decimal place" integer, where you maintain two integers for an element; one for the number and one for the decimal. This way, you can avoid renumbering. However, the decimal integer will eventually overflow.
Using a list of integers or bits for each label can entirely avoid the renumbering; this is basically equivalent to using decimal numbers with unlimited length. Comparison would be done lexicographically, and the comparison times will increase to the length of the lists involved. However, this can unbalance the labeling; some labels might require only one integer (no decimal), others might have a list of long length (long decimals). This is a problem, and renumbering can help here too, by redistributing the numbering (here lists of numbers) evenly over a chosen range (range here possibly meaning length of lists) so that after such a renumbering, the lists are all the same length.

This method actually is actually used in this algorithm (implementation,relevant data structure); in the course of the algorithm, an arbitrary ordering must be kept and the author uses integers and renumbering to accomplish this.

Trying to stick to numbers makes your key space somewhat limited. One could use variable length strings instead, using comparison logic "a" < "ab" < "b". Still two problems remain to be solved
A. Keys could become arbitrarily long
B. Long keys comparison could become costly


Identifying an object in an image based on color (AI ?) First off, I am not sure if this is the correct stackexchange site to ask this question on, so moderators can feel free to move it.

I am working on an application that identifies an object in an image.  For example, let's say that the object is an apple, and the apple can be green, red, or both.

My plan is to create an array the same size as the image, then scan through the image, pixel by pixel, and if the current pixel is within my range of colors (green-ish or red-ish), add a 1 to the corresponding location in the array, else add a 0.

After this scan through the array, I will have an array of 1s and 0s, which will hopefully contain a concentration of 1s, representing the apple.

I am a computer science student, but have yet to take an AI class.  So my question is:  is this a good way to go about doing this?  Or are there more established AI methods (or algorithms) for identifying objects in an image based on color?

EDIT:  I should clarify that the problem isn't identifying if the image contains an apple, the problem is identifying where the apple is in the image.

The general class for this problem is Template matching. The most common approach is performing a cross correlation of the template, in your example an apple, and an image which may contain the template.

A Google search for "template matching fast normalized cross correlation" will bring up some literature that should be helpful.


Path between two vertices in directed graph without cyclic vertices I have been searching online for some time but I have not found an answer.

Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic vertices can be found:

A path $v_1,\ldots , v_n$ (so $v_i\rightarrow v_{i+1}\in E$ for all $i$) has cyclic vertices when $v_{j}\rightarrow v_i \in E$ for some $i < j$.

For example: a the path $m \rightarrow v \rightarrow n\rightarrow u$ has cyclic vertices when $u\rightarrow v$.

My previous suggestion was wrong. So I have deleted, and will now modestly suggest another approach. Hope this works.

It seems your problem is NP hard. I will sketch a reduction from 3SAT.
take a formula $\varphi$. Construct a single line of vertices, with alternatives in between. The path describes a valuation, and a verification that all clauses are true.

First, let the variables be $x_1,x_2, \dots,x_n$. Then we have vertices $u_0,u_1, \dots u_n$, $x_1, \dots x_n$, and $\bar x_1, \dots \bar x_n$. And we set edges $(u_{k-1},x_k)$, $(x_k,u_k)$ and $(u_{k-1},\bar x_k)$, $(\bar x_k,u_k)$ for $k=1,\dots,n$. A path from $u_0$ to $u_n$ sets the variables.

Now consider the $m$ clauses. We continue by having $m$ fresh vertices $v_0,v_1, \dots v_m$. Connect $u_n$ to $v_0$. Let the $k$th clause be (for instance, to avoid too many variables) $(x_3\lor \lnot x_7 \lor x_8)$. For have three vertices $c_1, c_2,c_3$ for the alternatives, and connect these in parallel between $v_{k-1}$ and $v_k$: edges $(v_{k-1},c_i)$ and $(c_i,v_k)$.
Now we want to be able to choose a path via $c_i$ if the corresponding variable makes the clause true: so connect $c_1$ with a back edge to $\bar x_3$,  $c_2$ with a back edge to $x_7$, and  $c_3$ with a back edge to $\bar x_8$.

This somehow reminds me of a problem called Geography, which also uses a similar reduction, but is even PSPACE complete! So, check out that reduction, for reference. Your problem has no two players, and is within NP: one easily guesses and verifies a solution in polynomial time.


Time complexity of arithmetic operations I want to calculate the time complexity of the listed algorithms, please correct if I'm doing something wrong:
The question is, do some operations like multiplying, dividing, or plus really affect on time complexity ?

// Time complexity is O(log n)
    void calculate(n: Int) {

        while (k < n) {
            k *= 2 //or k *= k
        }
    }

// Time complexity is O(n)
void calculate(n: Int) {

    while (k < n) {
        k += 1000
    }
}

//Time complexity is O(log n)
void calculate(n: Int) {

    k = n

    while (k > 1) {
        k /= 4
    }
}

Your question is excellent! Unfortunately, my answer might disappoint you: the complexity of arithmetic operations depends on the computation model; to some extent, it's up to you to decide how much does it cost to add or multiply two numbers. Usually when analyzing algorithms, we assume the unit cost RAM model, in which arithmetic operations on two "reasonably sized" integers takes time $O(1)$. Here "reasonably sized" means of length $A\log n$, or equivalently, of absolute value at most $n^A$ (here $n$ is the size of the input). The constant $A>0$ should be fixed per algorithm. Its exact value doesn't matter, since we can simulate arithmetic operations on operands of size $m^2$ using $O(1)$ arithmetic operations on operands of size $m$.

In some cases, we have to do arithmetic on large integers. This happens in cryptography, for example. When adding or multiplying large numbers, operations no longer take $O(1)$ even in the unit cost RAM. For example, adding $m$-bit integers takes time $\Theta(m)$, and the best known algorithm for multiplication runs in $\tilde{O}(m\log m)$ (the tilde hides smaller multiplicative factors).

In most elementary algorithms, large integers do not show up, so you can just assume that arithmetic operations on variables take constant time. This is intended to be the case in all your examples.


Why any problem can be reduced to SAT is NP-Complete? I have a book statement says the title, I don't understand it. From my current understanding if a problem A can be reduced to a problem B then it only means B is at least as difficult as A.

Indeed that is incorrect. All problems in $\mathbf{P}$ are reducible to SAT. In fact, even trivial problems (e.g., finite languages) are reducible to SAT.

What is probably meant is that, if a problem in $\mathbf{NP}$ is such that SAT is reducible to it, then it is $\mathbf{NP}$-complete.


First Order interpretation of arbitrary structures as a graph I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph".

Given some arbitrary relational structure $S$ of some vocabulary $\sigma$, show that there are first-order queries $I$ and $I^{-1}$, such that $G:=I(S)$ is a directed graph, and $I^{-1}(G)$ is isomorphic to $S$.

I would be grateful for some hints and proof ideas, as I struggle a bit with seeing how the encoding would work.

The following is, as requested, a hint rather than a full answer.  I'll hint at one way of doing the coding; I'll not touch on how to define the queries but those formulas will always be horrible and you'd probably end up describing them in words anyway.  We'll code a structure $\cal{A}$ that has universe $A$ as a graph $G_\cal{A}$. The will contain one vertex for each element of $A$, plus a whole bunch of other vertices that encode the relations and so on.

You can assume a purely relational vocabulary by using standard codings of constants and functions as relations.
Coding is done by adding "gadgets": small graphs that you can recognize. Remember that, for every graph $H$ on $k$ vertices, there is a formula $\varphi_H(x_1, \dots, x_k)$ such that $(G, v_1, \dots, v_k)\vDash \varphi_H$ iff the subgraph of $G$ induced by $v_1, \dots, v_k$ is $H$.
You probably need a way to say "This vertex is an element of $A$." Come up with a gadget, make a copy of the gadget for each element of $A$ and add an edge between the gadget and the vertex coding that element.  (You might not need to do this but it's normally easier to just do it than to prove that it's unnecessary.)
You definitely need a way to say "This tuple $a_1\dots a_r$ is in the $r$-ary relation $R$." Come up with a gadget for each relation and a way to attach each tuple in $R$ to its own copy of the gadget. Remember that the tuple $a_1a_2a_3$ is different from $a_2a_3a_1$ so your coding needs to make those different.

If you don't understand what I mean about gadgets, mouse-over the following for a concrete example. However, the example gives away a lot of the answer, so try not to look at it.

   You could mark a vertex $v\in G_\cal{A}$ as coding an element of $A$ by adding a $k$-clique to your graph, along with an edge from one vertex of the clique to $v$. So, being adjacent to a $k$-clique means a vertex codes an element of $A$. Make $k$ big enough so there are no other $k$-cliques in $G_\cal{A}$.

If you still don't understand, leave a comment and I'll try to explain it better.


Connection between Pseudo random generators and hardness For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $U_n$ is uniform distribution over $\{0,1\}^n$.
According to Nisan Wigderson 1988, I know that if there exists $f\in E$ with $H_{avg}(f)\geq S(n)$ then there is a $S'(l)$-Prg where $S'(l)=S(n)^{0.01}$. For any general $S(l)$, a Pseudo-random generator, is called an $(S(l),\epsilon)$-Prg if for circuit family $C_{S(l)}$ of size $S(l)$ $|Pr_{x\in U_{l}}[C_{S(l)}(G(x))=1]-Pr_{x\in U_{S(l)}}[C_{S(l)}(x)=1]|<\epsilon$. Here $G$ is a pseudo random function $G:\{0,1\}^l\longrightarrow\{0,1\}^{S(l)}$, generates an $S(l)$ length strings from length $l$.
I was thinking if the converse is also true or not. Means, if we can show the existence of $S(l)$-Prg, then does it follows that there is $f$ with $H_{avg}(f)\geq S(n)$?

Theorem 1 in [Nisan Wigderson 1988] implies:
For any function $l\le s(l)\le 2^l$, the following are equivalent:

For some $c>0$, there exists a quick PRG $G: l\to s(l^c)$.
For some $c>0$, there exists a function $f$ in EXPTIME with hardness $s(l^c)$.

Although their definition of (quick) PRG and hardness are slightly different from yours, I think the conclusion is still the same (as long as $\epsilon <1/2$, and your conclusion should be $H_{avg}(f)\ge S(l^c)$ for some $c$ rather than $H_{avg}(f)\ge S(n)$).
The proof can be summarized as follows:

Regard the PRG as an extender from string of length $l$ to string of length $l+1$, and consider the boolean function $f$ corresponding to this extender.

Show that $f$ cannot be approximated by circuits of size $S(l^c)$, i.e., for some constant $k$, all large enough $l$, and all circuits $C_l$ of size $S(l^c)$, $\mathrm{Pr}_{x\in U_l}[C_l(x)\neq f(x)]>n^{-k}$ (note this is a weaker condition compared to the definition of hardness, i.e. your $H_{avg}$).

Use Yao's lemma [Yao 1982] to xor multiple copies of $f$ to obtain a function $f'$ such that $H_{avg}(f')\ge S(l^c)$.

You can see more details in [Nisan Wigderson 1988].


Is subtype polymorphism a kind of ad hoc polymorphism? "Ad-hoc polymorphism is obtained when a function works, or appears to work, on several different types (which may not exhibit a common structure) and may behave in unrelated ways for each type." – Strachey 1967

Subtype polymorphism seems to fit this description, albeit usually with late binding on the type that dictates the function's behavior. In Java, for example, the toString function works on any object at all, but has many wholly distinct implementations which are distinguished from one another based on the runtime type of the object; i.e., any class can override it and create a new ad hoc definition.

But when I poke around online, I usually find people making a sharp distinction between subtype polymorphism and ad hoc polymorphism; they are treated as wholly different beasts. Would it be correct to say that subtype polymorphism is a kind of ad hoc polymorphism? If not, why not?

They're definitely different things, which is easier to see with a clearer definition of ad-hoc polymorphism. Quoting from Wikipedia:

  ...ad hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types...

So in the definition you've quoted, they're using "on" to mean "passed as arguments", rather than "called from". Ad-hoc polymorphism is available in Java in the form of method overloading. For example BigDecimal has 5 divide(...) methods, all taking different sets of parameters. Other languages have more obvious examples of ad-hoc polymorphism, where there's only one function/procedure, with a list of parameters, and the programmer has to decide what to do with them inside the function/procedure.

Subtype polymorphism, however, is when you can treat an instance of one type as an instance of another type, so anything available on the second type is also avaialable on the first. This is the toString() example you give. toString() doesn't operate on different arguments, but it can be called from different types (because it's defined on Object which everything in Java is a subtype of).


Reducing 3CNF to Clique: Why do we omit negated literals? I have an example for a reduction of 3CNF to Clique, there is one thing I don't get about it, hopefully you could clarify it.  The reduction works like this:

  Construct a graph G = (V, E) as follows:

  Vertices: Each literal corresponds to a vertex.

  Edges: All vertices are connected with an edge except the vertices of
  the same clause and vertices with negated literals.

Why is it important that that negated literals will not be connected? How would that effect the reduction?

What is meant, is that literals that are the negation of each other are not connected. The reason for this is that they cannot both be satisfied at the same time. (The idea of the reduction is, that the graph contains a clique containing nodes corresponding to one literal from each clause, exactly if all these literals can be satisfied at the same time.)


Trouble understanding Grammar Rules I am totaly new to theoretical computer science, so I am sorry if I get the terminology wrong:

I was reading the definition of a grammar, what I didn't get was the formal definition of the production rules:
Let V be the set of Variables and sigma the alphabet. Let P be the set of Rules or productions. Formal: $P \subset (V \cup\sum)^+\times (V \cup\sum)^*$.

I saw an example with G = ({P}, {0,1}, A, P) with the set of rules A:

1.P $\to \epsilon$

2.P $\to 0$

2.P $\to 1$

4.2.P $\to 0P0$

Now my question: How can the last rule (no 4) exist? It is not an element of the subset of the cartesian product mentioned above.

$(V\cup\Sigma)$ represents the set of variables (like $P$) and terminals (like $0$).

$(V\cup\Sigma)^*$ represents all finite strings (including the empty string) that can be made from variables and terminals (like $0P0$ or, $01P10PP0P0$, for instance). The expression $(V\cup\Sigma)^+$ is almost the same, but excludes the empty string.

Functions are essentially matchings so can be represented by a Cartesian product $(x, f(x))$, so in your definition, a production in $(V\cup\Sigma)^+\times(V\cup\Sigma)^*$ is a pairing from nonempty strings to strings, like the ones you gave. Others would include

$V\rightarrow \epsilon$ (the empty string is often denoted by $\epsilon$ or $\lambda$).
$S\rightarrow 01001$, or even
$aT\rightarrow TbT$


How to prove "if every subset of a set is a CFL, then the set must be regular." "If every subset of a set is a CFL, then the set must be regular."

I want to prove it, could anyone please give me some hints?

Suppose that $L$ is a language such that each subset of $L$ is context-free. I claim that $L$ must be finite, and so regular. Indeed, otherwise $L$ would have uncountably many subsets, and so not all of them could be context-free (since there are only countably many context-free languages).


How to denote an array in writing paper How can I represent an array when I am writing to show an algorithm in writing paper. Like Pi is represented by Greek letter. We use that Greek symbol to denote the value of Pi, Kind of like a pointer.

So, is there any general symbol for representing array?

People often use capital letters to represent arrays.  $A$ is a common choice (for the 'a' in 'array'), but by no means mandatory.


Find the origin and the destination of a trip from a serie of tickets I was asked to design an algorithm that solves the following problem :

  Consider a travel from city A to city B, made of several trips by
  train through other cities in between. With an access to the
  unordered list of train tickets from which you can read the cities of
  departure and arrival of each trip, find A and B.

Unfortunately, I was unable to give an efficient algorithm when I needed to (in pseudo code), but once I got home, I came up with this answer (in JavaScript).

var tickets = [
    {from:'Paris', to:'Berlin'},
    {from:'London', to:'Paris'},
    {from:'Zurich', to:'Milan'},
    {from:'Berlin', to:'Zurich'}
    ];

function getTrip(tickets)
{
    var ticket = tickets.shift();
    var trip = {from:ticket.from, to:ticket.to};

    while(tickets.length > 0)
    {
        ticket = tickets.shift();

        if(ticket.from == trip.to)
        {
            trip.to = ticket.to;
        }
        else if(ticket.to == trip.from)
        {
            trip.from = ticket.from;
        }
        else
        {
            tickets.push(ticket);
        }
    }

    return trip;
}

var trip = getTrip(tickets);

console.log('The trip was from %s to %s', trip.from, trip.to);

While this might look like a very simple problem, I am still curious to see if there is a more efficient solution (for both time and space) or simply considerations I completely forgot. This may not need to be in JavaScript (especially if the language gives greater control over some aspects of the problem).

Using a hash table, record for each city mentioned how many times it was mentioned as a source and how many as destination. The source of the trip is the city that has appeared as a source an odd number of times, and similarly for the destination of the trip. That's linear time and space (with high probability).

Also, as Jan comments, the statistic that should be odd is the total number of times that the city has appeared. If a city appeared an odd number of times, then it is the source if it appeared as a source more than as a destination, and vice versa for destination.


Is there a more intuitive proof of the halting problem's undecidability than diagonalization? I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization.

While the proof is convincing (I understand each step of it), it is not intuitive to me in the sense that I don't see how someone would derive it, starting from the problem alone.

In the book, the proof goes like this: "suppose $M_H$ solves the halting problem on an input $M;x$, that is, decides whether Turing machine $M$ halts for input $x$. Construct a Turing machine $D$ that takes a Turing machine $M$ as input, runs $M_H(M;M)$ and reverses the output." It then goes on to show that $D(D)$ cannot produce a satisfactory output.

It is the seemingly arbitrary construction of $D$, particularly the idea of feeding $M$ to itself, and then $D$ to itself, that I would like to have an intuition for. What led people to define those constructs and steps in the first place?

Does anyone have an explanation on how someone would reason their way into the diagonalization argument (or some other proof), if they did not know that type of argument to start with?

Addendum given the first round of answers:

So the first answers point out that proving the undecidability of the halting problem was something based on Cantor and Russell's previous work and development of the diagonalization problem, and that starting "from scratch" would simply mean having to rediscover that argument.

Fair enough. However, even if we accept the diagonalization argument as a well-understood given, I still find there is an "intuition gap" from it to the halting problem. Cantor's proof of the real numbers uncountability I actually find fairly intuitive; Russell's paradox even more so.

What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you define them.

P.S.

@babou summarized what was troubling me better than myself: "The problem with many versions of the proof is that the constructions seem to be pulled from a magic hat."

It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context.

Remember that Turing knew Cantor's diagonalisation proof of the uncountability of the reals. Moreover his work is part of a history of mathematics which includes Russell's paradox (which uses a diagonalisation argument) and Gödel's first incompleteness theorem (which uses a diagonalisation argument). In fact, Gödel's result is deeply related to the proof of undecidability of the Halting Problem (and hence the negative answer to Hilbert's Entscheidungsproblem).

So my contention is that your question is in a sense badly founded and that you can't reach the Halting Problem without going past the rest (or something remarkably similar) first. While we show these things to students without going through the history, if you were a working mathematician it seems unlikely that you go from nothing to Turing Machines without anything in between - the whole point of them was to formalise computation, a problem many people had been working on for decades at that point.

Cantor didn't even use diagonalisation in his first proof of the uncountability of the reals, if we take publication dates as an approximation of when he thought of the idea (not always a reliable thing), it took him about 17 years from already knowing that the reals were uncountable, to working out the diagonalisation argument.

In reference to the "self-application" in the proof that you mention, this is also an integral part of Russell's paradox (which entirely depends upon self-reference), and Gödel's first incompleteness theorem is like the high-powered version of Russell's paradox. The proof of the undecidability of the Halting Problem is so heavily informed by Gödel's work that it's hard to imagine getting there without it, hence the idea of "self-application" is already part of the background knowledge you need to get to the Halting Problem. Similarly, Gödel's work is a reworking of Russell's paradox, so you don't get there without the other (note that Russell was not the first to observe a paradox like this, so prototypes of the diagonalisation argument has been around in formal logic since about 600BCE). Both Turing and Gödel's work (the bits we're talking about here that is) can be viewed as increasingly powerful demonstrations of the problems with self-reference, and how it is embedding in mathematics. So once again, it's very difficult to suggest that these ideas at the level Turing was dealing with them came a priori, they were the culmination of millennia's work in parts of philosophy, mathematics and logic.

This self-reference is also part of Cantor's argument, it just isn't presented in such an unnatural language as Turing's more fundamentally logical work. Cantor's diagonalisation can be rephrased as a selection of elements from the power set of a set (essentially part of Cantor's Theorem). If we consider the set of (positive) reals as subsets of the naturals (note we don't really need the digits to be ordered for this to work, it just makes a simpler presentation) and claim there is a surjection from the naturals to the reals, then we can produce an element of the power set (i.e. a real) that is not in the image of the surjection (and hence derive a contradiction) by take this element to be the set of naturals who are not in their own image under the surjection. Once we phrase it this way, it's much easier to see that Russell's paradox is really the naïve set theory version of the same idea.


Algorithm to find a path connecting given nodes in a graph Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for such a scenario?

Your problem is known as the Steiner tree problem. While this problem is NP-complete, it has efficient constant-factor approximation algorithms.


maximum matching in a bipartite graph for solving a chess rook maximization problem There's an n x n chessboard where some cells are instead holes. I want to have as many rooks as possible in a way that the rooks won't be able to capture each other. Rooks cannot be placed on the holes but can jump over them. How can I solve this problem using the finding maximum matching principle in a bipartite graph?

This is a well known problem in competitive programming. When you put a rook in a row and a column, you can no longer have any other rooks in that row and in that column. That is, you are matching rows to column, such that each row gets at most one column and each column gets at most one row. Sounds like bipartite matching?

What do the holes represent? Positions where you cannot place rooks. These are row-column pairs that cannot be matched. I will leave it as an exercise for you to figure out what that means in the bipartite graph of rows and columns.


Bachmair and Ganzinger, ordering of equations Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', page 4, defines an order on equations. (This is an arcane piece of machinery but a critical one in the overall attempt to get to the point where equations can be applied in one direction, thereby dramatically improving the performance of automated reasoning on problems involving equality.)

If $s \succ t \succ u$

Let $s\approx t$ have the multiset representation $\{\{s\},\{t\}\}$

Let $s\not\approx t$ have the multiset representation $\{\{s,\bot\},\{t,\bot\}\}$ where $\bot$ is a new symbol such that every existing symbol is greater than $\bot$.

Then $s\not\approx u \succ s\approx t$ even though $t \succ u$.

... wait, how? Sure, $s\not\approx u$ also contains a couple of occurrences of $\bot$, but what of that? $t \succ u \succ \bot$, so the comparison should be decided by $t$ vs. $u$; $\bot$ should not have enough weight to tip the balance, so to speak.

What am I missing?

(I have seen later writing that gives $s\not\approx t$ the multiset representation $\{\{s,s\},\{t,t\}\}$, and I see how this solves the problem, but I don't see how it is solved in the original version.)

A short answer to your question is to use the definition of multiset extension of a partial ordering.

We have the following:

Let $M = \{s,\bot\}$ and $N=\{s\}$. We have  $M\succ M$ since $M(\bot) > N(\bot)$ and there does not exist $x$ such that $N(x)> M(x)$.
Let $M=\{\{s,\bot\},\{u,\bot\}\}$ and $N=\{\{s\},\{t\}\}$. We have $M(\{s,\bot\})>N(\{s,\bot\})$ and by (1) $\{s,\bot\}\succ\{s\}$. Therefore $M\succ N$.

It would be interesting to see examples where the two ways of extending an ordering on equations to clauses disagree and discuss how that might affect the properties or performance of a rewrite-based prover.


Algorithm to find the size of a quotient of a free group Are there any algorithms to find the size of an algebraic quotient of a free group? It would take the generators as input and output the size. For example, an input could be something like
{a,b: a^8=b^2=1, ab=ba^3} (a quasidihedral group), and the output would be the integer 16, since there are 16 different ways to write a string formed of a's and b's if you treat aaaaaaaa and bb as the empty string, and the string ab as the same as the string baaa.

Ideally the algorithm would also be able to say if a group was infinite. It's not obvious by looking at the presentation what the size of the group is, and I think it's a fairly interesting question that I've comes across a few times in my algebra class, so I was surprised that I couldn't find a tool to solve it for me or any papers talking about it, it seems that computers should be good at this. Wondering if anyone has any good ideas.

I think you're asking: given a group presentation $\langle X | R \rangle$, determine the size of the group.

Unfortunately, it is undecidable to determine whether the group is finite or infinite.  See the Adian-Rabin theorem.

For some additional references, see also https://math.stackexchange.com/a/606/14578, https://math.stackexchange.com/q/3106606/14578, https://math.stackexchange.com/q/2756802/14578, https://math.stackexchange.com/q/1516849/14578, or the following lecture notes: Presentation of Groups.  Derek Holt.


How to get to the efficient solution of a problem on buying with exchange policy I was working through some coding challenges at hackerrank.com and got to this one.

I understand the problem and how to solve it, but after solving it I searched for more solutions to improve mine. So I found this.

After explaining the naive method, which is the one that I used, then there is the efficient solution. But I can not understand the explanation that goes from the naive method to the efficient solution.

Can someone help me understand how is the logic to get to the efficient solution:

  In above naive implementation, we noticed that after finding initial number of chocolates, we recursively divide the number of chocolates with the number of wrappers required. until we left with 1 chocolate or wrapper.
  We are recomputing the values i.e. ((choc/wrap + choc%wrap)/wrap until we get 1.
  It is observed that, we can get the result by just reducing the values of chocolates and wrappers by 1 and then divide them to get the result (choc-1)/(wrap-1)

It is observed that, we can get the result by just reducing the values of chocolates and wrappers by 1 and then divide them to get the result (choc-1)/(wrap-1).

First, we can verify by brute force that the number of additional chocolates we can get by returning wrappers repeatedly is indeed (choc-1)/(wrap-1).

Second, here is how we can understand or prove that formula.

Suppose we have wrap-1 wrappers. Imagine we can borrow one wrapper from a benefactor. Then we can return the wrap wrappers for a chocolate, the wrapper for which will be returned to the benefactor. So we do not owe the benefactor anything any more.

Looking back, we had wrap-1 wrappers initially while we had enjoyed one chocolate without wrapper in the end. So, every wrap-1 wrappers will bring one chocolate without wrapper, as long as we had no less than wrap wrappers. If we have choc wrappers, we will have choc/(wrap-1) wrapper-less chocolates. However, there is a catch. There is, in fact, no benefactor. So the number should be (choc-1)/(wrap-1) instead.

In a more friendly world where there are benefactors or a more admissible policy where wrap-1 wrappers can be exchanged for one wrapper-less chocolate, the number of additional wrapper-less chocolates will be choc/(wrap-1).


Turing machine that decides $A=\{0^{2^n} | n \ge 0 \}$ with an alphabet of two symbols I need to build a turing machine that decides $A=\{0^{2^n} | n \ge 0 \}$ with an alphabet of two symbols - $\{0, \_ \}$.
I'm aware of the known TM that decides this language with three symbols $\{0, x, \_\}$ but I am not able to come up with one that does it with just two.
Any advice would be highly appreciated

I'm assuming that $\_$ denotes the blank character. A strategy for the TM  you are looking for is the following:

Check if the input is a single $0$, if so accept.
Replace every other $0$ with $\_$. If, during this process, the number of encountered $0$s is odd, reject.
Pack all the $0$s together. This can be done as follows:

Reset the head to the beginning of the tape (search for a $0$ preceded by two $\_$).
Locate the last $0$ (i.e., the only one followed by two $\_$) and, in the process, remember if a $\_$ is encountered before it.
If no $\_$ is encountered you are done. Otherwise continue.
Replace the last $0$ with $\_$.
Locate the first $0$ and write write $0$ before it.
Repeat from step 3.2.

Repeat from step 1.


difference between deadlock avoidance and detection I know the difference between deadlock prevention and avoidance. But i want to know the difference between deadlock avoidance and detection. ?

Simply to put
Deadlock avoidance: you employ some methods to avoid the deadlock ,but prevention is more restrictive than avoidance.

Deadlock detection: Here only the detection only takes place whether the current state is in deadlock or not.


Count numbers less than $K$ in array Let's say we have given array $A$ consisting of $n$ integers, and integer $K$. Now we want to count number of indexes $i$ such that $A_i<K$. What is the easiest way to pre-process the array and answer queries for different $K$ fast. Note that the elements of the array will be small up to $10^5$, so it will be possible to count how many times each elements appears.

For example, let $A = \{1, 2, 3,0,0,2\}, K =3$ the answer is $5$, because all $\{1,2,0,0,2\}$ are less than $3$.

I know that we can implement this with segment tree and than answer queries in $O(\log N)$, but I was thinking that we can implement easier solution that is easier to code.

Here is a $O(1)$ solution after $O(n)$ preprocessing step, assuming that all elements are less than some number $C$ (in your case $10^5$) in pseudocode

count = new int[C] (array of integers)
for every a[i] in a
   count[a[i]]++
for i = 1, i < C, i++
   count[i] += count[i-1]

To Answer a query for a given k you just return count[k - 1]


Chomsky normal form and regular languages I'd love your help with the following question:

  Let $G$ be context free grammar in the Chomksy normal form with $k$
  variables.

  Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ?

What is it about the amount of variables and the Chomsky normal form that is supposed to help me solve this question? I tried to look it up on the web, but besides information about the special form itself, I didn't find an answer to my question.

The answer for the question is that $B$ might be regular.

Assuming that $B$ is regular, then $L(G)=B \cup \lbrace w \in L(G) \mid \vert w \vert \leq 2^k \rbrace$ is also regular because the union of a finite number of regular languages is regular  (especially, $k$ is a constant as the number of variables in the Chomsky normal form).

This can not be true in general because there are context free languages which are not regular.


Physical Meaning Behind Matrix Factorization As we all know, Matrix Factorization is an effective method to do rating prediction jobs in recommender systems. Thanks to the work of Yahuda Koren. My question is why MF can do this job? What's the physical meaning behind it?

The idea in matrix factorization is to find the latent variables which connect the input and the output. Suppose that we are interested in a movie recommendation system, and that movies "live" on a one-dimensional axis, having romantic comedies in one end, and action movies in the other. Each "input" and "output" move can be rated in this scale (say $1$ to $-1$). Given the input movies, we can estimate a person's location $p$ on the axis (say a point in $[-1,1]$) by taking the inner product between the movies they saw and their "ratings" $r_i$, i.e. $p \approx \frac{1}{n} \sum_{i=1}^n r_i$, where $1,\ldots,n$ are the movies seen by the person. Given the location, we can estimate how much that person will like other movies: movie $t$ will be liked by an amount proportional to $pr_t$ (this is just a simplistic linear model).

In this example, the recommendation matrix can be decomposed as an outer product $A_{it} = r_i r_t$. More generally, the situation could depend on several latent variables, and this is the general situation described by matrix factorization. The number of latent variables is the "middle" dimension in the factorization. If you have found a good factorization with only a few variables, then you have a succinct explanation of your data that could have predictive power.


Shortest unambiguous representation of a graph over an alphabet I just started reading a book on theoretical computer science and here are a couple of beginner questions about graphs, which I am struggling to answer:

  Given the graph with the matrix representation
  \begin{bmatrix}0&0&1&1\\0&0&1&1\\0&1&0&1\\0&0&0&0\\\end{bmatrix}
  what is its shortest possible unambiguous representation over the boolean alphabet? How about over any alphabet?

Thank you :)

Using the definitions from: Theoretical Computer Science: Introduction to Automata and Computability by Juraj Hromkovič.

A representation for the graph will be said to be Unambiguous if the graph can be reconstructed from that representation.

Basically, we wish to encode a general graph using boolean alphabet $\Sigma = \{0,1\}$. If we had an additional symbol $|$ in our alphabet, then we can easily encode the graph matrix as $0011|0011|0101|0000$.

But, as we dealing with only boolean symbols, we have to come up with some encoding that doesn't need the separator $|$. An easy way for doing this could be making each 5th bit special. If it is $0$ then it will mark a separator, else the next four bits are also encoding a single row of the matrix, and it won't mark a separator. If the encoding of row doesn't need additional four bits, then make the extra bits $0$. (You need few more such rules to make this encoding "unambiguous").

For example, your matrix can simply be encoded 0011 0 0011 0 0101 0 0000.

Of course, there are much better possible encodings which might utilize the presence of patterns in the matrix (like sparse matrix).

But, your question asks: Given a matrix representation of a graph, what is its shortest possible unambiguous representation over the boolean alphabet? Well, we can easily come up with a trivial encoding: the empty string $\epsilon$ represents the given graph and all other strings represent the graph as per the encoding described above.

So, the smallest unambiguous representation of the given graph matrix would be of length $0$.

This will also hold for any other alphabet.


Implement a search procedure in terms of a set test procedure Suppose you have a procedure $\mathrm{Prod}(S, t)$ that inputs a finite set of integers $S$ and an integer target $t$, and outputs either “yes” or “no” according to whether there exist distinct elements $x_1, \dots, x_n \in S$ with $\prod_{i=1}^n x_i = t$. You would like to implement an enhanced version of $\mathrm{Prod}(S, t)$, called $\mathrm{ProdSearch}(S, t)$ that outputs the elements $x_1, \dots, x_n$ if such elements exist.

Describe an efficient such procedure $\mathrm{ProdSearch}$ that works by making multiple calls to $\mathrm{Prod}$ as a sub-routine. Carefully explain why your procedure is correct.

Hint: Suppose you asked your oracle whether there is a subset of $\{x_2,\ldots,x_n\}$ whose product is $t$. What can you deduce if the answer is YES? What can you deduce if the answer is NO?

Here is the full solution:

   If the oracle answers YES, we deduce that we can remove $x_1$ from $S$. If the oracle answers NO, we deduce that every solution must contain $x_1$. We therefore remove $x_1$ from $S$ and update our target product to $t/x_1$. Continuing in this vein for $n-1$ more iterations, we find a solution. This requires at most $n$ calls to $\mathsf{Prod}$ in total.


What is the fastest online sorting algorithm? Quoting Online algorithm from Wikipedia:

  In computer science, an online algorithm[1] is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.

One is Insertion Sort, but it runs in horrible $O(n^2)$ time.

I suggest Tree Sort, variant with self-balanced tree. In this case complexity is $O(logn)$ (per insertion).
In that case you can access sorted structure at any time.

If inputs comes in batches, sort batch (with any fast algoritm) and then merge.

Other algorithms will also suffer from divided input, but insertion sort is poor even if input is available at once.

Natural split into sorted parts occurs in Mergesort and Timsort. But overall performance should be adjusted to needs: if data comes one at the time, but there is no need to retreive sorted version, it would be nice to keep smaller sorted buffers.
When length of array is known in advance and distribution the set it is possible to do distribution based sort, it spares some empty cells for incomming data.
If data could be divided into ranges, this would enable partitioning of data as it arrives.


Lower bound on positive coefficients of the optimum of 0,1-linear programming problem I have an instance linear programming such that the coefficients and the constant terms are 0 or 1.
Formally, the set of variables is denoted as $V$ and $|V| = n$. There are $m$ constraints, formed as
$$ \mathbf{a}_{1}^{\top} \mathbf{v} \leq 1 $$
or
$$ \mathbf{a}_{2}^{\top} \mathbf{v} \geq 1 $$
where $\mathbf{a}_{1}, \mathbf{a}_{2} \in \{0,1\}^{n}$ and $\mathbf{v} = [v_{1}, v_{2}, \ldots, v_{n}]^{\top}$. (Assume that $0 \leq v_{i} \leq 1$).
The objective function is
$$\min \sum_{i}v_{i} = [1,1, \ldots, 1] \cdot\mathbf{v}$$
I am hoping to find a constant $c \geq 0$ (depending only on $n$) such that there always exist an optimum $\mathbf{v}^{*} \in [0,1]^{n}$ satisfying $v^{*}_{i} = 0$ or $v^{*}_{i} \geq c$.
Does it hold for $c = 1/n$? Is there any positive lower bound on $c$?
For example, consider the LP relaxation of the vertex cover problem. The constraints are formed as
$v_{i} + v_{j} \geq 1$, for each edge $v_{i}v_{j} \in E(G)$. We know that there exists a half-integral optimum, i.e., $v_{i} \in \{0,1/2,1\}$.

$\frac 1n$ is not a lower bound.
For example, let $n=10$.
Consider 3 set of equations (you can get equalities by considering both $a^\top v \le 1$ and $a^\top v \ge 1$):

\begin{align}
v_1 + v_2 + v_3 \qquad = 1\\
\qquad v_2 + v_3 + v_4 = 1\\
v_1 \qquad  + v_3 + v_4 = 1\\
v_1 + v_2 \qquad + v_4 = 1\\
\end{align}
It's easy to check that $v_1=v_2=v_3=v_4=\frac 13$ is the unique solution.

Consider $v_5 + v_6 + v_7 + v_8 + 0 \cdot v_9 = 1$ and, similarly to the above case, all cyclic shifts of $(v_5, \ldots, v_9)$. Again, the unique solution is $v_5 = v_6 = v_7 = v_8 = v_9 = \frac 14$.

The last equation is
$$v_1 + v_2 \qquad + v_5 \qquad + v_{10} = 1$$
Then $v_{10} = 1 - 2 \cdot \frac 13 - \frac 14 = \frac 1 {12}$.

Generalizing it, you can always obtain coefficient $\frac 1{k (k+1)}$ using $2k + 4$ variables.
I think that by properly selecting numbers $p_1, \ldots, p_k$, you should be able to get a coefficient as small as $O\left(\frac 1 {\prod_i p_i}\right)$ with $O\left(\sum_i p_i\right)$ variables.


Regular Expression for language I have a grammer with the following productions,
S -> aA | bC | b
A -> aS | bB
B -> aC | bA | a
C -> aB | bS

I have to construct regular expression for it. I derived words for this language and which are

b, aab, aba, baa, bbb, aaaab, aaaba, aabbb, abaaa, baaaa, ...

So after I deriving the words I concluded that it's a language of strings having odd number of b and having odd length.
Can you please help me to construct regular expression for it.
I appreciate your help.

Note that your grammar is regular. Quoting from wikipedia:

A grammar is regular when no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side.
Every regular grammar corresponds directly to a nondeterministic finite automaton, so we know that this is a regular language.

In theory, every regular grammar generates a regular language. Also, its not hard to construct the relevant NFA for the generated language: for a specific example on how to do that, you can click here (this is actually what has been done in @Matthieu Latapy's answer). Once you have an NFA for the language, you can translate it into a regular expression (there are several ways to achieve this based on state removal methods which are a bit tedious: see here).
BTW, you already know that your language is all words with "odd length and odd number of b's". It is easy to build a DFA for it consisting of 4 states (hint: your language is an intersection of two languages, each having a DFA with two states).


Can application DNS requests bypass a firewall on Windows and Linux Assuming I have firewall set to block an application from accessing the Internet, would I DNS request go through?
I tried using C (gethostbyname) on Windows and the answer is no. It seems that the application sends the DNS request to the public DNS server, but I wonder if this is the same under Linux.
In particular, could there be that there is a local DNS server (loopback interface) running on the OS such that gethostbyname would instead use the local DNS for the requests. Firewalls may block public packets but for private subnets especially for loopback that may be allowed to applications depending on how one configures the firewall. This way a block app would place a request to an unblocked app (DNS local relay server) that can communicate with a remote system.

It depends on the policy enforced by the firewall.  If it blocks outbound DNS requests, then the request wouldn't go through; if it doesn't, the request would go through.  A firewall is a mechanism; it has to be configured with a policy that determines which packets or connections are allowed and which are blocked.  Just saying you have a firewall does not tell us what policy you have chosen to have it enforce.
The details of how gethostbyname() behaves are beyond the scope of this site.
You certainly could have a situation where the firewall blocks an application from making DNS requests to the outside world but allows them to a local DNS server; and where the local DNS server acts as a resolver or a proxy and itself makes requests to the outside world.  That will depend on the firewall and how it is configured as well as the DNS server and how it is configured.


Finding farthest item in an array with duplicates I have an array $A[]$ of size $L$, which contains numbers in the range $1 \ldots N$.  Here $L>N$, so the array will contain repetitions.  If $x,y$ are two numbers that are both present in the array, define the distance $d(x,y)$ to be the minimum difference in positions where $x,y$ appear, i.e.,

$$d(x,y) = \min \{|i-j| : A[i]=x, A[j]=y\}.$$

Given a number $x$ that is present in the array, I need to find the number $y$ in the array distance from $x$ is as large as possible.  In other words, given $x$, I am trying to find $y$ that makes $d(x,y)$ as large as possible (subject to the restriction that $y$ is a number in $A[]$).

Can this be done in $o(L)$ time per query?  It's OK to do some pre-processing of the array.

For example, suppose the array is $[1,3,2,3,4,5,3]$.  Then $d(5,3)=1$, since there is a $5$ one position away from a $3$ (a $5$ appears at index $5$ and a $3$ appears at index $6$).  If the query is $x=5$, the correct answer is $y=1$, since this makes the value of $d(5,y)$ as large as possible.

Here's a scheme that does $O(L \lg L)$ preprocessing, and thereafter lets you answer query for the value $x$ in $O(rN \lg L)$ time, where $r$ counts the number of times that $x$ is repeated.  This will be slightly more efficient than the naive algorithm for values $x$ that don't occur too many times in the array, but inefficient for common values.

Here's how.  During preprocessing, we're going to build a map $f$ defined by

$$f(y,i) = \min \{ j>i : A[j]=y \}.$$

Similarly, we're going to build a map $g$ defined by

$$g(y,i) = \min \{j<i : A[j]=y \}.$$

(We'll also build a set of inverted indices that, given $x$, enables us to enumerate all indices where $x$ appears in $A$.)

Note that these maps $f,g$ help us compute the distance function $d$ efficiently.  In particular,

$$d(x,y) = \min \{ f(y,i)-i : A[i]=x \} \cup \{ i-g(y,i) : A[i]=x \},$$

which can be computed with $r$ evaluations of $f$ and $r$ evaluations of $g$.  Consequently, given $x$, we'll be able to find the value $y$ that maximizes $d(x,y)$ using $rN$ evaluations of $f,g$, by simply trying all possibilities for $y$.

We're going to use the preprocessing to arrange things so we can evaluate $f,g$ at an input of our choice in $O(\lg L)$ time.  How do we do that?

Unfortunately, storing $f$ explicitly would take $NL$ space, which is too much.  Fortunately, there is a lot of redundancy in $f$: there are long ranges of indices $i,i+1,\dots,i'$ such that $f(y,i)=f(y,i+1)=\dots=f(y,i')$.  This is going to help us represent $f$ more compactly.  Similarly for $g$.

In particular, we'll store $f(y,\cdot)$ as an interval tree: whenever we have an interval $[i,i']$ such that $f(y,i)=f(y,i+1)=\dots=f(y,i')=\alpha$, then we add a single interval to the tree with the mapping $[i,i'] \to \alpha$.  In this way, $f$ is stored as $N$ different interval trees.  It is possible to show that the total number of leaves, across all of these interval trees, is at most $L+N=O(L)$ (in particular, the tree for $f(y,\cdot)$ has at most $r'+1$ leaves, where $r'$ counts the number of occurrences of $y$ in $A$).  If we store these trees as balanced binary trees, their height will be upper-bounded by $O(\lg L)$.  Consequently, the total amount of space needed to store these trees is $O(L \lg L)$.  You can also show how to generate these trees in $O(L \lg L)$ time.  Finally, evaluating $f$ at a point of your choice amounts to a stabbing query in the corresponding interval tree, which takes $O(\lg L)$ time.  This shows how to achieve the time complexity quoted in the first sentence of my answer.

As an optimization, if $x$ appears in $A$ more than $L/(N \lg L)$ times, you can answer the query in $O(L)$ time using a standard linear scan (skipping the above cleverness).  Of course, you can detect quickly which values of $x$ occur that often by using the inverted indices built during preprocessing.

With this idea, we get a scheme that requires $O(L \lg L)$ preprocessing and lets us answer each subsequent query in $O(\min(L, rN \lg L))$ time, where $r$ counts the number of times that the queried value occurs in $A$.


Solving 2-CNF TQBF with #SAT solver? We clearly know that 2-QCNF is in $\mathsf{P}$. Since that, if I understand it right, it is possible to solve it with #SAT solver (because $\mathsf{P} \subseteq \mathsf{\#P}$). But how can we only knowing amount of positive assignments for some non-quantified formulae solve 2-QCNF? And why this doesn't hold (at least, assumed so) for general case of TQBF?

First of all, it is a bit misleading to say that $\mathsf{P} \subseteq \mathsf{\#P}$, since $\mathsf{P}$ is a class of decision problems, while $\mathsf{\#P}$ is a class of counting problems. However, we can think of a decision problem as a counting problem in which the answer is 0 (no) or 1 (yes), and in that sense it is certainly true that $\mathsf{P} \subseteq \mathsf{\#P}$.

The problem $\mathsf{\#SAT}$ is $\mathsf{\#P}$-complete. This means that for any problem $A \in \mathsf{\#P}$ there exists a polynomial time reduction $f$ such that for any instance $x$ of $A$, we have
$$ A(x) = \mathsf{\#SAT}(f(x)), $$
where $A(x)$ is the value of the counting problem $A$ on instance $x$.

Since $\mathsf{2QCNF} \in \mathsf{P}$, there is a trivial reduction from $\mathsf{2QCNF}$ to $\mathsf{\#SAT}$: if the $\mathsf{2QSAT}$ is satisfiable, we output the formula $x$, and otherwise we output the formula $x \land \lnot x$. This reduction runs in polynomial time since $\mathsf{2QCNF} \in \mathsf{P}$.


What is the minimum required storage for a sparse, depth-first octree? For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree on disk, given the following conditions:

It is very sparse (i.e., not all nodes exist), but potentially deep (a depth of 20 or beyond)
It is stored depth-first (pre-order)
All parent nodes up to the root node must be stored (i.e., it is not sufficient to store just the leave nodes)
The amount of data per node is a global constant

The best I can come up with is 6 7 bits per node: 3 bits to indicate the position of a node with respect to its parent, and 3 4 bits to store how many child nodes exist. However, intuition tells me there should be a more efficient way. Please note that algorithmic efficiency is not part of the question, as its representation in memory will be different anyways.

P.S.: Please let me know if CS is not the right SE venue for this kind of question.

Update

The resulting data structure will be stored in a file on disk, thus the need for an efficient encoding of the octree. There are additional data files that contain information associated with each existing node (e.g., solution data). To have a one-to-one relationship between nodes ("cells") in the octree file and the datasets, it is required to store all internal nodes (i.e., non-leaf nodes) in the octree file as well.

Example

An octree with 5 nodes: 0, 1, ..., 4. Their relationship is the following:

0 is the root
1 is child 0 of node 0
2 is child 1 of node 1
3 is child 5 of node 1
4 is child 1 of node 0

The resulting tree would look something like this (with missing nodes omitted)

    0
   / \
  1   4
 / \
2   3

and the nodes need to be stored 0 1 2 3 4 (pre-order depth-first).

The number of octrees with $n$ nodes is OEIS sequence A007556:

$$T(n) = {8n \choose n}/(7n+1)$$

I worked this out, incidentally, by writing a short program to generate the first few values of $T(n)$ and then searching for it.

If you had no other information than $n$, then the minimum number of bits required to store an octree with $n$ nodes is $\log\,T(n)$. (We're doing information theory here, so all logarithms are in base 2 unless otherwise specified.) Using Stirling's approximation to the logarithm of the factorial:

$$\log n! = n \log n - n \log e + O(\log n)$$

We find:

$$\log\,T(n) = (24 - 7 \log 7) n + O(\log n)$$

Which works out to $24 - 7 \log 7 \approx 4.349$ bits per node. So to answer the first part of your question, this is the theoretical minimum. You cannot do better than this.

Now we just have to address the second part: How close can we get?

Consider a bit vector of size $8n$, $8$ bits per node, where you put a 1 if the node has a child in that slot, and a 0 if it doesn't. This obviously uses about twice the space theoretically needed.

However, 0's and 1's don't occur with the same frequency. Specifically, given an octree with $n$ nodes, exactly $n-1$ of the bits must be 1 (exercise: why?), leaving $7n+1$ of them 0. The entropy of a bit is, therefore, approximately:

$$H = -\frac{1}{7} \log \frac{1}{7} - \frac{6}{7} \log \frac{6}{7} \approx 0.59$$

So you should be able to compress the bit vector to $8nH \approx 4.733n$ bits.

The actual compression method that I will suggest, because it's easy to understand and doesn't use anything complicated to implement like arithmetic coding, is Elias-Fano coding with parameter $b=2$.

We'll use your octree as an example. The bit vector corresponding to your exanple is:

11000000 01000100 00000000 00000000 00000000

We know that because $n=5$, the number of bits that are set must be $n-1=4$. We work out the indexes of the bits that are set:

$$\left\{0, 1, 9, 13\right\}$$

Or in binary, using $\left\lceil \log(8n) \right\rceil = 6$ bits per entry:

0000 00
0000 01
0010 01
0011 01

I've separated the low order $b$ bits for a reason. The compressed representation has two parts, one for the high-order bits and one for the low-order bits.

For the low-order bits, we just store these in an array. That is:

00 01 01 01

For the high-order bits, we count the patterns. Since there are no indexes that are larger than $8n-1=39$, There are only 10 possible patterns for the high-order bits:

$$\{0000,0001,0010,0011,0100,0101,0110,0111,1000,1001\}$$

We count the number of indices with each of the high-order patterns, and then encode those counts using a unary code:

110 0 10 10 0 0 0 0 0 0

(In practice, you probably don't need to work out all the high-order bit patterns, just stop when you run out of indices. But I digress.)

On this example, the representation uses 8 bits for the first array, and 14 bits for the unary-encoded bit vector, for a total of 22 bits, or 4.4 bits per node.

Recall that the asymptotic theoretical minimum is 4.349 bits per node.

Working out the asymptotic size of this representation as $n \rightarrow \infty$ is left as an exercise. So is actual code to do the compression and decompression.

Finally, I know you didn't ask about algorithmic efficiency, but storing the bit vector in an SDArray with succinct rank/select indices (there are implementations all over the place; look them up), you should be able to make this data structure random access in close to constant time. That is, you should be able to query the octree in its compressed form. The details are, again, left as an exercise.


Which is more computationally efficient: multiplication or 0 padding? On a PC I am implementing an algorithm in which a number from a look table will be chosen randomly, and will be multiplied by 1000 or 10000. Instead of multiplying by 1000 or 10000 I am thinking of simply padding the numbers with the required 0s. This padding will be nothing but some write operations (though random writes) in memory.

Which is more computationally efficient: multiplication or 0 padding?

I'm assuming that your numbers are in binary. In this case, 0 padding is shift left: x << 3 is the same as x * 0x08, where 0x08 (hex) is 1000 (binary).

Shifting is much simpler to implement in hardware and is generally more efficient. You could check by writing a short C program.

Note that there is one significant difference between shift left and multiplication. The former does not signal if there is an overflow error, whereas the latter will.


Does a DPDA halt on all inputs? Given a deterministic DPA, is it possible to tell whether it halts on all possible inputs?  Is this problem decidable?

The standard halting problem is "Given a DPDA and an input $x$, determine whether it halts on input $x$", and that problem is decidable.  But what about the variant above?

Yes, this problem is decidable.  It can be answered in polynomial time.  We can check whether there exists any input $x$ that causes it to enter an infinite loop, by characterizing the states from which it could enter an infinite loop.

First, let me establish some terminology.  Let $Q$ denote the set of states of the DPDA, and $\Gamma$ the stack alphabet.  A configuration is a pair $(q,t)$ with $q \in Q$, $t \in \Gamma^*$, where $q$ represents the state of the automaton and $t$ the contents of its stack.  Define the status of the automaton at any point to be a pair $(q,\gamma)$ where $q \in Q$ represents the state of the automaton and $\gamma \in \Gamma$ the symbol at the top of the stack.  Thus, the status gives only partial information about the configuration of the automaton.

Now, the strategy is going to be twofold:

We will determine, for each possible status $(q,\gamma)$, whether that status is reachable (i.e., whether there is some input $x$ that takes the automaton to a point where it is in that status).
We will also determine, for each possible status $(q,\gamma)$, whether the automaton enters a particular kind of infinite loop if the automaton starts in the configuration $(q,\gamma)$ and then reads the input $\epsilon$ (the empty word).  In particular, if it starts in configuration $(q,\gamma)$ and reads the input $\epsilon$, we'll test whether it transitions to any configuration $(q,t)$ where $t$ has the form $\cdots \gamma$ (i.e., $\gamma$ at the top of the stack, with some other stuff below it in the stack) in the process of reading the empty word.

Putting these two together, if there is a status $(q,\gamma)$ for which the answer to both questions is yes, then we will learn that the input $x$ causes the automaton to enter an infinite loop.  We will show a polynomial-time algorithm for each.  Since there are only finitely (in fact, polynomially) many possibilities for the status, this gives a polynomial-time algorithm for the original problem.  So, on to the details of how to check each of these things.

First, reachability is easy and can be tested using standard methods.  (For instance, construct a new automaton that halts when it enters the status $(q,\gamma)$ and otherwise doesn't halt, then check whether that automaton accepts the empty language or not; there is a standard algorithm for that.)

Second, it's easy to find all statuses $(q,\gamma)$ where an automaton that starts in configuration $(q,\gamma)$ and reads the empty word will enter an infinite loop of the particular kind mentioned above.  (One way is to reduce this to reachability; construct a new automaton that starts in configuration $(q,\gamma)$ and halt if it reaches any configuration of the form $(q,\dots \gamma)$ apart from the initial state, discarding all non-$\epsilon$ transitions from the original automaton and keeping only the $\epsilon$ transitions.  Then, check whether this new automaton accepts a non-empty language.)

This yields an algorithm for the original problem.  Why is it correct?

Well, if this algorithm outputs "yes", then it is correct -- there exists an input $x$ that causes the automaton to halt.  In particular, we know there exists an input $x$ that causes the automaton to transition to status $(q,\gamma)$, i.e., to some configuration of the form $(q,t_0 \gamma)$.  Suppose reading the empty word causes the automaton to transition from configuration $(q,\gamma)$ to $(q,t_1 \gamma)$; then it follows it will subsequently transition to $(q,t_1 t_1 \gamma)$ and even later to $(q,t_1 t_1 t_1 \gamma)$ and so on, entering an infinite loop.  Thus, reading the empty word will cause the automaton to transition from the configuration $(q,t_0 \gamma)$ to the configurations $(q, t_0 t_1 \gamma)$ and $(q, t_0 t_1 t_1 \gamma)$ and so on, thus entering an infinite loop.  Since the input $x$ takes us to that configuration $(q,t_0 \gamma)$, we have found an input $x$ that causes the DPDA to enter an infinite loop.  So if the algorithm says "yes", it is correct.

What about the converse?  Let's suppose there exists some input $x$ that causes the DPDA to enter an infinite loop.  It follows that the infinite loop must happen during the $\epsilon$-transitions that follow some finite prefix of $x$, say $x'$.  Let $(q',t')$ denote the configuration of the automaton immediately after reading the last letter of $x'$ (but before following any of the subsequent $\epsilon$-transitions).  Let's consider the sequence of configurations that the DPDA visits after that point, by following the $\epsilon$-transitions.  By assumption, this is an infinite sequence.  Consider the corresponding sequence of statuses.  Since that is infinite sequence, and there are only finitely many statuses, there must be at least one status that appears infinitely many times.  Discard a large enough prefix of the sequence so that you remove all the statuses that occur only finitely many times, so that now we have a sequence where all statuses recur infinitely many times; such a prefix must exist.   Among all configurations in the resulting sequence, pick the configuration where the height of the stack is minimal.  Call this configuration $(q,t)$ where $t=t_0 \gamma$.  By the choice of $(q,t)$, it follows that in all subsequent configurations the stack is at least as tall, so the original symbols $t_0$ are never popped, i.e., all subsequent configurations are of the form $(q',t_0 u)$ for some $q' \in Q$, $u \in \Gamma^+$.  Also since the status $(q,\gamma)$ recurs infinitely often in the sequence and since $(q,t_0 \gamma)$ was the one of minimal height, there must be some subsequent configuration of the form $(q, t_0 t_1 \gamma)$ (i.e., some subsequent configuration with the same status, but stack at least as high).  And since we got from $(q, t_0 \gamma)$ to $(q, t_0 t_1 \gamma)$ by $\epsilon$-transitions, without ever popping off the $t_0$ part, this means we'll enter an infinite sequence $(q, t_0 \gamma) \leadsto (q, t_0  t_1 \gamma) \leadsto (q, t_0  t_1  t_1 \gamma) \leadsto (q, t_0  t_1 t_1  t_1 \gamma) \leadsto \cdots$.  Since the $t_0 \gamma$ was never popped off, that also means that if we had started in the configuration $(q, \gamma)$, we would also have entered an infinite sequence $(q, \gamma) \leadsto (q,  t_1 \gamma) \leadsto (q, t_1 t_1 \gamma) \leadsto \cdots$, and this would have been detected in step 2 of the  algorithm.  Also, by assumption, since the configuration $(q, t_0 \gamma)$ is reachable on input $x'$, the status $(q,\gamma)$ is reachable and this would be detected in step 1 of the algorithm.  In summary, if there exists an input $x$ that causes the DPDA to enter an infinite loop, there exists a status $(q,\gamma)$ that is reachable and that triggers an infinite loop of the specific kind detected in step 2 of the algorithm, so the algorithm will output "yes".


Prove correctness of DFA ending with ab I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$

I know that I need to prove by induction on the length of the word but I am not sure how to do the induction step.

My try:

Anchor: After processing the only string of length zero, ε, the automaton is in state $q_0$ as claimed.

Hypothesis: After reading a string u the automaton is in state $q_1$ iff $u=xa$, and in state $q_2$ iff $u=xab$ and in $q_0$ iff $u=ε$ or $u=xb$. The claim holds for input fragments of length up to n.

Step: Any string $v$ of length $n+1$ is either $v=ua$ or $v=ub$

We split to cases:

$v=ua$ : According to the hypothesis- if $u$ ends with $b$ then it must be either in $q_0$ or $q_2$ - there for if we call $a$ after that we get to $q_1$ so $ua$ is not accepted.
Also, if $u$ ends with $a$ then it must be in $q_1$ - there for if we call $a$ after that we get to $q_1$ so $ua$ is not accepted.
$v=ub$ : According to the hypothesis- if $u$ ends with $b$ then it must be either in $q_0$ or $q_2$ - there for if we call $b$ after that we get to $q_0$ so $ub$ is not accepted.
Also, if $u$ ends with $a$ then it must be in $q_1$ - there for if we call $b$ after that we get to $q_2$ so $ua$ is accepted.

There is no induction needed. There is only one transition reaching the final state $q_2$, namely $q_1 \xrightarrow{b} q_2$. Furthermore, every transition reaching $q_1$ is labelled by $a$. It follows that every word accepted by the automaton has to end by $ab$. It remains to prove that, conversely, any word of the form $uab$ is accepted. After reading $u$ from the initial state $q_0$, you reach one of the three states $q_0$, $q_1$ or $q_2$. It suffices now to observe that $q_0 \xrightarrow{ab} q_2$, $q_1 \xrightarrow{ab} q_2$ and $q_2 \xrightarrow{ab} q_2$. Thus $q_0 \xrightarrow{uab} q_2$ in all cases, which means that $uab$ is accepted.


Combinatorial optimization algorithm with constraints and objective function I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function.
.e.g
Say each item in the set has integer-valued properties A, B, C. I need to select n items (say 2, can pick any item at most once) such that the sum of the property B among all selected items is at least 50 and the sum of all C's is at least 60 (two constraints), and I need to maximize for sum of A.
Where should I start looking? I was pointed towards LP but am unable to formulate it since I'm looking to pick exact items from a set.

You can indeed formulate an Integer Linear Program. Let $x_i \in \{0,1\}$ denote whether you select item $i$. For each item $i$ define $f_a(i)$,  $f_b(i)$, and $f_c(i)$ as the integer values for the properties $A$, $B$, and $C$.
Then we define the objective function as maximizing $\sum_{i = 1}^{m} f_a(i) \cdot x_i$, given $m$ items in total.
Your constraints are very similar as well, namely $\sum_{i = 1}^{m} f_b(i) \cdot x_i \geq 50$, and $\sum_{i = 1}^{m} f_c(i) \cdot x_i \geq 60$.
Since you can select at most $n$ of those $m$ items, you need to following constraint: $\sum_{i = 1}^{m} x_i \leq n$.
You can then easily recover the solution from your variables. Simply check whether $x_i = 1$, and if so, add item $i$ to your solution.


Combinator terminology: What is "strong" about strong composition? A strong composition operator seems to be very fundamental. (Hindley and Seldin use the notation S for "strong" composition combinator). It abstracts the pattern $f(x, g(x))$, i.e. a direct and a $g$-mediated effect of $x$. It's probably my inexperience but, why is this "strong"? Is it because normal (weak?) composition looks like a special case of this (where $f$ just ignores the argument $x$)?
I'm probably cheating and squeezing in another question here, but is there an intuition for why this form of composition seems to be the more fundamental one in combinatory logic?

I'm not familiar with the "strong" terminology. However, the 'obvious' answer to the other question is that it both duplicates the $x$ argument and exchanges the relative positions of (one copy of) the $x$ and $g$ arguments:
$$\mathsf s\ f \ g\ x = f\ x\ (g\ x)$$
The other combinator it's usually paired with:
$$\mathsf k\ x\ y = x$$
discards an argument. Together, this is all three of the structural rules for a variable context (contraction, exchange, weakening), and it includes composition as well.


Proof for BFS and DFS equivalence I'm trying to prove (by induction) that BFS in equivalent to DFS, in the sense that they return the same set of visited nodes, but I'm stuck in the middle of some of the cases.

Let $G$ be a directed graph and $u \in V(G)$.

We want to prove that $  BFS(G,u) = DFS(G,u)$.

$\text{BASE CASE}$

$V(G) = \{u\}$

$BFS(G, u) = \{u\} \quad DFS(G,u) = \{u\}$

$BFS(G,u) = DFS(G,u) \quad Qed.$

$\text{INDUCTIVE HYPOTHESIS}$

$BFS(G,u) = DFS(G,u) \;\;\forall G, u \in V(G)$.

$\text{INDUCTIVE STEP}$

$(i)\;G' = (V(G) \cup\{v\}, E(G))$

We know that $BFS(G',u) = BFS(G,u)$ if $u \ne v$ (and so does $DFS$), because $v$ is disjoint from the rest of the graph, and so the proof follows from the hypothesis.

But if $u = v$ ?

$(ii)\;G' = (V(G), E(G) \cup (v,w)) \quad v,w \in V(G)$

How can I use the hypothesis here?

There is not much hope in proving $BFS(G,u) = DFS(G,u)$ directly by mathematical induction on the number of nodes in $G$ or on the degree of $u$. The problem is that as an induction hypothesis that equality does not capture the "right" kind of information or cover the "right" cases that are useful for the induction step.
Approach one: the explicit description as reachable nodes
Instead, you can try proving separately that each side is equal to the set $R$ of reachable nodes from $u$, that is, $R=\{v\in V(G)\mid \mbox{ there is a directed path from } u \mbox{ to } v \}$. More specifically,
$$R=\{u\}\cup\left\{v\in V(G)\mid \mbox{ there exist } u_0, u_1, \cdots,u_n \text{ such that }u_0=u, u_n=v, u_i\in V(G) \text{ for } 0\le i\le n \text { and }(u_i,u_{i+1})\in E(G)\text{ for } 0\le i\lt n\right\}$$
You can prove the case of $DFS$ by mathematical induction on the total number of nodes of $G$. You can prove the case of $BFS$ by mathematical induction on the distance of $v$ to $u$. Or use whatever as you see fit.
Approach two: the characterization as nodes closed under neighbourhood
A set of nodes $S$ is said to be closed under neighbourhood if for any node $n$, $S$ contains the adjacent nodes of $n$. That is, if $n\in G$ and $(n, m)\in E(G)$, then $m\in S$. Here are the critical observations on both $BFS$ and $DFS$.
Lemma 1. $DFS(G,u)$ is closed under neighbourhood.
Proof: It becomes obvious once we check what $DFS$ does when it discovers a new node.
Lemma 2. $BFS(G,u)$ is closed under neighbourhood.
Proof: It becomes obvious once we check what $BFS$ does when it pops out a node from the queue.
Lemma 1 and 2 suggest us to consider the minimal set of nodes that contains $u$ and closed under neighbourhood. Name it $C(G,u)$. It is enough to prove that both $BFS(G,u)$ and $DFS(G,u)$ are equal to $C(G,u)$. We have shown both contain $C(G,u)$. It is easy to verify "the set of nodes visited so far are contained in $C(G,u)$" is an invariant of $BFS$ on $G$ starting from $u$. The same hold for $DFS$.


When are two CFG's different? If two CFG's differ only in what names they use for their non-terminals, are they different?

For example, are these CFG's different:
$$\begin{align*}
S &\to A  \\
A &\to a \end{align*}$$
and
$$\begin{align*}
S &\to B  \\
B &\to a
\end{align*}$$

Two grammars $G_1 = \langle \Sigma, V_1, S_1, P_1 \rangle$ and $G_2 = \langle \Sigma, V_2, S_2, P_2 \rangle$ are

weakly equivalent if $L(G_1) = L_(G_2)$
strongly equivalent if $L(G_1) = L_(G_2)$ and for every string $w$ in the language, the minimal left-most derivations of $w$ in $G_1$ and the minimal left-most derivations of $w$ in $G_2$ are exactly the same in number, and can be put in one-to-one corresponce (note that the number of derivation trees must be the same in number if the grammars are ambiguous, i.e. they must be ambiguous "in the same way")

Example:

$G_1 = S \to A; A \to 1B; A\to 1; B\to 0A$; we have $L(G_1) = \{ (10)^*1 \}$

$G_2 = S \to B; B \to A1; B\to 1; A\to B0$; we have $L(G_2) = \{ 1(01)^* \}$

isomorphic if there is a bijection $\phi : V_1 \to V_2$ such that $\phi(S_1) = S_2$ and $\phi(P_1) = P_2$ (after extending $\phi$ to productions and set of productions in the natural way).

Note that weakly equivalence is undecidable, while strongly equivalence (and ismorphism) are decidable.

As a final remark I think that - in most formal language contexts - it would be fine to say that the grammars in your question are the same grammar :-)


Is the set of context free grammars that generate all words in co-RE? Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.

For $A = \{\langle G \rangle \mid L(G) \neq \Sigma^\ast\}$ this procedure, returns "yes" iff there is a word $w \notin L(G)$ for a given grammar  encoding $\langle G \rangle$ and never halts otherwise:

Assume the input encodes a context-free grammar $G$. Otherwise, accept the input if it is not an encoding of a context-free grammar. (Note, however,  that we can always assume that every string encodes some dummy grammar, e.g. $(\{S\}, \{a\}, \{S \to \varepsilon\}, S)$).
Convert $G$ in Chomsky normal form $G'$.
For each $w \in \Sigma^\ast$:
Check whether there exists a derivation in $G'$. Note that for a grammar in Chomsky normal form a derivation of a word $w$ has length $ \leq 2 |w|$, so you only have to check finitely many for each word. If such an derivation does not exists, return "yes", otherwise continue with next word.

Thus, $A$ is recursively enumerable and $A^C = \{\langle G \rangle \mid L(G) = \Sigma^\ast\}$ is co-RE.


Height of AVL tree with balance condition of 2 The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed imbalance condition between two child nodes would be 2), how could I find the maximum height of such a tree. Would I need to solve some kind of recurrence relation or fibonacci sequence. Is there an easier way of figuring out the maximum height of a tree with a balance condition of 2 by using what we already know? Thanks.

Let $T_h$ denote the minimal number of nodes that a standard AVL tree of height $h$ could have.
If $h>0$, then there's the root and two subtrees. One of the subtrees must have height $h-1$. The other must have height at least $h-2$, otherwise it's not a valid AVL tree. So we have the recurrence:
$$T_h = T_{h-1} + T_{h-2} + 1$$
And we can throw in $T_0 = 0$ and $T_1 = 1$ for obvious reasons.
The easy way to solve the recurrence is to denote $F_h = T_h + 1$. Then:
$$\begin{align*}F_0 & = 1 \\ F_1 & = 2 \\ F_h & = F_{h-1} + F_{h-2}\end{align*}$$
That is, they're Fibonacci numbers with the sequence offset by 3.
Since:
$$F_h \approx \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{h+3}$$
Inverting this, we get:
$$h \approx \frac{1}{\log \left( \frac{1 + \sqrt{5}}{2} \right)} \log \left( T_h \right) + 3$$
And that is where the 1.44 comes from.
So what you need is to solve the recurrence:
$$U_h = U_{h-1} + U_{h-3} + 1$$
with suitable initial conditions.
If you can't think of a clever way to do this, you can do it the not-clever-but-always-works way by observing that:
$$\begin{bmatrix} U_h \\ U_{h-1} \\ U_{h-2} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \begin{bmatrix} U_{h-1} \\ U_{h-2} \\ U_{h-3} \\ 1\end{bmatrix}$$
Therefore:
$$\begin{bmatrix} U_{h+2} \\ U_{h+1} \\ U_{h} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}^{h} \begin{bmatrix} U_{2} \\ U_{1} \\ U_{0} \\ 1\end{bmatrix}$$
Next, perform eigendecomposition on the matrix. Let:
$$M = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}$$
Suppose you can find a matrix $Q$ and a diagonal matrix $\Lambda$ such that $M = Q \Lambda Q^{-1}$. Then:
$$M^h = Q \Lambda^h Q^{-1}$$
Taking the power of a diagonal matrix is trivial, and this should give you a closed form. You will then need to find an approximate inverse to solve your problem.


Calculating time complexity of a code which may be incorrect I am a sophomore taking a course in algorithm analysis. We were asked by our professor to calculate time-complexity of several C functions, but some of them were incorrect and would result in a compile error. As far as I know time complexities of correct algorithms are calculated and then we choose which one to implement. We tried to discuss this with her but she insisted on solving those problems nevertheless stating that it doesn't matter whether the code gets executed or not.

Is there a way one can realise that the algorithm is incorrect after finding it's time complexity?

Does it make sense calculating time complexity for an incorrect program?

PS :

1) The program wasn't implementing any proven algorithms, it was just some loops.

2) This may sound like a silly question, but my professor got me confused.

Downvotes are welcome but please give your opinion.

On a more practical level, it sounds like this probably just stems from a typo on the instructor's part. If this is in the context of a big-O exercise, I'd just fix the typos and move on. Instructors do make mistakes too!

Getting a bit more abstract, if a program won't run, it doesn't really make sense to speak of its time complexity because it has no runtime.

Getting even more abstract - you actually can use big-O analyses to show that certain pieces of code cannot be correct. For example, suppose someone proposes a new comparison-based sorting algorithm. If you do a big-O analysis and see that it runs in time O(n) in the worst case, you are guaranteed that the code has to be wrong because of the requirement that all comparison-based sorting algorithms run in time $\Omega(n \log n)$ on average. This is different than talking about code that won't even compile, but it does show that analyzing the time complexity of incorrect (here, legal but wrong) code may be worthwhile.


Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1? I'm interested in creating a graphs whose vertices are strings, and whose edges represent the relation of having an edit distance of 1 under a given string metric.

An obvious approach is to make all $\frac{n^2-n}{2}$ comparisons among the $n$ vertices, giving us $O(n^2)$ time complexity.

Excluding parallelizing the comparisons, is there a better algorithm in terms of time complexity?

I'm interested in string metrics where strings of different length are allowed.

In the worst case any such algorithm will work $\Omega(n^2)$ because your graph can have $\Omega(n^2)$ edges.

By the way, are you interested in some particular string metric?


What's the error in the following proof of the halting problem decidability? Let's encode every state and tape word (with position of Turing machine on it) with a single integer. Then the transition function can be represented as a total function from integers to themselves. Now let's apply any known algorithm for searching a cycle in the chain of pointers to that function and we've got it!

P.S. Sorry, it's late night question... The proof has to be complete nonsense :-)

A Turing machine may run forever without ever entering any kind of cycle. (Consider the machine which always just moves its head to the right.)


Is It Possible For a Data Structure to Have Constant Time Access/Insertion/Deletion? I'm trying to come up with a data structure that could access, insert, and delete any element in constant time. I know that's pretty difficult, but I'm just doing it to invoke thought and understanding about computer science. However, I'm starting to question whether it is even possible.

My theory is: For access to be in constant time, the data would need to be stored in a static location (like an array). And for insertion/deletion to be in constant time, the data would need to be stored dynamically using pointers or some sort of lookup table (like a linked list). Therefore, no data structure can have all three operations run in constant time.

Is this reasoning correct?

EDIT:

access(index): returns element at given index

insert(element, index): Inserts element into 'index' and shifts everything after 'index' right one index

delete(index): Removes element at 'index' and corrects indexes so that there are no gaps (i.e. shifts everything after 'index' left one index)

How do we get lower bounds?

As D.W. noted, lower bounds are hard. But that doesn't mean that no progress can be made. To get a lower bound, it is required (well, not strictly, but you won't get very far without one) that you make a (possible restrictive) model of all algorithms or data-structures that can solve your problem.

For example, the $\Omega(n\log n)$ lower bound for sorting holds only for the restrictive 'comparison based sorting' algorithms. (this is why counting sort can 'beat' this time in some cases: it isn't comparison based)

Lower bounds for data structures

For the case of data-structures, the cell-probe model seems a good place to start. This model is similar to the more common RAM-model, but can be useful for lower bounds as it 'only counts' the number of accesses to stored data (i.e. the number of 'probes' to a cell).

For example, in the paper by Yao that introduces this model, lower bounds are calculated for the data structure supporting INSERT, DELETE and MEMBER (test for membership) queries. I think that a similar technique could work for your data-structure as well.

Do note that the paper by Yao is a bit outdated. I mostly mentioned it because the problem it considered is relatively simple and similar to yours. More modern techniques are covered in the dissertation of Kasper Green Larsen.


Finding a function which is a mapping reduction of A to B How do I precisely define the function which is a mapping reduction of A to B for the following examples?

What is the process of figuring this out?

Given: A and B are languages over the alphabet {0,1}.

Examples:

A is the language described by 1*0*, B is the language described by 01*0*
A={w | the length of w is even}, B={w | the length of w is odd}
A=B={w | the length of w is even}
A={0,1}*, B={00,1,101}

I am studying this material and I am not sure of how to 'precisely' define these functions. Could somebody provide me with solutions and a methodology to finding the solution?

The answers are as follows, just functions with input w:

f(w) = 0w
f(w) = 0w
f(w) = w
f(w) = 00

Basically make sure all scenarios which occur in A are mapped to B and that all which are not, do not map to B


Is there a greedy algorithm to solve the assignment problem? The assignment problem is defined as:

There are n people who need to be assigned to n jobs, one person per job. The cost that would accrue if the ith person is assigned to the jth job is a known quantity C[i,j] for each pair i, j = 1, 2, ..., n. The problem is to find an assignment with the minimum total cost.

There is a question asking to design a greedy algorithm to solve the problem. It also asks if the greedy algorithm always yields an optimal solution and for the performance class of the algorithm. Here is my attempt at designing an algorithm:

Am I correct in saying that my algorithm is of O(n^2)? Am I also correct in saying that a greedy algorithm does not always yield an optimal solution? I used my algorithm on the following cost matrix and it is clearly not the optimal solution. Did I Do something wrong?

The answer of your post question (already given in Yuval comment) is that there is no greedy techniques providing you the optimal answer to an assignment problem.

The commonly used solution is the Hungarian algorithm, see

Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955

for the original paper.

Otherwise your solution seems correct to me, and as usually with greedy algorithms, it will provide you a feasible solution which you may hope to not be "too far" from the global optimal solution.


Computation Tree Logic and its Temporal Opeators I've got some questions about the temporal operators in computation tree logic:

Does the Finally path-specific quantifier Fq mean that q has to hold in a subsequent state or is it also fulfilled when q holds in the current state?
Please consider the following example:

What exactly is specified here? Does it mean: If q AND r holds on a path P in a graph G then q has to hold somewhere on the subsequent path of P.
Or does it mean: ... q has to hold somewhere on the subsequent path of every path of G?

First, a small comment - the $F$ operator comes from the word "future", rather than "finally", although it is indeed very tempting to say "finally".

The semantics of $Fq$ with respect to a computation $\pi$ is:
$$\pi\models Fq \iff \exists i\ge 0, \pi^i \models q$$
Thus, the 0th suffix is also considered, so if $q$ hold immediately, the formula is still satisfied.
Observe that you can capture the notion of "strict future" with the formula $XFq$.
The formula states that along every path ($A$), every state $s$ satisfies ($G$) the following: if $q$ and $r$ are true in $s$, then in every path starting from $s$, $q$ eventually appears.

I think this is what you meant in your second option.


Doron ZEILBERGER's P = NP computer proof In 2009 Doron has published a paper stating "Using 3000 hours of CPU time on a CRAY machine, we settle the notorious P vs. NP problem in the affirmative, by presenting a “polynomial” time algorithm for the NP-complete subset sum problem.". I've been looking for other people's opinions on this but I haven't found anything significant. Has this problem been officially settled? is this a correct solution? I am not able to assess the paper because of my limited knowledge. What do you guys think ?

Paper : http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/pnp.pdf

That paper is a hoax. If you look, it just throws numbers around for a huge polynomial bound, purports to solve a problem by "Laurent polynomials" without any clue on how they relate to the problem, shifts to integrals and estimates them by numerical means "sufficiently precisely" (and that is supposed to give the huge degree polynomial somehow). And nowhere are the 3000 hours of CRAY time to be seen.


Negation of the semantics of the Until operator in LTL I have been looking at the Until operator and the release operator and when introduced to the release operator it was suggested that it is equivalent to:

$\phi R \psi \equiv \neg(\neg\phi U \neg \psi)$

But when trying to get from the semantic definition of the Until operator to the semantic definition of the Release operator by negation I get stuck part way. Specifically, I get stuck trying to negate a $\forall j < i$ expression as I will show below.

So the semantic definition of Until:

$\pi \models \phi U \psi \iff \exists i \geq0, \pi[i] \models \psi \land \forall j\leq i-1, \pi[j]\models \phi$

Putting the negations in:

$\pi \models \neg(\neg\phi U \neg\psi) \iff \neg(\exists i \geq0, \pi[i] \models \neg\psi \land \forall j< i, \pi[j]\models \neg\phi)$

$\iff \forall i \geq 0, \neg(\pi[i]\models\neg\psi)\lor \neg(\forall j < i,\pi[j]\models\neg\phi)$

$\iff \forall i \geq 0, (\pi[i]\models\psi)\lor (\exists j < i,\pi[j]\models\phi)$

In words, I am ending up with globally $\psi$ or globally there always exists some predecessor that satisfies $\phi$. Which cannot be correct as $\pi[j]$ is not defined when $i=0$.

The semantic definition for the release operator that I was aiming for is:

$\pi \models \phi R\psi \iff (\exists i\geq 0, \pi[i]\models\phi \land \forall j\leq i, \pi[j]\models\psi)\lor (\forall k \geq 0, \pi[k] \models \psi)$

So I have part of the expression correct ($\forall k \geq 0, \pi[k] \models \psi \equiv \forall i \geq 0, (\pi[i]\models\psi)$), but I am really stumped about how to get the second part or where I went wrong.

Any help enlightening me is greatly appreciated!

Thanks!

First, note that you did not really get the "first part the the expression correct". The first formula is, roughly, of the form

$$
\forall i, (p(i) \lor q(i))
$$
while the second one is of the form
$$
r \lor (\forall k, p(k))
$$
Note the different bracketing.

That being said, you have two definitions for the semantics of the release operator, and you want to prove them equivalent. So far, you tried to manipulate those formulae according to standard logical rules (a correct approach), but failed to do so. Indeed, as far as I can see, that approach can not succeed. The nice news is that you do not need to use that approach: in order to prove that definition $A$ and $B$ are equivalent, you can also write two distinct proofs, one for $A \implies B$ and one for $B \implies A$. In writing such proofs, you can leverage all the known results from mathematics, not just those allowing formula manipulation.

In your specific case, you will need to use the well-ordering property of natural numbers, stating that any non-empty set of naturals must have a least element. Let me sketch a part of the proof.

Assume your first definition, and let's prove the second one.
We consider two cases.

If $\pi[k] \models \psi$ for all $k$, then the second definition is trivially true.
Otherwise, $\pi[k] \not\models \psi$ for some $k$. This means that the set of natural numbers $\{k|\pi[k] \not\models \psi\}$ is not empty, hence has a least element -- let $m$ be that element. This means that $m$ satisfies $\pi[m] \not\models \psi$, and that (minimality) $\forall n<m, \pi[n] \models \psi$. Now, using the hypothesis, we can obtain that $\exists j<m, \pi[j]\models\phi$. From this and minimality we obtain the thesis.

Note that you still need to prove the other direction.


What's non-algorithm-specific I am reading the paper "Understanding Random SAT beyond the Clauses-to-Variables Ratio" and at beginning of the page 2 say

  the hardest region corresponds exactly to a phase transition in a non-algorithm-specific theoretical property of the instance

I am a Spanish speaker.  Can you help to understand what means "non-algorithm-specific theoretical property of the instance".

The phrase is explained by the rest of the passage.  I'll give a larger excerpt of the paper for context.

  A seminal paper by Selman, Mitchell and Levesque considered the empirical performance of DPLL-type solvers running on uniform-random SAT instances.  It found a strong correlation between the instance's hardness and the ratio of the number of clauses to the number of variables in the instance. Furthermore, it demonstrated that the hardest region (e.g., for random 3-SAT, a clauses-to-variables ratio of roughly 4.26) corresponds exactly to a phase transition in a non-algorithm-specific theoretical property of the instance: the probability that a randomly-generated formula having a given ratio will be satisfiable.

The non-algorithm-specific property is the probability that a randomly-generated formula having a given clauses-to-variables ratio will be satisfiable.  While the perceived hardness of a particular instance will vary depending on the algorithm used to solve it, the probability that a randomly generated SAT instance is satisfiable does not change if you use different SAT solvers.  Yet these two properties are somehow linked.

An example of an algorithm-specific property would be the apparent hardness of pigeon-hole problems encoded as SAT instances.  It's been proven that deciding the unsatisfiability of such instances requires exponentially long proofs in the resolution proof system, and thus exponentially long runtimes of solvers implementing that system.  However, a solver that implements a simple procedure to break the symmetry of such instances (such as forcing a specific ordering of the pigeons in the holes) allows unsatisfiability to be decided in polynomial time.