# Question
Title: Finding issues in concurrent implementation of carpark overflow control
Firstly, I am revising for my Concurrent Programming exam and have come across the following question from a previous exam paper. I have attempted to answer it, and will try and convey this effort; I'm very stuck with this question and not sure how to further progress.

### Question

This question is from a 2011 Past Paper from my University created by the Examining Body that year. Examiners: Professor E K Burke Dr P Sage and the internal examiners

> A car park has 100 parking spaces. Because of building work max cars must be accommodated in an overflow area which is accessed via the main car park. Entrance to the main and overflow areas is controlled by two automatic barriers as follows.
>
> * When the car park is empty both barriers are closed.
> * Normally, the main barrier is raised as a car approaches and is lowered immediately the car has entered.
> * An exception occurs immediately after the main car park is full i.e. when it has 100-max cars in it. As the next car approaches the overflow barrier is raised first, then the main barrier is raised. Once the car has entered the main car park the overflow barrier remains raised and the main barrier is lowered. The normal main barrier action described above then resumes.
>
> Consider the following program which is intended to control the two barriers.
>
> All instructions, o1, o2, o3, m1, m2, m3 and m4, are atomic. You may assume that $0 \< \max \leq 100$.
>
> ```
> int #cars=0;
>
> process Main {
> while (true)
>  {
>  m1: <#cars++>;
>  m2: <openMainBarrier>;
>  m3: <closeMainBarrier>;
>  m4: <if (#cars==100)
>      break>;
>  }
> }
>
> process Overflow {
> int max;
> o1: <input(max)>;
>  while (true)
>  {
>    o2: <if (#cars==100-max+1)  break>;
>    o3: <openOverflowBarrier>;
>  }
> }
>
> ```
> 1. The program terminates only if both processes terminate. Explain why the program may not terminate.
> 2. Explain why, even if the program does terminate, it may not operate as specified.
> 3. By introducing the use of semaphores, ensure that program does terminate and operates as specified. You must only use atomic instructions. You may introduce new additional non-semaphore variables but you must not alter the scope of #cars and max.

### My attempt

Most semaphore exercises I have looked at so far often have the main process in a `while(true){...}` infinite loop, thus, termination has never been an issue before - it is normally not addressed in these short exercises.

It is because of this I am having difficulty trying to produce an answer for 2) and 3). The question does not even appear to address cars leaving the car park, which leads me to understand this isn't an infinite ongoing cycle type process, but will terminate when both car parks reach maximum capacity?

In this instance, the only thing I can think of is that the process will not terminate in the event the main carpark or overflow carpark does not reach capacity, however I feel this answer is not 'clever' enough and I'm worried I may be missing something.

I have attempted 3) as follows but I am worried this is incorrect as I'm not sure if I am supposed to handle cars leaving the car park, or if I am supposed to ignore that in order to force it to terminate.

```
OverflowCarPark{
int max;
<input (max)>
while(true){
 down(maxFull)
 if(#cars <= 100 + max){
    down(openMainBarrier)
    up(openOverflowBarrier)
 }
  else { break; }
}

MainCarPark{
<cars++;>
while(true){
 if(#cars <= 100){
    up(openMainBarrier)
  } else if (#cars > 100 + max) { break;
  } else {
    up(maxFull);
    down(openOverflowBarrier);
 }
}

```

What is the recommended approach to dealing with termination here?

# Answer
> 2 votes
For the first task think about what might happen, if the loop in Overflow is not run for each car.

For the second task, look at the following things:

* How is the opening and closing of bars linked to arriving cars?
* Does the overflow bar really open at the $100-\max$-th car?
* The specification requests a specific order of opening and closing the bars. Is this enforced?

In the third task you should address the problems identified in the first two tasks by adding semaphores and possibly additional variables and atomic operations to the code.

Concerning your attempt and the questions therein:

* The setting as described assumes that no car leaves the car park.
* You may assume that eventually 100 cars will have arrived. (Otherwise you could not ensure termination.)
* You should mostly keep the operations m1-m4 and o1-o3 (depending on your approach you might change one or two of them). Just add additional code around and inbetween them, in order to address the problems.
* You use $100+\max$ twice, where you probably intended to use $100-\max$.
* Using max in Process Main is changing its scope, since in the original code it is a variable local to Process Overflow.
* Also your code does not solve most of the problems I hinted at for task 2. (This is no surprise, given that you had not identified them, when writing the code.)

---
Tags: algorithms, concurrency, synchronization, mutual-exclusion
---


# Question
Title: Creating admissible heuristics from functions?
I'm having trouble figuring out how to create admissible heuristics from cost functions. For example, if I was trying to create an admissible heuristic from a cost function that takes in starting position and ending position and returns the cost based on differences in height, I don't understand how to create an admissible heuristic from such a basic function.

Any help would be greatly appreciated.

# Answer
Most beginners in the field see heuristics construction more as an art than a science. While I am not claiming here that there is a truly scientific (or even computable) method to derive them, I am sure they are not an art and we know about specific procedures to derive them (some of which are truly computable). In any case, we do not consider the differences in cost between the goal and start states as you suggest in the question. In all cases, admissible heuristics are obtained after *relaxing* any component in the problem formulation.

Let me just introduce you to three different methods to compute *admissible* heuristics: *constraint relaxation*, *pattern databases* and *max heuristics*. First, I will just introduce the overall idea. Next, I will provide further details of every technique. I will try to mention also some of the most relevant works that went along any of these lines including merge-and-shrink and Linear Programming.

In all cases, I will refer to the definition of *state spaces* which consist of two main ingredients:

* *States*: they are defined by any structure that represents the contents of either the start or final state (denoted as $s$ or $t$ respectively) or any other configuration.
* *Operators*: computable functions that are used to derive the immediately reachable descendants of a given state

Also, I will be using the $N$-puzzle as a running example. The proper definition of a *state space* in the $N$-puzzle is as follows:

* *States*: they are defined by a permutation $\pi$ of symbols such that $\pi\[i\]$ represents the contents of location $i$
* *Operators*: there is only one *move (i,j)* which swaps the contents of locations $i$ and $j$ provided that $\pi\[i\]=0$ (i.e., the blank location) and that $i$ and $j$ are either vertically or horizontally adjacent.

Please, be aware of the following: these techniques are not so simple that I could fully explain them in detail in a single response so that, unfortunately, my explanations will be rather incomplete

**Constraint relaxation** \[Judea Pearl. Heuristics. Addison-Wesley, 1984\] Judea Pearl proposed to pay attention to the constraints of the problem (and there should be some, otherwise we would not have an optimization problem), and then to relax a subset of them so that the resulting problem could be optimally solved. The optimal cost of the so-called *relaxed problem* can be easily proved to be an *admissible* estimate to reach the goal state. The constraints are usually found (but not only) in the pre-conditions implemented in the operators.

Take the $N$-puzzle. In this case, the constraints are found in the operator *move*. How would you program such a function? Well, most likely you would verify that $\pi\[i\]=0$ (i.e., $i$ is the blank location) and that $i$ and $j$ are either vertically or horizontally adjacent locations. Now, select either one of these constraints or both and relax them.

For example, relax both and consider now the resulting (*relaxed*) problem. For any state, how many moves does it take to get to the target node? If you are not constrained (and this is the point) to consider adjacent locations or the fact that you have to move the blank then *you can swap any pair of locations*. The optimal solution of the relaxed problems consists just of swapping the misplaced tiles.

Another example, relax only the first one. In this case, you are forced to swap adjacent locations but you are free to ignore the role of the blank tile. Clearly, the optimal solution consists of the sum of the minimum number of horizontal and vertical moves to place every misplaced tile in its goal location. This is known as the *Manhattan distance*.

In general, the heuristics that relax less constraints produce better estimations and are prefered.

**Pattern databases** \[Culberson, J. C., Schaeffer, J. 1998. Pattern Databases. Computational Intelligence 14(3): 318-334\] Constraint relaxation is just a general procedure that you, as an optimizer, have to follow in order to derive an admissible heuristic that you hard-code in your programs. *Pattern databases* are, instead, computable means to derive automatically the heuristic value of a lot of different configurations which are then stored in a large table.

I will not go here through more detailed explanations and I do suggest you instead to have a look at Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle I am also providing a reply there but I do strongly suggest you to have a look at the response by Shashwat which is more detailed and uses the $N$-puzzle instead for explaining the main ideas. If you are interested in getting the source code for creating Pattern Databases, please e-mail me (carlos.linares@uc3m.es).

In case you are interested in the current state of the art of admissible heuristics in Automated Planning (introduced next) I do recommend you to have a look at *merge-and-shrink* (which do generalize Pattern Databases). A nice discussion is offered in: Malte Helmert, Patrik Haslum, Jörg Hoffmann and Raz Nissim. Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces. Journal of the ACM. 2013 (which was accepted at the time of writing but has not seen the light yet as far as I know).

Also, there has been some work on using Linear Programming Tasks to get the optimal cost of the relaxed problems:

(**NOTE**: all this people are really nice, so that if you contact them to get a copy of the paper to appear it is very likely that they will send it to you. The other option is to wait for ICAPS 2014 to take place and then to download the papers: they are absolutely free).

Note please that, in this context, Linear Programming Tasks are used just to derive optimal costs of the relaxed problems precisely in the same way noted by Raphael: you first relax some constraints (according to any procedure) and then you set up a LP task to derive the optimal cost. I do fully believe that this is a hot topic in the field that will get more and more attention.

**Max heuristics** \[Blai Bonet and Héctor Geffner. Planning as Heuristic Search: New Results. Proc. 5th European Conf. on Planning (ECP). Durham, UK. 1999. Springer LNCS 1809. Pages 359-371\] The two previous methods for deriving (either automatically or not) admissible heuristics were motivated by the need of creating domain-dependent solvers. However, what if you want to create a single solver that is expected to optimall solve any problem (with some constraints, of course, and not just saying that "The Answer to life, the universe and everything is 42" :) )? This field is known as *Automated Planning* In this case we relax the reachability analysis by ignoring the delete effects (i.e., the fact that when swapping two locations they are removed from their initial locations; indeed, they are preserved so that the same tile appears in various places at the same time in the relaxed problem).

We just assume that all actions can be executed in parallel and compute the minimum cost to reach every literal (i.e., any atomic observation of our state formulation such as tile 6 is in location 2) from any other literal. You can certainly assume that actions have to be executed in sequence. In this case, the resulting heuristic is known as *h add* but it is not admissible so I left out of the discussion.

I am just leaving a lot of details out of the discussion here and I do recommend you to have a look at the paper I am just referencing. This is a simple, very simple idea.

Hope all of this helps,
> 5 votes

---
Tags: algorithms, heuristics
---


# Question
Title: Distributivity of $\omega$-regular expressions
Recall that a language is $\omega$-regular if and only if it is recognized by a Büchi automaton. How can I prove that

$\qquad (E\_1 + E\_2).F^\omega$

is equivalent to

$\qquad {E\_1.(F^\omega)+E\_2.(F^\omega)}$

where

* both expressions are *omega* regular expressions, and
* $E\_1$, $E\_2$ and $F$ are *arbitrary regular expressions* with $\epsilon \notin L(F)$.

One way I could think of is to convert expression to a DFA and check if it is equivalent.

Or I will really appreciate a hint on how to do the equivalence proof, but how to represent $E\_1$, $E\_2$ and $F$ in DFA.

# Answer
> 6 votes
As suggested by Raphael, here's a proof doing it via the sets represented by those expressions.

$\qquad L\_\omega((E\_1+E\_2) \cdot F^\omega) \\\= L(E\_1+E\_2) \cdot L\_\omega(F^\omega) \\\= (L(E\_1) \cup L(E\_2)) \cdot L\_\omega(F^\omega) \\\= \\{w\_1w\_2 | w\_1 \in (L(E\_1) \cup L(E\_2)) \wedge w\_2 \in L\_\omega(F^\omega) \\} \\\= \\{w\_1w\_2|(w\_1 \in L(E\_1) \wedge w\_2 \in L\_\omega(F^\omega)) \lor (w\_1 \in L(E\_2) \wedge w\_2 \in L\_\omega(F^\omega))\\}\\\= \\{w\_1w\_2|(w\_1 \in L(E\_1) \wedge w\_2 \in L\_\omega(F^\omega))\\} \cup \\{w\_1w\_2|(w\_1 \in L(E\_2) \wedge w\_2 \in L\_\omega(F^\omega))\\} \\\= (L(E\_1)\cdot L\_\omega(F^\omega)) \cup (L(E\_2)\cdot L\_\omega(F^\omega))\\\=L\_\omega(E\_1 \cdot F^\omega) \cup L\_\omega(E\_2 \cdot F^\omega)\\\=L\_\omega(E\_1\cdot F^\omega + E\_2 \cdot F^\omega)$

So the only thing that's actual work here is to translate the logical operators into set operators.

# Answer
> 3 votes
The question has nothing to do with ($\omega$-)regular languages. Indeed, it is a consequence of the equality $$ (L\_1 + L\_2)L = L\_1L + L\_2L $$ which holds for all subsets $L\_1, L\_2$ of $A^\*$ and all subsets $L$ of $A^\omega$. The proof is straightforward: if $w \in (L\_1 + L\_2)L$, then $w = uv$ for some $u \in L\_1 + L\_2$ and some $v \in L$. Thus either $u \in L\_1$ or $u \in L\_2$ whence either $uv \in L\_1L$ or $uv \in L\_2L$. In the opposite direction, if $w \in L\_1L + L\_2L$, then either $w \in L\_1L$ or $w \in L\_2L$. In the first \[second\] case, $w = uv$ for some $v \in L$ and some $u \in L\_1$ \[$u \in L\_2$\]. In both cases, $w \in (L\_1 + L\_2)L$.

# Answer
> 2 votes
We have to show that

$\qquad (E\_1 + E\_2).F^\omega = E\_1.(F^\omega) + E\_2.(F^\omega)$.

We have do to some preparation. $E\_1, E\_2$ and $F$ are regular expressions, so they have (deterministic) finite automata $A\_1, A\_2, A\_F$. It is easy to see that we can construct NBA for the left and right hand side from those, respectively:

\[source\]

\[source\]

Showing that these are correct should be a simple exercise, given the proof for the equivalence of $\omega$-regular expressions and NBA you should have seen.

Note that the transitions going into the DFA connect with their respective initial states, while the outgoing one originate from their final states (w.l.o.g. there is only one in each DFA).

Now, as usual, show $\subseteq$ and $\supseteq$ separately. Both directions work in the same way; let's look at it for $\subseteq$.

Assume a word $w$ is in the language generated by $(E\_1 + E\_2).F^\omega$. Then, there is an accepting (infinite) path in above automaton. The same path basically works for the lower automatong: depending on whether the run goes through $A\_1$ or $A\_2$, replace $q\_m$ with $q\_{m1}$/$q\_{m2}$ and $q\_e$ similarly.

A similar construction works for $\supseteq$.

---
Tags: regular-expressions, buchi-automata
---


# Question
Title: Find the centre of a circle given two points lying on it and its radius
We have been given 2 points on a circle and its radius. Now I want to find out the centre point of such a circle. How can I code this efficiently without solving the quadratic equations?

# Answer
> 1 votes
$$INPUT \rightarrow P\_1(x\_1, y\_1), P\_2(x\_2,y\_2), r$$ $$d=\sqrt{(x\_1-x\_2)^2+(y\_1-y\_2)^2}$$ $$h=\sqrt{r^2-(\frac{d}2)^2}$$ $$\alpha=arcsin(\frac{y\_1-y\_2}{d})$$ $$x\_c=\frac{x\_1+x\_2}2+h sin(\alpha)$$ $$y\_c=\frac{y\_1+y\_2}2+h cos(\alpha)$$

# Answer
> -1 votes
\begin{align\*} \mathbf{v} &= (\mathbf{p\_2} - \mathbf{p\_1}) = \begin{pmatrix} v\_x \\ v\_y \end{pmatrix} \\ h &= \sqrt{r^2 - \frac{\lvert \mathbf{v} \rvert^2}{4}} \\ \mathbf{u\_h} &= \frac{1}{\lvert \mathbf{v} \rvert} \begin{pmatrix} v\_y \\ -v\_x \end{pmatrix} \\ c\_{1,2} &= \mathbf{p\_1} + \frac{1}{2} \mathbf{v} \pm h\mathbf{u\_h}\\ \end{align\*}

The algorithm is obvious, it's complexity should be $O(n^2)$.

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


title: Data Structure For Closest Pair Problem

text:
# Question
Title: Data Structure For Closest Pair Problem
Suppose I have a list of distinct integers. I'm looking for a data structure that will support the operations `search`, `insert`, `delete` and `closest_pair` in $O(\log n)$ time.

I know that a sorted array supports `search`, `insert` and `delete` in $O(\log n)$ time. So, all we need to do is maintain information about the closest pair during the `insert` and `delete` operations.

The only problem is that the `closest_pair` would perform in better than $O(\log n)$ time since information about the closest pair would already be available. So, I'm stuck at this point.

# Answer
> 7 votes
Your confusion appears to arise from a misunderstanding: $O(\log n)$ means "proportional to $\log n$ **or better**". So being able to get the closest pair in constant time is not a problem.

While you seem to already have found a solution to the original problem, I'll still give hints towards a solution, in order to make this answer helpful for other people stuck with that problem.

Hint 1: Basic data structure to start from: (Contrary to the claim in the current version of the question, a sorted array does not work, since you can not insert or delete in an array in $O(\log n)$.)

> A height balanced binary search tree (e.g. AVL tree) works.

Hint 2: What additional information should be stored:

> Each node stores: the smallest and largest value in the subtree below this node and the closest pair in that subtree.

Hint 3: How to update the information in a single node:

> * The smallest value is the smallest value in the left subtree (or the value of the node itself, if no left subtree is present).
> * The largest value is the largest value in the right subtree (or the value of the node itself, if no right subtree is present).
> * There is no closest pair in a leaf.
> * In an inner node there are at most 4 candidates for the closest pair:
>     1. The closest pair in the left subtree,
>     2. the closest pair in the right subtree,
>     3. the pair (largest value in the left subtree, value of the node) and
>     4. the pair (value of the node, smallest value in the right subtree). Simply compute minimum of these.

Finally: How to do the operations:

> - $\text{search}$ just ignores the additional information.
> - $\text{closest\_pair}$ reads the required information from the root node.
> - $\text{insert}$:
> 1. perform a normal AVL-insert
> 2. update all nodes on the path from the inserted leaf to the root and all nodes affected by rotations (starting at the leaf)
> - $\text{delete}$:
> 1. perform a normal AVL-delete
> 2. update all nodes on the path from the deleted leaf to the root and all nodes affected by rotations (starting at the leaf)
> If the descent into the tree in insert and delete is done via recursion, the updates can --just as the rotations -- be done when returning from the recursive calls.
> Of course, once a node is unchanged, the nodes above it will remain unchanged as well (unless affected by a rotation).

---
Tags: data-structures, search-algorithms
---


# Question
Title: Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem
This is a question from an exam I did today:

> Given $M$, a turing machine, we need to decide the following:
>
> 1) $M$ halts on every input
>
> 2) The language of $M$ is CFL

My question is, can I prove that this problem is not in $RE$ (recursively enumerable) using Rice's theorem? I understand that Rice's theorem works for languages and not machines, and when first looking at it, number 1 is a property of a machine not the language. But what I said, is that actually it *is* a property of a language: $M$ halts on every input *iff* $L(M)$ is decidable! (in $R$), so we can use Rice.

What do you think?

# Answer
First of all, it is not true that $M$ halts on every input iff $L(M)$ is decidable. Indeed, $L(M)$ can be decidable even if $M$ doesn't halt on every input. Consider for example the machine which never halts on any input—the empty language is certainly decidable.

Rice's theorem considers properties of *partial functions*. The partial function is the one computed by the Turing machine, with $\bot$ representing the case that the Turing machine doesn't halt on a specific input. If a machine $M$ always halts then the corresponding function is total—never attains the value $\bot$. This is a property of partial functions, and fits within the framework of Rice's theorem.

If you're not sure about this, have a look at the proof that the language of total Turing machines (ones that halt on all inputs) is not decidable.
> 2 votes

---
Tags: computability, semi-decidability
---


# Question
Title: Instruction Set Architecture (ISA) design
Yes, this is a homework question, I've tried working it out and was hoping I could get pointed in the right direction.

## Here's the question:

You are designing the instruction set for a new type of computer. The computer has 64 instructions, 16 general-purpose registers. It supports a byte-addressable memory of up-to 32MB. Answer the following question:

a. For a 3-operand ADD instruction that only uses register addressing mode, how long (number of bits) should the instruction be?

b. For a 2-operand ADD instruction, in which one of the operands is a memory location with direct addressing mode, how long (number of bits) should the instruction be?

---

I know the question's been asked recently but both questions and answers weren't helpful.

I know that with 64 instructions and 16 registers, there must be 4 bits per register. I don't exactly know the usage for the 32MB memory right now.

A similar example of part (a) exists on Wikipedia, where it states 4 instructions are needed for a 3-operand register addressing mode (load reg1 into a load reg2 into b, add reg1 and reg2 to reg3, store reg3 in c). Because it mentions 4 instructions, I thought that would be 1 bit, but that's a really small amount. There are 3 registers used in the instruction, which would be 12 bits.

For part (b), I believe one is a memory location with a direct addressing mode (as stated) and the other is like part (a), using register addressing mode. There are only two operands, but only one is using register addressing mode, meaning only one register is used? In that case, the length of the instruction should be 4 bits.

I would appreciate any help! If I'm misunderstanding some of the terms please let me know! Thanks!

# Answer
> 3 votes
Hint: If there are $X$ of some resource, then it takes $\log\_2 X$ bits to encode which of them you chooses. This includes instructions, registers, and memory locations. If you are encoding $N$ copies of the resource, you will need $N\log\_2 X$ bits. The instruction should contain an encoding of everything needed to specify it, including the instruction itself.

(Real life CPUs don't quite behave this way. For example, common instructions could have shorter length.)

Example: A computer has $956$ instructions. The instruction NOP takes $\lceil \log\_2 956 \rceil = 10$ bits.

Another example: A computer has $13$, and $100$ I/O ports. The instruction IN , which reads a byte from the port into the accumulator, takes $\lceil \log\_2 13 \rceil + \lceil \log\_2 100 \rceil = 11$ bits.

Yet another example: A (useless) computer has a single instruction but $10000$ registers. The single instruction takes $10$ of them and does something really complicated. It takes $\lceil \log\_2 1 \rceil + 10 \lceil \log\_2 10000 \rceil = 140$ bits to encode.

---
Tags: computer-architecture, memory-management
---


# Question
Title: AVL Trees - Maintaining Closest Pair information on a Delete
In the accepted answer to my question Data Structure For Closest Pair Problem, I do not see why deletion works.

Let's say (x, y) are the closest pair before the delete. If the node to be deleted is either x or y, then we would have to recalculate the closest pair, which would not satisfy the O(log n) requirement. The best solution I currently see is that each time a "new" closest pair occurs during an insertion, we link it to the previous closest pair. That is, instead of storing just the closest pair in the root node, we store a linked list of closest pairs. However, this seems like overkill.

Is there a better way resp. why does the proposed solution work?

# Answer
The solution I posted on your previous question does work.

To recap, I suggested to maintain in each node:

* The largest and smallest element in the subtree below this node and
* the closest pair in that subtree.

On `insert` and `delete`, update the information in every node on the path from the inserted/removed leaf to the root and every node affected by a rotation.

Intuitively, this works since the information on the closest pair for each unaffected subtree is stored in the root of that subtree and our update will look at the roots of all maximal unaffected subtrees (and all nodes affected by the upadte). Thus, implicitly, our update will look at the complete tree, in order to find the new closest pair.

In order to show more formally that the update is correct for the root (the only node, where we actually need the annotation), we can show that the following stronger invariant holds:

> After each operation the annotations in all the nodes are correct.

This is obvious for operations that don't change the tree. For `insert` and `delete`, we distinguish two classes of nodes:

* If the subtree below the node is unchanged, the annotations that were correct before still are.
* If the subtree below the node is changed, then the node must be on the path from the inserted/removed leaf to the root or affected by a rotation. In this case we explicitly update the information, so it will be correct.

That the update of each node will produce a correct annotation, can be shown by a simple induction, using the following arguments:

* (Anchor): The procedure is correct for leaves.
* (Step): If the information in both children is correct then the described procedure will produce the correct annotation for the parent node.
> 3 votes

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


# Question
Title: Theoretical foundations of Divide and Conquer
When it comes to the design of algorithms, one often employs the following techniques:

* Dynamic Programming
* The Greedy-Strategy
* Divide-and-Conquer

While for the first two methods, there are well-known theoretical foundations, namely the Bellman Optimality Principle and matroid (resp. greedoid) theory, I could not find such a general framework for algorithms based on D&C.

Firstly, I am aware of something that we (or rather, the prof) introduced in a functional programming class, called an "algorithmic skeleton", that arose in the context of combinators. As an example hereof, we gave such a skeleton for D&C algorithms as follows:

**Definition**: Let $A,S$ be non-empty sets. We call the elements of $S$ *solutions*, and the elements of $P:=\mathfrak{P}(A)$ (that is, the subsets of $A$) are referred to as *problems*. Then, a *D&C-skeleton* is a 4-tuple $(P\_\beta, \beta, \mathcal{D}, \mathcal{C})$, where:

* $P\_\beta$ is a predicate over the set of problems and we say that a problem $p$ is *basic* iff $P\_\beta(p)$ holds.
* $\beta$ is a mapping $P\_\beta \rightarrow S$ that assigns a solution to each basic problem.
* $\mathcal{D}$ is a mapping $P \rightarrow \mathfrak{P}(P)$ that divides each problem into a set of subproblems.
* $\mathcal{C}$ is a mapping $P\times \mathfrak{P}(S) \rightarrow S$ that joins the solutions (depending on kind of a "pivot problem") of the subproblems to produce a solution.

Then, for a given skeleton $s=(P\_\beta, \beta, \mathcal{D}, \mathcal{C})$ and a problem $p$, the following generic function $f\_s: P\rightarrow S$ computes a solution (in the formal sense) for $p$:

$f\_s(p)= \left\\{ \begin{array}{l l} \beta(p) & \quad \text{if $p$ is basic}\\ \mathcal{C}(p,f(\mathcal{D}(p))) & \quad \text{otherwise} \end{array} \right.$

where in the second line we use the notation $f(X) := \\{f(x) : x\in X\\}$ for subsets $X$ of the codomain of a mapping $f$.

However, we did not further examine the underlying, "structural" properties of problems that can be formulated this way (as I said, it was a functional programming class and this was only a small example). Unfortunately, I could not find further reference on this very approach. Hence I don't think the above definitions are quite standard. If someone recognizes what I have stated above, I would be glad about related articles.

Secondly, for the greedy strategy we have the famous result that a problem is correctly solved by the general greedy algorithm if and only if its solutions constitute a weighted matroid. Are there similar results for D&C-algorithms (not necessarily based on the method outlined above)?

# Answer
> 5 votes
A formal treatment (somewhat resembling the model proposed in the question) of the subject using what is called *pseudo-morphisms* (that is, functions that are *almost* morphisms, with some pre- and post-computation done), as well as considerations of complexity analysis and parallel implementation of such algorithms are given in:

An algebraic model for divide-and-conquer and its parallelism by Zhijing G. Mou and Paul Hudak (in The Journal of Supercomputing , Volume 2, Issue 3, pp. 257-278, November 1988)

# Answer
> 2 votes
I'm not aware of something as concrete as Bellman's Optimality Principle for Divide and Conquer algorithms. However, the underlying foundation of divide and conquer seems to me to be a recursive (or inductive) definition of the problem's input and then a means of combining solutions to the problem in to larger solutions. The key insight here is thinking about problem inputs recursively and leveraging that in to recursive, D&C algorithms.

Take mergesort as an example. Let's begin with the input, an array of $n$ elements. One can *recursively define the structure of the array* as follows:

* For $n=0$, the array is empty.
* For $n=1$, The array is a singleton element
* For $n\>1$, the array is the concatenation of an array of of size $\lceil{\frac{n}{2}}\rceil$ (*left*) and size $\lfloor{\frac{n}{2}}\rfloor$ (*right*)

We then approach the mergesort algorithm by then mapping *sort* to this structure. The base cases, where $n\leq1$ are trivially sorted. The recursive case begins by *recursively sorting where the data is recursive*, namely *left* and *right*. We then essentially find a replacement for *concatenate*, which ends up being *merge*. So notice we've basically just taken the recursive structure of the data and mapped that to a recursive solution.

It's important to note that this doesn't necessarily lead to what you expect from D&C algorithms. We could define the array structure as follows:

* For $n=0$, the array is empty.
* For $n\>0$, the array is a single element concatenated to an array of size $n-1$.

Following the same strategy we used for mergesort here leads to recursive insertion sort. So, typically we develop recursive definitions that involve multiple recursive elements, i.e. cut the data set in half or third.

Now, there is the Master Theorem for analyzing D&C algorithms and this sheds some light on the efficiency expectations for the sub-components of a D&C algorithm with a particular overall run-time efficiency.

---
Tags: algorithms, reference-request, divide-and-conquer
---


# Question
Title: How to measure processing power of a quantum computer?
Is there any way to get an equivalent of computing power of quantum computers in terms of computing power of common computers? I mean, how many teraflops (or so) can a quantum computer compute? How can I calculate that equivalence? I think it depends on the architecture, like a x64 in common computer, and a 512-qubit.

# Answer
this is a very difficult/subtle/controversial question at the heart of current research that even topnotch scientists are having a lot of trouble answering precisely. there are two main lines of QM computer development:

* adiabatic QM computing, this is the Dwave computer that is up to 512 qubits, but it doesnt operate using "qbit transport" which is the main line of scientific research
* "standard" QM computing transports qbits so their spins can interact as laid out in "quantum circuits". there is a lot of theoretical research on this topic but physics researchers are apparently still far from actually implementing (physically building/realizing) this type of computing.

unfortunately in both cases there are other further issues:

* theoretically, can one get a speedup based on the mathematics/physics of quantum computing? see eg proof of speedup with \[adiabatic\] qm computing tcs.se
* in practice, after one builds the computer, and one applies various systems, eg error correction being one of the main ones, and decoherence being one of the main challenges to overcome, how efficient will it be? will there be any speedup over conventional computing?
* QM algorithms run completely differently, they are not based on binary logic! so therefore there is not yet any way to determine what the "equivalent" or "corresponding" qm algorithm is to a "classical" algorithm that is under consideration. the best we can do is try to optimize the performance of both & see what happens but that is obviously not satisfactory and somewhat dependent on human factors.

so the best answer right now is "nobody can really say right now". or, the best quantum computer in the world, Dwave, (apparently costing in \\$ millions per unit, and over $100M research so far) is now shown in scientific papers to be slower than desktop computers when algorithms are optimized on those computers. or, "its an open question subject to cutting edge international research". there are many posts in Aaronsons blog on the subject. see also
> 2 votes

---
Tags: terminology, quantum-computing
---


title: What is a clairvoyant algorithm?

text:
# Question
Title: What is a clairvoyant algorithm?
When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes on to say:

> Amortized cost can be:
>
> * absolute (e.g. for every sequence σ of operations (O(n log n))
> * competitive (e.g. for every sequence σ of operations O(OPT(σ)))
>
> where OPT(σ) is the optimal cost of clairvoyant algorithms

I can't really make any sense of this. Googling throws up this but I can't see the relevance to data structures more generally. Can anyone help me understand the quoted text?

# Answer
A clairvoyant algorithm is a (usually hypothetical) algorithm that can look into the future to guarantee that it makes the best possible decisions. The typical application is in so-called "online" problems, where the input must be processed as it arrives, before the whole input is known, or in other situations where an algorithm must act based on incomplete knowledge. The point is that the hypothetical clairvoyant algorithm would be able to make perfect decisions so you can use that as a benchmark to judge your real algorithm for the problem.

The example given in the page you link is for page replacement algorithms. You need to swap some page of virtual memory out to disk and, of course, you'd rather not swap out a page that's just about to be accessed. The hypothetical clairvoyant algorithm would know which page will not be needed for the longest time and will swap that one out; a real algorithm would have to estimate, for example by assuming that a page that has not been used for a long time will not be used again in the near future.

Now, you can do a comparison. Suppose you have enough physical memory to hold 1000 pages and you have a process that cycles through 1001 pages accessing them in the order 1, 2, ..., 1000, 1001, 1, 2, ... The real algorithm performs terribly in this case: when page 1001 is requested, it swaps out page 1, which is the very next page to be requested. In fact, the page the process requests is never in memory. A clairvoyant algorithm might, for example, keep pages 1–999 in memory all the time and swap in pages 1000 and 1001 as needed, giving page faults only 0.2% of the time.

Other applications of this sort of idea are things like process scheduling (in most cases, a real algorithm doesn't know what demands a process will make, so it must guess) and various auction schemes where the auctioneer uses the early bids to figure out what people are prepared to pay for an item, before selling it to the next highest bidder. The classic pop-science application is in deciding who you should marry which, for some reason, academics call the Secretary Problem. The clairvoyant algorithm would be to magically know who your ideal partner is and marry them; the best you can do in practice is to spend a few years dating and dumping people and then marry the next person you meet who is better than all the ones you dumped. (This carries the risk that you'll meet your ideal partner during the date-and-dump phase and then never meet anyone else that good; math doesn't always make your life better.)
> 10 votes

---
Tags: algorithms, terminology, data-structures, amortized-analysis
---


# Question
Title: Arithmetic code: from interval to code value
I've not clear how to pass from final interval to code value, for example:

Suppose we have the set of **symbols**={0,1,2,3} with **probability**={0.2, 0.5, 0.2 , 0.1} and that we have to encode a **source** S={2,1,0,0,1,3};

After the encoding process we'll have an interval $\[ 0.7426, 0.7428 ) $.

Now the final step is to find the shortest representation to transmit and in the book the chosen value is **0.10111110001** = **0.74267578125**.

> How is it possible to calculate the shortest representation and the code value to transmit having the final interval?

# Answer
You transmit the bit pattern of the left(smaller) end, until you either run out of bits or you find a difference of the left and the right (bigger) number. The first difference will have a 0 on the left side, and a 1 on the right side. If this 1 is not the last bit on the right side, you transmit this 1 and you are done, you transmitted the shorted number from within the interval.

```
a=0011001100
b=0011010010
->001101

```

If this 1 is the last bit you cannot transmit it directly, because then you would send exactly the right end which is not within the interval. In this case you have to continue sending bits from the left side, until you hit the next 0. Here you transmit a 1, and you are done.

```
a=00110010101
b=00110011000
->0011001011

```
> 3 votes

# Answer
One method that comes to mind is computing in tandem the *next* value (in lexicographic order), and storing enough bits to separate the two. This doesn't incur double computation, since most of the time carry lasts only for the few last symbols.
> 1 votes

---
Tags: information-theory, data-compression
---


# Question
Title: How to find the minimal description for an array?
The following array occupies 10000 slots in memory:

```
a = [0,1,2,3,4,5,6,7,8,9,10,...,10000]

```

But one could easily represent the same array as:

```
a = {len:10000, get: λ idx -> idx}

```

Which is much more compact. Similarly, there are several arrays that can be represented compactly:

```
a = {a:1000, get: λ idx -> idx * 2}
Is a description for [0,2,4,6,8,10,...,2000]

a = {a:1000, get λ idx -> idx ^ 2}
Is a description for [0,1,2,4,9,...1000000]

And so on...

```

Providing so many arrays can be represented in much shorter ways than storing each element on memory, I ask:

1. Is there a name for this phenomena?
2. Is there a way to find the minimal representation for a specific array?
3. Considering this probably depends on the language of description (in this case, I used an imaginary programming language with functions, objects and math operators). Is there a specific language that is optimal for finding that kind of minimal description for objects?

# Answer
> 9 votes
The phenomenon you're describing is Kolmogorov complexity. Essentially, if you fix a programming language (or, more formally, a coding of Turing machines) then the Kolmogorov complexity $K(s)$ of a string $s$ is the length of the shortest program that outputs $s$ when started with no input. It turns out that, within reason, it doesn't matter what programming language you use, since using a different language makes at most a constant additive difference to $K(s)$. If you want to define Kolmogorov complexity with respect to some whacko language, I can just use that language to write an interpreter for a sensible language, so the Kolmogorov complexity of a string with respect to your language cannot be worse than the complexity in my language plus the fixed, constant overhead of the interpreter.

Like all interesting properties of Turing machines, the Kolmogorov complexity of a string is undecidable. However, this doesn't stop it being a useful concept and there's been a large amount of research on the subject.

# Answer
> 4 votes
If you look at this from a practical POV you can call it data compression. This is basically what data compression algorithms do: They define a language, and then try to represent the given data set in this language. But even for a very simple language it is very hard to find the optimal representation in that language. Take for example Deflate, despite being very simple there is still active research in how to apply it in an optimal way.

---
Tags: algorithms, complexity-theory, formal-languages, programming-languages, data-compression
---


# Question
Title: How does automatic differentiation work?
What is the intuitive idea behind automatic differentiation?

If I have a program which computes $f(x, y)=x^2+yx$, which steps lead to the program which computes the derivative $df/dx$ of f?

```
double f(double x, double y)
{
    double res = x*x;
    double res2 = x*y;
    double res3 = res + res2
    return res3;
}

```

If I read the corresponding Wikipedia entry correctly I need nothing besides the chain rule, but I don't understand how this can be done in practice.

My understanding so far is that I use a table of the derivatives of all involved basic functions, such as:

* $dx/dx=1$
* $dy/dx=0$
* $d(x\*y)/dx=y$
* $d(x+y)=dx/dx+0$
* $d(x^2)/dx=2x$

How do I get the final function from this?

I would expect something like this:

```
double f(double x, double y, double* dx)
{
    *dx = 0;
    double res = x*x;
    ? *dx = 2*x ?
    double res2 = x*y;
    ? *dx = *dx ?
    double res3 = res + res2
    ? *dx = ??? ?

    return res3;
}

```

---

*Edit:* I have found this video "Beautiful Differentiation" of a talk at the International Conference on Functional Programming (ICFP) 2009, by Marcom Wallace which explains the topic quite well.

# Answer
The function is given as a "decorated" tree. Your sample function has a root node decorated "+", with one child representing $x^2$ and the other $yx$. The first child has root node "^", with children "$x$" and "2", both leaves. The second child has root node "\*" with children "$y$" and "$x$".

In principle, automatic differentiation just applies the rules of differentiation recursively. In your case, we start with $\partial f/\partial x = \partial(x^2)/\partial x + \partial (yx)/\partial x$. To compute $\partial (yx)/\partial x$, we use the product rule: $$ \frac{\partial(yx)}{\partial x} = y \frac{\partial(x)}{\partial x} + \frac{\partial(y)}{\partial x} x. $$ For variables we know that $\partial x/\partial x = 1$ while $\partial y/\partial x = 0$, and simplification (one of the basic building blocks in any computer algebra system) gives $\partial(yx)/\partial x = y$. It is similar for $x^2$, though here the rule is more complicated: $(f^g)' = f^g (gf'/f+g'\log f)$.

In practice, there are probably some optimizations. Using pattern matching techniques (that is, by having specific rules) we can, for example, recognize $x^2$ for what it is, and directly calculate $\partial(x^2)/\partial x = 2x$. Similarly, if there is a subtree not depending on $x$, we could directly conclude that its derivative with respect to $x$ is zero.
> 6 votes

---
Tags: computer-algebra, computable-analysis
---


title: Solving AlienTiles with an A* heuristic

text:
# Question
Title: Solving AlienTiles with an A* heuristic
Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A\* algorithm but I cannot find any good heuristic function so far.

In AlienTiles you have a board with $N \times N$ tiles, all coloured red. By clicking on a tile, all tiles in the same row and column advance to the next color, with the colour order being red $\rightarrow$ green $\rightarrow$ blue $\rightarrow$ purple, resetting to red after purple. A goal state is a state where every tile has the same colour, as long as its not red.

Is there any good point to start? I am completely frustrated about how I am supposed to handle the problem. An easy function that I came up with was the distance of the colour of the current tile with the target tile, but it is very slow.

# Answer
> 3 votes
One candidate approach: for each color $c \in \\{\text{green}, \text{blue}, \text{purple}\\}$, try to define a distance heuristic $f\_c(\cdot)$ that approximates the distance to the specific goal of getting all tiles to be the color $c$. For instance, if $s$ is a state, then $f\_\text{green}(s)$ should be an estimate of the distance to the all-green state.

Next, given these heuristics, define a distance heuristic

$$f(s) = \min(f\_\text{green}(s), f\_\text{blue}(s), f\_\text{purple}(s)).$$

Then you could use $f$ as your distance heuristic with $A^\*$.

I leave it up to you to see if you can find a suitable definition of $f\_c(s)$. One candidate would be the number of tiles in $s$ whose color is not $c$, but that's probably not going to work; you'll probably need something smarter.

---

If you're willing to use something other than the $A^\*$ algorithm, there is an elegant solution to this problem using linear algebra.

Identify the colors red, green, blue, purple with the integers $0$, $1$, $2$, $3$, taken modulo 4 (so you are working in $\mathbb{Z}/4\mathbb{Z}$). Now you can solve the problem using linear algebra. In particular, the state $s$ is a $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$. Clicking on a tile at position $i,j$ corresponds to updating the state from $s$ to $s+v\_{i,j}$, where $v\_{i,j}$ is a fixed $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$. Thus, you can get from state $s$ to state $s'$ if and only if $s'-s$ is in the linear span of the $v\_{i,j}$. If it is in the span, then find coefficients $c\_{i,j} \in \mathbb{Z}/4\mathbb{Z}$ such that

$$s' - s = \sum\_{i,j} c\_{i,j} v\_{i,j},$$

and this will give you a solution method: for each $i,j$, click on tile $i,j$ exactly $c\_{i,j}$ times (order is irrelevant). You can use generalized Gaussian elimination to check whether $s'-s$ is in the span, and if so, to find the coefficients $c\_{i,j}$.

---
Tags: algorithms, search-algorithms, heuristics, board-games
---


# Question
Title: Finding a O(n) solution to: max difference of pairs array question
I don't know an O(n) solution to the following:

Given an array of n integers, find the largest difference between any two pairs in the array: however, the larger integer must have a higher index in the array than the other.

Ex: alg({9, 2, 6, 7}) = 5

It seems straightforward, yet it eludes me.

# Answer
> 5 votes
Create an array considering the minimum value seen so far in the array (in O(n)).

Ex. (9, 2, 2, 2)

Create an array containing the differences between the previous array and the original array (again, in O(n)).

Ex. (0, 0, 4, 5)

Find the maximum value in the array (O(n)). In this case, the answer is 5 as required.

This can be done in O(1) memory and only one pass if a few optimizations are made.

# Answer
> -1 votes
It is rather tempting to think that the problem asks for the largest and smallest integers in the array such that the larger integer has a higher index, and therefore forget about "largest difference". It is rather straightforward if you don't get trapped in thoughts like that! The code below solves the problem:

```
larger = array[1];
smaller = array[0];
smallest = array[0];
largest_difference = array[1]-array[0];

for(i=1; i<n-1; i++)
{
    if(array[i] < smallest)
        smallest = array[i];

    if( array[i+1] - smallest > largest_difference )
    {
        largest_difference = array[i+1] - smallest;
        smaller = smallest;
        larger = array[i+1];
    }
}

```

Proof: In short, for every integer X in the array starting from X=array\[1\], we know the smallest integer S before it. We compute its difference with this smallest integer (X-S), and so we know the largest difference as far as 'X' is concerned. As we do this for all X, we keep track of the largest of these 'largest differences'.

---
Tags: algorithm-analysis, arrays
---


title: Randomised Median

text:
# Question
Title: Randomised Median
I have tried hard , but i'm unable to come up with the expected running time for the number of comparisons to find the Randomized Median (find the median of an unsorted array). Also i wanted to make sure that we CANNOT take expectation of the recurrence that we use to find the randomized mean , or any other recurrence in any other problem as they belong to different probability spaces? Is this statement right?

# Answer
> 0 votes
One approach would be to form up a recurrence for the *expected* running time $T(n)$. At each stage there is $O(n)$ processing, and the result is a new list of length distributed according to some distribution $D\_n$ (for you to determine), and so we can write $$ T(n) = O(n) + \operatorname\*{\mathbb{E}}\_{m \sim D\_n} T(m). $$ This looks much less frightening when you substitute the actual distribution $D\_n$ and replace the expectation with a (weighted) sum. Then it remains to solve the recurrence.

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


# Question
Title: What can distributed computing do besides parallel computing?
I have some experiences of working on clusters and grids for parallel computing. But I wonder what distributed computing can do besides parallel computing? If I understand correctly, parallel computing is to solve a common task by multiple processors (computers).

Are the Internet and a intranet considered distributed systems? They don't necessarily involve parallel computing, or solving a common task by multiple computers.

# Answer
Distributed computing can be seen as a special case of parallel computing with some additional features and restrictions, some of which I'll outline here.

* **Multiply IO throughput**

In some settings, e.g. databases, IO is the main limiting factor of performance, e.g. hard drive accesses. By serving requests on many machines, you can parallelise hard drive accesses (not possible in typical many-core machines).
* **Avoid slow IO**

Real machines have technical limits regarding quick memory. These limits change constantly, but at any given point in time every machine can only hold so much data in RAM. A distributed system can be scaled so that *all* data resides in RAM, thus eliminating the need to resort to slower mediums.
* **Focus on throughput over response time**

When faced with many small requests already dominated by, say, IO, you can not speed up individual requests anymore. Having multiple nodes serve requests can increase throughput.
* **Redundancy**

Many nodes should be able to serve any given request so you can perform load balancing.
* **Consistency**

When a requests not only retrieves but also *changes* data, many nodes may need to be informed of these changes. This is probably the factor with the most impact on performance.
* **Failure tolerance**

The system as a whole should be robust against failure of individual nodes, i.e. continue to work (if with reduced throughput). This is not trivial since you can typically not hold all data on all nodes.
* **Communication cost**

In a distributed system, nodes typically communicate over some kind of network. Delays in the order of milliseconds (typical response times in Ethernet) are prohibitive for systems/algorithms that require frequent communication. In specialised network implementations, wire length actually becomes a significant factor in delay times *even inside a single server farm*.
* **Security**

If you don't control all aspects of the network connecting your nodes, the inner workings of your system are open to outside attack.

Note that all of these are interconnected.
> 4 votes

---
Tags: parallel-computing, distributed-systems
---


# Question
Title: Regular language concatenation with superset
Let $A$ be some alphabet.

$A$ itself is a regular language.

$E = A^\*$ is regular language over $A$. $E$ is a superset of all languages over $A$, regular or otherwise, i.e $E$ contains every possible string from symbols of $A$.

Now let $L$ be some regular language over $A$.

What is $\tilde{L} = L \cdot E$ ? More specifically, how $\tilde{L}$ and $E$ relate to each other? Are they equal? Is one subset of the other? Something else?

Source of the confusion is the following reasoning: closure under concatenation says that $\tilde{L}$ is a regular language and therefore $\tilde{L} \subseteq E$ (according to the above). On the other hand $\tilde{L}$ seems to contain strings $E$ does not, i.e. those that are formed by concatenating non-empty string from both languages.

Obviously this is wrong. What is going on here?

# Answer
> 2 votes
There is a very simple answer to your question: the equality $LA^\* = A^\*$ holds if and only if $L$ contains the empty word.

# Answer
> 3 votes
Simply put, this statement of yours:

> On the other hand $\tilde{L}$ seems to contain strings E does not, i.e. those that are formed by concatenating non-empty string from both languages.

is wrong.

As you say, $E$ contains *every* string containing only symbols from $A$. Since $L$ also only contains strings with symbols from $A$, $\tilde{L}$ must as well. Concatenating strings that have symbols only from $A$ will just get you *another* string whose symbols only come from $A$.

Your statement is flipped; it is $E$ that contains strings that $\tilde{L}$ may not.

---
Tags: formal-languages, regular-languages, closure-properties
---


title: Positive term for "unnegated"?

text:
# Question
Title: Positive term for "unnegated"?
I read a paper which talks about "a logic formula in which each variable appears at most twice unnegated and once negated". The term "unnegated" is double-negative, which makes it slightly unclear. Is there a more positive term to denote a variable that is not negated?

I looked in an English thesaurus, but all suggestions seem out-of-context in logic.

# Answer
> 6 votes
You can rephrase your statement as "a logic formula in which each variable appears at most twice positively and once negatively". This relies on the common usage of positive and negative *literals*.

# Answer
> 6 votes
You often see negative variables ($\neg x$) and positive variables ($x$). A literal is either a positive or a negative variable.

---
Tags: terminology, logic
---


# Question
Title: Runtime analysis of a "find the secret number" algorithm
> The algorithm task is to find an integer (range is not known). the function `guess(num)` returns one of three chars: '\>','\<' or '='.
> Find the secret number with `O(logS)` guesses, where `S` is the secret number. You can use `find_secret(N1, N2)` which operate with `O(log(N2-N1))`.. What it does is simply a binary search.

So, the algorithm implemented (with Python) as follows:

```
def find_secret2():
    low = 1
    high = 2
    answer = guess(high)
    while answer == ">":
        low *= 2
        high *= 2
        answer = guess(high)

    if answer == "=":
        return high
    return find_secret(low, high)

```

my thoughts about the complexity of this algorithm:

it takes `O(logS)` to reach the range where `low < secret < high`.
then, it takes `O(log(high-low))` \- because we're using `find_secret(N1, N2)` method.

I'll be glad if you could help me explain why the algorithm's complexity is `O(logS)` in a mathematical/rigorous way using the O-notation.
Thanks!

# Answer
You're almost there. It takes $O(\log S)$ time for your while loop to finish (by the way, how would you go about proving that? You can try induction on $\lceil \log\_2 S \rceil$ or on $\lfloor \log\_2 S \rfloor$, one of them should work). Then $\mathrm{low} \leq S \< \mathrm{high}$. Furthermore $\mathrm{low}$ and $\mathrm{high}$ are certain powers of two, and so you can relate $\mathrm{high}-\mathrm{low}$ to $S$. More concretely, you want to bound $\mathrm{high}-\mathrm{low}$ from above in terms of $S$. This is the part you're missing. Perhaps you should try a few concrete examples and then generalize.
> 3 votes

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


# Question
Title: Restricting longest path with 2-coloring to paths of at most constant length
I am trying to create a polynomial time algorithm for a problem defined as follows:

> ### c-ZPath(cZP)
>
> $c$ is an integer constant $\geq 1$
>
> **Input:** An undirected graph $G=(V,E)$.
>
> **Question:** Can the vertices in $G$ be colored with two colors such that
>
> 1. no edge’s endpoint vertices have the same color and
> 2. there is a path in this colored version of $G$ with $\geq c$ edges in which no vertex or edge repeats and the vertex-colors alternate for the entire length of the path?

I understand that the coloring can be checked by a simple breadth first search in polynomial time.

My problem is with the path of length $c$. My professor stated that the reason that this is not NP-complete and analogous to the longest path problem is because $c$ is a constant. I fail to see why this restriction causes it to differ from longest path. If anyone could clarify this for me I'd be really greatful.

# Answer
If you want to check whether a graph has a path of length $c$, you can go over all ordered sequences of $c+1$ vertices, and check whether all the edges in the corresponding path exist. On a RAM machine, this is an $O(n^{c+1})$ algorithm. When $c$ is constant, this is polynomial time.
> 1 votes

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


# Question
Title: Quicksort's asymptotic performance for array of [50,...,50,100,...100]
Let's have an array where first half are of value 50 and the second half 100. What would be the asymptotic performance when sorting using Quicksort.

I think it it should be $O(n^2)$ as for array of same elements the complexity is $O(n^2)$ and this particular problem could be rewritten as sorting the first half + sorting the second hald $O(2\*(\frac{n}{2})^2 + n)$ which is still $O(n^2)$.

But my schoolmates claim it should be $O(n log(n))$.. so which one is correct?

# Answer
That depends very much on exactly what quicksort variant you use. Perhaps you should take a peek at Sedgewick "Quicksort with equal keys", SIAM J. Comp 6:2 (jun 1977), pp 240-267 (get it here) or Bentley, McIllroy "Engineering a sort function", Software: Practice & Experience 23:11 (nov 1993), pp 1249-1265.
> 2 votes

# Answer
We can observe the input array given to the algorithm is already sorted. So at each step, the array is partitioned into two subarrays of size $n-1$ and 0 (why?). This gives us the recurrence $T(n) = T(n-1) + T(0) + \Theta(n)$. Can you now bound $T(n)$, and answer your question?
> 0 votes

---
Tags: algorithms, asymptotics, performance, quicksort
---


# Question
Title: How to structure device driver software?
I'm asking here for both the *scientific, programmatic, and structural format* of a device driver. What does that mean? Basically, **I'm not asking how to write a driver in general** ... I'm asking how to structure one to behave as software that can act as the "middleware" between higher-level code and the hardware itself. I've decided to embark on a journey of low-level computer programming (e.g. systems programming) to develop reusable software that can "expose" accessibility of hardware memory access by driver calls.

I basically run a freelance group of a small programming team/company, and I've decided to take on development across various retro-gaming platforms from the ground up (those which have decent documentation, or reverse engineering will endue). What I'm asking here is how would one envision the development or structure of software that can act as a intermediary between the application software and the hardware; developmentally, structurally, and programmatically. My choice of console was originally the Nintendo 64's GPU (which I have documentation for). The issue isn't with writing the code to access the GPU, it's with developing a reusable driver/graphics engine (I'm new to it).

I would have asked this at Programmers.SE, but they reject these kind of questions since they're not about specific programming issues, but about careful design methodologies, modularity, and structuring.

So I'll ask again with hope to receive a somewhat explanatory answer on this process ... **how do I go about the design methodology, structural format, or developmental logic to create a piece of software that can be accessed by other software to enable device access modularly? In other words, how do I structure and design a driver (i.e. what procedure should I take in creating such software)?**

Again, to clarify, **I am not asking how to write a driver, *but how to go about structuring the system, methodology, and behavior of a driver.*** Are there any specific ways of going about this that prove successful (e.g. certain data types to define behavior for accessibility, methods used in accessing parts of a driver independently, etc.)?

# Answer
> 1 votes
That very, very much depends on the kernel for which you are writing your driver. I'm (a bit) familiar with Linux. There are structures defined into which your drver *has* to hook. Those structures *define* most of the structure you are looking for, the driver itself just hooks into the kernel's structures on startup, gets its marching orders through a structure to be filled with function pointers for the relevant operations on the hardware. See Corbet, Rubini, Kroah-Harman "Linux Device Drivers" (3rd edition, get it here). It is somewhat dated, but the fundamentals haven't changed that much. The Linux Drivers Project gathers people trying to write drivers.

For a graphics card, the picture is quite different, I believe you'll find the above split between the kernel and X.org.

(The above general picture, with the kernel defining the overall architecture and the driver filling in the details of what object-oriented programming fans would call an "object" in an operating system defined device type "class" is the *only* reasonable way of structuring a non-toy, non-one-machine-only operating system. Most of the time written in C, not C++ or ($deity forbid) Java, but OO all the same.)

# Answer
> 0 votes
To write a device driver you need to first know about how the device works. If you have documentation for the N64 GPU then you're already in good hands. What you'd first want to do is read that documentation, and see how you could programmatically create an interface that can send, receive, measure, read, write, etc. A good example you can start with (and that's probably much easier) is a PS/2 mouse device driver. You'll send bytes, track the positional-axis that the mouse trackball/left/right click sends from its microchip to the port 0x60 or the like (if set up to do so; check the link above for more info). After that, you need to structure this input within the scope of a program that can make adequate calls to read/send information. This is, in general, the same way with any piece of hardware, but much more difficult with N64's GPU.

Another similar, and possibly even easier method is the equivalent PS/2 keyboard, which sends scan codes that are read, and simple flow-of-logic code can decide what to do with the bytes it receives. If you're working at a low-level like this you're probably familiar with assembly languages for various architectures, as these will almost always be necessary in some cases. It's a bit intense, but since you mentioned the N64 GPU I'll do my best to add this:

**To render graphics, the N64 CPU constructs a display list (GBI command list) and designates the RSP as the processor to use to render graphics. The RSP outputs the resulting graphic drawing into the frame buffer in RDRAM by simply reading and executing the display list provided by the CPU. The accumulated content of the frame buffer is output as a video signal from the video DAC (digital-to-analog converter) by way of the VI (video interface). The following diagram summarizes this process(check N64's Wiki for all of the abbreviations mentioned):**

You'd probably want to operate through DMA, and you should be aware of the memory map for the N64.

DMA registers: **$A460:0000 = RAM address (address & 0x00FFFFFF) $A460:0004 = ROM address (address & 0x1FFFFFFF) $A460:0008 = Transfer size (from RAM to cartridge) $A460:000C = Transfer size (from cartridge to RAM) $A460:0010 = DMA Status**

And here's the entire memory map:

0x0000 0000 to 0x03EF FFFF RDRAM Memory

0x03F0 0000 to 0x03FF FFFF RDRAM Registers

0x0400 0000 to 0x040F FFFF SP Registers

0x0410 0000 to 0x041F FFFF DP Command Registers

0x0420 0000 to 0x042F FFFF DP Span Registers

0x0430 0000 to 0x043F FFFF MIPS Interface (MI) Registers

0x0440 0000 to 0x044F FFFF Video Interface (VI) Registers

0x0450 0000 to 0x045F FFFF Audio Interface (AI) Registers

0x0460 0000 to 0x046F FFFF Peripheral Interface (PI) Registers

0x0470 0000 to 0x047F FFFF RDRAM Interface (RI) Registers

0x0480 0000 to 0x048F FFFF Serial Interface (SI) Registers

0x0490 0000 to 0x04FF FFFF Unused

0x0500 0000 to 0x05FF FFFF Cartridge Domain 2 Address 1

0x0600 0000 to 0x07FF FFFF Cartridge Domain 1 Address 1

0x0800 0000 to 0x0FFF FFFF Cartridge Domain 2 Address 2

0x1000 0000 to 0x1FBF FFFF Cartridge Domain 1 Address 2

0x1FC0 0000 to 0x1FC0 07BF PIF Boot ROM

0x1FC0 07C0 to 0x1FC0 07FF PIF RAM

0x1FC0 0800 to 0x1FCF FFFF Reserved

0x1FD0 0000 to 0x7FFF FFFF Cartridge Domain 1 Address 3

0x8000 0000 to 0xFFFF FFFF External SysAD Device

**Some more info for further reading (even though it may not 100% help):**

RSP(Reality Signal Processor)

RSP is your transform and lighting unit (TnL). Manipulates world data and textures.

Mathematically, lots of matrices to transform from local data -\> world space -\> view space (projection w/ z-perspective correction).

Transform means scaling, translating and rotating for polygons, lighting normals, texture UVs.

Creates primitive lists of triangles and lines for the RDP to render.

RDP(Reality Drawing Processor)

RDP is the display unit.

Rasterizer, fog, environmental, color blending. Anti-aliasing effects.

Lower-level pixel handler.

uCodes

The RCP has its own language, dubbed 'uCodes' (256 microcodes).

Think of modern vertex and pixel DirectX shaders - both stages combined.

R4000 coprocessor (COP2). Each uCode is a string of ASM instructions run by the RSP. Also sets up the RDP batch renderer.

Display lists are a sequence of uCodes defined by the game. This is fed to the RSP.

Note: Emulator authors choose to translate uCodes into higher-level languages.

The programmers can define their own vertex / texture formats. Lighting methods. Overdraw detection and other flexible wizardry.

The microcodes are uploaded to the RCP at run-time. So each game has its own library of drawing functions (some are like DSP1 -\> DSP1A -\> DSP1B and others are akin to DSP2,DSP3).

But I'll just go all out here for the N64:

Main 2D Drawing Routine The main drawing routine forms the executing core for the 2D image drawing sample. The process is completed in three steps that are executed over and over in a loop:

Construct the display list in the CPU. Transfer the display list to the RCP for execution. The RCP creates the actual display data and outputs the video signal by way of the frame buffer, VI, and video DAC as previously outlined in this chapter. Keep the CPU and RCP processes in sync, and return to step 1. The following code points to the display list, sets the sprite size, and sets up the loop(all psuedocode):

```
void entry(void)

{

 Gfx *gp;  /* points to display list */

 u16 w, h;

 w=64; h=64;  /* sets up sprite size */

 while(1){

```

Step 1 -- Construct the display list The following code reserves the necessary memory area for the construction of the display list, sets up the RCP execution process for sprite drawing in the reserved area, and provides a termination process for the constructed display list. Each code snippet is followed by s short explanation.

```
 /* Start to construct a display list */

gp = gfxBegin(1024);

```

This code checks to see if a display list has already been constructed. If a display list hasn't been completed, this code reserves the GBI command area for new construction. If it has been completed, this code moves on to step 2, the process that transfers the display list to the RCP.

```
/* Set the drawing mode for RSP and RDP */

gp = setup_SP_DP(gp);

```

This code constructs a command that sets the necessary RCP drawing mode, and then adds that command to the display list.

```
/* Accept the texture pattern */

gp = load_texture(gp,w,h);

```

This code sets up a texture pattern loading command in the display list.

```
/* Write the texture pattern */

gp = draw_texture(gp,124,92,w,h);

```

This code sets up a texture drawing command in the display list.

```
/* End the construction of display list */

gfxEnd(gp);

```

This code terminates the display list.

Caution: Watch out for an unterminated display list. If it is transferred to the RCP, it will cause the RCP to hang (stop responding). Also, be sure to put the gDPFullSync function at the end of each display list. Otherwise, the RDP end message won't ever come.

Step 2 -- Transfer the display list to the RCP to execute the drawing process The following code transfers the display list to the RCP where the display list is interpreted and executed. /\* Transfer display list to RCP \*/

```
gfxFlush( );

```

This code transfers the display list to the RCP where it is executed. This function also provides the frame buffer switch that writes the created image data into the frame buffer.

Step 3 -- Synchronize the CPU with the RCP The following function ensures coordination between the CPU and RSP:

```
/* Wait for the retrace */

gfxWaitSync( );

 }

}

```

Techniques for Construction of the Display List The actual construction of the display list uses one of these processes:

Set the RSP and RDP Drawing Modes Set and Read the Texture Set the Drawing Sequence of the Bitmap Pattern Set the RSP and RDP Drawing Modes The following routines set the RCP drawing mode that actually creates the commands that render the drawing reflected in the display list.

The gSP and gDP functions are included in the N64 library; for more information about them, please see the online N64 Function Reference Manual (HTML manual pages).

```
static Gfx *setup_SP_DP(Gfx *gp)

{

/* Set all sorts */

/* Set the texturing parameter */

gSPTexture(gp++,0x8000,0x8000,0,

   G_TX_RENDERTILE,G_ON);

/* The synchronous setting between the

   rendering and the sub-attribute */

gDPPipeSync(gp++);

/* Set the RDP cycle type */

gDPSetCycleType(gp++,G_CYC_COPY);

/* Set the rendering mode of the

   blender within RDP */

gDPSetRenderMode(gp++,G_RM_NOOP,G_RM_NOOP2 );

/* Set the texture LOD */

gDPSetTextureLOD(gp++,G_TL_TILE);

/* Set the perspective of the texture map */

gDPSetTexturePersp(gp++,G_TP_NONE);

/* Set the detail type */

gDPSetTextureDetail(gp++,G_TD_CLAMP);

/* Set the texture filter type */

gDPSetTextureFilter(gp++,G_TF_BILERP);

/* Set the conversion mode of

   the color space */

gDPSetTextureConvert(gp++,G_TC_FILT);

/* Set the compare mode of the alpha value */

gDPSetAlphaCompare(gp++,G_AC_NONE);

/* Set the dithering mode of the color data */

gDPSetColorDither(gp++,G_CD_DISABLE);

/* Set the dithering mode of the alpha value */

gDPSetAlphaDither(gp++,G_AD_NOISE);

return gp;

}

```

Set and Read the Texture The gDP functions are included in the N64 library; for more information about them, please see the online N64 Function Reference Manual (HTML manual pages).

```
static Gfx *load_texture(Gfx *gp,u16 w,u16 h)

{

/* Read TLUT */

/* Set the texture look-up table */

gDPSetTextureLUT(gp++,G_TT_RGBA16);

/* Read the texture look-up table */

gDPLoadTLUT_pal16(gp++,0,texturetlut);

/* Read the bitmap pattern */

gDPLoadTextureTile_4b(gp++,texture,

   G_IM_FMT_CI,w,h,

   0,0,w-1,h-1,0,

   G_TX_WRAP | G_TX_NOMIRROR,G_TX_WRAP |

   G_TX_NOMIRROR,

   G_TX_NOMASK,G_TX_NOMASK,G_TX_NOLOD,

   G_TX_NOLOD);

return gp;

}

```

Set the Drawing Sequence for a Bitmap Pattern The following code sets the drawing sequence for an accepted texture image. The gSP functions are included in the N64 library; for more information about them, please see the online N64 Function Reference Manual(HTML manual pages).

```
static Gfx *draw_texture(Gfx *gp,

   u16 left,u16 top,u16 w,u16 h)

{

/* The bitmap pattern drawing */

gSPTextureRectangle(gp++,

   left<<2,top<<2,((left+w)<<2)-1,

   ((top+h)<<2)-1,

   G_TX_RENDERTILE,

   0,0,4<<10,1<<10);

   return gp;

}

```

---
Tags: operating-systems, software-engineering, api-design
---


# Question
Title: Is the language with decreasing numbers of a, b and c context-free by pumping lemma?
So I've been given the following language on an assignment. It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours.

$$L=\\{w:w\in(a+b+c)^\*, n\_a(w) \> n\_b(w)\>n\_c(w)\\}$$

where $n\_x(w)$ represents the number of character $x$ found in $w$. The problem statement is: **prove or disprove that the language is context-free**. Context-free grammars or pushdown automata are acceptable proofs. Use pumping lemma to disprove.

I've extensively explored both possibilities and I'm fairly certain that it is context-free.

The approach I've taken in finding a context-free grammar for the language involves using rules which preserve the constraint $n\_a(w) \> n\_b(w) \> n\_c(w)$ (ie. whenever a $b$ is added, add an $a$; whenever a $c$ is added, add a $b$). Then, I've attempted to enforce that there are at least two $a$s and at least one $b$ (base case for the constraint).

The grammar I've used is:

$S\implies XaXaXbX | XaXbXaX | XbXaXaX$

$X \implies XX| A | B | C | \lambda$

$A \implies a$

$B \implies ab | ba$

$C \implies abc | acb | bac | bca | cab | cba$

(where $\lambda$ is the empty string)

My grammar fails for strings like $cccaaaaabbbb$.

I'm confused as to where to go from here.

**I would really like a push in the right direction, not an answer.** Any help is greatly appreciated!

# Answer
> 3 votes
If your language is context free, so is its intersection with the regular language $a^\* b^\* c^\*$. And your proof in the answer that this isn't context free does go through. Your proof omits the cases where one of the strings straddles the $a/b$ or $b/c$ boundaries.

# Answer
> -2 votes
The following is my attempt at an answer. I took a screenshot of my assignment, rather than retyping the proof into StackExchange.

Comments?

---
Tags: context-free, formal-grammars, pumping-lemma, pushdown-automata
---


# Question
Title: Drawing Annotated Parse Tree for Syntax Directed Definition
Im trying to draw an annotated parse tree for `3*5+4n`, the text book shows the following:

<sup>\[*Compilers - Principles, techniques and tools (Dragon Book) by Aho, p308*\]</sup>

I have a few questions regarding this

1. Why is `3*5+4` considered as a single string? Can't I draw a parse tree something like for the same string ie:with operator at the node
2. What is the need for giving `T.VAL=3` and then giving another child `F.VAL=3`. (I understand that the integer attribute for digit needs to be supplied by the lexical analyzer)

# Answer
> 2 votes
The Dragon book style starts with the parse tree of the expression, i.e., the root (I think the very top is a mistake, the expression is an error as written) is the step $E \Rightarrow E + T$. The tree is then decorated giving the attributes their value (like $E.val = 19$). In an attributed grammar you give the grammar and the attributes, so that the grammar looks in part as (subindices mark diferent uses of the same symbol, left to right): \begin{eqnarray} E \rightarrow T \quad E.val \leftarrow T.val \\ E \rightarrow E + T \quad E\_0.val \leftarrow E\_1.val + T.val \end{eqnarray} You see that the answer to your second question is that the value of the child $F$ is used to compute the value of $T$.

# Answer
> 1 votes
I would say, yes, you may draw the parse tree as you have presented it. Your presentation is more abstract than the one from the textbook.

On one hand, this means that it will be easier to manipulate. But it does also mean that things like generating accurate and useful error messages will be much more difficult, depending of course on what sort of information has been abstracted away.

Beyond this, I cannot answer the remainder of your question. I don't even know what textbook you are talking about – that is, you've copied the page without proper citation.

---
Tags: formal-grammars, compilers, parsing, syntax-trees
---


title: Provability of NP /= P?

text:
# Question
Title: Provability of NP /= P?
I'm a novice to the topic of provability so bear with me...

During a discussion with a friend, the question came up whether it could be possible that proving that $NP \neq P$ (or $NP = P$) is an unprovable statement. My friend opposed that, if indeed it was unprovable, then this would imply that there cannot be a polynomial time algorithm for NP-hard problems (as the existence of such proves the statement), thus implying $NP \neq P$. This seems to be imply that the statement cannot be unprovable or am I missing something?

# Answer
Statements that are independent are not *true* or *false*, their truth value just cannot be decided given the axioms. For example, consider natural numbers. It is true that a given number is a product of primes. It is unprovable that a given number is prime, nor that it is not prime – since it depends on the number. For each given number, it is either prime or not, but it depends.

The same goes for independent statements – the "number" is here replaced with the set-theoretic universe (or whatever universe you base your logic in). It could be that in some universes P equals NP, while in some universes the two are different. The "real world" is one of these particular universes, but as Gödel showed, it is impossible to completely describe the real world: there will always be independent statements. When faced with one, we could try to find other properties of the real world which help determine the statement. This approach hasn't fared so well on the canonical example, the continuum hypothesis.

Despite the foregoing, it is not considered likely that the P vs. NP question is one of these independent statements. That's a declaration of faith. Even though it seems hard to settle, most theoreticians believe that it is just a difficult question, similar to many other difficult questions in mathematics, some of which have been solved one way or another (for example, Fermat's last theorem), some of them haven't (for example, the Riemann hypothesis).
> 5 votes

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


# Question
Title: Compute minimum hamming distance of a code
How do you find the minimum hamming distance of a code?
A naive way is computing the distance of each pair of codewords in our code.

It becomes hard when the code is sufficiently large. Is there a formula for minimum hamming distance?

# Answer
When the code is linear, there is no need to go over all pairs of codewords, due to linearity. Indeed, since $d(x,y) = d(x\oplus y, 0)$ and for any two codewords $x,y \in C$, linearity implies that $x\oplus y \in C$, we see that the minimal distance is the minimal weight of a non-zero codeword. There are other ways characterization of the minimal distance, for example in terms of the generator matrix. See also this question.

By the way, an $(n,k,d)$-code is one with $2^k$ codewords of length $n$ and minimal distance $d$. So if you have a $(7,4,3)$-code, the minimal distance must be...?
> 3 votes

---
Tags: string-metrics, coding-theory
---


# Question
Title: Why is the halting problem unsolvable by a turing machine?
So my knowledge of CS is amateurish at best but to me, logically, it seems like the halting problem is solvable.

So any human can determine if a problem halts with rigorous inspection, so why can't a very advanced, say human AI, solve the halting problem?

Also, is there a machine, say more powerful than a turing machine, that can solve this problem?

PS: I might be making some bad assumptions, please point that out if so.

# Answer
> 7 votes
It can be proved that the halting problem cannot be solved by any Turing machine. There are several question regarding this on this side which you can look up.

It is *not* true that humans can determine if a given Turing machine halts. For example, we have been unable so far to compute many values of busy beaver functions, which measure the maximal number of steps a halting Turing machine can run given the number of tape symbols and number of states.

According to the Church–Turing thesis, every machine can be simulated by a Turing machine. So DNA computers, quantum computers and the like will not help. All they can do (especially the latter) is to dramatically speed up computation, but they cannot help computing non-computable functions.

There is a field known as *hyper-computation* which studies machines stronger than Turing machines, but these are not believed to be realizable by most practitioners. *Recursion theory* explores such models from a more theoretical perspective.

# Answer
> 7 votes
The major bad assumption is that "any human can determine if a problem halts with rigorous inspection". The strong Goldbach conjecture states that every even integer greater than 2 can be expressed as the sum of two primes. So consider the following program.

```
n = 4
loop
  if there exists two primes p and q and p + q = n then
    n = n + 2
  else
    return
  endif
end loop

```

The program loops until it finds an even integer that can't be expressed as the sum of two primes. So if it halts, the conjecture is proven false. If indeed "any human could determine if a program halts", we could settle this, and several other famous conjectures (at least theoretically).

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


# Question
Title: Why can any polynomial and exponential be represented as a recurrence?
I posted this question on math.SE but I haven't got any reply so I'm posting here also.

I am reading The Algorithm Design Manual by Steven S Skiena.

In Section 4.10.1 Recurrence Relations, I understand what a recurrence relation is, but after that following statements have been given:

> Any polynomial can be represented by a recurrence, such as the linear function:
> $a\_n = a\_{n-1} + 1, a\_1 = 1 \implies a\_n = n$
>
> Any exponential can be represented by a recurrence:
> $a\_n = 2a\_{n-1}, a\_1 = 1 \implies a\_n = 2^{n-1}$

Can anyone explain me the above statements by proving them for any linear function and exponential function, respectively?

EDITED : After help from Raphael and Yuval Filmus , I concluded following prove. Correct me if I am wrong

---

For any Liner function, General form is $a\_n = \alpha n + \beta$
$a\_n - a\_{n-1} = \alpha n + \beta - (\alpha (n-1) + \beta)$
$a\_n - a\_{n-1} = \alpha n + \beta - \alpha n + \alpha - \beta$
$a\_n - a\_{n-1} = \alpha \implies a\_n = a\_{n-1} +\alpha $
As relation holds in question, $a\_n = a\_{n-1} + 1 \implies \alpha = 1 $
Now,
$a\_{n-1} = a\_{n-2} + \alpha , a\_{n-2} = a\_{n-3} + \alpha , a\_{n-3} = a\_{n-4} + \alpha , ...$
Therefore, we can expres $a\_{n}$ in terms of $a\_{n-2}$ and so on
$a\_{n} = a\_{n-2} + \alpha + \alpha \implies a\_{n} = a\_{n-2} + 2\alpha $
We can generalize
$a\_{n} = \alpha + (n-1)\alpha \implies a\_{n} = n\alpha $
As $\alpha = 1 \implies a\_{n} = n$

---

For Exponential, General form is $a\_n = cb^n$
$a\_n - a\_{n-1} = cb^n - cb^{n-1} \implies a\_n - a\_{n-1} = cb^n - cb^n . b^{-1}$
$a\_n - a\_{n-1} = cb^n\left(1 - \dfrac{1}{b}\right) $
Substitute $a\_n = cb^n$
$a\_n - a\_{n-1} = a\_n\left(1 - \dfrac{1}{b}\right) $
$a\_{n-1} = \dfrac{a\_n}{b} \implies a\_{n} = ba\_{n-1} $
As relation holds in question, $a\_n = 2a\_{n-1} \implies b = 2 $
Now, $a\_n = cb^n \implies a\_1 = cb^1$
Substitute $a\_1 = 1$ and $b=2 \implies c = \dfrac{1}{2}$
Substitute c and b in general form i.e. $a\_n = cb^n$
$a\_n = \dfrac{1}{2}2^n \implies a\_n =2^n2^{-1} \implies a\_n = 2^{n-1} $

# Answer
> 3 votes
The general form for a polynomial is $a\_n = \sum\_{i=0}^k c\_i n^i$. Thus, for $n\>0$, we have $$a\_n - a\_{n-1} = \sum\_{i=0}^k c\_i n^i - \sum\_{i=0}^k c\_i (n-1)^i,$$ which can be transformed into the recurrence $$a\_n = a\_{n-1} + \sum\_{i=0}^k c\_i n^i - \sum\_{i=0}^k c\_i (n-1)^i,~~~ a\_0 = c\_0.$$

For exponentials, the general form is $a\_n = c\cdot b^n$. In complete analogy to the example in the book, this is generated by the recurrence $$a\_n = b\cdot a\_{n-1},~~~ a\_0 = c.$$

# Answer
> 2 votes
Suppose that we are given a polynomial $P$ of degree $d-1$. Consider the following recurrence relation:

$$f(n) = \sum\_{k=1}^d (-1)^{k+1} \binom{d}{k} f(n-k).$$

I claim that every polynomial of degree $d-1$ satisfies this recurrence relation; this is shown below. The space of solutions is $d$-dimensional, since we can set (for example) $f(1),\ldots,f(d)$ in any way we want. Since there are also $d$ degrees of freedom for $P$, we conclude that by setting the initial values $f(1),\ldots,f(d)=P(1),\ldots,P(d)$, we get $f(n) = P(n)$ for all $n$.

For example, if $P(n) = \alpha n + \beta$ then the resulting recurrence is $f(n) = 2f(n-1) - f(n-2)$ with initial values $P(1) = \alpha + \beta$ and $P(2) = 2\alpha + \beta$.

---

We now prove that every polynomial of degree $d-1$ satisfies the recurrence stated above. Since the recurrence is homogeneous, it is enough to show that for $0 \leq t \leq d-1$,

$$ \sum\_{k=0}^d (-1)^k \binom{d}{k} (n-k)^t = 0. $$

Opening up the binomial, we get

$$ \sum\_{k=0}^d (-1)^k \binom{d}{k} \sum\_{\ell=0}^t (-1)^\ell \binom{t}{\ell} n^{t-\ell} k^\ell = 0. $$

It is thus enough to show that for $0\leq\ell\leq d-1$,

$$ \sum\_{k=0}^d (-1)^k \binom{d}{k} k^\ell = 0. $$

The linear span of $k^0,\ldots,k^{d-1}$ is spanned by the "falling powers" $1,k,k(k-1),\ldots,k(k-1)\cdots(k-d)$. So it is enough to show that for $0\leq\ell\leq d-1$,

$$ \sum\_{k=0}^d (-1)^k \binom{d}{k} k(k-1)\cdots(k-\ell+1) = 0. $$

This quantity is equal to

$$ d(d-1)\cdots(d-\ell+1) \sum\_{k=\ell}^d (-1)^k \binom{d-\ell}{k-\ell} = d\cdots(d-\ell+1) (1-1)^{d-\ell} = 0, $$

using the binomial theorem.

---

Exponentials are easier, as demonstrated by FrankW's answer.

---

The functions expressible using recurrence relations with constant coefficients are all of the following form: for some $n\_0$ and all $n \geq n\_0$, $$ f(n) = \sum\_i P\_i(n) \lambda\_i^n, $$ where $\lambda\_i$ are arbitrary complex numbers and $P\_i$ are arbitrary complex polynomials. The proof uses Jordan canonical form. Above we have seen two special cases of the *converse*. Here's a question for you to ponder: can any function of this form be realized by a recurrence relation?

---
Tags: recurrence-relation, discrete-mathematics
---


# Question
Title: What's an example of an unsatisfiable 3-CNF formula?
I'm trying to wrap my head around an NP-completeness proof which seem to revolve around SAT/3CNF-SAT.

Maybe it's the late hour but I'm afraid I can't think of a 3CNF formula that cannot be satisfied (I'm probably missing something obvious).

Can you give me an example for such formula?

# Answer
Technically, you can write $x\wedge \neg x$ in 3-CNF as $(x\vee x\vee x)\wedge (\neg x\vee \neg x\vee \neg x)$, but you probably want a "real" example.

In that case, a 3CNF formula needs at least 3 variables. Since each clause rules out exactly one assignment, that means you need at least $2^3=8$ clauses in order to have a non-satisfiable formula. Indeed, the simplest one is:

$$(x\vee y\vee z)\wedge (x\vee y\vee \neg z)\wedge (x\vee \neg y\vee z)\wedge(x\vee \neg y\vee \neg z)\wedge(\neg x\vee y\vee z)\wedge(\neg x\vee y\vee \neg z)\wedge(\neg x\vee \neg y\vee z)\wedge(\neg x\vee \neg y\vee \neg z)$$ It is not hard to see that this formula is unsatsifiable.
> 35 votes

# Answer
If you want more complex examples of such formulas, have a look some benchmark problems of SATLIB. ToughSAT is also a nice tool for creating 3-SAT instances; it's easy to build both satisfiable and unsatisfiable instances.
> 9 votes

---
Tags: logic, satisfiability, 3-sat
---


# Question
Title: What are the difference between and consequences of using type parameters and type indexes?
In type theories, like Coq's, we can define a type with parameters, like this:

```
Inductive ListP (Element : Type) : Type
  := NilP  : ListP Element
   | ConsP : Element -> ListP Element -> ListP Element.

```

Alternatively, we can define a type with an index, like this:

```
Inductive ListI : Type -> Type
  := NilI  : forall t, ListI t
   | ConsI : forall t, t -> ListI t -> ListI t.

```

My questions are:

* Are these fundamentally different or fundamentally the same?
* What are the consequences of using one over the other?
* When is it preferable to use one over the other?

# Answer
`ListP t` and `ListI t` are isomorphic: they have exactly the same constructors.

```
<prompt>Coq < 12 || 0 < </prompt>Check (NilP, NilI).
(NilP, NilI)
     : (forall t : Type, ListP t) *
       (forall t : Type, ListI t)

<prompt>Coq < 13 || 0 < </prompt>Check (ConsP, ConsI).
(ConsP, ConsI)
     : (forall t : Type, t -> ListP t -> ListP t) *
       (forall t : Type, t -> ListI t -> ListI t)

```

However Coq generates different induction principles.

```
<prompt>Coq < 14 || 0 < </prompt>Check (ListP_ind, ListI_ind).
(ListP_ind, ListI_ind)
     : (forall (t : Type) (P : ListP t -> Prop),
        P (NilP t) ->
        (forall (t0 : t) (l : ListP t), P l -> P (ConsP t t0 l)) ->
        forall l : ListP t, P l) *
       (forall P : forall T : Type, ListI T -> Prop,
        (forall t : Type, P t (NilI t)) ->
        (forall (t : Type) (t0 : t) (l : ListI t),
         P t l -> P t (ConsI t t0 l)) ->
        forall (T : Type) (l : ListI T), P T l)

```

The induction principle of `ListI` requires the property to be parameteric in the element type (`P : forall T, ListI T -> Prop`) whereas the induction principle of `ListP` can be instantiated at any type `t` (`P : ListP t -> Prop`). This is a weakness of Coq's front-end, in that it is not smart about non-uniform recursive types; you can manually define the same induction principle (the typechecker accepts it, which is unsurprising given that it is `ListP_ind` transformed by the obvious isomorphism between `ListP` and `ListI`).

The parametric form `ListP` is simpler and easier to use out of the box. The `ListI` form can generalize to non-uniform recursion, where the parameters in the recursive calls are not the original. See Polymorphism and Inductive datatypes for an example.
> 8 votes

# Answer
I've also found the following quite useful, especially the comments:

http://homotopytypetheory.org/2011/04/10/just-kidding-understanding-identity-elimination-in-homotopy-type-theory/

> The reason is that the identity type Id A M N is “parametrized” by A and M, but “indexed” by N. This terminology expresses the difference between “a family of inductively defined types” (where the arguments of the family are called parameters) and “an inductively defined family of types” (where the arguments are called indices). Parameters come before the ‘mu’ (for each choice of parameters, there is an inductive type). Indices are “in the loop”—you are simultaneously defining the whole family of types at once, so different instances of the family can refer to each other. As a consequence, indices can occur non-uniformly (e.g. in the result type of constructors), whereas parameters are fixed once and for all.
> 4 votes

---
Tags: type-theory, dependent-types
---


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

> Construct a graph G = (V, E) as follows:
>
> Vertices: Each literal corresponds to a vertex.
>
> Edges: All vertices are connected with an edge except the vertices of the same clause and vertices with negated literals.

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

# Answer
The goal of the reduction is to enforce the fact that a clique of the graph of size $|Clauses|$ is exactly a valid instanciation of the variables satisfying all clauses of the formula.

So by not connecting variables of the same clause together, you force a clique of size $|Clauses|$ to pick one variable in each clause, setting it to true.

However, you don't want this instanciation to contradict itself: you cannot have $x$ and $\neg x$ true at the same time. For instance the formula with two clauses $x\wedge \neg x$ should not be satisfiable. So you forbid a clique to contain a variable and its negation, by not connecting them together. Therefore, a clique has to be coherent, so it always represents a valid instanciation. Notice that it can be only a partial instanciation, in which case you can choose anything for the remaining variables.
> 1 votes

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

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