title: Reduction from PARTITION to MAX-CUT

text:
# Question
Title: Reduction from PARTITION to MAX-CUT
I am trying to prove the NP-Hardness of the **MAX-CUT** problem. Other sources seem to reduce from the **NAE-3SAT** problem, however I have been trying to reduce from **PARTITION** because **PARTITION** and **MAX-CUT** are both in Karp's list of 21 NP-Complete problems and this is the reduction that he did \[1\].

**PARTITION**: Given ($c\_1,c\_2,\dots,c\_n)\in\mathbb{Z}^n$, does there exist $S\subseteq\\{1,2,\dots,n\\}$ such that $$\sum\_{i\in S}c\_i=\sum\_{j \not\in S}c\_j$$

**MAX-CUT**: Given a weighted graph $G=(V,E)$ with weight function $w:E\rightarrow\mathbb{Z}$ and a target weight $W\in\mathbb{Z}^+$, does there exists $S\subseteq V$ such that $$\sum\_{(u,v)\in E\\::\\:u\in S,\\,v \not\in S}w((u,v))\geq W$$

After spending a lot of time trying to construct a reduction to prove **PARTITION** $\leq\_p$ **MAX-CUT** myself, I eventually gave up and looked at Karp's paper. The problem I could not manage to solve is how you encode the equality constraint of **PARTITION** in a **MAX-CUT** instance which only has one inequality constraint. The reduction that Karp gives (which I would not have been able to come up with) is as follows:

Given a **PARTITION** instance $(c\_1,c\_2,\dots,c\_n)$, construct a **MAX-CUT** instance $(G=(V,E),\\,w,\\,W)$ such that: $$V=\\{1,2,\dots,n\\}$$ $$E=\\{(u,v) \\: : \\: i,j\in V,\\, u\neq v\\}$$ $$\forall (u,v) \in E,\\,w((u,v))=c\_ic\_j$$ $$W=\lceil \frac{1}{4} \sum\_{i=1}^{n}c\_i^2\rceil$$

I am having trouble proving the correctness of this reduction (the paper does not seem to give any justification). I can kind of appreciate the need to be squaring values - is my intuition correct that this is to account for needing to the equality constraint with an inequality constraint?

I have tried using the Cauchy–Schwarz inequality to prove this with no luck. Similarly, I have tried to relate this to the variance/covariance of two partition sets, but I'm not sure if this is helping me understand why this reduction works.

A proof plus any intuition of how one might have arrived at this reduction would be greatly appreciated.

\[1\] Richard M. Karp (1972). "Reducibility Among Combinatorial Problems". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. (pdf)

# Answer
Since the graph is complete, any set $S$ will induce a cut of weight

$$\sum\_{i\in S, j\notin S} c\_ic\_j ~~=~~ \sum\_{i\in S} c\_i \cdot \sum\_{j\notin S} c\_j.$$

Denote the two sums in the latter formula by $A$ and $B$. The problem of finding a maximal cut then means maximizing $A\cdot B$, while $A+B$ is fixed. It is well-known that the maximum of this product is achieved for $A=B$. In this case the product becomes $\left(\frac 12 \sum\_{i=1}^n c\_i\right)\cdot \left(\frac 12 \sum\_{i=1}^n c\_i\right) = \frac 14 \left(\sum\_{i=1}^n c\_i\right)^2$. So $W$ should not be a quarter of the sum of squares, but a quarter of the square of the sum.

So the reason you could not prove the correctness of the reduction is, that the reduction as given is not correct. (And I'm somewhat embarrassed that I only noticed this after your followup question in the comment.)
> 4 votes

---
Tags: complexity-theory, np-complete, reductions, partition-problem, max-cut
---


title: Determine Epsilon for identification

text:
# Question
Title: Determine Epsilon for identification
I have a project in which I need to compare different distances in a database with a distance in input in order to identify a person. For that I use this expression: DistanceDB - DistanceInput \< epsilon, if this is true then the distance and information in the Database row are related to the person standing before the kinect. How can I choose epsilon because if it's too small, no one will be identifier, and if it's too big the application will return the first row of the database. Thank you for your answers.

# Answer
Your best bet is probably to start with a value that seems reasonable and improve it by trial and error.
> 1 votes

# Answer
Whenever you have a parameter that you don't know how to set, you should probably tune it based on sample or training data.
> 1 votes

---
Tags: data-mining, databases
---


# Question
Title: How is a nondeterminisitic automaton running on an input?
A nondeterministic automaton, after reading an input symbol at some state, may jump into any of a (finite?) number of states.

Does the automaton uniformly randomly choose one out of the several states?

So different runs on the same input will give different sequence of states?

Does the automaton have to run in all the possible sequences of states on a given input? Or just one random run?

# Answer
> 9 votes
A non-deterministic automaton runs in all possible sequence of states on a given input. It is not a random run.

An input symbol is accepted only if in **at least one** of the runs it has reached an accepting state after reading the given input.

Hope this helps :D

# Answer
> 6 votes
Non-deterministic machines are not realistic devices. They are conceptual devices useful for developing some theories. There are several possible ways of conceiving of the operation of a non-deterministic automaton:

1. Whenever the non-deterministic automaton has to make a choice, it "forks" or "splits" to several different automata running in parallel, each making a different choice. The automaton accepts if at least one of its "copies" accepts.
2. Whenever the non-deterministic automaton has to make a choice, it asks a "deity" for a "hint" (sometimes known as a "witness"), and follows the hint. The automaton accepts if some sequence of hints given it by the deity will make it accept.
3. The non-deterministic automaton considers all possible execution paths sequentially (one by one). If any of them accepts, it accepts the input.

All these different views are valid. Choose whichever you like the most.

Regarding the second viewpoint, more can be said. You can think of it as a one-player game. The deity is trying to "convince" the automaton to accept the input. It's up to the deity to come up with a convincing sequence of hints. If the input does not belong to the language, then nothing the deity does will convince the automaton. If the input does belong to the language, then the deity can convince the automaton somehow.

A good example is the language of *true propositions*. Here a hint is a *proof*. Every true proposition has a proof, and no false proposition has one.

# Answer
> 5 votes
The computation of a non-deterministic automaton can be modeled by a tree. The input is accepted if there is a root-to-leaf path that eats the input and terminates in an accepting state.

When the automaton branches, each branch carries the computation on its own. So you can imagine that all possible root-to-leaf paths are being considered at the same time, meaning that the overall running time is bound by the height of the tree.

This process can be simulated on a real machine by trying out every possible path. The simulation takes more time naturally. Each branch contributes a factor of $2$, so the simulation takes $2^n$ or something similar.

# Answer
> 3 votes
Strictly speaking I do not answer your question, but I will hint at a broader automaton model. (It is meant as a PS to the answer by Yuval.) I will not anwer questions here: it might get off-topic.

The nondeterministic automaton is "existential": it accepts a string iff a run on that string exists. How you want to visualize that is your own choice, and Yuval has sketched three possibilities: try all possibilities in parallel, one-by-one, or accept divine hints.

There is a larger type of automata, called *alternating*, that have existential and universal states. In an existential state one requires the existence of at least one succesful continuation, while in a universal state all continuations should end in a final state.

For finite state automata, the existential extension is equivalent in power as the original FSA, whether deterministic or nondeterministic). For Turing machines there is an additional layer of complexity classes for alternation: e.g., $P \subseteq NP \subseteq AP$. And there is an even much nicer connection to games and logic: alternation is like a two player game.

---
Tags: automata, nondeterminism
---


title: Quantifier String Placement

text:
# Question
Title: Quantifier String Placement
This is the edited question:

Suppose I have $(x\_1 \vee y\_1 \vee y\_2)$. x is existential and y is universal. Then it should be like this in the quantifier string: $\forall y\_1 \forall y\_2 \exists x\_1$ (WHY?)

Now suppose I introduce a new variable z and convert the above clause to: $(x\_1 \vee \neg z \vee y\_2 ) \land (z \vee x\_2)$. My question is where should I insert z in the quantifier string and with which quantifier(exisential or universal)?

Also, don't reply saying that you can place it anywhere...because the position of insertion does matter.

Thank you

# Answer
If, as I suspect, you are still trying to convert quantified 3-CNF formulas into quantified mixed Horn formulas, the answer is that quantifiers for the newly added bridge variables can be placed anywhere in the quantifier list. This is because their final values are completely contingent on the setting of all other variables in the formula, so you will *always* be able to set them to correct values to satisfy the formula if the formula is satisfiable.
> 1 votes

---
Tags: algorithms, logic, satisfiability
---


title: Solving SAT using tableau calculus

text:
# Question
Title: Solving SAT using tableau calculus
I've learned about tableau calculus which is a decision procedure solving the problem of satisfiability of a first order logic formula. Now I'm wondering why this technique can't be used to solve the satisfiability problem (SAT)?

# Answer
> 7 votes
It can be, but the solution process is equivalent to converting a CNF formula to DNF, which is NP-hard. You will at worst end up exploring an exponential number of disjunction branches.

---
Tags: logic, first-order-logic, sat-solvers, sat
---


# Question
Title: Checking whether an integer is a square or higher power
Is there an algorithm to check whether an integer $n$ is a square? What about higher powers, e.g., testing whether $n$ is a $k$th power?

I understand that the Jacobi symbol $\left(\frac{b}{n}\right)$ can be computed in $O(\log n)$ without needing to know the prime factorization of $n$ but then this seems to be useful only for squares (not higher powers), and even then, it can still be inconclusive.

Maybe there is some way of refining the use of the Jacobi symbol for my question?

# Answer
> 4 votes
The standard algorithm for determining whether an integer $n$ is a perfect power goes like this. We check whether it is a perfect $k$th power for $k \in \\{2,\ldots,\log n\\}$; as an optimization, it suffices to consider only prime $k$. Given $k$, we compute $\sqrt\[k\]{n}$ using binary search or using some fixed-point iteration such as Newton's method. Either way, we find a candidate for $\sqrt\[k\]{n}$, and can check whether $(\sqrt\[k\]{n})^k = n$ or not. For more details on computing $\sqrt\[k\]{n}$, consult for example this paper (mentioned in Ricky Demer's deleted answer), Step 1.

---
Tags: algorithms, integers
---


# Question
Title: Converting (math) problems to SAT instances
What I want to do is turn a math problem I have into a boolean satisfiability problem (SAT) and then solve it using a SAT Solver. I wonder if someone knows a manual, guide or anything that will help me convert my problem to a SAT instance.

Also, I want to solve this in a better than exponential time. I hope a SAT Solver will help me.

# Answer
Chapter 2 of the SAT Handbook (by Steven Prestwich) covers how to turn discrete decision problems into CNF, in some depth. (Unfortunately, I don't think there is a draft version online -- probably best to consult your local library.) Several of the other references cited in Magnus Björk's quirky overview *Successful SAT Encoding Techniques* are also useful.

If your problems are continuous, or you are especially interested in systems of inequalities, then other kinds of solvers are more likely to be useful. As Kyle points out, SMT solvers (such as Z3, Yices, or OpenSMT) might be useful, although traditionally SMT theories tend to be focused on verification of computer software, so SMT solvers usually have great support for things like expressions involving intervals of integers, but may perform poorly on injectivity constraints. For problems that are naturally expressed as systems of inequalities, CPLEX is the one to beat (it used to be available for academic use for free, and it might still be). For some combinatorial decision problems (like finding packings of rectangles into a square), constraint solvers such as Minion outperform SAT solvers and are often easier to use.
> 20 votes

# Answer
Unless you're translating mathematical problems to SAT instances as a learning exercise, your time will be much more fruitfully spent learning about satisfiability modulo theories. SMT will allow you to express equations and other constraints much more naturally than as Boolean SAT instances. Some SMT solvers support existential and universal quantifiers, allowing you to move beyond NP and express PSPACE problems.

Besides being more expressive, SMT solvers are faster. Not P=NP faster, but more efficient in that a good SMT solver doesn't discard theory-specific structural information that helps guide the solver through the search space. Doing a Karp reduction directly to a SAT instance forces the SAT solver to relearn all that structure, often at exponential cost. For example, the fact that addition is commutative is lost on both DPLL-based and local search based SAT solvers; the solver isn't aware that it is dealing with numbers at all! To avoid trying all the permutations of x+y+z=10 a SAT solver needs symmetry-breaking code, which requires graph automorphism detection. The best current graph automorphism recognition algorithms require time exponential to the number of vertices in the worst case, so exponential time might be spent relearning a simple rule of arithmetic.
> 14 votes

# Answer
Two tools that convert high level languages to SMT or CNF.

CVC The syntax is close to CAS.

CBMC It convert a C program to CNF, allowing assertions. The assertions are either always true, or if false a counterexample input is found. CBMC unrolls loops, so certain C programs have exponentially large CNF/SMT.
> 5 votes

---
Tags: algorithms, reductions, satisfiability
---


# Question
Title: What is the difference between symbol recognition, classification and identification?
I've just wondered if there is a difference between symbol recognition, classification and identification.

What would you use when you have a hand-written symbol and you want to get the LaTeX code for it? Is that symbol classification, because you have about 1200 classes of LaTeX symbols? Or identification? Are some of those words synonyms? Which words are used more often?

# Answer
> 1 votes
The way I've seen it used classification divides a data set into different groups (or classes), while symbol recognition means looking for a specific pattern and checking if it is present in the data or not.

If I understand correctly, what you are talking about is optical character recognition but instead of matching the symbol to an ASCII/unicode value you match it to a LATEX symbol. I think that this could be called both symbol recognition and identification.

---
Tags: terminology, classification, pattern-recognition
---


# Question
Title: How is this formula for dynamic array reached?
I am reading through Skiena's "The Algorithm Design Manual". He analyses the number of copy operations performed in a dynamic array.

> "Suppose we start with an array of size 1, and double its size from $m$ to $2m$ each time we run out of space. This doubling process involves allocating a new contiguous array of size $2m$, copying the contents of the old array into the lower half of the new one. The apparent waste is in the recopying of the old contents, on each expansion."

Skiena then asks:

> "How many times might an element have to be recopied after a total of $n$ insertions?".

He then gives a formula for calculating the total number of movements $M$, for $n$ insertions, which is

$$\mathbf{M}=\sum\_{i=1}^{\log n} i\cdot\frac{n}{2^i}.$$

His explanation is:

> "Well, the first inserted element will have been recopied when the array expands after the first, second, fourth, eighth, ...insertions. It will take $\log\_{2}n$ doublings until the array gets to have n positions. However, most elements do not suffer much upheaval. Indeed, the $(n/2 + 1)$st through $n$th elements will move at most once and might never have to move at all."

But I really don't understand how he draws the formula from that. Can anyone help me understand how he reaches it? Mainly what I can't understand is why he is multiplying $\frac{n}{2^i}$ by $i$.

# Answer
Let's look at the moment just after we copy the array to insert element $2^k + 1$, so we're doubling the array size from $2^k$ to $2^{k+1}$. There are $n = 2^k$ elements in the array at this moment.

The first term in the sum is $1 \cdot n/2$, representing the fact that $n/2$ elements (namely, elements $(n/2+1), \ldots, n$) have been copied exactly once (just now!).

The next term is $2 \cdot n/4$. The previous $n/4$ elements - that is, elements $(n/4) + 1, \ldots, n/2$ - will have been copied exactly twice, once just now and once when we expanded the array from size $n/2$ to $n$.

The next term is $3 \cdot n/8$. The previous $n/8$ elements will have been copied three times: now, at the last expansion and at the second-to-last expansion when we expanded from size $n/4$ to $n/2$. You can probably see where this is going by now.

The thing to remember is that each element gets copied every time the array expands *after* the element in question has been inserted, and the copies happen every time the size exceeds a power of two.
> 6 votes

# Answer
> Mainly what I can't understand is why he is multiplying $\frac{n}{2^i}$ by $i$.

I believe this is a mistake in the book. Let's take a look at an example (taken from https://softwareengineering.stackexchange.com/questions/119151/how-many-copies-are-needed-to-enlarge-an-array)

```
Array of 1 element.
Let's call it array-1.
+--+
|a |
+--+

Double the array (2 elements).
Let's call it array-2.
+--++--+
|a ||b |
+--++--+

Double the array (4 elements).
array-4.
+--++--++--++--+
|a ||b ||c ||c |
+--++--++--++--+

Double the array (8 elements).
array-8.
+--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||d ||d ||d ||d |
+--++--++--++--++--++--++--++--+

Double the array (16 elements).
array-16.
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||d ||d ||d ||d ||  ||  ||  ||  ||  ||  ||  ||  |
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+

```

So, accordingly to the book number of copyings is governed by the following formula: $M = 1 \cdot 8 + 2 \cdot 4 + 3 \cdot 2 + 4 \cdot 1$

The first term of the sum $1 \cdot 8$ is for copying *array-8's* items into *array-16*.

We copy the *array-4's* items (a, b, c, c) twice. Once from the *array-4* to *array-8*. And then when copying *array-8's* items to *array-16* we copy (a, b, c, c) items for the second time. Accordingly to the book, hence the second term: $2 \cdot 4$.

But now notice that the $1 \cdot 8$ term already takes into account copying of (a, b, c, c) items from *array-8* to *array-16*. Consequently the $2 \cdot 4$ term must not include the $2$ multiplier.

The same logic applies to all the other terms. And so multiplying by $i$ is a mistake.
> -1 votes

---
Tags: algorithms
---


title: Join large list of pairs

text:
# Question
Title: Join large list of pairs
I have a list of millions of pairs of strings, and I want to join all of the pairs that have matching members into lists without duplicates.

Example input:

```
[["A", "B"],
 ["A", "D"],
 ["M", "Q"],
 ["A", "F"],
 ["D", "E"],
 ["Q", "Z"]]

```

Example output:

```
[["A", "B", "D", "E", "F"],
 ["M", Q", "Z"]]

```

Does anyone know of an efficient algorithm for this? I'm somewhat constrained by memory. Anything that would square the memory from the input would not be an option.

# Answer
> 3 votes
You can use a two pass approach:

In the first pass, identify all the different strings appearing in your input. (This can be done in various ways, e.g. hashing, trie, BST)

For the second pass initialize a Disjoint-set data structure with the strings found in the first pass and perform a union operation for each pair in the input.

---
Tags: algorithms, data-structures, lists
---


title: Resolve left-rescursion

text:
# Question
Title: Resolve left-rescursion
Can anybody give me a hint on how to get rid of the left recursion in the following grammar?

$$A \rightarrow B \mid a$$ $$B \rightarrow b \mid C \mid D \mid E \mid F \mid G$$ $$C \rightarrow c \mid A d$$ $$D \rightarrow A e \mid f$$ $$E \rightarrow g \mid B h$$ $$F \rightarrow i \mid A j \mid k$$ $$G \rightarrow l \mid A m \mid n$$

So far I've tried this algorithm and this tool. But both are only applicable for smaller grammars and provide practically unusable results (1000's of rules).

# Answer
**This explanatory part can be skipped :**

Non-terminal in a Context-Free Grammar can be interpreted as standing for the set of strings they generate (this is actually one standard interpretation of CF grammars as string set equations).

For example $A \rightarrow C \mid D \mid a$ may be read as a set equation $A = C \cup D \cup \\{a\\}$ where $A$, $C$ and $D$ now stand for sets of strings and {a} for a singleton set containing the string "$a$".

Algebraic properties of concatenation and set union on strings and string sets can be used to transform grammars. In particular, you can use factorization in ways that are similar to what you do in arithmetics to make formulae simpler to compute.

Typically, if $A$, $B$ and $C$ are string sets (possibly reduced to a simgleton, i.e. a single string), then $(A \cup B)C = AC \cup BC$, i.e. concatenation is distributive for set union, like product is for sum.

**How to do it**

So, when you transform a CF grammar, you can first reduce the size with factorization. For that, you may replace some non-terminals by the right-hand-side of their defining rule, or introduce new non-terminals when convenient.

$A \rightarrow C \mid D \mid a$
$C \rightarrow c \mid A d$
$D \rightarrow A e \mid f$

can be rewritten as

$A \rightarrow X \mid a$
$X \rightarrow AY \mid Z$
$Y \rightarrow d\mid e$
$Z \rightarrow c\mid f$

There are various ways of using this, but you should be able to use it to do away with the complexity of your grammar.

*I deliberately did **not** make it as simple as I could have*. My purpose is only to give you an idea of what can be done.

The correctness of transformations can also be proved directly on derivations, without having to consider interpretations on string sets as I did above.

**Complete solution**

Here is a suggested answer. Hoping to simplify presentation, I used extended context-free notation that allows for regular expressions on the right-hand side (RHS) of rule. It does not change the practical uses and properties of CF grammars. You can do it as well by introducing new non-terminals. This was not really necessary here, but I found it convenient while doing the transformations. In retrospect, it would be simpler without it.

With this convention the rule $X\rightarrow Y\mid Z$ is equivalent to $X\rightarrow Y+Z$. Essentially the operators ¨$+$" and ¨$\mid$" have the same role.

Starting with your grammar, I first eliminate some non-terminals by replacing them by the corresponding RHS. I do that in the rule for $B$, and it gives:

$A\rightarrow B \mid a$
$B\rightarrow (b+c+f+g+i+k+l+n) \mid A(d+e+j+m) \mid Bh$

Then, substituting $A$ by the RHS of its rule: $A\rightarrow B \mid a$
$B\rightarrow (b+c+f+g+i+k+l+n) \mid (B+a)(d+e+j+m) \mid Bh$

and simplifying

$A\rightarrow B \mid a$
$B\rightarrow (b+c+f+g+i+k+l+n) \mid a(d+e+j+m) \mid B(h+d+e+j+m)$

And going back tu usual CF notation:

$A\rightarrow B \mid a$
$B\rightarrow BX \mid Y$
$X\rightarrow h \mid U$
$U\rightarrow d\mid e\mid j\mid m$
$Y\rightarrow aU \mid V$
$V\rightarrow b\mid c\mid f\mid g\mid i\mid k\mid l\mid n$

Now you only have to remove the left recursion from the $B$ rule in the usual way, replacing it by:

$B\rightarrow Y \mid YH$
$H\rightarrow X \mid XH$

and you are set.
> 3 votes

---
Tags: formal-languages, context-free, formal-grammars, left-recursion
---


# Question
Title: Two functions which can create any computable function by composing?
Do there exist two computable functions, a and b, which can construct every computable function by a finite serie of a's and b's which is function composed? Fx. let's take the serie, *a,b,a,b,b,a,a,a* , which function composed is the function, a∘b∘a∘b∘b∘a∘a∘a ( =*a(b(a(b(b(a(a(a(x))))))))* ), this function is the function described by the serie, *a,b,a,b,b,a,a,a*. And I want to know if every program can be described, by such serie.

If such functions exist, can you tell a example of a and b?

Thanks.

# Answer
> 2 votes
If such functions existed, they would constitute a computable enumeration of all computable functions, which is impossible for the following reason. Suppose you had a computable enumeration $f\_i$ of all computable functions. The function $g\colon i \mapsto f\_i(i) + 1$ is then computable, but by definition $g \neq f\_i$ for all $i$.

---
Tags: computability, turing-completeness
---


title: Packing unsplittable flows problem

text:
# Question
Title: Packing unsplittable flows problem
For a **single stream of elements** as input every elements should be routed into a fixed number of $k$ **output streams** trying to keep them balanced. In the following example $k=3$ :

Let's define as *flow* a sequence of **element of the same type** represented in the following diagrams using the same colour. Every flow must be routed into the same output stream keeping the elements ordered as found on the input stream:

Another correct solution that is more balanced than the previous one:

Considering also that:

* After a number of elements (called $timeout$) on the input stream without any element of the type of a specific flow, that flow should be considered ended and the element found should be the starting point of a new flow

I have some questions:

* Do you know any paper covering this kind of problems?
* What is a good algorithm that maximise the throughput, in other words keeping the output stream balanced?

**Update**

Thanks to @D.W. for the comments, here some clarifications:

* I am looking for an "online algorithm" where a "reasonable" latency is allowed therefore a lookahead-buffer/moving-window is definitely allowed
* I am not looking for theoretical guarantees, I am looking for an approximate algorithm to try against few hundreds test cases made of \[millions..billion\] elements with a mix of few *elephant* flows and many *mice* ones.
* The stream balance I am looking for should be considered over a period of time and not in an "absolute sense". In other words an algorithm that fills the first stream only then the second and then the third is as balanced as an algorithm that fill only the first stream

# Answer
The obvious algorithm is the greedy algorithm. Each time you see a new element that's not part of an existing flow, you identify which output stream currently has lowest occupancy, and route that element to that output stream. When you see an element that is part of an existing flow, you obviously have no freedom about where to route it; it has to go to the same output stream as the rest of the flow.

In an online setting where you must decide immediately where to route each element and where you have no information about the distribution of flow sizes or other domain knowledge, this is the natural strategy. When you see the first element of a flow, you have no information about how large the flow will be, and you must decide immediately where to route it based only upon the current state of the output streams. It's not clear whether there is any theoretical sense in which one can provably do better, if we have zero knowledge.

Now in practice I suspect you will typically have some a priori knowledge about the distribution of flow sizes. In this case, you can do bit better.

For instance, suppose you knew that all flows were either mice (they have 1 element) or elephants (they have 1000 elements). Then it would be easy to do better. When you get a new element that's not part of an existing flow, look at the existing flows in the output streams. For each existing flow in an output stream that has more than 1 element, you know exactly how many more elements are yet to be received in that flow, so you get a lower bound on how full that output stream will become once all of the remaining packets in the existing flows arrive (it is a lower bound since for the flows where you've only seen one packet you don't know yet whether they are mice or elephants). Call this the degree to which that output stream is "committed". Now you can use these lower bounds to pick which output stream is least committed, and route the new element to that output stream.

If you additionally know what fraction of flows are mice and what fraction are mice, instead of computing a lower bound you can compute an expected value and choose which output stream to route to by going for the choice where the expected value of the imbalance is minimized.

In general, you can use a greedy algorithm that uses expected output stream commitment as the basis for choosing an output stream. Let the random variable $X$ be distributed according to the distribution on flow sizes, i.e., $X$ is a random variable that counts the number of elements in a randomly chosen flow. Suppose you have seen $k$ elements in a particular flow, so far. Then the conditional expectation $\mathbb{E}(X | X\ge k)$ is in some sense your "best guess" at what the total flow size will be; it is the expected flow size, given that the flow contains at least $k$ elements. Thus, you can compute this for each active flow, and compute the sum of these values for each output stream, and route the new flow to the least-committed output stream. If you know the distribution of $X$, you should be able to compute $\mathbb{E}(X | X\ge k)$ easily.

This algorithm is fairly simple and should be pretty efficient: it requires $O(1)$ state per active flow (a counter to keep track of the number of elements seen in that flow so far). Assuming you can compute the conditional expectation in $O(1)$ time, the algorithm requires $O(1)$ time per element.

Whether this algorithm is sufficiently better than the simple greedy (choose the lightest output stream, based only upon its current size, not its expected commitment) in practice can only be answered by experimenting on some realistic data sets.
> -1 votes

---
Tags: algorithms, approximation, online-algorithms
---


# Question
Title: Covering grid with constrained rectangles
I need to place N rects on a 2-dimensional grid with constraints.

For the each rect height/width and placing limitations($x\_{min}$-$x\_{max}$) are known.

The problem is to place all rects on a grid with no intersections that every rect's bottom left $x$ is in rect's $x\_{min}$-$x\_{max}$.

I've implemented the naive solution where I just iterating over rects and incrementing $x$ by some fixed step while checking for intersections. If no place found then I increment $y$ and iterate again.

The question: I'm sure that there are algorithms/data structures that will help me to solve this task faster, but I do not know where to start.

# Answer
I suggest you use a constraint solver, like Minion. The following paper shows that they are effective for a related problem:

My thanks to András Salamon for pointing to this information.

You could also try using a SAT solver.
> 1 votes

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


# Question
Title: Are there any CS-trees named after flora-trees?
This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real world?

In computer science we have red-black trees, B-trees, quadtrees, and so on. In the biological sense of the word tree, we have palm trees, pine trees, redwood trees, etc.

My question: is there a word $w$ such that a $w$ tree could refer to a physical tree in the real world, or a mathematical object?

# Answer
> 4 votes
Robert Tarjan defines the *palm tree* in "Depth-first search and linear graph algorithms" (1972):

> Let $P$ be a directed graph of two disjoint edge sets, denoted $v \rightarrow w$ and $v \overset{-}{\rightarrow} w$ respectively. If $P$ satisfies the following properties:
>
> 1. The subgraph $T$ containing the edges $v \rightarrow w$ is a spanning tree of $P$;
> 2. Each edge not in $T$ connects a vertex with one of its ancestors in $T$. The edges $v \overset{-}{\rightarrow} w$ are called the *fronds* of $P$.

e.g.,

He goes on to prove that the directed graph generated by a depth-first search of a connected graph is a palm tree.

In Collective Tree Spanners and Routing in AT-free Related Graphs, Dragan, Yan, and Corneil construct a specific spanning tree that they call a *willow-tree.*

# Answer
> 3 votes
How about a banana tree? The organic kind are colloquially, but not botanically, trees.

---
Tags: terminology, data-structures, reference-request, trees
---


# Question
Title: Why does Pascal have a high code density?
The plots in http://blog.wolfram.com/2014/06/04/how-the-wolfram-language-measures-up/ seems to indicate that Pascal has a relatively high code density. What features of the language makes it so?

Follow-up question:

Does this explain why Pascal are often introduced in high schools as one of the first programming languages?

# Answer
> 2 votes
What makes Pascal dense is not the features it has, but the features it doesn't. Here is a small list of features that make other languages less dense:

* higher order functions
* classes and inheritance
* specialised syntax for sets, lists, hashes
* built in regular expression syntax
* good libraries

---
Tags: programming-languages
---


title: Model marbel toy with finite automata

text:
# Question
Title: Model marbel toy with finite automata
I'm resolving this question of Hopcroft and *et al* Book. Figure 1 below is a marble rolling-toy. A marble is dropped at A or B. Levers $x\_1,x\_2$ and $x\_3$ cause the marble to fall either to the left or to the right. Whenever a marble encounters a lever, it causes the lever to reverse after the marble passes, so the next will take the opposite branch.

I got resolve the question ...

a)Model this toy by finite automaton: To model this toy, a state is represented as sequence of three bits followed by r or a (previous input rejected or accepted). For instance, 010a, means left, right, left, accepted. Then the Transition table is

b)Informally describe the language of the automaton

but not b) question. How I will be able to resolve this question?

**EDIT** I see a solution here I modify my question using suggestions and that solution. According that solution exist a case:

Penultimate configuration interrupts is * \ / , where * means / or \\; and the ending is 1 and X mod 4 = 0, or (X-3) mod 4 = 0 (X is the numbers of 0's and 1's).

For my question, from this case I get the subcase

Penultimate configuration interrupts is * \ / , where * means / or \\; and the ending is 1 and X mod 4 = 0.

Then, the restrictions are: the number of 1's, without the ending, is even and the number of 0's is impar. I will be able to verify that configuration with that restrictions for few instances, but How I will be able to demonstrate that the $x\_2$ interrupt configuration is \\?

# Answer
Count $A$'s and $B$'s. The next $A$ will only exit at $D$ iff the first two levers are in right position. When does that happen? The first lever toggles at every $A$, but the second lever interacts with the $B$'s.

At the same time, the situation for $B$ is symmetric. The next $B$ will *not* exit $D$ only if both levers are left. When does that happen?
> 3 votes

---
Tags: automata, finite-automata
---


# Question
Title: Finding minimum path in a matrix algoritm
I'm looking for an algorithm that do the following thing.

Given $n$ the number of rows and columns of a matrix of positive integers.

Given $(x\_1,y\_1)$ the starting coordinates.

Given $(x\_2,y\_2)$ the ending coordinates.

and $k$ an integer.

This are some rules of how you can travel through the matrix:

* When stepped in some coordinate $(x,y)$ with a given value $w$, you can travel to $(x \pm w,y)$ or any value between this range or $(x ,y \pm w)$ or any value between this range.
* Also you can spend the integer $k$ in order to travel a little further in a row or a column. For example with $k=4$ you can travel to $(x ,y + w + 3)$ spending $3$ of your $k$. In this case, now you only have $k=1$ to spend.

The objective here is find the minimum path between $(x\_1,y\_1)$ and $(x\_2,y\_2)$.

I already implemented an algorithm that do this in $O(n^3k)$, the problem it's that given the implementation it's very difficult to justify its correctness.

How would you resolve this problem in a way that is easily shown it's correctness?

# Answer
> 1 votes
A conceptually simple approach is to form an unweighted graph with $(k+1)n^2$ vertices: one copy of the matrix for each possible number of credits remaining. Each edge represents a way you can travel in a single step. You start at $(x\_1,y\_1,k)$ and want to end at $(x\_1,y\_1,0)$. Now, look for the shortest path in this graph. There is a straightforward algorithm to find the shortest unweighted path in such a graph. Also, any good algorithms textbook will tell you how to justify its correctness.

This should produce an approach where it is very easy to justify its correctness. Its running time is not the best possible, but it's not too terrible, either. The running time is something like $O(n^2 k^2 w)$: the degree of each vertex is $O(kw)$, and there are $O(n^2 k)$ vertices, so $O(n^2 k^2 w)$ edges in total. This is $O(n^3 k^2)$, so not *too* much slower than your algorithm. If your primary criterion is ease of justifying correctness, this might be a simple solution.

---
Tags: algorithms, time-complexity
---


# Question
Title: Are there inherently ambiguous and deterministic context-free languages?
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.

Let us call a context-free language inherently ambiguous if and only if all context-free grammars which generate the language are ambiguous, and unambiguous otherwise.

An example of a deterministic, unambiguous language is the language: $$\\{a^{n}b^{n} \in \\{a, b\\}^{\*} | n \ge 0\\}$$ An example of a nondeterministic, unambiguous language is the language: $$\\{w \in \\{a, b\\}^{\*} | w = w^{R}\\}$$

From Wikipedia, an example of an inherently ambiguous context-free language is the following union of context-free languages, which must also be context-free: $$L = \\{a^{n}b^{m}c^{m}d^{n} \in \\{a, b, c, d\\}^{\*} | n, m \ge 0\\} \cup \\{a^{n}b^{n}c^{m}d^{m} \in \\{a, b, c, d\\}^{\*} | n, m \ge 0\\}$$

Now for the questions:

1. Is it known whether there exists a deterministic, inherently ambiguous context-free language? If so, is there an (easy) example?
2. Is it known whether there exists a nondeterministic, inherently ambiguous context-free language? If so, is there an (easy) example?

Clearly, since an inherently ambiguous context-free language exists ($L$ is an example), the answer to one of these questions is easy, if it is known whether $L$ is deterministic or nondeterministic. I also assume that it's true that if there's a deterministic one, there's bound to be a nondeterministic one as well... but I've been surprised before. References are appreciated, and apologies in advance if this is a well-known, celebrated result (in which case, I'm completely unaware of it).

# Answer
If a language $L$ is deterministic, it is accepted by some deterministic push-down automaton, which in turn means there is some LR(1) grammar describing the language, and as every LR(1) grammar is unambiguous, this means that $L$ cannot be inherently ambiguous. Knuth proved this in his paper in which he introduced LR(1) (On the Translation of Languages from Left to Right).

A language can be described by some context-free grammar if and only if it can be recognized by some nondeterministic automaton. As a special case of this, inherently ambiguous context-free grammars can be parsed by some nondeterministic automaton.

On a final note, any deterministic push-down automaton is also nondeterministic (this is the case for just about anything that can be nondeterministic, for a reasonable definition of nondeterminism).
> 33 votes

# Answer
reading wikipedia & the answer & your comment on it, re (Q2) to state outright, all inherently ambiguous CFLs must be nondeterministic under the std defn (incl your own example!). ran across this ref
> 0 votes

---
Tags: formal-languages, automata, formal-grammars, pushdown-automata
---


# Question
Title: Greedily Schedule Events based on value/hours
Suppose we are given a list of $n$ events $E = \\{E\_1, E\_2, \ldots, E\_n\\}$ where each $E\_i$ is represented by $(s\_i, h\_i, v\_i)$ or $(start, hours, value)$. So if you attend an **entire** event that lasts 5hrs and has a value of 10 then you will gain 10 points. If you only attend for 3 hours, you only get 3\*(10/5) = 6 points. The output that the algorithm should produce is the maximum number of points that can be obtained by attending combinations of various events. **Note:** you are allowed to leave and come back to an event.

**My Algorithm (pseudocode):**

* Sort all the events $E$ by order of their $v\_i/h\_i$ ratio to produce a new set of events $E'$ such that $E'\[1\]$ has a higher *value/hours* ratio than $E'\[2\]$, $E'\[3\]$, etc...
* $max = 0$
* For each event $e \in E'$
    + $h =$ hours that have not yet been taken
    + $max\ += h\* (e\_{v\_i}/e\_{h\_i})$

**Note:** I did not specify in the algorithm how to determine the hours that have been scheduled/taken already but you can assume that there is an array that flags hours that have been scheduled.

I do believe that my algorithm gives the optimal result, but how do I prove this?

# Answer
I'm assuming that the value given to $h$ in each step is "number of hours during the running of the event, which are not yet covered". (Your wording is somewhat ambiguous.)

In the following I'll assume that all events start and end at full hours. For real valued times, just replace hours by an amount of time small enough that all the differences between relevant moments (start and end times) are multiples of that amount.

From the constraints given, we see that the event visited at one point in time has no influence on the profit we can make at a different moment in time. Thus, the optimal solution will be to visit the most profitable event at each point in time, i.e. during each hour. Now, we only have to show that the algorithm achieves this:

Assume that there is an hour $h$ during which the algorithm suggests to visit event $e$, while visiting $e'$ would be more profitable. Since $e'$ is more profitable, it will have been put before $e$ during the first step of the algorithm. Furthermore, since $e'$ has been scheduled for $h$, $h$ must have been available when the algorithm processed $e$ and (since the algorithm never frees an hour) also when it processed $e'$. But this means that the algorithm would have scheduled $e'$ for hour $h$, contradicting our assumption. Thus we conclude that the algorithm is correct.
> 2 votes

# Answer
In the following I'll assume that all events start and end at full hours. For real valued times, just replace hours by an amount of time small enough that all the differences between relevant moments (start and end times) are multiples of that amount.

Since your algorithm is a greedy algorithm, its correctness can be proven by showing that the underlying structure is a matroid.

In your case the base set $E$ of the matroid would be all pairs $(e, h)$ (called visits in the following), where event $e$ runs during hour $h$. The weight of $(e,h)$ will be the respective *value/hours* ratio.

We will interpret adding $(e, h)$ to the result set as visiting $e$ during hour $h$. Thus the family of independent sets $I$ should contain all those subsets of $E$ where no two events are scheduled for the same hour, i.e. they contain no pairs $(e,h)$ and $(e',h)$, where $e\ne e'$. (The algorithm will only create such sets as intermediate or final results during its run, and each such set can occur given an appropriate set of weights on the elements of the base set.)

Now we have to show that $(E,I)$ actually is a matroid:

1. $\emptyset$ does not contain any colliding visits, so it is in $I$.
2. If $A\in I$ and $B \subset A$, then $B$ can not contain any colliding visits, as those would also be in $A$. So $B\in I$.
3. If $A\in I$ and $|B|\<|A|$, there has to be an hour $h$ so that $A$ contains a visit $(e,h)$ but $B$ does not contain a visit $(e',h)$. (Remember that $A$ may cantain at most one visit for each hour.) Thus $B\cup \\{(e,h)\\} \in I$.

The canonical greedy algorithm resulting from this would split each event into visits for each hour. The first step then sorts the visits and the loop considers the visits in order of profit. The algorithm from the question can be considered as doing the same, but grouping visits for the same event together for the sorting. This is ok, since we have the constraint, that the profits for each of these visits are equal. So we can conclude that the algorithm is correct.
> 1 votes

---
Tags: algorithms, efficiency, greedy-algorithms
---


title: does every CFL have an ambiguous CFG?

text:
# Question
Title: does every CFL have an ambiguous CFG?
some questions have been popping up recently on ambiguity in CFLs/CFGs which can have subtleties (eg languages vs grammars & ambiguity vs inherent ambiguity). wikipedia states:

> *Many* \[context free?\] languages admit both ambiguous and unambiguous grammars, while some languages admit only ambiguous grammars.

the sentence is phrased in wikipedia without the "CFL" inserted but am now wondering what effect it has on the logic. after pondering the technical defn of ambiguity (on wikipedia pg) & thinking about it a bit my question:

> does *every* CFL have an ambiguous CFG? if not what is a counterexample ie a CFL that does not have *(any)* ambiguous CFG?

(the question arose in that every CFL has multiple CFGs, ie a CFG is only unique to a CFL under additional restrictions, and it seems that given any (unambiguous) CFG one could add small chgs/productions rules to get an equivalent ambiguous CFG...? is this trivial? but rarely pointed out anywhere?)

somewhat related question somewhat involved in sparking this one: Are there inherently ambiguous and deterministic context-free languages?

# Answer
Every nonempty context-free language has an ambiguous grammar. Consider any context-free grammar for the language with starting symbol $S$. We add new non-terminals $S',A',B'$, make $S'$ the new starting symbol, and add the following rules: $$ \begin{align\*} &S' \to A' \\ &S' \to B' \\ &A' \to S \\ &B' \to S \end{align\*} $$
> 12 votes

# Answer
The following statement seems mathematically correct, though confusing.

Any grammar for the empty language $\varnothing$ is unambiguous: it has no strings for which there are two different valid derivation trees.
> 6 votes

---
Tags: formal-languages, formal-grammars, ambiguity
---


# Question
Title: How to design xml schema for digital circuits?
how can i design XML Schema for logical and digital circuits?

i cant find any help or manual for this work

for example i have a digital circuits with AND OR NOR ,... gates

now i want design xml and schema for that

thanks for help

soryy for bad english

# Answer
> 1 votes
A simple example.

Assume the following circuit in symbolic notation:

Cir = ((A OR B) AND (C OR D)) OR (NOT(D) AND F), where OR , AND, NOT etc can be realized with serial/parallel connections etc..

XML scheme proposition:

```
<circuit>
    <gate-or>
        <element>
            <gate-and>
                <element>
                    <gate-or>
                        <element>A</element>
                        <element>B</element>
                    </gate-or>
                </element>
                <element>
                    <gate-or>
                        <element>C</element>
                        <element>D</element>
                    </gate-or>
                </element>
            </gate-and>
        </element>
        <element>
            <gate-and>
                <element>
                    <gate-not>D</gate-not>
                </element>
                <element>F</element>
            </gate-and>
        </element>
    </gate-or>
</circuit>

```

This is an example xml-scheme where the root element is circuit and can have gates or elements as children and each gate (eg gate-or or gate-and) can have elements as children etc..

Of course this is very verbose , a yaml or json representation scheme would be lighter

---
Tags: data-structures, logic, circuits
---


# Question
Title: Correspondence between automata and formal grammars?
From Wikipedia

> Since there is **a one-to-one correspondence** between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string to be recognized by the automaton.

Note: If I am correct, "such grammars" mean context-sensitive grammars.

I wonder if the quote means that:

> a context-sensitive language can have multiple context-sensitive grammars that can generate it, and multiple linearly bounded machines that can have it as their recognized languages, and there exists a one-to-one correspondence between the linearly bounded machines and the context-sensitive grammars, for the context-sensitive language.

**More generally**, a recursively enumerable formal language can have multiple formal grammars that can generate it, and multiple Turing machines that can have it as their recognized languages. So I wonder if there exists a one-to-one correspondence between Turing machines and formal grammars, for a recursively enumerable formal language.

Given a formal grammar, how can we construct a Turing machine to have the language generated by the grammar as its recognized language?

Conversely, given a Turing machine, how can we construct a formal grammar which can generate the language which is the one recongized by the Turing machine?

# Answer
The expression "one-to-one correspondence" seems a little too strong for me. It suggests that for every grammar there is a specific automaton. It should be read as: for every grammar an automaton can be constructed for the same language and vice-versa.

Context-sensitive languages are accepted by linear bounded automata and generated by context-sensitive grammars. Context-sensitive grammars have productions of the form $\beta A \gamma \to \beta\alpha\gamma$ where $A$ is a nonterminal and $\alpha$ is nonempty. They are equivalent to length-increasing (more properly noncontracting, or monotone) grammars, which have the form $\alpha\to \beta$ where $|\alpha| \le |\beta|$ (usually $\alpha$ is assumed to include at least one nonterminal).

The languages of Turing machines are generated by unrestricted, or type-0, grammars. See Chomsky Hierarchy.
> 7 votes

# Answer
> Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string to be recognized by the automaton.

that wikipedia statement can be understood as that there is a 1-1 correspondence between *unique* LBAs and CSLs/CSGs. in other words every "unique" CSL has an LBA and vice versa but multiple LBAs can be equivalent (to the same CSL). in other words the same CSL can be "encoded" in different LBAs & CSGs. but note that determining equivalence of CSLs (as encoded eg as CSGs or LBAs) is undecidable.\[1\]

for your other question about TMs←→grammars conversions see \[2\] which also hints at both directions.

\[1\] Which properties of context sensitive languages are decidable?

\[2\] How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?
> 2 votes

---
Tags: formal-languages, terminology, automata, formal-grammars
---


title: Proof for factors of a number

text:
# Question
Title: Proof for factors of a number
I was trying to prove the following:

```
  if  x%(x/2) != 0 or x%(x/2) == 0

  then x%(x/y) != 0 or x%(x/y) == 0  such that y = [2,4)

```

So I am trying to figure out whether a number can have a factor in between its half and its fourth. I am trying to use it in a factoring algorithm.

# Answer
If a number $n$ has a factor $m$ in the range $n/4 \leq m \leq n/2$, then the quotient $k = n/m$ satisfies $2 \leq k \leq 4$, that is, $k \in \\{2,3,4\\}$. This should give you a fast algorithm for determining whether such a factor $m$ exists.
> 1 votes

# Answer
Yuval Filmus' answer is better than this brute force attempt

Pseudo-code following:

```
Input: n (number to check if it has a factor in [n/4, n/2])

n1 = [n/4]
n2 = [n/2]

for k in n1..n2

     if ( n mod k === 0) return true

return false

```

Of course the previous algorithm will do what is asked in the question, however since a factor of a number (eg a prime) needs at most $\sqrt{n}$ it would not be very efficient
> 0 votes

---
Tags: factoring, proof-assistants
---


# Question
Title: Checking whether a number is a square or higher power modulo n
Is there an algorithm to check whether an integer $x$ is a square modulo $n$, where $n$ is an integer whose factorization we do not know? Is the Jacobi symbol helpful?

What about higher powers, e.g., testing whether $x$ is a $k$th power modulo $n$?

# Answer
> 2 votes
## Recognizing squares

No. As far as we know, there is no efficient algorithm to tell whether $x$ is a square modulo $n$, if the factorization of $n$ is not known.

This is the quadratic residuosity problem; see Wikipedia for an overview. The conjecture is that the quadratic residuosity problem is as hard as factoring (i.e., the best algorithm is to first factor $n$). In fact, some cryptosystems have been built whose security rests on this assumption.

The best we can do is to use the Jacobi symbol. If the Jacobi symbol $\left(\frac{x}{n}\right)$ is $-1$, then $x$ is certainly not a square modulo $n$. However, if $\left(\frac{x}{n}\right)=+1$, then $x$ might or might not be a square. In particular, if $n$ is the product of $k$ large, distinct primes, then about $1/2^k$ of all numbers modulo $n$ are squares; about $1/2$ have Jacobi symbol $+1$; so about $1/2^{k-1}$ of all numbers with Jacobi symbol $+1$ are squares, and the remaining are non-squares. Thus, the Jacobi symbol is not enough to determine whether $x$ is a square modulo $n$.

## When $n$ has known factorization

If the factorization of $n$ is known, then you can easily determine whether $x$ is a square modulo $n$ or not by using the Chinese remainder theorem. Similarly for higher powers; again, use the Chinese remainder theorem; then check whether $x^{(p^e-p^{e-1})/k} \equiv 1 \pmod{p^e}$, for each prime $p^e$ dividing $n$.

(You might also like the following post, which discusses not only how to detect whether it is a $k$th power but whether you can compute the $k$th root, when working modulo a prime $p$: https://crypto.stackexchange.com/q/6518/351. If the factorization of $n$ is known, this will determine when you can compute $k$th roots modulo $n$.)

So, in the rest of this answer, I'm assuming the factorization of $n$ is unknown, and $n$ is hard to factor.

## Recognizing higher powers

What if we want to test whether $x$ is a $k$th power modulo $n$? Here things bifurcate, according to whether $k$ is relatively prime to $\varphi(n)$ or not.

If $k$ is relatively prime to $\varphi(n)$, then every number $x$ that is relatively prime to $n$ is a $k$th power modulo $n$. This follows from the fact that $(x^j)^k \equiv = x \pmod n$, where $j \equiv k^{-1} \pmod n$. (The case where $x$ is not relatively prime to $n$ is easy to handle: you compute $d=\gcd(x,n)$ and split the problem into one of determining whether $x$ is a $k$th power modulo $d$ and whether $x$ is a $k$th power modulo $n/d$.)

If $k$ divides $\varphi(n)$, then we are in a situation analogous to that of detecting squares. This is only case where I'm not 100% certain about the answer, and I don't know whether it has been studied or not. (I would conjecture that detecting $k$th powers modulo $n$ is probably also hard if $n$ is hard to factor, but I have no proof.)

If $k$ is not relatively prime to $\varphi(n)$ but does not divide $\varphi(n)$, let $k'= \gcd(k,\varphi(n))$. Then the question of whether $x$ is a $k$th power reduces to the question of whether $x$ is a $k'$th power, which is discussed above.

---
Tags: algorithms, integers, number-theory, factoring
---


# Question
Title: checking if there're equal bits in binary string
We have two binary strings, $X$ and $Y$, in two different computers. Both of them in length $n$. The computers can communicate by sending bits to each other.

We have to build randomized algorithm to check whether there's an index $i$ such that $X\_i=Y\_i$. We can send only $O(\log n)$ bits between the computers.

If there's no such index the algorithm will always return "false". If there's such index, the algorithm will return "true" in probability 0.5 (at least).

Any suggestions?

# Answer
Hint: This is the classical problem of EQUALITY in disguise, a problem whose randomized communication complexity is known to be $O(\log n)$. In other words, you can reduce your problem to EQUALITY.
> 1 votes

---
Tags: randomized-algorithms, randomness
---


# Question
Title: Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set
I am confronted with task to find polynomial time complexity solution for weighted hitting set problem. I have found that usual hitting set problem is NP-complete and therefore the task seems to be contradictory.

But there are several other reformulations of this problem. E.g. d-Hitting set problem can be solved in polynomial time (when each class or set contains no more than d elements).

Maybe the weighted case has completely different algorithms and complexity estimation? Apparently the non-weighted problem is the special case of weighted one and therefore there should not be different complexity estimation, isn't so?

# Answer
The unweighted case is a special case of the weighted case, corresponding to all weights being equal. Therefore the unweighted case is *easier* or *as hard as* the weighted case. The reason is that given an algorithm for the weighted case, you can use it to solve an unweighted problem by endowing the relevant objects with unit weight.
> 3 votes

---
Tags: complexity-theory, time-complexity, np-complete, optimization
---


# Question
Title: Is there a term for a tree where the values of the children add up to a fixed value?
I have a tree with percentages of the following form

```
        100
       /   \
      /     \
     /       \
    /         \
   25          75
  /  \       / | \
 15  10    35  10 30
    /  \      / \
   1    9    5   5
      / | \
     3  3  3

```

So child nodes are added up in the parent node.

Does a tree with this attribute has a already defined name in the algorithmic world?

---

Thanks for the positive feedback so far.

In this case the nodes hold actually values which are added up in the parent and the example tree shows the percentages of these values in comparison to the root.

I have to implement an algorithm to find those nodes which have the biggest impact and add up to 95 percent.

Since the problem description in case what "biggest impact" means, is pretty open I was thinking about setting the percentage in relation to its child nodes + itself.

Therefore node 25 would have a weight of 25/8, node 75 would have on of 75/6 and so on.

In the next step I would order by weight, min amount of children, in descending order and add up the percentages of the nodes until I reach 95 percent. Always removing a sub node from the result when the parent is added.

I hope I could make myself clear

# Answer
> 2 votes
Building off of Matt Ball's answer, there's an implementation of this here on SO, and there's some mention of it here. It sounds like a second-cousin of a heap, and it's the reverse of a Fenwick tree, in some sense.

However, it's hard to imagine a situation where this would be useful.

# Answer
> 2 votes
I believe it is creatively called a "sum tree."

Algorithmically it's not especially useful nor interesting because it is not efficiently modifiable.

---
Tags: data-structures
---


# Question
Title: Reducing a system of two boolean algebra assertions to a single one
Given a system of two Boolean Algebra equalities

```
a = b.
c = d.

```

one can exhibit a single equation

```
F(a,b,c,d) = 0.

```

which is equivalent to the former system. (Symmetric difference is pivotal for constructing such quaternary operation F(a,b,c,d)).

Questions:

* Is there binary operation `x ? y` (infix notation) such that

a ? c = b ? d.

is equivalent to the original system?
* Is there binary operation `x ? y` such that

a ? b = c ? d.

is equivalent to the original system?

*Edit (June 13):* The question is more subtle than I managed to convey. Boolean algebra is a finitely definable variety. I was wondering if we can get a single axiom system by combining identities. Padmanabhan proved in 1968 that every definable class of lattices (such as BA) can be defined by a single identity within the class of lattices. The key observation in his method is equipping the identities

```
a = b.
c = d.

```

with *disjoint* sets of variables. Then, simple disjunction

```
a v c = b v d.

```

would do.

# Answer
No. There is no such binary operation.

This is easy to prove with a counting argument. Given a candidate binary operation $?$, count the number $n$ of boolean values $x,y$ such that $x?y$ is true. Out of the 16 possible values for $a,b,c,d$, exactly $m=n^2+(4-n)^2$ of them will satisfy $a?c = b?d$. The possible values for $m$ are $m \in \\{16,10,8\\}$. However, there are only 4 possible values of $a,b,c,d$ such that $a=b$ and $c=d$, which is not in the set of possible values for $m$.

Or, you could do as David Clarke suggests and write a tiny program to enumerate all possibilities. Frankly, you probably should have done that before asking in any case; that would have helped you ask a more specific question, such as "I know no such binary operation exists; can you give me any insight why not?".
> 3 votes

---
Tags: boolean-algebra
---


# Question
Title: Bellman-Ford without getting stopped by negative cycles
Let $s$ be the source vertex. In the standard Bellman-Ford algorithm (e.g. the version found in CLRS), when there is a negative cycle reachable form $s$, the algorithm will return that a negative cycle is found.

But let's say I am interested in the shortest path from $s$ to some vertex $a$, and it might be that there is a negative cycle reachable from $s$, but it could also be that no such negative cycles have a path to $a$. So technically there is still a shortest path from $s$ to $a$. But Bellman-Ford would still say "negative cycle detected" although it is irrelevant! How might Bellman-Ford be modified to still spit out either the shortest path or that there is no shortest path?

**Attempt:** At first I saw thinking of running Bellman-Ford until $2n$ (or some large number) and then seeing if the value for $s$ to $a$ stays stable, but I found an example that invalidates this. It appears that I must find all negative cycles reachable from $s$ and check if each of them can reach $a$. That seems like an immense amount of work! So is there any clever way to do this?

# Answer
Solution 1: First pre-process the graph to remove all vertices that cannot reach $a$. This can be done using depth-first search (backwards in the graph; i.e., in the reverse graph), in linear time. You can also pre-process the graph to remove all vertices that are not reachable from $s$, again in linear time.

Solution 2: Run Bellman-Ford for $2n$ iterations and see if the value from $s$ to $a$ stays stable for the last $n$ iterations. This should work: any simple path (with no cycle) from $s$ to $a$ must use at most $n-1$ edges, and if there is a non-simple path from $s$ to $a$ traversing a negative-weight cycle, then there is one with at most $2n-1$ edges. You might want to double-check your example; maybe you made a mistake when simulating Bellman-Ford by hand.
> 2 votes

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


# Question
Title: choice of data structure for domino tilings
A domino tiling is a tesselation of a region in the plane by 2 × 1 squares. What is a good data type for storing and manipulating such objects?

In my current manipulation, use an array to store all the half-squares numbering them 1-2 for a horizontal domino, 3 4 for a vertical. It's not ideal but I can draw the tiling in `ASCII` or using a graphics editor.

```
     _ _         _ _
1 2 |_ _|  3 3  | | |
1 2 |_ _|  4 4  |_|_|

```

In some applications, I have to identify specific features within array. For example, I might have to count all instances of 2 ×2 squares of dominos in my array, excluding things like

```
 _ _
 _|_   2 1
|_ _|  1 2

```

These queries are not difficult, but they make me start to question my use of arrays.

# Answer
There is an alternative, more compact kind of array representation which might be better if you are working with diamonds as defined in the paper you linked (for axis aligned rectangles you need to find the smallest covering diamond).

The idea is to checkerboard the plane and assign a 2-bit number to each "black" cell, such that the number represents the orientation of the domino relative to the cell. Consider for example:

where $0$ means "horizontal domino pointing east", $1$ means "vertical domino pointing north", etc. Tilting the numbers clockwise yields the array representation:

$$A = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 2 & 3 & 3 & 0 \\ 2 & 3 & 0 & 2 \\ 2 & 1 & 0 & 1 \\ 2 & 2 & 2 & 1 \\ \end{pmatrix}$$

To find two dominos forming a square search for a $0$ adjacent to a $2$ or a $1$ adjacent to a $3$. Now, if you deal with big tesselations and are into implemtations sped up by bit operations, you can do this:

Let $A$ be a $\\{0,1,2,3\\}^{m \times n}$ matrix, $b$ be the bit mask $\dots 01010101$, then we can represent the $i^{th}$ row of $A$ as a single integer by using bit-concatenation:

$$r\_i = \bigvee\_{j=1}^n (a\_{ij} \<\< 2(j-1))$$

where $\vee$ denotes a bitwise OR and $\<\<$ a leftshift. Denoting $\oplus$ as bitwise XOR we can calculate

$$s\_i=(r\_i \text{ mod } 2^{2n}) \oplus (r\_i \>\> 2) \oplus b \\ t\_i=r\_i \oplus r\_{i+1} \oplus b, ~~i \< m$$

Then domino $a\_{ij}$ and domino $a\_{ij+1}$ form a square iff bits $(s\_i)\_{2j-2}$ and $(s\_i)\_{2j-1}$ are both $1$. Likewise domino $a\_{ij}$ and domino $a\_{i+1j}$ do so iff bits $(t\_i)\_{2j-2}$ and $(t\_i)\_{2j-1}$ are both $1$.

Example calculation for rows 1,2 (little-endian!):

```
r_1    00 00 00 00
r_2    10 11 11 00
b      01 01 01 01
xor    -----------
       11 10 10 01

```

Therefore $a\_{11}$ and $a\_{21}$ form a square.
> 3 votes

# Answer
i had a similar issue in order to store (crossword) puzzle grids, which can have different types of squares (eg letter cells, definition cells, images, etc..)

The representation was this (which can be easily serialized into json)

```
dimensions:{ rows, columns, etc..}  // for my example this covers almost all default cells

```

then a series of attributes describing any cells that are different from default cells

eg.

```
separators: [{row: r, column: c}, {row: r1, column: c2}, ..],
images: [{row1: r1, column1: c1, row2: r2, column2: c2, image-data: ..}, ..]

```

This is only illustrative example, the logic behind this is that the default cells are covered by using just the dimensions and any other types of squares are explicitly described, so in effect this on average should produce minimal representations
> 1 votes

---
Tags: data-structures, combinatorics, tiling
---


# Question
Title: Understanding non-linear dimensionality reduction algorithm (locally linear embedding)
I have a question about Locally Linear Embedding. I am trying to study this algorithm and implement it for better understanding. I have read An Introduction to Locally Linear Embedding. However, I don't think I really understood this algorithm. There are several questions I want to ask.

1. I understand that this algorithm takes some high dimensional data set and reduce it into lower dimensional data set while keeping some geometric features of the original data set. In the article, they use S-shape manifold, sample data from the manifold and reduce it into lower dimension. So I see from the picture that each region on the manifold specified by colors are conserved. But I don't think I understood why do we need this kind of reduction. I don't think it is guaranteed that any data set can be reduced to two or three dimension so that we can visualize the original data set which means how the geometric features are conserved. Can anyone explain this with some example?
2. I don't really understand how this algorithm can be implemented. The paper shows the reconstruction error $\epsilon(W)=\sum\_i \left| X\_i - \sum\_jW\_{ij}X\_j \right|^2$ and says`The weights summarize the contribution of the jth data point to ith reconstruction.` I don't understand what this sentence means and how the weight matrix $W\_{ij}$ can be constructed. Each $X\_i$ represents each column in the data?? Then how can I understand $\sum\_jW\_{ij}X\_j$?? Can anyone explain this?
3. The paper says that the data reduced into lower dimension can be constructed by the closest points of each data points. How is this work?

Thank you

# Answer
To answer your first question:

Usually we want to reduce the dimension, because dealing with high-dimensional data is a pain: (a) algorithms for dealing with high-dimensional data tend to have higher computational complexity, and (b) high-dimensional data is hard to visualize and hard to understand. If you can reduce the dimension without significant loss of effectiveness of the subsequent computational task, that can be useful.
> 2 votes

---
Tags: machine-learning
---


# Question
Title: Is proof of totality of a semantic function for binary numbers cicular?
I think the following proof found in a textbook is circular, since the proof for case n=n'0 assumes the case n=n'1 and vice versa. Am I missing something?

Proof that the semantic function N is a total function from binary strings into the integers:

> Let N be defined thusly:
>
> N(0) = 0; N(1) = 1; N(n0) = 2\*N(n); N(n1) = 2\*N(n) + 1;
>
> For any n, there is one and only on integer mapped to by N(n), that is to say, N is a total function from binary strings into the integers. (A)
>
> In the case n = 0, there is only one way to evaluate N(n) and that is with N(n) = N(0) = 0; hence (A) clearly holds. The proof for the case n = 1 is similar.
>
> In the case n = n'0, we have only one way to evaluate N(n) and that is with N(n) = N(n'0) = 2\*N(n'). Assuming by induction that (A) holds for N(n'), (A) clearly holds for N(n). The proof for n = n'1 is similar.
>
> QED

In the second part of the proof, for the case n = n'0 you have to assume for induction that * holds for n = n'1, and vice versa. Does this not lead to a circular dependency in the proof?

# Answer
The proof is by induction on the length of the string. You're proving the inductive claim for *all* strings of length $n$, both those terminating in $0$ and those terminating in $1$. The proof goes by considering these two cases, but you're assuming and proving the inductive hypothesis for all strings of a particular length at once.
> 2 votes

---
Tags: proof-techniques, semantics
---


title: How to store factorials?

text:
# Question
Title: How to store factorials?
Can someone help me to store the factorial of large numbers such as 100! efficiently?

UPDATE: obviously, storing the argument rather than the factorial digits themselves achieves a significant saving. The true challenge is to find a data compression scheme that achieves a significant compression ratio, but with a lighter computational complexity than recomputing the factorial(s) from the argument.

More precisely, can you design an algorithm to produce all decimal digits of $n!$, for $n\le N$, using $o(N\log N!)$ storage and small computational cost, such as the lower bound $O(\log n!)$.

# Answer
We can calculate 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000. You can store this in any way you want: as `100!`, as the ASCII string `93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000`, as a Unicode string, or in binary in any number of formats. It all depends on what you want to do with the value. If you want to display the value on screen as a decimal, you might as well store the decimal string. If you want to do arithmetic, then you should be using a library for dealing with "big numbers" such as GMP, and in this case the library will provide its own means for storing numbers. If you're just interested in storing the expression 100!, and intend to use it in a computer algebra software (CAS), you might as well store it as just `100!`.
> 2 votes

---
Tags: integers, encoding-scheme, storage
---


# Question
Title: How many Turing Machines are there that run in time $t$ or in space $s$ on inputs of length $k$?
I think half the battle in answering this question lies in formulating it precisely! A search engine doesn't turn up much, so I was wondering if this is a well-known or well-studied question.

My thoughts: I think the most straightforward way to formulate this question is as in my title: Given constants $t,s,k \in \mathbb{N}$, how many TMs are there that run in $t$ steps or fewer on all inputs of size $k$, and how many TMs are there that use $s$ tape squares or fewer on all inputs of size $k$? This seems like the most direct and simple way to ask the question, but we might want to restate it in a different way -- for example, given a function $p(k)$, how many TMs are there that run in time $p(k)$ on inputs of size $k$ for all $k$ (or how "dense" are these TMs)? This seems harder to me.

We should probably fix a tape alphabet (or a Godel numbering??). We could consider two TMs with different but isomorphic state diagrams to be the same or different, either way.

The immediate problem is that there are an infinite number: Take any TM that satisfies the criteria and add "dead states". I can think of two ways to deal with this. The first (which I don't like) is to add an additional parameter: how many TMs whose description has length $\leq L$ satisfy the criteria? The second (which I prefer) is to consider two TMs *equivalent* on inputs of size $\leq k$ if, for all such inputs, the TMs have exactly the same behavior (enter the same states and write/move on the tape identically). Then we would restrict to the minimal TM in each equivalence class, or just ask how many equivalence classes satisfy the criteria.

Edit: As pointed out by Vor in the comments, the problem with the second approach is that it's basically the same as a circuit at that point. So how about the first one? Or is there a nicer way to formalize this question?

Any references/literature, thoughts, or answers would be very interesting and appreciated!

# Answer
Given $k$, consider the set of $\mathcal{M}\_k = \\{ M\_i \mid i \in \mathbb{N} \\}$ with $M\_i$ defined by

```
if |x| = k
  accept
else
  simulate TM i on x

```

The set $\mathcal{M}\_k$ is a subset of the Turing machines you want to count for all $s,t$. Since it is infinite, the set you want to count is infinite, too.

As far as I can tell, this result is stable against all restrictions you impose as long as you don't restrict the set of all feasible Turing machines to be finite.
> 3 votes

# Answer
Your question is closely related to the busy beaver problem. It asks for the maximum number of symbols an $n$-state Turing machine with 2 output symbols that always halts writes before halting. The function of $n$ defined this way is not computable.
> 1 votes

# Answer
you ask some questions and formulate some interesting ideas that generally nearly relate to open questions about complexity class separations. for example P=?NP can be reformulated as asking about "how many" NP(-hard) languages can be executed in P time. however there are probably not too many theoretical (or otherwise) results in this area. there are some theoretical papers that do give bounds on both time/space complexity of SAT that would touch on your question. however maybe the closest research to this is empirical analysis of TMs, which is hinted at in the other answer by vonbrand eg with busy beaver research.

there is similar but relatively rare research that looks at empirically-generated TMs with "clocks" eg P-time etc. here is one such ref from 2013. it enumerates TMs with P-time clocks and looks at/for fractal patterns in the resulting/generated "time-space diagrams" (also called "computational tableaus"). another approach is to look at "small finite" samples eg limiting $t, s, k$ (and also other parameters like enumerated TM states).
> 1 votes

---
Tags: complexity-theory, reference-request, turing-machines, combinatorics
---


# Question
Title: Fast algorithm for matrix chain multiplication in special case
An exercise from the book Foundations of Algorithms Using Java Pseudocode:

> Write an efficient algorithm that will find an optimal order for multiplying $n$ matrices $A\_1 \times A\_2 \times \ldots \times A\_n$, where the dimension of each matrix is $1 \times 1$, $1 \times d$, $d \times 1$ or $d \times d$ for some constant $d$.

The standard dynamic programming approach is $\mathcal{O}(n^3)$, thus probably not much efficient. Hu-Shing algorithm (a link to their paper) works in $\mathcal{O}(n \log n)$ but it's rather an overkill for much simplified version of the problem. I have a concept for quite simple, greedy based, algorithm working in $\mathcal{O}(n \log n)$ but the main difficulty I have is in proving its corectness. First, let's observe what is the cost of multiplication of two matrices of given dimensions and what are the dimensions of their product (column - first matrix, row - second matrix):

```
  Cost:                           Product:
  dxd |  -   -  d^2 d^3           dxd |  -   -  dx1 dxd
  1xd |  -   -   d  d^2           1xd |  -   -  1x1 1xd
  dx1 |  d  d^2  -   -            dx1 | dx1 dxd  -   -
  1x1 |  1   d   -   -            1x1 | 1x1 1xd  -   -
      +----------------               +----------------
        1x1 1xd dx1 dxd                 1x1 1xd dx1 dxd

```

If we look at the tables above more closely, we can notice a nice property, that a cheap multiplication gives as a result a matrix that is also likely to be multiplied cheaply. A bit more formally, if we imagine a graph with four nodes representing dimensions of matrix and declare that there is a weighted arc from node M to N if and only if matrix M multiplied by some matrix gives matrix N, with weight of this arc equal to the cost of that multiplication (so every node has exactly two outgoing arcs and exactly two ingoing arcs), then we'll see that graph has two connected components, one of which has arcs that tend to have smaller weights than these in the other one.

This would suggest sticking to that cheap CC at any cost (hehe) and order types of multiplications that we prefer in this way (for brevity, now \[ab\] denotes a matrix of dimensions $a \times b$):

```
[11]x[11] < [1d]x[d1] < [11]x[1d] < [d1]x[11] <
[1d]x[dd] < [dd]x[d1] < [d1]x[1d] < [dd]x[dd] (*)

```

So a greedy approach would be to have a priority queue which maintains the order of matrices in the following way:

```
matrix [ab] comes before matrix [cd] if and only if
[ab]x[a'b'] < [cd]x[c'd'] with respect to order (*),
where [a'b'] is a matrix immediately to the right of matrix [ab],
and [c'd'] similarly.

```

and always take its minimum, memorize somewhere that we multiply that matrix with its neighbour on the right, and then replace these two matrices with their product.

Does anyone see a counterexample to this approach or have an idea for a proof of correctness?

## UPDATE

I was too convinced that it works just after testing few trivial inputs that passed, that I focused only on devising a proof. However, thanks to **D.W.** I sobered up and tested it on bigger input - and soon enough I found a counterexample: for this sequence of matrices

```
[1d] [d1] [11] [11] [1d] [dd] [dd] [d1] [1d] [d1] [11] [1d]

```

The dynamic algorithm gives the following tree of parenthesization (it's quite easy to see we can model it via a tree)

```
[1d] [d1] [11] [11] [1d] [dd] [dd] [d1] [1d] [d1] [11] [1d]
   [11]     |    |     \    \    [d1]      [11]    /    /
     |      |    |      \    [d1]              [11]    /
     |      |    |       [11]                  /      /
     |      |    |          \                 /      /
     |      |    |           ------[11]-------      /
     |      |    |                  /              /
     |      |    [11]---------------              /
     |       \   /                               /
     |       [11]                               /
      \        /                               /
       --[11]--                               /
           \                                 /
            --------------[1d]---------------

```

With a total cost: $5+4d+2d^2$.

Whereas the greedy one gives:

```
[1d] [d1] [11] [11] [1d] [dd] [dd] [d1] [1d] [d1] [11] [1d]
   [11]      [11]    /    /    /    /      [11]    /    /
     \        /     /    /    /    /         \    /    /
      \-[11]-/     /    /    /    /           [11]    /
          \       /    /    /    /              \    /
           --[1d]-    /    /    /                [1d]
                \    /    /    /                  /
                 [1d]    /    /                  /
                    \   /    /                  /
                     [1d]   /                  /
                       \   /                  /
                        [11]                 /
                           \                /
                            ------[1d]------

```

With total cost: $3+6d+2d^2$.

And we can see that for any $d \> 1, \quad 3+6d+2d^2 \> 5+4d+2d^2$, so it's not optimal...

So the competition changes: is it at all possible to solve that problem greedily? Or more broadly (and essentially getting back to the original question from the book) - how could we solve it efficiently (I believe it should be $\mathcal{o}(n^2)$) without resorting to Hu-Shing algorithm? I don't have any ideas unfortunately.

# Answer
Perhaps this solution is incorrect. Feel free to provide counterexamples. I'll provide you with both my solution and the reasoning.

The cost function turns out to be a cubic function in $d$, and the attempt is to minimise the coefficients of the highest power terms. Only possible problem with this approach is that if

$$pd^{3}+qd^{2}+rd+s$$

and

$$wd^{3}+xd^{2}+rd+s$$

are two solutions with $p \< w$ then the first solution is only good as long as $(q-x)d \< (p-w)$

It however seems like such a situation is impossible to generate (correct me if I am wrong.)

My solution:

1. Go to the first $\[dd\]$ matrix. Since it is the first occurrence of $\[dd\]$, it should either be the first matrix or there should be a $\[1d\]$ matrix to the left of it. Multiply these matrices. Do this for every $\[dd\]$ matrix.
2. To take care of $\[dd\]$ matrices that are the first in the list, start from the right this time. There should be a $\[d1\]$ matrix to the right of $\[dd\]$ matrix unless its the last. Multiply them.
3. This should get rid of all $\[dd\]$ matrices unless the input only has $\[dd\]$ matrices, as pointed out by @D.W. This approach is correct because each $\[dd\]$ matrix can contribute either a $d^2$ or a $d^3$. This ensures that their contribution is the least.
4. Every $\[1d\]$ matrix should now have $\[d1\]$ matrix to its right, since $\[dd\]$ matrices have been removed. (unless the $\[1d\]$ matrix is the last one.) Multiply them.
5. This should leave you with no $\[1d\]$ and $\[d1\]$ matrices unless they are the last and the first ones respectively. This can only happen if they were the last and the first in the original list of matrices as well. This suggests that there is no way to have these matrices generate a $\[11\]$.
6. Preform all $\[11\]$ multiplications.
7. Finally you'd be left with anywhere from 1 to 3 matrices. Between these it doesn't matter how you perform multiplications.

At point 5 the multiplication of matrices was stalled to the end. This is because, when stalled till the end they'll contribute a $d^2$ or $d$ depending on whether the end result is $\[dd\]$ or not. Clearly we can't do better since a result of $\[dd\]$ requires at least $d^2$ operations on the last multiplication.
> 1 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms, matrices, multiplication
---


# Question
Title: Is model theory useful for computer scientists
It is often stated in the CS folklore that Turing was inspired by Gödel's incompleteness theorem, more specifically the diagonalization proof and the isomorphism between axiomatically generated statements (Gödel numberings).

Are there other such links between model theory and computer science? Should a computer scientist be interested in model theory?

# Answer
A special case of model theory is finite model theory which is closely related to complexity theory and database theory. However the methods being used in classical model theory (e.g. types, stability theory, forcing, large cardinals etc) are geared towards infinite models and assume compactness. Hence they don't appear to be useful in computer science.

A second connection that is not well-known is with program verification and program logics. Model theoretic techniques like quantifier elimination and skolemisation come from model theory, but are now at heart of verification tools. Questions of importance in program logics like Hennessy-Milner theorems are in the language of model theory simply model-theoretic characterisations of the elementary equivalence (a model theoretic concept) on models of the logic. In many logics coming from program verification, the elementary equivalence is some variant of bisimulation, a concept invented independently in computer science. More examples along those lines could be given.

In summary, there is a lot of overlap, but the communities have been developing separately, use different terminology and have different focus (model theory: infinite, CS: finite and efficient), so currently both communities don't have much to say to each other.
> 11 votes

---
Tags: computation-models, turing-completeness
---


title: What's the point of Subnet Masks?

text:
# Question
Title: What's the point of Subnet Masks?
I'm having trouble understanding the point of Subnet Masks.

I was reading a nice article on Tech-FAQ on the topic, but it has left me a bit confused.

When I first heard about Subnets, it was explained to me that these are small independent networks connected to the main internet at one point. For example in an office building there would be a subnet for the thousand computers there, instead of wasting a thousand regular IP addresses.

However, from this article it seems a subnet is a collection of computers with *similar* IP addresses and a subnet mask is used to describe which bits are the ones in range of your subnetwork.

Example from the article:

So what's the point of this? We still don't save IP addresses and if I want to contact Dave at **Company X** and Bill at the same **Company X** I still have to send messages to `105.23.44.89` and `105.23.44.90`.

How do subnets make life any easier or contribute anything?

# Answer
> 5 votes
The main benefit is in the size of routing tables. Instead of having to store an entry for every machine on the network, you only need to store an entry for the particular subnet.

For example ISP might have X.Y.Z.W/16 and anyone sending a packet from the outside to any machine in this subnet only needs to know the route to their border. Their border router has a more fine grained view of the subnet (which is probably further split into many more subnets) and then knows which router on their network to send the packet to based on which smaller subnet it belongs to. Thus, subnets provides a level of abstraction to the OUTSIDE. Not the INSIDE which you seemed to have expected.

EDIT: Here's a simplified example. Assume that some large ISP has the network 1.0.0.0/8. Within this large network there are two smaller networks 1.0.1.0/24 and 1.0.2.0/24. To reach a system on either of the two smaller networks a system outside of 1.0.0.0/8 only needs to know the address of the border router of 1.0.0.0/8. Once the packet reaches the router managing 1.0.0.0/8, that router will know how to get to 1.0.1.0/24 or 1.0.2.0/24. Finally, your home router does not even need to know the address of the router of 1.0.0.0/8. It will just blindly send all your packets to a router on your home ISP assuming that this larger router will know how to get to 1.0.0.0/8 (this is what's typically called the default route/gw).

Here's a way to think about this. Think about being on a train station and having to get from city A to B. When you look at the map at the train station in city A it will tell you what trains to take to get to city B. However, that map will not tell you how to get you to your final destination in city B. However, in city B you can probably find a more detailed map that will tell you how to get you to your final destination within city B, but you don't need to have access to that map while still in city A.

---
Tags: computer-networks, communication-protocols
---


# Question
Title: Why do compute time complexity for algorithms?
I read about Big-O notation with modular arithmetic. So, Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor. Some algorithms have a worst-case time of $O(n)$ or $O(n^2)$ or $O(n^3)$.

What I want to know is what is the best time complexity of an algorithm? And why?

# Answer
The problem you are describing is indeed a shortcoming of asymptotic notation. Asymptotic notation has several advantages:

1. It doesn't depend as much on the underlying computation model. For example, the microprocessor executing the compiled code shouldn't affect the running time by more than a constant.
2. It avoids cumbersome exact results, for example instead of $n^2 + 3.5n\log n + 700\log n\lfloor \log\log n \rfloor$ we can write simply $O(n^2)$ (or even $\Theta(n^2)$).
3. In many cases it is hard to analyze exactly the running time (even ignoring the first issue), but easy to come up with asymptotics. Standard examples are recursive algorithms. In those case, however, it is often possible to come up with first-order estimates, that is, perhaps we can say that the running time satisfies $T(n) \sim 2n^2$, which is more accurate than $T(n) = \Theta(n^2)$.
4. Practically speaking, in many cases the constants hidden by the big O notation are "small" or at least "reasonable", and therefore for $n$ which is not too small, a $\Theta(n)$ algorithm will usually be faster than a $\Theta(n^2)$ algorithm.
5. Big O estimates function as ball park heuristics, which allow us to guess which algorithm is better or which part of an algorithm needs optimization the most. If in doubt, however, it is better to use profiling.

On the other hand, in some cases the problem you're indicating is serious. A classical case is fast matrix multiplication, where the trivial $O(n^3)$ algorithm often beats Strassen's $O(n^{\log\_2 7})$, and always beats all other algorithms (which have better asymptotic running time).

Summarizing, there is no easy answer. Asymptotic notation is a good model of reality in many cases, but not always. Still, it is useful since it is concise and allows quick comparison between different algorithms.
> 7 votes

# Answer
The "best" time complexity of an algorithm is when it reaches the upper complexity bound for the given problem.

Let us take a trivial example: design an algorithm to count zeroes in a sequence of $N$ numbers.

Obviously, you need to "read" every number to get the answer (because you can't guess a number by reading the others), so that the complexity of any solution is at least $\Omega(N)$. If you are able to design an algorithm that takes $O(N)$ time, then you can stop searching for better solutions (at least in the asymptotic sense), your algorithm is optimal and can't be improved.

Asymptotic complexities are used mostly for mathematical tractability, and for "portability". Because they ignore numerous "premature" details in the analysis, simplify the equations (even though in many cases the developments remain extremely involved), and because they are independent of any architectural specifics of the hardware.

Asymptotic analysis is a powerful tool for algorithm designers to rate the performance of their solutions. Anyway, they are just a valid indication for sufficiently large problem sizes. In practice, nothing replaces benchmarking on representative data sets, and a theoretically poor algorithm can be the real winner.
> 3 votes

---
Tags: algorithms, algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: Could someone explain Fagin's theorem on the equivalence between NP and existential quantifier
This quote on descriptive complexity theory is given in Wikipedia:

"The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974. It established that NP is precisely the set of languages expressible by sentences of existential second-order logic; that is, second order logic excluding universal quantification over relations, functions, and subsets."

Is there a simple proof of the theorem?

# Answer
You can check out these lecture notes, as well as countless more. The proof of Fagin's theorem is divided into two parts: showing that every language expressible in existential second-order language is in NP, and showing that every language in NP is expressible in existential second-order language. The first part is easy – we just have to guess the quantified relations. The second part is more complicated, but resembles the proof of Cook's theorem. The idea is that the quantified relations encode the computation of an NP machine.

For more details, you can consult Neil Immerman's book *Descriptive Complexity*.
> 5 votes

---
Tags: complexity-theory
---


title: Graph Theory Handshaking problem

text:
# Question
Title: Graph Theory Handshaking problem
Mr. and Mrs. Smith, a married couple, invited 9 other married couples to a party. (So the party consisted of 10 couples.) There was a round of handshaking, but no one shook hand with his or her spouse. Afterwards, Mrs. Smith asked everyone except herself, “how many persons have you shaken hands with?” All 19 answers were diﬀerent.

Unfortunately, when I try to simulate a smaller problem with 3 couples, I am getting that each couple is shaking 4 hands. Here is the diagram:

As you can see both a1 and a2 have 4 blue lines each that are "attached" (ie they shake hands) to the other couples. Both b1 and b2 have 2 red lines and 2 blue lines. Do we count the blue lines again adding it to the 2 red lines giving us that b1 and b2 have 4 lines attached or do we just ignore the blue lines connecting to b1 and b2 and say that both b1 and b2 shake 2 hands each?

Both c1 and c2 also have 2 blue and 2 red lines. I meant to have blue lines designated for a1 and a2, and the red lines for b1 and b2. Does that mean that c1 and c2 have shaken 0 hands each? Or do I try another few lines attaching the c's to the a's and b's?

Another problem with the approach above is that each couple has the same number of handshakes even though that is not possible according to the question. I would appreciate any clarification on the question and what exactly am I doing wrong.

Thanks.

# Answer
Here is a solution for two couples, $m\_1,w\_1$ and $m\_2,w\_2$. The edges are $(m\_1,w\_2),(w\_1,w\_2)$. The degrees are $1,1,0,2$ (in the order $m\_1,w\_1,m\_2,w\_2$).

Here is a solution for three couples, $m\_1,w\_1,m\_2,w\_2,m\_3,w\_3$. The edges are $(m\_1,w\_2),(w\_1,w\_2),(m\_1,w\_3),(w\_1,w\_3),(m\_2,w\_3),(w\_2,w\_3)$. The degrees are $2,2,1,3,0,4$.

Hopefully you can generalize this construction to an arbitrary number of couples. If not, you can always try running the Havel–Hakimi algorithm, trying to avoid connecting a husband to his wife.
> 2 votes

---
Tags: graphs
---