# Question
Title: A relational algebra extended to model the full DML ("CRUD") domain
There are multiple references about the relational algebra for modeling queries (`SELECT`) but I have found very very little on the expanded algebra that would include concepts in all of DML such as `INSERT`, `UPDATE`, `DELETE` and maybe even `MERGE`, `DECLARE`, `SET` (as defined by MS SQL Server, whenever I must choose). I'm looking for information about such an expanded algebra to help me reason about DML operations.

I assume that MS SQL Server, for example, must have some meta-domain model and/or type system that helps it validate SQL Scripts. Here are a few of SQL SERVER 2008's `SYS.MESSAGES` (issued for scripted DML operations) that suggest to me violations of a *type* or *domain-rule* nature, not syntactic:

```
286 - The logical tables INSERTED and DELETED cannot be updated.
417 - TOP is not allowed in an UPDATE or DELETE statement against a partitioned view.
10729 - A nested INSERT, UPDATE, DELETE, or MERGE statement is not allowed in a SELECT statement that is not the immediate source of rows for an INSERT statement.
354 - The target '%.*ls' of the INSERT statement cannot be a view or common table expression when the FROM clause contains a nested INSERT, UPDATE, DELETE, or MERGE statement.
4005 - Cannot update columns from more than one underlying table in a single update call.

```

The database engine is compiling and analyzing the scripted commands it is given and emitting these messages in response to violations against its domain.

An engine executing this following statement isn't merely tacking on something trivial to the join of `Table1` and `Table2`. Beyond what it needed to `SELECT`, for the `UPDATE` it has to track more information throughout the statement such as the actual tables that `ColB` and `ColC` in the resulting join came from so that 1) it knows that they are from the same table (Error #4005) and 2) so it can actually write the results to somewhere permanent (not just a local transformation of the join):

```
UPDATE Table2
SET
    ColB = Table2.ColB + Table1.ColB,
    ColC = 3
FROM Table2
INNER JOIN Table1 ON Table2.ColA = Table1.ColA
WHERE Table1.ColX < 100

```

I've never used jOOQ, but the documentation suggests to me an uncommon level of sophistication/understanding compared to software with similar goals. It apparently includes a fluent-style API for DML, and assuming that some of the library's value is in its ability to detect certain errors at compile-time, this suggests to me a decent domain model of DML. Are jOOQ developers breaking ground with new and proprietary ways of understanding DML operations or is there published research into DML/CRUD types that they're implementing? I'm so far overwhelmed trying to reverse-engineer the domain models from an implementation but I cannot find such a pure reference.

What is the domain model that is behind DML engines like SQL Server's script execution engine or softwares like the jOOQ library enabling them to understand/analyze DML scripts? For sql statements, relational algebra gives mathematical concepts of views, selections, projections, various joins, aggreggations, windowing, grouping, pivoting and each concept has type calculus that it dictates. (Perhaps that a *selection* over a view yields a view of the same type with equal or fewer elements, that join takes two views and a join condition and yields a view of tupled elements, etc). There are several implementations including Linq-To-SQL, Entity Framework which support (to varying degrees of competency) an alternate encoding and code translation of queries. I assume that those softwares are grounded in the domain model of relational algebra. But what would be the same basis for a library that supports full DML reasoning?

Thanks!

# Answer
Excellent question, and since you referred to us ("jOOQ developers", which I am - working for the company behind jOOQ), I feel qualified to give a partial answer.

### A bit of historic context first

Since the very beginning of software, there had been:

* Theory (which is what "Computer Science", i.e. this Stack Exchange subsite is about)
* Practice (more like Stack Overflow, i.e. *"how can I get the compiler to stop barking at me"*)

The origins of set theory, relational algebra, and relational calculus were clearly on the theoretical side. Up to this day, popular RDBMS implementations have only managed to approximate this theory, mostly through SQL.

Although there had been competing languages before SQL was standardised mainly by Oracle and IBM, the power of SQL lay in the fact that it was a very *practical* language, which worked sufficiently well both for computer programs (e.g. written in COBOL, which was an equally *practical* language), software engineers, and most importantly: "other people", including analysts, project managers, and also managers. Everyone can quickly write up a `SELECT * FROM person WHERE first_name = 'John'` query. More theoretical languages like QUEL, which would have been closer to relational calculus, lacked the business vision that Oracle had.

Since then, SQL has emancipated from the outdated relational model and embraced a lot of alternative models, including procedural extensions (stored procedures), OLAP features, XML, JSON, etc. Not all of these enhancements were very well executed. To this day, the XML integration, for instance, is rather weak, poorly standardised and hard to grasp. I'm just speculating that the ANSI/ISO/IEC SQL standards committee and the w3c didn't work together closely enough to truly embed XQuery into SQL at the time. Unfortunately for w3c, as hardly anyone is using XQuery today, while everyone still uses SQL.

The historic irony here is that a lot of innovation came from academia, and I'd like to specifically mention Michael Stonebraker (Quel, Ingres, the original Postgres, Vertica, H-Store, and much more) who was recently awarded with the well-deserved turing award. Stonebraker has always been innovating into new areas. Most of the recent in-memory column store "hype" (also often referred to as "NewSQL") evolved around him. Stonebraker is a good example of the difference between academia and business. We've blogged about this some time ago here:

When you hear the excellent talks by Oracle's Andrew Mendelsohn for instance, or other influencers from companies like Microsoft, SAP, IBM, you will notice that business has always embraced SQL for very good reasons, which were often not at all academic.

### Context for your question

You have to differentiate between around four levels of abstraction:

1. Relational calculus
2. The SQL standard
3. The SQL Server specification
4. The SQL Server implementation

Your example is a particularly interesting one, because `UPDATE .. SET .. FROM` is not part of the latest SQL:2011 standard. To our knowledge, the `UPDATE .. FROM` clause is supported in at least:

* SAP HANA
* Ingres
* Postgres
* SQL Server
* Sybase

Other databases allow for updating views, e.g.

* `UPDATE t1 JOIN t2 ON ... SET ...`
* `UPDATE (SELECT * FROM t1 JOIN t2 ON ...) SET ...`

In terms of *Codd's Rules*, the following two would apply:

> **Rule 6**: The view updating rule:
>
> All views that are theoretically updatable must be updatable by the system.
>
> **Rule 7**: High-level insert, update, and delete:
>
> The system must support set-at-a-time insert, update, and delete operators. This means that data can be retrieved from a relational database in sets constructed of data from multiple rows and/or multiple tables. This rule states that insert, update, and delete operations should be supported for any retrievable set rather than just for a single row in a single table.

So, Codd demands that an RDBMS can update views using sets, but he wouldn't want to specify *how* to actually do that (e.g. syntax-wise).

In fact, the concrete rules which apply to these kinds of statement are rather different from database to database. This has nothing to do with the SQL language, or with relational calculus per se, but simply with the individual implementations of each database - often also because of how the locking / concurrency model is implemented - something that is left open to implementations by both Codd's Rules as well as to some extent by the SQL standard. For instance, the standard does not explicitly refer to MVCC.

In the particular case of `UPDATE .. FROM`, think of it this way (assumptions only):

1. Some customer probably wanted to be able to write `UPDATE` statements that take into account more than one table
2. Some database vendor then implemented a "reasonable" syntax that fits into the general feeling of writing SQL
3. Some other database vendor then copied this syntax in order to provide migration paths, but "improved" on syntax and/or semantics
4. Yet another database vendor (probably IBM or Oracle) came up with yet another, much more powerful syntax for such use-cases, namely `MERGE`
5. As that database vendor has closer ties to the ANSI/ISO/IEC standards committee, and as this syntax was clearly more useful, `MERGE` now became a standard, and is now implemented in more and more RDBMS. To our knowledge in at least:

* CUBRID
    * DB2
    * Firebird (upcoming 3.0 only)
    * HSQLDB
    * Informix
    * Oracle
    * SQL Server
    * Sybase SQL Anywhere

### Answer to your questions

> Are jOOQ developers breaking ground with new and proprietary ways of understanding DML operations \[...\]?

We're not really breaking ground here. Before jOOQ, there had been many many SQL parsers and translators / migrators that allowed for standardising *some* vendor-specific SQL features. One example is Gudu Software's SQL Parser \- the use case being migrating off DB2 towards Oracle, for instance.

What's new in jOOQ is that we introduced another "SQL dialect" implemented directly in Java, which mimicks a bit of the SQL standard and a bit of popular vendor-specific SQL dialects. Since jOOQ users explicitly create an Abstract Syntax Tree in their Java programs by using jOOQ API, jOOQ can easily perform a lot of SQL transformation internally in order to standardise the generated SQL output for all currently supported ~20 RDBMS, without the need to previously parse SQL statements (which is extremely hard). This extends to DML statements only to a certain degree, of course, as the underlying database implementation still needs to be able to process the semantics of a given statement.

What's also new (or at least different) in jOOQ is that unlike HQL, JPQL, LINQ, and many other abstractions, jOOQ is sticking to SQL instead of embedding also other concepts / domains like objects (ORMs) or XML/Collections (LINQ)

> Or is there published work on this?

jOOQ is not academic work. It evolved from real user needs over the past 6 years. We're following SQL here as we want to follow real business needs. We're not aware of third-party publications about jOOQ, although there had been a lot of similar papers about other, similar APIs in the past:

Embedding an external language like SQL in Java is rather easy, though. The basic technique is published in our article

> I'm so far overwhelmed trying to reverse-engineer the domain models from an implementation.

So are we :-)

As you can see, SQL is a very real-world, pragmatic, sometimes (often) a bit ugly, vendor-specific (although well standardised), huge thing. The SQL:2011 standard's main document has almost 1500 pages, including DML (you can find some publicly available draft document versions here, for free). This doesn't even include extensions like XML, the `INFORMATION_SCHEMA` or other extensions.

Most people I've talked with in the past would agree that we really need something better than SQL. But the ugly truth is, there is nothing better than SQL right now, and even if there were, it would have to be backwards-compatible. There is no way that our whole industry will stop using the excellent and huge tool-chain that has been built around SQL. If "NoSQL" databases want to be successful these days, they build SQL-esque langauges (e.g. Cassandra with CQL, Couchbase with N1QL, Neo4j with Cypher). Oracle shows that SQL-on-Hadoop (BigDataSQL) is possible, and SAP's HANA completely bypassed NoSQL and implemented their number-crunching in-memory database directly on top of SQL.

The flip-side of this focus on practicality is that the academic quality of something like `UPDATE .. FROM` deteriorates to a point where you simply shrug and accept that this is merely a useful, perhaps a bit weird SQL statement.

### TL;DR

If you want to understand the individual error messages that your SQL Server instance displays to you, then you're probably best off learning about SQL Server first. These concrete, real-world problems are so far away from the original theory ("Codd's Rules", "Tutorial D") that you'll be much better off bypassing the theory for these cases.
> 8 votes

---
Tags: database-theory, databases, relational-algebra
---


title: Enumerating connected subgraphs

text:
# Question
Title: Enumerating connected subgraphs
Is there an efficient algorithm to visit/enumerate all unique connected subgraphs of a labelled graph?

E.g., when the graph is a path, $v\_1v\_2\dots v\_N$, there are $N(N-1)$ unique connected graphs: for any $1\leq i\<j\leq N$, the subgraph $v\_i\dots v\_j$. For graphs with denser edge structure, the number of unique connected subgraphs can be as high as $2^{|V|}$ (for cliques).

Fortunately, graphs I'm interested in have a lot of articulation points, so the total number of unique connected subsets should be polynomial in the size of the input.

For those who are interested, I'm modeling a problem in protein mass-spectrometry. Starting from a protein (chain of amino acids, with occasional long-distance bonds due to disulphide bonds), I'd like to generate a database of all possible sub-species that may result from breaks in peptide and/or disulphide bonds.

# Answer
> 0 votes
As explained in enumerating all connected induced subgraphs (on TCS.SE), there is an algorithm whose running time is polynomial in the number of connected subgraphs. Therefore, if you know that the number of connected subgraphs is polynomial in the input size, there is an algorithm that is polynomial in the size of the input. The polynomial might be fairly high degree, so I don't know whether the algorithm will be efficient in practice, but you could try it out and see.

See also https://stackoverflow.com/q/15658245/781723.

---
Tags: algorithms, graphs, enumeration
---


# Question
Title: Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge
A test is consisted of $N$ multiple choice questions, each has $k$ possible answers.

A test solution is the sequence of answers $S\in\[k\]^N$.

Given is a black box which receives a solution as input and returns the number of correct answers. After failing a test, the student may take the test again, and the questions do not change.

In order to pass the test, a student must have at least $m\le N$ correct answers.

---

* **What is the minimal number of attempts you need to make (as a function of $N,k$ and $m$) in order to be sure to pass the test, assuming you have no knowledge about the questions in hand?**
* **Assuming you are allowed to use randomization, how can we minimize the expected number of attempts needed?**

---

A trivial algorithm is to "guess" an initial solution $S\_0$, and then change one answer at a time until you have $m$ correct ones. This results in $1+(k-1)\cdot m$ attempts at the worst case.

For the probabilistic part, it seems some kind of an experts algorithm could work here: pick a few random tests and then construct additional tests such that answers appearing in high-scoring solutions will get higher probability.

# Answer
Here is an algorithm to identify the answers with successive attempts.

It has a worst case complexity of $O(m(1+\log\_2 k))$

This corresponds roughly to collecting in each attempt one bit of information on the right answer, for each question in succession.

Of course we cannot do that, because we can only give one whole answer per question. So the trick in to transpose the problem, by identifying k correct answers and trying to find their questions.

Apologies for the rough presentation. I am running out of time.

# The algorithm

We assume, to simplify the presentation, that $N\geq k$. But it does not really matter. We also assume that $k=2^p$ for some positive integer $p$, again to simplify the presentation.

We assume that the only result of an attempt $T\in \[1,k\]^N$ is a score $s(T)$ corresponding to the number of correct answers. The individual answers for each question are noted $T\[j\]\in \[1,k\]$ for the answer to question $j$, ($j\in \[1,N\]$), in attempt $T$.

We define $T\_i=i^k1^{N-k}, \forall i\in\[1,k\]$

The $N-k$ last answers always contribute the same amount $r$ to the result $s(T\_i)$ since they do not change.

Together, the first $k$ answers of all $k$ attempts will produce $k$ good answers, distributed in some way over all $k$ attempts, since for each question there is exactly one good answer among the $k$ being proposed.

If one attempt has 2 good answers, or more, for one of the first $k$ questions, then another must have 0. Thus, if the scores $s(T\_i)$ are not all equal, the smallest is equal to $r$. Furthermore, if they are all equal, then they are all equal to $r+1$. So the value of $r$ is easily determined.

## We first assume $\exists r\in\[0,N-k\],\\; \forall i\in\[1,k\],\\; s(T\_i)=r+1$

This implies that each attempt has exactly 1 good answer among the first $k$ answers (to the first $k$ questions). But we do not know which.

We define a second set of $k-1$ attempts $T\_i'=i^{k/2}1^{N-k/2}, \forall i\in\[1,k\]$

Note, that $T\_1'=T\_1$, so that k-1 new attempts only are needed, but the duplication makes things simpler to explain.

If the good answer $1$ in the first $k$ questions in $T\_1$ was for one of the first $k/2$ questions, then $1$ is a bad answer for questions $Q\_j,\\; \forall j\in\[k/2+1,k\]$. Hence all the $T\_i$ attempts that had a good answer for one of these $k/2$ questions will lose 1 point in score, thus falling to $r$. All other attempts, that had a good answer in the first $k/2$ questions will have an unchanged score $r+1$.

If the good answer $1$ in the first $k$ questions in $T\_1$ was for one of the last $k/2$ questions, i.e. for questions $Q\_j,\\; \forall j\in\[k/2+1,k\]$, then all attempts $T\_i'$ benefit from that good answer $1$. Those that had a good answer for the first $k/2$ questions will keep it and see their score increase from $r+1$ to $r+2$, while the others will lose their good answer as before, but have it replaced by the good answer $1$ for one question, thus keeping the score $r+1$.

Thus we can conclude that, if some score decrease, then the firat attempt $T1$ has a good answer $1$ in one of the first $k/2$ questions, and if some increase it is in one of the next $k/2$ questions. Forall other attempts $T\_i'$, those with the higher score have a good answer for one of the first $k/2$ questions, and those with the lower score have a good answer in one of the next $k/2$ questions.

Recall that $k=2^p$, i.e. $p=\log\_2 k$.

If we number the first $k$ questions in binary, starting from 0, we can see that this is a way to determine the $p^{th}$ bit of the index question that is correctly answered by some attempt $T\_i$.

If for some $i\>1$, the score decrease from $T\_i$ to $T\_i'$, then $T\_1$ has a good answer for a question $Q$ such that the $p\_{th}$ bit of its binary index is $0$, while it is $1$ for an increase. For the other attempts $T\_i$, those with the higher score for $T\_i'$ have a good answer for a questions with the index $p^{th}$ bit $0$, and the lower scores have a good answer for a questions with the index $p^{th}$ bit $1$

It is then quite simple to repeat the procedure identically for each of the other bits of the binary index of the first $k$ questions.

That makes $p=\log\_2k$ series of $k-1$ attempts, in addition to the first $k$ attempts, that is a total of $k+(k-1)\log\_2k$ attempts, to get the first k answers.

However we can improve a bit on that count. We do $\log\_2 k$ attempts to identify the question associated with each answer, i.e. each index $i\in \[1,k\]$. Actually we need to identify only $k-1$ such question. The last one in necessarily the one that was not found yet.

Thus in the above algorithm, we do not need to compute $T\_{k}'$, nor any of the other attempts of index $k$, except for the first $T\_k$ in the first attempts of the algorithm. Since it is also unnecessary for $T\_1'$ and similar, we only need, at most $\log\_2k$ series of $k-2$ attempts, in addition to the initial $k$ attempts, that is a total of $k+(k-2)\log\_2k$ attempts, to get the first k answers.

But this relied on the assumption that each of the first $k$ attempts has exactly one good answer for the first $k$ questions. What if that is not the case?

## One of the first $k$ attempts had more than one good answer in the first $k$.

Then there is at least one attempt, say $T\_h$ that failed on the first $K$ questions, which means that answer $h$ is wrong for the first $k$ questions.

Actually there may be several such attempts caracterized by the fact that they have the same smallest score $r$. They can all be discounted as containing no information for the first $k$ questions, other than the fact that their index is not the answer to these questions.

Futhermore, for any attempt $T\_i$, we know that it has $s(T\_i)-r$ correct answer $i$ in the first $k$ questions.

If there is only one answer, it can be identified with the previous binary technique using $\log\_2k$ attempts, given that we can replace half the answers (as specfied by a bit in their binary index) by $h$ which is known to be wrong (which makes thing simpler than previously).

If there are two correct answers, the same technique is used with a small variation. The binary approach is used again for both answers together, until one of the attempts separates them by indicating a bit $0$ for one answer and a bit $1$ in the same position of the question binary index for the other answer. From then on, one answer can be hidden by using the answer $h$ in the questions corresponding to that index, while the binary search is resumed for the other answer. Once that answer has identified its question, it is replaced by the answer $h$ that is wrong so that the search can be resumed for the question of the second answer.

The same technique can be used independently of the number of answers, progressively splitting them until only one is searching for its question, then replaced by wrong answer $h$ when its question is found, so that another can be searched, and so on.

Since the splitting and searching is based on the bits of the binary indexes of questions, it is quite clear that this costs never more than $\log\_2 k$ for each question to be associated with one of the $k$ answers.

So the cost in number of attempts for identifying the questions for the first $k$ answers (I am deliberately inverting the view) is not more than $k\log\_2 k$, to be added to the first $k$ attempts. It might be a bit less with a finer analysis.

However we can again use the fact that each question has necessarily an answer, so as to skip the binary search on one line of answers (i.e., one answer number).

First recall that we simply ignore all answer numbers that correspond to no answer. Then we also set aside the answer number that corresponds to the largest number of questions for which it is the right answer. This corresponds by hypothesis to at least two good answers.

Then we determine the corresponding question for all other identified good answers, at most $k-2$ of them, with a cost that is at most $\log\_2 k$ for each. The correct answer set aside can then be assigned to all questions that have not been identified as associated with another answer.

This makes for a total cost of at most $(k-2)\log\_2k$ attempts, to be added to the initial $k$ attempts, thus again a total of $k+(k-2)\log\_2k$ attempts, to get the first k answers, as in the first case.

## Overall

The cost of this algorithm, mesured in number of attemps, is bounded by $k(1+\log\_2 k)-2\log\_2 k$ for identifying the $k$ answers to $k$ questions (as the above could have been done for any set of $k$ questions.

So for $m$ questions, assuming for simplicity that $m$ is a multiple of $k$, the total cost is bounded by $m/k$ times that cost, i.e. $m(1+\log\_2 k)-(2m/k)\log\_2 k$.

Apparently the total number $N$ of questions does not matter. But the last questions are not considered with this technique, except to identify their global effect to factor it out. We do not take advantage of the fact that some groups of question-answer pairs might be easier to identify (because their costs can be factored, for example). Possibly this could help for the worst case analysis with a different technique that would identify patterns of answers that are easier to analyze, but there might be a cost in finding them.

Regarding purely asymptotical complexity: this algorithm is $O(m\log\_2k)$
> 3 votes

# Answer
You can produce an information-theoretic lower bound by viewing the problem as a decision tree. At each step, you try some solution and get a response (0..$N$) of how many answers were correct, which leads to your next guess.

## Simple case: $m=N$

Your decision tree ends with a solution that is entirely correct, and every possible solution must be represented as a leaf of the tree. Since there are $k^N$ possible solutions, and each decision branches with $N+1$ possible results, we end up with a lower bound of $\log\_{N+1} {k^N} \approx N \log\_N(k)$ guesses.

## General case: any $m \leq N$

In this case, it is not necessary for every leaf in the decision tree to be different, but any one solution may be used at most $k^{N-m}$ times; this is because one solution can only have $\geq m$ correct answers for ${N \choose M} k^{N-m}$ different arrangements of answers. In other words, there must be at least $\frac{k^m}{N \choose m}$ distinct leaves in the decision tree, yielding a lower bound of $\log\_{N+1} \left({\frac{k^m}{N \choose m}}\right) = m \log\_{N+1} {k} - \log\_{N+1} {N \choose m}$ guesses (although there is a minimum of one guess).

## Upshot

An overall (non-constructive) lower bound is $\max(1,m \log\_{N+1} {k}- \log\_{N+1} {N \choose m})$ guesses. If $N$ is very large compared to $m$, this bound is trivially 1. If $m$ is large, then this is roughly $m \log\_m (k)$, which is a bit smaller than @babou ’s solution.
> 3 votes

---
Tags: combinatorics, probability-theory, randomized-algorithms
---


# Question
Title: Proof that CFL aren't closed under intersection using synchronous parallel (N)PDA composition
It is well known that the class of CFLs is not closed under intersection as follows e.g. from the following example: $$L\_1 \cap L\_2 = \left\\{ a^mb^mc^n \mid m,n \ge 1 \right\\} \cap \left\\{ a^mb^nc^n \mid m,n \ge 1 \right\\} = \left\\{ a^ib^ic^i \mid i \ge 1 \right\\} \not \in \mathcal{L\_2},$$ where $L\_1,L\_2 \in \mathcal{L2}$.

I was wondering if this could be proven using the synchronous parallel composition of two (non-deterministic) PDAs, or rather what is wrong with the following construction which seemingly comes to the opposite conclusion:

> Let $PDA\_1, PDA\_2, PDA\_{1,2}$ be, WOLOG, (non-deterministic) PDAs accepting by final state and with total transition functions: $$ PDA\_1 = \Big(Q\_1, \Sigma\_1, \Gamma\_1, \delta\_1, q^0\_1, \gamma^0\_1, F\_1 \Big) \\ PDA\_2 = \Big(Q\_2, \Sigma\_2, \Gamma\_2, \delta\_2, q^0\_2, \gamma^0\_2, F\_2 \Big) \\ PDA\_{1,2} = \Big(Q\_1 \times Q\_2 \cup \big(q\_{\emptyset}, q\_{\emptyset}\big), \Sigma\_1 \cup \Sigma\_2, \Gamma\_1 \times \Gamma\_2, \delta\_{1,2}, \big(q^0\_1, q^0\_2 \big), \big(\gamma^0\_1, \gamma^0\_2 \big), F\_1 \times F\_2 \Big)$$ where $q\_{\emptyset} \not\in Q\_1 \cup Q\_2$ and $\delta\_{1,2}$ is defined as follows: $$ \delta\_{1,2} \Big(\big(q\_1, q\_2 \big), a, \big(\gamma\_1, \gamma\_2 \big) \Big) = \begin{cases} \Big(\big(q'\_1, q'\_2 \big), \big(\gamma'\_1, \gamma'\_2 \big) \Big) & \big(q'\_1, \gamma'\_1 \big) \in \delta\_1 \big(q\_1, a, \gamma\_1 \big) \land \\ & \big(q'\_2, \gamma'\_2 \big) \in \delta\_2 \big(q\_2, a, \gamma\_2 \big) \\ & \text{(if such transitions are defined)} \\ \Big(\big(q\_{\emptyset}, q\_{\emptyset} \big), \big(\gamma\_1, \gamma\_2 \big)\Big) & \text{otherwise} \\ \end{cases} $$

Surely $PDA\_{1,2}$ accepts only words from the intersection of languages $L(PDA\_1)$ and $L(PDA\_2)$. Why doesn't it accept all of them?

# Answer
This doesn't work, because the stacks of the two PDAs aren't synchronized. You can get to a state where $\text{PDA}\_1$ pushes a symbol but $\text{PDA}\_2$ pops a symbol. What is $\text{PDA}\_{1,2}$ supposed to do at that point? It's screwed.

The product construction would work if there was a guarantee that the length of the stack of $\text{PDA}\_1$ was always the same as the length of the stack of $\text{PDA}\_2$ -- but as explained, this is not guaranteed.

Another way to put it: Your definition of $\delta\_{1,2}$ does not make any sense. The output is supposed to be an element of $Q \times \Gamma^\*$, where here $\Gamma = \Gamma\_1 \times \Gamma\_2$. However, a pair like $(\lambda'\_1,\lambda'\_2)$ is not an element of $(\Gamma\_1 \times \Gamma\_2)^\*$. If the length of $\lambda'\_1$ was the same as the length of $\lambda'\_2$, you could interpret $(\lambda'\_1,\lambda'\_2)$ as an element of $(\Gamma\_1 \times \Gamma\_2)^\*$: it is the string whose $i$th symbol is $(\lambda'\_1\[i\],\lambda'\_2\[i\])$. Unfortunately, when the length of $\lambda'\_1$ is different from the length of $\lambda'\_2$, there's no way to interpret $(\lambda'\_1,\lambda'\_2)$ as an element of $(\Gamma\_1 \times \Gamma\_2)^\*$. Consequently, your definition of $\delta\_{1,2}$ is not well-formed: it does not have the proper type signature.

As you quite accurately summarize the situation: One stack can grow ad infinitum while the other not and in order to access the previous element from the shorter stack, the PDA would need to indestructibly go through the potentially infinitely long stack. This could be fixed if we had an automaton with two separate stacks; however, such an automaton would be computationally equivalent to a Turing machine and thus is more powerful than a PDA (which only has one stack).
> 4 votes

---
Tags: context-free, automata, closure-properties, pushdown-automata
---


# Question
Title: Find a sequence of integer powers faster than the naive algorithm
Let $k\in \mathbb{N}$ be fixed. The naive way to compute a sequence of values $a\_1^k,\ldots,a\_n^k$ where $a\_i\in \mathbb{N}$ for all $1\leq i\leq n$ is compute $a\_i^k$ individually with the exponentiation by squaring. This takes a total of $O(n\log k)$ multiplications.

Is this optimal? What if for each $a\_i$, we have $\frac{1}{c} a\_i \leq a\_{i+1}\leq c a\_i$.

I come up with this question because I was doing a binary search over $f(n)=n^k$.

# Answer
In the worst case, this seems to be optimal. If your $a\_i$ are pairwise coprime, e.g. $k$ different primes, they powers do not share any factors.

Of course, if $k$ is large but $c$ from your proposed restriction is small, there may not be such a set; then, you powers share factors. You *could* exploit this if you knew the shared factors for your $a\_i$; but finding those is harder than just computing all the powers.

So I daresay, no, you can not do this faster without more knowledge about the $a\_i$.
> 1 votes

---
Tags: algorithms, arithmetic
---


title: Bipartite Matching in the Plane

text:
# Question
Title: Bipartite Matching in the Plane
I'm currently working on a problem that I came across:

> You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have to Suggest an $O(n^{3})$ time algorithm for determining if there is a perfect matching between them, with the constraint that each point in $R$ is matched to a point in $B$ point whose distance is at most 1 unit away.

I have tried solving using the minimum distance using bipartite algorithm but could not arrive at a solution. Can anyone provide me with any ideas?

# Answer
This problem has been solved by Alon Efrat, Alon Itai and Matthew J. Katz in their paper Geometry Helps in Bottleneck Matching and Related Problems. The running time of the algorithm is $O(n^{1.5} \log n)$.
> 3 votes

# Answer
Using existing algorithms, you solve this with a basic network flow approach.

First construct a bipartite graph from the point sets where every point is a vertex in the graph and there is an edge between points $x$ and $y$ if $x\in R$, $y \in B$ and $d(x,y) \leq 1$. This takes $\mathcal{O}(n^{2})$ time.

Then we can apply the normal bipartite perfect matching algorithm, which uses a *Maximum Flow* approach:

* Add a source vertex $s$ and sink vertex $t$.
* Add all edges $su$ where $u \in R$.
* Add all edges $vt$ where $v \in B$
* Assign all edges a capacity of $1$ unit.

Then we have a flow network which has a flow of $n$ units if and only if there's a perfect matching between $R$ and $B$. Thus we can use any Max Flow algorithm we care to, but in particular the augmenting path algorithm, in this case, runs in time $\mathcal{O}(|V|\cdot|E|)$, which is at most $\mathcal{O}(n^{3})$.

Of course we can use any faster algorithm, and still answer the question positively.
> 2 votes

# Answer
In time $O(n^2)$, you can construct a bipartite graph that has an edge from $r\in R$ to $b\in B$ if, and only if, they're at distance at most $1$ from each other. Then, use any standard algorithm for matchings of bipartite graphs: even the simplest ones run in time $O(n^3)$.
> 1 votes

---
Tags: algorithms, computational-geometry, bipartite-matching, matching
---


# Question
Title: Period of a pseudo-random sequence generated using an LFSR
I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR). I have read from many sources that the length of the pseudo random sequence generated from the LFSR would be maximum if and only if the corresponding feedback polynomial is primitive.

I have tried to generate the pseudo random sequence for the primitive polynomial (4,1,0) (corresponding to polynomial $x^4 + x + 1$) by tapping at bits 4 and 1, and it has resulted in a sequence with a period of $2^4$ - 1 = 15. Similarly I have tried primitive polynomial given by (3, 1, 0) (corresponding to polynomial $x^3 + x + 1$) by tapping at bits 3 and 1 and it has resulted in a sequence of period $2^3$ - 1 = 7.

When I tried to apply this same logic to the primitive polynomial (5, 2, 0) (corresponding to polynomial $x^5 + x^2 + 1$) it yields a sequence with period 15. While it should have yielded a sequence with period 2^5 -1 = 31. Following is the circuit diagram for (5, 2, 0)

1) What is the exact procedure to convert the given polynomial into a maximal length LFSR?

2) How do I determine the correct tap bits for a given polynomial?

# Answer
The LFSR that you give is really of length $4$ rather than $5$, since $b\_1$ never gets used. The correct way to implement a "Fibonacci" LFSR is explained in the Wikipedia article: $b\_1$ should be the *leftmost* bit rather than the *rightmost* bit.

There is also an alternative kind of LFSR knows as a "Galois" LFSR, also described in Wikipedia, which is dual to a Fibonacci LFSR: at each point, the contents of the register is shifted, and if the bit which is shifted out is 1, then a mask is XORed to the contents. In both types of LFSR, the resulting sequence has maximum period iff the feedback polynomial is primitive.

---

The polynomials that you give as examples are known as *trinomials*, polynomials with three non-zero monomials. Not all trinomials are primitive. There are algorithms for deciding whether a trinomial, or any other polynomial, is primitive. As far as I know, there is no explicit construction of primitive polynomials.

How do we test whether a given polynomial $P$ of degree $n$ is primitive? The first step is verifying that it is irreducible. The second step verifies that $x^{(2^n-1)/p} \not\equiv 1 \pmod{P}$ for every prime divisor $p$ of $2^n-1$ – this step requires factoring $2^n-1$. A list of primitive polynomials can be found on Wikipedia.
> 3 votes

---
Tags: algorithm-analysis, pseudo-random-generators, random-number-generator
---


# Question
Title: Do compression tables exist and where are they used?
Let's take the zip compression for example, from what scraps I can gather on the Internet, the 2 major simplified ways it works is by looking for arrangements of bits that repeat throughout the file, and by compressing certain bit orders.

So for example, we have 010111111111110101

A zip file would look something like:

```
x = 0101

x|repeat(1,8)|x

```

So the zip compression creates its own table of arrangements that it finds.

But, is there anything that already uses a predetermined table? For example you'd have a table like:

```
x = 010101010101010101010110010101010101010101010101...
y = 10101...
...

```

And then I'd download a file that follows this compression table, without having to download the table because you already have it.

So my question is, is this method used anywhere, and why or why not?

# Answer
> 2 votes
The big advantage of Lempel-Ziv-style compression is that

* it creates its own dictionary on the fly and
* tailors it to the data. Therefore, they are
* *general-purpose* compression algorithms which
* can be used without having to keep dictionaries in sync; all you need for decoding is the encoded file and the algorithm.

If you fix a dictionary, this is going to perform well for *some* inputs. For instance, you can order all English words by frequency in some corpus, number them and store a sequence of these numbers instead of the words themselves. This will then work very well for English texts similar to your corpus, worse for other texts, and not well at all for weather data or images.

Note that LZ-style compression is used in popular formats such as (g)zip, PNG and GIF.

FLAC is one noteable format that uses something different, namely linear predictors. In a certain sense, you can view this as a fixed (though conceptually infinite) dictionary; the method estimates parameters of a certain model and represents bits of data by these parameters (plus some error information). This works well because the model fits the kind of data (apparently) very well, and the representatives are significantly smaller than the data itself. However, the decoder only knows the model; there is no fixed set of parameters everybody uses. So I don't think this fits your idea, either.

---
Tags: algorithms, data-compression, algorithm-design
---


# Question
Title: FM-index and pattern search with wildcards
in one of my algorithm courses i'm studying the FM-Index.

In one of the exercise I'm trying to do I was asked to give a procedure to search patterns of the form `w*` (where `*` indicates any character) using backwards search (see here).

How could this be possible? It seems to me that the algorithm already returns all the possible patterns of the form `w*` (because the starting range in which the search start is $0 - |T|$).And what kind of modification requires the procedure to search pattern in which for example one char is `*`, for example `www*ww`?

# Answer
> 2 votes
You are correct that w\* is already addressed by fixed-substring search. I'll give some pointers on general regex search; most text indexes can be searched for variable patterns with a bit of extra work.

First, backwards search is a consequence of the fact that the FM index and most full text indexes use suffix sorting with the most significant digit on the left, because virtually no one thinks in terms of prefix sorting with the MSD on the right. If the latter were used the FM index would use forward search; it's simply a product of the choices made when setting up the data structure. Another fact to note is that regex's can be reversed, so any pattern in the forward direction can be reversed and applied using backward search.

Search with wildcards is not hard to do, but it requires multiple branches through the wildcard matches, which must be searched through some sort of tree-traversal strategy, with backtracking and so on. This paper describes pattern-matching on Patricia trees for instance.

It's not that different from searching sequential text; in the FM index case you can always find the characters immediately preceding the matches found so far and determine if they match the pattern correctly.

---
Tags: algorithms, search-algorithms, strings
---


# Question
Title: Most Efficient Method To Determine Triangle Fill Values Based On Corner Values
I have a triangle and the value of the pixel intensity at each of the three corners of the triangle. I want to interpolate to find interpolated pixel intensities for a set of points inside the triangle. How can I do this?

The method I've tried is to do an value determination based on the distance of that fill-in point from each of the corners.

As an example, here is a single triangle example, with three points described in the format of (Value, X, Y), though in practice all values might be floating point.

```
(1.78, 2337, 1955)
(2.95, 2342, 1948)
(1.12, 2347, 1941)

```

# Answer
> 1 votes
One very simple approach is to use a linear model. Let $I(x,y)$ be the pixel intensity of the pixel at coordinates $(x,y)$. We can fit to a linear model:

$$I(x,y) = \alpha x + \beta y + \gamma,$$

where $\alpha,\beta,\gamma$ are parameters to be determined. If we are given the pixel intensity at each corner of the triangle, then we know the value of $I(x,y)$ for each corner point $(x,y)$. Since a triangle has 3 corners, this gives us 3 linear equations in 3 unknowns. We can solve this system of linear equations to find $\alpha,\beta,\gamma$, and then use this linear model to fill in the value of all other points.

In particular, if the $i$th corner is at $(x\_i,y\_i)$ and has pixel intensity (value) $v\_i$, then we get a system of three equations:

$$\begin{align\*} I(x\_1,y\_1) &= v\_1\\ I(x\_2,y\_2) &= v\_2\\ I(x\_3,y\_3) &= v\_3 \end{align\*}$$

Expanding the linear model, this becomes

$$\begin{align\*} \alpha x\_1 + \beta y\_1 + \gamma &= v\_1\\ \alpha x\_2 + \beta y\_2 + \gamma &= v\_2\\ \alpha x\_3 + \beta y\_3 + \gamma &= v\_3 \end{align\*}$$

Here we have three unknowns ($\alpha,\beta,\gamma$) and the rest are known constants. So, we can solve this system of linear equations for $\alpha,\beta,\gamma$. This involves inverting a $3 \times 3$ matrix and then multiplying it by a $3$-vector, so it should be relatively efficient.

Once you have derived the parameters $\alpha,\beta,\gamma$, you can now evaluate the value $I(x,y)$ at any other point $(x,y)$ in the triangle (or on its interior). This lets you interpolate the value at each fill-in point.

The approach I described above works for black-and-white images. If you have a color image, you can interpolate independently for each of the 3 channels (R, G, and B; you might get better results if you work in a transformed color space, e.g., HSV, CIELAB, CIECAM02).

I recommend you take a look at barycentric coordinates, as they simplify the formulas for interpolation in a triangular mesh.

If you are familiar with interpolation for image processing, bilinear interpolation is a slight generalization of this approach, where you add a $\delta xy$ term to the linear model. However, bilinear interpolation isn't applicable here, because it requires 4 points: 3 points isn't enough.

It's possible to come up with more sophisticated interpolation models. For instance, you could fit a linear model to more than 3 points (e.g., taking the corner points of all adjacent triangles as well), and use ordinary least squares linear regression to find a best-fit linear model, weighting the corners of the adjacent triangles lower than the corners of the target triangle. You could also build generalizations of bicubic interpolation, etc.

---

More generally, I recommend that you do a bit of research on "tetrahedral interpolation", as I believe that is the catch-phrase for the kind of problem you are asking about (or the generalization of it to 3 dimensions).

---
Tags: algorithms, computational-geometry, graphics
---


# Question
Title: What is practical difference between NP and PSPACE-complete?
Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing.

Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\\,\neq\\,$NP, PSPACE$\\,\neq\\,$NP etc. this means that there are NP-complete problems that cannot be solved in polynomial time on a DTM. Which means that either they have some complexity that lies between polynomial and exponential (which I am not sure what that might be) or they must take exponential time on a DTM (and no more than polynomial space). If its the latter, then consider the PSPACE-complete problems. A problem is in PSPACE if it can be solved using a polynomial amount of space. Since NP$\\,\subseteq\\,$PSPACE$\\,\subseteq\\,$EXPTIME, PSPACE-complete problems must also take exponential time on a DTM. Then what is the practical difference between NP-complete and PSPACE-complete problems?

# Answer
I think it depends on what you're interested in. If you're looking for an exact solution to a problem and you hear that it's either NP-hard or PSPACE-hard, then in either case you won't be able to find an algorithm for that problem that is simultaneously worst-case efficient, deterministic, and always correct unless P = NP or P = PSPACE. Therefore, if you're just looking for whether the problem is efficiently solvable in all cases, both NP-hardness and PSPACE-hardness probably means that you're out of luck.

However, if that's not the lens you're looking through, then (based on the suspicion that NP ≠ PSPACE) there's a difference between NP-completeness and PSPACE-completeness. If a problem is NP-complete, then even if you can't solve the problem efficiently, you can still check "yes" answers efficiently. On the other hand, if NP ≠ PSPACE and you have an instance of a PSPACE-complete problem you're convinced has a "yes" answer, there might not be any efficient way to convince someone else of this.

Hope this helps!
> 15 votes

# Answer
The main practical implication is that PSPACE-complete problems are probably even harder than NP-complete problems.

With NP-complete problems, you at least have some small hope to solve them with a SAT solver, an ILP solver, or with other methods. With PSPACE-complete problems, a SAT solver or ILP solver probably won't work (at SAT can only express problems in NP; PSPACE-complete problems cannot be formulated as an instance of SAT), and many other methods for dealing with NP-completeness are less likely to work.

If you're interested in "practical" approaches to PSPACE-complete problems, this site has some resources for solving some PSPACE-complete problems... though you shouldn't necessarily expect it to be as effective as SAT solvers have been for NP-complete problems, given that PSPACE-complete problems are believed to be harder than NP-complete problems.
> 8 votes

---
Tags: complexity-theory, np-complete, complexity-classes
---


# Question
Title: Contraint with three variables into three binary constraints
I'm having a hard time tackling the following problem (perhaps some key data is missing). We have a constraint:

$A+B= C$

One is supposed to represent this one constraint using three binary constraints. Is this even possible? No domain is given, but even if it was, I really don't see how this could be achieved...

# Answer
Good question. Your instinctive reaction is quite valid: if you stick with the variables $A,B,C$, there is no way to introduce some set of binary constraints that will be equivalent to $A+B=C$ (where each constraint is only allowed to mention two of $A,B,C$).

The trick is to introduce new variables, or change the set of variables. If you do that, it can be done. For instance, see the reference that hengxin suggests: http://ktiml.mff.cuni.cz/~bartak/constraints/binary.html. However, it would be understandable if you feel that this is in some sense "cheating"... which might be why you didn't think of this approach.
> 3 votes

# Answer
agreed there is not enough info. please clarify. lacking that here is one interpretation; your ref may be using "+" to refer to binary OR ($\vee$), this is common in many refs. then we have the table

```
a + b = c
0   0   0
0   1   1
1   0   1
1   1   1

```

leading to a truth table (x is true iff the eqn A + B = C holds)

```
a b c x
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

```

this can be encoded as four binary constraints but not fewer (proof exercise for reader):

$(A \vee B \vee \bar{C}) \wedge (A \vee \bar{B} \vee C) \wedge (\bar{A} \vee B \vee C) \wedge (\bar{A} + \bar{B} + C)$

however introducing auxiliary (free) variable D one can write using 3 boolean constraints:

$(C \vee \bar{D}) \wedge (\bar{A} \vee D) \wedge (\bar{B} \vee D)$

background: this is basically the same construction used in the Tseitin transform (exercise for reader to show the correspondence).
> -1 votes

---
Tags: constraint-satisfaction
---


# Question
Title: What is the order of this traversal method?
Please see below pseudo-code for finding the max-height of a b-tree

```
maxDepth()
1. If tree is empty then return 0
2. Else
     (a) Get the max depth of left subtree recursively  i.e.,
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e.,
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,
                             max depth of right subtree)
                             + 1
     (d) Return max_depth

```

My guess is that this is `post-order traversal`.

Because we are calculating the height of the left tree and then the right tree and in the end, we find the max(left\_tree\_height, right\_tree\_height) to figure out the max height of the root node.

# Answer
This is a depth first recursive binary tree traversal.

Such a traversal may be qualifed as pre-order, in-order, or post-order if you do some specific action on each node, before the first recursive call, between the two recursive calls, or after the second recursive call.

Actually, you can have several actions to perform, some in pre-order, some in in-order, and some in post-order.

In your case, you have to collect and combine the information from the two subtrees, and that is necessarily in post-order. But it is just using terminology, which I see as moderately meaningful in this context.

These concept often suppose an order of the daughters of a node, but this is largely irrelevant here. You can process your subtrees in any order, left first or right first. I guess that is also why I am a bit reluctant to make this postorder distinction. The pre-order, in-order, post-order distinction assumes you are exploring depth first from left to right.

They also correspond to distinct linear notations for representing binary trees, where nodes are labeled differently from leaves: prefix, infix and postfix.
> 2 votes

---
Tags: algorithms, terminology, trees, binary-trees, graph-traversal
---


title: Learning a small disjunction

text:
# Question
Title: Learning a small disjunction
I have a boolean function $f: \\{0,1\\}^n \to \\{0,1\\}$ that I know takes the form

$$f(x\_1,\dots,x\_n) = x\_{i\_1} \lor x\_{i\_2} \lor \dots \lor x\_{i\_k},$$

but I don't know the values of $i\_1,\dots,i\_k$. I am given many pairs $(x,f(x))$ for random values of $x$ (chosen uniformly and independently at random).

I'm looking for an efficient algorithm to recover $i\_1,\dots,i\_k$, given this information. How efficiently can this be done? How many pairs are needed? Randomized algorithms are OK. I'm particularly interested in the regime where $k \ll n$.

This is similar to the learning juntas problem, but it might be much easier. With the learning juntas problem, we know that $f(x\_1,\dots,x\_n) = g(x\_{i\_1},\dots,x\_{i\_k})$ but neither $i\_1,\dots,i\_k$ nor $g$ are known. Here, we know $g$ and know that it is a disjunction, so it seems like the problem might be much easier.

I can see an information-theoretic lower bound: $\Omega(k \lg n)$ pairs are needed. There are ${n \choose k}$ possible candidates for $f$, and each pair gives us only one bit of information about $f$, so we need at least $\lg {n \choose k}$ pairs; for small $k$, ${n \choose k} = \Theta(k \lg n)$. How close to this can one get?

This is motivated by an application in inferring input-output relationships in programs (black-box taint analysis).

# Answer
> 2 votes
$\Theta(2^k \lg n)$ queries are necessary and sufficient.

## Algorithm

Define $I = \\{i\_1,\dots,i\_k\\}$. Our goal is to recover $I$. Given $x$, define $Z(x) = \\{i : x\_i = 0\\}$. For each $x$ where $f(x)=0$, we learn that $Z(x) \subseteq I$. This suggests the following algorithm:

* Set $J := \\{1,2,\dots,n\\}$.
* For each $x$ in the input such that $f(x)=0$, set $J := J \cap Z(x)$.
* Output $J$.

Analysis: It's guaranteed that this algorithm will output a set $J$ satisfying $I \subseteq J$. Can we ensure that $I=J$? Well, if we have $c \lg n$ values of $x$ where $f(x)=0$, then for any fixed $j \notin I$, $\Pr\[j \in J\] \le 1/2^{c \lg n} = 1/(2^c n)$; then by a union bound, $\Pr\[J \ne I\] \le 1/2^c$. So, the probability that this produces the wrong output can be made exponentially small in $c$, as long as we have $c \lg n$ values of $x$ where $f(x)=0$.

Moreover, given $m$ pairs, we expect $m/2^k$ of them to have $f(x)=0$. So, if we have $c \cdot 2^k \lg n$ pairs, we expect $c \lg n$ where $f(x)=0$. Therefore, $O(2^k \lg n)$ pairs suffice to ensure that this algorithm will give the correct answer (except with negligible probability of failure).

## Lower bound

This is the best we can do. We can extend the information-theoretic lower bound in the question.

Let's start by showing that $\Omega(2^k)$ pairs are needed. For a random $x$, we have $\Pr\[f(x)=0\] = 1/2^k$. Therefore, we obviously need $\Omega(2^k)$ pairs to have a good chance of observing at least one pair where $f(x)=0$. With $o(2^k)$ pairs, there's an overwhelming probability that all pairs satisfy $f(x)=1$, in which case we have learned nothing about $f$. So, $\Omega(2^k)$ pairs are needed.

We can improve this lower bound a bit. Call $x$ *good* if it satisfies $f(x)=0$. Suppose we have to examine $p$ pairs before we see the first good value of $x$. Once we see our first good value of $x$, how many bits of information have we learned about $f$? Only $\lg p$ bits (because one of those $p$ pairs yields 0 and all the rest are 1; there are $p$ ways to select one of them to be 0). It takes about $2^k$ pairs to see the first good value of $x$. So, after observing $2^k$ pairs, we expect to learn about $k$ bits of information about $f$. In general, each good value of $x$ gives us about $k$ bits of information about $f$, and we need to see about $2^k$ pairs per good value obtained. Now as described in the question, we need $\Omega(k \lg n)$ bits to specify $f$ uniquely. Therefore, we need $\Omega(\lg n)$ good values of $x$, so we need $\Omega(2^k \lg n)$ pairs in total.

This gives a lower bound that matches the performance of the algorithm above, to within a constant factor. Therefore, the algorithm above is asymptotically optimal.

---
Tags: algorithms, machine-learning, boolean-algebra, propositional-logic, learning-theory
---


# Question
Title: Printing the array elements sorted by repetition
I just can't figure this question out:

Given an array of N elements, its values range are from 0 to 100. Write a function that prints the array's elements sorted by repetition.

Time complexity : O(N)

---

For example: Array: \[20,60,10,80,100,0,20,20,30,35\]

The function should print: 20 20 20 60 10 80 100 0 30 35

# Answer
Hint: Use some arrays of length 100, and the fact that 100 is a constant.
> 1 votes

---
Tags: algorithms, sorting, arrays
---


# Question
Title: Could min cut be easier than network flow?
Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a minimum $(s,t)$-cut is no more than the complexity of computing a maximum $(s,t)$-flow.

Could it be less? Could there be an algorithm for computing a minimum $(s,t)$-cut that is faster than any max-flow algorithm?

I tried finding a reduction to reduce the $(s,t$)-max-flow problem to the $(s,t)$-min-cut problem, but I wasn't able to find one. My first thought was to use a divide-and-conquer algorithm: first find a min-cut, which separates the graph into two parts; now recursively find a max-flow for the left part and a max-flow for the right part, and combine them together with all of the edges crossing the cut. This would indeed work to produce a maximum flow, but its worst-case running time might be as much as $O(|V|)$ times as large as the running time of the min-cut algorithm. Is there a better reduction?

I realize the max-flow min-cut theorem shows that the complexity of computing the *value* of a max-flow is the same as the complexity of computing the *capacity* of a min-cut, but that's not what I'm asking about. I'm asking about the problem of finding a max-flow and finding a min-cut (explicitly).

This is very closely related to Compute a max-flow from a min-cut, except: (1) I'm willing to allow Cook reductions (Turing reductions), not just Karp reductions (many-one reductions), and (2) perhaps given $G$ we can find some graph $G'$ such that the min-cut of $G'$ makes it easy to compute the max-flow of $G$, which is something that's out of scope for that other question.

# Answer
Here is a possible approach:

Suppose you know the cut S, then finding the flow from $S$ to $t$ is a min cost network flow problem with zero cost, since you know exactly the outflow at each vertex in $V\setminus S$ and in the inflow at $t$. Suppose $f$ denotes an $S-t$ flow and $A$ the node-arc matrix (i.e. row $i$, col $j$ has 1 if $i$ is the tail of $j$, -1 if its the head, zero otherwise), and let $b$ be such that $Af = b$ if $f$ satistfies the supply/demand, and the flow conservation. Then with gaussian elimination we can find a feasible solution in $|V|^3$ operations.

To find a cut from a flow we need to construct the residual graph which takes at most $|E|$ time, and then potentially traverse $|V|$ vertices.

So for complete graphs and the minimum cut being just the source or just the sink, the reduction takes equal time in both directions worst case. However, I would think that finding a feasible solution to $Af =b$ can be done faster than $|V|^3$ given the special structure. I am not sure how to prove that though.
> -1 votes

---
Tags: complexity-theory, reductions, network-flow, graph-algorithms
---


# Question
Title: Computing the k shortest edge-disjoint paths on a weighted graph
Looking for k shortest paths that do not share edges. i.e if the paths were represented as sets of edges, their intersection has to be empty.

We could use Dijkstra to find the 1st "disjoint" (edge unique) shortest path from the origin to all vertices. However, to naively find the 2nd disjoint path, one would need to create $|V|$ versions of the graph, each one with a specific set of set of edges missing, corresponding to a path that was discovered with the original Dijkstra results.

Is there a more computationally efficient method to find the $k$ shortest, edge disjoint paths? Even a heuristic would help me.

Edit:

I think this article posted by Raphael is exactly what I need to $k=2$ but I would like to support a great k if possible, up to 4. One more thing, I don't understand the following instruction:

> Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex

What does "equivalent to two oppositely directed arcs" mean? What does replacing an edge with a single arc directed towards the source vertex mean?

https://en.wikipedia.org/wiki/Edge\_disjoint\_shortest\_pair\_algorithm

Wait, the problem with the above algorithm is that it doesn't lessen the complexity. It is just as efficient as running Dijkstra twice for each pair of vertices. I'm looking for a better way to get the k disjoint shortest paths between each $v\_i$ and $v\_j$

# Answer
A comment by D.W. makes a lot of sense (it would do in general but it does in this specific case since there are many different variants of the same problem). Hence, in my response I just refer to a few variants of the same problem (which contain descriptions of various algorithms):

Usually, the term $k$ shortest edge-disjoint paths is plainly interpreted as follows:

> Given a graph $G$ and $k$ pairs of distinct vertices $(s\_i, t\_i)$, $1 \leq i \leq k$, find whether there exist $k$ pairwise disjoint shortest paths $P\_i$, between $s\_i$ and $t\_i$ for all $1 \leq i \leq k$.

And this is taken from the paper you pointed to: Tali Eilam-Tzoreff. The disjoint shortest paths problem. Discrete Applied Mathematics. Volume 85, Issue 2, pp 113--138. 1998.

This problem is known to be NP-hard for arbitrary values of $k$ but the authors actually provide a polynomial algorithm for the case of $k=2$ with positive edge-costs.

In this variant, there is no interest in minimizing any particular metric. The best result, to the best of my knowledge, refers to Directed Acyclic Graphs (DAGs) and $k=2$:

Torsten Tholey. Linear time algorithms for two disjoint paths problems on directed acyclic graphs. Theoretical Computer Science, 465:35–48, 2012

However, the oldest formulation I know of this problem actually considers the minimization of a specific metric:

> Given a directed graph G containing $n$ vertices, one of which is a distinguished source $s$, and $m$ edges, each with a non-negative cost, find a pair of edge-disjoint paths from $s$ to $v$ of minimum total cost.

This problem is known to be a special case of minimum-cost network flow, and there is a brilliant, splendid, beautiful and amazing algorithm for solving it with $k=2$: Suurballe's algorithm.

Another variant that has received some attention imposes a limit on the number of edges (and these are known as *Length Constraints*):

> Given a graph $G$ compute a pair of disjoint paths between nodes $s$ and $t$ of an undirected graph, each having at most $K$ edges.

Again, this problem is known to be NP-complete: Spyros Tragoudas and Yaakov L.Varol. Graph-Theoretic Concepts in Computer Science, volume 1197 of Lecture Notes in Computer Science, chapter Computing disjoint paths with length constraints, pages 357–389. Springer Verlag Heidelberg, 1997.

Approximation algorithms have been developed also for this particular variant. See: Longkun Guo. Frontiers in Algorithmics, volume 8497 of Lecture Notes in Computer Science, chapter Improved LP-rounding Ap- proximations for the k-Disjoint Restricted Shortest Paths Problem, pages 94–104. Springer International Publishing, 2014.

In all these works (but the first two ones), the authors refer to shortest paths but watch out what D.W. is asking in his comment: this is not to find the minimum number $m$ of shortest paths from which a set of $k$ shortest paths could be extracted such that they do not share any edge. In general, the computation of these $k$ shortest paths refer to an additional metric. For example, Tragoudas and Varol consider the minimization of the maximum length and Guo introduces the minimization of an additional parameter, $delay$.

Summarizing, there are many variants of the same problem, Suurballe's minimizes the sum of the cost of the pair of paths, others consider the minimization of the longest path (Tragoudas and Varol), and this is known as a min-max version but also max-min versions exist and this is just in case a metric is used. If not, it depends whether you impose limits or not on the length of the paths and other cases. All of them, however, are known to be exponentially hard.

I would like to end just by pointing out that I am not aware of any generalization of A$^\*$-like search algorithms that deal with this problem. I think that can be definitely an interesting line of research.

Hope this helps,
> 3 votes

---
Tags: algorithms, graphs, shortest-path, weighted-graphs
---


# Question
Title: Algorithms that are using John's ellipsoid
The Lowner–John ellipsoid is a minimum volume enclosing ellipsoid of some convex body $K$. This ellipsoid is unique (as is the maximum volume ellipsoid contained in $K$). I'm looking for algorithms based on those ellipsoids, or any significant practical use that requires finding them explicitly.

# Answer
Rimon and Boyd use Lowner–John ellipsoids in their "...method for estimating the distance between a robot and its surrounding environment".

From the abstract:

> First, approximate the detailed geometry of the robot and its environment by minimum-volume enclosing ellipsoids. ... Then compute a conservative distance estimate using ... \[a\] formula for the distance of a point from an n-dimensional ellipse.

E. Rimon and S Boyd. Obstacle Collision Detection Using Best Ellipsoid Fit. Journal of Intelligent and Robotic Systems, 1997 - Springer
> 2 votes

---
Tags: algorithms, reference-request, optimization, computational-geometry
---


# Question
Title: $A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$?
> $A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$?

Basically, I've understood that if $A$ is finite, then there's a reduction for every $B$ which isn't trivial (empty or $\Sigma^\*$).

BUT, if $B$ is NPC then $B\ne \emptyset, \Sigma^\*$, so in which case there's is no polynomial reduction from $A$ to $B$?

# Answer
I think you've confused the direction of the reductions. A reduction from $A$ to $B$ means that you could solve $A$ efficiently if you had an efficient way of solving $B$. It's certainly true that you could determine membership of a finite language efficiently if you could solve some **NP**-complete problem. After all, you can determine membership of a finite language efficiently already, without needing to solve, say, travelling salesman.

On the other hand, it would be surprising if there was a polynomial-time reduction from some **NP**-complete problem to the problem of determining membership of a finite language. That would be saying, "If I could determine membership of this finite language efficiently, I could solve every problem in **NP** efficiently."

In case you weren't confused about which way reductions go, here's a concrete reduction from the language $\mathcal{L} = \\{\mathrm{elimination}, \mathrm{computer}, \mathrm{science}\\}$ to Boolean satisfiability. We will define a polynomial-time computable function $f$ from strings $\\{a, \dots, z\\}^\*$ to Boolean formulae such that $f(w)$ is satisfiable if, and only if, $w\in \mathcal{L}$.

```
if w = "elimination" or w = "computer" or w = "science"
    return "X"
else
    return "X∧¬X"

```
> 4 votes

# Answer
$A$ is polynomial since we can just compare its instances with the finite number of positive instances in polynomial (linear in the instance description size) time. *P* $\subset$ *NP*, so $A$ is also in *NP*.

$B$ is *NPC*, so by definition every problem in *NP* can be reduced in polynomial time to B.

Thus, there is always a reduction from $A$ to $B$.

If $A$ is a finite problem or a polynomial problem or even a *NP* problem, there is a reduction. So, in which case there is no reduction from $A$ to a *NPC* problem $B$ ? We know that there is no such reduction when $A$ is an *NEXPTIME-hard* problem, but it's probably also true for simpler problems like *co-NPC* problems.
> 2 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Algorithm for automatic/optimal database joins?
I'm curious if there is existing literature or well known algorithms out there for a problem I am working on.

Given a normalized relational database with valid foreign key constraints and a list of fields across different tables, what is a good or at least consistent algorithm for determining the (inner) joins required to provide that information? Ideally using the minimal number of joins possible.

Given a graph and a set of nodes that I want. How do I find a subgraph which is connected that contains all those nodes.

---

My initial thoughts:

I see the table as a directed graph with tables as vertices and foreign keys as edges between them. For the purposes of the algorithm treating the graph as undirected seems like it might be useful.

Shortest path between tables seemed obvious but as soon as more than 2 tables are requested then I would be finding the shortest path that visits all nodes (traveling salesman territory ACK!). My second thought is the minimum spanning tree of the subgraph. However, how would I choose the subgraph?

---

Edit: After thinking about it more I think this could work. Run Kruskal's minimum spanning tree on the graph beginning from a desired node. Assign weights to the edges like so weight=1 if (a,b) is between two desired nodes. Weight = n^2, where n is the number of nodes, if (a,b) is between a desired node and a undesired. Weight = n^4 if between two undesired nodes. The weights are arbitrary. I just thought it would be better to use values that couldn't overlap.

Once all desired nodes are added to the MST, exit Kruskal's. Then from the root (starting node) walk down to each leaf. If a leaf is not desired node, then delete it. Repeat until no nodes are deleted.

# Answer
This is the minimum Steiner tree problem for general graphs. It is known to be NP-hard. Here you have the special case where every edge has weight 1, but that special case is still NP-hard.

However, there are approximation algorithms, which you could use to get somewhat close to the optimum. Alternatively, if you want the exact optimal solution and your graph is not too large, you could express your problem as an instance of integer linear programming (ILP) and try using an off-the-shelf ILP solver, though the worst-case running time will still be exponential.
> 1 votes

---
Tags: algorithms, data-structures, optimization, database-theory, databases
---


# Question
Title: DFA for a strings whose every subsequence of length five has at least two zeroes
I have a regular language consisting of such `{0,1}^k` sequences, in which every subsequence of length 5 has at least two `0`'s in it (which also means every sequence of length \<5 is 'good'). I need to find a DFA which generates this language.

I can't say I tried everything, but each time I encountered the same problem, that is it always generated a subsequence of the form `11111`... (I tried incorporating each subsequence of length 5 with two 0's in my DFA so that the last element returned to the beginning of the automaton, but this resulted in accepting 'bad' subsequences - for instance `00111` and `11100` were 'good', but `0011111100` wasn't).

Is there any way to do it?

# Answer
There is a standard technique for problems like this, where the language can be specified in the form

> All words over some alphabet $\Sigma$ where \[some condition\] is satisfied by all contiguous substrings of a fixed length, $k$.

The key idea here is to define a collection of states $s\_i$ where $0\le i \le |\Sigma|^k$. Basically, you are using the states to "remember" the most recently-seen $k$ characters. These states will be part of the finite automaton we'll build for our language.

In what follows, I'll use a simpler language than yours, so that the FA will be sufficiently small to fit here and still be readable. Let $$ L=\\{w\in\\{0, 1\\}^\*\mid \text{every length-3 substring of $w$ contains at least 2 zeros}\\} $$ We'll define states $s\_0, s\_1, \dotsc, s\_7$ to represent the three most recently-seen characters. It's convenient to do this representation in lexicographic order, so $s\_0=\mathtt{000}$, $s\_1=\mathtt{001}$, $s\_2=\mathtt{010}$, $s\_3=\mathtt{011}$, $s\_4=\mathtt{100}$, $s\_5=\mathtt{101}$, $s\_6=\mathtt{110}$, and $s\_7=\mathtt{111}$. In other words, $s\_N$ will correspond to the 3-bit binary representation of $N$.

Now we'll add some more states to get from the start state to the $s$'s. All it takes is to construct a complete tree (binary in this example) having the $s$ states as leaves, like this:

All of the states in the FA above will be accepting states, except for the darkened ones. The $p\_i$ states are all accepting, since we haven't yet seen a length-3 string, so we haven't violated the condition that defines the language $L$ and only the patterns $\mathtt{011}, \mathtt{101}$, $\mathtt{110}$, and $\mathtt{111}$ violate the condition of the language. These correspond to states $s\_3, s\_5, s\_6, s\_7$. Once we've entered one of these states, we reject the input word, so we might as well merge these into a single "dead" state, $d$, from which there will be no exit.

We're almost done; all that remains is to fill in the transitions among the $s\_i$. Because of the way we chose the representations of the states, that's an easy task. If we're in state $s\_i$, having just seen characters $b\_1b\_2b\_3$, on input $b$ we'll pass to the state $s\_j$, corresponding to the new pattern $b\_2b\_3b$. If you think about it for a moment, you'll see that $\delta(s\_i, 0) = s\_j$ where $j\equiv 2i\pmod8$ and $\delta(s\_i, 1) = s\_j$ where $j\equiv 2i+1\pmod8$. Thus, we'll have the following $s$ transitions (recall that we merged states $s\_3, s\_5, s\_6, s\_7$ into a single dead state, $d$): $$\begin{array}{c|cc} & 0 & 1 \\ \hline s\_0 & s\_0 & s\_1 \\ s\_1 & s\_2 & d \\ s\_2 & s\_4 & d \\ s\_4 & s\_0 & s\_1 \\ d & d & d \end{array}$$

completing the construction. The nice feature of this technique is that it's almost completely mechanical: the only hard part is making the $s$ transitions. The downside is that it produces a pretty big FA. Even in this simple example, we wound up with a 12-state FA, and if we had needed to look at the five most recent characters, we'd have a FA with 31 states just for the $p$s. In fact, if we apply the standard technique for DFA minimization, we would find that the minimal-state DFA for this example language would require only 7 states, with 6 of them being final.
> 11 votes

---
Tags: formal-languages, regular-languages, automata, finite-automata
---


# Question
Title: Complete examples of program correctness proofs
Does anyone have any complete example of a proof of program correctness? I'm talking about something that includes the usual predicate, base case, inductive hypothesis, and inductive step. But also important is the loop invariant, and termination. I'm just not sure what the proper format for something like this is.

The only things I've been able to find are powerpoint slides from random schools, but they are for teaching purposes, and all over the place. I'm looking for something from start to finish, easy to follow, and formatted nicely that it can be submitted academically.

I wish to understand what a program proof looks like when (if) it is used for real, rather than as a proof sketch for a toy example in the classroom.

# Answer
You will find a collection of proof techniques illustrated with poofs of small programs in the following paper:

Inductive Methods for Proving Properties of Programs, Manna, Ness, Vuillemin, CACM 16-8, August 1973.

It is made available on the web by one of the authors. It is also the first paper I ever read on the subject, and I remember enjoying it.

But I would expect the literature, on and off the web, refereed papers, textbooks and other sources. to include a considerable number of such proofs, considering that today people are working on the proofs of real program (such as compilers), with the help of mechanized proof systems.

OF course, you are aware that there is no such thing as correctness in an absolute sense. Correctness is defined only with respect to some specification, i.e. to some predicate in a logic that can also express the meaning of programs (or whatever part of it is relevant).

Of course, there are different ways of defining the semantics of a program. So one might expect to have proof techniques that vary accordingly.
> 7 votes

---
Tags: algorithms, reference-request, programming-languages, proof-techniques, correctness-proof
---


# Question
Title: How does this Turing machine accept $a^n b^n$?
I'm reading this tutorial from the University of Illinois about Turing Machines, and I don't understand something.

They give a pseudocode algorithm for an machine that accepts strings from the language

$L = {0^n1^n}$

and a diagram of the machine. Both are pictured below:

What I don't understand however is how does this machine know that the number of $0$s are the same as the number of $1$s. I see no mechanism that can do that. All it seems the machine can do is recognize that there are no $0$s after $1$s.

# Answer
> 3 votes
It might be helpful to see what happens when the machine encounters $0^31^3$, say:

1. Initial state: $000111$.
2. Mark the first unmarked zero: $A00111$.
3. Mark the first unmarked one: $A00B11$.
4. Mark the first unmarked zero: $AA0B11$.
5. Mark the first unmarked one: $AA0BB1$.
6. Mark the first unmarked zero: $AAABB1$.
7. Mark the first unmarked one: $AAABBB$.
8. There are no unmarked zeros and no unmarked ones, so accept.

In contrast, here is what happens on input $00011$:

1. Initial state: $00011$.
2. Mark the first unmarked zero: $A0011$.
3. Mark the first unmarked one: $A00B1$.
4. Mark the first unmarked zero: $AA0B1$.
5. Mark the first unmarked one: $AA0BB$.
6. Mark the first unmarked zero: $AAABB$.
7. Crash (reject) since there are no remaining unmarked ones.

And here is what happens on input $00111$:

1. Initial state: $00011$.
2. Mark the first unmarked zero: $A0111$.
3. Mark the first unmarked one: $A0B11$.
4. Mark the first unmarked zero: $AAB11$.
5. Mark the first unmarked one: $AABB1$.
6. There are no unmarked zeroes but there is an unmarked one, so crash (reject).

# Answer
> 4 votes
The machine just changes the $O$ to $A$ and the $1$ to $B$, in such a way that it changes a $1$ each time it has changes a $0$. Hence, if there is the same number of $0$ and $1$, they all end up being changed at some point. The TM no longer finding any $0$ will go to the bottom part of the diagram and check that all $1$ have been changed to $B$, i.e. that the sequence of $B$ is followed by a blank space. In that case it accepts.

But is some $1$ is left after the $B$, then the TM will block in state $q\_3$ (no transition corresponding to $1$ on the tape) and reject. Indeed, that means hat there were more $1$ than $0$, which does not conform.

But if there were more $0$ than $1$, say $0^n1^m$ with $n\>m$, the TM will block in state $q\_1$. The reason is that, after erasing $m$ symbols $0$ and correspondingly $m$ symbols $1$, the TM will erase another $0$, and try in state $q\_1$ to find another $1$ to erase. But it will find none, only a blank space.

---
Tags: formal-languages, turing-machines, automata, correctness-proof
---


title: Cache question help me here?

text:
# Question
Title: Cache question help me here?
Quantify the effect in performance which comes from using the cache ,if We are going to use a program which is made from 500 machine instructions ,from which 100 are in a cycle which is executed 25 times.Suppose that the main memory has a memory stall of 10 units of time and the cache memory has a stall of 1 unit.

So the performance equation in this case would be:

CPU exe time=I\*(CPI exe + Miss rate * (Memory accesses/Instruction)\* Miss penalty )\* Clock cycle time

**Is this the right performance formula I should use for this case?**

Miss penalty in my opinion = 10+1 =11

I=500

Memory accesses/Instruction= 25/100

Are these correct?

How do I find Miss rate and clock cycle time here?

# Answer
**Clock cycle** can be the base unit. That is, the "running time" can be measured in clocks, so a valid answer would be 1000clock cycles (and not, 10 milliseconds, unless you are given that 1clock-cycle is xx seconds.)

**Miss rate:** assume each time you read an instruction for the first time, it is a miss. If you read the same instruction for the second time, assume it is already in the cache. (Otherwise, one must specify the size of the cache and give you more details to decide about miss/hit)

Thus, the 100 instructions that appear in cycle will be a miss for the first time, and a hit in the other 24 times.

The other 400 instructions are always a miss (but they are called only once).

So the miss rate would be.. ?
> 1 votes

---
Tags: cpu-cache, memory-hardware
---


# Question
Title: How do you swap consecutive boxes on a Turing Machine tape?
I can't figure out how to swap boxes on a Turing Machine tape.

So for example, I have a tape that says

```
a 1 0 1 1 1 0
^

```

And I want to move that `a` over so that it is in the middle. (but my end goal is not important here)

How do I get the Turing Machine to do

```
1 a 0 1 1 1 0
  ^

1 0 a 1 1 1 0
    ^

etc...

```

# Answer
Here is a possible set of transition to do one move, as you request. Note that $x$ is to be replaced by $0$ and by $1$, so that each transition with $x$ is actually a pattern to be replaced by 2 transitions, one with $0$ and the other with $1$, instead of $x$ (so you really have 5 transitions below)
And of course $q\_{2,x}$ stands for two states: $q\_{2,0}$ and $q\_{2,1}$.

I present things that way so that you know what to do if you can have more than two disctinct symbols to deal with.

The $\*$ is just a wild card, indicating that the content of the tape does not matter.

This will do the required exchange, with $0$ or $1$. You end up in state $q\_2$, still pointing to the $a$

$\begin{align} q\_1, a&\to q\_{1,a},a,R\\ q\_{1,a},x&\to q\_{2,x},a,L\\ q\_{2,x},\*&\to q\_2,x,R \end{align}$

I hope this is clear.

What it does is to note $a$ in the finite state control, by going in state $q\_{1,a}$, and then moving Right. There it notes in the finite state control whatever $x$ is found there, a $0$ or a $1$, thus going in state $q\_{2,x}$, and write down the $a$ (so it can forget it), and moves back Left. Back on the left square, there is still an $a$, it does not matter, it can write down the $x$ it memorized in the finite state control, and move Right again, in state $q\_2$, so that it is pointing to the $a$ that was moved.

Note that the $\*$ could be replaced by $a$. The $\*$ is a convenient notation to say that it does not matter, as you could have several symbols other than $a$ to be moved in this way.

$q\_2$ is whatever state you need to be in after performing one such permutation.
> 3 votes

# Answer
To this end, you first need to find the middle point. In this answer there is a good algorithms to do that:

1. mark the start and the end of your tape
2. move the start marker one step to the right, move the end marker one step to the left
3. repeat until the markers reach each other

Then, you move the "a" until you get to the marker, and remove the marker.

---

EDIT:

**How to move a letter:** Say you have an "a" among a string of 0 and 1. here is a way to shift it to the right:

1. $q\_{start},a \to q\_?,a,L\quad$ and also $\quad q\_{?},a \to q\_?,a,L$
2. $q\_?,0 \to q\_0,a,R$
3. $q\_?,1 \to q\_1,a,R$
4. $q\_0,\* \to q\_?,0,L$
5. $q\_1,\* \to q\_?,1,L$

where $\*$ is "don't care".

What is going on here? If we see an $a$, we move to the cell to the right of it, remember what was written there, and write an $a$ instead. If it was a $0$ we deleted, we move to state $q\_0$, if it was a $1$ we move to $q\_1$. This is how we "remember" what was deleted. Then we move the head one step to the left, and write 0 or 1 according to whether we are in state $q\_0$ or $q\_1$. Then we move one step to the right and repeat the same process. Try to simulate it for yourself on a paper...
> 2 votes

---
Tags: turing-machines
---


title: How can I prove algorithm correctness?

text:
# Question
Title: How can I prove algorithm correctness?
How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ?

For example, consider the program below.

You’re given a read only array of $n$ integers. Find out if any integer occurs more than $n/3$ times in the array in linear time and constant additional space.

Algorithm: We will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with its proper count. If we reach the size of count array we decrement one from count of each number. If number count becomes zero it can be safely eliminated from the count array.

Here is an example:

* Input: 4 3 3 7 2 3 4 5
* count arr (4,1) 4 as first element and 1 is its count till now
* count arr (4,1)(3,1)
* count arr (4,1)(3,2)
* count arr (4,1)(3,2)(7,1). Here we reach the max allowed size for count then we need to decrement count by one and if it reaches zero its item will be removed from our count array so count arr becomes count arr (3,1). We will proceed with next element in the array which is 2.
* count arr (3,1)(2,1)
* count arr (3,2)(2,1)
* and so on. At the end count arr will be (3,1)(5,1).

We will make another loop to the input array to count occurrence of 3 and 5 and if any one exceeds $n/3$ it will be printed out.

# Answer
> 9 votes
In practice, to prove an algorithm you should search a good invariant property for each loop. For example, if you compute in a given order the sum of $n$ integers with a for loop (indexed by $i$), the invariant could be : "At the end of an iteration, the $sum$ variable contains the sum of the $i$ first values". It's invariant over iterations number and always true, it's easy to prove this by recurrence on the iterations number. Afterwards you can easily conclude that, at the end of the loop, $i=n$ and thus that $sum$ is the expected sum.

Then, there is several levels of strictness, but for simple algorithms we can generally conclude promptly since the correction of the algorithm becomes almost always trivial with all the loops invariants. A very classical approach is to prove before that the algorithm finishes and after that the algorithm is correct when it ends. For complete examples you can look here. For more subtil algorithms, you can also need some mathematical theorems which provide some links beetween objects.

Your example is very close to Misra-Gries algorithm. You can look for the proof of the Misra-Gries algorithm and try to adapt it or you can try to bound the number of times the count of the most frequent number is decreased.

In general, there isn't a systematic way to find if an algorithm produces the expected output or not. Indeed, this systematic way would be an algorithm and such an algorithm can't exist (Rice's theorem).

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Algorithm for finding all the combinations on a boolean array
I have to design an algorithm to do the next task:

I have one array of booleans. For example:

Array: \[0 1 0 0 1 0 1 1\]

I want to obtain all the existing combinations of 1's, having in mind that it is allowed only a **maximum of one 0 between 1's**. For example, in the previous case, we would have the outputs (**I am using the indices now**): \[1\] and \[4,5,6,7\].

But also it should include \[4\], \[6\], \[7\], \[4,5,6\], \[6,7\].

Another example:

Array: \[0 1 0 1 0 1 0 0 1\]

The output would be: \[1\], \[3\], \[5\]. \[8\], \[1,2,3\], \[1,2,3,4,5\], \[3,4,5\].

Can you imagine any approach to solve this? The combination explosion could be quite big.

Thank you very much in advance.

# Answer
> 2 votes
The pattern you're trying to match is regular and can be matched by the regular expression **1(0?1)\***. A good strategy would be to convert the binary array to a string and do regular expression matches over substrings of it.

There aren't an exponential number of bit strings to check. For a string of length $n$, you only have to check 1 string of that length. You then check 2 strings of length $n - 1$, 3 strings of length $n - 2$ and so on. In total there are $n(n+1)/2$ strings to check.

# Answer
> 2 votes
Simple $O(n^2)$ solution -

```
def combs(A):
    n=len(A)
    for i in range(n): # Primary loop, i loops over possible starting points
        if A[i]==1:    # Wherever we see a 1...
            yield [i]  # Yield the location and
            prev=i     # Store position as last see index of 1, and
            for j in range(i+1,n):  # Start secondary loop
                if A[j]==0:         # If we see a 0
                    if j-prev>1:    # Break if this and last are both 0s
                        break
                else:               # If we see a 1
                    prev=j          # Store this as last seen index of 1
                    yield list(range(i,j+1))  # Yield the from start till this location

```

Then you get -

```
list(combs([0,1,0,0,1,0,1,1]))
# [[1], [4], [4, 5, 6], [4, 5, 6, 7], [6], [6, 7], [7]]

```

# Answer
> 1 votes
It seems to me that your main problem is stating what you want. The following is inferred from what you say and the examples you give.

Essentially, you have a string $w\in \\{0,1\\}^\*$, which you call an array of booleans.

What you want is list all substrings that begin and end with a $1$ such that they do not contain two consecutive $0$.

This is a pretty standard problem that you can solve with a finite state control, and some extras, depending on how you wish to express the result. Here is simply a direct pseudo-code solution.

First, you should not be afraid of a combinatorial explosion. Given a string of length $n$, indexed from $1$ to $n$, there are $n$ ways of choosing the first index $i$ of a substring, and for each choice of $i$, there are $i$ ways of choosing the last index of the substring. So that make a total of $\sum\_{i=1}^{n}i=\frac{n(n+1)}{2}$ substrings, which is only quadratic, and not too combiatorial.

The answers you are looking for are only a subset of the set of substring, so there is not too much to be afraid of.

Then the algorithm goes as follow:

```
Start from beginning of the string.
loop
  Look for the index i of the first 1
  Scan the string while you do not see two consecutive 0, or the end
    of string
  let j be the index of the last encountered 1
  list correct-substrings (i,j)
  Exit loop if end of string has been reached

Subprogram correct-substrings (i,j)
  for all k in [i,j] such that w[k]=1 do
    for all h in [k,j] such that w[h]=1 do
      output substring(k,h)

The subprogram substring(k,h) produces the list of indexes from k to h.

```

---
Tags: algorithms, algorithm-analysis, search-algorithms
---


# Question
Title: Can Tarjan's SCC algorithm find satisfying assignment to just 'any' digraph?
Is Tarjan's algorithm capable of finding satisfying assignment to any digraph consists of variables (vertices) and implications (edges)? I know that it solves implication graphs constructed by 2SAT clauses, but I wonder if the algorithm can handle the digraphs which cannot be expressed as 2SAT clauses. Let me clarify this by the following examples:

(a+b)(~b+c) translates to the following (~a -\> b), (~b -\> a), (b -\> c), (~c -\> ~b) It is OK. But how about the following implications: (a -\> b), (b -\> ~c) There is obviously no corresponding set of 2SAT instances. Does Tarjan's algorithm find a satisfying assignment to this?

# Answer
> 1 votes
You have a faulty premise. There *is* a 2SAT instance corresponding to $(a \implies b) \land (b \implies \neg c)$. Just note that $x \implies y$ is equivalent to $\neg x \lor y$. Then you can transform the original formula to $(\neg a \lor b) \land (\neg b \lor \neg c)$, which is obviously a 2SAT instance.

That algorithm you refer to can solve 2SAT, but it can't solve anything stronger as is. However, there *are* related graph-based algorithms to test satisfiability of arbitrary conjunctions of Horn clauses.

---
Tags: satisfiability
---


# Question
Title: Why is it true that $NP \ne coNP \implies X = \emptyset$?
Let the class of languages $$X = \\{ L \ | \ L\in NPC \land L\in coNPC\\}$$

Why is it true that $NP \ne coNP \implies X = \emptyset$?

# Answer
> 3 votes
Summarizing the comment as an answer:

Consider $L\in NPC$. By definition it means that every $A\in NP$ satisfies $$ A\le\_p NPC.$$ Similarly, if $L\in coNPC$, then by definition (which is not very common, but we can defined it in similar way to NPC), every $B \in coNP$ satisfies $$B\le\_p coNPC.$$

So assume $X$ is non-empty, that is, there is $L$ which is both NP-complete, and coNP-complete.

Now, $L$ is in $NP$ (since $NPC\subseteq NP$), but it is also in $coNP$ from a similar reason. From here we will get that $NP=coNP$. Assume not, so there is a language $A\in NP$ but $A\notin coNP$ (or the other way). But $A\le\_p L$ since $L$ is complete for $NP$. This means $A$ can be reduced to a $coNP$ language (L!), which implies that $A\in coNP$, a contradiction. More generally, this reasoning implies that $NP \subseteq coNP$, and the other direction holds symmetrically. Thus $NP=coNP$ under these assumptions.

---
Tags: complexity-theory, computability
---


# Question
Title: Is an inverse homomorphism always a homomorphism?
Given a homomorphism $h: \Sigma \rightarrow \Delta^\*$ such that e.g. $\forall a \in \Sigma: h(a) = \delta$, where $\delta \in \Delta$ (i.e. all symbols from the alphabet $\Sigma$ have the same image $\delta$), is the inverse homomorphism $h^{-1}$ a homomorphism?

Since a homomorphism maps every symbol of the input alphabet to one word from the output alphabet, the inverse transformation to $h$ is a substitution $\sigma: \delta \mapsto \Sigma$ (which maps one symbol to a whole language - alphabet $\Sigma$).

What would be an inverse homomorphism to $h': a \mapsto \epsilon, \forall a \in \Sigma$ or would such a transformation even exist?

**EDIT:** The question should have rather stated: "Is there always an inverse homomorphism?" There obviously isn't since only isomorphisms have their inverse homomorphisms.

# Answer
> 7 votes
If all letters map to the same letter $\delta$, then the inverse $h^{-1}(w) = \\{w\mid h(x) = w\\}$ is only defined (nonempty) when $w\in\delta^\*$ and would consist of all strings in $\Sigma$ that have the same length as $w$. This is not an homomorphism, as these have only one image for each input. (Except for the very special case that $|\Sigma| = |\Delta| = 1$.)

The inverse *is* a substitution, mapping the letter $\delta$ to the set $\Sigma$ and all other letters in $\Delta$ to the empty set.

Obviously homomorphism $h'$ maps all strings to the empty string. Thus the inverse maps the empty string to $\Sigma^\*$ and all other strings to the empty set. Silly mapping, but it is a finite state transduction (finite state automaton mapping with output).

Let me explicitly answer the question from the title. No. An homomorphism is one-to-one \[meaning single valued\], an inverse homomorphism in many cases is one-to-many \[many-valued\]. (If the inverse morphism is one-to-at-most-one \[injective\] again it usually is not a morphism, but the morphism is called a coding, because it can be "decoded").

# Answer
> 4 votes
The expression "closed under inverse homomorphism" is often used in formal languages: see for instance this question and this needs a clarification. As Hendrik Jan pointed out in his answer, a homomorphism is a map, but an "inverse homomorphism" is usually not.

To make the definition of "inverse" correct, one needs to view a homomorphism $h : A^\* \to B^\*$ as a relation on $A^\* \times B^\*$, whose graph is $$ \\{(x, h(x)) \in A^\* \times B^\*\mid x \in A^\*\\} $$ Now, the inverse of $h$ as a *relation* is the relation $h^{-1}$ defined by its graph as follows $$ \\{(h(x), x) \in B^\* \times A^\* \mid x \in A^\*\\} $$ and hence, for $y \in B^\*$, $h^{-1}(y) = \\{x \in A^\* \mid h(x) = y \\}$.

---
Tags: formal-languages
---