# Question
Title: What is the exact meaning of a Predicate, decidability and computability?
In the `Computability, Complexity and Languages` book written by Davis in page 5 he defines a predicate as:

> By a predicate or a Boolean-valued function on a set $S$ we mean a *total function* $P$ on $S$ such that for each $a \in S$, either $P(a) = True$ or $P(a)=False$.

So every predicate is a total function. in Page 30 he says:

> * A given partial function $g$ (of one or more variables) is said to be partially computable if it is computed by some program
> * A function is said to be computable if it is both partially computable and total.

in page 68 he says:

> **Theorem 2.1**. $HALT(x, y)$ is not a computable predicate.

Since every predicate is total, so the only reason which causes this theorem to be true is that there must be no program that computes $HALT(x,y)$, it means $HALT(x,y)$ is not a partially computable, if it was then it would be computable because it is total!

Not that in page 76 the writer says:

> Note that a partially computable predicate is necessarily computable

In this link I found two statements that seems to be a contradiction.

> * In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable or Turing-acceptable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.
> * The Halting problem is recursively enumerable but not recursive.

I know that decidability terminology is used for sets but computability terminology is used for languages. if we can say that recursively enumerable sets are partially computable (= partially deciable) then Since Halting problem is r.e. so it is partially computable. If it is partially computable and since it is total so Halting problem must be computable !!!

# Answer
There is an unfortunate clash of terminology here. Before exposing it, let me just mention that *decidable* and *computable* are synonyms. You mention several concepts, including:

1. Partially computable: A partial function which is computed by some program that doesn't necessarily always halt.
2. Partially decidable (terminology I personally have never heard): A language (i.e. set of words) that is enumerated by some program.

These are different concepts. Partial computability is a property of (partial) functions. Since languages can also be viewed as predicates, partial computability can also apply to languages, though this is somewhat misleading, since a partially computable predicate is always computable.

Partial decidability, usually known by some of the other names you mention, is a property of languages. Partial decidability can also apply to predicates by considering the language of all input tuples satisfying the predicate.

The halting problem itself has many variants, of which you mention two:

1. The halting predicate $HALT(x,y)$, true if the program encoded by $x$ halts on input $y$.
2. The halting problem, which is the language of all pairs $(x,y)$ such that the program encoded by $x$ halts on input $y$.

The halting problem is a language whose corresponding predicate is the halting predicate. Both are partially decidable but *not* partially computable or computable.
> 3 votes

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$?
Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum\_{i=1}^n (n/i)^2$?

Also, why is $f(n) = \Theta(g(n))$ where $f(n) = n^{\log\_49}$ and $g(n) = 3^{\log\_2 n}$?

I know what notations mean - I just want to prove them.

# Answer
> 2 votes
Since you get $$g(n) = \sum\_{i=1}^n (n/i)^2\geq n^2\sum\_{i=1}^1 (1/i)^2=n^2\cdot H\_n^{(2)}$$

Where $H\_n^{(2)}$ is the second generalized harmonic number.

Since $$\forall n\geq 1:\ \ 1 \< H\_n^{(2)} \< \frac{\pi^2}{6}$$

You get that $$n^2 \< g(n) \< n^2 \cdot \frac{\pi^2}{6}$$

and $$f(n)=\frac{n(n+1)}{2}\leq \frac{(n+1)^2}{2}\leq \frac{(2n)^2}{2}\leq 2n^2$$ $$f(n)=\frac{n(n+1)}{2} \geq \frac{n^2}{2}$$

Then $$\forall n\geq 1: \frac{3}{\pi^2} g(n) \leq f(n)\leq 2\cdot g(n)$$

And thus $f(n)=\Theta(g(n))$.

---

As for the second part of the question:

Since $$\forall x,y,z\>0:x^{\log\_z y}=(z^{\log\_z x})^{\log\_z y}=z^{\log\_z x\cdot {\log\_z y}}=(z^{\log\_z y})^{\log\_z x}=y^{\log\_z x}$$ you get that:

$$g(x)=3^{\log\_2 n}=n^{\log\_2 3}=n^{\log\_4 9}$$

And thus $$f(n)=\Theta(g(n))$$

---
Tags: asymptotics
---


# Question
Title: Reduction examples from the strongly NPC problem 3-PARTITION
3-PARTITION is strongly NP-complete, i.e. it remains NP-complete even if the input is given in unary.

I'm searching two or three examples of (possibly well-known) *non-numeric problems* that have been proved to be NP-complete using a reduction from 3-PARTITION (and the reduction obviously relies on the strongly np-completeness). I would like the references to the original papers.

# Answer
I found two articles, both on Tetris.

The first one is Tetris is Hard, Even to Approximate by Erik D. Demaine et al. It uses the unary encoding scheme for 3-Partition problem and constructs a polynomial reduction:

> The $a\_i$'s and $T$ are represented in unary, so the size of the game is polynomial. (from Theorem 3.2, page 9)

The other one is Tetris is Hard, Made Easy by Ron Breukelaar et al. It also uses the unary 3-Partition problem:

> Note that the board is constructable in polynomial time (measured in the input size), since the variables in the problem definition may be given in unary due to the strong sense of NP-completeness (Theorem 1). On its constructibility, consult \[4\]. (from section 2.3)

I did not go into the two articles. Are them qualified to your references request?

**EDIT:** I recently found another example of optimal scheduling of a job system with ordered precedence constraints on two dedicated processors. Here is the paper "On the Complexity of Scheduling Problems for Parallel/Pipelined Machines" (IEEE Transactions on Computers 1989).
> 4 votes

# Answer
Prof. Erik Demaine has contributed the wonderful (video) lecture of *"Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall'14)"*. In particular, lectures 2 and 3 are devoted to the reductions (directly or indirectly) from $\textsf{3-Partition}$.

For example, Lecture 2 is concerned with several variants of Jigsaw puzzles. The results are collected in the paper *"Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity"*. Its abstract says

> We show that jigsaw puzzles, edge-matching puzzles, and polyomino packing puzzles are all NP-complete. Furthermore, we show direct equivalences between these three types of puzzles: any puzzle of one type can be converted into an equivalent puzzle of any other type.

---

Most probably you have known these results and this video lecture. However the wonderful lecture may be also useful for other people.
> 4 votes

---
Tags: reference-request, np-complete
---


# Question
Title: Sorted-greedy for Load Balancing Problem
In load balancing problem we have $m$ machines and $n$ jobs, each taking processing time $t\_j$. Total processing time on the machine $i$ is $T\_i =\sum\_{j\in A(i)}{t\_j}$, where $A(i)$ is the set of jobs assigned to machine $i$. Goal is to provide an assignment of jobs, such that $\max T\_i$ is minimized.

It is known that sorted greedy algorithm is only approximation solution for load balancing problem. But I can't find an instance of problem, when it actually doesn't find an optimum solution. Can someone provide an example when this algorithm gives a wrong answer?

# Answer
Take for instance $m=2$ machines and $n=5$ jobs with processing times $4,3,3,2,2$.

* The optimal schedule puts $4+3$ on one machine and $3+2+2$ on the orther machine.
* Sorted-greedy assigns $4$ to the first machine, $3$ to the second machine, $3$ to the second machine, $2$ to the first machine, $2$ to the first machine. Hence the loads are $4+2+2$ and $3+3$.
> 3 votes

---
Tags: approximation, greedy-algorithms
---


# Question
Title: Why is this argument for $P\neq NP$ wrong?
I know its silly, but i managed to confuse myself and i need help settling this

Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the fact that there exists some oracle $A$ for which $P^A\neq NP^A$, hence $P\neq NP$

Whats wrong? Thanks!

# Answer
> 13 votes
Sure, you just have to be careful thinking about what it means to have an oracle.

The problem comes from an annoying abuse of notation we use in CS: In the statement $P=NP$, $P$ refers to a set of languages. But in the statement $P^A = NP^A$, $P$ refers to a class of Turing Machines (determinstic polytime TMs). You should think of these two $P$s as of completely different types.

So even if the two sets of languages $P$ and $NP$ are the same, deterministic polytime TMs still do not work in the same way as nondeterministic ones. In particular, given an oracle, a nondeterministic TM can "ask many questions at once", which is something the regular TM cannot do. So even if they decide the same set of languages when neither type of machine is given additional help, the oracle might help one type of machine more than another.

---
Tags: complexity-theory, p-vs-np, oracle-machines
---


title: 2-SAT or 3-SAT or k-SAT in AC-0

text:
# Question
Title: 2-SAT or 3-SAT or k-SAT in AC-0
This may be an elementary question, but I'm new to circuit complexity. Does 2-SAT in CNF form belong to the complexity class AC$^0$?

It seems simple enough to construct an AC$^0$ circuit of depth 2 of polynomial size for 2-SAT. $~$Given $n$ variables (which means $2n$ literals), there can be at most $\frac{(2n)(2n-1)}{2} = n(2n-1)$ number of OR gates at Level one, because, given $2n$ literals, there can be at most $n(2n-1)$ clauses. At Level 2, there is just one gate (an AND gate).

But we can also extend this to 3-SAT. $~$The only difference is that at Level one, the maximum number of OR gates would now be ($2n$ choose $3$), which is $O(n^3)$, still polynomial in the number of variables. Doesn't this mean that 3-SAT is also a member of AC$^0$? Wouldn't this mean that 3-SAT is polynomially solvable? What am I doing wrong?

# Answer
2SAT is the following problem: given $\varphi$ (a Boolean formula in 2-CNF), is $\varphi$ satisfiable?

To show that 2SAT is in $\textsf{AC}^0$, you must show a constant-depth, polynomial-size circuit that can solve 2SAT. In other words, you need to come up with an algorithm to solve 2SAT, and then show that the algorithm can be implemented by an $\textsf{AC}^0$ circuit.

In your question, you showed that $\varphi$ is in $\textsf{AC}^0$, but that's not what we need. We need to know that the algorithm to solve 2SAT (i.e., to check whether $\varphi$ is satisfiable) is in $\textsf{AC}^0$, not that $\varphi$ is in $\textsf{AC}^0$.
> 3 votes

---
Tags: circuits
---


# Question
Title: Finding a solution to the following conditions?
So for these 5 conditions, I am trying to find the solution/formula for them. What would $a\_n$ equal basically? If it helps, the recurrence relation these 5 conditions were generated from was $a\_n = a\_{n - 1} + 2n$. Any help would be greatly appreciated.

$$ \begin{align\*} a\_0 &= 4 \\ a\_1 &= 6 \\ a\_2 &= 10 \\ a\_3 &= 16 \\ a\_4 &= 24 \end{align\*} $$

# Answer
There are infinitely many sequences starting $4,6,10,16,24$. If I understand you correctly, this sequence was generating according to the rule $a\_n = a\_{n-1} + 2n$ with the initial value $a\_0 = 4$. In that case, you have $$ a\_n = a\_0 + \sum\_{k=1}^n (2k) = a\_0 + 2 \frac{n(n+1)}{2} = n^2 + n + 4. $$
> 0 votes

---
Tags: recurrence-relation
---


title: Proving $DTime(n^3) \subset PSpace$

text:
# Question
Title: Proving $DTime(n^3) \subset PSpace$
It is pretty obvious that $DTime(n^3) \subseteq PSpace$, since $DTime(n^3) \subseteq DSpace(n^3) \subseteq PSpace$, but I fail to see how to find such a language $L$ so that $L\in PSpace\\,\\,\\,$ yet $\\,\\,L\notin DTime(n^3) $. Can someone assist with an idea of how to find such $L$?

# Answer
> 3 votes
Hint: Use the *time hierarchy theorem* which shows, for example, that $\mathsf{DTIME}(n^3) \subsetneq \mathsf{DTIME}(n^4)$.

---
Tags: complexity-theory
---


title: Turing Machine notation

text:
# Question
Title: Turing Machine notation
I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class.

The question gives us a string $\alpha \in \\{0,1\\}$\* and the function $\mathsf{int}(\alpha)$ that changes a binary number to its base 10 form. (example, $\mathsf{int}(00010) = \mathsf{int}(10) = 2$)

Now comes the tricky part: Define the language $L ⊆ \\{0, 1, \\#\\}\*$ by:

$L = \\{\alpha\\#\beta | α, \beta ∈ \\{0, 1\\}$\* and $|\beta| ≥ \mathsf{int}(\alpha) ≥ 1 $ and $\beta \\{ \mathsf{int}(\alpha) \\} = 1 \**\\}$.

This bolded section is confusing me, and it seems like there are different variations of T.M. notation as well...

Could someone give me a rough approximation of what this might mean?

Extra: Examples for language $L$:
$\\#111 \notin L$
$00010\\#11100 \in L$
$00011\\#010111 \notin L$
$00011\\#11 \notin L$
$1\\#\\#1 \notin L$

Thanks in advance.

# Answer
The function $\mathsf{int}$ actually doesn't change a binary number to its base 10 form. Rather, it takes a string *encoding* some number $n$ in binary, and outputs $n$. When we write the output, we use decimal (base 10), but the output is just a number. It's us who use base 10.

The language $L$ consists of all strings $\alpha\\#\beta$, where $\alpha,\beta \in \\{0,1\\}^\*$, such that

1. $\alpha$ encodes (in binary) an integer $a$ in the range $1$ to $|\beta|$, where $|\beta|$ is the length of $\beta$.
2. The $a$th bit of $\beta$ is $1$.

It's difficult to say what the $a$th bit of $\beta$ is, since there are several possible conventions:

1. The "first" bit could be bit number $0$ or bit number $1$; in this case it seems like the first bit should be bit number $1$.
2. We could be counting bits from the left or from the right; the usual convention is from the left, though if you think as a string as encoding a number, it is more natural to count from the right.

Assuming we are counting bits from the left and starting with $1$, $L$ consists of strings $\alpha\\#b\_1b\_2\cdots b\_n$ where $\alpha$ encodes a number $a$ in the range $1 \leq a \leq n$ and $b\_a = 1$. This interpretation also matches your examples.
> 3 votes

---
Tags: turing-machines, notation
---


title: Mutations as a crossover by product

text:
# Question
Title: Mutations as a crossover by product
Let's say I'm writing a GA to find an optimal path to travel from point $A$ to point $B$. Genotypes are a list of directions (north, south, east, west) to follow.

So a genotype "NENWEE" will move north once, east once, then north again, west once, and finally east twice.

The directions are encoded as follows:

```
N : 00
E : 01
W : 10
S : 11

```

Our first genotype, "NENWEE" (let's call it $P$), will thus be encoded as follows: $00\\,01\\,00\\,10\\,01\\,01$

Let $Q$ be a second genotype, say "EENEWW", which is encoded as follows: $01\\,01\\,00\\,01\\,10\\,10$

Now let's do a one-point crossover operation on genotype $Q$, from $P$. The randomly-chosen crossover point is between the $9$-th and $10$-th bit, so bits $10$, $11$ and $12$ from genotype $P$ will replace those same bits from genotype $Q$. Let's call the resulting genotype $Q'$.

```
P  :  00 01 00 10 01 01
Q  :  01 01 00 01 10 10
Q' :  01 01 00 01 11 01

```

After decoding $Q'$ we find that the result is "EENESE". However neither $P$ nor $Q$ contained direction south.

My question is, do crossover operators imply a certain degree of mutation by definition?

# Answer
I have contacted Inman Harvey from the University of Sussex and here is his answer to my question:

> In your example you have given each genotype $6 \\,\\,\\,\\, 2$-bit 'genes'. Let's look at how different your example parents $P$ and $Q$ are:
>
> In genes $2 (01)$ and $3 (00)$, the genes are identical in $P$ and $Q$ In genes $1, 4, 5$ and $6$ the $2$-bit genes differ
>
> Ie $2/3$ of the genes differ between parents.
>
> If you have $1$-point crossover at any of $12$ positions on the genotype (including here the non-functional case where the crossover-point is 'off-the-end', then:
>
> $6$ of the possible crossover points are between-genes and hence do not count as sort-of mutations. $2$ of the possible crossover points are within the $2$-bit genes that are identical in $P$ and $Q$ – hence do not result in any 'crossover-style-mutation' in $Q'$
>
> $4$ of the possible crossover points are within non-identical genes, and hence DO result in a crossover-style-mutation in $Q'$.
>
> So -- with your specific example, $4$ out of $12$, ie $1/3$ of the time, crossover will produce a crossover-style-mutation. Sounds a lot. Sounds like maybe you should be worried about this in terms of impacting on effective mutation rates...
>
> BUT WRONG!! Your example was atypical. You will find in practice, after only a few generations of evolution, your parents $P$ and $Q$ will be genetically very similar to each other. This is the basic SAGA insight, see any of my papers with SAGA in the title. If you doubt this, then run any binary-style GA for as few as $10$ generations and check on how similar any $2$ randomly chosen parents are. It won't be (as in your example above) $67\\%$ of genes differing between parents, it will be more like order of $1\\%$ (if your genotypes are say $100$ bits long) differ between parents. Don't believe me, run the tests yourself, it is very easy to do!
>
> ... and hence your concern about these crossover-style-mutations should, I suggest, diminish to near vanishing point when you take account of the reality that most parents have mostly identical genotypes.
>
> Anecdotally and simplistically, if human genotypes are $98\\%$ similar to chimpanzee genotypes, then you should expect your average human-human parental couple to be $99.99\\%$ genetically identical, and only $0.01\\%$ open to the possibilities that worry you above (that $\sim 0.01\\%$ is of course important and interesting for different reasons). Elephant mating with a flea, then you can expect problems -- in fact what you are discussing above relates closely to inter-species breeding problems. Your standard $GA$ does not run into such problems.

I hadn't thought of it this way. So in fact crossover operators may introduce unwanted mutations in early generations (depending on how they are implemented) but these mutations will have little, if any, effect on the actual optimal mutation rate.
> 2 votes

---
Tags: genetic-algorithms
---


title: Listing all possible train routes

text:
# Question
Title: Listing all possible train routes
I'm interested whether there is the standard solution to the following problem. Some number of train routes is given:

Route1: First City -\> Next City -\> ... -\> Last City

Route2: ...

...

We need to list all possible ways to get from one given city to the other with possible transfers but without visiting any city more than once. So, for example, if we're given

R1: A -\> B -\> C

R2: B -\> D -\> E

R3: C -\> D -\> A

R4: C -\> E -\> F

than the routes from A to E are the following:

A -\> \[R1\] -\> B -\> \[R2\] -\> E

A -\> \[R1\] -\> C -\> \[R4\] -\> E

I hope i've managed to explain properly. And thank you very much in advance for any tips.

# Answer
> 1 votes
Based on your comments, I'm assuming that if the problem asked to find all paths between $A$ and $B$ on a directed graph, you'd have no problem. So the only hurdle is how to deal with the extra route information. Here's an outline of the most obvious approach that I can see:

1. Convert the given set of routes to an adjacency matrix. Since each edge $(A,B)$ belongs to some route $R$, store that route in the corresponding entry for $(A,B)$ in the matrix.
2. Run your algorithm to find all paths between your start and goal nodes.
3. Convert the output of your algorithm to the desired form by collapsing all consecutive edges that belong to the same route into one edge.

# Answer
> 0 votes
This problem has a very simple solution, it is called DFS! Except whenever leaving a node, you should also clean it up (unmark it) so it can be used again the next time. This means you just need to add a single line `remove discovered label from v` at line 6 in psudo code provided there to get something like this:

```
1   procedure DFS(G,v):
2       label v as discovered
3       for all edges from v to w in G.adjacentEdges(v) do
4           if vertex w is not labeled as discovered then
5               recursively call DFS(G,w)
6       remove discovered label from v

```

This routine will iterate over all the paths originating from vertex/city `v`. But to print the path, you also have to check if `v` is the destination city, and if so print the path traveled in this iteration.

---
Tags: graphs, routing
---


# Question
Title: Arbitrary precision integer square root algorithm?
Are there any known subquadratic algorithms for calculating the floor of the square root of an `n` bit integer?

The naive algorithm would be something like

```
def sqrt(x):
    r = 0
    i = x.bit_length() // 2
    while i >= 0:
        inc = (r << (i+1)) + (1 << (i*2))
        if inc <= x:
            x -= inc
            r += 1 << i
        i -= 1
    return r

```

This takes `O(n)` iterations, each one involving additions that are `O(n)` time, so it's `O(n^2)` time overall. Is there anything faster? I know that for the case of multiplication there are special algorithms that do better than quadratic time, but I can't find anything for square roots.

# Answer
> 5 votes
You can use Newton's method or any of a number of other methods for finding approximations to roots of the polynomial $p(x) = x^2 -c$.

The rate of convergence for Newton's method will be quadratic, which means that the number of bits that are correct doubles in each iteration. This means $O(\lg n)$ iterations of Newton's method suffice.

Each iteration of Newton's method computes

$$x\_{j+1} = x\_j - (x\_j^2 -c)/(2x\_j) = 0.5 x\_j + \frac{c}{2x\_j}.$$

The bit complexity of multiplication is $\stackrel{~}{O}(b \lg b)$, to multiply two $b$-bit integers (ignoring $\lg \lg b$ factors). The bit complexity for division (to $b$ bits of precision) is the same. Therefore, each iteration can be computed in $\stackrel{~}{O}(n \lg n)$ operations. Multiplying by $O(\lg n)$ iterations, we find that the overall running time to compute the square root to $n$ bits of precision is $\stackrel{~}{O}(n (\lg n)^2)$. This is sub-quadratic.

I think a more careful analysis shows that this can be improved to $\stackrel{~}{O}(n \lg n)$ running time (by taking into account that we only need to know each $x\_j$ to within about $j$ bits of precision, rather than $n$ bits of precision). However, even the more basic analysis already shows a running time that is clearly subquadratic.

# Answer
> 8 votes
One of the problems with Newton's method is that it requires a division operation in each iteration, which is the slowest basic integer operation.

Newton's method for the *reciprocal* square root, however, doesn't. If $x$ is the number for which you want to find $\frac{1}{\sqrt x}$, iterate:

$$r\_{i+1} = \frac{1}{2} r\_i (3 - x r\_i^2)$$

This is often expressed as:

$$w\_i = r\_i^2$$ $$d\_i = 1 - w\_i x$$ $$r\_{i+1} = r\_i + \frac{r\_i d\_i}{2}$$

That's three multiplication operations. The division by two can be implemented as a shift-right.

Now the problem is that $r$ is not an integer. However, you can manipulate it as such by implementing floating-point manually, and doing a bunch of shift operations to compensate when appropriate.

First, let's rescale $x$:

$$x' = 2^{-2e} x$$

where we would like $x'$ to be greater than, but close to, $1$. If we run the above algorithm on $x'$ instead of $x$, we find $r = \frac{1}{\sqrt x'}$. Then, $\sqrt{x} = 2^e r x'$.

Now let's split $r$ into a mantissa and exponent:

$$r\_i = 2^{-e\_i} r'\_i$$

where $r'\_i$ is an integer. Intuitively, $e\_i$ represent the precision of the answer.

We know that Newton's method roughly doubles the number of accurate significant digits. So we can choose:

$$e\_{i+1} = 2e\_i$$

With a little manipulation, we find:

$$e\_{i+1} = 2e\_i$$ $$w\_i = {r'\_i}^2$$ $$x'\_i = \frac{x}{2^{2e - e\_{i+1}}}$$ $$d\_i = 2^{e\_{i+1}} - \frac{w\_i' x'\_i}{2^{e\_{i+1}}}$$ $$r'\_{i+1} = 2^{e\_i} r'\_i - \frac{r'\_i d\_i}{2^{e\_i + 1}}$$

At every iteration:

$$\sqrt{x} \approx \frac{r'\_i x}{2^{e + e\_i}}$$

As an example, let's try calculating the square root of $x = 2^{63}$. We happen to know that the answer is $2^{31}\sqrt{2}$. The reciprocal square root is $\frac{1}{\sqrt{2}} 2^{-31}$, so we'll set $e = 31$ (this is the scale of the problem) and for our initial guess we'll pick $r'\_0 = 3$ and $e\_0 = 2$. (That is, we pick $\frac{3}{4}$ for our initial estimate to $\frac{1}{\sqrt{2}}$.)

Then:

$$e\_1 = 4, r'\_1 = 11$$ $$e\_2 = 8, r'\_2 = 180$$ $$e\_3 = 16, r'\_3 = 46338$$ $$e\_4 = 32, r'\_4 = 3037000481$$

We can work out when to stop iterating by comparing $e\_i$ to $e$; if I've calculated correctly, $e\_i \> 2e$ should be good enough. We'll stop here, though, and find:

$$\sqrt{2^{63}} \approx \frac{3037000481 \times 2^{63}}{2^{31+32}} = 3037000481$$

The correct integer square root is $3037000499$, so we're pretty close. We could do another iteration, or do an optimised final iteration which doesn't double $e\_i$. The details are left as an exercise.

To analyse the complexity of this method, note that multiplying two $b$-bit integers takes $O(b \log b)$ operations. However, we have arranged things so that $r'\_i \< 2^{e\_i}$. So the multiplication to calculate $w\_i$ multiplies two $e\_i$-bit numbers to produce a $e\_{i+1}$-bit number, and the other two multiplications multiply two $e\_{i+1}$-bit numbers to produce a $2e\_{i+1}$-bit number.

In each case, the number of operations per iteration is $O(e\_i \log e\_i)$, and there are $O(\log e)$ iterations required. The final multiplication is on the order of $O(2e \log 2e)$ operations. So the overall complexity is $O(e \log^2 e)$ operations, which is sub-quadratic in the number of bits in $x$. That ticks all the boxes.

However, this analysis hides an important principle which everyone working with large integers should keep in mind: because multiplication is superlinear in the number of bits, any multiplication operations should only be performed on integers which have the roughly the magnitude of the current precision (and, I might add, you should try to multiply numbers together which have a similar order of magnitude). Using integers larger than that is a waste of effort. Constant factors matter, and for large integers, they matter a lot.

As a final observation, two of the multiplications are of the form $\frac{ab}{2^c}$. Clearly it's wasteful to compute the all the bits of $ab$ only to throw $c$ of them away with a right-shift. Implementing a smart multiplication method which takes this into account is also left as an exercise.

---
Tags: algorithms, numerical-algorithms
---


# Question
Title: Scheduling a tournament with variable game lengths
I want to solve the following scheduling problem: We have $N$ resources and $\binom{N}{2}$ tasks, such that every task requires exactly two resources and every pair of resources is required by exactly one task. The number of resources $N$ and the durations $t\_i$ of each task are the input. Output is smallest possible $T$ and a list of starting times $T\_i$ for each task, such that

* $T\_i \geq 0$ for each $i$.
* If tasks $i$ and $j$ share a resource, then either $T\_i+t\_i \leq T\_j$ or $T\_j + t\_j \leq T\_i$.
* $T\_i + t\_i \leq T$ for each $i$.

Is there a practical algorithm for this, let's say for $N \leq 10$? We can assume that the durations are integers, let's say at most $200$.

A more general case of the scheduling problem would be one where each task is allowed to use any number of resources there is no constraint on how many tasks use each resource. However, I couldn't find even that problem anywhere.

---

Example input with $6$ resources (A,B,C,D,E,F): The number in row $i$ column $j$ is the duration of the task that requires resources $i$ and $j$. $$ \begin{array}{rrrrrrr} & B & C & D & E & F \\ A & 112 & 2 & 2 & 2 & 2 \\ B & & 2 & 2 & 2 & 2\\ C & & & 40 & 38 & 38 \\ D & & & & 38 & 38 \\ E & & & & & 40 \end{array} $$

Example output: total duration $124$ and schedule as follows: $$ \begin{array}{rrr} \text{start} & \text{end} & \text{task} \\ 0 & 2 & B-F \\ 0 & 2 & A-D \\ 2 & 4 & B-C \\ 2 & 4 & A-E \\ 4 & 6 & A-F \\ 4 & 6 & D-B \\ 6 & 118 & A-B \\ 6 & 44 & C-F \\ 6 & 44 & D-E \\ 44 & 84 & C-D \\ 44 & 84 & E-F \\ 84 & 122 & C-E \\ 84 & 122 & D-F \\ 122 & 124 & A-C \\ 122 & 124 & B-E \end{array} $$

---

Background: Our chess club organized a small one-evening tournament with the following idea:

* There are $N$ players, and everyone plays against everyone exactly once.
* Each player is given a budget of, say 60 minutes, which he allocates to all his $N-1$ games before the tournament. For example, he may decide to have 20 minutes against player A, 30 minutes against player B, 5 minutes against player C and 5 minutes against player D. For practical purposes, everyone has to allocate at least one minute against each player.

The maximum duration of the game A vs B is the time A allocated against B plus the time B allocated against A. We want to finish the tournament as quickly as possible, assuming all time is used in each game. Multiple games can be played at the same time but "rounds" are not needed, so games can start whenever two players are free, and it does not matter if player A plays 3 games before player B finishes his first game.

---

My ideas: I settled for a genetic algorithm where an individual is an ordered list of the $\binom{N}{2}$ games. A list corresponds to a schedule which is made by going through the games in the list and scheduling each game as early as possible. The initial population is taken from randomized standard round-robin pairing tables. Sometimes the genetic algorithm finds a solution that is better than one obtained by standard round-robin tables, but it's hard to say if the best solution found is actually best possible or not, so I'd prefer an exact algorithm.

A trivial lower bound for the duration of the tournament is the sum of lengths of games of a player (which may vary from player to player if everyone decides to allocate more time against a certain player), but that lower bound is not always achievable.

---

Variations: An interesting variation occurs if we take into account that games may end early. When a game ends, the ending time is entered to a computer which then calculates a new schedule for the remaining games, possibly ending earlier than the previous schedule. I guess this can be done by scheduling the remaining games using the same algorithm used for the whole tournament. However, while it is no problem if the initial scheduling takes a minute or two, as there are other things to do before the start of the tournament, but it would be nice to have the schedules appear very quickly if the algorithm is run in the middle of the tournament, so nobody has to wait for that.

# Answer
Another option is using an SMT (SAT modulo theories) solver such as Z3 or MathSAT. The constraints you give are a boolean combination of constraints in linear arithmetic, which is one of the bread-and-butter theories for these tools. The formula you would hand to the solver is essentially what you wrote:

$\varphi := \bigwedge\_i(T\_i\ge 0 \wedge T\_i+t\_i\le T) \wedge \bigwedge\_{i\<j}(T\_i+t\_i\le T\_j \vee T\_j+t\_j\le T\_i)$.

Note that doing it this way, you still have to try different values for $T$ (SMT solvers check satisfiability, they don't directly allow you to specify an objective to be minimized). In principle, you could encode the minimality requirement into additional constraints (using boolean algebra transformations and Farkas' lemma), but this complicates things a bit.
> 1 votes

# Answer
You could find a schedule using a SAT solver.

We have ${N \choose 2}$ games. Let $\ell\_g$ denote the length of game $g$.

Let's formulate this as a SAT instance. For each game $g$ and each time $t$, we have a variable $x\_{g,t}$ that is true if game $g$ starts at time $t$, and a variable $y\_{g,t}$ that is true if game $g$ is ongoing at time $t$. Note that if $g$ starts at time $t$, then it will end at time $t+\ell\_g$, so we have

$$x\_{g,t} \implies (y\_{g,t} \land y\_{g,t+1} \land \dots \land y\_{g,t+\ell\_g-1}).$$

Now for each pair of games $g,g'$ that share a player in common, we add a constraint that indicates that $g,g'$ should not be ongoing at the same time. We can do this by adding a clause of the form

$$(\neg y\_{g,t} \lor \neg y\_{g',t})$$

for each $t$ and each such pair of games $g,g'$.

Finally, suppose we'd like to know if is possible to finish the tournament by time $T$. We can enforce this by adding a clause of the form

$$(x\_{g,0} \lor x\_{g,1} \lor \dots \lor x\_{g,T-\ell\_g})$$

for each game $g$.

Feed this set of clauses to a SAT solver, and see whether they are all simultaneously satisfiable. If they are, then you have a schedule that finishes within $T$ units of time (the satisfying assignment immediately gives you a schedule for your tournament).

Our last job is to minimize $T$. We can do this by binary search, repeatedly invoking the SAT solver until we find the smallest value of $T$ for which you can find a valid schedule.

Given the effectiveness of modern SAT solvers, I suspect this might be reasonably effective if the number of players in your club is not too large. But the only way to find out for sure is to implement it and see. (If this is not effective, there are probably approximation algorithms you could use to get an approximately-optimal schedule -- but start here, as if this approach works, it will give you an exactly optimal schedule, and without requiring too much deep thought on your part.)
> 0 votes

---
Tags: scheduling
---


# Question
Title: How to identify periodic pattern recognition
I'm dealing with a time series that consists of one year's data of the result of some measurement. The time index is in second and the result of the measurement is a non-negative integer.

Interestly, after some tweaks & transformation & plot of the original data, I found that in some days the data shows a periodic pattern within that each day.

For an instance, I found that on one day throughout the whole day a specific measurement (integer) is recorded every 1 minute. The pattern is obvious because the integers are almost the same and spaced in nearly 1 minute interval while others are kind of random.

Whilst it is relatively easy to spot the pattern I found it hard to precisely state it. The main issues here are that

1. The "specific" integers are slightly varying, say the majority of the integers are 1700, but occasionally I can find 1800, 1600, or 1701, etc;
2. The "specific" integers are different across days and sometimes even different within one day.
3. The interval is not necessarily 1 minute and furthermore, it is not the same even within a single day. Say, in the morning the pattern is spaced in 58 second interval whilst in the afternoon, it is in 61 second interval;
4. The interval is not very precise either. Say, in the first 2 hours patterns are spaced in 60 second interval but then a 61-second interval occurrs and then after that going back to the 60-second interval again;

Because the data is huge and so I want to see if I can programmatically identify the patterns (if it exists for a day) and also retrieve those "specific" integers in the pattern.

Anyone suggest an approach? Or any guidance?

Thanks.

# Answer
> 1 votes
One way to detect a pattern is to write a filter that scans the entire sequence and returns true/false at each point. True means that the pattern was recognized, false means that it was not found. Count the number of "true" values and divide by the entire length to see the fraction of times that the pattern was found.

For example, one filter would require three parameters: f, the expected frequency (60 seconds); w, the allowed width (2 seconds means 58-62 seconds); and d, the allowable difference between values.

In Python code:

```
f = 60    # frequency, every 60 points
w = 2     # width, (point - f) +/- w
d = 10    # delta, allowable difference

points = [... list of data points ...]
n = len(points)

found = 0     # start counting the number of matches
# main loop: start at point f+w so we can look back that far
for p1 in range(f+w, n+1):
    # compare point p1 with point p0, looking back (f +/- w)
    for p0 in range(p1-f-w, p1-f+w+1):
        if abs(points[p1] - points[p0]) < d:
            found += 1    # filter found a match
            break         # exit innermost loop
print 100.0 * found / (n - f - w)    # show the percentage of matches

```

You can play around with the parameters, and maybe use d as a percentage instead of an absolute value.

For more complex pattern recognition, you will need to write more complex filters. This is a start.

---
Tags: pattern-recognition
---


# Question
Title: Maximum chromatic number of sparse graphs
It is well-known that the chromatic number of a graph can be as high as $n$.

But what is the maximum chromatic number of a graph with $m = O(n)$?

# Answer
> 6 votes
A graph with $O(n)$ edges has chromatic number $O(\sqrt{n})$, and this is tight.

Suppose first that a graph has $m = O(n)$ edges and chromatic number $\chi$. Take a $\chi$-coloring of the graph. Any two color classes must be connected by an edge, since otherwise we can identify them. Therefore $m \geq \binom{\chi}{2} = \Omega(\chi^2)$, and so $\chi = O(\sqrt{n})$.

To show that this is tight, consider the union of a clique on $\sqrt{n}$ vertices and an independent set on $n-\sqrt{n}$ vertices. This is a graph with $n$ vertices and $\binom{\sqrt{n}}{2} = O(n)$ edges, and chromatic number $\sqrt{n}$.

---
Tags: algorithms, graphs
---


# Question
Title: Problem on Floating Point Representation
Consider the floating-point representation

```
31-24 : Exponent
23-0  : Mantissa

```

The exponent is in 2's complement representation and mantissa is in the sign magnitude representation. the range of the magnitude of the normalized numbers in this represntaion is

> $(a)\ 0\ to \ 1$
>
> $(b)\ 0.5\ to\ 1$
>
> $(c)\ 2^{-23}\ to \ 0.5$
>
> $(d)\ 0.5\ to \ (1-2^{-23})$

My approach: as the normalized number in floating point representation has as implicit 1.

Hence smallest mantissa would be

> $1.0000\cdots \[24\ 0's\]=1$

Largest mantissa would be

> $1.1111\cdots \[24\ 1's\]=1+(1-2^{-24})\approx2$

So my ans coming as `1 to 2`, Which is not in the option. What mistake I'm doing..

# Answer
> 0 votes
First, this is not the way standard IEEE P754 single precision floating point numbers are represented :

* Exponent is not two's complement, there is instead an offset, for IEEE normalised : F=2^(Exponent - 127) * 1.Mantissa * Sign
* Normalised numbers have an exponent different from 00 (being denormals) and FF (for infinites, NaN)

If this peculiar format has no implicit 1, mantissa should be between 0.10\[..\]0000 and 0.11\[..\]1111 : Answer (D) or between 1.0000 and 1.11111, which is your proposal.

(IIRC, Intel double extended x87 80bits format does not have the implicit 1 and works as you describe. It is not striclty IEEE compliant, the 8087 being older than the standard.)

---
Tags: floating-point
---


title: Complexity of BST

text:
# Question
Title: Complexity of BST
I have the following pseudo-code for printing all nodes of a BST :

```
traverse(x):
    if x == nil:
        return
    else:
        print x
        traverse(x.left)
        traverse(x.right)

```

I want to find its complexity. I have an idea, but I'm not sure if I am implementing it correctly.

$T(n) = 2T(n-1) + cn$

Where $T(n-1)$ for each recursive call and $cn$ for the return statement.

Is my solution correct?

# Answer
> 1 votes
What i said in previous reply was about finding a node. I excuse for misunderstanding your question. For worst case its the same but for printing in average case it's $T(n)=2T(n/2)+1$ which is $O(n)$.

# Answer
> 1 votes
It sometimes helps to start by seeing what an algorithm does, rather than immediately jumping to computing the timing. In your case, you're generating a preorder traversal of a binary tree:

```
visit (node x)                // x is the root node of the tree being visited
   if x exists
      print the value in x
      visit (x's left subtree)
      visit (x's right subtree)

```

For example, consider this binary tree:

Starting at the root, we print its value, $5$, and then recursively visit the left subtree (the $2, 8, 4$ piece). The root of that subtree is the $2$ node, so that would be printed next. Continuing this way, we print $5, 2, 8, 4$ and backtrack from the $4$ node to the $8$ node, continuing until we find a right subtree to visit, namely the right subtree of the $5$ node. We then visit the $7, 1, 3, 6$ subtree, from left to right at each subtree. The traversal will then be $$ 5\quad2\quad8\quad4\quad7\quad1\quad3\quad6 $$ Now that we see what the algorithm does, let's see how long it takes. There are two important parts: printing the node values and then recursively printing the values in the left and right subtrees. For a tree with $n$ nodes we'll print $n$ values. We get to each of these print statements as part of a function call, so there will also be $n$ function calls. The total amount of work done, then will be $2n$ so $T(n)=\Theta(n)$. Note that the timing will not depend on the shape of the tree, only on the number of nodes in the tree.

# Answer
> 0 votes
Complexity of a BST differs in different cases. In worst case BST is is like a linear linked list (all sub nodes are only left-child or right-child of each other) which its complexity can be measured by solving following recursive equation:

$T(n)=T(n-1)+1$ which is $O(n)$. But for average case we can consider it as a complete binary tree so $T(n)=T(n/2)+1$ and it's complexity is $O(log(n))$ which $log(n)$ is height of the tree.

---
Tags: time-complexity, asymptotics, search-algorithms, search-trees
---


title: A Combinational circuit Problem

text:
# Question
Title: A Combinational circuit Problem
A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, …, 9 by 1001. A Combinational circuit is to be designed which takes these 4 bits as input and outputs 1 if the digit $\geq$ 5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required?

My Solution: After analyzing the patterns of the 4 bits ABCD

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

I've come up with this Combinational Circuit

But it took me 5 gates realzize the given output. I was wondering, can we realize the given output with less number of gates ($\<$ 5 gates)

# Answer
You can solve this problem on your own by writing a program to enumerate all circuits with fewer than 5 gates, and for each one, test whether it has the right truth table. The running time should be minimal, as there aren't that many circuits with fewer than 5 gates.
> 0 votes

---
Tags: boolean-algebra
---


# Question
Title: A BST can be broken by accessing one of its nodes, how can I always make sure this happens?
I have an assignment that asks for this. So I am not looking for the answer itself but a hint on how to find a value that will always break the BST condition by myself.

If I have access to any node N of a BST that has at least 2 nodes in its root, and where every node will always be different.

If I were to replace N.key with x, what should the value of x be in order for the tree not to be a BST anymore?

I can use the following operations: GetPre = key before N when seen from an inorder transverse.

GetSuc = key after N when seen from an inorder transverse.

MAX = gets the node value from the sub-tree that has N as root.

MIN = gets node value from the sub-tree that has N as root.

I broke it in several subcases, but I am sure this can be written as one single formula.

I came up with:

$x = N.key - GetPre(N)$ but it doesn't work as I expected.

I appreciate any insight.

# Answer
Hint: In a BST, an inorder traversal produces the keys in sorted order. If we had N.key = $20$ and the inorder traversal was $2, 4, 10, 11, 17, 20, 28, 31, 40$, what $x$ values would break the sorted order when put in the place of $20$?
> 1 votes

---
Tags: data-structures, binary-trees, search-trees
---


# Question
Title: Common method for solving satisfiability problems which lie in P
I know from Schaefer's Dichotomy Theorem that only a few types of satisfiability problems are in P and any other problem is NP-complete. However, all of the algorithms I know for them use specific techniques unique to that type of problem- e.g. unit propagation for Hornsat, linear algebraic techniques mod 2 for XORSAT, and various other techniques for 2-sat. Is there one general polytime algorithm which works for all of these problems in P? Thanks.

# Answer
> 7 votes
Schaefer's dichotomy theorem is proved by dividing CSPs into two types: those that can be reduced to one of a few specific problems in P, and the other to which SAT can be reduced (and so are NP-complete). Specifically, every CSP of the former type is either trivial (always satisfied by the constant 0 or the constant 1 assignment), can be reduced to 2SAT, can be reduced to HORN-SAT, or can be reduced to XOR-SAT. These are the only algorithms you need to solve these CSPs. There is no one single algorithm – there is a finite list of algorithms.

# Answer
> 3 votes
Look for papers/books written by Vijay Chandru, John Hooker and John Franco. Some of their techniques use Integer Programming (looking at special structures in the matrix generated by the CNF clauses of the SAT instance). The "extended Horn" formulas have a special structure when represented as graphs which make them polynomially solvable.

To quote Franco from his 2009 survey: *The reader may have the impression that the number of polynomial time solvable classes is quite small due to the famous dichotomy theorem of Schaefer. But this is not the case. Schaefer proposed a scheme for defining classes of propositional expressions with a generalized notion of “clause.” He proved that every class definable within his scheme was either NP-complete or polynomial-time solvable, and he gave criteria to determine which. But not all classes can be defined within his scheme. The Horn and XOR classes can be, but we will describe several others including q-Horn, extended Horn, CC-balanced and SLUR that cannot be so defined. **The reason is that Schaefer’s scheme is limited to classes that can be recognized in log space**.*

---
Tags: complexity-theory, satisfiability, polynomial-time, sat-solvers
---


# Question
Title: Quantum state probabilities and amplitudes - absolute value squared?
It has just appeared to me that I've overlooked a possibly important fact. When we want to calculate probability $p\_x$ of measuring the state $X$ and we know the amplitude of $X$ is $\alpha$, we know that $p\_x = |\alpha|^2$. Until today I thought that absolute value was not necessary anyway. However, it brings significant difference if we have complex amplitudes with non-zero imaginary parts.

For example, let's say we have a superposition of 16 states, where four amplitudes are like $\frac{i}{4}$, four like $\frac{-1}{4}$ and eight like $\frac{1}{4}$. If we keep with the recipe I wrote above, then this state is fine, as the sum of all probabilities is 1. However, if we skip the absolute value and compute probabilities like $\alpha^2$, then sum of all probabilities in the above state would be $\frac{1}{2}$ and the state would not be stable.

Is the recipe I wrote above ($p\_x = |\alpha|^2$ for $\alpha$ being an amplitude of state $X$) correct? Do we calculate the absolute value of the amplitude before we square it?

# Answer
Using $\alpha^2$ doesn't make sense since you get negative or even non-real probabilities! The correct "recipe" is indeed $|\alpha|^2$. This also meshes well with the fact that the operations you are allowed to apply are unitary.
> 2 votes

---
Tags: quantum-computing
---


title: turing machine decidability proof

text:
# Question
Title: turing machine decidability proof
An exercise problem once again has me stumped on a Turing Machine decidability proof.

We are given an alphabet with the strings 0 through 9.

Along with this, we have x as the infinite string of all digits in PI. (3141592...)

With L ⊆ Σ\*, the language L = {A ∈ Σ\*| A is a sub-sequence of x}. (from what I understand, the definition here of a sub-sequence is having a $x = x\_1x\_2x\_3... $ where each $x\_i$ can be constructed from Σ, then a sub-sequence of x is a finite string of the form $x\_{i1}x\_{i2}x\_{i3} ... x\_{ik}$ where $i\_1 \< i\_2 \< i\_3 \< ... \< i\_k.$

Other than that I have no idea where to start with this...

Thanks in advance.

# Answer
1. Can you come up with a Turing machine that writes the decimal expansion of $\pi$ to tape?
2. Can you come up with a Turing machine that, given a string, a separator, and the decimal expansion of $\pi$ on the tape, determines whether the string occurs as a subsequence of $\pi$? (see this question).
3. Given such machines, can you 'weave' them into a single machine?
> 0 votes

---
Tags: turing-machines
---


# Question
Title: If $g ∘ f$ is primitive recursive, are $f$ and $g$, too?
Assuming I have functions $f, g : \mathbb{N} \to \mathbb{N}$ and I know that $g \circ f$ is a primitive recursive function. What can I tell about $f$ and $g$? Are they primitive recursive as well? Or at least one of them?

# Answer
> 8 votes
Let $f$ be a bijective function, which is not primitive recursive. We know, that such a function exists. Let further be $g=f^{-1}$ the inverse function of $f$. Therefore $f\circ g$ is the identity function, which is clearly primitive recursive.

---
Tags: computability, closure-properties, primitive-recursion
---


# Question
Title: Where can I find a high quality copy of Turing's On Computable Numbers?
Currently, I'm reading a photocopied version of Turing's famous article *On Computable Numbers, With an Application to the Entscheidungsproblem*.

This is the best photocopy of his paper that I can find; most other copies are of pretty low quality to the point that I can't distinguish between different characters. The e in the *final m-config* column on page 233 for example, looks exactly like a c on many copies (not the one I'm using though). I also have trouble distinguishing between the german capitol letters C and E later in his paper on page 238 and such. Is there any place where I can find a well copied version of the paper? Perhaps a book would have a nice copy.

# Answer
> 2 votes
There is a very high resolution scan in the Turing Digital Archive, however it's presented via a flash player plugin which makes reading mildy awkward and doesn't seem to allow printing.

There are a handful of marginally nicer PDF copies than that Caltech one you link available online \[1\]\[2\], however they all seem to have been drawn from the same photocopy at some point.

# Answer
> 2 votes
Stephen Hawking's collection God Created the Integers has that paper included, as well as a lot of other pivotal math papers.

EDIT: Here's a preview on Google Books.

---
Tags: turing-machines, reference-request, history
---


# Question
Title: Is there a system behind the magic of algorithm analysis?
There are lots of questions about how to analyze the running time of algorithms (see, e.g., and ). Many are similar, for instance those asking for a cost analysis of nested loops or divide & conquer algorithms, but most answers seem to be tailor-made.

On the other hand, the answers to another general question explain the larger picture (in particular regarding asymptotic analysis) with some examples, but not how to get your hands dirty.

Is there a structured, general method for analysing the cost of algorithms? The cost might be the running time (time complexity), or some other measure of cost, such as the number of comparisons executed, the space complexity, or something else.

This is supposed to become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

# Answer
## Translating Code to Mathematics

Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for *additive* cost measures such as number of comparisons, swaps, statements, memory accesses, cycles some abstract machine needs, and so on.

### Example: Comparisons in Bubblesort

Consider this algorithm that sorts a given array `A`:

```
 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

```

Let's say we want to perform the usual sorting algorithm analysis, that is count the number of element comparisons (line 5). We note immediately that this quantity does not depend on the content of array `A`, only on its length $n$. So we can translate the (nested) `for`-loops quite literally into (nested) sums; the loop variable becomes the summation variable and the range carries over. We get:

$\qquad\displaystyle C\_{\text{cmp}}(n) = \sum\_{i=0}^{n-2} \sum\_{j=0}^{n-i-2} 1 = \dots = \frac{n(n-1)}{2} = \binom{n}{2}$,

where $1$ is the cost for each execution of line 5 (which we count).

### Example: Swaps in Bubblesort

I'll denote by $P\_{i,j}$ the subprogram that consists of lines `i` to `j` and by $C\_{i,j}$ the costs for executing this subprogram (once).

Now let's say we want to count *swaps*, that is how often $P\_{6,8}$ is executed. This is a "basic block", that is a subprogram that is always executed atomically and has some constant cost (here, $1$). Contracting such blocks is one useful simplification that we often apply without thinking or talking about it.

With a similar translation as above we come to the following formula:

$\qquad\displaystyle C\_{\text{swaps}}(A) = \sum\_{i=0}^{n-2} \sum\_{j=0}^{n-i-2} C\_{5,9}(A^{(i,j)})$.

$A^{(i,j)}$ denotes the array's state before the $(i,j)$-th iteration of $P\_{5,9}$.

Note that I use $A$ instead of $n$ as parameter; we'll soon see why. I don't add $i$ and $j$ as parameters of $C\_{5,9}$ since the costs do not depend on them here (in the uniform cost model, that is); in general, they just might.

Clearly, the costs of $P\_{5,9}$ depend on the content of $A$ (the values `A[j]` and `A[j+1]`, specifically) so we have to account for that. Now we face a challenge: how do we "unwrap" $C\_{5,9}$? Well, we can make the dependency on the content of $A$ explicit:

$\qquad\displaystyle C\_{5,9}(A^{(i,j)}) = C\_5(A^{(i,j)}) + \begin{cases} 1 &, \mathtt{A^{(i,j)}\[j\] \> A^{(i,j)}\[j+1\]} \\ 0 &, \text{else} \end{cases}$.

For any given input array, these costs are well-defined, but we want a more general statement; we need to make stronger assumptions. Let us investigate three typical cases.

1. **The worst case**

Just from looking at the sum and noting that $C\_{5,9}(A^{(i,j)}) \in \\{0,1\\}$, we can find a trivial upper bound for cost:

$\qquad\displaystyle C\_{\text{swaps}}(A) \leq \sum\_{i=0}^{n-2} \sum\_{j=0}^{n-i-2} 1 = \frac{n(n-1)}{2} = \binom{n}{2}$.

But *can this happen*, i.e. is there an $A$ for this upper bound is attained? As it turns out, yes: if we input an inversely sorted array of pairwise distinct elements, every iteration must perform a swap¹. Therefore, we have derived the exact *worst-case* number of swaps of Bubblesort.
2. **The best case**

Conversely, there is a trivial lower bound:

$\qquad\displaystyle C\_{\text{swaps}}(A) \geq \sum\_{i=0}^{n-2} \sum\_{j=0}^{n-i-2} 0 = 0$.

This can also happen: on an array that is already sorted, Bubblesort does not execute a single swap.
3. **The average case**

Worst and best case open quite a gap. But what is the *typical* number of swaps? In order to answer this question, we need to define what "typical" means. In theory, we have no reason to prefer one input over another and so we usually assume a uniform distribution over all possible inputs, that is every input is equally likely. We restrict ourselves to arrays with pairwise distinct elements and thus assume the random permutation model.

Then, we can rewrite our costs like this²:

$\qquad\displaystyle \mathbb{E}\[C\_{\text{swaps}}\] = \frac{1}{n!} \sum\_{A} \sum\_{i=0}^{n-2} \sum\_{j=0}^{n-i-2} C\_{5,9}(A^{(i,j)})$

Now we have to go beyond simple manipulation of sums. By looking at the algorithm, we note that every swap removes exactly one inversion in $A$ (we only ever swap neighbours³). That is, the number of swaps performed on $A$ is exactly the number of inversions $\operatorname{inv}(A)$ of $A$. Thus, we can replace the inner two sums and get

$\qquad\displaystyle \mathbb{E}\[C\_{\text{swaps}}\] = \frac{1}{n!} \sum\_{A} \operatorname{inv}(A)$.

Lucky for us, the average number of inversions has been determined to be

$\qquad\displaystyle \mathbb{E}\[C\_{\text{swaps}}\] = \frac{1}{2} \cdot \binom{n}{2}$

which is our final result. Note that this is *exactly half* the worst-case cost.

---

1. Note that the algorithm was carefully formulated so that "the last" iteration with `i = n-1` of the outer loop that never does anything is not executed.
2. "$\mathbb{E}$" is mathematical notation for "expected value", which here is just the average.
3. We learn along the way that *no* algorithm that only swaps neighbouring elements can be asymptotically faster than Bubblesort (even on average) -- the number of inversions is a lower bound for all such algorithms. This applies to e.g. Insertion Sort and Selection Sort.

### The General Method

We have seen in the example that we have to translate control structure into mathematics; I will present a typical ensemble of translation rules. We have also seen that the cost of any given subprogram may depend on the current *state*, that is (roughly) the current values of variables. Since the algorithm (usually) modifies the state, the general method is slightly cumbersome to notate. If you start feeling confused, I suggest you go back to the example or make up your own.

We denote with $\psi$ the current state (imagine it as a set of variable assignments). When we execute a program `P` starting in state $\psi$, we end up in state $\psi / \mathtt{P}$ (provided `P` terminates).

* **Individual statements**

Given just a single statement `S;`, you assign it costs $C\_S(\psi)$. This will typically be a constant function.
* **Expressions**

If you have an expression `E` of the form `E1 ∘ E2` (say, an arithmetic expression where  may be addition or multiplication, you add up costs recursively:

$\qquad\displaystyle C\_E(\psi) = c\_{\circ} + C\_{E\_1}(\psi) + C\_{E\_2}(\psi)$.

Note that

+ the operation cost $c\_{\circ}$ may not be constant but depend on the values of $E\_1$ and $E\_2$ and
    + evaluation of expressions may change the state in many languages,

so you may have to be flexible with this rule.
* **Sequence**

Given a program `P` as sequence of programs `Q;R`, you add the costs to

$\qquad\displaystyle C\_P(\psi) = C\_Q(\psi) + C\_R(\psi / \mathtt{Q})$.
* **Conditionals**

Given a program `P` of the form `if A then Q else R end`, the costs depend on the state:

$\qquad\displaystyle C\_P(\psi) = C\_A(\psi) + \begin{cases} C\_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\ C\_R(\psi/\mathtt{A}) &, \text{else} \end{cases}$

In general, evaluating `A` may very well change the state, hence the update for the costs of the individual branches.
* **For-Loops**

Given a program `P` of the form `for x = [x1, ..., xk] do Q end`, assign costs

$\qquad\displaystyle C\_P(\psi) = c\_{\text{init\_for}} + \sum\_{i=1}^k c\_{\text{step\_for}} + C\_Q(\psi\_i \circ \\{\mathtt{x := xi\\}})$

where $\psi\_i$ is the state before processing `Q` for value `xi`, i.e. after the iteration with `x` being set to`x1`, ..., `xi-1`.

Note the extra constants for loop maintenance; the loop variable has to be created ($c\_{\text{init\_for}}$) and assigned its values ($c\_{\text{step\_for}}$). This is relevant since

+ computing the next `xi` may be costly and
    + a `for`-loop with empty body (e.g. after simplifying in a best-case setting with a specific cost) does not have zero cost if it performs iterations.
* **While-Loops**

Given a program `P` of the form `while A do Q end`, assign costs

$\qquad\displaystyle C\_P(\psi) \\\qquad\ = C\_A(\psi) + \begin{cases} 0 &, \mathtt{A} \text{ evaluates to false under } \psi \\ C\_Q(\psi/\mathtt{A}) + C\_P(\psi/\mathtt{A;Q}) &, \text{ else} \end{cases}$

By inspecting the algorithm, this recurrence can often be represented nicely as a sum similar to the one for for-loops.

**Example:** Consider this short algorithm:

```
while x > 0 do    1
  i += 1          2
  x = x/2         3
end               4

```

By applying the rule, we get

$\qquad\displaystyle C\_{1,4}(\\{i := i\_0; x := x\_0\\}) \\\qquad\ = c\_\< + \begin{cases} 0 &, x\_0 \leq 0 \\ c\_{+=} + c\_/ + C\_{1,4}(\\{i := i\_0 + 1; x := \lfloor x\_0/2 \rfloor\\}) &, \text{ else} \end{cases}$

with some constant costs $c\_{\dots}$ for the individual statements. We assume implicitly that these do *not* depend on state (the values of `i` and `x`); this may or may not be true in "reality": think of overflows!

Now we have to solve this recurrence for $C\_{1,4}$. We note that neither the number of iterations not the cost of the loop body depend on the value of `i`, so we can drop it. We are left with this recurrence:

$\qquad\displaystyle C\_{1,4}(x) = \begin{cases} c\_\> &, x \leq 0 \\ c\_\> + c\_{+=} + c\_/ + C\_{1,4}(\lfloor x/2 \rfloor) &, \text{ else} \end{cases}$

This solves with elementary means to

$\qquad\displaystyle C\_{1,4}(\psi) = \lceil \log\_2 \psi(x) \rceil \cdot (c\_\> + c\_{+=} + c\_/) + c\_\>$,

reintroducing the full state symbolically; if $\psi = \\{ \dots, x := 5, \dots\\}$, then $\psi(x) = 5$.
* **Procedure Calls**

Given a program `P` of the form `M(x)` for some parameter(s) `x` where `M` is a procedure with (named) parameter `p`, assign costs

$\qquad\displaystyle C\_P(\psi) = c\_{\text{call}} + C\_M(\psi\_{\text{glob}} \circ \\{p := x\\})$.

Note again the extra constant $c\_{\text{call}}$ (which might in fact depend on $\psi$!). Procedure calls are expensive due to how they are implemented on real machines, and sometimes even dominate runtime (e.g. evaluating the Fibonacci number recurrence naively).

I gloss over some semantic issues you might have with the state here. You will want to distinguish global state and such local to procedure calls. Let's just assume we pass only global state here and `M` gets a new local state, initialized by setting the value of`p` to `x`. Furthermore, `x` may be an expression which we (usually) assume to be evaluated before passing it.

**Example:** Consider the procedure

```
fac(n) do
  if ( n <= 1 ) do         1
    return 1               2
  else                     3
    return n * fac(n-1)    4
  end                      5
end

```

As per the rule(s), we get:

$\qquad\displaystyle\begin{align\*} C\_{\text{fac}}(\\{n := n\_0\\}) &= C\_{1,5}(\\{n := n\_0\\}) \\ &= c\_{\leq} + \begin{cases} C\_2(\\{n := n\_0 \\}) &, n\_0 \leq 1 \\ C\_4(\\{n := n\_0 \\}) &, \text{ else} \end{cases} \\ &= c\_{\leq} + \begin{cases} c\_{\text{return}} &, n\_0 \leq 1 \\ c\_{\text{return}} + c\_\* + c\_{\text{call}} + C\_{\text{fac}}(\\{n := n\_0 - 1\\}) &, \text{ else} \end{cases} \end{align\*}$

Note that we disregard global state, as `fac` clearly does not access any. This particular recurrence is easy to solve to

$\qquad\displaystyle C\_{\text{fac}}(\psi) = \psi(n) \cdot (c\_{\leq} + c\_{\text{return}}) \+ (\psi(n) - 1) \cdot (c\_\* + c\_{\text{call}})$

We have covered the language features you will encounter in typical pseudo code. Beware hidden costs when analysing high-level pseudo code; if in doubt, unfold. The notation may seem cumbersome and is certainly a matter of taste; the concepts listed can not be ignored, though. However, with some experience you will be able to see right away which parts of the state are relevant for which cost measure, for instance "problem size" or "number of vertices". The rest can be dropped -- this simplifies things significantly!

If you think now that this is far too complicated, be advised: it *is*! Deriving exact costs of algorithms in any model that is so close to real machines as to enable runtime predictions (even relative ones) is a tough endeavour. And that's not even considering caching and other nasty effects on real machines.

Therefore, algorithm analysis is often simplified to the point of being mathematically tractable. For instance, if you don't need exact costs, you can over- or underestimate at any point (for upper resp. lower bounds): reduce the set of constants, get rid of conditionals, simplify sums, and so on.

### A note on asymptotic cost

What you will usually find in literature and on the webs is the "Big-Oh analysis". The proper term is *asymptotic* analysis which means that instead of deriving exact costs as we did in the examples, you only give costs up to a constant factor and in the limit (roughly speaking, "for big $n$").

This is (often) fair since abstract statements have *some* (generally unknown) costs in reality, depending on machine, operating system and other factors, and short runtimes may be dominated by the operating system setting up the process in the first place and whatnot. So you get some perturbation, anyway.

Here is how asymptotic analysis relates to this approach.

1. Identify *dominant* operations (that induce costs), that is operations that occur most often (up to constant factors). In the Bubblesort example, one possible choice is the comparison in line 5.

Alternatively, bound all constants for elementary operations by their maximum (from above) resp. their minimum (from below) and perform the usual analysis.
2. Perform the analysis using execution counts of this operation as cost.
3. When simplifying, allow estimations. Take care to only allow estimations from above if your goal is an upper bound ($O$) resp. from below if you want lower bounds ($\Omega$).

Make sure you understand the meaning of Landau symbols. Remember that such bounds exist for all three cases; using $O$ does not imply a worst-case analysis.

### Further reading

There are many more challenges and tricks in algorithm analysis. Here is some recommended reading.

There are many questions tagged around that use techniques similar to this.
> 159 votes

# Answer
## Execution Counts of Statements

There is another method, championed by Donald E. Knuth in his The Art of Computer Programming series. In contrast to translating the whole algorithm into one formula, it works independently from the code's semantics on the "putting things together" side and allows to go to a lower level only when necessary, starting from an "eagle's eye" view. Every statement can be analysed independently of the rest, leading to more clear calculations. However, the technique lends itself well to rather detailed code, not so much higher-level pseudo code.

### The Method

It's quite simple in principle:

1. Assign every statement a name/number.
2. Assign every statement $S\_i$ some cost $C\_i$.
3. Determine for every statement $S\_i$ its number of executions $e\_i$.
4. Compute total costs

$\qquad\displaystyle C = \sum\_{i} e\_i \cdot C\_i$.

You can insert estimates and/or symbolic quantities at any point, weakening resp. generalising the result accordingly.

Be aware that step 3 can be arbitrarily complex. It's usually there that you have to work with (asymptotic) estimates such as "$e\_{77} \in O(n \log n)$" in order to get results.

### Example: Depth-first search

Consider the following graph-traversal algorithm:

```
dfs(G, s) do
  // assert G.nodes contains s
  visited = new Array[G.nodes.size]     1
  dfs_h(G, s, visited)                  2
end

dfs_h(G, s, visited) do
  foo(s)                                3
  visited[s] = true                     4

  v = G.neighbours(s)                   5
  while ( v != nil ) do                 6
    if ( !visited[v] ) then             7
      dfs_h(G, v, visited)              8
    end
    v = v.next                          9
  end
end

```

We assume that the (undirected) graph is given by adjacency lists on nodes $\\{0,\dots,n-1\\}$. Let $m$ be the number of edges.

Just by looking at the algorithm, we see that some statements are executed equally often as others. We introduce some placeholders $A$, $B$ and $C$ for the execution counts $e\_i$:

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e\_i & A & A & B & B & B & B+C & C & B-1 & C \end{array}$

In particular, $e\_8 = e\_3-1$ since the every recursive call in line 8 causes a call of `foo` in line 3 (and one is caused by the original call from `dfs`). Furthermore, $e\_6 = e\_5 + e\_7$ because the `while` condition has to be checked once per iteration but then once more in order to leave it.

It's clear that $A=1$. Now, during a correctness proof we would show that `foo` is executed exactly once per node; that is, $B = n$. But then, we iterate over every adjacency list exactly once and every edge implies two entries in total (one for each incident node); we get $C = 2m$ iterations in total. Using this, we derive the following table:

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e\_i & 1 & 1 & n & n & n & 2m + n & 2m & n-1 & 2m \end{array}$

This leads us to total costs of exactly

$\qquad\begin{align\*} C(n,m) = (C\_1 + C\_2 - C\_8) &+\ n \cdot (C\_3 + C\_4 + C\_5 + C\_6 + C\_8) \\ &+\ 2m \cdot (C\_6 + C\_7 + C\_9) \\;. \end{align\*}$

By instantiating suitable values for the $C\_i$ we can derive more concrete costs. For instance, if we want to count memory accesses (per word), we'd use

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline C\_i & n & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{array}$

and get

$\qquad\displaystyle C\_{\text{mem}}(n,m) = 3n + 4m$.

### Further reading

See at the bottom of my other answer.
> 35 votes

# Answer
Algorithm analysis, like theorem proving, is largely an art (e.g. there are simple programs (like Collatz problem) that we do not know how to analyze). We can convert an algorithm complexity problem to a mathematical one, as answered comprehensively by Raphael, but then in order to express a bound on the cost of an algorithm in terms of known functions, we're left to:

1. Use techniques we know from existing analyses, such as finding bounds based on recurrences we understand or sum/integrals we can compute.
2. Change the algorithm to something that we know how to analyze.
3. Come up with a completely new approach.
> 10 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, proof-techniques, reference-question
---


# Question
Title: Scheduling Problem Optimisation using LP solvers
I am currently working on a scheduling system which schedules individuals based on **timeslots** that have the following attributes: (1) Day of Week (2) Month (3) Session(AM/PM).

The individuals currently indicate their preference for whether they prefer the AM/PM session for each day of the week in each month eg. (Monday|Jan|AM), this would mean that the person would prefer to do AM session for Mondays of January. Furthermore they are allowed to indicate that they do not want to be scheduled for certain months of the year, eg. he's able to choose that he does not want to do February time slots and thus my system is required to schedule him accordingly. \[Complexity\]

As such I currently am required to schedule this large set of data (individuals - 30 people / timeslots - 202). \[Large Set\]

I have been referred to by some advisors to look into Integer linear programming / linear programming in order to help me schedule these individuals optimally, thus I am currently looking into libraries such as Gurobi to help optimise the solution of this issue. I hope to be enlightened about the following question:

Would solution optimisers such as Gurobi be implementable in my scenario?

# Answer
Yes, your program can be modelled as an integer linear programming (ILP) instance, and yes, Gurobi is an ILP solver and can be used to solve your problem once you express it as ILP. I suggest you spend some quality time with a textbook that describes linear programming and integer linear programming.
> 1 votes

---
Tags: linear-programming, scheduling, integer-programming
---


title: $3EQ \leq _P 2EQ$

text:
# Question
Title: $3EQ \leq _P 2EQ$
Let:

* $2EQ$ - The language of all binary ($\mathbb{Z}\_2$) equation sets that have a solution in $\mathbb{Z}\_2$, where each multiplication is of at most two $x\_i,\\, x\_j$. Meaning a set of equations of the form: $\Sigma a\_i \cdot x\_i + \Sigma \\, \Sigma \\, a\_{i,j} \cdot x\_i \cdot x\_j = b $.
* $3EQ$ - Same just up to at most 3 multiplications, meaning a set of equations of the form: $\Sigma a\_i \cdot x\_i + \Sigma \\, \Sigma \\, a\_{i,j} \cdot x\_i \cdot x\_j + \Sigma \\, \Sigma \\, \Sigma \\, a\_{i,j,k} \cdot x\_i \cdot x\_j \cdot x\_k = b $.

I'd like to show that $3EQ \leq \_P 2EQ$, but I don't know how to deal with the expressions of $x\_i \cdot x\_j \cdot x\_k$. I thought about trying to represent them with using only at most two $\wedge$'s, but not sure if it's even possible. Maybe there's a better idea?

# Answer
> 3 votes
Hint: You can add a variable $x\_{ij}$ whose value is always $x\_ix\_j$ by adding the equation $x\_{ij}-x\_ix\_j=0$. This allows you to reduce cubic equations to quadratic ones.

# Answer
> 1 votes
They're both NP-hard, and both in NP, so they are both NP-complete. Therefore, there is a reduction between them.

Hint: Try proving that Independent SET $\le\_P$ 2EQ. Once you prove that, you should be able to take it from there, as the desired result follows immediately.

---
Tags: complexity-theory, turing-machines, reductions
---


# Question
Title: Integer factorization: comparing with floor
While working on integer factorization algorithm I came to the next problem:

$$\frac{a}{ex} = \lfloor{\frac{a}{ex}\rfloor} + c$$

* $a$ the number I want to factor
* $x$ factor of $a$
* $e$ positive integer that I choose

For $e = 1$ I found a linear representation for short sequences of $\lfloor{\frac{a}{x}\rfloor}$, this allows me to compare it to $\frac{a}{x}$ and find the value of $x$. The problem is that there are to many sequences, for this to be efficient. So I decrease their amount by using $e \> 1$. Unfortunately it created $c$, and now I have to test all its possible values, it looks some thing like this:

* for $e=2$, $c$ can be $\frac{1}{2}$
* for $e=3$, $c$ can be $\frac{1}{3}$ or $\frac{2}{3}$
* for $e=4$, $c$ can be $\frac{1}{4}$ or $\frac{2}{4}$ or $\frac{3}{4}$

Is there any way that I can predict the values of $c$, or give it a better estimation?

# Answer
The value of $c$ is given by the formula $$ c = \frac{(a/x) \pmod{e}}{e}. $$
> 1 votes

---
Tags: integers, factoring
---


title: Union of two finite automata?

text:
# Question
Title: Union of two finite automata?
How do you union of two finite automata as well as establish the transition table for it. I'm unsure of how to properly union the two finite automata. I believe the transition table would look something like this:

## state | a | b | a,b

```
x1|  x2 |  x3 |
x2|     |     |  x3
x3|     |     |  x3
y1|  y2 |  y3 |
y2|     |     |  y3
y3|     |     |  y3

```

I'm to sure how to properly develop the FA for these two diagrams. I would appreciate any links or advice on how to go about this.

# Answer
Hint from "Introduction to the Theory of Computation" by Michael Sipser (bible of theory of computation):

"We construct $M$ from $M\_1$ and $M\_2$ (the two original DFAs). To keep track of both simulation with finite memory you need to remember the state that each machine would be in if it had read up to this point in the input. Therefore you need to remember a pair of states...."

**Initial states:**

The start state will be a state constructed from the two original start states, i.e

$(x\_1,y\_1)$

**Transitions:**

What happens with input $a$?

Let's examine the two original automata:

$x\_1$ can transition to $x\_2$

$y\_1$ can transition to $y\_3$

Due to these facts we make the transition $\delta((x\_1,y\_1),a) = (x\_2,y\_3)$.

**Final/Accepting states:**

Any state pair $(x\_i,y\_j)$ where $x\_i$ was an accepting state in automata 1, or $y\_j$ was an accepting state in automata 2, i.e any state where $x\_2$ or $y\_2$ is mentioned.

One consequence is that the state we created a transition to i.e $(x\_2,y\_3)$, will be an accepting state.
> 3 votes

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


title: $25_r = 23_{10}$ solve for the base r

text:
# Question
Title: $25_r = 23_{10}$ solve for the base r
first of all this is a homework question and I don't want the solution. I just want a reference to how to solve similar questions like this. I believe it's explained my course textbook, "Computer Organization & Architecture: Themes and Variations" but I currently cannot afford the textbook.

Here's the question:

For each of the following numbers, state the base in use; that is, what are the values of r, s, and t?

a. $25\_r = 23\_{10}$

b. $1001\_s = 19684\_{10}$

c. $1011\_t = 4931\_{10}$

I recognize it's similar to solving an equation. I'm guessing I have to find r, s and t and they will be a specific base that matches the base ten number. I tried searching online for similar questions but I'm not sure what to search for so I have no clue where to start for solving these equations.

Any help would be appreciated.

# Answer
> 1 votes
Hint:

Consider $25\_{10}$. The number can be written as $5 \cdot 10^0 + 2 \cdot 10^1$.

How can $25\_{r}$ be written?

---
Tags: base-conversion
---


title: NP-Complete Proof of k sized common set

text:
# Question
Title: NP-Complete Proof of k sized common set
**Input:** A set $U= \\{w\_1, w\_2, \ldots, w\_n\\}$, subsets $S\_1, S\_2, \ldots, S\_m$ of $U$ and integer $k$.
**Question:** Is there a subset with $k$ elements of $U$ which intersects of every $S\_i$?

Which reduction should i use to prove that this is np-complete ?

**Hint:** Reduction from vertex cover.

# Answer
We will reduce vertex cover to our problem.

**Problem:** Vertex Cover
**Input:** Graph $G(V,E)$ and integer k
**Question:** Is there a subset $V'\subseteq$ V : $|V|\leq k$ which contains at least one vertex of each edge in $E$.

**Reduction:** For every $e\_i$ edge of $G$, we build a set $S\_i=\left \\{u\_i,v\_i \right \\}$ where $u\_i,v\_i$ are the incident vertices of $e\_i$. If there is a set with size k which intersects with every $S\_i$, it means that this set contains at least one vertex of each edge in $G$. In other words its a vertex cover with size k.
Because the reduction can be done in polynomial time and vertex cover $\in NP-Complete$, we can conclude that k sized common set is $NP-Complete$.
> 1 votes

---
Tags: np-complete, proof-techniques
---


title: Prove transitivity of big-O notation

text:
# Question
Title: Prove transitivity of big-O notation
I'm doing a practice question (**not** graded HW) to understand mathematical proofs and their application to Big O proofs. So far, however, the very first problem in my text is stumping me wholly.

Suppose $f(n) = O(g(N))$ and $g(n) = O(h(n))$ (all functions are positive).

Prove that $f(n) = O(h(n))$.

I am having lots of trouble with this, and it would be greatly helpful if someone showed me how to do this.

# Answer
> 5 votes
Consider using the definition of Big-O. If $f(n) \in O(g(n))$, then there exists a $c, n\_0 \> 0$ such that $f(n) \leq cg(n)$ for all $n \geq n\_0$. Similarly, we can write a similar inequality for $g(n)$. We have that if $g(n) \in O(h(n))$, then there exists a $d, n\_1 \> 0$ such that $g(n) \leq dh(n)$ for all $n \geq n\_1$.

To show what you are trying to show, consider putting both pieces together. Not only do we know that $f(n) \leq cg(n)$, but we also know that $g(n) \leq dh(n)$. Putting these two together gives $f(n) \leq c'h(n)$ where $c' = c \cdot d$, for the appropriate conditions. Can you verify what those are? In particular, for what values of $n$ does this hold?

From there, the desired result follows by definition of Big-O.

---
Tags: asymptotics, closure-properties, landau-notation
---


title: Heuristic for sokoban puzzle problem

text:
# Question
Title: Heuristic for sokoban puzzle problem
I am trying to write IDA\* for Sokoban puzzle problem (http://en.wikipedia.org/wiki/Sokoban) but It seems that my heuristic is not so good for making the algorithm fast.

My heuristic is to consider $h(s)$ as minimum distance between the Player and Boxes plus minimum distance between a Box and a Target in state $s$.

Can you please provide some better heuristics for this problem?

Edit: consider the number of Boxes(and Targets) is at most 3!

# Answer
Hi there CoderInNetwork,

That ain't an easy question and any advances regarding a good heuristic function would be very welcome. Indeed, I will refer in my answer to Andreas Junghanns' PhD written in 1999 (yeap, 16 years ago and still the current state of the art in the field). You can find it in citeseer:

Andreas Junghanns' PhD

Go to Section 4 and you will see a discussion about a heuristic function. The easiest one comes from a simple observation: every stone has to go to one and only one target location so you have to solve a *minimum cost perfect matching* in a *bipartite graph* where one set of vertices is made of the stones and the other one is made of the target locations ---so that there are obviously edges going only from the first set to the second and the goal is to find the minimum assignment of stones to goals. The cost of every edge would be equal to the estimated distance to get to the goal assigned from every stone.

This can be done in $O(n^3\log\_{2+\frac{n}{4}}n)$ using *minimum cost augmentation* ---again refer to Andreass Junghanns' PhD, Section 4.3.3 in page 52.

Even considering that this heuristic can be computed in an acceptable time (after making a good number of code optimizations) note that it does not account for *dead locks*. This is, it will naively move the stones without considering that either the walls or other stones can lead to unsolvable configurations.

From this observation, Andreas Junghanns introduced the idea of using *Pattern Databases* (PDBs) for improving this lower bound (see a discussion of their implementation in Chapter 5). At the time of writing his PhD, PDBs were not very well known but they are quite well known nowadays and a lot of progress has been made.

Finally, regarding your question: even if there are only 3 stones, problems can be really difficult to solve (or, at least, to solve *optimally* if that's what you are aiming for). See Appendix B, page 158, *The 61 Kids Problems* and you'll see lots of challenging problems. Many of those contain only 3 stones.

Hope this helps,
> 5 votes

---
Tags: search-algorithms, heuristics
---


# Question
Title: A* graph search heuristicfor pathfinding
A\* needs a consistent heuristic to work on a graph.

So I'm not sure if the heuristic of a straight line (bird flight) can be used.

For example: the costs to travel to a neighbors node is always positive.

```
              GOAL

 --------------------
 |                  |
 |      START       |
 |                  |    where to stripes are obstacles.

```

Am I correct that this the proposed heuristic isn't consistent here as it has to travel away from the goal first?

Is there a good heuristic for this kind of situation? Or should I keep it with Dijkstra a forget about A\*?

# Answer
Three points here:

1. A$^\*$ does not require consistency of the heuristic function (for this, I refer to the definition provided by Klaus Draeger, which is perfect). Instead, A$^\*$ requires *admissibility* of the heuristic function ($h(n)\leq h^\*(n), \forall n$ where $h^\*(n)$ is the optimal cost to reach the goal from a particular node $n$) or, in plain words, that it never overestimates the effort to reach the goal.
2. As a matter of fact, it has been proven that *inconsistencies* (while preserving *admissibility*) can be very beneficial. There are a number of papers on this issue but let me please refer the one which summarizes the most important findings: Ariel Felner, Uzi Zahavi, Robert Holte, Jonathan Schaeffer, Nathan Sturtevant, Zhifu Zhang. Inconsistent Heuristics in Theory and Practice. Let me put their main finding in this way: if a heuristic $h(n)$ is inconsistent but it preserves admissibility then there are points where by exceeding the cost of an edge (again, I am referring here to Klaus Draeger's definition) either the starting vertex or the ending vertex are better informed than the other. The authors then revise an old idea: the *Pathmax propagation rule* and show that it can be greatly enhanced in undirected state spaces resulting in the *Bidirectional Pathmax propagation rule* (BPMX).
3. Regarding your specific case, the *euclidean distance* or *aerial distance* however is both admissible and consistent so you should not bother about these issues ---it does not even matter if the optimal solution consists of moving away first from the goal to approach later, let A$^\*$ prove that for you.

Concluding: I would try the *euclidean distance* between the current location and the goal location to guide A$^\*$ to find optimal solutions in your domain. However, if you ever find out an inconsistent heuristic that serves this purpose to do not be afraid at all and just apply BPMX (which is a couple of lines of code, no more than that).

Hope this helps,
> 0 votes

# Answer
There is nothing wrong with the heuristic function you suggest. Note what the consistency condition actually says: If you have nodes $n\_1,n\_2$, and the cost of traveling from $n\_1$ to $n\_2$ is $c$, then the heuristic values need to satisfy a triangle condition: $h(n\_1)$ must not be more than $h(n\_2)+c$. It is ok for $h$ to underestimate the distance from a node, as it does for your start node (though obviously, the performance of the algorithm can suffer in this case).
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: CTL - model checking for formula $A [a \cup b]$
I'm trying to verify if the following model satisfy $A \[a \cup b\]$:

The algorithm I'm using is taken from "Concepts, Algorithms, and Tools for Model Checking", Joost-Pieter Katoen. In particular I applied the SatAU part (previous calculation of the states in which a and b are valid):

Intuitively the formula is verified in state $\\{s\_1, s\_2, s\_3, s\_4\\}$ (so the model does not satisfy the property because the set doesn't contain the other initial state $s\_0$). But if I apply the algorithm above the only state that I get are $\\{s\_2, s\_3, s\_4\\}$, **because the condition to generate the new $Q$ set (row 7) says to take a state s only if it has a connection with EACH element of the old $Q$ set.** Is it correct my interpretation of the algorithm? How can I get also $s\_1$ from the algorithm?

# Answer
> 3 votes
Your answer $Sat(A(a \cup b)) = \\{ s\_1, s\_2, s\_3, s\_4 \\}$ is correct. And your conclusion that the model does *not* satisfy the property is also correct because the initial state $s\_0 \notin Sat(A(a \cup b))$.

---

In my opinion, there is a *typo* in Line 7: $$Q := Q \cup \left( \\{ s \mid \forall s' \in Q. (s,s') \in R \\} \cap Sat(\phi) \right).$$

According to the fixed point interpretation, $Sat(A(\phi \cup \psi))$ is the smallest set $T \subseteq S$ satisfying $$Sat(\psi) \cup \\{ s \in Sat(\phi) | Post(s) \subseteq T \\} \subseteq T.$$ Therefore, the iteration step for Line 7 should be: $$Q := Q \cup \left( \\{ s \mid \forall (s,s') \in R. s' \in Q \\} \cap Sat(\phi) \right),$$ or concisely, $$Q := Q \cup \\{ s \in Sat(\phi) \mid \forall (s,s') \in R. s' \in Q \\}.$$

---

By the way, this lecture note by Joost-Pieter Katoen is quite out-of-date (back to 1999). In 2007, along with Christel Baier, he has published a wonderful book on model checking "Principles of Model Checking (The MIT Press)". You should read it now (online version avaiable).

---
Tags: logic, computation-tree-logic, temporal-logic
---


# Question
Title: Lower bounds for space with some probability of error
There is an information theoretic lower bound of $\log\_2 {U \choose x}$ for the number of bits to represent a subset of $x$ elements chosen from a universe of size $U$. We can in principle use this representation (perhaps inefficiently) as a data structure to test if any query is part of this subset.

How can you show a similar information theoretic lower bound if we are happy to have false positives with some probability $p$?

# Answer
In "Network applications of Bloom filters: A survey", Broder and Mitzenmacher show an $x \log\_2 (1/p)$ lower bound on the space usage.
> 2 votes

---
Tags: data-structures, information-theory, lower-bounds
---


# Question
Title: What does it mean for a function $f\colon M → N$ between *any* sets $M, N$ to be computable?
In our lecture notes on lamdba calculus, I encountered the sentence:

> Let $M$ be a set and $f\colon ℕ → M$ be computable.

Does this even make sense? Don’t we need aditional structure on $ℕ$ and $M$ to talk about computability and decidability? How can I make sense of this statement?

# Answer
> 2 votes
One convention is as follows. Your sets $\mathbb{N}$ and $M$ come with (injective) encodings as strings. In that way, you can think of $\mathbb{N}$ and $M$ simply as subsets of $\Sigma^\*$.

One can think of many other equivalent conventions. For example, you can treat the input as a bona fide natural number, and use the C programming language rather than the string-based Turing machine. All reasonable definitions will result in the same notion of computable function.

In terms of computational complexity, the exact encoding (or other convention) used can be important. For example, graphs can be encoded either using adjacency matrices or as adjacency lists, and this can affect the complexity of algorithms operation on them.

---
Tags: terminology, computability
---


# Question
Title: Determining if $G$ contains $K_4$ as a minor in polynomial time
I am trying to devise an algorithm for determining if an undirected graph $G$ contains $K\_4$ as a minor. I was able to show in a previous problem how to test for $K\_{2,3}$ by looking at all pairs of vertices and applying Menger's problem as a black-box on that pair of vertices (i.e checking for at least 3 vertex-disjoint paths). This gave an, although naive, $O(n^3)$ algorithm. However, the same trick doesn't seem to work for $K\_4$, since the same type of structure cannot be exploited. How can one test for $K\_4$?

I am also wondering what the best possible algorithm for $K\_{2,3}$ and $K\_4$ testing might be.... I seriously doubt that the brute-force approach highlighted above is optimal. Is there a known lower-bound?

# Answer
> 2 votes
I think your best bet would be to implement a treewidth 2 algorithm. We implemented one for an android app and you can find the source code of this specific implementation here: Treewidth. You can probably modify it to run in $O(n^4)$ time.

---
Tags: algorithms, graphs, lower-bounds
---


# Question
Title: Why are HMMs appropriate for speech recognition when the problem doesn't seem to satisfy the Markov property
I'm learning about HMMs and their applications and trying to understand their usages. My knowledge is a bit spotty, so please correct any incorrect assumptions I'm making. The specific example I'm wondering about is for using HMMs for speech detection, which is a common example in literature.

The basic method seems to be to treat the incoming sounds (after processing) as observations, where the actual words being spoken are the hidden states of the process. It seems obvious the hidden variables here are not independent, but I do not understand how they satisfy the Markov property. I would imagine that the probability of the Nth word is not just dependent on the N-1 word, but on many preceding words before that.

Is this simply ignored as a simplifying assumptions because HMMs are very good at correctly modeling speech detection problems, or am I not clearly understanding what the states and hidden variables in the process are? The same problem would appear to apply to a great deal of applications in which HMMs are quite popular, POS tagging, and so forth.

# Answer
On that subject I recommend you to read a very good paper by James Baker and others who were actually responsible for introduction of HMM in speech:

A Historical Perspective of Speech Recognition http://cacm.acm.org/magazines/2014/1/170863-a-historical-perspective-of-speech-recognition/abstract

> Using Markov models to represent language knowledge was controversial. Linguists knew no natural language could be represented even by context-free grammar, much less by a finite state grammar. Similarly, artificial intelligence experts were more doubtful that a model as simple as a Markov process would be useful for representing the higher-level knowledge sources recommended in the Newell report. However, there is a fundamental difference between assuming that lan- guage itself is a Markov process and modeling language as a probabilistic function of a hidden Markov process. The latter model is an approximation method that does not make an assumption about language, but rather provides a prescription to the designer in choosing what to represent in the hidden process. The definitive property of a Markov process is that, given the current state, probabilities of future events will be independent of any additional information about the past history of the process. This property means if there is any information about the past history of the ob- served process (such as the observed words and sub-word units), then the designer should encode that information with distinct states in the hidden process. It turned out that each of the levels of the Newell hierarchy could be represented as a probabilistic function of a hidden Markov process to a reasonable level of approximation. For today’s state-of-the-art language modeling, most systems still use the statistical N-gram language models and the variants, trained with the basic counting or EM-style techniques. These models have proved remarkably powerful and resilient. However, the N-gram is a highly simplistic model for realistic human language. In a similar manner with deep learning for significantly improving acoustic modeling quality, recurrent neural networks have also significantly improved the N-gram language model. It is worth noting that nothing beats a massive text corpora matching the application domain for most real speech applications.

Overall, the Markov model is pretty generic model for decoding black-box channel with very relaxed assumption on the transmission thus it is a perfect fit for the speech recognition, however, the question remains what to encode as a state indeed. It is clear that states should be more complex objects than what we assume now (just few preceding words). It is ongoing research to reveal true nature of such structure.
> 8 votes

# Answer
Hidden Markov Models were used to model phoneme units in words for speech recognition starting in the late 1980s.
> 3 votes

---
Tags: hidden-markov-models, markov-chains, speech-recognition
---


# Question
Title: Is it possble to store a counter that could reach $\lfloor \frac{N}{x}\rfloor$ using $\lceil\log_2(N+1)\rceil$ - $\lfloor\log_2 x\rfloor$ bits?
Let $x,N$ be positive integers.

I'd like to store a counter which could reach value of $\left\lfloor \frac{N}{x}\right\rfloor$ (i.e. could take any value in $0,1,\ldots,\frac{N}{x}$) using $$\lceil\log\_2(N+1)\rceil - \lfloor\log\_2 x\rfloor$$

bits.

Equivalently, does the following hold: $$\log\left\lfloor \frac{N}{x} + 1\right\rfloor \leq \lceil\log\_2(N+1)\rceil - \lfloor\log\_2 x\rfloor$$

Obviously, this holds for $x=1$, what about general $x$?

# Answer
**This is indeed possible.**

First, notice that for storing $\left\lfloor\frac{N}{x}+1\right\rfloor$ values ($0,1,2,\ldots,\left\lfloor\frac{N}{x}\right\rfloor$), you need $\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil$ bits (which might be larger than $\log\left\lfloor\frac{N}{x}+1\right\rfloor$). This won't stop us though :).

---

We first notice that for every $$\forall 1\<x,N\in\mathbb N:\left\lfloor\frac{N}{x}+1\right\rfloor\leq\left\lceil\frac{N+1}{x}\right\rceil$$ To see this, consider the case where $\frac{N}{x}\in \mathbb N$, and thus $$\left\lfloor\frac{N}{x}+1\right\rfloor = \frac{N}{x}+1=\frac{N}{x}+\left\lceil\frac{1}{x}\right\rceil=\left\lceil\frac{N+1}{x}\right\rceil$$ Otherwise, when $\frac{N}{x}\not \in \mathbb N$:$$\left\lfloor\frac{N}{x}+1\right\rfloor =\left\lceil\frac{N}{x}\right\rceil\leq\left\lceil\frac{N+1}{x}\right\rceil$$

Another useful inequality is $\forall r\geq 1:\log\left\lceil r\right\rceil\leq\left\lceil\log r\right\rceil$.

To see this, let $k\in \mathbb N$ such that $2^{k-1}\<r\leq2^{k}$.

Now $k-1\<\log r\leq k$, and therefore $\left\lceil\log r\right\rceil =k$. Now $\log\left\lceil r\right\rceil\leq k=\left\lceil\log r\right\rceil$.

Finally, we conclude that: $$\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil\leq\left\lceil\log\left\lceil\frac{N+1}{x}\right\rceil\right\rceil\leq\left\lceil\left\lceil\log\frac{N+1}{x}\right\rceil\right\rceil$$ $$=\left\lceil\log(N+1)-\log(x)\right\rceil$$ $$\leq\left\lceil\log(N+1)\right\rceil-\left\lfloor\log(x)\right\rfloor$$
> 2 votes

---
Tags: encoding-scheme, space-analysis
---